算法复杂度

基本概念

算法复杂度讨论的是数据规模趋于无穷大时的情况，所以也称渐进复杂度。渐进复杂度分时间渐进复杂度、空间渐进复杂度，简称时间复杂度、空间复杂度。由于在不同的硬件、操作系统、语言平台等条件下运行同一个算法总能得到不同的时间、内存消耗，所以，时间、空间复杂度描述的并不是程序运行具体所消耗的时间、内存，而是描述执行基本操作的次数、所需额外空间的大小。一般来说，影响算法复杂度的因素主要有以下两方面：

输入数据的状态。（比如排序有序数组，时间消耗很少）
输入数据的规模。（比如排序10、100000个元素，相同算法的时间差别会很大）

意义

程序除了要确保能正常运行，还要争取用尽量短的运行时间、尽量少的运行空间，达到预期效果。实际应用中，往往涉及相当大量的数据处理，随着数据规模的增大，基于不同算法的程序在解决同意问题时所需的运行时间、硬件资源会大不相同，有的可能只要几秒，有的却要几天，这时，对算法复杂度的分析就尤为重要。

通过对算法时间、空间复杂度进行分析，得出不同算法的各个特征值，是衡量、筛选有序算法的必要条件。根据算法的各个特征值，使我们能够定量的预测某个算法在解决某个问题时，将需要消耗多少时间、空间等资源，而不要每次都去实际运行测量，有助于我们在不同场景下快速选择出最合适的算法。

大O表示法

大O表示法是渐进复杂度的表示方法，时间复杂度T(n) = O(f(n))，空间复杂度S(n) = O(f(n))，其中n代表的便是数据的规模，如果随着n的增大，T(n)、S(n)增长的越慢，算法就越优秀。由于讨论的是数据规模趋于无穷大时的情况，所以渐进复杂度并不是一种精确描述，它所关注的点在数量级的层面上，故两三倍的误差一般不在考虑范围内。下面是一些由低到高排列的常见值：

复杂度	阶级
O(1)	常数阶
O(logn)	对数阶
O(n)	线性阶
O(nlogn)	nlongn阶
O(n^2)	平方阶
O(n^3)	立方阶
O(n^k)	k次方阶
O(2^n)	指数阶
O(n!)	阶乘阶
O(n^n)	无

算法复杂度关系为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)

指数时间算法复杂度关系为：

O(2n) < O(n!)< O(nn)

函数图：

通常复杂度超过O(n^3)的算法就不再具有应用价值了，因为这是即使很小的数据规模也会带来很大的消耗，比如O(2^n)的算法在100的数据规模下资源消耗达到2^100，在绝大多数情况下，无论是时间还是空间，都是令人无法接受的数字。

算法分析的种类

根据输入数据的初始状态不同，算法分析由三种情况：最坏情况、平均情况、最佳情况。

最坏情况：在当前输入规模下，是算法有最大运行时间、空间的数据状态。
平均情况：在当前输入规模下，算法在随机数据状态下的平均运行时间、空间，可以理解位算法复杂度的数学期望。
最佳情况：在当前输入规模下，使算法有最小运行时间、空间的数据状态，比如排序时，输入数据本身就是有序的。

对算法复杂度分析来说，通常讨论的都是最坏情况，但平均情况时最具实际意义的，最坏情况能保证算法在一定数据规模下，消耗保持在可忍受范围内，而平均情况是预测算法真正运行时资源开销的主要指标，不过很多算法的平均情况通常难以计算，经常只能通过不断运行测量、统计才能得出平均情况下的复杂度。

算法复杂度计算

时间复杂度

首先，时间复杂度计算的是算法执行基本操作的次数。计算方法是：找出算法的基本语句（增长最长的项），展开计算，仅保留最高项，系数化为1。

举个例子：

function bubbleSort(nums: number[]) {
    let i, j, temp;
    let len = nums.length;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1; j++) {
            if (nums[j] > nums[j + 1]) {        // 基本语句
                temp = nums[j + 1];             // 基本语句
                nums[j + 1] = nums[j];          // 基本语句
                nums[j] = temp                  // 基本语句
            }
        }
    }
}

