al_08 时间复杂度与空间复杂度

阅读数: 次 2021-01-01

如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议许可，附上本文作者及链接。
本文作者： 执笔成念
作者昵称： zbcn
本文链接： https://1363653611.github.io/zbcn.github.io/2021/01/01/al_08%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E4%B8%8E%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/

概述

时间复杂度和空间复杂度用来衡量一个算法的好坏。

时间复杂度：指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间复杂度：指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

时间复杂度

什么是大O？

T(n) = O(f(n))

n 表示数据规模
O(f(n)) 运行算法要执行的指令数，和 f(n)成正比

上面公式中用到的 Landau符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。

常见的时间复杂度量级

常数阶O(1)
线性阶O(n)
平方阶O(n²)
对数阶O(logn)
线性对数阶O(nlogn)

看动画轻松理解时间复杂度（一）

常数阶 O(1)

无论代码执行了多少行，其他区域不会影响到操作，这个代码的时间复杂度都是O(1)

看动画轻松理解时间复杂度（一）

void swap2Ints(int a, int b){
    int temp = a;
    a = b;
    b = temp;
}

线性阶O(n)

看动画轻松理解时间复杂度（一）

for循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此可以用O(n)来表示它的时间复杂度。

int sum(int n){
    int ret = 0;
    for(int i=0; i<=n; i++){
        ret += i;
    }
    return ret;
}

特别一提的是 c * O(n) 中的 c 可能小于 1 ，比如下面这段代码：

public void swap(String s){
	int n = s.length;
    for(int i =0; i< n/2; i++){
        swap2Ints(s[i],s[n-1 -1]);
    }
}

平方阶O(n²)

看动画轻松理解时间复杂度（一）

当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

public sort(int[] arr){
    int n = arr.size();
    for(int i=0; i< n; i++){
        int minInt = i;
        for(int j=i+1; j<n; j++){
            if(arr[j] < arr[i]){
                minInt = j;
            }
        }
         swap2Int(arr[j], arr[minInt]);
    }  
}

推导

当 i = 0 时，第二重循环需要运行 (n – 1) 次
当 i = 1 时，第二重循环需要运行 (n – 2) 次
。。。。。。

公式：

1	(n - 1) + (n - 2) + (n - 3) + ... + 0
2	= (0 + n - 1) * n / 2
3	= O (n ^2)

对数阶O(logn)

看动画轻松理解时间复杂度（一）

在二分查找法的代码中，通过while循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环。

int binarySearch(int[] arr, int target){
    int length = arr.size();
    int l = 0;
    int r = length -1;
    while(true){
        int mid = l+ (r-1)/2;
        if(arr[mid] == target){
            return target;
        }
        if(arr[mid] > target){
            r = mid-1;
        }else{
            r = mid+1;
        }
    }
    return -1;//没有找到
}

实例1

1	//// 整形转成字符串
2	String str2Int(int num){
3	String s = "";
4	//经过几次除以10的形式转换为 0
5	while(true){
6	s+="0" + num%10;
7	num /=10;
8	}
9	reverse(s);
10	return s;
11	}

线性对数阶O(nlogn)

将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)

1	//n*logn
2	void hello (){
3	//n
4	for( m = 1 ; m < n ; m++){
5	i = 1;
6	// logn
7	while( i < n ){
8	i = i * 2;
9	}
10	}
11	}

复杂的几种时间复杂度

递归算法的时间复杂度（recursive algorithm time complexity）
最好情况时间复杂度（best case time complexity）
最坏情况时间复杂度（worst case time complexity）
平均时间复杂度（average case time complexity）
均摊时间复杂度（amortized time complexity）

递归算法的时间复杂度（recursive algorithm time complexity）

如果递归函数中，只进行一次递归调用，递归深度为depth；
在每个递归的函数中，时间复杂度为T；则总体的时间复杂度为O(T * depth)。

归并排序与快速排序都带有递归的思想，并且时间复杂度都是O(nlogn) ，但并不是有递归的函数就一定是 O(nlogn) 级别的。从以下两种情况进行分析。

递归中进行一次递归调用的复杂度分析

二分查找

int binarrySearch(int[] arr, int l, int r, int target){
    if(l > r){
        return -1;
    }
    int mid = l + (r-1)/2;
    if(arr[mid] == target){
        return target;
    }
    if(arr[mid] < target){
        binarrySearch(arr,mid +1,r,target);
    }else{
        binarrySearch(arr, l, mid-1, target);
    }
}

比如在这段二分查找法的代码中，每次在 [ l , r ] 范围中去查找目标的位置，如果中间的元素 arr[mid] 不是 target，那么判断 arr[mid]是比 target 大还是小，进而再次调用 binarySearch这个函数。

在这个递归函数中，每一次没有找到target时，要么调用左边的 binarySearch函数，要么调用右边的 binarySearch函数。也就是说在此次递归中，最多调用了一次递归调用而已。根据数学知识，需要log2n次才能递归到底。因此，二分查找法的时间复杂度为 O(logn)。

求和

在这段代码中比较容易理解递归深度随输入 n 的增加而线性递增，因此时间复杂度为 O (n)。

