算法复杂度

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，时间复杂度表示执行的快慢，空间复杂度表示执行的消耗

时间复杂度

• 只关注循环执行最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度。
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

• 常见时间复杂度分析

  • O(1) 常数阶

  • O(logn) 对数阶, O(nlogn)

    function total1(n) {
      var sum = 0;
      var i = 1;
      while (i <= n) {
        sum += i;
        i = i * 2;
      }
    }
    function total2(n) {
      var sum = 0;
      for (var i = 1; i <= n; i = i * 2) {
        sum += i;
      }
    }
    
    2^x = n, x = log2n, O(log2n)

  • O(m+n), O(m*n)

操作数量事例	大O表示法	术语
10	O(1)	常数阶
2logn	O(logn)	对数阶
3n+5	O(n)	线性阶
5n^2 + 2n	O(n^2)	平方阶
2^n+1	O(2^n)	指数阶
n!+3	O(n!)	阶乘阶

空间复杂度

表示算法的存储空间和数据规模的关系。

• 常见的只有O(1), O(n), O(n^2)

思考题

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

此函数时间复杂度为O(n)，怎么降为O(1)

function total(n){
    return n * (n + 1) / 2;
}