绪论

O记号

问题：随着问题规模的增长，计算成本是如何变化的？考虑的是计算成本的增长趋势
分析：在问题规模足够大的情况下，计算成本如何变化：
- 需要执行的基本操作次数T(n)
- 需要占用的存储单元数量S(n)，一般不考虑空间占用
对于T(n)转为O(f(n))
- 常系数可以忽略，低次项可以忽略
O复杂度计算基于悲观的角度
判断代码的复杂度
- 常数复杂度O(1)：不含转向（循环、调用、递归等），部分特例虽然含有循环、调用、递归等，但是需要考虑到实际情况才能确定。
- 对数复杂度O(log n)：高效，复杂度无限接近常数
- 多项式复杂度O(n^c)：界定为多项式的最高次项
- 线性复杂度O(n)
- 指数复杂度O(c^n)：计算成本高

void func(int n){
    // n是正整数
    int i = 1;
    while(i<=n)i*=2;
}
// 被嵌套的深层语句是i*=2；频率由i<=n决定，显然时间复杂度为O(log n)

冒泡排序

观察：有序序列中，任意一对相邻元素顺序 / 无序序列中，存在一对相邻元素逆序
算法：依次比较每一对相邻元素，如果逆序则交换。如果某一趟没有元素进行交换，则算法结束；否则，再次进行一次扫描。
分析优化算法：
- 通过分析运算过程，可以得到冒泡算法的三个特性：
  - 不变性：经过k轮的扫描，最大的k个元素必然就位
  - 单调性：问题规模减小到n-k
  - 正确性：最多需要扫描n次

数据逻辑结构层次图

逻辑结构	物理结构
线性表	顺序存储结构、链式存储结构
树	顺序存储结构、链式存储结构
图	复合存储结构

数据的逻辑结构
- 线性结构
  - 一般线性表
  - 受限线性表
    - 栈
    - 队列
    - 串
  - 线性表推广
    - 数组
    - 广义表
- 非线性结构
  - 集合
  - 树形结构
    - 一般树
    - 二叉树
  - 图形结构
    - 有向图
    - 无向图

算法初步分析

算法是对特定问题的求解方法的一种描述，是指令的有限序列。
算法特性：
- 有穷性：算法必须在执行有穷步骤后结束，每一步执行时间。
- 确定性：算法每一条指令要有其确定含义，只有一个出口和一个入口。
- 可行性：描述的操作可以通过有限次基本运算实现。
- 输入
- 输出
算法设计的要求：
- 正确性
- 可读性
- 健壮性：算法应当具有容错处理
- 效率和存储量需求：高效率和低存储需求为调优方向
- 通用性：对一般数据结构均成立