前端JS 时间复杂度和空间复杂度

时间复杂度 BigO

算法的时间复杂度通常用大 O 符号表述，定义为 T(n) = O(f(n))
实际就是计算当一个一个问题量级（n）增加的时候，时间T增加的一个趋势
T(n)：时间的复杂度，也就相当于所消耗的时长
O：表示正比例关系
f(n)：代码执行的次数

f(n) 可以有的值：复杂度由简单到复杂

1.常数型 O(1)
2.对数型 O(log n)
3.线性型 O(n)
4.线性对数型 O(nlogn)
5.平方型 O(n^2)、立方型 O(n^3)、K 次方型 O(n^k)
6.平方底指数型 O(2^n)、立方底指数型 O(3^n)、K 次底指数型 O(k^n)
7.阶乘型 O(n!)

在这里插入图片描述

常数型 O(1)

只要没有循环或递归等复杂逻辑，无论代码执行多少行，代码复杂度都为O(1)，如下：
  1.function sum() {
	  const a = 1;
	  const b = 2;
	  return a + b;
	}
  2.int x = 0;
	int y = 1;
	int temp = x;
	x = y;
	y = temp;
上述代码在执行的时候，所消耗的时间不会随着特定变量的增长而增长，即使有几万行这样的代码，我们都可以用O(1)来表示它的时间复杂度。

对数型 O(log n)

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

在上面的循环中，每次i都会被乘以2，也意味着每次 i 都离 n 更进一步。那需要多少次循环 i 才能等于或大于 n 呢，也就是求解：2^x =n，答案x=log2^n。也就是说循环 log2^n次之后，i会大于等于n，这段代码就结束了。所以此代码的复杂度为：O(logN)。
3. 线性阶O(n)

function fun(n) {
  let sum = 0;
  for (let i = 0; i < n.length; i++) {
    sum += n[i];
  }
  return sum;
}

在这段代码中，for循环会执行n遍，因此计算消耗的时间是随着n的变化而变化，因此这类代码都可以用O(n)来表示其时间复杂度。
4. 线性对数阶O(nlogN)

线性对数阶O(nlogN)很好理解，也就是将复杂度为O(logN)的代码循环n遍：
function fun(n) {
  for (let j = 0; j < n; j++) {
    let i = 1;
    while (i < n) {
      i = i * 2;
    }
  }
}
因为每次循环的复杂度为O(logN)，所以n * logN = O(nlogN)

平方型 O(n^2)、立方型 O(n^3)、K 次方型 O(n^k)

O(n²)就是将循环次数为n的代码再循环n遍：
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        x++;
    }
}
O(n²)的本质就是n * n，如果我们将内层的循环次数改为m,复杂度就变为 n * m = O(n * m)
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        x++;
    }
}
O(n^3)就是将循环次数为n的代码再循环3遍：
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
         for (int j = 1; j <= n; j++) {
	        x++;
	    }
    }
}
O(n^k)就是将循环次数为n的代码再循环k遍：

平方底指数型 O(2^n)

斐波那契，使用递归的情况下，因为使用了两次递归，时间复杂度为 O(2^n) 
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

阶乘型 O(n!)

下例，时间复杂度为 O(n!)，基本不能称作为算法，n 越大，就容易卡死，小心尝试
function fun(n) {
  console.log(n);
  for (let i = 0; i < n; i++) {
    fun(n - 1);
  }
}

空间复杂度

算法的空间复杂度指的是在运行过程中临时占用的存储空间大小的量度
空间复杂度常见的为以下三个例子：

空间复杂度O(1)

所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
function sum() {
  const a = 1;
  const b = 2;
  return a + b;
}

空间复杂度O(n)

下例，定义一个数组的空间，数组的长度随着 n 的规模不同，会不一样，这里空间复杂度为 O(n)
function fun(n) {
  let arr = [];
  for (let i = 0; i < n.length; i++) {
    arr.push(n[i]);
  }
  return arr;
}

空间复杂度O(n^2)

下例，最终形成一个二维数组的空间，空间复杂度为 O(n^2)
function fun(n) {
  const arr = [];
  for (let i = 0; i < n; i += 1) {
    arr.push([]);
    for (let j = 0; j < n; j += 1) {
      arr[i].push(j);
    }
  }
}