algorithm - 为什么我们在合并排序算法中将 i 作为 log(n-1) 插入

Question

我对归并排序算法的数学证明有疑问。正如我所看到的，只有证明是数学的，但问题与算法有关。

归并排序在最坏情况下的时间复杂度，T(n) = 2T(n/2) + n-1

=> T(n) = n-1 + 2T(n/2)//递归部分总是放在最后以保持简单

通过即插即用的方法:

T(n) = n-1 + 2[n/2-1 + 2T(n/4) ]    //plug
     = n-1 + n-2 + 4T(n/4)          //chug
     = n-1 + n-2 + 4[n/4 -1 + 2T(n/8)]    //plug 
     = n-1 + n-2 + n-3 + ....... + n- 2^i-1 + 2^i T(n/2^i) //rounding off

现在我怀疑这一步为什么他把我当作log(n-1)？这给了我们一个答案:

     =nlogn -n+1

Answer 1

随着问题n 的大小减小，一次减半，n 成为可以在常数时间内解决的基本案例问题的大小。在这种情况下，n=1 是基本情况，因为已知 T(1) 的顺序为 O(1)。

在您的扩展中，数字 i 是 n 减半的次数。

现在的问题是:当递归停止时n变为1，此时i的值是多少？

也就是n可以被2除多少次直到变成1？

答案是log_2(n)

因此“即插即用”扩展在值 i = log_2(n)

处停止