数据规模n等于数组长度，基本语句是增长最快的项，对这个算法来说就是循环内层的四句，其语句执行次数是4(n-1)(n(n-1)/2)，展开后仅保留最高项，得到f(n)=4n^2，将系数化为1，便是T(n)=O(n^2)。

如果算法复杂度是个常数，即消耗时间、空间不随数据规模n的增大而变化，此类算法的复杂度是O(1)，比如高斯小时候计算1~100之和的算法：

function sum(a: number, b: number) {
    const result = (a + b) * (b - a + 1) / 2;
    return result;
}

该算法的时间复杂度是常数，无论数据规模b - a如何变化，执行的基本操作都只有一次，即f(n) = 1，所以T(n) = O(1)。

再看下从1累加到100的算法时间复杂度：

function sum(a: number, b: number) {
    let i, result = 0;
    for (i = a; i < b; i++) {
        result += i;
    }
    return result;
}

数据规模n同样是b - a，但执行的基本次数变成了n，所以f(n) = n，时间复杂度T(n) = O(n)，当数据规模很大时，这个算法跟高斯的算法在效率上会差好几个数量级。

再看个例子：

function find(nums: number[], target: number) {
    let len = nums.length;
    let l = 0, r = len - 1, mid = l + (r - 1) / 2;      //区间三点
    for (; mid !== l; mid = l + (r - 1) / 2) {
        if (nums[mid] === target) return mid;            // 找到
        else if (nums[l] === target) return l;           // 找到
        else if (nums[r] === target) return r;           // 找到
        else if (nums[mid] > target) r = mid;            // 中点偏大，更新右端点
        else if (nums[mid] < target) r = mid;            // 中点偏小，更新左端点
    }
    return -1;
}

这个是二分查找，二分查找的思路很简单，在一个有序序列内，每次将当前区间中、左、右三个端点与目标值进行比较，若相同便返回，若大于中间点便更新左端点，反之更新右端点，这样循环下去最终就能确定目标的位置。

假设数据规模为16，且每次循环时目标不在左、中、右三点上，且目标值大于中点，那么初始区间为[0,15]，第一次循环后为[7,15]，第二次循环后为[11,15],第三次循环后为[13,15]，第四次循环后为[14,15]，这时目标值就找出来了，共经过4次循环。

稍加思考可发现，最坏情况下共需要log(2)(n)次循环，比如上面就是log(2)(16) = 4，在复杂度分析中是比较常见的数字，通常可以直接写为logn。戒指，每次循环会进行四次比较，所以f(n) = 4 * logn，系数化为1后T(n) = O(logn)，所以二分查找的时间复杂度是O(logn)。

通常，计算时间复杂度，只需要关注最内层循环的语句，若存在递归，便再与递归次数相乘即可。

空间复杂度

算法执行期间所需要的存储空间一般包括三个部分：

算法程序所占空间。
输入的初始数据所占空间。
算法执行过程中所需要的额外空间。

空间复杂度描述的是算法在执行时所需要的额外空间，空间复杂度与时间复杂度的计算方法类似，只是计算换成了关注其在运行时产生的额外空间。

举个例子：

function demo(num: number) {
    if (num > 0 && num <= 2) return 1;
    else if (num < 0) return 0;
    return demo(num - 5);
}

如果输入数据规模是21，会进行4次递归，稍加推测，可以得到递归次数为num / 5，因为每次递归产生的额外空间是1，所以f(n) = n / 5，系数化为1，空间复杂度S(n) = O(n)。

如果一个算法产生的额外空间是常数或没有产生额外空间，则空间复杂度便是O(1)，没有产生额外空间或额外空间是很小的常数的算法又被称为原地算法。比如上面举例的冒泡排序、二分查找等就是原地算法，所有用递归实现的算法都不是原地算法。

附录

摘录：

参考：