自学算法之时空复杂度的计算
RobinHu 2018-07-23
体验到算法之美后，那么面对同一个问题却有着众多的解决方案。
我们心里应该会有点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：
- int i = 1;
- while(i <= n){
- i = i * 2;
- }
咳咳，对于算法萌新的笔者来说，算法2的时间复杂度，难度有点大。
首先，笔者不知道while语句和i = i * 2到底运行几次，这就有点像刺猬，无从下手。
笔者正在转换思维中.....
请看：
- int i = 1; //运行1次
- while(i <= n){ //假设运行X次
- i = i * 2; //假设运行X次
- }
遇到这种情况，我们可以假设嘛，哦也！
假设运行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，简单的两数交换：
- int temp;
- temp = a;
- a = b;
- b = temp;
我们可以看出，使用额外变量temp，即空间复杂度为O(1).
空间复杂度，好像没什么可说的，emmmmm!
