algorithm - 如何理解归并排序的时间复杂度表达式

Question

抱歉，这个问题可能是一个新程序员（我自己：）提出的愚蠢问题。来自以下链接： https ://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/ 归并排序的时间复杂度为 T(n) = 2*T(n/2) + cn

以下是我的问题：

1. 2*T(n/2) 表示n的左侧（从索引0到索引中间）和右侧（从索引中间+1到n的最后一个元素）“分而治之”过程所花费的时间输入，对吗？
2. cn 表示花费的时间：n 个输入的“征服”过程，因为我们需要遍历所有 n 个输入以便将它们按正确的顺序排列，对吗？

标签： algorithmmergesort

Answer 1

T(n) = 2*T(n/2) + cn 是理想时间与元素数量的关系。在这种情况下，它适用于自上而下和自下而上的合并排序。可以表示为：

T(2m) = 2*T(m) + 2cm   (2c is a constant, so it could just be ... + cm)

因此，用文字来说明这一点，对 2m 个元素进行排序所需的时间是对 m 个元素进行排序所需的时间加上合并 2m 个元素所需的时间的 2 倍。对于合并部分，移动次数始终为 2m，但比较次数范围为 m 到 2m-1。