Learn algorithm complexity through JavaScript

Tram Ho

1. What is Big O Notation ?

Big O notation is just one way of expressing computational complexity when you perform a task

Despite the other symbols, Big O notation is most often used because it focuses on the worst-case scenario, making it easier to quantify and exchange (there are also Big Theta, Big Omega).

The worst case means that it takes the most time as well as the memory to complete the task, because with the good cases, there is no need to bother.

As you learn more about Big O notation, you can see many different and better variations of this chart.

  • The image above is the complexity between sorting algorithms

The next section will be examples to further clarify the complexity of the algorithm

The data to perform the example will be two small and large data arrays to verify the complexity in each algorithm depending on the size of the data.

In addition, to be able to measure the time to perform tasks will have to use the JS performance API

Enough already, let’s begin !!!

2. O (1)

This is the ideal algorithm complexity, no matter how many items in the membrane, whether one or a million, the time to complete will remain unchanged because the task only needs to be done once.

Pushing an array, getting an item at a specific index, adding a child element, etc., all will take the same amount of time regardless of the length of the array.

3. O (log n)

The best example of logarithmic complexity is to imagine finding a word in a dictionary (aphabet sorted). You will start searching at any location, for example the letter N , and then compare the position with the position of the result you want to be able to adjust the search up or down (same as mysql select a record with indexing)

With this chia rẽ để trị approach, the amount of time it takes to find something will still vary depending on the size of the dictionary but nowhere near the O (n) ratio. Because it searches in specific sections gradually without looking at most data, searching in a thousand items can take less than 10 operations while a million can take less than 20, helping you. The search is faster

In this example, we can perform a simple quicksort.

4. O (n)

By default, all loops are an example of linearity in O(n) complexity because there is a one-to-one relationship between data size and completion time.

So an array with entries more than 1000 times will take exactly 1,000 times longer.

5. O (n ^ 2)

The exponential complexity is a trap that we all fall into at least once.

For example, need to find a matching value for each item in an array? Putting a loop inside a loop is a great way to turn an array of 1,000 items into a million search results that will lead to freezing your browser.

6. O (n!)

Finally, one of the worst possibilities, factorial complexity O(n!) .

For example, a textbook-style example is a problem with travel salespeople. If you have a series of cities with different distances, how do you find the shortest possible path between all of them and return to the starting point?

The mortar method will be to test the distance between the connection points between each city, this will be a factorial of the results and it is beyond our ability.

Because that problem becomes very complicated very quickly, we will prove this complexity by a short recursive function.

This function multiplies a number by its function, minus a number. Each digit in our factorial will run its own function until it reaches zero, with each recursive class appending its front to our original number. So 3 multiplied by 2 running functions multiplied by 1 replay is stopped at 0, returning 6 (3 2 1 = 6)

For example:

We can see how complicated this algorithm is, how much processing time is between 10 and 12.

I thought I was going to give it 15 but by 12 the personal computer could not stand it

7. Conclusion

Based on the above examples, we can see that keeping your code as efficient as possible is really necessary

We always have to keep the algorithmic complexity in our code lines as low as possible, ideally avoiding everything on O (n) .

Above is my research on Big O Notation , hoping to help everyone

Thanks for watching

8. References

https://en.wikipedia.org/wiki/Big_O_notation

Big O notation

Js performance API

I was dumped because I didn’t know Big O

Share the news now

Source : Viblo