插入排序的最坏情况时间复杂度不正确
Incorrect Worst-case time complexity of Insertion Sort
嗨，我是算法的新手，对它非常着迷。
我试图找出插入排序的最坏情况时间复杂度，它被称为 O(n**2)。相反，我们可以将时间复杂度设置为 O(N*logN).
这是我的解释，
插入排序查看第一个元素并假定它已排序。接下来它查看第 2 个元素并与 1 个元素的前一个排序子列表进行比较，并根据与前一个排序子列表中元素的比较将其插入。类似地重复此过程。
到处都提到将一个元素插入到前导排序子列表中，基本上是线性搜索，它需要 O(N) 时间，因为我们对 n 个元素执行这些操作，它需要我们 O(N**2 ).
但是，如果我们使用二进制插入将元素插入前导子列表，则需要 O(logn) 时间，其中 n 是子列表的长度。基本上将新元素与前一个排序子列表的中间元素进行比较，如果它大于中间元素，则新元素位于中间元素和子列表的最后一个元素之间。
当我们对 n 个项目重复操作时，它应该花费 O(N*logN)。我们可以使用二进制搜索方法，因为我们知道前导子列表已排序。
所以最坏情况下的时间复杂度不应该是 O(N*logN) 而不是 O(N**2)。
是的，您可以在 O(log n) 中找到插入点，但是您必须 space 才能插入该项目。这需要 O(n) 时间。
考虑这个部分排序的数组：
[1,2,3,5,6,7,9,4]
你到了最后一项，4，你做了二分查找来定位它需要插入的位置。但是现在你必须做 space，这意味着将数组中的第 9、7、6 和 5 项向下移动一个位置。这就是插入排序 O(n^2).
的原因
嗨，我是算法的新手，对它非常着迷。
我试图找出插入排序的最坏情况时间复杂度，它被称为 O(n**2)。相反，我们可以将时间复杂度设置为 O(N*logN).
这是我的解释，
插入排序查看第一个元素并假定它已排序。接下来它查看第 2 个元素并与 1 个元素的前一个排序子列表进行比较，并根据与前一个排序子列表中元素的比较将其插入。类似地重复此过程。
到处都提到将一个元素插入到前导排序子列表中，基本上是线性搜索，它需要 O(N) 时间，因为我们对 n 个元素执行这些操作，它需要我们 O(N**2 ).
但是，如果我们使用二进制插入将元素插入前导子列表，则需要 O(logn) 时间，其中 n 是子列表的长度。基本上将新元素与前一个排序子列表的中间元素进行比较，如果它大于中间元素，则新元素位于中间元素和子列表的最后一个元素之间。
当我们对 n 个项目重复操作时，它应该花费 O(N*logN)。我们可以使用二进制搜索方法，因为我们知道前导子列表已排序。
所以最坏情况下的时间复杂度不应该是 O(N*logN) 而不是 O(N**2)。
是的，您可以在 O(log n) 中找到插入点，但是您必须 space 才能插入该项目。这需要 O(n) 时间。
考虑这个部分排序的数组：
[1,2,3,5,6,7,9,4]
你到了最后一项，4，你做了二分查找来定位它需要插入的位置。但是现在你必须做 space，这意味着将数组中的第 9、7、6 和 5 项向下移动一个位置。这就是插入排序 O(n^2).
的原因