算法的时间复杂度

[reng99]

前言

作为一个非典型的前端开发人员，我们要懂得一些算法的概念，并将其理论知识引入日常的开发中，提高日常的开发效率和提升产品的体验。

本篇博文的概念偏多，模糊的点，有兴趣的谷歌起来啦！

相关概念

算法： 算法是指解题方案的准确而完整的描述，是一系列解决问腿的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法的效率： 是指算法执行的时间，算法执行时间需要通过算法编制的程序在计算机上运行时所消耗的时间来衡量。

一个算法的优劣可以用空间复杂度和时间复杂度来衡量。

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。

空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

算法设计时，时间复杂要比空间复杂度更容易复杂，所以本博文也在标题指明讨论的是时间复杂度。一般情况下，没有特殊说明，复杂度就是指时间复杂度。

时间频度： 一个算法中的语句执行次数称为语句频度或时间频度。

一个算法执行所消耗的时间，从理论上是不能算出来的，必须上机测试才知道。但我们不可能也没有必要对每个算法都上机测试，只需要知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句执行次数成正比例，哪个算法中执行语句次数多，它话费的时间就多。

时间复杂度： 执行程序所需的时间。（上面提到了）

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

在 T(n)=4nn-2n+2 中，就有f(n)=nn，使得T(n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n*n)

大O表示法： 算法的时间复杂度通常用大O符号表述，定义为T(n)=O(f(n))【上面有提到并举例】。

T(n) = O(f(n))称函数T(n)以f(n)为界或称T(n)受限于f(n)。如果一个问题的规模是n，解决一问题的某一算法所需要的时间为T(n)。

【注】时间复杂度和时间复杂度虽然在概念上有所区别，但是在某种情况下，可以认为两者是等价的或者是约等价的。

大O阶推导

推导大O阶就是将算法的所有步骤转换为代数项，然后排除不会对问题的整体复杂度产生较大影响的较低阶常数和系数。

有条理的说，推导大O阶，按照下面的三个规则来推导，得到的结果就是大O表示法：

1. 运行时间中所有的加减法常数用常数1代替
2. 只保留最高阶项
3. 去除最高项常数

先来看下图，对各个时间复杂度认下脸：

O(1)常数阶

let sum = 0,
    n = 100; // 执行一次
sum = (1+n)*n/2; // 执行一次
console.log(sum); // 执行一次 

上面算法的运行次数的函数是f(n)=3，则有O(f(n) = 3)即O(3)， 常数项用常数1表示，则最终的表示法为O(1)，我们称之为常数阶。

O(n)线性阶

线性阶主要分析循环结构的运行情况，如下：

for(let i = 0; i < n; i++){
    // 时间复杂度O(1)的算法
    ...
}

上面算法循环体中的代码执行了n次，因此时间复杂度是O(n)。

O(logn)对数阶

let number = 1;
while(number < n){
    number = number*2;
    // 时间复杂度O(1)的算法
    ...
}

上面的代码，随着number每次乘以2后，都会越来约接近n，当number不小于n时候就会退出循环。假设循环的次数为x，则由2^x=n得出x=log₂n，因此得到这个算法的时间复杂度为O(logn)。

O(n²)平方阶

平凡阶一般出现在嵌套的循环中，如下：

for(let i=0; i<n; i++){
    for(let j=i; j<n; j++){
        // 时间复杂度O(1)的算法
        ...
    }
}

上面的代码中，内循环的中是j=i。具体的算法过程如下：

n+(n-1)+(n-2)+(n-3)+……+1
=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
=(n+1)+(n+1)+(n+1)+(n+1)+……
=(n+1)n/2
=n(n+1)/2
=n²/2+n/2

根据上面说的推导大O阶的规则，得到上面这段代码的时间复杂度是O(n²)

其他常见复杂度

f(n)=nlogn时，时间复杂度为O(nlogn)，可以称为nlogn阶。

f(n)=n³时，时间复杂度为O(n³)，可以称为立方阶。

f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。

f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。

f(n)=(√n时，时间复杂度为O(√n)，可以称为平方根阶。

时间复杂度比较

嗯，我们再回头看下下面的图片：

通过图片直观的体现，能够得到常用的时间复杂度按照消耗时间的大小从小到大排序依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

参考

http://bigocheatsheet.com/

刘望舒 -- https://juejin.im/post/5bbd79a0f265da0aa74f46a6

李斌 -- https://zhuanlan.zhihu.com/p/32135157

O(log n) 怎么算出来的 -- https://www.jianshu.com/p/7b2082df8968

[TBLGSn]

【注】时间复杂度和时间复杂度虽然在概念上有所区别，但是在某种情况下，可以认为两者是等价的或者是

这里表述存在错误
@reng99