如何判断一个算法的好坏

我们常常用时间复杂度和空间复杂度来判断一个算法的好坏。通俗的讲就是从执行时间和占用空间来看,执行时间越短，占用的内存空间越小，那么它就是好的算法。时间复杂度代表的就是执行时间，空间复杂度就是代表占用的内存空间。

什么是时间复杂度？

时间复杂度并不是计算程序具体运行的时间，它计算的是算法执行语句的次数。随着执行次数的不断增大，时间复杂度不断增大，算法花费时间越多。

常见的时间复杂度有

• 常数阶 O(1)
• 对数阶 O(log2 n)
• 线性阶 O(n)
• 线性对数阶 O(n log2 n)
• 平方阶 O(n^2)
• 立方阶 O(n^3)
• k 次方阶 O(n^K)
• 指数阶 O(2^n)

计算方法

1. 选取相对增长最高的项
2. 最高项系数是都化为 1
3. 若是常数的话用 O(1)表示；

通常呢，我们计算时间复杂度都是计算最坏情况。 举个例子：如 f(n)=3\*n^4+3n+300 则 O(n)=n^4`

计算时间复杂度的要注意的几个点

1. 如果算法的执行时间不随 n 的增加而增长，假如算法中有上千条语句，执行时间也不过是一个较大的常数。此类算法的时间复杂度是 O(1)。 举例如下：代码执行 100 次，是一个常数，复杂度也是 O(1)。

   let x = 1
   while (x < 100) {
     x++
   }

2. 有多个循环语句时候，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的方法决定的。举例如下：在下面 for 循环当中，外层循环每执行一次，内层循环要执行 n 次，执行次数是根据 n 所决定的，时间复杂度是 O(n^2)。

     for (i = 0; i < n; i++) {
       for (j = 0; j < n; j++) {
         // ...code
       }
     }

3. 循环不仅与 n 有关，还与执行循环判断条件有关。举例如下：在代码中，如果arr[i]不等于 1 的话，时间复杂度是O(n)。如果arr[i]等于 1 的话，循环不执行，时间复杂度是O(0)。

   for (var i = 0; i < n && arr[i] != 1; i++) {
     // ...code
   }

什么是空间复杂度？

空间复杂度是对一个算法在运行过程中临时占用存储空间的大小。

计算方法：

1. 忽略常数，用 O(1)表示
2. 递归算法的空间复杂度=(递归深度 n)*(每次递归所要的辅助空间)

计算空间复杂度的简单几点

1. 仅仅只复制单个变量，空间复杂度为 O(1)。举例如下：空间复杂度为 O(n) = O(1)。

   let a = 1
   let b = 2
   let c = 3
   console.log('输出a,b,c', a, b, c)

2. 递归实现，调用 fun 函数，每次都创建 1 个变量 k。调用 n 次，空间复杂度O(n*1) = O(n)。

   function fun(n) {
     let k = 10
     if (n == k) {
       return n
     } else {
       return fun(++n)
     }
   }