为什么自顶向下合并排序的最佳情况的时间复杂度在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)- 因为在这种方法中,列表总是被划分为2个相等长度(直到差异1)列表.