关于前端:什么是时间复杂度

工夫复杂度

原文链接：https://note.noxussj.top/?source=sifo

什么是工夫复杂度？

定性描述该算法的运行工夫，一个函数、用大 O 示意，例如 O (1)、O (n)、O (logN) …

常见的工夫复杂度量级

• 常数阶 O (1)
• 对数阶 O (logN)
• 线性阶 O (n)
• 线性对数阶 O (nlogN)
• 平方阶 O (n²)
• 立方阶 O (n)
• K 次方阶 O (n ^ k)
• 指数阶 (2 ^ n)

下面从上至下顺次的工夫复杂度越来越大，执行的效率越来越低。

坐标图如下

根底案例

O(1)

当每次该文件执行的时候，以下代码永远只会执行一次。

    let i = 0

    i += 1

O(n)

这是一个循环语句，循环体内的代码会执行 n 次。

    for (let i = 0; i < n; i++) {console.log(i)
    }

O(1) + O(n) = O(n)

当两个工夫复杂度的代码在一块时，以工夫复杂度较大的为准，当 n 足够大的时候，1 能够忽略不计。

    let i = 0

    i += 1

    for (let i = 0; i < n; i++) {console.log(i)
    }

O(n) * O(n) = O(n ^ 2)

当遇到嵌套 for 循环时，两个工夫简单进行相乘，失去的后果就是实在的工夫复杂度。当工夫复杂度进行相加时，却能够忽略不计。

    for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {console.log(i, j)
        }
    }

O(logN)

log 个别都是以 2 为底，能够不写。log 称为对数，个别是求 2 的多少次方为 n。

    let i = 1

    while (i < n) {console.log(i)
        i *= 2
    }

原文链接：https://note.noxussj.top/?source=sifo