程序设计 = 数据结构 + 算法
1 数据结构
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
1.1 基本概念
- 数据：能别计算机识别、处理的符号集合
- 数据对象：性质相同的数据元素的集合，是数据的子集。
- 数据元素：组成数据的、有一定意义的基本单位。通常作为整体被计算机处理。
- 数据项：数据元素可由多个数据项组成，数据项是数据不可分割的最小单位
graph TD 数据-->数据对象 数据对象-->数据元素1 数据元素1-->数据项1 数据元素1-->数据项2 数据对象-->数据元素2 数据元素2-->数据项3 数据元素2-->数据项4
1.2 逻辑结构和物理结构
逻辑结构
数据对象中数据元素之间的相互关系。
- 集合结构：结构中的数据元素出了同属于一个集合外，没有其他关系
- 线性结构：一对一
- 树结构：一对多
- 图结构：多对多
物理结构
数据的逻辑结构在计算机中的存储形式
- 顺序存储结构
- 链式存储结构
2 算法
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
2.1 算法的特性
算法具有五个基本特性
- 输入：零个或多个输入
- 输出：一个或多个输出
- 有穷性：执行有限步骤后，在可接受时间内自动结束
- 确定性：没有二义性，相同的输入只能有唯一输出结果
- 可行性：每一步能通过有限次数完成
2.2 算法设计的要求
- 正确性：输入、输出和加工处理无歧义性、能正确反映需求、能得到正确答案
- 可读性：便于阅读、理解和交流
- 健壮性：能够处理不合法输入
- 时间效率高和存储量低
2.3 算法时间复杂度
推导大 O 阶方法
n 是问题规模，对数列运算出执行次数T(n) = O(f(n))
- 用常数 1 取代运行时间中的加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 若最高阶项存在且不是 1， 则去除与这个项相乘的常数。
常见的时间复杂度排序： O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
最坏情况与平均情况
没有特殊说明的情况下，都指最坏时间复杂度
2.4 算法空间复杂度
S(n) = O(f(n))。
若算法执行时所需的辅助空间对于输入量而言是个常数，则称此算法为原地工作，空间复杂度 O(1)。