How to Learn Algorithmic Complexity with JavaScript

How to Learn Algorithmic Complexity with JavaScript

Overview

In this article, we'll explore what terms like "quadratic" and "n log(n)" mean in the context of algorithms.

In the examples that follow, I will refer to these two arrays, one containing 5 elements and the other containing 50 elements. I’ll also use JavaScript’s handy performance API to measure the difference in execution time.

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];

What is Big O notation?

Big O notation is a way to express the overall increase in difficulty of a computational task as the size of the data set increases. Although there are other notations, big O notation is generally the most commonly used because it focuses on the worst-case scenario, which is easier to quantify and consider. The worst case scenario means the one that requires the most operations to complete the task; if you can unscramble the cube in under a second, you can't say you did the best job if you only twisted it once.

This is very useful as you get further into algorithms, because as you write code you understand this relationship and know where the time is being spent.

As you learn more about Big O notation, you may see different variations of the following diagram. We want to keep the complexity as low as possible, preferably not exceeding O(n).

O(1)

This is the ideal situation, no matter how many projects there are, whether it's 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 an item at a specific index, adding child elements, etc. 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 a one-to-one relationship between the size of the data and the time to complete. So if you have 1,000 array items, it will take 1,000 times as long.

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 we all fall into. Do you need to find a matching pair for every item in the array? Putting loops within loops is a great way to turn an array of 1,000 items into a million operation searches that will make your browser unresponsive. It is better to do 2,000 operations in two separate loops than to do a million operations using a doubly nested loop.

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 the best metaphor for logarithmic growth is to imagine looking up a word like "notation" in the dictionary. You don't search term by term, but first find the "N" section, then the "OPQ" page, and then search the list alphabetically until you find a match.

With this "divide and conquer" approach, the time to find something will still vary with the size of the dictionary, but it's nowhere near O(n). Because it searches progressively more specific parts without looking at the bulk of the data, searching a thousand items might require less than 10 operations, and a million items might require less than 20 operations, maximizing 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!)

The worst possibility is factorial growth. The classic example is the traveling salesman problem. If you are traveling between many cities of varying distances, how do you find the shortest route between all the cities back to your starting point? A brute force approach would be to check all possible route distances between each city, which is a factorial and will quickly get out of hand.

Because this problem can quickly become very complex, we will demonstrate this complexity with a short recursive function. This function multiplies a number by itself and then subtracts 1 from the number. Each number in the factorial is calculated this way until it reaches 0, and each recursive layer adds its product to the original number.

Factorials are simply the products starting at 1 and going up to that number. Then 6! is 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 had intended to display factorial(15), but values ​​above 12 were too many and crashed the page, demonstrating why this needs to be avoided.

Conclusion

It seems like an indisputable fact that we need to write performant code, but I’m sure almost every developer has created at least double or even triple nested loops because “it just works.” Big O notation is essential in expressing and thinking about complexity in a way that we never had before.

The above is the details of how to learn algorithm complexity with JavaScript. For more information about JS algorithm complexity, please pay attention to other related articles on 123WORDPRESS.COM!

You may also be interested in:
  • Using JS to implement binary tree traversal algorithm example code
  • How to use JavaScript to implement sorting algorithms
  • JavaScript programming through Matlab centroid algorithm positioning learning
  • Binary Search Tree Algorithm Tutorial for JavaScript Beginners
  • Summary of seven sorting algorithms implemented in JavaScript (recommended!)
  • A brief discussion on an efficient algorithm for constructing tree structures in JavaScript
  • js implements the algorithm for specifying the order and amount of red envelopes
  • How to use javascript to do simple algorithms

<<:  Randomly generate an eight-digit discount code and save it to the MySQL database

>>:  Mysql5.7 my.ini file loading path and data location modification method under windows7

Recommend

How to install Jenkins using Docker

Table of contents 1. Pull the image 2. Create a l...

A few front-end practice summaries of Alipay's new homepage

Of course, it also includes some personal experien...

Explanation of factors affecting database performance in MySQL

A story about database performance During the int...

Create an SSL certificate that can be used in nginx and IIS

Table of contents Creating an SSL Certificate 1. ...

Vue implements horizontal scrolling of marquee style text

This article shares the specific code for Vue to ...

WeChat applet implements calculator function

WeChat Mini Programs are becoming more and more p...

A comprehensive analysis of what Nginx can do

Preface This article only focuses on what Nginx c...

The perfect solution for MySql version problem sql_mode=only_full_group_by

1. Check sql_mode select @@sql_mode The queried v...

React dva implementation code

Table of contents dva Using dva Implementing DVA ...

HTML table markup tutorial (6): dark border color attribute BORDERCOLORDARK

In a table, you can define the color of the lower...

MySQL 5.7.24 installation and configuration method graphic tutorial

MySQL is the most popular relational database man...

HTML Tutorial: Collection of commonly used HTML tags (4)

Related articles: Beginners learn some HTML tags ...

Methods and techniques for designing an interesting website (picture)

Have you ever encountered a situation where we hav...

Detailed explanation of flex and position compatibility mining notes

Today I had some free time to write a website for...