这篇文章分析时间复杂度,假设最终分出来的序列的长度分别是$len_1,len_2,…,len_k$
一.普通倍增(指从大到小循环):,$O(n^2logn)$
在算$len_i$时,倍增倒序循环时,我们每次都会对新增的部分进行快速排序,时间复杂度为$O(nlogn+\frac{n}{2}log\frac{n}{2}+…)=O(nlogn)$;而每次合并的时候用的归并排序,不妨将每次合并的长度都看成$len_i$,于是合并的时间复杂度为$O(len_ilogn)$
对所有的序列求和,复杂度为$O(knlogn+nlogn)$,由于$k$最坏为$n$,所以时间复杂度为$O(n^2logn)$
二.蓝书倍增:$O(nlogn)$
首先说明一下,按照蓝书的倍增方法,长度一旦开始除以$2$之后,长度都不可能再翻倍,只能一直除以$2$,用数学归纳法可以证明
举个例子,假设长度在递增的变化分别是$1\space 2\space 4\space 8\space 16\space 32\space 64$,然后接下来发现$128$不能继续拓展了,那就回到$64$,假设也不能,那就变成$32$,假设可以拓展了,$32$是没有必要回到$64$的,因为如果可以的话,那么在之前第一次从$128$回到$64$的时候肯定就可以,但是实际上不可以,所以$64$不可以,继续保持$32$也不可以,否则的话相当于就可以加$32+32=64$,也就是发现$128$不行的时候,加$64$却可以,但是实际上加$64$不可以,所以$32$也不行,只能试$16$
于是对于$len_i$,每次只对新增的部分进行快速排序,有$O(2(len_iloglen_i+\frac{len_i}{2}log\frac{len_i}{2}+…))=O(len_iloglen_i)$(乘以$2$是在算后面长度除以$2$的时候进行排序的复杂度),归并的时间复杂度是$O(len_iloglen_i)$
对所有的序列求和,复杂度为$O(nlogn)$
经过实际代码测试,上面的论断是正确的
关于蓝书倍增长度变化是我自己想的,暂时没发现错误,如果有人发现错了请随时指出,thx