当前位置： 文江博客话题详情

为什么归并排序最坏情况运行时间是O(n log n)？

发布于 2024-12-10 04:37:32 字数 29 浏览 0 评论 0原文

有人可以用简单的英语或简单的方法向我解释吗？

原文

Can someone explain to me in simple English or an easy way to explain it?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（9）

烟酒忠诚 2024-12-17 04:37:32

归并排序使用分治方法来解决排序问题。首先，它使用递归将输入分成两半。划分后，它对两半进行排序并将它们合并为一个排序的输出。参见图

MergeSort recursion tree

这意味着最好先对问题的一半进行排序，然后执行一个简单的合并子例程。因此，了解合并子例程的复杂性以及在递归中调用它的次数非常重要。

合并排序的伪代码非常简单。

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

很容易看出，在每个循环中都会有 4 个操作：k++、i++ 或 j++、if 语句 strong> 和归因 C = A|B。因此，您将需要执行少于或等于 4N + 2 次操作，复杂度为 O(N)。为了证明，4N + 2 将被视为 6N，因为对于 N = 1 (4N +2 <= 6N) 成立。

因此，假设您有一个包含 N 个元素的输入，并假设 N 是 2 的幂。在每个级别，您都会遇到两倍多的子问题，其中输入包含前一个级别的一半元素输入。这意味着在 j = 0, 1, 2, ..., lgN 级别，将存在 2^j 个输入长度为 N 的子问题/ 2^j 。每个级别j的操作数量将小于或等于

2^j * 6(N / 2^j) = 6N

请注意，无论级别如何，您总是有少于或等于 6N 次操作。

由于有 lgN + 1 个级别，因此复杂度为

O(6N * (lgN + 1)) = O(6N*lgN + 6N) = O(n lgN)

参考文献：

The Merge Sort use the Divide-and-Conquer approach to solve the sorting problem. First, it divides the input in half using recursion. After dividing, it sort the halfs and merge them into one sorted output. See the figure

MergeSort recursion tree

It means that is better to sort half of your problem first and do a simple merge subroutine. So it is important to know the complexity of the merge subroutine and how many times it will be called in the recursion.

The pseudo-code for the merge sort is really simple.

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

It is easy to see that in every loop you will have 4 operations: k++, i++ or j++, the if statement and the attribution C = A|B. So you will have less or equal to 4N + 2 operations giving a O(N) complexity. For the sake of the proof 4N + 2 will be treated as 6N, since is true for N = 1 (4N +2 <= 6N).

So assume you have an input with N elements and assume N is a power of 2. At every level you have two times more subproblems with an input with half elements from the previous input. This means that at the the level j = 0, 1, 2, ..., lgN there will be 2^j subproblems with an input of length N / 2^j. The number of operations at each level j will be less or equal to

2^j * 6(N / 2^j) = 6N

Observe that it doens't matter the level you will always have less or equal 6N operations.

Since there are lgN + 1 levels, the complexity will be

O(6N * (lgN + 1)) = O(6N*lgN + 6N) = O(n lgN)

References:

回复 原文
氛圍 2024-12-17 04:37:32

在“传统”合并排序中，每次遍历数据都会使已排序子部分的大小加倍。第一次通过后，文件将被分为长度为 2 的部分。第二遍后，长度为四。然后是八个、十六个等等，直到达到文件的大小。

有必要不断地将已排序部分的大小加倍，直到有一个部分包含整个文件。需要 lg(N) 倍的节大小才能达到文件大小，并且每次传输数据所需的时间与记录数成正比。

On a "traditional" merge sort, each pass through the data doubles the size of the sorted subsections. After the first pass, the file will be sorted into sections of length two. After the second pass, length four. Then eight, sixteen, etc. up to the size of the file.

It's necessary to keep doubling the size of the sorted sections until there's one section comprising the whole file. It will take lg(N) doublings of the section size to reach the file size, and each pass of the data will take time proportional to the number of records.

