一、绪论

本章导览

共 2 个小节：数据结构的基本概念、算法和算法评价

本章重点

• 三要素：逻辑结构（线性/树/图/集合）、存储结构（顺序/链式/索引/散列）、运算
• 逻辑结构与存储结构相互独立，同一逻辑结构可有不同存储
• 复杂度量级基准：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

数据结构的基本概念

关键点

• 数据元素是基本单位，由不可分的数据项组成
• 同一批元素在线性（一对一）、树形（一对多）、图（多对多）中关系不同

算法和算法评价

关键点

• 算法：有穷、确定的指令序列；评价看时间 / 空间复杂度
• 二分查找 O(log n) 但要求有序；快排平均最优但不稳定