算法概念
算法是若干指令的有穷序列，满足以下性质：
- 输入：外部量作为输入
- 输出：至少产生一个量
- 确定性：每条指令是无歧义的
- 有限性：每条指令的执行次数和时间是有限的
- 可行性: 能够有效解决问题的
算法分析
算法分析是指对算法所需的时间和空间等资源进行预测。
算法复杂性 = 算法所需要的计算机资源。
时间复杂性 \(T(n)\) ，\(p(I)\) 是实例 \(I\) 出现的概率。
- 最坏情况：\(T_{max}(n)=max\left\{T(I)|size(I)=n\right\}\)
- 最好情况：\(T_{min}(n)=min\left\{T(I)|size(I)=n\right\}\)
- 平均情况：\(T_{avg}(n)=\sum_{size(I)=n}{p(I)T(I)}\)
空间复杂性 \(S(n)\)
当输入规模足够大时，运行时间中的低阶项和最高次项的常数系数可以忽略。
分析插入排序
一个算法的运行时间是指在特定输入时所执行的基本操作数（通常是算法最内层循环中最费时的操作）。
- 一般地，算法的运行时间与输入规模同步增长。
- 即使规模相同的两个不同输入，其运行时间也可能差别很大。
- 常量 \(c_i\) 表示执行第 \(i\) 行所花的时间。
- \(j\) 表示 \(for\) 循环的次数，\(t_j\) 表示第 \(j\) 次 \(for\) 循环的 \(while\) 循环的次数。
因此，插入排序的运行时间：\(T(n)=c_1*n+c_2*(n-1)+c_4*(n-1)+c_5*\sum_{j=2}^n{t_j}+c_6*\sum_{j=2}^n{(t_j-1)}+c_7*\sum_{j=2}^n{(t_j-1)}+c_8*(n-1)\)
最好的情况：数组已排好序，此时 \(t_j=1\)
因此，插入排序的运行时间：\(T(n)=c_1*n+c_2*(n-1)+c_4*(n-1)+c_5*(n-1)+c_8*(n-1)=(c_1+c_2+c_4+c_5+c_8)*n-(c_2+c_4+c_5+c_8)\)
\(T(n)\) 可以表示为 \(an+b\)，线性函数，其中 \(a\) 和 \(b\) 依赖于语句代价 \(c_i\)
最坏的情况：数组逆序，此时 \(t_j=j\)
因此，插入排序的运行时间：
\(\sum_{j=2}^n{t_j}=\sum_{j=2}^n{j}=\frac{n*(n+1)}{2}-1\)
\(\sum_{j=2}^n{(t_j-1)}=\sum_{j=2}^n{(j-1)}=\frac{n*(n-1)}{2}\)
\(T(n)=(\frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2})*n^2+(c_1+c_2+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8)*n-(c_2+c_4+c_5+c_8)\)
\(T(n)\) 可以表示为 \(an^2+bn+c\)，其中 \(a、b、c\) 依赖于语句代价 \(c_i\)
平均情况：\(E(t_j)=\frac{1}{j}(1+2+\cdot\cdot\cdot+j)=\frac{j+1}{2}\)
同最坏情况，最终 \(T(n)\) 可以表示为 \(an^2+bn+c\)
渐进符号
渐近上界记号 \(O\)（大 \(O\)），可用于标识最坏情况运行时间
渐近地给出了一个函数在常量因子内的上界：
\(O(g(n))=\left\{f(n):存在正常量c和n_0，使得对所有n_0\leq{n}，有0\leq{f(n)}\leq{cg(n)}\right\}\)
渐近下界记号 \(\Omega\)（大 \(\Omega\)），用于标识最佳情况运行时间
渐近地给出了一个函数在常量因子内的下界：
\(\Omega(g(n))=\left\{f(n):存在正常量c和n_0，使得对所有n_0\leq{n}，有0\leq{cg(n)}\leq{f(n)}\right\}\)
渐近紧确界记号 \(\Theta\)
渐近地给出了一个函数的上界和下界：
\(\Theta(g(n))=\left\{f(n):存在正常量c_1、c_2和n_0，使得对所有n_0\leq{n}，有0\leq{c_1g(n)}\leq{f(n)}\leq{c_2g(n)}\right\}\)
\(\Theta(g(n))\) 中所有函数都具有相同的最高阶项，\(f(n)\in{\Theta(g(n))}\)，当且仅当 \(f(n)\in{O(g(n))}\) 且 \(f(n)\in{\Omega(g(n))}\)
非渐近紧确上界记号 \(o\)（小 \(o\)）
\(o(g(n))=\left\{f(n):对任意正常量c>0，存在正常量n_0>0，使得对所有n_0\leq{n}，有0\leq{f(n)}<cg(n)\right\}\)
例如：\(5n=o(n^2)\)，虽然 \(5n^2=O(n^2)\)，但是 \(5n^2\neq{o(n^2)}\)
如果 \(f(n)=o(g(n))\)，那么 \(\lim_{n\to\infty}\frac{f(n)}{g(n)}=0\)
非渐近紧确下界记号 \(\omega\)
\(\omega(g(n))=\left\{f(n):对任意正常量c>0，存在正常量n_0>0，使得对所有n_0\leq{n}，有0\leq{cg(n)}<f(n)\right\}\)
例如：\(5n^2=\omega(n)\)，虽然 \(5n^2=\Omega(n^2)\)，但是 \(5n^2\neq{\omega(n^2)}\)
如果 \(f(n)=\omega(g(n))\)，那么 \(\lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty\)
所以，\(f(n)=\omega(g(n))\)，当且仅当 \(g(n)\in{o(f(n))}\)
极限
用极限去定义渐近符号：
\[\lim_{n\to\infty}\frac{f(n)}{g(n)}= \begin{cases} c>0, & 则f(n)=\Theta(g(n))\\ 0, & 则f(n)=o(g(n))\\ \infty, & 则f(n)=\omega(g(n)) \end{cases} \]- 前两种情况意味着 \(f(n)=O(g(n))\)
- 后两种情况意味着 \(f(n)=\Omega(g(n))\)
性质
传递性
- \(f(n)=O(g(n))\) 且 \(g(n)=O(h(n))\)，则 \(f(n)=O(h(n))\)
- \(f(n)=\Omega(g(n))\) 且 \(g(n)=\Omega(h(n))\)，则 \(f(n)=\Omega(h(n))\)
- \(f(n)=\Theta(g(n))\) 且 \(g(n)=\Theta(h(n))\)，则 \(f(n)=\Theta(h(n))\)
- \(f(n)=o(g(n))\) 且 \(g(n)=o(h(n))\)，则 \(f(n)=o(h(n))\)
- \(f(n)=\omega(g(n))\) 且 \(g(n)=\omega(h(n))\)，则 \(f(n)=\omega(h(n))\)
自反性
- \(f(n)=O(f(n))\)
- \(f(n)=\Omega(f(n))\)
- \(f(n)=\Theta(f(n))\)
- \(o、\omega\) 没有自反性
对称性
- \(f(n)=\Theta(g(n))\)，当且仅当 \(g(n)=\Theta(f(n))\)
- \(f(n)=O(g(n))\)，当且仅当 \(g(n)=\Omega(f(n))\)
- \(f(n)=o(g(n))\)，当且仅当 \(g(n)=\omega(f(n))\)
定理
-
如果 \(t_1(n)\in{O(g_1(n))}\) 且 \(t_2(n)\in{O(g_2(n))}\)，则 \(t_1(n)+ t_2(n)\in{O(max\left\{g_1(n),g_2(n)\right\})}\)
-
如果 \(t_1(n)\in{\Omega(g_1(n))}\) 且 \(t_2(n)\in{\Omega(g_2(n))}\)，则 \(t_1(n)+ t_2(n)\in{\Omega(max\left\{g_1(n),g_2(n)\right\})}\)
-
如果 \(t_1(n)\in{\Theta(g_1(n))}\) 且 \(t_2(n)\in{\Theta(g_2(n))}\)，则 \(t_1(n)+ t_2(n)\in{\Theta(max\left\{g_1(n),g_2(n)\right\})}\)
当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定，即效率较差的部分决定。
常用函数
多项式
对于一个 \(d\) 次的多项式 \(p(n)=\sum_{i=0}^d{a_in^i}\)，有 \(p(n)=\Theta(n^d)\)
若对某个常量 \(k\)，使得 \(f(n)=O(n^k)\)，则称函数 \(f(n)\) 是多项式有界的。
指数
对任意常数 \(a>1、b\)，\(\lim_{n\to\infty}\frac{n^b}{a^n}=0\)，故 \(n^b=o(a^n)\)，即任意正的指数函数较任意的多项式增长更快。
对数
若对某个常量 \(k\)，使得 \(f(n)=O(lg^kn)\)，则称函数 \(f(n)\) 是多对数有界的。
\(\lim_{n\to\infty}\frac{lg^bn}{2^{a^{lgn}}}=\lim_{n\to\infty}\frac{lg^bn}{n^a}=0\)，故 \(lg^bn=o(n^a)\)，即任意正的多项式函数较多项对数函数增长更快。
阶乘
\(n!\) 的弱上界是 \(n!\leq{n^n}\)
斯特林近似公式：\(n!=\sqrt{2\pi{n}}(\frac{n}{e})^n(1+\Theta(\frac{1}{n})\)
由上述公式可得：\(n!>(\frac{n}{e})^n\)
由于 \(\lim_{n\to\infty}\frac{b^n}{(n/e)^n}=\lim_{n\to\infty}(\frac{b}{n/e})^n=\lim_{n\to\infty}(\frac{be}{n})^n=0\)，故 \(b^n=o(n!)\)
根据斯特林近似公式还有如下结论：
- \(n!=o(n^n)\)
- \(n!=\omega(2^n)\)
- \(lg(n!)=\Theta(nlgn)\)