算法复杂性分析

1.理解指数增长的恐怖；
理解算法分析里为什么常数倍的差别可以被忽略；

2.掌握渐近符号O、Ω、Θ的含义，能判断一个函数属于哪个渐近增长阶；

3.能对给定函数按照渐进增长率进行排序，典型考题：作业1中的第2题；

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。

分析框架

输入规模度量

算法的时间效率和空间效率都用输入规模的函数进行度量。

对相同大小的输入实例具有相同的分析结果。

对于所有的算法，对于规模更大的输入都需要运行更长的时间。

经常使用一个输入规模n为参数的函数来研究算法的效率。

运行时间的度量单位

用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。

基本操作通常是算法最内层循环中最费时的操作。

算法运行时间的估计：

$$T(n)\approx c_{op}C(n)$$

$n$是该算法的输入规模
$c_{op}$是特定计算机上一个算法基本操作的执行时间
$C(n)$是该算法需要执行的基本操作的次数

算法的最优、最差和平均效率

最差效率是指在输入规模为n时，算法在最坏情况下的效率。

最优效率是指在输入规模为n时，算法在最优情况下的效率。

平均效率是指在“典型”或“随机”输入的情况下，算法具有的行为（效率）。

增长次数

小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来。

一个需要指数级操作次数的算法只能用来解决规模非常小的问题。

指数增长是恐怖的，在算法运行时间中应当尽量避免。很多问题很容易就可以给出一个指数运行时间的穷举搜索算法，但是否都存在多项式算法？（计算机科学的核心问题）

渐近表达式

常数间的差异较小。

• 很多情况下，没有意义去说一个运行$n^2$步的算法比一个运行$2n^2$步的算法要好.
• 在渐近表式方式中我们忽略常数，这样我们将下面式子看成相等的:
  $100n^2$, $1.5n^2$, $n^2+4$, $10n^2-3n+6$.

渐近表达式的核心内容就是忽略常数！

渐近表达式是一个被大家认同的计算机里表示运行时间和空间的方法。

渐近表达式系统产生另一个数学系统，与精确数学、模糊数学、近似数学都不相同。

渐近分析的符号

算法效率的主要指标是基本操作次数的增长次数。

为了对这些增长次数进行比较和归类，计算机科学家们使用了3种符号：

• O（读“O”）：上界
• Ω（读”omega”）：下界
• Θ（读”theta”）：近似

渐近上界符号O（≤）

存在正常数$c$和$n_0$使得对所有$n\ge n_0$有$f(n)\le cg(n)$，记为$f(n)\in O(g(n))$

渐近下界符号Ω（≥）

存在正常数$c$和$n_0$使得对所有$n\ge n_0$有$f(n)\ge cg(n)$，记为$f(n)\in \Omega (g(n))$

渐近近界符号Θ（=）

存在正常数$c_1$,$c_2$和$n_0$使得对所有$n\ge n_0$有：$c_{2}g(n)\le f(n)\le c_{1}g(n)$，记为$f(n)\in \Theta (g(n))$

非紧上界记号o（<）

o(g(n)) = { f(n) | 对于任何正常数c>0，存在正数n₀>0使得对所有n≥n₀有：0 ≤ f(n) < c g(n) }

等价于f(n) / g(n)→0 ，as n→∞。

非紧下界记号ω（>）

ω(g(n)) = { f(n) | 对于任何正常数c>0，存在正数n₀ >0使得对所有n≥n₀有：0 ≤ c g(n) < f(n) }

等价于f(n) / g(n) →∞ ，as n→∞。

渐近分析符号的定理

非紧上界记号 & 非紧下界记号

f(n)∈ω(g(n)) ⇔g(n) ∈o (f(n))

当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定

如果$t_1(n)\in O(g_1(n))$并且$t_2(n)\in O(g_2(n))$，则$ t_1(n)+ t_2(n) ∈O(max{(g_1(n), g_2(n)})$

对于符号Ω和Θ，该定理也成立。

该定理表明：当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。

渐近分析符号的性质

传递性

f(n)= Θ(g(n))， g(n)= Θ(h(n)) ⇒ f(n)= Θ(h(n))
f(n)= O(g(n))， g(n)= O (h(n)) ⇒ f(n)= O (h(n))
f(n)= Ω(g(n))， g(n)= Ω (h(n)) ⇒ f(n)= Ω(h(n))
f(n)= o(g(n))， g(n)= o(h(n)) ⇒ f(n)= o(h(n))
f(n)= ω(g(n))， g(n)= ω (h(n)) ⇒ f(n)= ω(h(n))

反身性

f(n)= Θ(f(n))；
f(n)= O(f(n))；
f(n)= Ω(f(n)).

对称性

f(n)= Θ(g(n)) ⇔ g(n)= Θ (f(n)) .

互对称性

f(n)= O(g(n)) ⇔ g(n)= Ω (f(n)) ；
f(n)= o(g(n)) ⇔ g(n)= ω (f(n)) ；

算术运算

f(n)+g(n)= O(f(n)+g(n)) ；
f(n)*g(n) = O(f(n)*g(n)) ；
cf(n) = O(f(n)) ；
g(n)= O(f(n)) ⇒ f(n)+g(n) = O(f(n)) 。

基本的效率类型

常量(c) < 对数(logn) < log²n < 线性(n) < nlogn < 平方(n²) <立方(n³) < 指数(2ⁿ) < 阶乘(n!)

最常用的关系式

线性时间:O(n)

线性时间.运行时间只是输入大小的一个常数倍数。

O(n log n) 时间

O(n log n) 时间多出现在分而治之算法中。

如排序算法：合并排序和堆排序方法都将产生O(n log n) 时间的算法。

平方时间 O(n²)

平方时间. 列举所有元素对.
比如说求平面上n个点(x1, y1), …, (xn, yn)中最近两个点之间的距离.
对每对点都尝试一下可得出平方时间的算法。

多项式时间O(n^k)

Independent set of size k. Given a graph, are there k nodes such that no two are joined by an edge?
O(n^k) solution. Enumerate all subsets of k nodes.

指数时间

最大独立集问题：给出一个图，求最大的一个点集使得其中任何两个点间都不存在一条边。

穷举搜索产生运行时间O(n² 2ⁿ)的算法.

渐近增长率比较的三种方法

定义法

找到正常数c和n₀使得对所有n≥n₀有f(n) ≤ cg(n)，则 f(n)=O(g(n))

极限法

比较两个函数f(n)和g(n)的渐近增长率时，可以对两个函数相除，然后令变量n趋向于无穷，看这个极限值是无穷大还是一个大于零的常数还是趋向于0.

取对数法

对于比较难的比较的两个函数，我们可以对它们同时取对数后再进行比较。

注意：取对数后不能忽略低阶项和常数

例如下面的反例：