算法设计与分析复习

1/8 第1章 算法概述

算法是若干指令的有穷序列，满足性质：

(1)输入(2)输出 (3)确定性 (4)有限性。

算法复杂性分析主要包括空间复杂性和时间复杂性。

算法复杂性分析

（1）渐近上界记号O

O(g(n)) = { f (n ) | 存在正常数c 和n0使得对所有n ≥ n0有：0 ≤ f (n ) ≤ cg (n ) }

（2）渐近下界记号Ω

Ω (g(n)) = { f(n) | 存在正常数c 和n0使得对所有n ≥ n0有：0≤ cg(n) ≤ f(n) }

（3）紧渐近界记号Θ

Θ (g (n )) = { f (n ) | 存在正常数c 1,c 2和n 0使得对所有n ≥ n 0有：c 1g (n ) ≤ f (n ) ≤ c 2g (n ) }

定理1： Θ (g (n )) = O (g (n )) ⋂ Ω (g (n ))

最常见的多项式时间算法的渐近时间复杂度

O(1)＜O(log n )＜O(n )＜O(n log n )＜O(n 2)＜O(n 3)

最常见的指数时间算法的渐近时间复杂度

O(2n )＜O(n ！)＜O(n n )

通用分治递推式

大小为n 的原问题分成若干个大小为n/b 的子问题，其中a 个子问题需要求解，而cn k 是合并各个子问题的解需要的工作量。

NP 完全性理论

P 是所有可在多项式时间内用确定算法求解的判定问题的集合。

NP 是所有可在多项式时间内用不确定算法求解的判定问题的集合。

（NP 难度）对于问题Q 以及任意问题Q1∈NP ，都有Q1∝Q ，则Q 是NP 难度（NP hard ）的。

其中∝表示约化，Q1∝Q ，表示Q1可以在多项式时间转化为问题Q ，从而可通过调用问题Q 的算法求解。

（NP 完全）对于问题Q ∈NP ，Q 是NP 难度的，则称Q 是NPC （NP complete ）的。 P NP NPC 的关系