证明了在O(n)中，7排序数组和11排序数组将由InsertionSort排序。
证明了在O(n)中，7排序数组和11排序数组将由InsertionSort排序。
提问于 2019-11-14 14:13:40
给出了一个简单的证明:证明了如果数组是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)。
但我不知道该怎么做。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-11-14 14:52:02
这里的小窍门是，任何高于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)组合！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58858795
复制相关文章
相似问题
腾讯云开发者
