时间复杂度和空间复杂度
案例来自漫画算法
时间复杂度
时间复杂度是统计代码基本执行次数的，下面用生活中的4个场景来进行说明。
场景1
一个长度为10 cm的面包，每3分钟吃掉1 cm，那么吃掉整个面包需要多久？
答案自然是3×10即30分钟。
如果面包的长度是n cm呢？
此时吃掉整个面包，需要3乘以n即3 n分钟。
如果用一个函数来表达吃掉整个面包所需要的时间，可以记作T(n) = 3 n，n为面 包的长度。
T(n) = 3n，执行次数是线性的。
void eat1(int n){
for(int i=0; i<n; i++){;
System.out.println("等待1分钟");
System.out.println("等待1分钟");
System.out.println("吃1cm 面包");
}
}
场景2
1个长度为16 cm的面包，每5分钟吃掉面包剩余长度的一半， 即第5分钟吃掉8 cm，第10分钟吃掉4 cm，第15分钟吃掉2 cm……那么把面包吃得 只剩1 cm，需要多久呢？
这个问题用数学方式表达就是，数字16不断地除以2，那么除几次以后的结果等 于1？这里涉及数学中的对数，即以2为底16的对数。
因此，把面包吃得只剩下1 cm，需要5×即20分钟。
如果面包的长度是n cm呢？
此时，需要5乘以即5
分钟，记作T(n) = 5
。
void eat2(int n){
for(int i=n; i>1; i/=2){
System.out.println("等待1分钟");
System.out.println("等待1分钟");
System.out.println("等待1分钟");
System.out.println("等待1分钟");
System.out.println("吃一半面包");
}
}
场景3
1个长度为10 cm的面包和1个鸡腿，每2分钟吃掉1个鸡腿。 那么吃掉整个鸡腿需要多久呢？
答案自然是2分钟。
因为这里只要求吃掉鸡腿，和10 cm的面包没有关系。
如果面包的长度是n cm呢？
无论面包多长，吃掉鸡腿的时间都是2分钟，记作T(n) = 2。
void eat3(int n){
System.out.println(" 等待1分钟");
System.out.println(" 吃1个鸡腿");
}
场景4
1个长度为10 cm的面包，吃掉第1个1 cm需要1分钟时间，吃 掉第2个1 cm需要2分钟时间，吃掉第3个1 cm需要3分钟时间……每吃1 cm所花的时间就 比吃上一个1 cm多用1分钟。
吃掉整个面包需要多久呢？
答案是从1累加到10的总和，也就是55分钟。
如果面包的长度是n cm呢？
根据高斯算法，此时吃掉整个面包需要 1+2+3+…+(n-1)+ n 即(1+n)×n/2分 钟，也就是0.5 * n * 2 + 0.5 * n分钟，记作T(n) = 0.5 * n * 2 + 0.5 * n。
void eat4(int n){
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
System.out.println("等待1分钟");}
System.out.println("吃1cm 面包");
}
}
上面所讲的是吃东西所花费的时间，这一思想同样适用于对程序基本操作执行次数的统计。
渐进时间复杂度
有了基本操作执行次数的函数T(n)，是否就可以分析和比较代码的运行时间了 呢？还是有一定困难的。
例如算法A的执行次数是T(n)= 100 * n，算法B的执行次数是T(n)= ，这两个 到底谁的运行时间更长一些呢？这就要看n的取值了。
因此，为了解决时间分析的难题，有了渐进时间复杂度（asymptotic time complexity）的概念，其官方定义如下。
若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的 常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算 法的渐进时间复杂度，简称为时间复杂度。
因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。
对于上述四种场景，
- T(n) =
，
最高阶项为 - T(n) =
，
最高阶项为)。
- T(n) = 2，
只有常数量级，则转化的时间复杂度为：T(n) =O(1)。 - T(n) =
，
最高阶项为，省去系数0.5，则转化的时间复杂度为：T(n) =O(
)。
这4种时间复杂度究竟谁的程度执行用时更长，谁更节省时间呢？
当n的取值足 够大时，不难得出下面的结论：
O(1)<O()<O(n)<O(
)
在编程的世界中有各种各样的算法，除了上述4个场景，还有许多不同形式的时 间复杂度，例如：
O()、O(
)、O(
)、O(
)、O(
)
空间复杂度
用来描述一个算法所占空间的大小，叫空间复杂度。
空间复杂度计算
常量空间
当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记 作O(1)。例如下面这段程序：
void fun1(int n){
int var = 3;
…
}
线性空间
当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模n成 正比时，空间复杂度记作O(n)。
例如下面这段程序：
void fun2(int n){
int[] array = new int[n];
…
}
二维空间
当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n 成正比时，空间复杂度记作O()。
例如下面这段程序：
void fun3(int n){
int[][] matrix = new int[n][n];
…
}
递归空间
递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合， 但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。
“方法调用栈”包括进栈和出栈两个行为。
当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。
当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。
下面这段程序是一个标准的递归程序：
void fun4(int n){
if(n<=1){
return;
}
fun4(n-1);
…
}
执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。
