算法分析技术

1. 算法

算法严格的定义需要使用图灵机的概念，即一种简化了的冯诺依曼式计算机架构，但只有在考虑可计算性时才有引入图灵机的必要，在大多数情境下理解算法可以简单认为其是一段良定义的程序段，即若干描述清晰、无歧义的步骤序列，对于给定输入能够给出相应输出。合法的数据对象集记为 F F F。

尽管各种算法中的步骤不同，但基本的运算操作几乎是相同的。因而定义每进行一次下列的一种操作就记为进行了一次运算：

对于给定的 a a a和 b b b， a , b ∈ F a,b\in F a,b∈F，求

（1）加法： a + b a+b a+b；
（2）减法： a − b a-b a−b；
（3）乘法： a × b a×b a×b；
（4）除法： a   /   b a~/~b a / b；
（5）赋值： a ← b a\gets b a←b；

上述符号中" / / /“表示带余除法或者算术除法，” ← \gets ←"表示用右侧的值来替换左侧符号所代表的值。

一般来说称一个算法对于一类问题是有效的，是指算法至少要满足以下的三个条件：

① 算法的时间复杂度可以接受；
② 算法给出的输出恰是原问题的答案；
③ 算法能够解决问题的每一个合法的输入数据序列（称为实例）。

2.算法的时间复杂度

我们关心算法的时间效率。对于给定正整数 n n n，算法对于每个合法输入数据序列 a 1 , . . . , a n , ( ( a 1 , . . . , a n ) ∈ F ) a_1,...,a_n,((a_1,...,a_n)\in F) a1​,...,an​,((a1​,...,an​)∈F)都在经历有限个步骤后给出某个输出，则称算法是有效的。如果一个算法不是有效的，我们总可以缩小合法数据集到其某个子集使得算法成为有效的。我们只讨论有效算法的时间复杂度

（1）时间函数

一个算法的时间函数 T : Z + → Z + T:\Z_+\rightarrow \Z_+ T:Z+​→Z+​在 n n n处的值为算法在所有合法输入数据序列下执行运算的最多次数，即：
T ( n ) = m a x ( a 1 , . . . , a n ) ∈ F { S t e p s ( a 1 , . . . , a n ) } T(n)=max_{(a_1,...,a_n)\in F}\{Steps(a_1,...,a_n)\} T(n)=max(a1​,...,an​)∈F​{Steps(a1​,...,an​)}

这里的时间函数与计算的是最坏情况下算法执行的基本运算次数，这是因为在输入规模相同时输入数据序列的不同特性会影响算法的运行效率，而这种影响一般很难分析；而另一方面，算法的最坏运算次数也基本上符合算法在实际效果上的表现。虽然上文中六种基本运算的次数并不完全相同，甚至例如加法、乘法、除法之间有较大差别，但相比起输入规模的增长带来的算法执行时间的增大，这一差别可以忽略。当然，在更对算法效率要求更高的领域中，需要考虑基本运算的效率优化。

计算时间函数只需要已知算法在某种合适语言下的代码，通过对流程的分析就可以计算出时间函数，但也有一些情况下计算具体的时间函数较为困难。事实上，我们并不需要了解具体的时间函数，只需要大致了解算法用时随输入规模增大的增长趋势即可，因而我们引入渐进复杂度的概念。

（2）渐进复杂度

以下用 T T T记算法的时间函数， f : Z + → R + f:\Z_+\rightarrow \R_+ f:Z+​→R+​。那么有：

① 称 T T T是 O ( f ) O(f) O(f)的当且仅当存在正整数 n 0 n_0 n0​和正数 c c c，使得 T ( n ) < c f ( n ) T(n)<cf(n) T(n)<cf(n)成立于所有的 n > n 0 n>n_0 n>n0​，记作 T = O ( f ) T=O(f) T=O(f)，称 f f f是 T T T的一个渐进上界；

② 称 T T T是 Ω ( f ) \Omega(f) Ω(f)的当且仅当存在正整数 n 0 n_0 n0​和正数 c c c，使得 T ( n ) > c f ( n ) T(n)>cf(n) T(n)>cf(n)成立于所有的 n > n 0 n>n_0 n>n0​，记作 T = Ω ( f ) T=\Omega(f) T=Ω(f)，称 f f f是 T T T的一个渐进下界；

③ 称 T T T是 Θ ( f ) \Theta(f) Θ(f)的当且仅当 T = O ( f ) T=O(f) T=O(f)且 T = Ω ( f ) T=\Omega(f) T=Ω(f)，记作 T = Θ ( f ) T=\Theta(f) T=Θ(f)，称 f f f是 T T T的一个紧界。

以下的讨论中， S ∈ { O , Ω , Θ } S\in\{O,\Omega,\Theta\} S∈{O,Ω,Θ}， O , Ω , Θ O,\Omega,\Theta O,Ω,Θ统称渐进记号。渐进的意思是只考虑时间函数的大致增长趋势。大多数情况下时间复杂度都是指某个算法时间函数的一个渐进上界，尽管一个函数有无穷多个渐进上界，为了能更够好地刻画这个函数的效率特性我们要求这个上界尽可能地小；然而，如果一个渐进上界恰好是其紧界，我们将采用紧界的记号记它的时间复杂度，因为紧界的记号包含更多的信息。（遗憾的是，在一般情况下，我们只能或者更容易证明算法的渐进上界。）

