时间复杂度和空间复杂度

2019-11-04 本文已影响0人程序员will

时间复杂度和空间复杂度

案例来自漫画算法

时间复杂度

时间复杂度是统计代码基本执行次数的，下面用生活中的4个场景来进行说明。

场景1

一个长度为10 cm的面包，每3分钟吃掉1 cm，那么吃掉整个面包需要多久？

答案自然是3×10即30分钟。

如果面包的长度是n cm呢？

此时吃掉整个面包，需要3乘以n即3 n分钟。

如果用一个函数来表达吃掉整个面包所需要的时间，可以记作T(n) = 3 n，n为面包的长度。

T(n) = 3n，执行次数是线性的。

void eat1(int n){
    for(int i=0; i<n; i++){;
       System.out.println("等待1分钟"); 
       System.out.println("等待1分钟"); 
       System.out.println("吃1cm 面包"); 
    } 
}

场景2

1个长度为16 cm的面包，每5分钟吃掉面包剩余长度的一半，即第5分钟吃掉8 cm，第10分钟吃掉4 cm，第15分钟吃掉2 cm……那么把面包吃得只剩1 cm，需要多久呢？

这个问题用数学方式表达就是，数字16不断地除以2，那么除几次以后的结果等于1？这里涉及数学中的对数，即以2为底16的对数。 $log_2 16$

因此，把面包吃得只剩下1 cm，需要5× $log_2 16$ 即20分钟。

如果面包的长度是n cm呢？

此时，需要5乘以 $log _2 n$ 即5 $log _2 n$ 分钟，记作T(n) = 5 $log_2 n$ 。

 void eat2(int n){ 
     for(int i=n; i>1; i/=2){                     
         System.out.println("等待1分钟");
         System.out.println("等待1分钟");         
         System.out.println("等待1分钟");         
         System.out.println("等待1分钟");         
         System.out.println("吃一半面包"); 
     }
}

场景3

1个长度为10 cm的面包和1个鸡腿，每2分钟吃掉1个鸡腿。那么吃掉整个鸡腿需要多久呢？

答案自然是2分钟。

因为这里只要求吃掉鸡腿，和10 cm的面包没有关系。

如果面包的长度是n cm呢？

无论面包多长，吃掉鸡腿的时间都是2分钟，记作T(n) = 2。

 void eat3(int n){
     System.out.println(" 等待1分钟"); 
     System.out.println(" 吃1个鸡腿");
 }

场景4

1个长度为10 cm的面包，吃掉第1个1 cm需要1分钟时间，吃掉第2个1 cm需要2分钟时间，吃掉第3个1 cm需要3分钟时间……每吃1 cm所花的时间就比吃上一个1 cm多用1分钟。

吃掉整个面包需要多久呢？

答案是从1累加到10的总和，也就是55分钟。

如果面包的长度是n cm呢？

根据高斯算法，此时吃掉整个面包需要 1+2+3+…+(n-1)+ n 即(1+n)×n/2分钟，也就是0.5 * n * 2 + 0.5 * n分钟，记作T(n) = 0.5 * n * 2 + 0.5 * n。

void eat4(int n){
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){ 
            System.out.println("等待1分钟");}
            System.out.println("吃1cm 面包");
    }
}

上面所讲的是吃东西所花费的时间，这一思想同样适用于对程序基本操作执行次数的统计。

渐进时间复杂度

有了基本操作执行次数的函数T(n)，是否就可以分析和比较代码的运行时间了呢？还是有一定困难的。

例如算法A的执行次数是T(n)= 100 * n，算法B的执行次数是T(n)= $5n^2$ ，这两个到底谁的运行时间更长一些呢？这就要看n的取值了。

因此，为了解决时间分析的难题，有了渐进时间复杂度（asymptotic time complexity）的概念，其官方定义如下。

若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。

因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

对于上述四种场景，

T(n) = $3*n$ ，
最高阶项为 $3*n$ ，省去系数3，则转化的时间复杂度为：T(n)=O(n)。
T(n) = $5logn$ ，
最高阶项为 $5logn$ ，省去系数5，则转化的时间复杂度为：T(n) =O( $logn$ )。
T(n) = 2，
只有常数量级，则转化的时间复杂度为：T(n) =O(1)。
T(n) = $0.5*n^2+ 0.5*n$ ，
最高阶项为 $0.5*n^2$ ，省去系数0.5，则转化的时间复杂度为：T(n) =O( $n^2$ )。

这4种时间复杂度究竟谁的程度执行用时更长，谁更节省时间呢？

当n的取值足够大时，不难得出下面的结论：

O(1)<O( $logn$ )<O(n)<O( $n^2$ )

在编程的世界中有各种各样的算法，除了上述4个场景，还有许多不同形式的时间复杂度，例如：

O( $nlogn$ )、O( $n^3$ )、O( $mn$ )、O( $2^n$ )、O( $n!$ )

空间复杂度

用来描述一个算法所占空间的大小，叫空间复杂度。

空间复杂度计算

常量空间

当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。例如下面这段程序：

void fun1(int n){    
    int var = 3;
    … 
}

线性空间

当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。
例如下面这段程序：

void fun2(int n){
    int[] array = new int[n];
    … 
}

二维空间

当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n 成正比时，空间复杂度记作O( $n^2$ )。
例如下面这段程序：

void fun3(int n){
    int[][] matrix = new int[n][n];
    … 
}

递归空间

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。

“方法调用栈”包括进栈和出栈两个行为。

当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。
当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。

下面这段程序是一个标准的递归程序：

void fun4(int n){
    if(n<=1){
        return;
    }
    fun4(n-1);
    … 
}

执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

时间复杂度和空间复杂度

时间复杂度和空间复杂度