为何归并排序递归树的根层时间代价为cn？

首先明确：cn里的n确实是输入规模（数组元素个数），但这个表达式代表的是处理该规模输入所需的时间代价，并非把n直接等同于时间。

• c是一个常数，用来概括处理单个元素时，所有相关操作（比如比较、复制、移动等）的总时间开销。这些操作的时间都是固定的常数级，所以可以用一个统一的常数c打包表示。
• 归并排序的根层对应的是处理整个规模为n的数组的核心操作：当递归拆分到最底层后，往上合并的顶层步骤就是合并两个规模为n/2的已排序子数组，合并n个元素的时间复杂度是线性的O(n)，用cn是把这个线性时间做了具体量化——因为递归树分析需要具体数值来逐层求和，而非只看渐进复杂度。
• 书中假设n是2的整数次幂，只是为了让递归树成为完美二叉树，每一层的子问题规模都是整数，简化分析过程，不影响最终的时间复杂度结论。

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