一：渐近符号
1.1 符号的辨析
1.1.1 符号O
O，读作“大O”，非正式来说，O(g(n))是增长次数小于等于g(n)及其常数倍（n趋向于无穷大）的函数集合。
定义 如果函数f(n)包含在O(g(n))中，记作f(n)∈O(g(n))（平时使用为了方便书写，我们通常使用f(n)=O(g(n))代替）。它的成立条件是：对于所有足够大的n，f(n)的上界由g(n)的常数倍所确定，也就是说，存在大于0的常数c和非负整数n0，使得：
n≥n0来说，
f(n)≤c(g(n)
下图说明了这个定义：
下面给出几个例子：
n100n+512n(n−1)n30.00001n3=O(n2)=O(n2)=O(n2)≠O(n2)≠O(n2)(1.1.1.1)(1.1.1.2)(1.1.1.3)(1.1.1.4)(1.1.1.5)
1.1.2 符号Ω
Ω，读作“omega”，Ω(g(n))是增长次数大于等于g(n)及其常数倍（n趋向于无穷大）的函数集合。
定义 如果函数f(n)包含在Ω(g(n))中，记作f(n)=Ω(n))。它的成立条件是：对于所有足够大的n，f(n)的下界由g(n)的常数倍所确定，也就是说，存在大于0的常数c和非负整数n0，使得：
n≥n0来说，
f(n)≥c(g(n)
下图说明了这个定义：
下面给出几个例子：
n312n(n−1)100n+5=Ω(n2)=Ω(n2)≠Ω(n2)(1.1.2.1)(1.1.2.2)(1.1.2.3)
1.1.3 符号Θ
读作“theta”。
定义 如果函数f(n)包含在Θ(g(n))中，记作f(n)=Θ(n))。它的成立条件是：对于所有足够大的n，f(n)的上界和下界由g(n)的常数倍所确定，也就是说，存在大于0的常数c1,c2和非负整数n0，使得：
n≥n0来说，
c1g(n)≤f(n)≤c2g(n)
下图说明了这个定义：
下面给出几个例子：
12n(n−1)6n3=Θ(n2)≠Θ(n2)(c1=14,c2=12,n0=2)(1.1.3.2)
1.2 符号的性质
定理 如果t1(n)=O(g1(n))并且t2(n)=O(g2(n))，则
t1(n)+t2(n)=O(max{g1(n),g2(n)})
对于Ω和Θ符号，同样成立。
证明 增长次数的证明是基于以下简单事实：对于4个任意实数a1,b1,a2,b2，如果a1≤b1并且a2≤b2，则a1+a2≤2max{b1,b2}。
因为t1(n)=O(g1(n))，存在正常量c1和非负整数n1，使得：
n≥n1,t1(n)≤c1g1(n)
t2(n)=O(g2(n))，
n≥n2,t2(n)≤c2g2(n)
c3=max{c1,c2}并且n≥max{n1,n2}，就可以利用两个不等式的结论将其相加，得出以下结论：
t1(n)+t2(n)≤c1g1(n)+c2g2(n)≤c3g1(n)+c3g2(n)=c3[g1(n)+g2(n)]≤c3⋅2max{g1(n),g2(n)}(1.2.1)(1.2.2)(1.2.3)
那么，对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大增长次数的部分所决定的，即效率较差的部分决定。
二：复杂度求解方法分析
对于一个普通函数（即非递归函数），其时间复杂度自然易求。下面我们主要谈谈如何求解递归函数的时间复杂度。
递归函数通常会有以下的方程式：
T(n)=aT(nb)+f(n)(2.1)
其中，a≥1,b>1，且都是常数，f(n)是渐近正函数。递归式（2.1）描述的是这样一种算法的运行时间：它将规模为n的问题分解为a个子问题，每个子问题规模为nb，其中a≥1,b>1。a个子问题递归地求解，每个花费时间T(nb)。函数f(n)包含了问题分解和子问题解合并的代价。
常用的方法有两种：主定理和分治法。
2.1 主定理（Master Theorem）
定理 令a≥1,b>1，且都是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式，即：
T(n)=aT(nb)+f(n)
其中我们将nb解释为⌊nb⌋或⌈nb⌉。那么T(n)有如下渐近界：
（Case 1）如果f(n)=O(nc)，其中c<logba，则：
T(n)=Θ(nlogba)
k≥0，使f(n)=Θ(nclogkn)，其中c=logba，则：
T(n)=Θ(nclogk+1n)
f(n)=Ω(nc)，其中c>logba，并且对某个常数k<1和所有足够大的n有af(nb)≤kf(n)，则：
T(n)=Θ(f(n))
算法导论已有关于这个定理的证明，故此处省略，有兴趣的读者可以去翻阅下。
2.2 分治法
nb，其中a个实例需要实际求解，对于n=bk,k=1,2,3...，其中a≥1,b>1，得到以下结果：
T(n)T(bk)=aT(nb)+f(n)=aT(bk−1)+f(bk)=a[aT(bk−2)+f(bk−1)]+f(bk)=a2T(bk−2)+af(bk−1)+f(bk)=a3T(bk−3)+a2f(bk−2)+af(bk−1)+f(bk)=...=akT(1)+ak−1f(b1)+ak−2f(b2)+...+a0f(bk)=ak[T(1)+∑j=1kf(bj)aj](原始递归方程式)(2.2.2)(2.2.3)(2.2.4)(2.2.5)(2.2.6)(2.2.7)
ak=alogbn=nlogba,当n=bk时，对于式（2.2.7）我们可以推出下式：
T(n)=nlogba[T(1)+∑j=1logbnf(bj)aj](2.2.8)
显然，T(n)的增长次数取决于常数a和b的值以及函数f(n)的增长次数。
三：无意发现的定理
以下是我自己在演算时无意发现的，并给出了证明。
该定理依旧建立在递归方程式中，即：
T(n)=aT(nb)+f(n)(a≥1,b>1)
根据以上的方程式有以下两个定理：
定理1
定理1 对于递归方程式，若a=1,b>1,f(n)=c,c为某个常数，即：
T(n)=T(nb)+c
则：
T(n)=Θ(logn)
证明 应用主定理 Case 2，其中c=logba=logb1=0，再使k=0，则f(n)=Θ(nclogkn)=Θ(1)，这里的f(n)即等于常数c，证明成立。
定理2
定理2 对于递归方程式，若a=1,b>1,f(n)=kn+p，其中k>0,p>0且为某个常数（也就是f(n)是一个线性直线方程），即：
T(n)=T(nb)+(kn+p)(b>1,k>0,p为某个常数)
则：
T(n)=Θ(n)
证明 应用分治法中式（2.2.8）：
T(n)=nlogba[T(1)+∑j=1logbnf(bj)aj]=∑j=1logbn(kbj+p)=plogbn+kbb−1(n−1)<pn+kbb−1(n−1)=cn−kbb−1=Θ(n)(3.2.1)(3.2.2)(k>0,p>0,b>1)(3.2.4)(c>0且为某个常数)(3.2.5)
证明成立。
四：总结
O,Ω,Θ三种符号的区别以及它们的性质。
第二部分介绍了两种常用的计算时间复杂度方法，即主定理和分治法。
第三部分给出了个人在演算时发现的两个定理，并给出了证明，题外话，这两条定理比较实用，希望读者能够熟记。另外如果您在其它网站看到类似原创定理，纯属巧合，勿喷。
参考文献：
[1] Thomas H.Cormen,etc. 算法导论（第三版）.
[2] Anany Levitin. 算法设计与分析基础（第三版）.
[3] . Master theorem. Wikipedia.