时间复杂度与空间复杂度详解

一. 算法效率

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

二.时间复杂度

1.定义

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。但注意，此函数并非我们代码中的main这类函数，而是我们数学中定义的，像：f(x) = x + c,这种函数。

2.用途

也许你看到以上时间复杂度的定义会认为时间复杂度测量的是程序运行的时间，但其实并不是这样的。程序的运行速率与许多因素挂钩，如计算机配置、网络或计算机所处状态等等，也就是说专门设计出一个概念去测量程序的运行时间是没有意义的。
时间复杂度真正测量的是算法中的基本操作的执行次数。

3.大O渐进表示法

大O渐进表示法：用于描述函数渐进行为的数学符号。

对于现在的计算机来说，其每秒完成的计算次数可达数亿，因此我们要将决定算法中的基本操作的执行次数的N近似当作无穷来看。有了这个前提，我们便能得到以下推到方法

推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
例如：对于算法中的基本操作的执行次数可以用F(N) = N^2 + N + 1000000表示的算法，其时间复杂度为O(N ^2)。

另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界）
在实际中一般情况关注的是算法的最坏运行情况。

4.计算程序的时间复杂度

voidFunc2(intN){intcount=0;for(intk=0;k<2*N;++k){++count;}intM=10;while(M--){++count;}printf("%d\n",count);}

如这个代码，其基本操作次数（如循环、递归）可以用F = N / 2 + 10（M）来表示
1.判断其时间复杂度情况是否唯一：
是的，其情况只由N决定，并且不会出现提前跳出循环等情况。
2.将变量近似无穷，取其最大次数：
N / 2。
3.去其系数：
时间复杂度 = O(N)。

// 计算Func3的时间复杂度？voidFunc3(intN,intM){intcount=0;for(intk=0;k<M;++k){++count;}for(intk=0;k<N;++k){++count;}printf("%d\n",count);}

表达式：F = M + N
1.判断其时间复杂度情况是否唯一：
是的，其情况由N,M决定，并且不会出现提前跳出循环等情况。
2.将变量近似无穷，取其最大次数：
这里存在两个变量，都将其近似无穷后它们就没什么区别了，
因此M可以看成N，所以取2 * N。
3.去其系数：
时间复杂度 = O(N)。

// 计算Func4的时间复杂度？voidFunc4(intN){intcount=0;for(intk=0;k<100;++k){++count;}printf("%d\n",count);}

表达式：100
对于这种可以用常数表示其最大运行次数的算法，其时间复杂度为O(1)。

// 计算BubbleSort的时间复杂度？voidBubbleSort(int*a,intn){assert(a);for(size_tend=n;end>0;--end){intexchange=0;for(size_ti=1;i<end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange=1;}}if(exchange==0)break;}}

表达式：F = N - 1 + N - 2 + ……+2+1 = N^2/2 - N / 2。
1.判断其时间复杂度情况是否唯一：
不，当exchange = 0时会直接跳出循环
最好情况：不用排序，F = N - 1；
平均情况：F= N ^ 2 / 4 + N / 4 - 1 / 2
最坏情况：最后一次大循环(以end记的)才排好序，F= N^2/2 - N / 2；
取最坏：F= N^2/2 - N / 2

2.将变量近似无穷，取其最大次数：
N^2 / 2。
3.去其系数：
时间复杂度 = O(N^2)。

// 计算BinarySearch的时间复杂度？intBinarySearch(int*a,intn,intx){assert(a);intbegin=0;intend=n-1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while(begin<=end){intmid=begin+((end-begin)>>1);if(a[mid]<x)begin=mid+1;elseif(a[mid]>x)end=mid-1;elsereturnmid;}return-1;}

每查找一次，范围都缩小一半
表达式：F = logN。(底数为2一般都直接写log)
1.判断其时间复杂度情况是否唯一：
不，不一定要将数组全部遍历才能找到查找值。
最好情况：第一个直接查到(F = 1)
平均情况：F = (1 + logN) / 2
最差情况：最后一个才找到(F = logN)
取最差：F = logN
2.将变量近似无穷，取其最大次数：
logN
3.去其系数：
时间复杂度 = O(logN)。

// 计算阶乘递归Fac的时间复杂度？longlongFac(size_tN){if(0==N)return1;returnFac(N-1)*N;}

要递归N次
表达式：F= N
1.判断其时间复杂度情况是否唯一：
是的，其情况只由N决定，并且不会出现提前跳出递归等情况。
2.将变量近似无穷，取其最大次数：
N
3.去其系数：
时间复杂度 = O(N)。

三.空间复杂度

1.定义：

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。
特别注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候需要申请的额外空间来确定。

2.用途

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

3.计算空间复杂度

// 计算BubbleSort的空间复杂度？voidBubbleSort(int*a,intn){assert(a);for(size_tend=n;end>0;--end){intexchange=0;for(size_ti=1;i<end;++i){if(a[i-1]>a[i]){Swap(&a[i-1],&a[i]);exchange=1;}}if(exchange==0)break;}}

1.找到需要开辟的额外空间：
int exchange
2.看开了多少个额外空间：
1个
3.取最高次
O(1)

// 计算Fibonacci的空间复杂度？// 返回斐波那契数列的前n项longlong*Fibonacci(size_tn){if(n==0)returnNULL;}longlong*fibArray=(longlong*)malloc((n+1)*sizeof(longlong));fibArray[0]=0;fibArray[1]=1;for(inti=2;i<=n;++i){fibArray[i]=fibArray[i-1]+fibArray[i-2];}returnfibArray;

1.找到需要开辟的额外空间：
long long * fibArray
2.看开了多少个额外空间：
N + 1：（(n+1) * sizeof(long long)）
3.取最高次
O(N)

// 计算阶乘递归Fac的空间复杂度？longlongFac(size_tN){if(N==0)return1;returnFac(N-1)*N;}

1.找到需要开辟的额外空间：
函数Fac
2.看开了多少个额外空间：
每递归一次要创建一个函数栈帧，递归N次：N
3.取最高次
O(N)

四.常见复杂度对比

复杂度从小到大：
常数阶：O(1)
对数阶：O(logn)
线性阶：O(N)
nlogn阶：O(nlogn)
平方阶：O(N^2)----分界线，以下的效率太低
立方阶：O(N^3)
指数阶：O(2^N)