在本文中，咱们将讨论 “二次方” 和 “n log(n)” 等术语在算法中的意义。

在后面的比如中，我将引证这两个数组，一个包括 5 个元素，另一个包括 50 个元素。我还会用到 JavaScript 中便利的 performance API 来衡量履行时刻的差异。

constsmArr=[5,3,2,35,2];
constbigArr=[5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2,5,3,2,35,2];

什么是 Big O 符号?

Big O 表明法是用来表明跟着数据集的增加，核算使命难度整体增加的一种办法。虽然还有其他表明法，但一般 big O 表明法是最常用的，由于它着眼于最坏的状况，更简略量化和考虑。最坏的状况意味着完结使命需求最多的操作次数;假如你在一秒钟内就能康复打乱魔方，那么你只拧了一圈的话，不能说自己是做得最好的。

当你进一步了解算法时，就会发现这十分有用，由于在了解这种联系的一起去编写代码，就能知道时刻都花在了什么地方。

当你了解更多有关 Big O 表明法的信息时，或许会看到下图中不同的改动。咱们期望将复杂度坚持在尽或许低的水平，最好防止超越 O(n)。

O(1)

这是抱负的状况，不管有多少个项目，不管是一个仍是一百万个，完结的时刻量都将坚持不变。履行单个操作的大多数操作都是 O(1)。把数据写到数组、在特定索引处获取项目、增加子元素等都将会花费相同的时刻量，这与数组的长度无关。

consta1=performance.now();
smArr.push(27);
consta2=performance.now();
console.log(`Time:${a2-a1}`);//Lessthan1Millisecond
constb1=performance.now();
bigArr.push(27);
constb2=performance.now();
console.log(`Time:${b2-b1}`);//Lessthan1Millisecond

O(n)

在默许状况下，一切的循环都是线性增加的，由于数据的巨细和完结的时刻之间存在1对1的联系。所以假如你有 1,000 个数组项，将会花费的 1,000 倍时刻。

consta1=performance.now();
smArr.forEach(item=>console.log(item));
consta2=performance.now();
console.log(`Time:${a2-a1}`);//3Milliseconds
constb1=performance.now();
bigArr.forEach(item=>console.log(item));
constb2=performance.now();
console.log(`Time:${b2-b1}`);//13Milliseconds

O(n^2)

指数增加是一个圈套，咱们都掉进去过。你是否需求为数组中的每个项目找到匹配对?将循环放入循环中是一种很好的办法，能够把 1000 个项目的数组变成一百万个操作查找，这将会使你的浏览器失掉呼应。与运用两层嵌套循环进行一百万次操作比较，最好在两个独自的循环中进行 2,000 次操作。

consta1=performance.now();
smArr.forEach(()=>{
arr2.forEach(item=>console.log(item));
});
consta2=performance.now();
console.log(`Time:${a2-a1}`);//8Milliseconds
constb1=performance.now();
bigArr.forEach(()=>{
arr2.forEach(item=>console.log(item));
});
constb2=performance.now();
console.log(`Time:${b2-b1}`);//307Milliseconds

O(log n)

我以为关于对数增加比较好的比方，是幻想在字典中查找像 “notation” 之类的单词。你不会在一个词条一个词条的去进行查找，而是先找到 “N” 这一部分，然后是 “OPQ” 这一页，然后按字母顺序查找列表直到找到匹配项。

经过这种“分而治之”的办法，找到某些内容的时刻仍然会因字典的巨细而改动，但远不及 O(n) 。由于它会在不查看大部分数据的状况下逐渐查找更详细的部分，所以查找一千个项目或许需求少于 10 个操作，而一百万个项目或许需求少于 20 个操作，这使你的功率最大化。

在这个比如中，咱们能够做一个简略的 快速排序。

constsort=arr=>{
if(arr.length<2)returnarr;
letpivot=arr[0];
letleft=[];
letright=[];
for(leti=1,total=arr.length;i<total;i++){
if(arr[i]<pivot)left.push(arr[i]);
elseright.push(arr[i]);
};
return[
...sort(left),
pivot,
...sort(right)
];
};
sort(smArr);//0Milliseconds
sort(bigArr);//1Millisecond

O(n!)

最糟糕的一种或许性是析因增加。最经典的比如便是游览的推销员问题。假如你要在许多间隔不同的城市之间游览，怎么找到在一切城市之间回来起点的最短道路?暴力办法将是查看每个城市之间一切或许的道路间隔，这是一个阶乘而且很快就会失控。

由于这个问题很快会变得十分复杂，因而咱们将经过简略的递归函数演示这种复杂性。这个函数会将一个数字去乘以函数自己，然后将数字减去1。阶乘中的每个数字都会这样核算，直到为 0，而且每个递归层都会把其乘积增加到原始数字中。

阶乘仅仅从 1 开端直至该数字的乘积。那么 6!是 1x2x3x4x5x6 = 720。

constfactorial=n=>{
letnum=n;
if(n===0)return1
for(leti=0;i<n;i++){
num=n*factorial(n-1);
};
returnnum;
};
factorial(1);//2Milliseconds
factorial(5);//3Milliseconds
factorial(10);//85Milliseconds
factorial(12);//11,942Milliseconds

我本来计划显现 factorial(15)，可是 12 以上的值都太多，而且使页面溃散了，这也证明了为什么需求防止这种状况。

结束语

咱们需求编写高性能的代码似乎是一个不争得现实，可是我敢肯定，简直每个开发人员都创立过至少两重乃至三重嵌套循环，由于“它的确有用”。Big O 表明法在表达和考虑复杂性方面是十分必要的，这是咱们从未有过的办法。