好多天没有更新blog了。其实人的大脑就好比一台复杂的机器，每天24小时不停的工作着，某一局部负责对应的工作，如果大脑的一直将压力都压在这个部分上，那么这个部分就会’过载’、’发热’，导致今后几天工作效率下降。拿我们程序员来说，如果不能适当的调节一下自己大脑的工作部位，一段时间后就会思维枯竭而且感到很是疲劳，这几天我就处于这样的状态，其实有很多工作需要去做、很多技术书籍等待我去读，可是我的大脑告诉我，该歇歇了。的确，这种感觉让自己无心无力去继续做了，那就换种生活–’娱乐’，具体点看电影，让大脑切换到’形象思维’当中去。

大脑需要适当切换休息，我们赖以生存的家园-地球又何尝不是呢。’核震过后’这部灾难片给我们讲述的或者说告诫人类的就是这个道理。在这之前，我从未听说过’核震过后’这部片子，记得最近看的一部灾难片叫’The Day After Tomorrow’，挺壮观和震撼的。而’核震过后’给人们带来的思考我想不亚于’后天’。这是一部关于’北美洲大陆板块’剧烈变动引发连锁超级大地震的故事，当然之所以这块板块发生动荡，也是人类过渡破坏环境所致，过度开采地下水、采煤、采油，建造摩天大楼，挖掘隧道，炸山取石等等。该片代表性人物较多，导演意图通过对不同阶层人们在灭顶之灾面前所表现出来的行为的描述来展开该片，上至总统、州长、科学家下至普通医生的一家人，既展现了这些人作为普通人的恐惧，又展现了这些人在各自的岗位上团结一心、各负其责的精神，同时也告诫人们在大自然无穷力量面前，人类是那么的无助。

影片在场面制作拍摄上也称得上’波澜壮阔’了，由于该片早’后天’几年，所以一些技术手段可能还不如’后天’，不过其制作的真实还原的程度还是蛮高的，让人看到高潮的时候有一种’身临其境’的感觉。影片在背景音乐上也是下足了功夫，特别是在’最后一次改变南加州地貌的10.8级的大地震发生时，人们奔走逃离时的那个音乐，强烈的表现了’人类在大自然面前的渺小与无力’，黑白镜头和彩色镜头的交替，让人们的心灵震撼随着色彩的变化而变化，直至高峰。

当南加州陷入一片汪洋中的时候，当大地震消逝的时候，幸存的人们都驻足观望，相信此时此刻坐在电影前的观众的心灵也在’驻足’，反思着过去的一切一切，思考着’为什么’。我想这恰恰是导演所要达到的效果。建议有机会看看这部电影，片子较长，看得过瘾！^_^

在我的评论栏中有人说："你是程序员?"，我可以确定、一定以及肯定地告诉他/她：'我就是一个程序员，如假包换'。也许是最近技术类的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)使等式相等"。

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