当 A 近似排序且 k 为常数时 INSERTION SORT 的时间复杂度

Time complexity of INSERTION SORT when A is nearly sorted and k is a constant

提问人：m615 提问时间：10/18/2022 更新时间：10/18/2022 访问量：17

问：

假设 A 是一个几乎经过排序的整数数组 如果每个元素最多有 k 个位置 远离其正确位置。什么是时间复杂度 当 A 接近排序且 k 为 a 时，InsertionSort 的 不断？

算法 排序 时间复杂度

评论

1赞 Paul Hankin 10/18/2022
如何在没有“几乎排序”约束的情况下计算插入排序的时间复杂度？当每个元素最多相距 k 个位置时，该计算会发生什么？
1赞 Paul Hankin 10/18/2022
也许如果你不能弄清楚一般的 k，试着通过 k=0，然后是 k=1，然后是 k=2，依此类推，直到你明白为止。

答： 暂无答案

上一个：如何在方程式中设置数学精度？

下一个：echo 'hello' vs echo “hello” vs echo hello，我应该在 Bash 脚本中使用哪个？[复制]