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

还好，解决递归方程涉及的数学知识我还是能应付的了的^_^。在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可要牢牢记在心上才行哟。

这也是在ChinaUnix上看了几篇关于C语言'位域(Bit Fields)'的帖子之后，才想写下这篇文章的。其实在平时的工作中很少使用到'位域'，我是搞服务器端程序设计的，大容量的内存可以让我毫不犹豫的任意'挥霍'^_^。想必搞嵌入式编程的朋友们对位域的使用应该不陌生吧。这里我也仅仅是凭着对C语言钻研的兴趣来学习一下'位域'的相关知识的，可能有些说法没有实践，缺乏说服力。

具体也不是很清楚当年C语言的创造者为什么要加入位域这一语法支持，那是太遥远的事情了，我们不需要再回顾了，既然大师们为我们创造了它，我们使用便是了。

毋庸置疑，位域的引入给用户的最大的好处莫过于可以有效的利用'昂贵'的内存和操作bit的能力了。而且这种操作bit位的能力很是方便，利用结构体域名即可对这些bit进行操作。例如：

struct foo {
 int a : 1;
 int b : 2;
 short c : 1;
};

struct foo aFoo;
aFoo.a = 1;
aFoo.b = 3;
aFoo.c = 0;

通过结构体实例.域名即可修改某些bit得值，这些都是编译器的'甜头'。当然我们也可以自己通过一些'掩码'和移位操作来修改这些bit，当然如果不是十分需要，我们是不需要这么做的。

位域还提供一种叫'匿名'位域的语法，它常用来'填缺补漏'，由于是'匿名'，所以你不能像上面那样去访问它。如：
struct foo1 {
 int a : 1;
 int   : 2;
 short c : 1;
};
在foo1的成员a和c之间有一个2 bits的匿名位域。

在foo结构体的定义中，成员a虽然类型为int，但是它仅仅占据着4个字节中的一个bit的空间；类似b占据2个bit空间，但是b到底是占据第一个int的2个bit空间呢还是第二个int的2个bit空间呢？这里实际上也涉及到如何对齐带有'位域'的结构体这样一个问题。我们来分析一下。

我们再来看看下面两个结构体定义：
struct foo2 {
        char    a : 2;
        char    b : 3;
        char    c : 1;
};

struct foo3 {
        char    a : 2;
        char    b : 3;
        char    c : 7;
};
我们来打印一下这两个结构体的大小，我们得到的结果是：
sizeof(struct foo2) = 1
sizeof(struct foo3) = 2
显然都不是我们期望的，如果按照正常的内存对齐规则，这两个结构体大小均应该为3才对，那么问题出在哪了呢？首先通过这种现象我们可以肯定的是：带有'位域'的结构体并不是按照每个域对齐的，而是将一些位域成员'捆绑'在一起做对齐的。以foo2为例，这个结构体中所有的成员都是char型的，而且三个位域占用的总空间为6 bit 8 bit(1 byte)，这里位域是不能跨越两个成员基本类型空间的，这时编译器将a和b两个成员'捆绑'按照char做对齐，而c单独拿出来以char类型做对齐，这样实际上在b和c之间出现了空隙，但这也是最节省空间的方法了。我们再看一种结构体定义：

struct foo4 {
        char    a : 2;
        char    b : 3;
        int c : 1;
};

在foo4中虽然三个位域所占用空间之和为6 bit < 8 bit(1 byte)，但是由于char和int的对齐系数是不同的，是不能捆绑在一起，那是不是a、b捆绑在一起按照char对齐，c单独按照int对齐呢？我们打印一下sizeof(struct foo4)发现结果为4，也就是说编译器把a、b、c一起捆绑起来并以int做对齐了。

通过上面的例子我们发现很难总结出很规律性的东西，但是带有'位域'的结构体的对齐有条原则可以遵循，那就是："尽量减少结构体的占用空间"。当然显式的使用内存对齐的机会也并不多。^_^