自底向上归并排序法的复杂度分析
来源：2-5 实现自底向上的归并排序
hxcchan
2022-01-05 13:54:49
老师自底向上的归并排序因为是用了跌打的方法，和之前用递归画递归树的分析方式感觉可能稍微有点不一样，我是这么分析的：
假设输入数据的规模是n：
时间复杂度：
外层for循环每次size都加了一倍，直到数组的长度n为止，所以大致执行了logn次；
内部的for循环，索引i每次也是增加了两倍的size，直到数组长度n为止，也大约执行了logn次；
内层for循环中的merge每次循环大约执行了O(n)的时间；
最开始拷贝整个数组使用了大约O(n)的时间；
所以时间复杂度总共是：
O(logn * logn * n + n) = O(nlogn^2 + n) = O(2nlogn + n) = O(nlogn)
空间复杂度：经过优化之后，总共就开辟了输入数组的长度的新数组，也就是O(n)。
谢谢老师指导！
相关截图：
1回答
-
这个分析是有问题的。
首先，从数学上看， logn * logn 即 (logn)^2 和 log(n^2) 不是一回事儿。log(n^2) = 2logn，而 (logn)^2 无法做化简，所以，如果一个算法的复杂度是 O(n(logn)^2) 的话，他和 O(nlogn) 不等价。（而如果一个算法是 O(nlog（n^2)）的话，能得到他就是 O(2nlogn) 即 O(nlogn) 的。
但这一点和这个问题无关，因为归并排序不是 O(n(logn)^2) 的。
==========
你的分析中，对外层循环的分析是正确的，for(sz = 1; sz < n; sz += sz)，这个循环的执行次数是 O(logn) 的。
但是，内层循环 for(int i = 0; i + sz < n; i += sz + sz)，这重循环不是 O(logn) 的。
内层循环的循环变量 i，增速是每次稳定加 2 * sz，直到加到 n，所以，其循环执行的次数是 n / (2 * sz)。
而外层循环是每次循环变量 sz 自身做 sz += sz（其实就是 sz *= 2），所以，循环变量 sz 在成指数级增长，所以其循环执行次数是 logn 级别的。
（两层循环看似循环的改变量都和 2 * sz 有关，但是因为他们作用的对象不同，所以复杂度分析是不同的。）
==========
那内层循环为什么是 O(n) 的？就是因为，for(int i = 0; i + sz < n; i += sz + sz) 这重循环执行了 n / (2 * sz) 次，而每次执行了一个 merge，而这个 merge 就是对总共 2*sz 的区间（两个 sz 的有序区间）做合并，合并用的操作数和元素个数成线性关系，即 O(2 * sz) 级别的。
因此：(n / (2 * sz)) * O(2 * sz) = O(n)。
在综合外层循环执行了 logn 次，所以总体是 O(nlogn) 的。
这其实和自顶向下的过程是类似的。自顶向下的递归树中，每一层，对应了这里的内层循环的分析，而总的层数，就是外层循环的执行个数。
==========
空间复杂度的分析是正确的：）
继续加油！：）
1
相似问题