算法设计与分析 - 证明与复杂度分析

1 证明

1.1 构造证明

1.2 反向证明

• 反证法
• 逆否命题

1.3 分类讨论

1.4 数学归纳法

• 弱数学归纳法
  • 假设k成立，证明k+1成立
• 最小反例集（贪心）
  • 假设k为最小的反例，则k-1成立，证明两者矛盾
• 强数学归纳法
  • 假设从$n_0$~k都成立，证明k+1成立

1.5 Peano公理

1.6 伪代码

• 标题
• 输入、输出
• 注释
  • 注释行没有行号
  • 只标注重要步骤

2 算法分析

2.1 计算理论

2.2 时间复杂度

• O上确界、$\Omega$下确界、$\Theta$等势
• o上界、$\omega$下界
• 
• 偏序小于$\prec$，可看做小o关系
• $\sum\lfloor x \rfloor$形式一般用两边夹来分析

2.3 空间复杂度

2.4 复杂度分析

• best
• worst
• average
• amortized 均摊分析
  • 考虑的是worst case

3 搜索算法

• 线性搜索
  • best: $\Omega$(1)
  • worst: O(n)
  • average: O(n)
  • 空间复杂度: O(1)
• 二分搜索
  • best: $\Omega$(1)
  • worst: O(logn)
  • average: O(logn)
  • 空间复杂度: O(1)

4 线性排序算法

• 选择排序
  • best: $\Theta (n^2)$
  • worst: $\Theta (n^2)$
  • average: $\Theta (n^2)$
  • 空间复杂度: O(1)
  • 通过增加break，在特殊情况下可以提前结束
• 冒泡排序
  • best: $\Theta (n^2)$
  • worst: $\Theta (n^2)$
  • average: $\Theta (n^2)$
  • 空间复杂度: O(1)
• 插入排序
  • best: $\Omega (n)$
  • worst: $O(n^2)$
  • average: $O(n^2)$
    • 先对第i个要插入的数进行分析：可能的插入位置有i个
    • 再对所有的i进行求和：共需要插入n次
  • 空间复杂度: O(1)

5 递归排序算法

• 归并排序
  • 比较两个长度分别为m和n的段，需要的操作次数
    • best: min{m, n}
    • worst: m + n - 1
  • best: $\Theta(nlogn)$
  • worst: $\Theta(nlogn)$
  • average: $\Theta(nlogn)$
  • 空间复杂度: O(n)
• 快速排序
  • best: $\Omega(nlogn)$
    • 每次的pivot都把数组均分，因此与merge sort相似
  • worst: $O(n^2)$
    • 每次的pivot都在数组端点，于是退化成线性算法
  • average: O(nlogn)
  • 空间复杂度: O(logn)
    • 对于每一层，只需要维护一个pivot即可（先不考虑并行）