Jic*_*hao 1 priority-queue binary-search time-complexity sortedlist
来自维基百科：
排序列表实现：就像超市的收银台一样，但重要的人可以在不太重要的人面前“插队”。（O(n) 插入时间，O(1) 下次获取时间，O(n*log(n)) 构建时间）
我认为如果用二分查找算法来查找插入位置，插入时间复杂度应该是O(log(n))。这里我把作业的到达顺序作为优先级因素。
那么是我错了还是维基百科错了？
更新：根据 TAOCP 列表的严格定义：
线性列表是 n >=0 个节点 X 1 , X[2], ... , X[n] 的序列，其基本结构属性仅涉及项目之间出现在一行中时的相对位置。
我假设维基百科引用的列表不是链接列表，它可能是数组。
谢谢。
如果它支持链表，则不能进行二分搜索；找到插入点是 O(n)，实际插入是 O(1)，因为只需更改相邻节点，总体 O(n)。
如果它的数组支持，你可以进行二分搜索；查找插入点的时间复杂度为 O(log(n))，但插入数组的时间复杂度为 O(n)，因为您可能需要移动数组的所有元素，总体时间复杂度为 O(n)
这就是为什么你实际上有树/堆支持，所以所有操作都可以是 O(log(n))