我们将学习每位开发者都应该熟悉的顶级算法的运行时间。了解这些时间复杂度将有助于评估代码的可扩展性。此外，它还有助于比较同一问题的不同解决方案。最后，您将能够一眼看出不同的实现方式，并知道哪种方式性能更佳。
为了澄清文章其余部分中使用的一些概念：
n。例如 O(n) 或 O(n 2 )。在深入探讨之前，这里先提供一份大O公式速查表和我们将在本文中介绍的示例。点击即可跳转到相应的实现部分。😉
| 大O符号 | 姓名 | 示例 |
|---|---|---|
| O(1) | 持续的 | #奇数或偶数， #查找表 |
| O(log n) | 对数 | #使用二分查找法在已排序数组中查找元素 |
| 在） | 线性 | #查找未排序数组中的最大元素， #使用哈希映射删除数组中的重复元素 |
| O(n log n) | 线性对数 | 使用归并排序对数组元素进行排序 |
| O(n 2 ) | 二次方程 | #数组中重复元素（朴素算法） # 使用冒泡排序对数组进行排序 |
| O(n 3 ) | 立方体 | # 3变量方程求解器 |
| O( 2n ) | 指数 | #找出所有子集 |
| 在！） | 阶乘 | #找出给定集合/字符串的所有排列 |
现在，让我们逐一提供代码示例！
O(1)描述无论输入规模如何，计算所需时间都相同的算法。
例如，如果一个函数处理 10 个元素和处理 100 万个元素所花费的时间相同，那么我们就说它具有恒定的增长率O(1)。让我们来看一些例子。
判断一个数是奇数还是偶数。
function isEvenOrOdd(n) {
return n % 2 ? 'Odd' : 'Even';
}
console.log(isEvenOrOdd(10)); // => Even
console.log(isEvenOrOdd(10001)); // => Odd
进阶提示：您也可以使用n % 2位与运算符来代替：n & 1。如果第一个位（最低有效位）为1奇数，则为奇数；否则为偶数。
无论 n 是 010还是 1 10,001，它都会执行第 2 行一次。
不要被那些看似简单的承诺所迷惑。它们并不总是能转化为实际效果。你必须了解它们是如何实现的。
如果你有一个类似 `get` 的方法Array.sort()，或者任何其他数组或对象方法，你必须查看其实现以确定其运行时间。
像加法、乘法、减法、除法、取模、位移等基本运算的运行时间是恒定的。这可能会让你感到惊讶！
如果使用教科书上的长乘法算法，两个数相乘需要花费一定的时间。然而，大多数编程语言都限制了数字的最大值（例如，在 JavaScript 中，`i` 的值是 ` max` ）。因此，你不能对大于此值的数字进行运算。所以，原始运算要么需要在固定数量的指令内完成，要么会抛出溢出错误（在 JavaScript 中，使用 ` if` 关键字）。O(n2)Number.MAX_VALUE1.7976931348623157e+308MAX_VALUEO(1)Infinity
这个例子很简单，我们再来一个。
给定一个字符串，找出它的词频数据。
const dictionary = {the: 22038615, be: 12545825, and: 10741073, of: 10343885, a: 10144200, in: 6996437, to: 6332195 /* ... */};
function getWordFrequency(dictionary, word) {
return dictionary[word];
}
console.log(getWordFrequency(dictionary, 'the'));
console.log(getWordFrequency(dictionary, 'in'));
再次强调，即使字典包含 10 个单词或 100 万个单词，它仍然只会执行一次第 4 行代码来查找单词。但是，如果我们决定将字典存储为数组而不是哈希表，情况就不同了。在下一节中，我们将探讨在数组中查找元素的运行时间。
只有使用完美哈希函数的哈希表才能实现O(1)的最坏情况运行时间。完美哈希函数并不实用，因此会存在一些冲突，需要通过变通方法来避免，导致最坏情况运行时间变为O(n)。尽管如此，平均查找时间仍然是O(1)。
线性运行时间算法非常常见。线性运行时间意味着程序会遍历输入中的每个元素。
线性时间复杂度O(n)意味着随着输入的增长，算法完成所需的时间也会成比例地延长。
例如：
假设你想从一个未排序的数组中找到最大值。
function findMax(n) {
let max;
let counter = 0;
for (let i = 0; i < n.length; i++) {
counter++;
if(max === undefined || max < n[i]) {
max = n[i];
}
}
console.log(`n: ${n.length}, counter: ${counter}`);
return max;
}
该函数将执行多少次运算findMax？
它会检查输入中的每个元素n。如果当前元素大于目标元素，max则会执行赋值操作。
请注意，我们添加了一个计数器，以便帮助我们统计内部代码块执行的次数。
如果计算时间复杂度，结果大概是这样的：
所以，这就把我们难住了3(n) + 2。
应用我们在上一篇文章中学到的大 O 符号，我们只需要最高阶项，因此O(n)。
我们可以使用我们的方法来验证这一点counter。如果n它有 3 个元素：
findMax([3, 1, 2]);
// n: 3, counter: 3
或者如果n它有 9 个元素：
findMax([4,5,6,1,9,2,8,3,7])
// n: 9, counter: 9
现在想象一下，你有一个包含一百万个元素的数组，它将执行一百万次操作。如果我们绘制出元素数量 n 和findMax运行时间的图像，我们将得到一个类似于线性方程的曲线。
时间复杂度为二次方的函数，其增长率为 n² 。如果输入大小为 2，则需要执行 4 次操作。如果输入大小为 8，则需要执行 64 次操作，依此类推。
以下是一些二次算法的代码示例：
你想在一个数组中查找重复的单词。一个简单的解决方案如下：
function hasDuplicates(n) {
const duplicates = [];
let counter = 0;
for (let outter = 0; outter < n.length; outter++) {
for (let inner = 0; inner < n.length; inner++) {
counter++;
if(outter === inner) continue;
if(n[outter] === n[inner]) {
return true;
}
}
}
console.log(`n: ${n.length}, counter: ${counter}`);
return false;
}
时间复杂度分析：
n2我们得到3n^2 + 2。
同样，当我们使用大O表示法时，我们会忽略所有常数，只保留最高有效项：n^2。所以，它应该是O(n^2)。
我们使用一个计数器变量来帮助我们进行验证。该hasDuplicates函数有两个循环。如果输入 4 个单词，它将执行内部代码块 16 次。如果输入 9 个单词，它将执行计数器指定的次数 81 次，依此类推。
hasDuplicates([1,2,3,4]);
// n: 4, counter: 16
n 大小为 9：
hasDuplicates([1,2,3,4,5,6,7,8,9]);
// n: 9, counter: 81
我们来看另一个例子。
我们想要对数组中的元素进行排序。
function sort(n) {
for (let outer = 0; outer < n.length; outer++) {
let outerElement = n[outer];
for (let inner = outer + 1; inner < n.length; inner++) {
let innerElement = n[inner];
if(outerElement > innerElement) {
// swap
n[outer] = innerElement;
n[inner] = outerElement;
// update references
outerElement = n[outer];
innerElement = n[inner];
}
}
}
return n;
}
此外，您可能注意到，对于非常大的规模n，解决问题所需的时间会大幅增加。您能看出嵌套循环与运行时间之间的关系吗？当一个函数只有一个循环时，其运行时间复杂度通常为 O(n)。现在，这个函数有两个嵌套循环，运行时间复杂度为二次方：O(n² )。
多项式运行的时间复杂度表示为 O(n^ c )，其中 n ≥ c > 11。正如你已经看到的，两个内层循环的时间复杂度几乎为 O(n^ 2 )，因为大多数情况下它需要遍历数组两次。三个嵌套循环的时间复杂度是三次的吗？如果每个循环都访问所有元素，那么是的！
通常情况下，我们会尽量避免多项式运行时间（二次、三次、n- c ……），因为随着输入数据快速增长，它们的计算时间会更长。然而，它们并非最糟糕的选择。
假设你想求解一个如下所示的多元方程：
3x + 9y + 8z = 79
这个简单的程序将给出满足方程的所有解，其中x，y且z< n。
function findXYZ(n) {
const solutions = [];
for(let x = 0; x < n; x++) {
for(let y = 0; y < n; y++) {
for(let z = 0; z < n; z++) {
if( 3*x + 9*y + 8*z === 79 ) {
solutions.push({x, y, z});
}
}
}
}
return solutions;
}
console.log(findXYZ(10)); // => [{x: 0, y: 7, z: 2}, ...]
该算法的运行时间为立方时间：。O(n3)
注：我们可以采用更高效的解决方案，但为了展示立方运行时的示例，这已经足够好了。
对数时间复杂度通常适用于每次都将问题分解成两半的算法。例如，假设我们要在一本老式词典中查找一个单词。这本词典中的所有单词都按字母顺序排列。至少有两种方法可以做到这一点：
算法A：
算法B：
哪个算法更快？第一个算法逐字查找，时间复杂度为O(n)，而算法 B 在每次迭代中将问题分成两半，时间复杂度为O(log n)。第二个算法是二分查找。
查找已排序数组中某个元素的索引。
如果我们实现算法 A，遍历数组中的所有元素，则需要 O(n^2)。O(n)我们能否做得更好？我们可以尝试利用集合已排序这一事实。之后，在查找目标元素时，我们可以将时间复杂度减半。
function indexOf(array, element, offset = 0) {
// split array in half
const half = parseInt(array.length / 2);
const current = array[half];
if(current === element) {
return offset + half;
} else if(element > current) {
const right = array.slice(half);
return indexOf(right, element, offset + half);
} else {
const left = array.slice(0, half)
return indexOf(left, element, offset);
}
}
const directory = ["Adrian", "Bella", "Charlotte", "Daniel", "Emma", "Hanna", "Isabella", "Jayden", "Kaylee", "Luke", "Mia", "Nora", "Olivia", "Paisley", "Riley", "Thomas", "Wyatt", "Xander", "Zoe"];
console.log(indexOf(directory, 'Hanna')); // => 5
console.log(indexOf(directory, 'Adrian')); // => 0
console.log(indexOf(directory, 'Zoe')); // => 18
计算该函数的时间复杂度indexOf并不像之前的例子那么直接。该函数是递归的。
分析像主方法这样的递归算法的方法有很多，但这些方法超出了本文的讨论范围。一般来说，当你看到一个算法将输入分成两半时，它很可能涉及一定的log n运行时间。由于递归之外的工作量是恒定的，因此我们的运行时间为O(log n)。
线性对数时间复杂度比线性算法稍慢，但仍然比二次算法好得多（您将在帖子的最后看到一个比较所有这些算法的图表）。
对数组进行排序的最佳方法是什么？之前，我们提出了一种使用冒泡排序的解决方案，其时间复杂度为 O(n² )。我们能否做得更好？
我们可以使用一种叫做算法的方法mergesort来改进它。
它的工作原理如下：
以下是归并排序的代码：
function sort(n) {
const length = n.length;
// base case
if(length === 1) {
return n;
}
if(length === 2) {
return n[0] > n[1] ? [n[1], n[0]] : [n[0], n[1]];
}
// slit and merge
const mid = length/2;
return merge(sort(n.slice(0, mid)), sort(n.slice(mid)));
}
function merge(a = [], b = []) {
const merged = [];
// merge elements on a and b in asc order. Run-time O(a + b)
for (let ai = 0, bi = 0; ai < a.length || bi < b.length;) {
if(ai >= a.length || a[ai] > b[bi]) {
merged.push(b[bi++]);
} else {
merged.push(a[ai++]);
}
}
return merged;
}
如您所见，它有两个函数sort。merge合并（Merge）是一个辅助函数，它遍历集合一次a，b因此其运行时间为 O(n)。排序（Sort）是一个递归函数，每次都将数组分成两半，归并排序的总运行时间为O(n log n)。
注：如果您想查看完整的解释，请查看归并排序的精通方法。
指数（以 2 为底）运行时间意味着算法执行的计算量随着输入的增长而翻倍。
找出给定集合的所有不同子集。例如，让我们举几个例子，尝试提出一个解决这个问题的算法：
getSubsets('') // => ['']
getSubsets('a') // => ['', 'a']
getSubsets('ab') // => ['', 'a', 'b', 'ab']
你发现什么规律了吗？
b添加了第二个元素。如果要查找 的子集呢abc？嗯，它恰好是 'ab' 的子集，以及在每个元素末尾附加 的ab的子集。c
正如你所看到的，每次输入长度增加，输出长度都会是前一次的两倍。让我们用代码来实现它：
function getSubsets(n = '') {
const array = Array.from(n);
const base = [''];
const results = array.reduce((previous, element) => {
const previousPlusElement = previous.map(el => {
return `${el}${element}`;
});
return previous.concat(previousPlusElement);
}, base);
console.log(`getSubsets(${n}) // ${results.slice(0, 15).join(', ')}... `);
console.log(`n: ${array.length}, counter: ${results.length};`);
return results;
}
如果我们对几个案例运行该函数，将会得到：
getSubsets('') // ...
// n = 0, f(n) = 1;
getSubsets('a') // , a...
// n = 1, f(n) = 2;
getSubsets('ab') // , a, b, ab...
// n = 2, f(n) = 4;
getSubsets('abc') // , a, b, ab, c, ac, bc, abc...
// n = 3, f(n) = 8;
getSubsets('abcd') // , a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd...
// n = 4, f(n) = 16;
getSubsets('abcde') // , a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd...
// n = 5, f(n) = 32;
正如预期的那样，如果你绘制n和 的图像f(n)，你会发现它与函数 完全相同2^n。该算法的运行时间为O(2^n)。
注意：应尽可能避免使用运行时间呈指数级增长的函数，因为它们的扩展性很差。处理输出所需的时间会随着输入规模的增加而翻倍。但指数级运行时间还不是最糟糕的；还有一些函数的运行速度更慢。让我们在下一节中再看一个例子。
阶乘是指小于它的所有正整数的乘积。例如：
5! = 5 × 4 × 3 × 2 × 1 = 120
它生长速度很快：
20! = 2,432,902,008,176,640,000
正如你可能猜到的那样，你应该尽可能远离运行时间如此之长的算法！
编写一个函数，计算给定字符串可以组成的所有不同单词。例如
getPermutations('a') // => [ 'a']
getPermutations('ab') // => [ 'ab', 'ba']
getPermutations('abc') // => [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]
你会如何解决这个问题？
一个简单的办法是检查字符串的长度是否为 1，如果是，则返回该字符串，因为你无法以不同的方式排列它。
对于长度大于 1 的字符串，我们可以使用递归将问题分解成更小的子问题，直到处理长度为 1 的情况。我们可以取出第一个字符，然后处理字符串的剩余部分，直到字符串长度为 1。
function getPermutations(string, prefix = '') {
if(string.length <= 1) {
return [prefix + string];
}
return Array.from(string).reduce((result, char, index) => {
const reminder = string.slice(0, index) + string.slice(index+1);
result = result.concat(getPermutations(reminder, prefix + char));
return result;
}, []);
}
如果将输出结果打印出来，大概会是这样：
getPermutations('ab') // ab, ba...
// n = 2, f(n) = 2;
getPermutations('abc') // abc, acb, bac, bca, cab, cba...
// n = 3, f(n) = 6;
getPermutations('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd...
// n = 4, f(n) = 24;
getPermutations('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde...
// n = 5, f(n) = 120;
我尝试使用长度为 10 的字符串。大约花了 8 秒！
time node ./lib/permutations.js
# getPermutations('abcdefghij') // => abcdefghij, abcdefghji, abcdefgihj, abcdefgijh, abcdefgjhi, abcdefgjih, abcdefhgij...
# // n = 10, f(n) = 3,628,800;
# ./lib/permutations.js 8.06s user 0.63s system 101% cpu 8.562 total
我给你布置了一点作业……
你能试试用 11 个字符的排列组合吗？ ;) 在下方评论区留言，说说你的电脑发生了什么！
我们探讨了最常见的算法运行时间，并分别举了一两个例子！这些例子应该能帮助你了解如何在项目开发过程中计算运行时间。下面是一个图表，展示了我们讨论过的所有时间复杂度：
注意时间复杂度！
您可以在Github代码库中找到所有这些示例以及更多内容：
amejiarosario / dsa.js-数据结构-算法-javascript
这是DSA.js 书籍的代码实现以及 NPM 包的仓库。
在这个代码库中，你可以找到 JavaScript 中算法和数据结构的实现。这些资料可以作为开发者的参考手册，也可以帮助你在面试前复习特定主题。此外，你还可以从中获得更高效的问题解决方法。
您可以克隆此仓库或从 NPM 安装代码：
npm install dsa.js
然后您可以将其导入到您的程序或命令行界面中。
const { LinkedList , Queue , Stack } = require ( 'dsa.js' ) ;
有关所有公开数据结构和算法的完整列表，请参见。
算法是……