顺序数组的入队复杂度

Question

和插入排序一样，如果一直维护优先队列的排序，那对于有序的数组来说，怎么会有最差情况O(n²)呢？不是稳定O(n)么

Answer 1

liuyubobobo 2017-06-07 11:24:57

在这里，我讲述的是进行n次操作的时间复杂度。因为对于动态的数据结构而言，要不停的维护元素的增删改查操作。如果单次操作的时间复杂度是O(n)，n次操作以后就是O(n^2)级别的啦。

• 提问者 易萧 #1

  还有这种操作、、、

Answer 2

agjsytt 2020-01-03 16:06:27

哦，对，这里实际是计算的n次操作的累加值。

总的操作时间 = 单次操作最差时间 * n