前言
通常，对于一个给定的算法，我们首先要验证算法的正确性，
其次主要从算法的执行时间和所需要占用的存储空间两个方面衡量一个算法的优劣。
时间复杂度：时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的最大次数。
空间复杂度：类似于时间复杂度的讨论，一个算法的空间复杂度为该算法所耗费的存储空间。往往跟为最大创建次数。
几类常见时间复杂度的示例解析
求解算法的时间复杂度的具体步骤是：
【1】找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
【2】计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析。
【3】 用大Ο记号表示算法的时间性能。
1、常数阶
int sum = 0, n = 100; /*执行一次*/
sum = (1 + n) * n / 2; /*执行一次*/
printf("%d",sum); /*执行一次*/
执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。
对于分支结构而言，无论是真，还是假，执行的次数都是恒定的，
不会随着n 的变大而发生变化，所以单纯的分支结构(不包含在循环结构中)，其时间复杂度也是0(1)。
2、线性阶
int i;
for(i = 0; i < n; i++){
/*时间复杂度为O(1)的程序步骤序列*/
}
线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。
因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。
上面这段代码，它的循环的时间复杂度为O(n)， 因为循环体中的代码须要执行n次。
3、对数阶
int count = 1;
while (count < n){
count = count * 2;
/*时间复杂度为O(1)的程序步骤序列*/
}
由于每次count乘以2之后，就距离n更近了一分。 也就是说，有多少个2相乘后大于n，
则会退出循环。 由2^x=n 得到x=logn。 所以这个循环的时间复杂度为O(logn)。
4、平方阶
下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)。
int i, j;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
/*时间复杂度为O(1)的程序步骤序列*/
}
}
而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。 所以这段代码的时间复杂度为O(n^2)。
如果外循环的循环次数改为了m，时间复杂度就变为O(mXn)。
所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
5、立方阶
下面例子是一个三重循环嵌套。
int i, j;
for(i = 1; i < n; i++)
for(j = 1; j < n; j++)
for(j = 1; j < n; j++){
/*时间复杂度为O(1)的程序步骤序列*/
}
这里循环了(1^2+2^2+3^2+……+n^2) = n(n+1)(2n+1)/6次，按照上述大O阶推导方法，时间复杂度为O(n^3)。
6、指数阶
long aFunc(int n) {
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
}
显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，
同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。
常见的时问复杂度如表所示:
常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
从图中可见，当n取不同值的时候，不同算法的时间复杂度优劣表现不同。我们应该根据实际情况和n的取值来选择最优的算法！
空间复杂度
我们在写代码时，完全用空间来换取时间.
比如说，要判断某某年是不是闰年，
你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，
都是要通过计算得到是否是闰年的结果。 还有另一个办法就是，
事先建立一个有2050个元素的数组(年数略比现实多一点)，然后把所有的年份按下标的数字对应，
如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，
就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，
但是硬盘上或者内存中需要存储这2050个0和1。
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
一个算法在计算机存储器上所占用的存储空间，包括
【1】存储算法本身所占用的存储空间，
【2】算法的输入输出数据所占用的存储空间。
【3】算法在运行过程中临时占用的存储空间这三个方面。
算法的输入输出数据所占用的存储空间是由要解决的问题决定的，
是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。
存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。
算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，
而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法；
有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，
当n较大时，将占用较多的存储单元。
如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；
当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；
当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n)。
二分查找时，每次都在原有查找内容进行二分，所以时间复杂度为O（log2 n）
因为变量值创建一次，所以空间复杂度为O（1）
时间复杂度为O（log2 n）
每进行一次递归都会创建变量，所以空间复杂度为O（log2 n）
时间复杂度O（n)
空间复杂度为O（1）
时间复杂度为O（2^n）
空间复杂度为O（n）
总结
下面贴出一个常用排序算法中的时间复杂度和空间复杂度的分析图：
网友评论