归并排序复杂度混乱
Merge Sort Complexity Confusion
谁能用通俗易懂的英语向我解释一下合并排序的复杂度是 O(n*logn)。我知道 'n' 来自这样一个事实，即合并两个大小为 n/2 的已排序列表需要 n 个追加。让我困惑的是日志。如果我们要在 32 个元素的列表上绘制 运行 合并排序的函数调用树，那么它将有 5 个级别。 Log2(32)= 5。这是有道理的，但是，为什么我们使用树的级别，而不是 Big O 定义中的实际函数调用和合并？
在这个 diagram 中我们可以看到对于一个 8 元素的列表，有 3 个级别。在这种情况下，Big O 试图找出随着输入增加操作数量的行为方式，我的问题是（函数调用的）级别如何被视为操作？
函数调用的层级是这样考虑的（在【算法导论】一书中（https://mitpress.mit.edu/books/introduction-algorithms第2.3.2章）：
We reason as follows to set up the recurrence for T(n), the worst-case running time of merge sort on n numbers. Merge sort on just one element takes constant time. When we have n > 1 elements, we break down the running time as follows.
Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = Θ(1).
Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time.
Combine: We have already noted that the MERGE procedure on an n-element subarray takes time Θ(n), and so C(n) = Θ(n).
When we add the functions D(n) and C(n) for the merge sort analysis, we are adding a function that is Θ(n) and a function that is Θ(1). This sum is a linear function of n, that is, Θ(n). Adding it to the 2T(n/2) term from the “conquer” step gives the recurrence for the worst-case running time T(n) of merge sort:
T(n) = Θ(1), if n = 1; T(n) = 2T(n/2) + Θ(n), if n > 1.
那么利用递归树或者主定理，我们可以计算：
T(n) = Θ(nlgn).
简单分析：-
假设数组的长度是 n 要排序。
现在每次都会分成两半。
因此，请参见：-
n
n/2 n/2
n/4 n/4 n/4 n/4
.....................................
1 1 1 .....................
如您所见，树的高度将为 logn( 2^k = n; k = logn)
在每个级别总和将为 n。 (n/2 +n/2 = n, n/4+n/4+n/4+n/4 = n).
所以最后级别 = logn 并且每个级别需要 n
结合我们得到 nlogn
现在关于你的问题，关卡如何被认为是操作，考虑如下：-
数组 9、5、7
假设它分成 9,5 和 7
对于 9,5 它将转换为 5,9（在这个级别需要一次交换）
然后在上层 5,9 和 7 合并时转换为 5,7,9
（再次在这个级别需要交换一次）。
在最坏的情况下，任何级别的数字操作都可以是 O(N) 和级别数 logn。因此 nlogn.
为了更清楚地尝试编写合并排序代码，您将能够将其可视化。
让我们以您的 8 项数组为例。我们从 [5,3,7,8,6,2,1,4].
开始
如您所述，共有三道关卡。在第一遍中，我们合并 1 元素子数组。在这种情况下，我们会将 5 与 3、7 与 8、2 与 6 以及 1 与 4 进行比较。典型的合并排序行为是将项目复制到辅助数组。所以每个项目都被复制了；我们只是在必要时更改相邻项目的顺序。第一遍后，数组为[3,5,7,8,2,6,1,4].
在下一轮中，我们合并二元序列。所以[3,5]与[7,8]合并，[2,6]与[1,4]合并。结果是[3,5,7,8,1,2,4,6]。同样，每个元素都被复制了。
在最后一遍中，算法再次复制每个项目。
有 log(n) 遍，每遍复制 n 项。 （当然也有比较，但是数量是线性的，不会超过项目的数量。）反正，如果你在做 n 次操作 log(n) 次，那么算法就是 O(n log n)。
谁能用通俗易懂的英语向我解释一下合并排序的复杂度是 O(n*logn)。我知道 'n' 来自这样一个事实，即合并两个大小为 n/2 的已排序列表需要 n 个追加。让我困惑的是日志。如果我们要在 32 个元素的列表上绘制 运行 合并排序的函数调用树，那么它将有 5 个级别。 Log2(32)= 5。这是有道理的，但是，为什么我们使用树的级别，而不是 Big O 定义中的实际函数调用和合并？ 在这个 diagram 中我们可以看到对于一个 8 元素的列表，有 3 个级别。在这种情况下，Big O 试图找出随着输入增加操作数量的行为方式，我的问题是（函数调用的）级别如何被视为操作？
函数调用的层级是这样考虑的（在【算法导论】一书中（https://mitpress.mit.edu/books/introduction-algorithms第2.3.2章）：
We reason as follows to set up the recurrence for T(n), the worst-case running time of merge sort on n numbers. Merge sort on just one element takes constant time. When we have n > 1 elements, we break down the running time as follows.
Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = Θ(1).
Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time.
Combine: We have already noted that the MERGE procedure on an n-element subarray takes time Θ(n), and so C(n) = Θ(n).
When we add the functions D(n) and C(n) for the merge sort analysis, we are adding a function that is Θ(n) and a function that is Θ(1). This sum is a linear function of n, that is, Θ(n). Adding it to the 2T(n/2) term from the “conquer” step gives the recurrence for the worst-case running time T(n) of merge sort:
T(n) = Θ(1), if n = 1; T(n) = 2T(n/2) + Θ(n), if n > 1.
那么利用递归树或者主定理，我们可以计算：
T(n) = Θ(nlgn).
简单分析：- 假设数组的长度是 n 要排序。 现在每次都会分成两半。 因此，请参见：- n n/2 n/2 n/4 n/4 n/4 n/4 ..................................... 1 1 1 .....................
如您所见，树的高度将为 logn( 2^k = n; k = logn) 在每个级别总和将为 n。 (n/2 +n/2 = n, n/4+n/4+n/4+n/4 = n).
所以最后级别 = logn 并且每个级别需要 n 结合我们得到 nlogn
现在关于你的问题，关卡如何被认为是操作，考虑如下：- 数组 9、5、7 假设它分成 9,5 和 7 对于 9,5 它将转换为 5,9（在这个级别需要一次交换） 然后在上层 5,9 和 7 合并时转换为 5,7,9 （再次在这个级别需要交换一次）。
在最坏的情况下，任何级别的数字操作都可以是 O(N) 和级别数 logn。因此 nlogn.
为了更清楚地尝试编写合并排序代码，您将能够将其可视化。
让我们以您的 8 项数组为例。我们从 [5,3,7,8,6,2,1,4].
如您所述，共有三道关卡。在第一遍中，我们合并 1 元素子数组。在这种情况下，我们会将 5 与 3、7 与 8、2 与 6 以及 1 与 4 进行比较。典型的合并排序行为是将项目复制到辅助数组。所以每个项目都被复制了；我们只是在必要时更改相邻项目的顺序。第一遍后，数组为[3,5,7,8,2,6,1,4].
在下一轮中，我们合并二元序列。所以[3,5]与[7,8]合并，[2,6]与[1,4]合并。结果是[3,5,7,8,1,2,4,6]。同样，每个元素都被复制了。
在最后一遍中，算法再次复制每个项目。
有 log(n) 遍，每遍复制 n 项。 （当然也有比较，但是数量是线性的，不会超过项目的数量。）反正，如果你在做 n 次操作 log(n) 次，那么算法就是 O(n log n)。