复杂度分析笔记

常见复杂度

• ：常数复杂度
• ：对数复杂度
• ：线性时间复杂度
• ：线性对数复杂度
• ：平方阶
• ：立方
• ：K次方阶
• ：指数阶
• ：阶乘

注意：一般只看最高阶复杂度的运算

如何计算复杂度

var n = 1000
console.log("n=",n)

var n = 1000
console.log("1、n=",n)
console.log("2、n=",2*n)
console.log("3、n=",3*n)

时间复杂度为

var sum = 0
for(var i=1;i<=n;i++){
    sum = sum + i
}

时间复杂度为

for(var i=1;i<=n;i++){
  for(var j=1;j<=n;j++){
        console.log(`i=${i},j=${j}`)
  }
}

时间复杂度为

for(var i=1;i<=n;i = i*2){
    console.log('i=',i)
}

时间复杂度为

变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于等于 n 时，循环结束。

实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的

只要知道 x 值是多少，就知道这行代码执行的次数。通过 求解得

所以这段代码的时间复杂度就是

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为

因为对数之间是可以互相转换的， 就等于 ，所以 ，其中 是一个常量。在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))

记为

function fibonaccii(n) {
   if (n < 2) {
      return n
   }
   return fibonaccii(n - 2) + fibonaccii(n - 1);
 }

image

时间复杂度为

image

图中可以看出，较优的时间复杂度是和，以上的都不可取

🌰累加求和

//循环累加法
var sum = 0
for(var i=1;i<=n;i++){
    sum = sum + i
}

时间复杂度为

//等差数列求和
var sum = n(n+1)/2

注意：时间复杂度不是而是(1)

空间复杂度

1、数组的长度，有数组就看数组长度，一维，二维

2、递归的深度，递归深度

总结

1、常见时间复杂度有 、、、，只看最高阶，忽略常数项；

2、常见空间复杂度有，数组长度、递归深度；

3、递归的时间复杂度可以用递归状态树来计算，空间复杂度看深度。