《算法导论》笔记

更新说明：本文与数据结构与算法笔记互补，基本的数据结构与算法在该文中提及的不再重复介绍。

---

Foundations

算法衡量指标

渐进表示法 Asymptotic notation

• \(O\) 表示法 - 函数存在渐进上界

  设函数\(f(n),\,g(n)\)，则集合\(O(g(n))\)可表示为： \[\{f(n)\,|\,\exists{c,n_0}>0,\,\forall{n\geq{n_0}},\,0\leq{f(n)}\leq{cg(n)}\}\]

• \(\Omega\) 表示法 - 函数存在渐进下界

  设函数\(f(n),\,g(n)\)，则集合\(\Omega(g(n))\)可表示为： \[\{f(n)\,|\,\exists{c,n_0}>0,\,\forall{n\geq{n_0}},\,0\leq{cg(n)}\leq{f(n)}\}\]

• \(\Theta\) 表示法 - 函数存在渐进紧确界

  设函数\(f(n),\,g(n)\)，则集合\(\Theta(g(n))\)可表示为： \[\{f(n)\,|\,\exists{c_1,c_2,n_0}>0,\,\forall{n\geq{n_0}},\,0\leq{c_1g(n)}\leq{f(n)}\leq{c_2g(n)}\}\]

排序

插入排序 Insertion sort

方法	最好情况	最差情况	平均情况	辅助存储	稳定性
直接插入排序	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	稳定
希尔排序	\(O(n)\)	\(O(n^2)\)	\(\approx{O(n^{1.3})}\)	\(O(1)\)	不稳定

交换排序

方法	最好情况	最差情况	平均情况	辅助存储	稳定性
冒泡排序	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	稳定
快速排序	\(O(n\log_2{n})\)	\(O(n^2)\)	\(O(n\log_2{n})\)	\(O(n\log_2{n})\)	不稳定

选择排序 Selection sort

方法	最好情况	最差情况	平均情况	辅助存储	稳定性
简单选择排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	不稳定
堆排序	\(O(n\log_2{n})\)	\(O(n\log_2{n})\)	\(O(n\log_2{n})\)	\(O(1)\)	不稳定