时间复杂度怎么算？

时间复杂度怎么算？

我们直接来个例子吧，思考一下，下面这段代码，一共执行多少次？

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

很显然，函数里的第一行代码，只会被执行一次。

var len = arr.length

还有一个很显然的一处代码是循环体：

console.log(arr[i])

我们观察一下for(var i = 0; i < len; i++)就会知道，for循环跑了n次（遇到这种算复杂度的题，输入规模默认都是n），所以这个循环体代码会被执行n次。

循环体上面那行的几个部分挤在一起显得有些复杂，我们拆开来看。

首先是i的初始化语句：

var i = 0

因为初始化只有一次，所以它只会被执行1次。

接着是i < len这个判断。有个规律大家可以记下：

所有的for循环都有这样的规律：判断语句比递增语句多执行一次。

递增语句i++被执行多少次？因为递增语句是跟随整个循环体的，毫无疑问会被执行n次。

而判断语句执行次数比递增语句多一次，所以判断语句被执行n + 1次。

假如我们把这段代码总的执行次数记为T(n)，下面我们就可以来加一下了：

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

注意，这个T(n)是「代码的执行次数」。

代码的执行次数可以反映出代码的执行时间。但是如果每次我们都逐行去计算T(n)，这就太麻烦了。

算法的「时间复杂度」，其实它反映的并不是算法的逻辑代码被执行了多少次，而是随着输入规模的增大，算法对应的执行总次数的一个「变化趋势」。

如果你对「导数」这个概念还有印象的话，就能理解「变化趋势」是什么意思了。

T(n)的结果一般是一个「多项式」，要想反映趋势，只抓主要矛盾即可。

例如，如果T(n)是3n^2 + 5n + 3，这是一个典型的「多项式」，我们只需要保留次数最高的那一项即可，并且将其常数系数改为1。

照着这个思路，T(n)就被简化为了O(n^2)。

但是，有时候T(n)不是「多项式」，而是「常数」。

这时候T(n)转换为时间复杂度是O(1)。

以上，之所以写得那么具体，先算T(n)，然后再推导O(n)，是为了方便大家理解O(n)的简化过程，在实际的操作中，如果你对算法比较熟练的话，O(n)基本可以目测。