知识卡片
数组有序性转移操作成本
无序数组可让插入、删除为 Θ(1),但查找和次序相关查询为 Θ(n)。
保持数组有序后,极值与前驱后继可为 Θ(1),二分查找为 O(log n),代价是插入、删除最坏 Θ(n)。
预先排序没有消除成本,只是把成本移到更新。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第三部分 数据结构 · 查看原书依据
If instead the array is maintained in sorted order, then MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR take Θ(1) time
参考来源
- 位置:《算法导论(第4版)》第三部分引言(`OEBPS/part003.xhtml`,文本字符 [3500, 5300))。
- 结论依据:原文逐项对比无序与有序数组上的操作时间。
- 原始内容:If instead the array is maintained in sorted order, then M INIMUM , M AXIMUM , S UCCESSOR , and P REDECESSOR take Θ(1) time