简简单单

时间复杂度

 
  • 2018年 11月29日

时间复杂度

定义

时间复杂度表示的是 随着数据的增长，代码执行时间的变化趋势

大O表示法

function aaa (let n) {
    let sum = 0
    for (let i = 0; i < n; i++) {
        sum += i
    }
    return sum
}

假设每行代码执行的时间是一样的，我们称之为 one_timer,那么上述代码的第2行执行时间为1个one_timer, 3、4行分别执行n * one_timer, 所以总的时间为 T（n）（n+1）* one_timer, 由此可以得出结论， 代码执行行数与执行总时间成正比

即可以表示为 T(n) =O(f(n)) , O表示正比系数。

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码

    还是拿上边的代码举例子

    function aaa (let n) {
    let sum = 0
    for (let i = 0; i < n; i++) {
        sum += i
    }
    return sum
}

上述代码中，代码总共执行了 （n+1）次，当n无限大时， 1可以省略，所以他 的时间复杂度可以表示为 O(n)。

  1. 加法法则： 总复杂度等于量级最大的那段代码的复杂度

    function aaa (let n) {
    let a = 1
    for (let i = 0; i < 100; i++) {
        a++
    }
    for (let i = 0; i < n; i++) {
        a++
    }
    for (let i = 0； i < n; i++) {
        for (let j = 0; j < n; j++) {
            a++
        }
    }
}

    代码的第一个循环执行了100次，第二个循环执行了n次，第三个循环执行了n2

    次， 所以总的次数为100 + n + n2次，当n无限大时， 低阶和常量可以忽略掉，所以时间复杂度为 n2。

  2. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    function aaa (let n) {
    for (let i = 0; i < n; i++) {
    	bbb(i)    
    }
}
function bbb (let n) {
    for (let i = 0; i < n; i++) {
        // ...
    }
}

    第一个函数的时间复杂度为n,第二个函数的时间复杂度也是n, 但是aaa函数调用了bbb函数，函数发生了嵌套，此时执行次数最多为 n2,所以上述代码的时间复杂度为n2。

常见的时间复杂度分析

  1. O(1) 常量阶
  2. O(logn) 对数阶
  3. O(n) 线性阶
  4. O(nlogn) 线性对数阶
  5. O(n2), O(n3) … 平方阶，立方阶 …
  6. O(2n) 指数阶
  7. O(n!) 阶乘阶

上述7种时间复杂度可以分为两种，多项式量级 和非多项式量级， 6.7则属于非多项式量级，当n越大，代码执行时间飞速增长，所以， 6.7 是非常低效的。

  1. O(1)

    let a = 0
for (let i = 0; i < 100; i++) {
    a++
}

    循环执行次数为100次，与n无关，虽然它执行了100次，但是时间复杂度仍为O(1), 此处的1并不表示执行次数，而是代表一个常量。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行代码，它的时间复杂度仍然是O(1)

  2. O(logn)

    let i = 1
while (i <= n) {
    i = i * 2
}

    上面代码可以好好看一看，我们假设n为常量。一个一个的来。

    n 1 2 3 4 5 6 7 8
    执行情况 1*2=2 1x2=2 2x2=4 1x2=2 2x2=4 1x2=2 2x2=4 4x2=8 1x2=2 2x2=4 4x2=8 1x2=2 2x2=4 4x2=8 1x2=2 2x2=4 4x2=8 1x2=2 2x2=4 4x2=8 8x2=16
    执行次数 1 2 2 3 3 3 3 4

​ 不知道你有没有看出规律来，当n= 2/4/8/16时，满足2x-1=n, 所以执行次数为x= log2n+1,去掉常量, 则时间复杂度为为 O(log2n)。 实际上，不管是以2为底，还是以5为底，我们通通称之为logn

同理，nlogn 则是在线性事件复杂度的算法中嵌套一个对数复杂度

for (let i = 1； i < n;i++) {
    while (i <= n) {
        i = i*2
    }
}
搜索