事实上， S ( f ) S(f) S(f)是一个集合，即那些以 f f f作为一个渐进上界的函数的集合，但是一般情况下我们用 S ( f ) S(f) S(f)表示这个集合中某个不特定的元素，因此我们使用记号" = = =" 而不是" ∈ \in ∈"。

以下 f , g , h , l f,g,h,l f,g,h,l都是 Z + \Z_+ Z+​到 R + \R_+ R+​的函数。根据定义显然有 S S S的部分性质如下：

① 自反性： f = S ( f ) f=S(f) f=S(f)
② 传递性： f = S ( g ) ∧ g = S ( h ) → f = S ( h ) f=S(g)\wedge g=S(h)\rightarrow f=S(h) f=S(g)∧g=S(h)→f=S(h)
③ 可加性： f = S ( h ) ∧ g = S ( h ) → f + g = S ( h ) f=S(h)\wedge g=S(h)\rightarrow f+g=S(h) f=S(h)∧g=S(h)→f+g=S(h)

由可加性可以得到推论，当算法中相继执行时间函数分别为 T T T和 T ′ T' T′的两组步骤时，如果有 T ′ = O ( T ) T'=O(T) T′=O(T)那么 T + T ′ = O ( T ) T+T'=O(T) T+T′=O(T)，即只需要考虑时间复杂度更大的那组步骤就可以获知全部步骤的总时间复杂度，这也体现了渐进式见复杂度忽略一个函数中增长较慢的那部分的特性。

（3）复杂度评价

算法的时间复杂度有高有低，当时间复杂度过高的时候即使利用效率极高的超级计算机进行计算对于较大的输入规模也许也需要耗费超乎想象的较长用时，只有时间复杂度在不过高时一个算法才能称为有效的。一般地，我们希望当输入规模加倍时，算法的运行时间至多增大常数倍。多项式时间复杂度就是满足这一性质的一个典例，因为假设 T ( n ) = A n α T(n)=An^\alpha T(n)=Anα，有 T ( 2 n ) = A ( 2 n ) α = 2 α A n α T(2n)=A(2n)^\alpha=2^\alpha An^\alpha T(2n)=A(2n)α=2αAnα，因而每当输入规模加倍，时间函数增加 2 α 2^\alpha 2α倍，这是一个常数。

定义一个时间函数为 T T T的算法是多项式时间复杂度的当且仅当 T = O ( p ) T=O(p) T=O(p)，其中 p ∈ P ( R ) = { f : Z + → R +   ∣   f ( n ) = c 0 + . . . + c m n m , c 0 , . . . , c m ∈ R } p\in\mathcal{P}(\R)=\{f:\Z_+\rightarrow\R_+~|~f(n)=c_0+...+c_mn^m,c_0,...,c_m\in\R\} p∈P(R)={f:Z+​→R+​ ∣ f(n)=c0​+...+cm​nm,c0​,...,cm​∈R}即 p p p是个多项式。容易证明 p = Θ ( n d e g   p ) p=\Theta(n^{deg~p}) p=Θ(ndeg p)，其中 d e g   p deg~p deg p是 p p p的度数（即次数最高的非零项次数），所以一般记作 T ( n ) = O ( n d e g   p ) T(n)=O(n^{deg~p}) T(n)=O(ndeg p)。那么我们将上文中提到的关于算法有效的三个条件中的第一条：

算法的时间复杂度可以接受；

修改为：算法为多项式时间复杂度的。

此外考虑几种常见的复杂度形式。定义一个时间函数为 T T T的算法是对数时间复杂度的当且仅当 T = O ( f ) T=O(f) T=O(f)，其中 f ( x ) = l o g 2 x f(x)=log_2x f(x)=log2​x。由对数的换底公式可知这里可以将底数 2 2 2替换为任意大于 1 1 1的正数，所以一般记作 T ( n ) = O ( l o g n ) T(n)=O(logn) T(n)=O(logn)。对数时间复杂度往往优于多项式时间复杂度，这是因为 l o g n = O ( n α ) logn=O(n^\alpha) logn=O(nα)对于所有的正数 α \alpha α都成立。

定义一个时间函数为 T T T的算法是指数时间复杂度的当且仅当 T = O ( f ) T=O(f) T=O(f)，其中 f ( x ) = a x f(x)=a^x f(x)=ax，其中 a > 1 a>1 a>1，记作 T ( n ) = O ( a n ) T(n)=O(a^n) T(n)=O(an)。多项式时间复杂度往往优于指数时间复杂度，这是因为 n α = O ( a n ) n^\alpha=O(a^n) nα=O(an)对于任意的正数 α \alpha α都成立。

凡事总有例外，有的算法虽然没有达到多项式时间算法，但是却因为最坏情况很少出现得以广泛应用；而有的算法虽然能够达到多项式时间复杂度，但是却由于其高幂次和大常数的特点导致实践效果很差。

3. 算法的复杂度分析

分析一个算法的时间复杂度对于较简单的情形往往只需关注其循环迭代的次数，但对于涉及递归、回溯的复杂情形分析复杂度需要深刻地分析并利用一些技巧。对于具体的复杂度分析技巧将在具体的算法分析时提及。