归并排序时间复杂度代数证明：推导时额外2^k的疑问

归并排序的标准递归式为 T(n) = 2T(n/2) + n（推导时通常假设n=2^k，即k=log₂n），初始条件为T(1)=1（单个元素排序的常数时间）。你推导中出现的额外2^k，核心问题出在递归展开后的变量替换环节：

• 递归展开k层后，式子会变为 T(n) = 2^k · T(1) + n·k
• 因为n=2^k，所以2^k直接等于n，而非额外保留的因子。代入后式子变为 T(n) = n·T(1) + n·log₂n
• 由于T(1)是常数时间（通常取1），所以第一项n·T(1)就是n，属于低阶项。在渐进时间复杂度分析中，低阶项会被高阶主导项nlogn覆盖，最终时间复杂度为O(nlogn)。

你得到的n + 2nlogn，大概率是在替换时误将k的系数搞错，或是错误保留了2^k而非替换为n。只要把2^k替换成n，再结合初始条件的常数属性，就能修正推导结果。

内容的提问来源于stack exchange，提问作者Matt