我们之所以做复杂度分析是为了表示算法的性能。复杂度描述的是随着数据规模n的增大，算法性能的变化趋势。

时间复杂度

常见的时间复杂度

这里我们举例来说明各种常见的时间复杂度，因为只是简单的罗列出来并不利于理解。

1. O(n)

求依次输出一维数组中的元素的时间复杂度。

function getRes(arr) {
  for (let i = 0, len = arr.length; i < len; i++) {
    console.log(arr[i])
  }
}

解析：只需要循环遍历逐一输出即可，假设数组的长度为n，此时的时间复杂度为O(n)。

2. O(n^2)

求遍历一个n*n的二维数组的时间复杂度。

function getRes(arr) {
  for (let i = 0, len = arr.length; i < n; i++) {
    for (let j = 0; j < len; j++) {
      console.log(arr[i][j])
    }
  }
}

解析：第一次和第二层循环总共执行了n*n次，所以这个算法的时间复杂度为 O(n^2)

3. O(2^n)

求长度为n的二进制数字

解析：长度为n的二进制数字相当于有n个位置，每个位置后者填0或者填1。也就是每个位置有两种选择，现在我们有n个位置，每个位置都要填0或者填1，相当于是n个2乘起来，所以这个算法的时间复杂度为O(2^n)

4. O(n!)

求长度为n的数组的所有排列的时间复杂度。

解析：由全排列公式f(n)=n!(定义0!=1)，所有排列的个数为n!，所以这个算法的时间复杂度为O(n!)

5. O(logn)

求数字n的二进制位数是多少

function getRes(n) {
  if (isNaN(n)) return
  let res = ''
  while(n) {
    res += n % 2
    n = parseInt(n / 2)
  }
  return res.split('').reverse().join('')
}

getRes(3)

解析：因为每次while循环n都是除以2的，所以这个算法的时间复杂度为O(logn)

JS将一个数表示为二进制还有个更简单的方法：

console.log(100 .toString(2))

6. O(√n)

求数字n的所有约数

function getRes(n) {
  for(let i = 1; i * i <= n; i++)
    if (n % i == 0) console.log(`数字${n}的约数为`,i, n / i)
}

getRes(10)

解析：如果一个数字是n的约数就代表n可以整除这个数字，但是注意一个数字的约数总是成对出现的，所以我们实际需要需要的并不是n次，所以这个算法时间复杂度为O(√n)

7. O(1)

判断数字n是否是偶数

function isEven(n) {
  return n % 2 == 0
}

解析：可以看出判断一个数是否是偶数核心代码只需要一步和n的大小无关，所以这个算法的时间复杂度为O(1)

常见时间复杂度从小到大的排序：

O(1) < O(logn) < O(√n) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它是内存增长的趋势。

通常在算法设计的时候更强调时间复杂度，是因为对于现在的计算机来说存储空间越来越大，很多时候是用空间换时间。