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

This article introduces the relevant knowledge of "what is the Big O symbol". In the operation of actual cases, many people will encounter such a dilemma. Then 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!

Time complexity vs space complexity

The large O symbol is used to measure time complexity and space complexity.

Time complexity: the number of minor operations that must be performed to complete the overall operation.

Space complexity: the amount of additional memory required to run the code in the algorithm-often referred to as auxiliary space complexity, that is, it only refers to the space occupied by the algorithm, not the input.

Complexity type

Time complexity can be divided into several different types. The following are some of the more common types:

Constant order / O (1): no matter how large the dataset, it is always executed in the same time or space.

Logarithmic order / O (log n): the power that must be increased by fixed data in order to obtain a given data.

Linear order / O (n): complexity is directly related to the size of the input data.

Linear logarithmic order / O (nlog n): performs an O (log n) operation on each item in the input.

Square order / O (n ²): performance is proportional to the square size of the input data.

Image source: Colt Steele's JavaScript algorithm and data structure master class

General rules that help to determine the complexity of time and space

These rules are the direction in which they can work, but they are not guaranteed to work every time.

Determine the time complexity:

Arithmetic operation is constant

Variable is assigned to a constant

Access elements in an array (by index) or object (by key) are constant

In a loop, complexity is the length of the loop multiplied by the complexity of anything that happens within the loop.

Determine the space complexity:

Most primitives are constant spaces. Boolean constants, numbers, undefined variables, null.)

The string requires O (n) space, where n is the length of the string.

The reference type is usually O (n), where n is the array length or number of keys of the object.

Let's look at some examples.

Image source: Colt Steele's JavaScript algorithm and data structure master class

As for space complexity, addUpToN has two variable assignments (total and I). When the loop completes its operation, these variables are reassigned, but the space occupied by these variables remains the same regardless of the size of the input dataset. The space complexity will be constant order / O (1).

Here are three simple operations (multiplication, addition, division). Regardless of the size of n, the number of operations remains the same. The time complexity of addUpToNAgain is constant order / O (1).

Only one value is returned at this time. Entering a value does not change the space allocated to this function. Therefore, the space complexity is also linear order / O (1).

Here, there is a linear order O (n) operation nested in another O (n) operation. When the n value entered is scaled, the run time changes accordingly. The time complexity of sumEachPair is square order / O (n ²).

Reviewing the general rules described earlier, this case corresponds to one of them: the reference type is generally O (n), and the amount of space required is directly related to the input value. The space complexity is linear order / O (n).

To analyze the performance of the algorithm, you can use the big O symbol to help the analysis, the big O symbol can deepen the understanding of the time and space requirements of the algorithm.

In short, programmers should understand the time and space complexity of the code they write, and then ensure that the running time and execution speed are as fast as possible. at the same time, ensure that the code is always within the physical storage range of its running system, and "refine" to become an efficient programmer.

This is the end of "what is the Big O symbol". Thank you for your 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.