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

文章目录

• • @[toc]
  • • 1.1|算法与程序
    • • 算法
      • • 性质
      • 程序
    • 1.2|算法复杂性分析
    • • 算法复杂性
      • 时间复杂性
      • • 最坏情况下的时间复杂性
        • 最好情况下的时间复杂性
        • 平均情况下的时间复杂性
      • 渐进复杂性
      • O表示法
      • • 运算规则
        • • 证明
      • Ω表示法
      • θ表示法
      • o表示法
    • 1.3|NP完全性理论
    • • 判定形式的旅行售货员问题
      • P类问题
      • NP类问题
      • NP完全问题——NPC问题

个人主页：丷从心·

系列专栏：算法

1.1|算法与程序

算法

性质

• 确定性：组成算法的每条指令是清晰的，无歧义的

• 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

程序

• 程序可以不满足有限性

1.2|算法复杂性分析

算法复杂性

• 分别用$N$、$I$和$A$表示算法要解的问题的规模、算法的输入和算法本身，用$C$表示复杂性，有$C=F(N,I,A)$

• 通常$A$隐含在复杂性函数名当中

时间复杂性

• $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)$，对于每个$i(1\le i\le k)$，$e_i$是$N$和$I$的函数，即$e_i=e_i(N,I)$，因此有$T(N,I)=\sum _{i=1}^k{t}_i{e}_i(N,I)$

最坏情况下的时间复杂性

• $T_{\max }(N)=\underset{I\in D_N}{\max }T(N,I)=\underset{I\in D_N}{\max }\sum _{i=1}^k{t}_i{e}_i(N,I)=\sum _{i=1}^k{t}_i{e}_i(N,I^{\ast })=T(N,I^{\ast })$

• $D_N$是规模为$N$的合法输入的集合，$I^{\ast }$是$D_N$中使$T(N,I)$达到$T_{\max }(N)$的合法输入

最好情况下的时间复杂性

• $T_{\min }(N)=\underset{I\in D_N}{\min }T(N,I)=\underset{I\in D_N}{\min }\sum _{i=1}^k{t}_i{e}_i(N,I)=\sum _{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)=\sum _{I\in D_N}P(I)T(N,I)=\sum _{I\in D_N}P(I)\sum _{i=1}^k{t}_i{e}_i(N,I)$

• $P(I)$是在算法的应用中出现输入$I$的概率

渐进复杂性

• 当$N$单调增大且趋于$\infty$时，$T(N)$一般也将单调增大且趋于$\infty$

• 对于$T(N)$，如果存在$\tilde{T}(N)$，当$N\to \infty$时，使得$(T(N)-\tilde{T}(N))/T(N)\to 0$，就说$\tilde{T}(N)$是$T(N)$当$N\to \infty$时的渐进性态，或称$\tilde{T}(N)$为算法$A$当$N\to \infty$的渐进复杂性

• $\tilde{T}(N)$是$T(N)$中略去低阶项留下的主项，比$T(N)$简单

O表示法

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

运算规则

• $O(f)+O(g)=O(\max (f,g))$

证明

• 设$F(N)=O(f)$，存在正常数$C_1$和自然数$N_1$，使得对所有的$N\ge N_1$，有$F(N)\le C_{1}f(N)$
• 设$G(N)=O(g)$，存在正常数$C_2$和自然数$N_2$，使得对所有的$N\ge N_2$，有$G(N)\le C_{2}g(N)$
• 令 C 3 = max ⁡ {   C 1 , C 2   } C_{3} = \max\set{C_{1} , C_{2}} C3​=max{C1​,C2​}， N 3 = max ⁡ {   N 1 , N 2   } N_{3} = \max\set{N_{1} , N_{2}} N3​=max{N1​,N2​}， h ( N ) = max ⁡ {   f , g   } h(N) = \max\set{f , g} h(N)=max{f,g}，则对所有的$N\ge N_3$，有$F(N)\le C_{1}f(N)\le C_{1}h(N)\le C_{3}h(N)$，$G(N)\le C_{2}g(N)\le C_{2}h(N)\le C_{3}h(N)$
• $O(f)+O(g)=F(N)+G(N)\le C_{3}h(N)+C_{3}h(N)=2C_{3}h(N)=O(h)=O(\max (f,g))$

Ω表示法

• 如果存在正的常数$C$和自然数$N_0$，使得当$N\ge N_0$时有$f(N)\ge Cg(N)$，则称函数$f(N)$当$N$充分大时下有界，且$g(N)$是它的一个下界，记为$f(N)=\Omega (g(N))$

• 当$f(N)$对自然数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画$f(N)$的下界，例如$f(N)=\{\begin{array}{ll}100,& N为正偶数\\ 6N^2,& N为正奇数\end{array}$，按上述定义，只能得到$f(N)=\Omega (1)$，这是一个平凡的下界，对算法分析没有什么价值

θ表示法

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

o表示法

• 如果对于任意给定的$\epsilon >0$，都存在正整数$N_0$，使得当$N\ge N_0$时有$f(N)/g(N)<\epsilon$，则称函数$f(N)$当$N$充分大时的阶比$g(N)$低，记为$f(N)=o(g(N))$

1.3|NP完全性理论

判定形式的旅行售货员问题

• 对于给定的带权图$G=(V,E)$和一个正数$d$，判定图$G$中是否存在总费用不超过$d$的周游路线

P类问题

• 所有可以在多项式时间内求解的判定问题构成$P$类问题

NP类问题

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

NP完全问题——NPC问题

• 性质：如果一个$NPC$问题能在多项式时间内得到解决，那么$NP$中的每个问题都可以在多项式时间内求解
• 第一个$NPC$问题是布尔表达式的可满足性问题，即$Cook$定理：布尔表达式的可满足性问题$SAT$是$NP$完全的
• 对于任何问题$Q$，只要能证明$Q\in NP$，而且可以在多项式时间内将$SAT$变换为问题$Q$，便有$Q\in NPC$
• $NP$完全问题树中任一结点表示的问题可以在多项式时间内变换为它的任一后裔节点表示的问题