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

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

又是老生常谈-'单元测试'，说实话自己在单元测试上是'语言上的巨人，行动上的矮子'，属于那种说的比做的多的人^_^。不过也不能说什么也没做。记得去年年末的时候自己还设计并实现过一个简单的'C语言单元测试包'呢^_^，至今这个包仍然还在使用呢。不过大多数的单元测试都不像想象中那样简单，我们在介绍单元测试的时候，大多拿Add、Sub等作例子，这样当然有好处，简单易懂。其实学习单元测试初期关键是学习单元测试的思想，所以这些Add、Sub也能满足需求。不过在真正的项目中，单元测试大多做起来较为困难，我是在Unix上做C开发的，Java的咱暂先不提，也没什么资格提，虽然曾经花过一段时间专心研究过，还写过些Java学习心得，但是毕竟没做过实际的项目，说起来心里也发虚。

曾经很长一段时间，自己在编码阶段基本上都是缺少单元测试的，一是项目中Legacy代码较多，耦合太紧，想把那部分代码拿出来比'登天还难'(有点夸张)，反正基本上是'一扯一大帮'，俗称'一个都不能少'；而是部门在这方面积淀较少，在计划的时候对这方面考虑不够，时间上也不充裕，经常是在集成测试或者系统测试的时候顺便带上单元测试了，这样的后果就是'浪费'。本来在单元测试阶段发现一个Bug需要10 minutes，拖到集成测试或者系统测试后，这个时间就可能是1 hour或者 1 day 或者更多时间，这里可不是'耸人听闻'，的确有真实的事例，有过这样的经历的人都体会到其中的痛苦。

痛定思痛，自己终于觉醒了。恰好，一个新的短期项目刚刚处于开发阶段，正好是发挥单元测试的大好时机。杀开一条血路，做就是了。但是不能盲目去做。单元测试是需要设计的，而且感觉单元测试设计因系统架构模式而异，有难有易；而且单元测试设计时需要考虑项目进度、测粒度和测试密度。测试粒度，也就是说你选择多大的功能单元来作为单元测试的基本单元，是函数一级的还是模块一级的；测试密度，则是你的单元测试用例的语句覆盖度有多少了。完美的单元测试是应该覆盖程序运行的每条分支的，但是要编写出这么多的单元测试用例，其工作量我想比开发这个系统的工作量只多不少，这样一来即使你能编写出这么多用例的代码，你的Leader也会对你吼的。选择关键路径覆盖是我的选择测试密度的'标准'。我们的系统的架构是基于'队列/管道架构模式'的，这也决定了我们的单元测试较容易，根据这个特点我选择我的单元测试的力度是模块一级的。基本策略就是根据模块内的关键路径设计模块级别的单元测试用例–对我们这个系统来说具体就是造各种各样的消息，放到输入队列中即可。

我的单元测试已经进行了两天多了，效果很是明显，有些bug的发现都出乎我的意料。每当测试完一个功能模块，我会感觉对这个模块更有信心了，还有一种莫名的成就感^_^。

好的单元测试最好是能自动化，这样一旦修改了代码，可以对以前测试过的代码进行回归单元测试，保证此次修改不影响到以前已经测试过的代码的正确性。不过自动化又谈何容易？Java有很好的工具支持，可谓众星捧月；C则是孤家寡人，少有有利的工具支持。这样的话，我们就需要自己写自动化的逻辑，当然这些逻辑因系统而异，至今我也很难想出好的通用的办法，比如像Mock Test这样的测试，在C中就很难实现，我们常常以真实的情景代之，而不是使用Mock，这样就可能让不同的用例对执行顺序有一个依赖，执行顺序不一致，测试的结果可能不相同。

以上的一些经验都有一定的语言局限性，对于使用C开发的系统可能有些借鉴的意义，但是对于Java开发的系统上面的很多说法也许还是误导的，大家一定要'睁大眼睛'，看清楚了^_^。单元测试仍在进行中…^_^