背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

日常代码中的大O

确定代码效率是优化的第一步。如果连代码运行速度都不知道，那又怎么知道所做的修改能不能让它更快呢？

此外，一旦确定了代码的时间复杂度，就能判断它是否需要优化。例如，一般认为复杂度为O(N2)的算法是比较“慢”的。所以，如果你判断自己的算法也属于此类，那么就应该停下来考虑有没有优化的方法。

当然，O(N2)的算法对于特定问题可能是最优解。但知道自己的算法不够快，则会让我们深入思考和分析，并寻找更好的方案。

偶数平均数

下面这个Ruby方法会读取一个数字数组，并返回其中所有偶数的平均数。如何用大O记法表示其效率呢？

def average_of_even_numbers(array)
  # 因为我们定义偶数平均数为数组中偶数之和与偶数个数的商，所以需要同时记录偶数的和以及个数：
  sum = 0.0
  count_of_even_numbers = 0
  # 遍历数组中的每个数，如果发现偶数，就更新和以及个数：
  array.each do |number|
    if number.even?
      sum += number
      count_of_even_numbers += 1
    end
  end
  # 返回平均数：
  return sum / count_of_even_numbers
end

大O分析法的根本在于回答如下核心问题：如果有N个数据元素，那么算法需要多少步？因此，首要任务是确定“N”个数据元素是什么。

本例中，算法处理的是传入的数字数组。那么“N”个数据元素指的就是这些数，其中N表示数组大小。

可以看出，该算法的核心是一个遍历数组中每一个数的循环，因此我们首先来分析这一循环。因为循环需要遍历N个元素，所以该算法需要至少N步。

进一步观察循环内部会发现在每轮循环中执行的步数不同。对于数组中的每一个数，都要检查它是不是偶数。如果是，则还需要额外两步：更新变量sum和count_of_even_numbers。因此，处理偶数比处理奇数要多执行两步。

大O分析法主要关注最坏情况。本例的最坏情况是，所有数都是偶数，那么每一轮循环都需要3步。因此，可以说该算法需要用3N步来处理N个数据元素。换言之，对于这N个数中的每一个，算法都要执行3步。

这一方法在循环之外还有一些步骤要执行。在进入循环之前，要初始化两个变量并将它们赋值为0。严格意义上讲，这需要2步。在退出循环之后还有1步：计算sum/count_of_even_numbers。也就是说，我们的算法在3N步之外还需要额外的3步，因此总的步数是3N + 3。

大O记法会忽略常数，因此简单地说，这是一个O(N)算法，而不是O(3N + 3)算法。

构词程序

下一个例子中的算法会读取一个单字母数组，并返回使用这些字母且长度为2的所有字符串组合。如果输入数组["a", "b", "c", "d"]，那么程序会返回包含如下字符串组合的新数组。

[
  'ab', 'ac', 'ad', 'ba', 'bc', 'bd',
  'ca', 'cb', 'cd', 'da', 'db', 'dc'
]

下面是该算法的JavaScript实现。来看看能否给出它的时间复杂度：

function wordBuilder(array) {
  let collection = [];
  for(let i = 0; i < array.length; i++) {
    for(let j = 0; j < array.length; j++) {
      if (i !== j) {
        collection.push(array[i] + array[j]);
      }
    }
  }
  return collection;
}

在循环中嵌套了另一个循环。外层循环会遍历数组中的每一个字母，记录其索引i。对于每一个索引i，我们都执行一个内层循环。内层循环会使用索引j再次遍历同一数组，只要i和j不相等，就把索引为i和j的字母连接起来。

要判断该算法的效率，还是需要先确定N个数据元素是什么。N都是传给函数的数组中元素的数量。下一步就是判断算法处理N个数据元素所需要的步数。在本例中，外层循环会遍历N个元素。对于每一个元素，内层循环都要再次遍历N个元素，也就是在N步的基础上再乘以N步。

就和一般的循环嵌套算法一样，它也是典型的O(N^2)算法。

数组抽样

从数组中抽取小块样本。因为输入数组预期会很大，所以只取数组的第一个、最中间的那个以及最后一个值。

函数的Python实现如下所示，来看看它的时间复杂度：

def sample(array):
  first = array[0]
  middle = array[int(len(array) / 2)]
  last = array[-1]
  return [first, middle, last]

主要数据是传入函数的数组，因此N表示数组中元素的数量。不过，无论N是多少，这个函数所需步骤数都相同。无论数组大小是多少，从数组的开头、中间和结尾读取都只需要1步。计算数组长度以及长度除以2同样只需要1步。

无论N是多少，步骤数都是固定的，因此这个算法是O(1)算法。

总结

学会了分析各种算法的时间复杂度，运用这些知识，可以帮助开发者系统地优化代码速度了。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。