提升算法水平的 4 个技巧

不要害怕编程面试

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

TL;DR（太长不看）。

1. 将 O(1) 与查表和数学运算联系起来。
2. O(n) 表示列表遍历。
3. 这个奇怪的对数是用于排序的：O(nlogn)
4. 将 O(n² ⁾与嵌套循环连接起来

无论你是否认同白板面试和算法题，掌握这些技能是你迟早都应该学习的。而要精通算法，你需要理解大O符号的概念。注意我用的是“理解”，而不是“掌握”。这个概念并不神秘。

BigO 表示法是一种简单的符号，它告诉你随着输入规模的增长，你的算法性能会如何变化。我总结了一些我偶尔会用到的技巧，用来解决和分析算法。

几周前，我把这篇文章发给了邮件列表里的 450 多位开发者。如果你想获得我关于职业发展的建议和想法，请点击这里加入。

1. 将 O(1) 与查表和数学运算联系起来

这意味着无论输入规模大小，你的算法运行时间大致相同。这通常适用于数学运算和对象查找。

// regardless of a or b, a sum is a math operation that takes just 
// one clock cycle to complete
const add = (a, b) => a + b;

// no matter of how big your map is (e.g an object in JavaScript), 
// a lookup will take 1 cycle to complete
const lookup = (map, key) => map[key];

你知道当你像这样bar从对象中访问属性时吗？嗯，那是一个 O(1) 操作。foofoo.bar

注意：理论上，无论哈希表如何解决冲突，其查找操作的时间复杂度都被认为是 O(1)。

2. O(n) 表示列表遍历。

这意味着你的算法运行时间将随输入数据线性增长。例如，求列表中最大值的算法。你的算法必然需要访问列表中的每个元素才能确定哪个数字是最大值。如果列表增长两倍，你的算法运行时间也将大致翻倍。

// you need to loop through all the elements to find the max.
function findMax(list) {
  let max = -Infinity;
  for (obj of list) {
    if (obj > max) max = obj
  }
}

3. 这个奇怪的对数用于排序：O(nlogn)

这个比看起来要简单。别担心那边那个奇怪的对数。大O表示法中的对数通常表示将某个东西分成两半，每一半再分成两半。但是，你只需要记住这一点：O(nlogn) 主要与排序相关。排序列表并非免费操作，使用排序会产生额外的开销。我们来看一个效率很低的获取列表最大值的方法：

function getMax(list) {
  return list.sort((a, b) => b - a)[0]
}

O(n) 比 O(nlogn) 更好，因为如果将 🦄 乘以 logn，你会得到更大的 🦄。

现在你已经有了很好的判断标准，可以根据这些标准来决定哪种方法最有效地找到最大值。你会选择使用 O(n) 算法还是 O(nlogn) 算法？

4.用嵌套循环连接 O(n² ^)问题

这意味着输入规模对算法的影响非常大（虽然不像其他算法那么严重）。如果输入规模翻倍，运行时间将增加 4 倍；如果输入规模增加 4 倍，运行时间将增加 16 倍。这通常表现为嵌套循环。让我们用一种效率极低的方法来检查数组中是否存在重复元素。

function hasDuplicates(list) {
  for (let [i, el_i] of list.entries()) {
    for (let [j, el_j] of list.entries()) {
      if (i !== j && el_i === el_j) return true;
    }
  }
  return false;
}

对于大小为 n 的列表中的每个元素，我们都会遍历整个大小为 n 的列表。这意味着我们要访问元素 n*n = n^次。

你能想出一个时间复杂度为 O(n) 的算法来解决这个问题吗？最好是只需要遍历列表一次的算法？请在评论区告诉我。

概括

如果你反对学习算法，就没必要深入研究这个话题，我尊重你的选择。你只需要保存这张表格，了解哪些任务比其他任务成本更高以及原因即可。

其他的

这个话题涉及方方面面，充满了各种复杂性和细微差别。你可以继续深入研究。但是，如果你能掌握这四个概念并牢记于心，你的算法能力将会得到显著提升，无论是在面试、PR评审，还是仅仅为了编写更优质的代码，都能事半功倍。

不要害怕编程面试

我运用这些概念提升了算法编程能力。之后，我获得了亚马逊、Toptal以及其他几家顶尖远程工作平台的面试机会（并拿到了工作offer） 。我撰写了一份免费指南，其中包含许多远程技术面试的技巧和窍门。如果您感兴趣，可以点击此处注册，即可在我的下一封邮件中收到这份指南。

我的推特私信一直开放，可以帮助你解决职业发展、算法面试、简历问题或成长建议。欢迎给我发消息，或者只是打个招呼！