为什么自顶向下归并排序的最佳情况时间复杂度为O(nlogn)？
我认为自顶向下归并排序的最佳情况是1，只需要比较1次。
自底向上归并排序在最坏情况、最佳情况和平均情况下的时间复杂度如何呢？
还有一个问题是，为什么每次迭代都需要精确地O(n)？有人可以帮忙解答吗？
还有一个问题是，为什么每次迭代都需要精确地O(n)？有人可以帮忙解答吗？
1个回答
5
为什么自顶向下的归并排序在最佳情况下的时间复杂度为O(nlogn)？
因为在每次迭代中，您将数组拆分为两个子列表，并递归调用算法。在最佳情况下，您将它刚好拆分到一半，因此您将问题（每个递归调用的问题）减少到原始问题的一半。您需要log_2(n)次迭代，每次迭代都需要精确地花费O(n)（每次迭代都在所有子列表上进行，总大小仍然是n），因此总共为O(nlogn)。
但是，通过简单的预处理来检查列表是否已排序，可以将其减少到O(n)。
由于检查列表是否已排序本身就是O(n)，因此无法以O(1)完成。请注意，“最佳情况”是通常的n的“最佳情况”，而不是特定大小的“最佳情况”。
那么自底向上的归并排序在最坏情况、最佳情况和平均情况下的时间复杂度如何呢？
同样的方法可以给出自底向上的最佳情况O(n)（简单的预处理）。自底向上归并排序的最坏情况和最佳情况是O(nlogn)——因为在这种方法中，列表总是被分成两个等长（最多相差1）的列表。
因为在每次迭代中，您将数组拆分为两个子列表，并递归调用算法。在最佳情况下，您将它刚好拆分到一半，因此您将问题（每个递归调用的问题）减少到原始问题的一半。您需要log_2(n)次迭代，每次迭代都需要精确地花费O(n)（每次迭代都在所有子列表上进行，总大小仍然是n），因此总共为O(nlogn)。
但是，通过简单的预处理来检查列表是否已排序，可以将其减少到O(n)。
由于检查列表是否已排序本身就是O(n)，因此无法以O(1)完成。请注意，“最佳情况”是通常的n的“最佳情况”，而不是特定大小的“最佳情况”。
那么自底向上的归并排序在最坏情况、最佳情况和平均情况下的时间复杂度如何呢？
同样的方法可以给出自底向上的最佳情况O(n)（简单的预处理）。自底向上归并排序的最坏情况和最佳情况是O(nlogn)——因为在这种方法中，列表总是被分成两个等长（最多相差1）的列表。
- amit
6
为什么迭代次数应该是log_2(n)？这方面有公式吗？另外一个问题是关于二叉树的，为什么二叉树的长度是log(n)。 - J.L
@Justin：在递归的最深层，您有1个元素。第二层有2个。第三层有4个，第四层有8个，...在第i层，您有2^(i-1)个元素。因此，我们正在寻找“i”，使得“2^(i-1) = n”。由于“2^logn == n”，我们得出结论“i = logn+1”-因此迭代的总次数为“O(logn)”对于二叉树也是如此。 - amit
你说的“有1个元素，2个元素”是什么意思？是指一开始有一个数组列表，然后分成两部分，以此类推吗？ - J.L
@Justin：这就是归并排序的工作原理，在最深层（停止子句）中只有一个元素。在它之前的一层中，有2个元素... 递归的每一层都在处理原始列表的某些子列表，该子列表的长度如我所描述的那样（1、2、4、... 2^(i-1)）。 - amit
谢谢！明白了，最坏情况怎么样呢？来自《算法设计与分析》这本书。为什么在两个数组中，最坏情况不是其中一个变为空，而是另一个只包含一个元素？而不是将输入精确地分成两半？ - J.L
还有一个问题，为什么每次迭代都需要O(n)的时间？你能详细解释一下吗？ - J.L
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
O(1)？也许通过预处理并检查数组是否已排序，可以达到O(n)。 - amitn的情况下最好的情况”，而不是“假设只有两个项目需要排序的最好情况”。 - Steve Jessop