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

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:


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

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

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

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

请看:


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

遇到这种情况,我们可以假设嘛,哦也!

假设运行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. int temp;
  2. temp = a;
  3. a = b;
  4. b = temp;

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

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

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

相关推荐