归并排序的大O复杂度
Big Oh Complexity of Merge Sort
我听过关于合并排序的 Big Oh 的讲座，但我很困惑。
显示的是：
0 合并 [<----- n -------->] = n
1 合并 [<--n/2--][-n/2--->] = (n/2 + n/2) = n
2 合并 [n/4][n/4][n/4][n/4] = 2(n/4 + n/4) =n
..
log(n) 合并 = n
总计 = (n + n + n + ... + n) = lg n
= O(n log n)
我不明白为什么 (n + n + ... + n) 也可以表示为 n 的以 2 为底的对数以及它们如何得到 2 次合并 = 2(n/4 + n/4)
您的树的深度为 log(n)，宽度为 n。 :)
日志部分是"how many times can I split my data in two before I have only one element left?"的结果这是递归树的深度。 n 的倍数来自于这样一个事实，即对于树中的每个级别，您将在该级别的所有合并步骤之后查看数据集中的每个元素一次。
recurse downwards:
n unsorted elements
[n/2][n/2] split until singletons...
...
merge n elements at each step when recursing back up
[][][]...[][][]
[ ] ... [ ]
...
[n/2][n/2]
n sorted elements
在 1 次合并的情况下，您有两个要排序的子数组，其中每个子数组花费的时间与要排序的 n/2 成正比。从这个意义上说，要对这两个子数组进行排序，您需要的时间与 n.
成正比
类似地，当您进行 2 次合并时，有 4 个子数组需要排序，每个子数组所花费的时间与 n/4 成正比，这将再次求和最多 n.
类似地，如果你有 n 合并，将花费与 n 成正比的时间来对所有子数组进行排序。从这个意义上说，我们可以将合并排序所花费的时间写成如下。
T(n) = 2 * T(n/2) + n
你会明白这个递归调用可以深入（比如达到 h 的高度）直到 n/(2^h) = 1。在这里取log，我们得到h=log(n)。这就是 log(n) 出现的原因。这里 log 取自基数 2.
由于您有 log(n) 个步骤，其中每个步骤花费的时间与 n 成正比，因此总时间可以表示为,
n * log(n)
在大 O 符号中，我们将其作为上限 O(nlog(n))。希望你明白了。
递归树的下图将进一步启发您。
在你的问题中写下以下部分的最后一行，
0 Merges [<----- n -------->] = n
1 Merge [<--n/2--][-n/2--->] = (n/2 + n/2) = n
2 Merges [n/4][n/4][n/4][n/4] = 2(n/4 + n/4) = n
....
n merges = n --This line is incorrect!
错了。您不会有总共 n 个大小为 n 的合并，而是日志 n 个大小为 n 的合并。
在每个级别，您将问题大小分成 2 个大小减半的问题。当您继续潜水时，您可以进行的总除法是 Log n。 （如何？假设可能的总除法是 x。那么 n = 2x 或 x = Log2n。）
由于每个级别的总工作量为 O(n)，因此对于 Log n 个级别，完成的所有工作的总和将为 O(n Log n)。
很简单。如您所演示的，每次合并都需要 O(n) 。您需要执行的合并次数是 log n（以 2 为底），因为每次合并都会使已排序部分的大小加倍。
我听过关于合并排序的 Big Oh 的讲座，但我很困惑。
显示的是：
0 合并 [<----- n -------->] = n
1 合并 [<--n/2--][-n/2--->] = (n/2 + n/2) = n
2 合并 [n/4][n/4][n/4][n/4] = 2(n/4 + n/4) =n
..
log(n) 合并 = n
总计 = (n + n + n + ... + n) = lg n = O(n log n)
我不明白为什么 (n + n + ... + n) 也可以表示为 n 的以 2 为底的对数以及它们如何得到 2 次合并 = 2(n/4 + n/4)
您的树的深度为 log(n)，宽度为 n。 :)
日志部分是"how many times can I split my data in two before I have only one element left?"的结果这是递归树的深度。 n 的倍数来自于这样一个事实，即对于树中的每个级别，您将在该级别的所有合并步骤之后查看数据集中的每个元素一次。
recurse downwards:
n unsorted elements
[n/2][n/2] split until singletons...
...
merge n elements at each step when recursing back up
[][][]...[][][]
[ ] ... [ ]
...
[n/2][n/2]
n sorted elements
在 1 次合并的情况下，您有两个要排序的子数组，其中每个子数组花费的时间与要排序的 n/2 成正比。从这个意义上说，要对这两个子数组进行排序，您需要的时间与 n.
成正比类似地，当您进行 2 次合并时，有 4 个子数组需要排序，每个子数组所花费的时间与 n/4 成正比，这将再次求和最多 n.
类似地，如果你有 n 合并，将花费与 n 成正比的时间来对所有子数组进行排序。从这个意义上说，我们可以将合并排序所花费的时间写成如下。
T(n) = 2 * T(n/2) + n
你会明白这个递归调用可以深入（比如达到 h 的高度）直到 n/(2^h) = 1。在这里取log，我们得到h=log(n)。这就是 log(n) 出现的原因。这里 log 取自基数 2.
由于您有 log(n) 个步骤，其中每个步骤花费的时间与 n 成正比，因此总时间可以表示为,
n * log(n)
在大 O 符号中，我们将其作为上限 O(nlog(n))。希望你明白了。
递归树的下图将进一步启发您。
在你的问题中写下以下部分的最后一行，
0 Merges [<----- n -------->] = n
1 Merge [<--n/2--][-n/2--->] = (n/2 + n/2) = n
2 Merges [n/4][n/4][n/4][n/4] = 2(n/4 + n/4) = n
....
n merges = n --This line is incorrect!
错了。您不会有总共 n 个大小为 n 的合并，而是日志 n 个大小为 n 的合并。
在每个级别，您将问题大小分成 2 个大小减半的问题。当您继续潜水时，您可以进行的总除法是 Log n。 （如何？假设可能的总除法是 x。那么 n = 2x 或 x = Log2n。）
由于每个级别的总工作量为 O(n)，因此对于 Log n 个级别，完成的所有工作的总和将为 O(n Log n)。
很简单。如您所演示的，每次合并都需要 O(n) 。您需要执行的合并次数是 log n（以 2 为底），因为每次合并都会使已排序部分的大小加倍。