证明了在O(n)中，7排序数组和11排序数组将由InsertionSort排序。

Question

给出了一个简单的证明:证明了如果数组是7排序的，InsertionSort的11排序时间是O(n)。

k sorted: for every i A[i] <= A[i+k]

我认为，7和11都是素数这一事实很重要。同样也是num of swaps = num of inversions，所以如果我要证明的话:对于每个元素num of inv < some const num，时间复杂度都是O(some const num * n)所以O(n)。

但我不知道该怎么做。

Answer 1

这里的小窍门是，任何高于m=60的数字都可以写成n*7 + k*11。(您可以通过将数字[m;m+6]构造为a*7+b*11，(a，b ) >0来证明这一点，如果我们可以将n作为线性组合，我们也可以构建n+7，因此我们可以构建m;+infinity )。

假设您的数组按升序排序，for any {x, N>m}, A[x] < A[x+N]。

因此，数组的最低值在间隔[0;m]中，在[1;36]中次之，依此类推。

最后，要排序您的数组，您需要m*n = O(n)组合！