为什么自顶向下归并排序的最佳情况时间复杂度为O(nlogn)? 我认为自顶向下归并排序的最佳情况是1,只需要比较1次。 自底向上归并排序在最坏情况、最佳情况和平均情况下的时间复杂度如何呢?还有一个问题是,为什么每次迭代都需要精确地O(n)?有人可以帮忙解答吗?
为什么自顶向下的归并排序在最佳情况下的时间复杂度为O(nlogn)?因为在每次迭代中,您将数组拆分为两个子列表,并递归调用算法。在最佳情况下,您将它刚好拆分到一半,因此您将问题(每个递归调用的问题)减少到原始问题的一半。您需要log_2(n)次迭代,每次迭代都需要精确地花费O(n)(每次迭代都在所有子列表上进行,总大小仍然是n),因此总共为O(nlogn)。但是,通过简单的预处理来检查列表是否已排序,可以将其减少到O(n)。由于检查列表是否已排序本身就是O(n),因此无法以O(1)完成。请注意,“最佳情况”是通常的n的“最佳情况”,而不是特定大小的“最佳情况”。那么自底向上的归并排序在最坏情况、最佳情况和平均情况下的时间复杂度如何呢?同样的方法可以给出自底向上的最佳情况O(n)(简单的预处理)。自底向上归并排序的最坏情况和最佳情况是O(nlogn)——因为在这种方法中,列表总是被分成两个等长(最多相差1)的列表。
O(1)
?也许通过预处理并检查数组是否已排序,可以达到O(n)
。 - amitn
的情况下最好的情况”,而不是“假设只有两个项目需要排序的最好情况”。 - Steve Jessop