我今天正在阅读 CLRS，以更好地了解合并排序的复杂性。我遇到了一行，上面写着“其中常数c表示解决大小为 1 的问题所需的时间，以及除法和组合步骤中每个数组元素的时间。” 我知道作者所说的大小为 1 的问题是什么意思，但是除法和组合步骤的每个数组元素的时间到底是什么，为什么它是“cn”？
下面给出文字的图像以供参考。
问问题
757 次
1 回答
1
你说得对，作者有点混乱，而且不是很精确。最好使用这样的重复来计算离散事件，如比较。但是你必须制定特定实现的细节，这变得很繁琐。这个证明是一种估计，这已经足够好了，因为我们只是在寻找大的 Omega 行为。恒定的因素不会产生影响。
为了理解它，将cn（即ctimes n）视为在总长度的列表上执行合并步骤所需的时间n。c处理一个元素所花费的恒定时间的粗略表达也是 如此：执行任何循环进行合并所花费的时间。
他称之为“合并”，而不是合并。他还建议拆分列表以进行递归排序可能会产生每个元素的成本。在正常的数组实现中，没有这样的每个元素成本。但是，链表合并排序将有一个：将大列表分成两半的循环。然后c表示两个循环的一次迭代。
递归项2T(n/2)是对两个子列表进行排序所花费的时间量的表达式。
你可以通过说使这个表达更精确一点
T(n) = 2T(n/2) + cn + k
哪里k是在合并循环之外运行的代码的恒定时间（如果有，则拆分）循环：函数调用开销，子列表长度数学等。您可以尝试使用这个额外的术语来解决递归问题，作为向自己证明的练习大欧米茄结果没有改变。
于 2015-09-19T19:27:41.887 回答