算法时间复杂性之渐近法分析基础

在我的评论栏中有人说："你是程序员?"，我可以确定、一定以及肯定地告诉他/她：'我就是一个程序员，如假包换'。也许是最近技术类的blog写得少了，其他类的多写了些，让人家误会了，这也无可厚非。不过我倒是想到这样一个问题：程序员一定要满篇地谈技术么，程序员也有自己丰富多彩的生活呀。好了，切入正题。今天我们谈谈算法时间复杂性的分析。我没系统学过，都是在书上看到的以及MIT算法导论课上听到的。这里仅从我的理解的角度写一些罢了，不是很严谨哟。^_^

啥也别说，先看一段算法程序吧。这段代码以前在blog中出现过(摘自MIT Press算法导论2nd)，不过那时它是用来阐述'Pseudocode Conventions'的。
Insertion-Sort(A) △ A[1..n]
    for j <- 2 to length[A]
        do key <- A[j]
            △ Insert A[j] into the sorted sequence A[1..j-1].
            i <- j-1
            while i > 0 and A[i] > key
                do A[i+1] <- A[i]
                    i <- i-1
            A[i+1] <- key
假设我们目前没有学过什么算法复杂性分析之类的知识，如果让你去计算这个算法的运行时间的话，你会怎么做呢？最简单、最直观的方法就是把每条语句的执行时间累加在一起。对于上面这个简单的算法，我们'掰手指头'还是可以计算的。不过我们必须在计算前有个约定，什么约定呢，就是事先约定好一些'basic operation'的执行时间。我们定义一个'单位时间(UC, Unit Cost)'的概念，所有的语句的执行时间均为该'单位时间'的整数倍。那么这样我们可以约定并得出：
1、赋值操作、比较操作、算术运算、逻辑运算、访问(读写)单个常量或单个变量(包括一个数组的单个分量或一个记录的单个域)的时间为1 UC；
2、对于条件语句(if condition then …)和'switch condition case 1…n'语句来说，它们的执行时间为'计算condition值的时间' + '最耗时分支语句的执行时间'，即T(condition) + max(Tcase1, Tcase2, … Tcasen)；
3、对于for…loop语句，其执行时间显而易见为：'执行循环体的时间 x 循环次数'，一般来说这个循环次数都是显式可知的；
4、对于do … while之类的循环语句，其执行时间类似于for … loop，为：'执行循环体的时间 x 循环次数'，但其循环次数是处于隐含状态的；
5、对于goto语句，如果结构合理，无滥用goto的情况(如将控制权转移到goto前面的语句)，其运行时间忽略不计；
6、对于函数或者是过程调用，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(6)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。

OK，知道了'时间约定'，我们就来算算这个算法程序需要花费我们多长时间呢。
for j >> (n – 2 + 1) x 1 = n – 1；
key >> (n – 2 + 1) x 1 = n – 1；
i >> (n – 2 + 1) x 1 = n – 1；
while i > 0 and A[i] > key —>>> 由于while循环的'隐式执行次数'，这里我们设该语句执行了Tj次，那么该条语句需要 (1 + 1 + 1) x Tj = 3 x Tj；
do A[i+1] >> (Tj – 1) x 1 = Tj – 1；
i >> (Tj – 1) x 1 = Tj – 1；
A[i+1] >> (n – 2 + 1) x 1 = n – 1；
我们来作和: Total_Running_Time = 4 x (n – 1) + Sum(3 x Tj) + 2 x Sum(Tj -1) = 4 x n – 4 + 3 x Sum(Tj) + 2 x Sum(Tj – 1); j belongs to [2,n]。这里唯一的未知量就是Tj，如何确定Tj呢？考虑两种极端的情况：
1、输入数字串是已经排好序的(already sorted) — Best Case
这里while i > 0 and A[i] > key语句只需执行一次，Tj = 1，这样我们可以得出：Total_Running_Time = 7 x (n – 1)，即n的线性函数；

2、输入数字串是逆序的(reverse sorted) — Worst Case
此时A[i]要与A[1..j-1]的每一个元素比较，所以Tj = j – 1，这样我们可以得出：Total_Running_Time = 5/2 x (n^2 – n)；

