# 基本概念

# 算法 (Algorithm)

• 算法是指解决问题的一种方法或一个过程。
• 算法是若干指令的有穷序列，满足性质：
  • 输入，输出，确定性，有限性

# 程序 (Program)

• 程序是算法用某种程序设计语言的具体实现。
• 程序可以不满足算法的性质 (4) 有限性。
• 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
• 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

# 算法分析基本概念

• 算法运行所需要的计算机资源的量称为算法的复杂性。
• 算法的时间复杂性$T(n)$；
• 算法的空间复杂性$S(n)$。
• 其中 n 是问题的规模（输入大小）。
  计算算法运行所需资源量的过程称为算法复杂性分析，简称为算法分析。

# 算法的时间复杂性

1. 最坏情况下的时间复杂性
   $T_{max}(n) = max$
2. 最好情况下的时间复杂性
   $T_{min}(n) = min$
3. 平均情况下的时间复杂性
   $T_{avg}(n) =\displaystyle \sum _{size(I)=n}P(I)T(I)$

其中 I 是问题的规模为 n 的实例，p (I) 是实 例 I 出现的概率。

# 算法渐近复杂性

$T(n) \to \infty , as \ n\to \infty$;
$(T(n) - t(n) )/ T(n) \to 0 ，as \ n\to \infty$;
t (n) 是 T (n) 的渐近性态，为算法的渐近复杂性。
在数学上， t (n) 是 T (n) 的渐近表达式，是 T (n) 略去低阶项留下的主项。它比 T (n) 简单。

# 渐近分析的记号

在下面的讨论中，对所有$n，f(n) \geq 0，g(n) \geq 0$。

1. 渐近上界记号$O$
   $O(g(n))=\{f(n) | 存在正常数c和n_0使得对所有n\geq n_0有： f(n) \leq cg(n) \}$

2. 渐近下界记号$\Omega$
   $\Omega(g(n))=\{f(n) | 存在正常数c和n_0使得对所有n\geq n_0有：0 \leq cg(n) \leq f(n) \}$

3. 非紧上界记号$o$
   $o(g(n)) = \{ f(n) | 对于任何正常数c > 0,存在正数n_0>0使得对所有n\geq n_0有：0 \leq f(n) \leq cg(n) \}$
   等价于 $f(n) / g(n) \to 0,as \ n\to \infty$

4. 非紧下界记号$\omega$
   $\omega(g(n)) = \{ f(n) | 对于任何正常数c > 0,存在正数n_0>0使得对所有n\geq n_0有：0 \leq cg(n) \leq f(n) \}$
   等价于 $f(n) / g(n) \to \infty,as \ n\to \infty$
   $f(n)\in \omega (g(n))\iff g(n) \in o(f(n))$

5. 紧渐近界记号$\Theta$
   $\Theta (g(n))=\{ f(n) | 存在正常数c_1,c_2和n_0使得对所有n \geq n_0有：c_1g(n) \leq f(n) \leq c_2g(n)\}$

• 注意到，紧渐进和非紧渐进的区别在于常数 c 是不是任意的，渐进是指量级相同，例如$2n^2,3n^2$, 而非紧渐进则是量级不同，例如$n^2,n^3$
• 同时，上下界不止一个，所以该函数 (例如$O(g(n))$) 的指向也是不定的，他可以同时代表多个满足条件的多项式，详见下文
• 定理 1:$\Theta(g(n))=O(g(n))\cap \Omega(g(n))$

# 渐近分析记号在等式和不等式中的意义

• $f(n)=\Theta(g(n))$ 的确切意义是:$f(n)\in \Theta(g(n))$
• 一般情况下，等式和不等式中的渐近记号$\Theta(g(n))$ 表示$\Theta(g(n))$ 中的某个函数。

# 渐近分析记号的若干性质

1. 传递性
   1. $f(n)=\Theta(g(n)),g(n)=\Theta(b(n)) \implies f(n)=\Theta(b(n))$
   2. 上述$\Theta$ 可换成任意其他四个符号
2. 反身性
   1. $f(n)=\Theta(f(n))$
   2. $f(n)=O(f(n))$
   3. $f(n)=\Omega(f(n))$
3. 对称性
   $f(n)=\Theta(g(n)) \iff g(n)=\Theta(f(n))$
4. 互对称性
   1. $f(n)=O(g(n)) \iff g(n)=\Omega(f(n))$
   2. $f(n)=o(g(n)) \iff g(n)=\omega(f(n))$

算术运算

1. $O(f(n))+O(g(n))=O(max\{f(n),g(n)\})$

证明

• 对于任意 f$_1(n)\in O(f(n))$, 存在正常数$c_1$ 和自然数$n_1$, 使得对所有$n \geq n_1$，有$f_1(n) \leq c_1f(n)$ 。
• 类似地，对于任意$g_1(n) \in O(g(n))$ ，存在正常数$c_2$ 和自然数$n_2$，使得对所有$n\geq n_2$，有$g_1(n) \leq c_2g(n)$ 。
• 令$c_3=max\{c_1, c_2\}， n_3 =max\{n_1, n_2\}，h(n)= max\{f(n),g(n)\}$ 。
• 则对所有的 $n \geq n_3$，有
  $f_1(n) +g_1(n) \leq c_1f(n) + c_2g(n)$
  $\leq c_3f(n) + c_3g(n)= c_3(f(n) + g(n))$
  $\leq c_3\ 2 max\{f(n),g(n)\}$
  $= 2c_3h(n) = O(max\{f(n),g(n)\})$

