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

来源：4-1 为什么使用堆？

相信光变成光

2018-10-21

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

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

写回答

1回答

liuyubobobo

2018-10-22

已采纳

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

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

liuyubobobo

yushou

二分法只可以在logn的时候找到待插入的位置。但是真正插入的时间复杂度还是O(n)的，回忆一下在数组中插入元素的过程？：）继续加油！

2019-06-25

共4条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 4

回答 1

回答 1