书上写有序数组实现优先队列时
删除要线性时间 这个能理解 移动数组的开销
找最大要常量时间
为什么删除最大只用常量时间?是书写错了嘛?
1
Vegetable 2018-12-30 12:43:19 +08:00 via Android 1
从小到大的有序数组删除最后一个元素是常量,删除第一个是线性
查找最小和最大是常量 删除任意一个是线性,插入任意一个也是线性。 删除最大就是出列操作,队列的出列设计成常量时间也是很合理的。 因为是删除最后一个元素,不需要移动其他的,自然就是 o1 |
6
sulinehk OP @leoaqr 不对 好像二分插入也是线性 先二分搜索要 lgn 再移位要线性 加起来大 O 线性?
|