algorithm - 这种“增量排序”的时间复杂度

Question

这使用与合并排序相同的合并功能，但输入的拆分方式不同，因此列表以这种方式合并^

在最坏的情况下，该算法的比较次数是多少？我知道归并排序是 (n log n - n + 1)，我认为这种排序比较慢

Answer 1

这种排序是 O(n^2)。对于添加的每个项目，您将比较现有列表中的每个项目。

所以在这里你将进行 1 + 2 + 3 + 4 + 5 + 6 + 7 = (n^2 + n)/2 比较。

这是假设您使用的是标准合并。

您也可以就地执行此操作，在这种情况下，它只是将内容插入到排序列表中。这也是 O(n^2)。您将进行 log(n) 比较以找到要插入项目的位置，但随后您必须将项目向下移动以腾出空间。所以插入每个项目是 n + log(n)，使得排序 O(n^2 + n log n)。

Answer 2

作为提示：你在其他地方见过这个算法吗？它的工作原理是从 n 个已排序元素的列表开始，然后在末尾添加第 n 个元素并将其交换到适当的位置。

一旦你弄清楚了那个算法是什么，你应该能够很容易地获得最好的、最坏的和平均情况的运行时。

希望这可以帮助！