程序=数据结构+算法

数据结构

基本概念

数据 数据元素和数据项
数据对象：具有相同性质的数据元素的集合，是数据的一个子集
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
数据类型：值的集合和定义在此集合上的一组操作的总称（原子类型和结构类型）
抽象数据类型（Abstract Data Type）：是抽象数据组织及与之相关的操作，数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。

数据结构三要素

逻辑结构 存储结构 运算

逻辑结构

线性结构：线性表、栈、队列、数组
非线性结构：集合、树、图

物理结构

指数据结构在计算机中的表示或映像。存储结构会影响数据运算的速度、存储空间分配的方便与否
常用存储结构：
顺序存储（下面三种为非顺序存储）
链式存储
索引存储：附加一个索引表（索引项=关键字+地址）
散列存储（哈希存储）：根据元素的关键字计算该元素的存储地址

数据运算

每个逻辑结构都有自己的基本的数据运算
运算的定义是针对逻辑结构的，指出运算的功能
运算的实现是针对存储结构的，指出运算的具体操作步骤（即不同存储结构有着不同的实现）

算法

基本概念

五个特性

有穷性：算法必须是有穷的，而程序可以是无穷的
确定性：相同的输入只能得出相同的输出
可行性：能通过基本操作实现算法
输入
输出：算法处理的结果

优秀算法的标准

正确性
可读性
健壮性：能处理异常状况
高效率与低存储

算法效率量度

时间复杂度分析

事前预估算法时间开销T(n)与问题规模n的关系（T表示“time”）
$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
助记：常对幂指阶
一般只需挑循环中的一个基本操作分析它的执行次数与n的关系即可，如果有多层嵌套循环，只需关注最深层循环循环了几次
存在不同情况讨论时，平均时间复杂度=各个情况的循环次数与概率的加权和
可以只考虑阶数高的部分
问题规模足够大时，常数项可以忽略
大O表示“同阶”，同等数量级
多项相加，只保留最高阶项；多项相乘都保留

空间复杂度分析

空间开销(内存开销)与问题规模n的关系
$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
普通程序
内存装入程序代码和数据，一般程序代码与问题规模无关，而数据格式：
单一变量 $O(1)$
一维数组 $O(n)$
k维数组 $O(n^k)$
递归程序：空间复杂度=递归调用的深度×数据格式

master公式

递归函数可表示成$T(N) = a * T(N/b) + O(N^d)$
$log_ba > d时，时间复杂度为O(N^{log_ba})$
$log_ba < d时，时间复杂度为O(N^d)$
$log_ba = d时，时间复杂度为O(N^d * log_2N)$