数据结构算法之时间复杂度和空间复杂度

2019-03-15 本文已影响0人 Peakmain

在了解时间复杂度之前，首先我们需要了解一下什么是时间频度

时间频度

一个算法花费的时间与算法中语句执行的次数成正比例，一个算法的语句执行的次数称为语句频度或者时间频度，表示为T(n),n表示问题的规模。简单点就是这条语句执行了的最终次数

时间复杂度

一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋于无穷大的时候，T(n)f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同量级函数，记住T(n)=O(f(n))称O(f(n))为算法的渐进时间复杂度，简称时间复杂度

也就是说当n趋于无限大的的时候，常数和低级次幂可以忽略不记。比如：某个函数的时间的频度是：
T(n)=100000n^2 +60000n+7000;但是它的时间复杂度实际就是T(n)=O(n^2)

时间复杂度计算

1.找出算法中的基本语句
算法中执行次数最多那条居于就是基本语句，通常是内层循环的循环体
2.计算基本语句的执行次数的数量级
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可
可以忽略所有低次幂和最高次幂的常数
3.用大O记号表示算法的时间性能

时间复杂度举例

一个简单语句的时间复杂度为O(1)

int i=0;

无论上面的代码是执行1000次还是10000次它的时间复杂度都是O(1)，因为1000和10000都是常数而不是趋于无穷大

一个循环的时间复杂度为O(n)

int n=100; count=100;
for(int i-1;i<n;<i++){
     count++:
}

当i=1的时候执行一次，当2的时候执行二次，以此推，n的时候执行的是n次

时间复杂度为O（log2n的循环语句）

int n=100; count=100;
for(int i-1;i<n;<i*2){
     count++:
}

其实很简单的我们发现这条语句执行的次数是log2n

时间复杂度是O(n^2)的二重循环

int n=100; count=100;
for(int i-1;i<n;<i++){
     for(int j=1;j<n;<j++){
       count++;
  }
}

当i=1的时候，j执行了n次，当i=2的时候，j又执行了n次，所以实际一共执行了n*n次

我们再看一个时间复杂度是O(n^2)的二重循环

int n=100; count=100;
for(int i-1;i<n;<i++){
     for(int j=1;j<=i;<j++){
       count++;
  }
}

当i=1的时候，实际j执行了1次，当i=2的时候，执行了2次以此推出实际执行的次数是：
1+2+3+......+n,也即是(n+1)*n/2.常数，低次幂忽略，所以时间复杂度也就是O(n^2)

空间复杂度

空间复杂度是对一个算法在运行过程中l临时占用的存储空间大小的量度，一般作为问题规模的n函数，以数量级形式给出,记住：S(n)=O(g(n))

空间复杂度分析

    int add(int n) {
        int i, j, k, s;
        s = 0;
        for (i=0; i<n；I++){
            for (j = 0; j < i; j++) {
                s++;
            }
        }
    }

空间复杂度实际就是4个，因为首先我们会给i,j,k,s四个开辟空间，无论你怎么变化，实际都是在自己的空间变化
我们继续看下案例：递归算法的控件复杂度

 void add(int a[], int n, int k) {
        int i;
        if (k == n - 1) {
            //打印
        } else {
            for (i = k; i < n; i++) {
                a[i] = a[i] + 10;
                add(a, n, k + 1);
            }
        }
    }

上面的代码每调用一次都会为i创建一个空间，那么add(a,n,0）共执行次数应该是n次，所以空间复杂度应该是O(n)