有人能用简单的英语向我解释一下归并排序是如何O(n*logn)的吗?我知道这个n来自于它需要n个加法来归并两个大小为n/2的排序列表。让我困惑的是原木。如果我们要在一个32个元素的列表上绘制一个函数调用的树，那么它将有5个级别。Log2(32) = 5。这是有道理的，然而，为什么我们在Big O定义中使用树的层次，而不是实际的函数调用和合并?在这个图中我们可以看到，对于一个有8个元素的列表，有3个级别。在这种情况下，大O试图找到操作的数量如何随着输入的增加而表现，我的问题是(函数调用)的级别如何被认为是操作?
函数调用的级别是这样考虑的(在[算法介绍]一书中(https://mitpress.mit.edu/books/introduction-algorithms Chapter 2.3.2):
我们的推理如下来建立T(n)的递归式，T(n)是n个数的归并排序的最坏情况运行时间。只对一个元素进行归并排序需要常数时间。当我们有n>1元素，我们将运行时间分解如下:
Divide: Divide步骤只计算子数组的中间，这需要常数时间。因此，D(n) = Θ(1)。
Conquer:我们递归地解决两个子问题，每个子问题的大小为n/2，这对运行时间的贡献为2T(n/2)。
Combine:我们已经注意到n元素子数组上的MERGE过程耗时Θ(n)，因此C(n) = Θ(n)。
当我们为归并排序分析添加函数D(n)和C(n)时，我们添加了一个函数Θ(n)和一个函数Θ(1)。这个和是n的线性函数，也就是Θ(n)将其与"征服"步骤中的2T(n/2)项相加，得到归并排序最坏情况下运行时间T(n)的递归式:
T(n) = Θ(1)，如果n = 1;T(n) = 2T(n/2) + Θ(n)，如果n>1 .
然后利用递归树或主定理，我们可以计算:
T(n) = Θ(nlgn).
简单分析:-假设要排序的数组长度为n。每次都会被分成两半。所以，请看下面:-nn/2 n/2N/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)
最后，levels = logn，每一层都需要n组合得到nlogn
现在关于你的问题，如何将级别视为操作，考虑如下:-数组9,5,7假设它被分成9 5和7对于9,5，它将被转换为5,9(在此级别需要一次交换)然后在上层，5,9,7在归并时被转换成5,7,9(同样在这个级别需要一次交换)。
在最坏的情况下，任何级别上的操作次数都可以是0 (N)，级别数可以是logn。因此nlogn。
为了更清晰地尝试编码合并排序，您将能够可视化它。
让我们以包含8个元素的数组为例。我们从[5,3,7,8,6,2,1,4]开始。
正如您所注意到的，有三个通道。在第一次传递中，我们合并了只有一个元素的子数组。在这种情况下，我们比较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)