知识卡片

普通读书笔记卡 · 3620.b.1

数组有序性转移操作成本

理解等级:高级

无序数组可让插入、删除为 Θ(1),但查找和次序相关查询为 Θ(n)。

保持数组有序后,极值与前驱后继可为 Θ(1),二分查找为 O(log n),代价是插入、删除最坏 Θ(n)。

预先排序没有消除成本,只是把成本移到更新。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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