考虑数组插入的时间复杂度

Question

给定一个数组的插入排序，你在其中进行 O(n) 次比较以找到要插入的索引，然后插入，时间复杂度是否为 O(n^3)？

因为对于每个元素 (n)，您遍历排序列表 (n)，然后插入 (n)。

据我所知，正常的实现没有任何插入，只有交换将它减少到 O(n^2)，因为项目是通过交换而不是插入放置在正确的位置。

O(n^3) 插入排序的伪代码：

for element in array
    find the correct location
    then insert in the correct location

Answer 1

您非常接近正确答案，但此处的正确时间限制是 O(n²).

你说得对，你必须访问数组的每个元素，所以你将做某事 O(n) 次。那是什么东西？如您所述，您首先找到插入点（这需要时间 O(n)），然后向下移动以腾出空间（这也需要时间 O(n)）。这意味着每个元素 完成的工作是 O(n) + O(n) = O(n)。在您的分析中，您将这两个 O(n) 项相乘，这就是您高估总数的原因。

总的来说，你正在做 O(n) 次 O(n) 次，所以完成的总工作量的一个很好的上限是 O(n²).

Answer 2

您非常接近正确答案，但此处的正确时间限制是 O(n2)。