自学算法之时空复杂度的计算

体验到算法之美后，那么面对同一个问题却有着众多的解决方案。

我们心里应该会有点B数。

所以，本博客不会花大篇幅去描述，算法的特性和概念。

直接进入时空复杂度的计算。

首先。

时间复杂度概念：算法需要运行的时间，一般将算法的执行次数作为时间复杂度的度量标准。

我们看算法1：

int sum = 0; //运行1次

int total = 0; //运行1次

for(int i = 0; i < n; i++){ //运行n次

sum = sum + i; //运行n次

for(int j = 0; j < n; j++){ //运行n*n次

total = total + i * j; //运行n*n次

}

那么，我们将所有语句的运行次数相加，得出： 1 + 1 + n + n + n*n + n*n = 2n^2 + 2n + 2 ,即用函数表达：

T（n） = 2n^2 + 2n + 2 时间复杂度：O（n^2）

所以，当n足够大的时候，函数取决于第一项，后面可以忽略不计。

当然，算法1对大多数读者显得没有什么难度，秒秒钟可以算出时间复杂度。

笔者汗颜。

那么请看算法2：

1. 
   
2. int i = 1;
3. while(i <= n){
4. i = i * 2;
5. }

咳咳，对于算法萌新的笔者来说，算法2的时间复杂度，难度有点大。

首先，笔者不知道while语句和i = i * 2到底运行几次，这就有点像刺猬，无从下手。

笔者正在转换思维中.....

请看：

1. 
   
2. int i = 1; //运行1次
3. while(i <= n){ //假设运行X次
4. i = i * 2; //假设运行X次
5. }

遇到这种情况，我们可以假设嘛，哦也！

假设运行X次后，每次运算后 i 的值为：2， 2^2， 2^3， ...... , 2^x

当X = n的时候结束，即 2^x = n

得出：x = log2n ， 那么算法2的时间复杂度为 : O（1 + 2log2n）

计算完算法1和算法2，笔者好像觉得时间复杂度的计算还OK啦，但是，请记住：

并不是每个算法都能直接计算运行次数。

比如：查找，插入，排序等等。

面对这种情况，我们需要从三个方面来描述一个算法的OK性。

最好、最坏、平均。(英文就不写了，自己查找)

时间复杂度，就说到这里。

空间复杂度概念：算法占用的空间大小，一般将算法的辅助空间作为衡量标准。

当然，算法的占用存储空间分为：

1， 输入输出数据

2， 算法本身

3，额外需要的辅助空间。

话不多说，看程序3，简单的两数交换：

1. 
   
2. int temp;
3. temp = a;
4. a = b;
5. b = temp;

我们可以看出，使用额外变量temp，即空间复杂度为O(1).

空间复杂度，好像没什么可说的，emmmmm!