1	int sum(int n){
2	if(n == 0){
3	return 0;
4	}
5	return n + sum(n-1);
6	}

求幂

1	//递归深度：logn
2	//时间复杂度：O(logn)
3	private static int pow(int x, int n){
4	if(n == 0){
5	return 1;
6	}
7	int t = pow(x,n/2);//每一次分一半，直到n不能再分，即 n = 0
8	if(n%2 != 0 ){//判断奇偶，1，3,5
9	return x tt;
10	}
11	return t*t;
12	}

递归深度为 logn，因为是求需要除以 2 多少次才能到底。

递归中进行多次递归调用的复杂度分析

递归算法中比较难计算的是多次递归调用。

两次递归调用

1	// O(2^n) 指数级别的数量级，后续动态规划的优化点
2	int f(int n){
3	if(n==0){//递归的终止条件
4	return 1;
5	}
6	return f(n-1) + f(n+1);
7	}

递归树中节点数就是代码计算的调用次数。

案例

比如当 n = 3 时，调用次数计算公式为

1	1 + 2 + 4 + 8 = 15

一般的，调用次数计算公式为

1	2^0 + 2^1 + 2^2 + …… + 2^n
2	= 2^(n+1) - 1
3	= O(2^n)

与之有所类似的是归并排序的递归树，区别点在于

上述例子中树的深度为 n，而归并排序的递归树深度为logn。
上述例子中每次处理的数据规模是一样的，而在归并排序中每个节点处理的数据规模是逐渐缩小的

因此，在如归并排序等排序算法中，每一层处理的数据量为 O(n) 级别，同时有 logn 层，时间复杂度便是 O(nlogn)。

最好、最坏情况时间复杂度

最好、最坏情况时间复杂度指的是特殊情况下的时间复杂度。

动图表明的是在数组 array 中寻找变量 x 第一次出现的位置，若没有找到，则返回 -1；否则返回位置下标。

int find(int[] array, int n, int x){
    for(int i =0; i < n; i++){
       if(array[i] == x){
           return i;
       } 
    }
    return -1;
}

在这里当数组中第一个元素就是要找的 x 时，时间复杂度是 O(1)；而当最后一个元素才是 x 时，时间复杂度则是 O(n)。

最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度，它的时间是最短的；最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度，它的时间是最长的。

平均情况时间复杂度

最好、最坏时间复杂度反应的是极端条件下的复杂度，发生的概率不大，不能代表平均水平。那么为了更好的表示平均情况下的算法复杂度，就需要引入平均时间复杂度。

平均情况时间复杂度可用代码在所有可能情况下执行次数的加权平均值表示.

还是以 find 函数为例，从概率的角度看， x 在数组中每一个位置的可能性是相同的，为 1 / n。那么，那么平均情况时间复杂度就可以用下面的方式计算：

1	((1 + 2 + … + n) / n + n) / 2 = (3n + 1) / 4

find 函数的平均时间复杂度为 O(n)。

均摊复杂度分析

public class MyVector<T> {
    /**
     * 需要存储的数据
     */
    private Object[] data;

    /**
     * 存储数组中的元素个数
     */
    private int size;
    /**
     * 存储数组中可以容纳的最大的元素个数
     */
    private int capacity;

    public MyVector() {
        data = new Object[100];
        size = 0;
        this.capacity = 100;
    }

    private void resize(int newCapacity){
        Object[] newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, capacity);
        data = newData;
        capacity = newCapacity;
    }
    //平均复杂度为 O(1)
    public void push(T o){
        if(size == capacity){
            resize(capacity*2);
        }
        data[size++] = o;
    }
    //平均复杂度为 O(1)
    public T pop(){
        if (size < 0){
            throw new OutputLengthException("已经没有数据");
        }
        return (T) data[--size];
    }

    public static void main(String[] args) {
        MyVector<Integer> myVector = new MyVector<>();
        for(int i = 0 ; i < 200; i++){
            myVector.push(i);
        }
        while (myVector.getSize() >0){
            System.out.println(myVector.pop());
        }
    }
}

push实现的功能是往数组的末尾增加一个元素，如果数组没有满，直接往后面插入元素；如果数组满了，即 size == capacity ，则将数组扩容一倍，然后再插入元素。

例如，数组长度为 n，则前 n 次调用 push 复杂度都为 O(1) 级别；在第 n + 1 次则需要先进行 n 次元素转移操作，然后再进行 1 次插入操作，复杂度为 O(n)。

因此，平均来看：对于容量为 n 的动态数组，前面添加元素需要消耗了 1 * n 的时间，扩容操作消耗 n 时间，总共就是 2 * n 的时间，因此均摊时间复杂度为 O(2n / n) = O(2)，也就是 O(1) 级别了。

可以得出一个比较有意思的结论：一个相对比较耗时的操作，如果能保证它不会每次都被触发，那么这个相对比较耗时的操作，它所相应的时间是可以分摊到其它的操作中来的。

空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

程序执行时所需存储空间包括以下两部分：

固定部分

这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

可变空间

这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

空间复杂度可以理解为除了原始序列大小的内存，在算法过程中用到的额外的存储空间。

空间复杂度和时间复杂度之间的关系

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。

空间换时间的概念

当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；
反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。