老师，关于优先队列的问题

Question

为啥顺序数组入队是O（n）呢，既然是顺序，肯定要排序，不是最好是nlogn吗

这个最差是n^2,我想不明白，差在哪里

Answer 1

liuyubobobo 2018-10-22 01:43:49

对于顺序数组，我们要在每次插入数据的时候，都保证整个数组有序。所以，每次插入一个新的数据，原始数组是有序的，我们只需要扫描一遍整个数组，获得新元素的正确插入位置（以保持整个数组依然有序），然后进行插入就好了。这个时间复杂度是O(n)的。

如果有n个请求，每次请求都是O(n)的，整个过程是O(n^2)的：）

• 提问者 张婧仪 #1

  非常感谢！老师，麻烦了，有些着急，感觉问的很蠢

• liuyubobobo 回复 提问者 张婧仪 #2

  不客气，加油

• yushou 回复 liuyubobobo #3

  既然是顺序数组插入时使用二分法不是可以达到O(logN)的效率吗？

点开查看后面1条评论