如何理解时间复杂度表达式以进行合并排序

2024-04-29 • 问答

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

这是我的问题：

2 * T（n / 2）表示花费的时间：左边部分（从索引0到索引中间）和右边部分（从索引middle + 1到n的最后一个元素）的“分治”过程）的n个输入，对吗？
cn表示花费的时间：n个输入的“征服”过程，因为我们需要遍历所有n个输入以使其顺序正确，对吗？

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个元素进行排序所花费的时间的2倍，加上对2m个元素进行合并所花费的时间。对于合并部分，移动数始终为2m，但是比较数的范围为m至2m-1。