时间复杂度的定义
一段代码的时间复杂度就是指该段代码运行所需要的时间。
一般来说，执行一条普通语句（非循环）需要耗时为1，则执行n条语句需要的时间为n。
void func(){
int n = 1; //1
int m = n+3; //2
return m+n; //3
}上面的代码运行耗时就为3，如果上面的函数有n行（规模为n），则需要的时间为n。
for (int i=0; i< 100; i++){
printf("hello %d",i);
printf("world %d",i);
}如果代码是一个循环，比如上图，每次循环需要的步骤是4（2个printf，i++, i和100比较），则100次循环的时候 耗时为 4*100，n次循环耗时为 4n。
for (int i=0; i< 100; i++)
for (int j=0; j< 100; j++)
printf("hello world");
for (int i=0; i< 100; i++)
n++如果是一个双循环，每次循环的需要执行步骤是5，则上图所需步骤为 100*100*5+3*100 ， 当循环的规模为n的时候，所需步骤为 5*n*n+3*n = 5n^2+3n。
渐进表示法和大O记号
上面的步骤标记一定程度上能反应真实的运算耗时，但并不精确，比如，printf函数未必真的和n++一样只需要1个步骤，而且当代码形成一定规模后（执行n次），我们只需要一个估算值而不是精确值来表示 该段代码的执行效率 （也就是时间复杂度），渐进表示法在规模n下的时间复杂度常常省略常数，且只记录最高次项（比如5n^2+3n，在n很大的情况下，可以忽略 3n的增长速度，只记为 n^2），并记为 O(n) ，对于上面3个例子，O(n)分别为 n, n, n^2。
O(n)的定义：
设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，
使得 n>=n0时，f(n)<=cg(n),则记作f(n)=O(g(n)),就称为大O记号。从上面的定义可知 函数 f(n) 始终小于 O(g(n)), 因此O 是 f(n) 的上限。
例1：f(n) = 10n^2+4n，求证f(n)=O(n^2)
当 n>=4 时， 4n <= n^2, 推出 当 n0=4,c=11, g(n)=n^2 时， 10n^2+4n <=11n^2，
所以 f(n)=O(n^2)例2：f(n) = 3n+12，求证f(n)=O(n)
当 n>=12 时， 3n+12<=12n，推出 当 n0=12，c=12, g(n)=n 时， 3n+12<=12n,
所以 f(n)=O(n)常见时间复杂度举例
时间复杂度常见的有以下几种：n, logn, nlogn, n^2, 2^n, n! 等等
while (i<n){
i =i*2;
printf("hello");
}上面的代码，因为每次i都乘以2，假设2^x>n，x=log2(n) ，所以当规模为n的时候，循环只需要执行c*log2(n)，c是一次循环需要的时间，根据渐进表示法，忽略常数取最高次，也要忽略log的底数，O(n)=logn，下面是其他的一些例子：
for (int i=0; i<n;i++){
while (i<n){
i =i*3;
printf("hello");
}
} //O(n)=nlogn
while (i<2^n){
printf("%v",i++);
}//O(n)=2^nθ 记号
θ记号的定义：
设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1,c2和n0，
使得 n>=n0时，c1g(n)<=f(n)<=c2g(n),则记作f(n)=θ(g(n)),就称为θ记号。从上面的定义可知 ， θ(g(n)) 既是 f(n) 的上限，也是 f(n) 的下限。
例1：f(n)=2n+3 求证f(n)=θ(n)
f(n)=2n+3; 则存在 c1*g(n) = 1*n 和 c2*g(n)=5*n，
可以保证当n>=1时(n0=1)， 1*n <= f(n) <= 5*n, 因此θ(g(n)) = n例2：f(n)=10n^2+4n+2 求证f(n)=θ(n^2)
f(n)=10n^2+4n+2, 则存在 c1*g(n)=10n^2 和 c2*g(n) =11*n^2,
可以保证当n>=5时(n0=5)， 10n^2 <=10n^2+4n+2 <=11*n^2，因此θ(g(n))=n^2Ω 记号（大Ω）
Ω 记号的定义：
设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，
使得 n>=n0时，f(n)>=cg(n),则记作f(n)=Ω(g(n)),就称为大Ω记号。从上面的定义可知 函数 f(n) 始终大于等于 Ω(g(n)), 因此Ω 是 f(n) 的下限。
例1: f(n)=2n+3 求证f(n)=Ω(n)
存在 c*g(n) = 2*n, 可以保证当n>=1时， f(n)>=g(n),也就是 2n+3>=2n, 因此g(n)=no 记号（小O） 和 w 记号（小Ω）
o记号是O记号的小写，表示 f(n)w记号是 Ω记号的小写，表示f(n)>cg(n). 和前面的差不多， 只是不包含了等于，是开区间，不再展开。
递归函数的时间复杂度
递归函数 涉及到时间复杂度的嵌套,其计算方法有以下几种，迭代法，归纳法，递归树, 公式套用法。
迭代法
void func2(int n, int m){
n++; //1
if(m > 0){//2
n++;
return func2(n,m-1);
}
return; //3
}上面这个递归函数，当m=0的时候，程序要只要执行 3步，记为 T(0)=3； 当 m=1的时候 根据代码可以分析出：T(1)=T(0)+4，则当m=n的时候需要执行 T(n) = T(n-1)+4步， 如下：
| 3 (n = 0)
T(n)|
| T(n-1)+4 (n > 0)那么 当 m=n时，需要的总时间为：
T(n) = T(n-1)+4 = T(n-2)+4+4 = T(n-3)+4+4+4 = T(0)+4*n = 4n+3所以上面递归函数的时间复杂度为 O(n)。
归纳法
使用数学归纳法，也可以计算时间复杂度：，比如 T(1)=1, T(n)=2T(n-1)+1, 先手工计算 简单的复杂度： T(1)=1, T(2)=3, T(3)=7, T(4)=15,T(5)=31, T(6)=63，
根据规律可以推测 T(n)=2^n-1, 则可以证明：
当 n = 1时， T(1)=2^1-1 =1， 成立
假设当 n = m 时， T(m) = 2^m-1,
则 T(m+1) = 2*T(m) +1 = 2*(2^m-1)+1 = 2^(m+1)-1,
用n代替m+1得：T(n)=2^n-1， 因此 T(n)=θ(2^n), 时间复杂度就是O(2^n)递归树
递归树其实算迭代法中的一种，这里单独讨论，递归树是使用画图的方式把递归的结构画出来，可以直观看到其迭代过程，因为得到的图往往是树形的，因此叫递归树。
例1： T(n)=2T(n/2)+n
分析：其中n层的规模为n，n层由2个n-1层相加，则n-1层的规模是2*n/2=n,因此每一层的规模都是n，一共有logn+1层，因此总规模为n*(logn+1) = O(nlogn)。 下面是伪代码：
void recursion(int n){
int i = 0;
while (i<n) //上面的规模简化为 n
printf("%d\n", n);
recursion(n/2) //T(n/2)
recursion(n/2) //T(n/2)
} //T(n)=2*T(n/2)+n例2：T(n) = T(n/3)+T(2n/3)+n
设其中最长的一条路径为K，则最长路径是（2/3)^K = n, K=log(2/3)n, 数的层数是K+1,因此 规模最大为 n*log(2/3)n = O(nlogn).
套用公式法
对于 格式为 T(n)=aT(n/b)+f(n) 形式，且a>=1,b>1，有以下公式,,其中Θ的含义增长阶数与g(n)相同的函数集合，Ω表示 增长阶数不低于g(n)的函数集合，（3）中c=a/b,
注意公式法也不能解决所有递归的复杂度
例1：T(n)=4T(n/3)+n
例2：T(n)=T(n/2)+1
例3： T(n)=3T(n/4)+n