2. $O(f(n))+O(g(n))=O(f(n)+g(n))$

证明

• 对于任意 f$_1(n)\in O(f(n))$, 存在正常数$c_1$ 和自然数$n_1$, 使得对所有$n \geq n_1$，有$f_1(n) \leq c_1f(n)$ 。
• 类似地，对于任意$g_1(n) \in O(g(n))$ ，存在正常数$c_2$ 和自然数$n_2$，使得对所有$n\geq n_2$，有$g_1(n) \leq c_2g(n)$ 。
• 令$c_3=max\{c_1, c_2\}， n_3 =max\{n_1, n_2\}$ 。
• 则对所有的 $n \geq n_3$，有
  $f_1(n) +g_1(n) \leq c_1f(n) + c_2g(n)$
  $\leq c_3f(n) + c_3g(n)= c_3(f(n) + g(n))$
  $= O(f(n)+g(n))$

3. $O(f(n))\times O(g(n))=O(f(n)\times g(n))$

证明

• 对于任意 f$_1(n)\in O(f(n))$, 存在正常数$c_1$ 和自然数$n_1$, 使得对所有$n \geq n_1$，有$f_1(n) \leq c_1f(n)$ 。
• 类似地，对于任意$g_1(n) \in O(g(n))$ ，存在正常数$c_2$ 和自然数$n_2$，使得对所有$n\geq n_2$，有$g_1(n) \leq c_2g(n)$ 。
• 令$c_3=max\{c_1, c_2\}， n_3 =max\{n_1, n_2\}$ 。
• 则对所有的 $n \geq n_3$，有
  $f_1(n) \times g_1(n) \leq c_1f(n) \times c_2g(n)$
  $\leq c_1\times c_2 f(n) \times g(n)= c_3(f(n) \times g(n))$
  $O(f(n)\times g(n))$

4. $g(n)=O(f(n))\implies O(f(n))+O(g(n))=O(f(n))$

证明

• 对于任意 f$_1(n)\in O(f(n))$, 存在正常数$c_1$ 和自然数$n_1$, 使得对所有$n \geq n_1$，有$f_1(n) \leq c_1f(n)$ 。
• 对于任意$g(n) \in O(f(n))$ ，存在正常数$c_2$ 和自然数$n_2$，使得对所有$n\geq n_2$，有$g(n) \leq c_2f(n)$ 。
• 对于任意$g_1(n) \in O(g(n))$ ，存在正常数$c_3$ 和自然数$n_2$，使得对所有$n\geq n_3$，有$g_1(n) \leq c_3g(n)$ 。
• 令$c_4=max\{c_1, c_2\times c_3\}， n_4 =max\{n_1, n_2,n_3\}$ 。
• 则对所有的 $n \geq n_4$，有
  $O(f(n))+O(g(n))=f_1(n)+g_1(n) \leq c_1f(n) + c_3g(n)$
  $\leq c_1f(n) + c_3\times c_2f(n)$
  $\leq c_4f(n)$
  $= O(f(n))$

5. $O(cf(n))=O(f(n))$, 其中 c 为正常数

证明

• 对于任意 f$_1(n)\in O(cf(n))$, 存在正常数$c_1$ 和自然数$n_1$, 使得对所有$n \geq n_1$，有$f_1(n) \leq c_1cf(n)$ 。
• 令$c_2=max\{c_1c, c_1,c\}$ 。
• 则对所有的 $n \geq n_1$，有
  $f_1(n) \leq c_1cf(n)$
  $\leq c_2f(n)=O(f(n))$

6. $f(n)=O(f(n))$

证明

渐进上界记号定义为:
$O(g(n))=\{f(n) | 存在正常数c和n_0使得对所有n\geq n_0有： f(n) \leq cg(n) \}$
取$g(n)=f(n),c=1$, 代入即可

# 算法渐近复杂性分析中常用函数

• $a^{log_bc}=a^{\frac{logc}{logb}}=a^{\frac{logc}{loga} \times \frac{loga}{logb}}=a^{(\frac{logc}{loga})^{(\frac{loga}{logb})}}=c^{\frac{loga}{logb}}=c^{log_ba}$
• $n!=\sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))$
• $n!=\sqrt{2\pi n}(\frac{n}{e})^ne^{\alpha_n},\frac{1}{12n+1}<\alpha_n<\frac{1}{12n}$
• $n!=o(n^n)$
• $n!=\omega(2^n)$
• $log(n!)=\Theta(nlogn)$

# 算法分析的基本法则

# 非递归算法：

1. for /while 循环
   循环体内计算时间 * 循环次数；
2. 嵌套循环
   循环体内计算时间 * 所有循环次数；
3. 顺序语句
   各语句计算时间相加；
4. if-else 语句
   if 语句计算时间和 else 语句计算时间的较大者。