给定倒排次数的列表的冒泡排序和插入排序的复杂度
The complexity of bubble sort and insertion sort for a list with a given number of inversions
设列表的长度为n，反转次数为d。为什么插入排序 运行 在 O(n+d) 时间内，为什么冒泡排序不是？
当我考虑这个问题时，我正在考虑最坏的情况。由于倒置的最坏情况是 n(n-1)\2，冒泡排序和插入排序 运行 同时进行。但后来我不知道如何回答这个问题，因为我发现它们是一样的。有人可以帮我弄这个吗？
对于冒泡排序，如果最后一个元素需要到达第一个位置（n 次反转），则需要遍历整个数组 n 次，每次将元素向前移动一个位置，以便得到 n^2 步，因此无论 d 的值如何，您都会得到 O(N^2)。
插入排序中的相同设置将只执行 n+n 步来对所有内容进行排序 (O(N+d))。 d 实际上是交换插入排序需要做的事情排序的总数。
当您假设 d 的最坏情况值为 n(n-1)/2 时，您就错了。虽然这是真的，但如果你想用 d 来表达复杂性，你不能用它的最坏价值情况来代替它，除非你接受更高的界限。
设列表的长度为n，反转次数为d。为什么插入排序 运行 在 O(n+d) 时间内，为什么冒泡排序不是？
当我考虑这个问题时，我正在考虑最坏的情况。由于倒置的最坏情况是 n(n-1)\2，冒泡排序和插入排序 运行 同时进行。但后来我不知道如何回答这个问题，因为我发现它们是一样的。有人可以帮我弄这个吗？
对于冒泡排序，如果最后一个元素需要到达第一个位置（n 次反转），则需要遍历整个数组 n 次，每次将元素向前移动一个位置，以便得到 n^2 步，因此无论 d 的值如何，您都会得到 O(N^2)。
插入排序中的相同设置将只执行 n+n 步来对所有内容进行排序 (O(N+d))。 d 实际上是交换插入排序需要做的事情排序的总数。
当您假设 d 的最坏情况值为 n(n-1)/2 时，您就错了。虽然这是真的，但如果你想用 d 来表达复杂性，你不能用它的最坏价值情况来代替它，除非你接受更高的界限。