0
已解决
中级天翼
今天估计是暑假问答的最后一天了
问一下，优先队列添加n个元素的时间复杂度是多少？是不是还比SORT快？（我记得是O（n））
0
已采纳
初级启示者
添加一个元素：O(log n)
添加n个元素：O(n log n)
∴优先队列和sort一样快（才怪，优先队列删除队首慢得要死
赵逸凡在2020-08-30 14:09:30追加了内容
顺便推理：
也就是说优先队列排序一遍并输出所有元素的时间大概是
O(n log n)+O(n (log n+1) )
因为在这里常数就变得很重要，所以优先队列比sort大概慢O(n (log n +1 -1) )，所以要想优先队列比sort快，你要保证
log n + 1 - 1 < 0
即log n < 0
0 < n < 1
∴当n为0~1间的小数时，优先队列才比sort快
PS：这里的排序是指一次性的排序，并不是动态维护的
赵逸凡在2020-08-30 14:27:02追加了内容
对了，我刚才的log函数是以自然常数e为底数的
0
中级天翼
O(logn)
0
初级天翼
你的记性真“棒”
