结束了数据结构基本功的学习，接下来在真正开始撸真题之前，大家还需要具备评价算法的能力。

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

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

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

很多同学算法入门直接就跪在复杂度理解这一环。时间复杂度、空间复杂度，直接读概念确实太无聊，我们本节从代码入手，大家的理解会更直观一点。

# 时间复杂度

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

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