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

36次阅读

共计 680 个字符,预计需要花费 2 分钟才能阅读完成。

工夫复杂度

原文链接: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

正文完
 0