什么是时间复杂度?
定性描述该算法的运行时间,一个函数、用大 O 表示,例如 O (1)、 O (n)、O (logN) ...
上面从上至下依次的时间复杂度越来越大,执行的效率越来越低。
坐标图如下
O(1)
当每次该文件执行的时候,以下代码永远只会执行一次。
javascript
let i = 0
i += 1
O(n)
这是一个循环语句,循环体内的代码会执行 n 次。
javascript
for (let i = 0; i < n; i++) {
console.log(i)
}
O(1) + O(n) = O(n)
当两个时间复杂度的代码在一块时,以时间复杂度较大的为准,当 n 足够大的时候,1 可以忽略不计。
javascript
let i = 0
i += 1
for (let i = 0; i < n; i++) {
console.log(i)
}
O(n) * O(n) = O(n ^ 2)
当遇到嵌套 for 循环时,两个时间复杂进行相乘,得到的结果就是真实的时间复杂度。当时间复杂度进行相加时,却可以忽略不计。
javascript
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 。
javascript
let i = 1
while (i < n) {
console.log(i)
i *= 2
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。