知识卡片
查找结构按查询与更新权衡
存在性查询回答目标是否存在;检索查询返回匹配元素;关联查找由键获得附加信息。设计接口时应明确匹配规则、重复键行为以及未找到如何表示,避免把合法值与缺失哨兵混淆。
索引或排序可加速某些查询,但建立、插入、删除和额外空间均有成本;应按查询频率、更新频率、随机访问能力和数据量一起选择结构。
112指出无序链表头插在已持有头指针时为常数操作;尾插需有尾指针,删除给定值通常先线性查找,而已持有合适节点或前驱时删除成本可以不同。数组扩容与移动也要计入总体工作量。
120指出有序数组便于二分查找,插入和删除可能移动 O(n) 元素;动态树等结构可以调整更新与查询成本,但具体界依赖平衡策略和实现。
122指出磁盘数据也可以按偏移读取,但单次随机读取、缓存与记录长度影响延迟;页式索引等结构可能减少外部存储访问,不应只比较内存中的比较次数。
130强调需要结合输入的静态或动态性质选择存储结构;查找快慢还要包括冲突处理和容量管理。
301与03468–03469图算法表强调优先队列及结构操作成本;二叉堆可取最小,但一般成员查询是线性时间,可额外维护索引或使用其他结构。不存在仅凭选择数据结构就使任意问题达到 O(n log n) 的普遍保证。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 查找结构按查询与更新权衡
- · 驱动因素
- · 驱动因素
- · 结论
- · 结果
- · 原则:选择正确的数据结构
原书出处 · 6 处
- · 查看原书依据
存在性查询:C包含一个目标元素t吗? 很多时候我们只想知道一个给定集合C中是否包含一个特定的值t。如果这样的元素存在并且其值和t相等,那么这个查询的结果将是真,否则的话就是假。 检索查询:返回C中值和t匹配的元素。 当复杂的元素存储在该集合时,元素匹配的定义是基于键值或者元素的属性集合的子集匹配。例
- · 查看原书依据
查找次数来看,顺序查找也许是最有效的查找算法。如果n相当低效,或者你不经常执行查找操作,那么对元素排序或者使用一个复杂的数据结构将得不偿失。 如果集合是无序的,并且是以链表的形式存储的,那么插入元素是一个常数时间的操作(仅仅简单地插入到表头或者表尾)。频繁地插入到一个数组形式存储的集合需要动态的数组
- · 查看原书依据
添加或者移除元素,这个方法就变得非常笨拙。你可以使用很多数据结构,最著名的一个是二叉树,将在“变种”中讨论。
- · 查看原书依据
二级存储器中,例如在磁盘上以文件的形式。在这种情况下,第i个元素能够根据其在文件中的偏移量来存取。如果使用二级存储器,查找一个元素所需要的时间就主要是存取二级存储器所需要的开销,其他和二分查找相关的解决方案也适用。参考算法的“变种”一节,其中对这些问题进行了处理。
- · 查看原书依据
动态性质是非常必要的,这有助于选择合适的数据结构。
- · 查看原书依据
选择正确的数据结构 著名算法设计者Robert Tarjan曾经引用过这样一句话:“如果使用正确的数据结构,任何问题都能够在O(n log n)的时间内解决掉”。许多算法需要使用有限队列来存储中间过程或者下一步运算。实现优先队列最常见的要数二叉堆了,它能够在O(log n)的时间内从优先队列中将最低