javascript 符号_通过JavaScript了解Big O符号

短命女 2022-11-27 04:27 119阅读 0赞

javascript 符号

If you’ve ever looked into getting a job as a developer you’ve probably come across this [Google interview][] at some point and wondered ‘what the heck are they talking about?’. In this article, we’re going to explore what they mean throwing around terms such as 'quadratic’ and 'n log n’.

如果您曾经寻求过作为开发人员的工作，那么您可能在某个时候遇到过[Google采访][Google interview] ，并且想知道“他们到底在说什么？”。 在本文中，我们将探讨它们的含义，例如“二次”和“ n log n”。

In some of these examples I’m going to be referring to these two arrays, one with 5 items and another with 50. I’m also going to be using JavaScript’s handy [performance API][] to measure the difference in execution time.

在这些示例中，我将引用这两个数组，一个包含5个项目，另一个包含50个项目。我还将使用JavaScript的便捷[性能API][performance API]来衡量执行时间的差异。

const smArr = [5, 3, 2, 35, 2];
    
    const bigArr = [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];

## 什么是大O符号？ **(**What is Big O Notation?**)** ##

Big O notation is just a way of representing the general growth in the computational difficulty of a task as you increase the data set. While there are other notations, O notation is generally the most used because it focuses on the worst-case scenario, which is easier to quantify and think about. Worst-case meaning where the most operations are needed to complete the task; if you solve a rubik’s cube in one second you can’t say you’re the best if it only took one turn to complete.

大O表示法只是表示随着数据集的增加，任务计算难度的总体增长的一种方式。 尽管还有其他表示法，但O表示法通常是最常用的，因为它专注于最坏的情况，这种情况更容易量化和考虑。 最坏的情况意味着完成任务需要最多的操作； 如果您在一秒钟内就能解决魔方的魔方，那么只用一转就可以说自己是最好的。

As you learn more about algorithms you’ll see these expressions used a lot because writing your code while understanding this relationship can be the difference between an operation being nearly instantaneous or taking minutes and wasting, sometimes enormous amounts of, money on external processors like Firebase.

随着您对算法的了解越来越多，这些表达式将变得非常有用，因为在理解这种关系的同时编写代码可能是操作几乎是瞬时的或花费数分钟而浪费了大量的时间，有时甚至浪费了大量外部处理器(如Firebase)上的钱。

As you learn more about Big O notation, you’ll probably see many different, and better, variations of this graph. We want to keep our complexity as low and straight as possible, ideally avoiding anything above O(n).

当您了解更多有关Big O表示法的信息时，可能会看到该图的许多不同且更好的变体。 我们希望将复杂度保持在尽可能低的水平，最好避免超过O(n)的任何事物。

## O(1) **(**O(1)**)** ##

This is the ideal, no matter how many items there are, whether one or one million, the amount of time to complete will remain the same. Most operations that perform a single operation are O(1). Pushing to an array, getting an item at a particular index, adding a child element, etc, will all take the same amount of time regardless of the array length.

这是理想的，无论有多少个项目，无论是一百万还是一百万，完成的时间量都将保持不变。 执行单个操作的大多数操作都是O(1)。 推送到数组，在特定索引处获取项目，添加子元素等都将花费相同的时间量，而与数组长度无关。

const a1 = performance.now();
    smArr.push(27);
    const a2 = performance.now();
    console.log(`Time: ${a2 - a1}`); // Less than 1 Millisecond
    
    
    const b1 = performance.now();
    bigArr.push(27);
    const b2 = performance.now();
    console.log(`Time: ${b2 - b1}`); // Less than 1 Millisecond

## 上) **(**O(n)**)** ##

By default, all loops are an example of linear growth because there is a one-to-one relationship between the data size and time to completion. So an array with 1,000 times more items will take exactly 1,000 times longer.

默认情况下，所有循环都是线性增长的一个示例，因为数据大小和完成时间之间存在一对一的关系。 因此，具有1,000倍以上项的数组将花费更长的1,000倍时间。

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

## O(n ^ 2) **(**O(n^2)**)** ##

Exponential growth is a trap we’ve all fall into at least once. Need to find a matching pair for each item in an array? Putting a loop inside a loop is great way of turning an array of 1,000 items into a million operation search that’ll freeze your browser. It’s always better to have to do 2,000 operations over two separate loops than a million with two nested loops.

指数增长是我们所有人都陷入了至少一次的陷阱。 是否需要为数组中的每个项目找到匹配对？ 将循环放入循环中是一种将一千个项目转换为一百万个操作搜索的好方法，这将冻结您的浏览器。 与两个嵌套循环中的一百万次操作相比，必须在两个单独的循环中执行2,000次操作总是更好。

## O(log n) **(**O(log n)**)** ##

The best analogy I’ve heard to understand logarithmic growth is to imagine looking up a word like 'notation’ in a dictionary. You can’t search one entry after the other, instead you find the 'N’ section, then maybe the 'OPQ’ page, then search down the list alphabetically until you find a match.

