复杂度分析

拥有对程序复杂度分析能力，提升程序和算法的性能

学习数据结构前先要理解时间复杂度和空间复杂度；算法所追求的就是 所需运行时间更少（时间复杂度更低）、占用内存空间更小（空间复杂度更低）。所以需要进行算法分析，就是从运行时间情况、空间使用情况两方面对算法进行分析

时间复杂度：算法运行所需要花费的时间，可以记作为T(n)。时间复杂度描述了算法的运行时间随着输入规模的增长而变化的趋势，它衡量了算法的执行效率

空间复杂度：算法所占用的空间大小，可以记作为S(n)。空间复杂度描述了算法在执行过程中所需要的内存空间随着输入规模的增长而变化的趋势

常数阶 O(1)

如下代码共有三行，每行代码都是只执行一次，因此这段代码的运行次数函数是f(n)=3。那么，按照大O记法，其时间复杂度是不是要记作T(n)=O(3)呢？

public void sum(int n) {
    int sum = 0; // 执行一次
    sum = n*2; // 执行一次
    System.out.println(sum); // 执行一次
}

不是的，原因是大O记法中，有一个基本法则：用常数1取代运行时间中的所有加法常数。因此，这段代码的时间复杂度是T(n)=O(1)。

一般来说，对于这种与问题规模n无关，执行时间恒定的算法，其时间复杂度都记作O(1)，又称之为常数阶。

对数阶 O(logn)

如下代码所示，其时间复杂度是多少呢？

public void logarithm(int n) {
    int count = 1; // 执行一次
    while (count <= n) { // 执行logn次
        count = count*2; // 执行logn次
    }
}

该段代码什么时候会停止执行呢？是当count大于n时。也就是说多少个2相乘后其结果值会大于n，即2^x=n。由2x=n可以得到x=logn，所以这段代码时间复杂度是O(logn)。

线性阶 O(n)

线性阶表示代码要执行n次，如下for循环中的代码，第二行和第三行代码都执行n次，即f(n)=2n。根据前面的分析，与最高次项相乘的常数2是可以忽略的，因此这段代码的时间复杂度是O(n)。

public void circle(int n) {
    for(int i = 0; i < n; i++) { // 执行n次
        System.out.println(i); // 执行n次
    }
}

线性对数阶 O(nlogn)

线性对数阶O(nlogn)就是将一段时间复杂度为O(logn)的代码执行n次，如下代码所示。

public void logarithm(int n) {
    int count = 1;
    for(int i = 0; i < n; i++) { // 执行n次
        while (count <= n) { // 执行logn次
            count = count*2; // 执行nlogn次
        }
    }
}

平方阶 O(n²)

如下代码是个双重for循环，其内循环的时间复杂度是线性阶O(n)。对于外循环来说，是将内循环这个时间复杂度为O(n)代码在执行n次，所以整个这段代码的时间复杂度为O(n²)。

public void square(int n) {
    for(int i = 0; i < n; i++){ // 执行n次
        for(int j = 0; j <n; j++) { // 执行n次
            System.out.println(i+j); // 执行n方次
        }
    }
}

当内层循环和外层循环的次数不一致时，时间复杂度又该怎么表示呢？如下，内层循环执行m次，其时间复杂度为O(m)，外层循环执行次数为n次，其时间复杂度为O(m)。整段代码的时间复杂度是就是O(m*n)，即循环的时间复杂度等于循环体的时间复杂度乘以该循环运行次数。

public void square(int n, int m) {
    for(int i = 0; i < n; i++){ // 执行n次
        for(int j = 0; j <m; j++) { // 执行m次
            System.out.println(i+j); // 执行mn次
        }
    }
}

对于上述这些常见时间复杂度，它们的执行次数T(n)和问题规模n的关系如下图：

4、最好、最坏、平均情况时间复杂度

我们以判断一个目标值在数组中是否存在为例来看一下如何进行最好、最坏、平均情况时间复杂度的分析。我们假设目标值在数组中要么唯一存在要么不存在，代码如下：

public boolean exist(int target, int[] arr) {
    boolean exist = false; // 执行一次
    int n = arr.length; // 执行一次
    for(int i = 0; i < n; i++) { // 执行n次
        if (arr[i] == target) { // 执行n次
            exist= true; // 执行一次
        }
    }
    return exist; // 执行一次
}

对于上述代码其总执行次数f(n)=2n+4，即其时间复杂度用大O记法表示是T(n)=O(2n+4)，根据之前的分析加法常数项和最高次项的常数项都可以忽略，因此T(n)=O(n)。

对于上述代码来说，由于已经假定目标值是唯一存在的，因此当在数组中找到目标值时，其后剩余元素就不用继续考察了。优化后的代码如下：