回复 原文
擦肩而过的背影 2024-12-17 04:37:32

将数组拆分到具有单个元素（即称为子列表）的阶段后，

  • 在每个阶段，我们将每个子列表的元素与其相邻子列表进行比较。例如，[重复使用@Davi 的图像
    ]

    在此输入图像描述

    1. 在第 1 阶段，每个元素都会与其相邻元素进行比较，因此进行 n/2 次比较。
    2. 在阶段2，子列表的每个元素都会与其相邻的子列表进行比较，因为每个子列表都是排序的，这意味着两个子列表之间进行比较的最大次数是<=子列表的长度，即2（在阶段-2) 和第 3 阶段的 4 次比较和第 4 阶段的 8 次比较，因为子列表的长度不断加倍。这意味着每个阶段的最大比较次数 = (子列表长度 * (子列表数量/2)) ==> n/2
    3. 正如您所观察到的，总阶段数将为 log(n) 以 2 为底
      因此总复杂度为 == (每个阶段的最大比较次数 * 阶段数) == O((n/2)*log(n)) ==> O(nlog(n))

After splitting the array to the stage where you have single elements i.e. call them sublists,

  • at each stage we compare elements of each sublist with its adjacent sublist. For example, [Reusing @Davi's image
    ]

    enter image description here

    1. At Stage-1 each element is compared with its adjacent one, so n/2 comparisons.
    2. At Stage-2, each element of sublist is compared with its adjacent sublist, since each sublist is sorted, this means that the max number of comparisons made between two sublists is <= length of the sublist i.e. 2 (at Stage-2) and 4 comparisons at Stage-3 and 8 at Stage-4 since the sublists keep doubling in length. Which means the max number of comparisons at each stage = (length of sublist * (number of sublists/2)) ==> n/2
    3. As you've observed the total number of stages would be log(n) base 2
      So the total complexity would be == (max number of comparisons at each stage * number of stages) == O((n/2)*log(n)) ==> O(nlog(n))
回复 原文
我的影子我的梦 2024-12-17 04:37:32

算法合并排序在 O(n log n) 中对大小为 n 的序列 S 进行排序
时间，假设 S 的两个元素可以在 O(1) 时间内进行比较。在此处输入图像描述

Algorithm merge-sort sorts a sequence S of size n in O(n log n)
time, assuming two elements of S can be compared in O(1) time.enter image description here

回复 原文
笑红尘 2024-12-17 04:37:32

这是因为无论是最坏情况还是平均情况，合并排序只是在每个阶段将数组分成两半，这给出了 lg(n) 分量，另一个 N 分量来自每个阶段进行的比较。因此组合起来几乎变成 O(nlg n)。无论是平均情况还是最坏情况，lg(n) 因子始终存在。剩余 N 因子取决于在两种情况下进行的比较。现在最坏的情况是每个阶段对 N 个输入进行 N 次比较。所以它变成了 O(nlg n)。

This is because whether it be worst case or average case the merge sort just divide the array in two halves at each stage which gives it lg(n) component and the other N component comes from its comparisons that are made at each stage. So combining it becomes nearly O(nlg n). No matter if is average case or the worst case, lg(n) factor is always present. Rest N factor depends on comparisons made which comes from the comparisons done in both cases. Now the worst case is one in which N comparisons happens for an N input at each stage. So it becomes an O(nlg n).

回复 原文
轻拂→两袖风尘 2024-12-17 04:37:32

许多其他答案都很好，但我没有看到任何提及与“合并排序树”示例相关的高度和深度。这是解决这个问题的另一种方法，重点关注树。这是另一张图片来帮助解释：
输入图像描述这里

只是回顾一下：正如其他答案所指出的，我们知道合并序列的两个排序切片的工作是在线性时间内运行的（我们从主排序函数调用的合并辅助函数）。< br>
现在看看这棵树，我们可以将根（根除外）的每个后代视为对排序函数的递归调用，让我们尝试评估我们在每个节点上花费了多少时间......序列和合并（两者一起）需要线性时间，任何节点的运行时间与该节点处序列的长度是线性的。

