algorithm - 给定倒排次数的列表的冒泡排序和插入排序的复杂度

Question

设列表的长度为n，反转次数为d。为什么插入排序在 O(n+d) 时间内运行，为什么冒泡排序不是？

当我考虑这个问题时，我想到的是最坏的情况。由于倒置的最坏情况是 n(n-1)\2，冒泡排序和插入排序同时运行。但后来我不知道如何回答这个问题，因为我发现它们是一样的。有人可以帮我弄这个吗？

Answer 1

对于冒泡排序，如果最后一个元素需要到达第一个位置(n 次反转)，则需要遍历整个数组 n 次，每次将元素向前移动一个位置，以便获得 n^2 步，所以无论 d 的值如何，你都会得到 O(N^2)。

插入排序中的相同设置将只执行 n+n 步来对所有内容进行排序 (O(N+d))。 d 实际上是交换插入排序需要进行排序的总数。

当您假设 d 的最坏情况值为 n(n-1)/2 时，您就错了。虽然这是事实，但如果您想用 d 表示复杂性，则不能将其替换为最坏的值情况，除非您接受更高的界限。