如何操作插入排序以始终在最复杂的情况下运行

Question

下面的伪代码：

function INSERTIONSORT(A[0..n − 1])
for i ← 1 to n − 1 do
     j ← i − 1
     while j ≥ 0 and HASH(A, j + 1) < HASH(A, j) do
          SWAP(A[j + 1], A[j])
          j ← j − 1

我知道插入排序的最坏情况复杂度是O(N²)，但是如果使hash（A,j+1)返回一个始终小于hash（A,j)的整数，从而使while循环运行到其最大循环量，那么是否会实现O(N²)的时间复杂度？

Answer 1

我认为最后一个问题是“这会实现O(N²)的时间复杂度吗？”它本身是错误的。
它显然实现了O(n²)的时间复杂度，怎么可能呢？

如果您希望始终在最坏情况下工作，那么除了O(N²)之外，您基本上还希望确保O(N²)，即您希望修复一个等于上限的下限。

无论如何，答案仍然是肯定的：mading散列(A,j+1)返回一个始终小于散列(A,j)的整数，您可以确保内部循环始终运行i次。因此，对于任何执行，您都将执行1+...+(n-1)，这是二次（上下）有界的。