这就是树深度的用武之地。如果 n 是原始序列的总大小，则任何节点处的序列大小为 n/2i，其中 i 是深度。如上图所示。将其与每个切片的线性工作量放在一起，我们可以得出树中每个节点的运行时间为 O(n/2i)。现在我们只需对 n 个节点求和即可。实现此目的的一种方法是认识到树中每个深度级别都有 2i 个节点。因此，对于任何级别，我们都有 O(2i * n/2i)，即 O(n)，因为我们可以取消 2i< /sup>s！如果每个深度都是 O(n)，我们只需将其乘以该二叉树的高度，即 logn。答案：O(nlogn)

参考：数据结构和算法Python

Many of the other answers are great, but I didn't see any mention of height and depth related to the "merge-sort tree" examples. Here is another way of approaching the question with a lot of focus on the tree. Here's another image to help explain:
enter image description here

Just a recap: as other answers have pointed out we know that the work of merging two sorted slices of the sequence runs in linear time (the merge helper function that we call from the main sorting function).
Now looking at this tree, where we can think of each descendant of the root (other than the root) as a recursive call to the sorting function, let's try to assess how much time we spend on each node... Since the slicing of the sequence and merging (both together) take linear time, the running time of any node is linear with respect to the length of the sequence at that node.

Here's where tree depth comes in. If n is the total size of the original sequence, the size of the sequence at any node is n/2i, where i is the depth. This is shown in the image above. Putting this together with the linear amount of work for each slice, we have a running time of O(n/2i) for every node in the tree. Now we just have to sum that up for the n nodes. One way to do this is to recognize that there are 2i nodes at each level of depth in the tree. So for any level, we have O(2i * n/2i), which is O(n) because we can cancel out the 2is! If each depth is O(n), we just have to multiply that by the height of this binary tree, which is logn. Answer: O(nlogn)

reference: Data Structures and Algorithms in Python

回复 原文
爱她像谁 2024-12-17 04:37:32

递归树将具有深度 log(N)，并且在该树的每一层，您将执行组合的 N 工作来合并一对或多对 em> 排序数组。

  1. 您递归地将起始数组分成两半，直到最终得到 N 个数组，每个数组都包含一个元素。因为只有一个元素，所以这些数组在技术上是排序的——这一点很重要。
  2. 现在，您可以通过使用 O(N) 排序算法重新组合每个已排序数组来展开递归（如下所示）。

合并排序数组

要合并两个排序数组 A[1,5] 和 B[3,4]，只需从头开始迭代即可，选择两个数组之间的最低元素并递增该数组的指针。当两个指针都到达各自数组的末尾时，您就完成了。

^ 表示迭代每个数组时各自的索引。

[1,5] [3,4]  --> []
 ^     ^

[1,5] [3,4]  --> [1]
   ^   ^

[1,5] [3,4]  --> [1,3]
   ^     ^

[1,5] [3,4]  --> [1,3,4]
   ^      x

[1,5] [3,4]  --> [1,3,4,5]
    x     x

Runtime = O(A + B)

合并排序插图

您的递归调用堆栈将如下所示。工作从底部叶节点开始并向上冒泡。

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2

  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

因此，您在树中的每个 k 级别上执行 N 工作，其中 k = log(N)

N * k = N * 日志（N）

The recursive tree will have depth log(N), and at each level in that tree you will do a combined N work to merge one or more pairs of sorted arrays.

  1. You recursively split the starting array into halves until you end up with N arrays that each contain a single element. Because there is just one element these arrays are technically sorted — this is important.
  2. Now you unwind the recursion by recombining each of these sorted arrays with an O(N) sort algorithm (shown below).

Merging sorted arrays