public boolean exist(int target, int[] arr) {
    boolean exist = false; // 执行一次
    int n = arr.length; // 执行一次
    for(int i = 0; i < n; i++) { // 还是执行n次吗
        if (arr[i] == target) { // 还是执行n次吗
            exist= true; // 执行一次
            break;
        }
    }
    return exist; // 执行一次
}

对于优化后的代码来说，第四行和第五行不一定会执行n次。这时，上述的时间复杂度分析就不适用于这种情况了。

如果目标值存在于数组中第一个位置，那么数组中剩余元素就不用考虑了，因此上述代码的时间复杂度是O(1)。对于这种最理想情况的时间复杂度我们称之为最好情况时间复杂度。

如果目标值存在于数组中最后一个位置，那么数组中的每个元素都需要和目标值进行比较，因此上述代码的时间复杂度是O(n)。对于这种最坏情况下的时间复杂度我们称之为最坏情况时间复杂度。

但是，不论是最好情况还是最坏情况，都是极端情况下才会发生的，因此为了更好的表示一个算法的时间复杂度，我们需要引入平均情况时间复杂度。

还是以上述优化后的代码为例看下如何进行平均情况时间复杂度计算。目标值在数组中和目标值不在数组中是两个基本情况，当目标值在数组中时，其可能在数组中的任意位置，即对于判断目标值是否在数组中这个算法来说一共有n+1中情况。

我们把这n+1种情况下需要考察数组中的元素个数加起来在除以n+1，就可以得到一个平均情况时间复杂度，即：

5、均摊时间复杂度

之前介绍的复杂度分析是基于一个算法从头运行到尾，我们来看其时间复杂度是怎么样的。有时，会出现一个算法的复杂度比较高，但是该算法是和其它操作是一起的，在将这个较高复杂度的算法和其它操作一起进行复杂度分析时，需要将其均摊到其它操作上，这种分析称之为均摊复杂度分析。

我们以如下代码来看下如何进行均摊复杂度分析。

public class MyVector {

    private int[] data;
    private int size; // 数组中已存储的元素格式
    private int capacity; // 数组中可容纳的最大元素个数

    public MyVector() {
        data = new int[10];
        size= 0;
        capacity = 10;
    }

    // 向数组末尾添加元素
    public void pushBack(int e) {
        // 如果原有数组已满，则扩容为原数组的2倍
        if (size == capacity) {
            resize(2*capacity);
        }
        data[size++] = e;
    }

    public void resize(int newCapacity) {
        if (newCapacity < size) {
            return;
        }
        int[] newData = new int[newCapacity];
        // 把原有数组中的元素一次复制到新的数组中
        for(int i = 0; i < size; i++) {
            newData[i] = data[i];
        }

        data = newData;
        capacity = newCapacity;
    }
}

上述代码中的pushBack方法是每次向数组末尾添加一个元素，然后当数组满时，进行扩容，扩容为原有数组的2倍；resize方法是用于扩容的，所谓的扩容就是新开辟一个容量大小为newCapacity的数组，然后将原数组的元素依次复制到新数组中。根据之前对时间复杂度的分析，resize方法的时间复杂度T(n)=O(n)。

接着看下pushBack方法的时间复杂度。对于pushBack这个方法来说，其中有两个操作，一个是向数组末尾添加元素，每次执行添加操作时，时间复杂度是O(1)；一个是扩容，每次扩容的时间复杂度是O(n)。那么，pushBack方法的时间复杂度是O(n)吗？

扩容这一步，是在数组满的情况下才会触发执行，也就是在扩容之前，会有n次向数组末尾添加元素的操作，且每次操作耗时是1，总耗时为n。扩容操作在数组满时触发一次，耗时是n，即将数组添加满并进行扩容总共需要n+1次操作，这些操作总耗时是2n。

因此，在将扩容这个操作的耗时均摊到之前每次添加元素到数组末尾这个操作上时，每次操作耗时约为2，即将数组添加满并进行扩容操作，其时间复杂度不是O(n)，而是O(1)。这种时间复杂度分析的方法，称之为均摊时间复杂度分析。

6、空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。

常数 O(1)

void algorithm(n) {
    int a = 1, b = 2;
    res = a * b + n;
    return res;
}

线性 O(n)

int algorithm(n) {
    if n <= 0
        return 1
    return n * algorithm(n - 1);
}

上述代码采用了递归调用的方式。每次递归调用都占用了 1 个栈帧空间，总共调用了 n 次，所以该算法的空间复杂度为 O(n)

总结

算法复杂度 包括 时间复杂度 和 空间复杂度，用来分析算法执行效率与输入问题规模 n 的增长关系。通常采用 「渐进符号」 的形式来表示算法复杂度。

常见的时间复杂度有：O(1)、O(log⁡n)、O(n)、O(n×log⁡n)、O(n^2)、O(n3)、O(2^n)、O(n!)。

常见的空间复杂度有：O(1)、O(log⁡n)、O(n)、O(n^2)