奇怪我们算出了两种不同的结果，到底采用那个呢？相信从直觉出发，大家也都会选择'Worst Case'，'Worst Case'给了我们一种保证(guarantee)：针对某种规模的输入n，该算法能保证其时间复杂性不超过某个上界限(upper bound)。而'Best Case'大多是个'Cheating'，毫无意义的(meaningless)。在大多数算法领域我们使用的也是'Worst Case'分析，还有一种分析方式叫'Average Case'分析，就拿上面的'INSERTION-SORT'而言，如何计算其'Average Case'的时间复杂性呢？'Average Case'一般依赖一个前提假设，而这个假设都符合一定的'Probability distribution'，这里我们可以假定Tj = j/2，也就是说已经sorted的数字串中一半的值 > key，另一半 < key；这样计算出来的Total_Running_Time也是n^2一级的。

Ok，那么是不是针对每个算法都需要精确计算出其时间复杂性结果呢？我想不必要，在我们平时的工作中，多数时间是在选择算法，当然从事算法设计的专业人员除外，而选择算法的时候，我们大致只需要知道这个算法的一个时间上限即可，再根据特定的问题模型选择适当的算法。如何找到一个算法的时间复杂性上界是我们面临的问题。像INSERTINO-SORT这样的简单算法我们还可以处理，但随着问题规模的扩大，结构越来越复杂，算法分析的工作量之大、步骤之繁将令人难以承受，人们遂引入了'渐近性分析'方法，其主旨就是简化算法分析的工作量。看上面我们得到的INSERTION-SORT的'Worst Case'的结果：5/2 x (n^2 – n)，这个结果中既包含n^2又包含n^1，对于这个简单的公式我们还是可以分析的，但是对于复杂的算法，可能存在这样的计算结果：n的诸多高次幂多项式，这样的多项式分析起来较为复杂，而渐近性恰是简化这样问题的好方法。

什么是渐近性？用数学语言表述就是：对于f(n)，如果存在g(n)，使得当n > 0, n -> ∞时有：(f(n) – g(n)) / f(n) -> 0，则g(n) 称为 f(n)的渐近表达式。用工程上的方法表述就是：g(n)是f(n)中略去低阶项(包括常数项)所留下的最高阶项，所以它无疑比f(n)来得简单。有了渐近表达式，寻找算法时间复杂性的界限就相对容易了。以后比较两个算法，就只需要比较两个算法的渐近表达式了，这样极大的简化了工作量。

我们定义了几种常用的渐近性符号用来对算法进行渐近性分析：
1、O符号
常用来分析算法复杂性上限(upper bound)，其定义为：O(g(n)) = {对f(n)，n为正整数，存在正整数常量C和N，使得0 <= f(n) = N}，可以看出O(g(n))是一个集合，为了表示T(n)是该集合内的一个成员，我们将之表示为：T(n) = O(g(n))。

2、θ符号
常用来给出算法复杂性的上下限(lower bound and upper bound)，其定义为：θ(g(n)) = {对f(n)，n为正整数，存在正整数常量C1、C2和N，使得0 <= C1g(n) <= f(n) = N}，可以看出O(g(n))也是一个集合，为了表示T(n)是该集合内的一个成员，我们将之表示为：T(n) = θ(g(n))。由于给出了上下限，所以θ符号集合为O符号集合的子集。

3、Ω符号
常用来分析算法复杂性的下限(lower bound)，不常用。其定义为：Ω(g(n)) = {对f(n)，n为正整数，存在正整数常量C和N，使得0 <= Cg(n) = N}，可以看出O(g(n))是一个集合，为了表示T(n)是该集合内的一个成员，我们将之表示为：T(n) = Ω(g(n))。

有了这些符号我们再来看看如何理解带有渐近性符号的一些等式:
[例1] 渐近性符号仅仅用在等式右边
如：2n^2 + 6n + 1 = 2n^2 + θ(n)，这里我们可以将该等式看成2n^2 + 6n + 1 = 2n^2 + a(n)，这里a(n)是一个匿名函数，并且a(n)是θ(n)集合中的一个函数。

[例2] 渐近性符号出现在等式两边
如：2n^2 + θ(n) = θ(n^2)，按照[例1]中匿名函数的方法，我们可以得到: 2n^2 + a1(n) = a2(n)，其中a1(n)属于θ(n)集合，a2(n)属于θ(n^2)集合。这个等式需要这样理解"无论等式左边的匿名函数a1(n)取任何函数，等式右边的总存在一个匿名函数a2(n)使等式相等"。

以上是渐近性分析的一些基本知识，但是在实践中还是需要技巧的，实践证明在渐近性分析存在大量的递归函数，要想真正掌握复杂算法的渐近性分析，解决递归问题必不可少，不过这是以后的内容了。