我对merge-sort算法的数学证明有疑问。我只看到证明是数学的，但这个问题与算法有关。
最差情况下合并排序的时间复杂性，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
现在我怀疑他为什么把我当作日志（n-1）这给了我们一个答案：
=nlogn -n+1
最佳答案
当问题的大小n减小时，一次减小一半，n就成为可以在恒定时间内求解的基本情况问题的大小。
在这种情况下n=1是基本情况，因为T(1)的顺序是O(1)。
在你的扩展中，i的数字是n被减半的次数。
现在的问题是：当n变成递归停止的1时，此时的值i是多少？
也就是说，有多少次n可以除以2，直到它变成1？
答案是log_2(n)
所以“插头和插头”的扩展停止值i = log_2(n)