评价算法的能力。

平时我们定义一个人是否“懂行”，一个重要的依据就是看这个人对某一个事物是否具备正确的评价能力。

举个例子，同样是买手机，外行进到手机店，他关注的可能是手机有没有跑马灯、有没有皮套护体、有没有“八心八箭”——这些东西，任何一部手机随便包装一下就都有了，根本没法反映出这台手机的本质问题。但如果是一个相对懂手机的人，他可能就会去关注这台手机的芯片、内存、屏幕材质及分辨率等等，从而对手机的整体性能和质量作出一个合理的判断，这样他买到好手机的概率就更大。

回到做算法题上，也是一样的道理。在面试时，自己给出的算法到底过不过得去，这一点在面试官给出评语之前，自己就应该有所感知。做到这一点，你才会掌握改进算法的主动权。

本节我们要学习的就是评价算法的两个重要依据——时间复杂度和空间复杂度。

时间复杂度

大家先来看这样一个问题：下面这段代码，一共会执行多少次？

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

首先，最没有悬念的是函数里的第一行代码，它只会被执行1次：

var len = arr.length

其次没有悬念的是循环体：

console.log(arr[i])

for循环跑了 n 次，因此这条语句就会被执行 n 次。
循环体上面的几个部分我们拆开来看，首先是 i 的初始化语句：

var i = 0

初始化只有1次，因此它也只会被执行1次。
接着是$i < len$ 这个判断。这里有个规律大家可以记下：在所有的 for 循环里，判断语句都会比递增语句多执行一次。在这里，判断语句执行的次数就是$n+1$。
再往下就是递增语句 $i++$ 了，它跟随整个循环体，毫无疑问会被执行 n 次。
假如把总的执行次数记为$T(n)$，下面咱们就可以来做个简单的加法：

T(n) = 1 + n + 1 + (n+1) + n = 3n + 3

接下来我们看看规模为 $n*n$ 的二维数组的遍历，一共需要执行多少次代码：

function traverse(arr) {
    var outLen = arr.length

    for(var i=0;i<outLen;i++) {
        var inLen = arr[i].length

        for(var j=0;j<inLen;j++) { 
            console.log(arr[i][j])
        }
    }
}

首先仍然是没有悬念的第一行代码，它只会被执行一次：

var outLen = arr.length

接下来我们来看最内层的循环体：

console.log(arr[i][j])

因为咱们是两层循环，所以这货会被执行 $n*n$ = n² 次。
其它语句的计算思路和咱们第一个🌰区别不大，这里我就不重复讲了，直接给出大家答案：

继续来做个求总执行次数 $T(n)$ 的加法看看：

T(n) = 1 + 1 + (n+1) + n + n + n + n*(n+1) + n*n + n*n = 3n^2 + 5n + 3

代码的执行次数，可以反映出代码的执行时间。但是如果每次我们都逐行去计算 $T(n)$，事情会变得非常麻烦。算法的时间复杂度，它反映的不是算法的逻辑代码到底被执行了多少次，而是随着输入规模的增大，算法对应的执行总次数的一个变化趋势。要想反映趋势，那就简单多了，直接抓主要矛盾就行。我们可以尝试对 $T(n)$ 做如下处理：

• 若 $T(n)$ 是常数，那么无脑简化为1
• 若 $T(n)$ 是多项式，比如 3n^2^+ 5n + 3，我们只保留次数最高那一项，并且将其常数系数无脑改为1。

经过这么一波操作，$T(n)$ 就被简化为了 $O(n)$：

T(n) = 10  
O(n) = 1

T(n) = 3n^2 + 5n + 3
O(n) = n^2

到这里，我们思路仍然是 计算$T(n)$-> 推导$O(n)$。这么讲是为了方便大家理解 $O(n)$ 的简化过程，实际操作中，$O(n)$ 基本可以目测，比如咱们上面的两个遍历函数：

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

function traverse2(arr) {
    var outLen = arr.length
    
    for(var i=0;i<outLen;i++) {
        var inLen = arr[i].length
        for(var j=0;j<inLen;j++) { 
            console.log(arr[i][j])
        }
    }
}

遍历 N 维数组，需要 N 层循环，我们只需要关心其最内层那个循环体被执行多少次就行了。
我们可以看出，规模为$n$的一维数组遍历时，最内层的循环会执行 n 次，其对应的时间复杂度是 $O(n)$；规模为 $n*n$ 的二维数组遍历时，最内层的循环会执行 $n*n$ 次，其对应的时间复杂度是 $O(n^2)$。

以此类推，规模为$n*m$ 的二维数组最内层循环会执行 $n*m$ 次，其对应的时间复杂度就是 $O(n*m)$；规模为 $n*n*n$ 的三维数组最内层循环会执行 $n^3$ 次，因此其对应的时间复杂度就表示为 $O(n^3)$。

常见的时间复杂度表达，除了多项式以外，还有 $log~n~$。我们一起来看另一个算法：

let t = 8;
while (t !== 1) {
    let s = []
    for (let i = 0; i < t; i++) {
        s.push(i)
    }
    console.log(s.toString());
    t = t / 2
}

查看输出结果

0,1,2,3,4,5,6,7
0,1,2,3
0,1

分析一下，复杂度我们取最大的

let t = 8; // 这一行代码只执行一次，肯定不是最大的,忽略！

其实一眼就能看出来！应该是内部for循环的语句复杂度是最高的！但是看看内部for循环的循环次数，第一次内部循环 8次，第二次是4次，第三次是2次，每次次数都少一半 2³ -> 2² -> 2¹,我们称这种复杂度为对数复杂度 $log~n~$

这里不减半的话~其实复杂度为$O(n)$，减半则是$log~n~$,所以$log~n~$的复杂度小于$O(n)$！
常见的时间复杂度按照从小到大的顺序排列，有以下几种：

空间复杂度

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

常见的空间复杂度有 $O(1)$、$O(n)$ 和$O(n^2)$。

理解空间复杂度，我们照样来看一个

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

后面尽管咱们做了很多次循环，但是这些都是时间上的开销
循环内部其实只开辟了一次额外内存var i=0对内存的占用量是恒定的，它对应的空间复杂度就是 $O(1)$

下面我们来看另一个，此时我想要初始化一个规模为 n 的数组，并且要求这个数组的每个元素的值与其索引始终是相等关系，我可以这样写：

function init(n) {
    var arr = []
    for(var i=0;i<n;i++) {
        arr[i] = i
    }
    return arr
}

在这个 init 中，涉及到的占用内存的变量有:n,arr,i,n和i都是一成不变的复杂度为$O(1)$,但是arr不是一直不变的，它会随着 n 的增大而增大、呈一个线性关系，因此这个算法的空间复杂度就是 $O(n)$,由此我们不难想象，假如需要初始化的是一个规模为 $n*n$ 的数组，那么它的空间复杂度就是 $O(n^2)$ 啦。