Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "how to use JavaScript to learn algorithm complexity". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

In this article, we will explore the meaning of terms such as "quadratic power" and "n log (n)" in the algorithm.

In later examples, I will refer to these two arrays, one containing 5 elements and the other containing 50 elements. I will also use the convenient performance API in JavaScript to measure the difference in execution time.

Const smArr = [5, 3, 2, 35, 2]; const bigArr = [5, 3, 2, 35, 2, 5, 2, 35, 2, 5, 3, 2, 5, 3, 2, 3, 3, 3, 3, 2, 5, 3, 3, 3, 2, 35, 2, 3, 3, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 35, 2, 5, 3, 3, 35, 2]

What is the Big O symbol?

Big O representation is a way to indicate that the overall difficulty of computing tasks increases with the increase of data sets. Although there are other representations, the big O notation is usually the most commonly used because it focuses on the worst-case scenario and is easier to quantify and consider. The worst-case scenario means that it takes the most operations to complete the task; if you can resume disrupting the Rubik's cube in a second, you can't say you're the best if you've only twisted it once.

When you learn more about the algorithm, you will find this very useful, because when you understand the relationship and write the code, you will know where the time is spent.

As you learn more about the Big O notation, you may see different changes in the following figure. We want to keep the complexity as low as possible, preferably to avoid exceeding O (n).

O (1)

This is an ideal situation, no matter how many projects, whether one or a million, the amount of time to complete will remain the same. Most operations that perform a single operation are O (1). Writing data to an array, getting items at a specific index, adding child elements, and so on will all take the same amount of time, regardless of the length of the array.

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 grow linearly because there is an one-to-one relationship between the size of the data and the time it takes to complete. So if you have 1000 array items, it will take 1000 times longer.

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)

Exponential growth is a trap, and we've all fallen into it. Do you need to find matching pairs for each item in the array? Putting a loop in a loop is a good way to turn an array of 1000 items into a million action searches, which will make your browser unresponsive. Instead of using a double nested loop for a million operations, it is best to perform 2000 operations in two separate loops.

Const A1 = performance.now (); smArr.forEach () = > {arr2.forEach (item = > console.log (item));}); const a2 = performance.now (); console.log (`Time: ${a2-A1} `); / / 8 Milliseconds const b1 = performance.now (); bigArr.forEach () = > {arr2.forEach (item = > console.log (item));}); const b2 = performance.now (); console.log (`Time: ${b2-b1}`) / / 307 Milliseconds

O (log n)

I think a better metaphor for logarithmic growth is to imagine looking up words like "notation" in a dictionary. Instead of searching entry by entry, you will find the "N" section first, then the "OPQ" page, and then search the list alphabetically until you find a match.

Through this divide-and-conquer approach, the time to find something still varies depending on the size of the dictionary, but far less than O (n). Because it gradually searches for more specific parts without looking at most of the data, searching for a thousand items may require less than 10 operations, while a million items may require less than 20 operations, which maximizes your efficiency.

In this example, we can do a simple quick sort.

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!) 最糟糕的一种可能性是析因增长。最经典的例子就是旅行的推销员问题。如果你要在很多距离不同的城市之间旅行，如何找到在所有城市之间返回起点的最短路线?暴力方法将是检查每个城市之间所有可能的路线距离，这是一个阶乘并且很快就会失控。 由于这个问题很快会变得非常复杂，因此我们将通过简短的递归函数演示这种复杂性。这个函数会将一个数字去乘以函数自己，然后将数字减去1。阶乘中的每个数字都会这样计算，直到为 0，并且每个递归层都会把其乘积添加到原始数字中。 阶乘只是从 1 开始直至该数字的乘积。那么 6!是 1x2x3x4x5x6 = 720。 const factorial = n =>

{let num = n; if (n = = 0) return 1 for (let I = 0; I < n; iTunes +) {num = n * factorial (n-1);}; return num;}; factorial (1); / / 2 Milliseconds factorial (5); / / 3 Milliseconds factorial (10); / / 85 Milliseconds factorial (12); / / 11942 Milliseconds

I was going to display factorial (15), but there were too many values above 12 and crashed the page, which proves why this needs to be avoided.

"how to use JavaScript to learn algorithm complexity" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.