不知不觉间已经快大学毕业两年了，最近热度很高的世界杯让我想起了2002年韩日世界杯期间和寝室哥们儿们一起为中国队加油、一起为阿根廷落魄而伤感的日子了，只因兄弟们都已经各奔东西、不在身边，想起这些未免有些感伤。恰巧，Google Earth最近更新了其中国区的卫星照片，使我有机会到我们学校的'上空'俯瞰我生活学习了4年的令人难忘的大学。

Google Earth真是个耗资源的软件，我的本本勉勉强强能运行之，察看一下内存，哇噻，GE居然占了105M内存，我的本本的物理内存才256，虽然有虚拟内存，但是总是换入换出，我的硬盘就开始哇哇叫了^_^。

下面是我大学校园的一些图片以及我点点滴滴的记忆^_^。

我所在的大学是位于中国北方哈尔滨的一座学校，人们俗称之'哈工大'，有人说它是'工程师的摇篮'，呵呵，在我身上这点体现的还真准确。学校其实并不大，甚至显得有些拥挤，由于处于市中心地段，再加上规划的并不合理，导致建筑物林立，剩余的自由空间倒是显得少得可怜。更奇怪的是整个校园被一条宽阔的马路一分为二。学校中的路并不平坦，高低起伏，就好像整座学校建在一座丘陵上似的。学校有两个校区，我生活在主校区，也就是本埠，二校区听说很大，规划也很好，不过我从未去多，多少有些遗憾。好了，下面看图说话吧。

全景图

从上图中可以清晰的看到整个校园中间有一条大马路从学校正门而入，沿东南方向延伸到学校的另一端。图上方主要分布着主教学楼、电机楼、机械楼、逸夫馆和实习工厂。图下方则是图书馆、食堂、A楼、D楼、学生公寓、篮球场，最下方其实还有个新体育场，不过图中放不下了。

主教学楼

不得不承认，主教学楼的确是整个校园最最壮观的建筑物，其实很多到哈尔滨旅游的人也都主动要到我们校园这参观参观主楼，当年到学校报到时第一眼就看到了这个宏伟的楼宇，这座楼宇也有很长时间的历史了，具体多少年我也记不清了，起码60多年了，在校园里还有更老的建筑，听说有些建筑是1920年的作品，真是老古董了。主楼、电机楼和机械楼构成了一个'凹'型，在它们后面是个小花园，那可是每天晚上一对对情侣最喜欢去的地方。也许很多人会看到这三栋楼的楼顶是亮亮的，你看的没错，我来告诉你那是什么，当然我也是在校园里看，不没有近距离看，我看到的是一块块的白色钢板铺满了这三座楼的楼顶，至于为什么做我也不清楚，很有意思吧。

图书馆

学校的图书馆的建筑风格很有特色，采用的是柱结构支撑，透明顶棚，中央区采光完全靠太阳光，当然阴天和夜晚有照明，这个图书馆项目可是当年的鲁班奖得主呀，不过在我离开校园的时候，图书馆正门的大柱子外皮有很多地方都脱落了，图书馆也该修修了。回想一下，那里留下了我很多的足迹。

三公寓

哈工大的学生都知道，三公寓是工大最神秘的角落，因为那是我们学校女生最集中的地方了–女生公寓。每天早上或者晚上你都能看到其门前总有不在少数的男同胞们在等他们的'梦中情人'，这绝对是一道特殊的风景。我曾经去过一次那里，那还是帮助我班女生换寝室时才有机会的。不过这个公寓也已经很陈旧了，也该修修了。

篮球、网球场

我是不太喜欢打篮球的，记得只是在毕业的最后那段时间和同学们一起在那'现眼'了一把，网球倒是我很喜欢的运动。学校的网球场设施还是很好的，而且是免费的，每天早晨都有很多人占场打球，我比较懒，从来不能早起，只能等到下午1、2点钟太阳最毒辣的时候去打球，而且还得死拉硬拽，才能叫到几个哥们儿一起，这里'岁岁年年'就是曾经的受害者。

体育场和一公寓

上图中我们的体育场一目了然，很容易识别，那里是我们上体育课、开运动会的地方，同时也有很多集体活动，比如什么明星演唱会、足协杯比赛了，我们学生都是'穷孩子'，没有钱入场，就趁机混入场内；如果实在混不进去，我们还有最后一招，也是大多数人使用的招数，看到这个体育场西北方向的那个建筑物了么，那就是我们的一公寓，号称亚洲最大的学生公寓，至于其中住了多少人，不得而知。我们最后的招数就是打开窗户，坐在一公寓的窗子上拿着望远镜看体育场内的节目，还别说，一目了然，很是清晰。当然你必须住在五楼以上才可以(公寓一共6层，还好我住在530^_^)。体育场东北方向有个'土场'，那是一块真正利用率很高的足球场地，体育场内的草坪是不允许我们踢球的，我们只能在土场里踢。还记得在我们的军训也在这块土场上，那时候可真惨，大热天，穿着厚厚的军服，在这块土场上拴趴滚打，弄得全身没一块好地方。

