翻译：通过理解大O来通过编程面试，并且编写更快的代码
世界顶级科技公司测试候选人的算法知识以及算法速度l，这是大O的用武之地。这篇文章解释了大O是什么，并且提供真实的算法以及大O的实际示例。
了解算法的速度是编程的必备技能。对于较小的数据集，这可能不会引起太多麻烦，但是具有大量用户、数据等，差异可能是惊人的。
尽管大O的知识只和大型科技公司的面试有关，但它仍然是需要知道如何是你的算法尽可能的更快。了解如何编写更有效的算法以及为什么它们更有效率在每个级别都很有用！
内容
1. 为什么效率很重要
2. 什么是大O
3. 先决条件
4. O(n) - 线性时间 - 线性时间)
5. O(N²) - 二次时间 - 二次时间)
6. 冒泡排序
7. O(N³，ON⁴）- 立方时间，四次方时间等
8. 为什么我们经常忽略倍数
9. 为什么我们忽略除大的次方的一切
10. 对数
11. O(logN）- 二分法查找
12. O(NlogN）- 快速排序
13. 最后一句话：时间和空间的复杂性
14. 总结
15. 我想了解的更多
为什么效率很重要
在解释大O之前，我想用一个愚蠢的例子来解释它为什么这个重要。假设你有十封电子邮件，每一个里面有包含一个你需要的电话号码，你不能使用搜索栏，那你怎么找到那个的电话号码呢？
好吧，它只有十封邮件，因此你可能一个一个的打开浏览，直到你找到电话号码，并且你最多检查十封邮件。那没关系，它只需要一两分钟。
但是想象一下，你有18亿封邮件，你仍然只需要一个电话号码。面对这种规模，你永远不会想着打开每一个邮件。即使你每秒都可以查看一封邮件而且从不睡觉，但仍需要57年才能找到你想要的电话号码。
这个例子非常傻，如果你不幸有18亿封邮件，你你肯定会使用搜索栏。但是这个例子清楚的表明：一个小规模的工作过程很大程度上是完全不切实际的。
我选择的数字为18亿，因为在2018年1月，这是互联网上活跃网站的估计数量，因此大致相仿于google等搜索引擎需要存储数据的网站数量。因此，像google搜索这样的服务利用最优化的算法来处理所有数据至关重要。
什么是大O
在基本的层面上，大O为我们提供了一种快速评估算法速度或者更恰当的性能的方法。它测量的是随着输入的增加，运行时相对输入增长的速度。
对于很多算法，可以一目了额安的确定它们的效率，并使用大O来表示它。这就是为什么许多世界顶级的变成公司在面试中测试这些知识的原因。
像二分法搜索这样高效的算法，可能具有O(logN)的性能。而像Bogosort这样极其低效的算法可能具有O(log(N!))的性能。
如果这些看起来不熟悉，不用担心，我将会逐一介绍必要的细节。本文适用于初学者，但是它比我遇到的其他任何初学者的文章更深入。这是因为，在这篇文章中，我们不仅会介绍大O的理论，还会在介绍大O的部分中看一些剧名的搜索排序算法，以及这些算法的代码。
先决条件
示例代码是使用js编写的，因此如果你对js有所了解，那么你将从本文中获得最大的收益。其中还涉及到有关数组、函数和循环的基本知识。
O(1)
这表示运行时固定的算法，无论你输入数据的量如何，算法只会花费固定的时间。
在下面的例子中，我们向函数传递一个数组，数组无论有一个值或者一千个值都没关系，它将得花费同样的时间，因为它只是简单的返回一个值。
我们称之为O(1)，无论输入的大小如何，函数只吐出一个值。这样的函数都可以被描述为具有O(1)的性能。
function(array) {
return array[0];
}
O(n) - 线性时间
这个相当于手动浏览所有的电子邮件。随着数组的长度增加，所需的处理量以相同的效率增加。
在这个函数中，将数组的每一项都打印到控制台上。随着数组长度增加量与执行console.log的次数增加的数量是一样的。
function logArray(array) {
for (let i = 0; i < array.length; i++) {
console.log(array[i]);
}
}
请注意，大O基于最大可能的迭代次数。因此，即使函数可以提前完成，以下函数仍具有O(n)的算法效率，这就是为什么有些人将“最坏情况”看作衡量的标准。
function findTheMeaningOfLife(array){
for (let i = 0; i < array.length; i++) {
if (array[i] === 42) {
return i;
}
}
}
O(N²) - 二次时间
效率为O(N²)的算法是以O(N)的相对速率的两倍增加，我将使用console.log作为演示。
假设我们有含有三个数字的数组：array = [1, 2, 3]。如果我将它传递给上面的logArray函数，那么它将只打印出数字1， 2， 3。但是这个方案怎么样呢？
function(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
console.log(array[j]);
}
}
}
它将打印出1 2 3 1 2 3 1 2 3。与上面的logArray相比，这是九个数字，因此它遵循3² = 9，并且该功能具有的O(N²)性能。
技术说明：使用大O时，我们关注函数执行的操作，而不是它返回的结果。为了帮助初学者，我选择的都是返回的值的数量等于操作的数量的函数，但在实践中这种情况很少。
这是O(N²)的另一例子，如果数组中任意两个数字的和事42，则返回true。如上所述，它可以提前返回，但是我们会假设它会花费最长的时间。
function isSum42(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
if (array[i] + array[j] === 42) {
console.log('Found the meaning of life!');
return true;
}
}
}
}
冒泡排序
现在我们的第一个实际排序算法的示例是冒泡排序。这是对一组值进行排序，其性能可以描述为O(N²)（原理我不翻译了）。
为什么冒泡排序的性能是O(N²)
当你看了代码时，冒泡排序的性能为O(N²)的原因变得清晰。这有一个最简单的实现，它运行可能需要最大的传递次数（一个更复杂的冒泡排序会阻止算法在没有交换的情况下的继续进行，但为了简单期间，我把它留了下来）。
function bubbleSort(array) {
let length = array.length;
// This loop handles the passes
for (let i = 0; i < length; i++) {
// This loop handles the swapping during a single pass
for (let j = 0; j < (length - i - 1); j++) {
if (array[j] > array[j + 1]) {
let tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
return array;
}
正如你看到的那样，其中有你两个循环，第二个嵌套在第一个里面。这是O(N²)的经典标志，这是我们对算大的第一次真实性能分析。
O(N³)，O(N⁴) - 立方时间，四次方时间等
如果两个嵌套循环给出了O(N²)，则三个嵌套循环给出了O(N³)，四个嵌套循环给出了O(N⁴)，以此类推。
让我们回到简单的数组[1, 2, 3]， 并将其传递给性能为O(N³)的函数：
function(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
for (let k = 0; k < array.length; k++){
console.log(array[k]);
}
}
}
正如我们期望的那样，输出是27（=3³）个数字，因为我们的输入N的值为3。
如果我们再添加一个循环，我们将获得：
function(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
for (let k = 0; k < array.length; k++){
for (let l = 0; l< array.length; l++){
console.log(l);
}
}
}
}
}
正如我们预期的那样，这个O（N⁴）函数产生81（=3⁴）个数。
为什么我们经常忽略倍数
假设对于我们放入函数的每个项目，它会对数据进行两次处理。例如，我们可以有这样的函数：
function countUpThenDown(array) {
for (let i = 0; i < array.length; i++) {
console.log(i);
};
for (let i = array.length; i > 0; i--) {
console.log(i);
};
}
我们可以称之为O(2N)。并且，如果我们在序列中添加了另一个for循环，那么它第三次处理数据就可以称之为O(3N)。
在小规模，差异非常重要。但是大O关注算法如何以非常高的规模运行。出于这个原因，我们倾向于忽略倍数。
一般来说，我们认为线性O(N)和二次O(N²)之间的差异，比同一类型的倍数之间的差异更重要。因此，在大多数情况下，您可以安全地忽略倍数。