概述
1.概述
1.1 程序 = 数据结构 + 算法
一个完整的程序可以拆解为两部分：数据结构负责数据怎么存，算法负责数据怎么用，两者共同决定了程序的性能与效率。
1.2 数据结构
数据结构（Data Structure）是指存储、组织数据的方式——相互之间存在一种或多种特定关系的数据元素的集合。
数据的种类有很多：字符串、整数、浮点、对象... 同样的数据，用不同的方式组织，就形成了不同的数据结构。
举例
同样存放 1~10 这组数据，可以组织成不同的结构：
- 线性地存成一个列表（顺序表）
- 分支地存成一棵树
- 关联地存成一张图
数据相同、结构不同，之后的查找、插入、删除等操作的效率就会不同。
1.3 数据结构的分类
数据结构通常分为两大类：
| 类别 | 特点 | 典型 |
|---|---|---|
| 线性结构 | 各结点具有线性关系，最多只有一个直接前驱结点和一个直接后继结点 | 栈、队列、链表 |
| 非线性结构 | 各结点具有多个对应关系，一个结点可能有多个直接前驱结点和直接后继结点 | 树、图 |
1.4 常用的数据运算
在数据结构上最常见的五种操作：
插入、删除、修改、查找、排序
1.5 算法
算法（Algorithm）是指为满足业务需求、实现业务目的而采取的方法和思路。
算法是为解决实际问题而设计的，数据结构是算法要处理问题的载体。同样的数据、同样的目的，不同的算法用不同的方法和思路，执行效率就会不同。
一句话总结
数据结构回答"数据怎么存"，算法回答"数据怎么用"，两者结合构成了程序的核心：程序 = 数据结构 + 算法。
2.算法的特性
2.1 算法的独立性
算法是独立存在的一种解决问题的方法和思想——与具体编程语言无关，重要的是思想本身。同一个算法可以用不同语言描述实现（如 C 描述、C++ 描述、Python 描述等），但思想是一样的。
2.2 算法的五大特性
| 特性 | 说明 |
|---|---|
| 有输入 | 算法具有 0 个或多个输入 |
| 有输出 | 算法至少有 1 个或多个输出 |
| 有穷性 | 算法在有限步骤后会自动结束，不会无限循环，且每一步都能在可接受的时间内完成 |
| 确定性 | 算法中的每一步都有确定含义，不会出现二义性 |
| 可行性 | 算法的每一步都是可行的，即每一步都能执行有限次完成 |
3.算法的时间效率衡量
如何客观评判一个算法的优劣？
我们假定计算机执行算法的每一个基本操作耗时固定为一个时间单位，那么基本操作的数量就代表了花费的时间——由此可以忽略机器环境的影响，客观反映算法的时间效率：
时间效率： 代码执行总时间(T) = 操作步骤数量 × 操作步骤执行时间
3.1 时间复杂度
时间复杂度表示一个算法随问题规模变化的主要趋势，用来衡量算法的优劣。通俗地说，它衡量的是"算法的量级"。
3.2 时间复杂度的表示形式——大 O 记法
大 O 记法用来表示时间复杂度随数据量变化的关系曲线，通常由最高次项决定：
- 主要条件：随问题规模变化而变化的条件
- 次要条件：随问题规模变化而不变的条件
当数据量较大时，低次项（次要条件）对结果的影响相对于最高次项很小，可以忽略。
3.3 时间复杂度的计算规则
| 结构 | 时间复杂度 |
|---|---|
| 基本操作 | O(1) |
| 顺序结构 | 按加法计算 |
| 循环结构 | 按乘法计算 |
| 分支结构 | 取最大值（最高次项） |
说明
- 判断算法效率时，只需关注操作数量的最高次项，次要项和常数项可以忽略。
- 在没有特殊说明时，我们分析的时间复杂度都是指最坏时间复杂度（算法的性能保证）。
3.4 最优、最坏与平均复杂度
分析算法时，通常从三种情况考量所需的基本操作数量：
| 复杂度 | 定义 | 参考价值 |
|---|---|---|
| 最优时间复杂度 | 完成工作最少需要的基本操作数 | 只反映最乐观情况，没有参考价值 |
| 最坏时间复杂度 | 完成工作最多需要的基本操作数 | 算法的性能保证——一定能在此复杂度内完成 |
| 平均时间复杂度 | 完成工作平均需要的基本操作数 | 评价全面，但难以计算（实例分布可能不均） |
结论
我们主要关注算法的最坏情况，即最坏时间复杂度——它才是算法可靠的性能保证。
3.5 常见时间复杂度
| 执行次数举例 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n²+2n+1 | O(n²) | 平方阶 |
| 5log₂n+20 | O(log n) | 对数阶 |
| 6n³+2n²+3n+4 | O(n³) | 立方阶 |
常见复杂度随数据量从小到大排列：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³)时间复杂度越低，效率越高。
备注
- O(log n)：大 O 记法下，时间 T 随问题规模变化的曲线呈对数趋势，典型如二分法（每轮把问题规模减半）。
- O(n log n)：外层循环执行 n 次，内层是二分（log n），两者相乘组合而成，典型如归并排序。
4.算法的空间效率衡量
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。
类似于时间复杂度，一个算法的空间复杂度 S(n) 定义为该算法所耗费的存储空间，同样使用大 O 记法。常见的有：
O(1) < O(log n) < O(n) < O(n²) < O(n³)4.1 常数阶 O(1)
普通常量、变量、对象，以及元素数量与输入数据大小 N 无关的集合，都使用常数大小的空间。
4.2 线性阶 O(n)
元素数量与 N 呈线性关系的集合（常见于一维数组、链表等），使用线性大小的空间。
4.3 平方阶 O(n²)
元素数量与 N 呈平方关系的集合（常见于矩阵），使用平方大小的空间。