algorithm - 归并排序计算复杂度时 "cn"到底是什么？

Question

我今天正在阅读 CLRS，以更好地理解归并排序的复杂性。我看到一行内容是“其中常量 c 表示解决大小为 1 的问题所需的时间以及划分和组合步骤中每个数组元素的时间。”我知道作者所说的大小为 1 的问题是什么意思，但拆分和组合步骤的每个数组元素的时间究竟是多少，为什么是“cn”？

文字图片如下，供引用。

Answer 1

你是对的，它有点令人困惑，而且作者不是很精确。最好使用像这样的重复来计算比较等离散事件。但是随后您必须制定特定实现的细节，这会变得很繁琐。这个证明是一种估计，这已经足够好了，因为我们只是在寻找大的 Omega 行为。常数因素不会产生影响。

为了理解它，可以将 cn(c 乘以 n)视为执行一个操作所需的时间在总长度为 n 的列表上合并步骤。所以 c 是处理一个元素所需的常数时间的粗略表达式:执行合并的任何循环的一次迭代所需的时间。

他称此为“合并”，而不是合并。他还建议拆分列表以进行递归排序可能会产生每个元素的成本。在正常的数组实现中，没有这样的每个元素成本。不过，链表归并排序会有一个:将一个大列表分成两半的循环。然后 c 表示两个循环的一次迭代。

递归项 2T(n/2) 是对两个子列表进行排序所需时间的表达式。

你可以通过说

使这个表达式更精确一点

T(n) = 2T(n/2) + cn + k

其中 k 是在合并(如果有的话则拆分)循环之外运行的代码的恒定时间:函数调用开销、子列表长度数学等。您可以尝试使用以下方法解决循环这个额外的学期作为一个练习来向你自己证明 Omega 的大结果不会改变。