知识卡片
结构选择取决于操作成本
同一批数据可以用不同结构组织,结构选择应看所需操作的成本。无序数组逐项查找在未找到或靠后命中时可能扫描全部元素;其他结构用额外组织和维护成本换取不同查找方式。
原文以哈希和二叉树作比较,不意味着它们无条件更快:具体性能还要看数据分布、平衡、更新频率和空间等前提,后章才展开。先列出需要哪些操作,再评价结构,避免只凭类型名决定效率。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
需要遍历数组中的每一个元素才行。通过使用另一种数据结构,比如哈希表(见第8章)或者二叉树(见第9章)我们可以显著地提高检索的速度。 抽象 数据结构使我们以一种更加容易理解的方式去看待数据。也就是说它们为解决问题提供了一层抽象概念。比如,要把数据存入一个栈(见第6章),可以把精力集中在可以对栈做什么操
参考来源
- 位置:《算法精解:C语言描述》第1章《数据结构简介》(spine1179;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1147_split_001.html;u014-ch01-003)。
- 结论依据:14效率段比较顺序数组检索与不同组织,指出可能遍历全体;本卡保留操作成本选择的理由,不把树/哈希提名当无条件更快。
- 原始内容:需要遍历数组中的每一个元素才行。通过使用另一种数据结构,比如哈希表(见第8章)或者二叉树(见第9章)我们可以显著地提高检索的速度。 抽象 数据结构使我们以一种更加容易理解的方式去看待数据。也就是说它们为解决问题提供了一层抽象概念。比如,要把数据存入一个栈(见第6章),可以把精力集中在可以对栈做什么操