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

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

2）。

您是正确的，您必须访问数组的每个元素，因此您将要做O（n）次。那是什么？如前所述，首先找到插入点（花费时间O（n）），然后向下移动东西以腾出空间（也花费时间O（n））。这意味着^{每个元素完成的功为O（n）+ O（n）= O（n）。在分析中，您将这两个O（n）项相乘，这就是为什么您高估了总数的原因。}

总体上，您要进行O（n）次工作O（n）次，所以完成的总工作量的一个很好的上限是O（n 2）。

Answer 2