【算法】【《计算机算法设计与分析（第5版）》笔记】第一章：算法概述

因上努力

个人主页：丷从心·

系列专栏：算法

果上随缘

$T (N, I)$ 是算法在一台抽象的计算机上运行所需要的时间，设此抽象的计算机提供的元运算有 $k$ 种，分别记为 $O_{1}$ ， $O_{2}$ ， $\cdots$ ， $O_{k}$ ，每执行一次这些元运算所需要时间分别为 $t_{1}$ ， $t_{2}$ ， $\cdots$ ， $t_{k}$
对于给定的算法 $A$ ，经统计，用到元运算 $O_{i}$ 的次数为 $e_{i} (i = 1 , 2 , \cdots , k)$ ，对于每个 $\leq i \leq k)$ ， $e_{i}$ 是 $N$ 和 $I$ 的函数，即 $e_{i} = e_{i}(N , I)$ ，因此有 $\displaystyle\sum\limits_{i = 1}^{k}{t_{i} e_{i}(N , I)}$

$T_{\max}(N) = \max\limits_{I \in D_{N}}{T(N , I)} = \max\limits_{I \in D_{N}}{\displaystyle\sum\limits_{i = 1}^{k}{t_{i} e_{i}(N , I)}} = \displaystyle\sum\limits_{i = 1}^{k}{t_{i} e_{i}(N , I^{*})} = T(N , I^{*})$
$D_{N}$ 是规模为 $N$ 的合法输入的集合， $I^{*}$ 是 $D_{N}$ 中使 $T (N, I)$ 达到 $T_{\max}(N)$ 的合法输入

$T_{\min}(N) = \min\limits_{I \in D_{N}}{T(N , I)} = \displaystyle\min\limits_{I \in D_{N}}{\displaystyle\sum\limits_{i = 1}^{k}{t_{i} e_{i}(N , I)}} = \displaystyle\sum\limits_{i = 1}^{k}{t_{i} e_{i}(N , \tilde{I})} = T(N , \tilde{I})$
$\tilde{I}$ 是 $D_{N}$ 中使 $T (N, I)$ 达到 $T_{\min}(N)$ 的合法输入

$T_{\mathrm{avg}}(N) = \displaystyle\sum\limits_{I \in D_{N}}{P(I) T(N , I)} = \displaystyle\sum\limits_{I \in D_{N}}{P(I) \displaystyle\sum\limits_{i = 1}^{k}{t_{i} e_{i}(N , I)}}$
$P (I)$ 是在算法的应用中出现输入 $I$ 的概率

当 $N$ 单调增大且趋于 $\infty$ 时， $T (N)$ 一般也将单调增大且趋于 $\infty$
对于 $T (N)$ ，如果存在 $\tilde{T}(N)$ ，当 $\rightarrow \infty$ 时，使得 $\tilde{T}(N)) / T(N) \rightarrow 0$ ，就说 $\tilde{T}(N)$ 是 $T (N)$ 当 $\rightarrow \infty$ 时的渐进性态，或称 $\tilde{T}(N)$ 为算法 $A$ 当 $\rightarrow \infty$ 的渐进复杂性
$\tilde{T}(N)$ 是 $T (N)$ 中略去低阶项留下的主项，比 $T (N)$ 简单

设 $f (N)$ 和 $g (N)$ 是定义在正数集上的正函数，如果存在正的常数 $C$ 和自然数 $N_{0}$ ，使得当 $\geq N_{0}$ 时有 $\leq C g(N)$ ，则称函数 $f (N)$ 当 $N$ 充分大时上有界，且 $g (N)$ 是它的一个上界，记为 $f (N) = O (g (N))$

设 $F (N) = O (f)$ ，存在正常数 $C_{1}$ 和自然数 $N_{1}$ ，使得对所有的 $\geq N_{1}$ ，有 $\leq C_{1} f(N)$
设 $G (N) = O (g)$ ，存在正常数 $C_{2}$ 和自然数 $N_{2}$ ，使得对所有的 $\geq N_{2}$ ，有 $\leq C_{2} g(N)$
令 $C_{3} = \max\set{C_{1} , C_{2}}$ ， $N_{3} = \max\set{N_{1} , N_{2}}$ ， $\max\set{f , g}$ ，则对所有的 $\geq N_{3}$ ，有 $\leq C_{1} f(N) \leq C_{1} h(N) \leq C_{3} h(N)$ ， $\leq C_{2} g(N) \leq C_{2} h(N) \leq C_{3} h (N)$
$\leq C_{3} h(N) + C_{3} h(N) = 2 C_{3} h(N) = O(h) = O(\max(f , g))$

如果存在正的常数 $C$ 和自然数 $N_{0}$ ，使得当 $\geq N_{0}$ 时有 $\geq C g(N)$ ，则称函数 $f (N)$ 当 $N$ 充分大时下有界，且 $g (N)$ 是它的一个下界，记为 $\Omega(g(N))$
当 $f (N)$ 对自然数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画 $f (N)$ 的下界，例如 $\begin{cases} 100 , & N 为正偶数 \\ 6 N^{2} , & N 为正奇数 \end{cases}$ ，按上述定义，只能得到 $\Omega(1)$ ，这是一个平凡的下界，对算法分析没有什么价值

定义 $\theta(g(N))$ 当且仅当 $f (N) = O (g (N))$ 且 $\Omega(g(N))$ ，称 $f (N)$ 与 $g (N)$ 同阶

如果对于任意给定的 $\varepsilon > 0$ ，都存在正整数 $N_{0}$ ，使得当 $\geq N_{0}$ 时有 $\varepsilon$ ，则称函数 $f (N)$ 当 $N$ 充分大时的阶比 $g (N)$ 低，记为 $f (N) = o (g (N))$

非确定性算法将问题求解分为猜测和验证两个阶段
- 猜测阶段是非确定性的
- 验证阶段是确定性的
设算法 $A$ 是解一个判定问题 $Q$ 的非确定性算法，如果算法 $A$ 的验证阶段可以在多项式时间内完成，则称算法 $A$ 是一个多项式时间非确定性算法，也称问题 $Q$ 是非确定性多项式时间可解的
所有非确定性多项式时间可解的判定问题构成 $NP$ 类问题