# 复杂度

# 时间复杂度

# O(n)

只关注循环执行次数最多的一段代码

单段代码看高频：比如循环。

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

执行次数最多的是 for 循环及里面的代码，执行了 n 次，所以时间复杂度为 O(n)。

# O(n2)

加法法则：总复杂度等于量级最大的那段代码的复杂度

多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。

function cal(n) {
   let sum_1 = 0;
   let p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   let sum_2 = 0;
   let q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   let sum_3 = 0;
   let i = 1;
   let j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

上面代码分为三部分，分别求 sum_1、sum_2、sum_3 ，主要看循环部分。

第一部分，求 sum_1 ，明确知道执行了 100 次，而和 n 的规模无关，是个常量的执行时间，不能反映增长变化趋势，所以时间复杂度为 O(1)。

第二和第三部分，求 sum_2 和 sum_3 ，时间复杂度是和 n 的规模有关的，为别为 O(n) 和 O(n2)。

所以，取三段代码的最大量级，上面例子的最终的时间复杂度为 O(n2)。

同理类推，如果有 3 层 for 循环，那么时间复杂度为 O(n3)，4 层就是 O(n4)。

所以，总的时间复杂度就等于量级最大的那段代码的时间复杂度。

# O(n2)

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

嵌套代码求乘积：比如递归、多重循环等。

function cal(n) {
   let ret = 0; 
   let i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i); // 重点为  f(i)
   } 
 } 
 
function f(n) {
  let sum = 0;
  let i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

方法 cal 循环里面调用 f 方法，而 f 方法里面也有循环。

所以，整个 cal() 函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2) 。

# O(m+n)

多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

function cal(m, n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

以上代码也是求和 ，求 sum_1 的数据规模为 m、求 sum_2 的数据规模为 n，所以时间复杂度为 O(m+n)。

公式：T1(m) + T2(n) = O(f(m) + g(n)) 。

# O(m*n)

多个规模求乘法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相乘

function cal(m, n) {
  let sum_3 = 0;
   let i = 1;
   let j = 1;
   for (; i <= m; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
}

以上代码也是求和，两层 for 循环 ，求 sum_3 的数据规模为 m 和 n，所以时间复杂度为 O(m*n)。

公式：T1(m) * T2(n) = O(f(m) * g(n)) 。

# O(logn)

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。

let i=1;
while (i <= n)  {
   i = i * 2;
}

代码是从 1 开始，每次循环就乘以 2，当大于 n 时，循环结束。

其实就是高中学过的等比数列，i 的取值就是一个等比数列。在数学里面是这样子的：

20 21 22 ... 2k ... 2x = n

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了，通过 2x = n 求解 x，数学中求解得 x = log2n 。所以上面代码的时间复杂度为 O(log2n)。

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？

因为对数之间是可以互相转换的，log3n = log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。

由于 时间复杂度 描述的是算法执行时间与数据规模的 增长变化趋势，所以 常量、低阶、系数 实际上对这种增长趋势不产生决定性影响，所以在做时间复杂度分析时 忽略 这些项。

因此，在对数阶时间复杂度的表示方法里，我们忽略对数的 “底”，统一表示为 O(logn)。

# O(nlogn)

function aFun(n){
  let i = 1;
  while (i <= n)  {
     i = i * 2;
  }
  return i
}

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

aFun 的时间复杂度为 O(logn)，而 cal 的时间复杂度为 O(n)，所以上面代码的时间复杂度为 T(n) = T1(logn) * T2(n) = O(logn*n) = O(nlogn) 。

# O(2n)

aFunc( n ) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

排序算法