To merge two sorted arrays A[1,5] and B[3,4] you simply iterate both starting at the beginning, picking the lowest element between the two arrays and incrementing the pointer for that array. You're done when both pointers reach the end of their respective arrays.

The ^ represents the respective index when iterating each array.

[1,5] [3,4]  --> []
 ^     ^

[1,5] [3,4]  --> [1]
   ^   ^

[1,5] [3,4]  --> [1,3]
   ^     ^

[1,5] [3,4]  --> [1,3,4]
   ^      x

[1,5] [3,4]  --> [1,3,4,5]
    x     x

Runtime = O(A + B)

Merge sort illustration

Your recursive call stack will look like this. The work starts at the bottom leaf nodes and bubbles up.

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2

  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

Thus you do N work at each of k levels in the tree, where k = log(N)

N * k = N * log(N)

回复 原文
云仙小弟 2024-12-17 04:37:32

MergeSort 算法需要三个步骤：

  1. 除步骤计算子数组的中间位置，并且需要常数时间 O(1)。
  2. 征服步骤递归地对两个大约包含 n/2 个元素的子数组进行排序。
  3. 合并步骤在每次传递中合并总共 n 个元素，最多需要 n 次比较，因此需要 O(n)。

该算法需要大约 logn 遍来对 n 个元素的数组进行排序，因此总时间复杂度为 nlogn。

MergeSort algorithm takes three steps:

  1. Divide step computes mid position of sub-array and it takes constant time O(1).
  2. Conquer step recursively sort two sub arrays of approx n/2 elements each.
  3. Combine step merges a total of n elements at each pass requiring at most n comparisons so it take O(n).

The algorithm requires approx logn passes to sort an array of n elements and so total time complexity is nlogn.

回复 原文
小姐丶请自重 2024-12-17 04:37:32

让我们以 8 个元素{1,2,3,4,5,6,7,8} 为例，您必须先将其分成两半意味着 n/2=4({1,2,3,4} {5 ,6,7,8}) 这两个除法部分需要 0(n/2) 和 0(n/2) 次，因此第一步需要 0(n/2+n/2)=0(n) 次。
2.下一步是除n/22，这意味着(({1,2} {3,4} )({5,6}{7,8}))
(0(n/4),0(n/4),0(n/4),0(n/4)) 分别表示这一步总共需要 0(n/4+n/4+n/4+ n/4)=0(n)次。
3. 接下来与上一步类似，我们必须将第二步进一步除以 2 意味着 n/222 ((({1},{2},{3},{4})({ 5},{6},{7},{8})) 其时间为 0(n/8+n/8+n/8+n/8+n/8+n/8+n/8+n /8)=0(n)
这意味着每个步骤需要 0(n) 次。让步骤将是 a，所以合并排序所花费的时间是 0(an) 这意味着 a 必须是 log (n)，因为步骤总是除以 2 。所以最终归并排序的TC为0(nlog(n))

lets take an example of 8 element{1,2,3,4,5,6,7,8} you have to first divide it in half means n/2=4({1,2,3,4} {5,6,7,8}) this two divides section take 0(n/2) and 0(n/2) times so in first step it take 0(n/2+n/2)=0(n)time.
2. Next step is divide n/22 which means (({1,2} {3,4} )({5,6}{7,8})) which would take
(0(n/4),0(n/4),0(n/4),0(n/4)) respectively which means this step take total 0(n/4+n/4+n/4+n/4)=0(n) time.
3. next similar as previous step we have to divide further second step by 2 means n/222 ((({1},{2},{3},{4})({5},{6},{7},{8})) whose time is 0(n/8+n/8+n/8+n/8+n/8+n/8+n/8+n/8)=0(n)
which means every step takes 0(n) times .lets steps would be a so time taken by merge sort is 0(an) which mean a must be log (n) because step will always divide by 2 .so finally TC of merge sort is 0(nlog(n))

回复 原文
~没有更多了~

关于作者

霊感

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文