我听说过的最好的类比对数增长方法是想象在字典中查找像“符号”之类的词。 您不能在一个条目之后搜索另一个条目，而是找到“ N”部分，然后找到“ OPQ”页面，然后按字母顺序向下搜索列表，直到找到匹配项。

With this 'divide-and-conquer’ approach, the amount of time to find something will still change depending on the size of the dictionary but at nowhere near the rate of O(n). Because it searches in progressively more specific sections without looking at most of the data, a search through a thousand items may take less than 10 operations while a million may take less than 20, getting you the most bang for your buck.

通过这种“分而治之”的方法，找到某些东西的时间仍然会根据字典的大小而改变，但远不及O(n)的比率。 因为它会在不查看大部分数据的情况下逐步搜索更具体的部分，所以搜索一千个项目可能需要少于10个操作，而一百万个项目可能需要少于20个操作，这使您的工作量最大。

In this example, we can do a simple [quicksort][].

在这个例子中，我们可以做一个简单的[quicksort][] 。

const sort = arr => {
      if (arr.length < 2) return arr;
    
      let pivot = arr[0];
      let left = [];
      let right = [];
    
      for (let i = 1, total = arr.length; i < total; i++) {
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
      };
      return [
        ...sort(left),
        pivot,
        ...sort(right)
      ];
    };

sort(smArr); // 0 Milliseconds
    sort(bigArr); // 1 Millisecond

## 上！) **(**O(n!)**)** ##

Finally, one of the worst possibilities, factorial growth. The textbook example of this is the [travelling salesman][] problem. If you have a bunch of cities of varying distance, how do you find the shortest possible route that goes between all of them and returns to the starting point? The brute force method would be to check the distance between every possible configuration between each city, which would be a factorial and quickly get out of hand.

最后，最糟糕的可能性之一是析因增长。 这方面的教科书示例是[旅行商][travelling salesman]问题。 如果您有一堆距离不同的城市，如何找到在所有城市之间返回起点的最短路线？ 蛮力方法将是检查每个城市之间每个可能配置之间的距离，这是一个阶乘并且很快会失控。

Since that problem gets very complicated very quickly, we’ll demonstrate this complexity with a short recursive function. This function will multiply a number by its own function taking in itself minus one. Every digit in our factorial will run its own function until it reaches 0, with each recursive layer adding its product to our original number. So 3 is multiplied by 2 that runs the function to be multiplied by 1 that runs it again to be stopped at 0, returning 6. Recursion gets confusing like this pretty easily.

由于该问题很快变得非常复杂，因此我们将通过简短的递归函数演示这种复杂性。 此函数会将一个数字乘以自己的函数，然后将自身减去1。 阶乘中的每个数字将运行其自己的功能，直到达到0，并且每个递归层都将其乘积添加到我们的原始数字中。 因此，将3乘以2将运行函数，然后将其乘以1再次运行该函数，以将其停止在0，返回6。递归很容易引起混淆。

A factorial is just the product of every number up to that number. So 6! is 1x2x3x4x5x6 = 720.

阶乘只是每个数字直至该数字的乘积。 那么6！ 是1x2x3x4x5x6 = 720。

const factorial = n => {
      let num = n;
    
      if (n === 0) return 1
      for (let i = 0; i < n; i++) {
        num = n * factorial(n - 1);
      };
    
      return num;
    };

factorial(1); // 2 Milliseconds
    factorial(5); // 3 Milliseconds
    factorial(10); // 85 Milliseconds
    factorial(12); //  11,942 Milliseconds

I intended on showing `factorial(15)` instead but anything above 12 was too much and crashed the page, thus proving exactly why this needs to be avoided.

我打算显示`factorial(15)`但是12之上的任何东西都太多了，导致页面崩溃，从而证明了为什么需要避免这种情况。

## 总结思想 **(**Closing Thoughts**)** ##

keeping your code as performant as possible may seem like an obvious concern, but I’m sure almost every developer has created double or even triple nested loops at least once because 'it just works’. Big O notation is very necessary in expressing and thinking about complexity is a way we never could before.

使您的代码尽可能保持高性能似乎是一个显而易见的问题，但是我敢肯定，几乎每个开发人员都至少创建过两次甚至三重嵌套循环，因为“它确实有效”。 大O表示法在表达和思考复杂性方面非常必要，这是我们从未有过的方式。

> 翻译自: [https://www.digitalocean.com/community/tutorials/js-big-o-notation][https_www.digitalocean.com_community_tutorials_js-big-o-notation]

javascript 符号

[Google interview]: https://www.youtube.com/watch?v=XKu_SEDAykw
[performance API]: https://www.digitalocean.com/community/tutorials/js-js-performance-api
[quicksort]: https://www.geeksforgeeks.org/quick-sort/
[travelling salesman]: https://en.wikipedia.org/wiki/Travelling_salesman_problem
[https_www.digitalocean.com_community_tutorials_js-big-o-notation]: https://www.digitalocean.com/community/tutorials/js-big-o-notation