当一个算法(如二分查找)中包含对自己的递归调用时，关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题，而这样的算法不在少数。实际上这是数学领域的问题，但是计算机科学又怎么能脱离数学而存在呢？^_^ 数学是好东西呀，可惜自己在这方面造诣颇浅，今生之遗憾亚。^_^

还好，解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法，我们这里就说说这三种方法！这些是基础，如果以后要深入研究算法的话，这些知识是必须要精通的；如果并不想在算法方面有所深入的话，多学些知识也没错。我本身也是在学习，像这类的知识一般都比较死性，有些记住了，就可以掌握了。

1、Substitution Method
这是一种使用数学归纳法推导证明的方法，其步骤为先假设一个解，然后带入到递归方程中，利用数学归纳法推导，以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧，比较保险^_^。
[Ex1.]
T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。

解：(这里我们只来找上界)
我们假设T(1) = θ(1)，猜测一个解T(n) = O(n^3)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^3，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出：
T(n) = 4T(n/2) + n
     <= 4c((n/2)^3) + n
     = (c/2)n^3 + n
     = cn^3 – ((c/2)n^3 – n)
当c >= 2, n >= 1时，((c/2)n^3 – n) >= 0，这时T(n) <= cn^3，即T(n) = O(n^3)；

我们再回过头来看看当n = 1时这个解是否成立，即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大)，即该推导出的解也满足初始条件，所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢，我们不妨缩小上界范围再推导一次，这次我们猜测解为T(n) = O(n^2)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^2，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出：
T(n) = 4T(n/2) + n
     <= 4c((n/2)^2) + n
     = cn^2 + n
     = cn^2 – (-n)
不能严格符合T(n) <= cn^2的定义，所以推导失败。但是失败是不是说明，T(n) = O(n^2)一定不成立呢？我们再做一次最后的努力，当出现上面的这种情况时，我们假设解仍为：T(n) = O(n^2)，只是我们选择对k < n, 有T(k) <= ak^2 – bk，我们选择减去一个低阶的项，这不会影响到n足够大时的渐进性的，这里是一个常用的技巧。
T(n) = 4T(n/2) + n
     <= 4(a(n/2)^2 – b(n/2)) + n
     = an^2 – bn – (bn – n)
     <= an^2 – bn (当b >= 1时)

这样我们找到了严紧解T(n) = O(n^2)。

2、Iteration method(Recursion-tree method)
这个方法的思想是："迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计"。而我们可以借助’树’的形式来帮助迭代展开的过程。

[Ex2.]
T(n) = T(n/4) + T(n/2)+ n^2；解这个递归等式，分析T(n)的渐近性。

解：
T(n) = n^2 + T(n/4) + T(n/2)
     = n^2 + {(n/4)^2 + T(n/16) + T(n/8)} + {(n/2)^2 + T(n/8) + T(n/4)}
     = …
     = n^2 {1 + 5/16 + (5/16)^2 + (5/16)^3 + … }
     = θ(n^2)

3、Master Method
这是一种典型的套用公式的方法，解决形如’T(n) = aT(n/b) + f(n)’递归方程形的解的方法。这种递归方程是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程’T(n) = aT(n/b) + f(n)’。

在f(n)的三类情况下，我们有T(n)的渐近估计式有三类情况：(log(b, a)表示以b为底的对数)
(1) 若对于某常数ε>0，有f(n) = O(n^log(b, a-ε))，即f(n)以慢于n^(log(b, a))的速率渐进增长，则T(n) = θ(n^(log(b, a))；

(2) 若有f(n) = θ(n^log(b, a) * (lgn)^k)，即f(n)以相似于n^(log(b, a))增长的速率渐进增长，则T(n) = θ(n^(log(b, a) * (lgn)^(k+1))，k为一常数，k >= 0；

(3) 若对于某常数ε>0，有f(n) = Ω(n^log(b, a+ε))，即f(n)以快于n^(log(b, a))的速率渐进增长，且对于某常数c > 1和所有充分大的正整数n有af(n/b) <= cf(n)，则T(n) = θ(f(n))。

举例来说吧：

[Ex3.]
T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n我们得到a = 4, b = 2, f(n) = n, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2，而f(n) = n = O(n^(2-ε))，此时ε= 1，根据Case (1)，我们得到T(n) = θ(n^2)。

[Ex4.]
T(n) = 4T(n/2) + n^2，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n^2，我们得到a = 4, b = 2, f(n) = n^2, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^2 = θ(n^2 * (lgn)^0)，即k = 0，这样按照Case (2)，我们得到T(n) = θ(n^2 * (lgn)^(k+1)) = θ(n^2 * (lgn))。

[Ex5.]
T(n) = 4T(n/2) + n^3，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n^3，我们得到a = 4, b = 2, f(n) = n^3, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^3 = Ω(n^(2+ε)，此时ε= 1，且4f(n/2) = (n^3)/2 <= cn^3(c >= 1/2)，所以得到T(n) = θ(n^3)。

对于大部分人来说’Master Method’应该是最常用的，这几个Case可要牢牢记在心上才行哟。