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

This article mainly explains "what are the knowledge points about time complexity". Friends who are interested might as well take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the knowledge points about time complexity"?

What exactly is time complexity?

Time complexity is a function that qualitatively describes the running time of the algorithm.

In software development, time complexity is used to facilitate developers to estimate the answer time of the program.

So how to estimate the running time of the program? the number of operating units of the algorithm is usually estimated to represent the time consumed by the program. Here, by default, the running time of each unit of CPU is the same.

Assuming that the problem scale of the algorithm is n, then the number of operation units is represented by the function f (n). With the increase of the data size n, the growth rate of the algorithm execution time is the same as that of f (n). This is called the asymptotic time complexity of the algorithm, which is called O (f (n)).

What is Big O?

What does Big O mean here? when it comes to time complexity, "everyone knows O (n), O (n ^ 2), but we can't tell what Big O is."

The explanation given in the introduction to the algorithm: "Big O is used to represent the upper bound". When it is used as the upper bound of the worst-case running time of the algorithm, it is the upper bound of the running time of arbitrary data input.

The introduction to the same algorithm gives an example: take insertion sorting, for example, the time complexity of insertion sorting is O (n ^ 2).

The form of input data has a great influence on the program operation time. In the case of ordered data, the time complexity is O (n), but if the data is in reverse order, the time complexity of insertion sort is O (n ^ 2), that is, for all input cases, the worst is the time complexity of O (n ^ 2), so it is called O (n ^ 2).

By the same token, if we look at quick sorting again, we all know that quick sort is O (nlogn), but when the data is already ordered, the time complexity of quick sort is O (n ^ 2), "so strictly from the definition of big O, the time complexity of quick sort should be O (n ^ 2)".

But we still say that quick sorting is the time complexity of O (nlogn), which is a default rule in the industry, and the O here represents the general situation, not the strict upper bound. As shown in the figure:

Our main concern is the form of data in general.

The time complexity of the algorithm in the interview refers to the general situation. But if the interviewer and we have an in-depth discussion of the implementation and performance of an algorithm, it is important to keep in mind that the data use cases are different and the time complexity is different.

Differences in different data sizes

The following figure shows the differences in the time complexity of different algorithms under different data input scales.

Time complexity, differences in different data sizes

When deciding which algorithm to use, it is not that the lower the time complexity, the better (because the simplified time complexity ignores the constant term, etc.), consider the size of the data, if the data size is very small, you can even use the O (n ^ 2) algorithm is more appropriate than O (n) (when there are constant terms).

Just like in the figure above, O (5N ^ 2) and O (100n) are obviously better and spend the least time before n is 20.

So why ignore the constant coefficient when calculating the time complexity, that is, O (100n) is the time complexity of O (n), and O (5n ^ 2) is the time complexity of O (n ^ 2), and it is the default that O (n) is better than O (n ^ 2)?

Here we refer to the definition of Big O, "because Big O is the time complexity shown when the data magnitude exceeds a point and the data magnitude is very large." this amount of data is the amount of data in which the constant coefficient no longer plays a decisive role.

For example, 20 in the above picture is that point, as long as the constant coefficient of n is greater than 20, it is no longer decisive.

"so the time complexity we are talking about omits the constant coefficient, because in general, the default data size is large enough. based on this fact, the ranking of the time complexity of the algorithm is as follows:"

O (1) constant order < O (logn) logarithmic order < O (n) linear order < O (n ^ 2) square order < O (n ^ 3) (cubic order) < O (2 ^ n) (exponential order)

But we should also pay attention to the large constant. If the constant is very large, for example, 10 ^ 7, 10 ^ 9, then the constant is a factor that has to be considered.

Simplification of complex expressions

Sometimes when we calculate the time complexity, we find that it is not a simple O (n) or O (n ^ 2), but a complex expression, such as:

O (2 * n ^ 2 + 10 million n + 1000)

Then how to describe the time complexity of this algorithm? one method is the simplification method.

Remove the addition constant term from the run time (because the constant term does not increase the number of operations of the computer because n increases).

O (2 * n ^ 2 + 10 * n)

Remove the constant coefficient (the reason why you can remove the constant term has been explained in detail above).

O (n ^ 2 + n)

Keep only the highest item, remove the n of an order of magnitude smaller (because the data size of n ^ 2 is much larger than n), and finally simplify to:

O (n ^ 2)

If it is difficult to understand this step, you can also extract n and change it to O (n (n) 1), and don't change it to:

O (n ^ 2)

So finally, we say: the time complexity of this algorithm is O (n ^ 2).

We can also use another simplified way of thinking. In fact, when n is greater than 40, the complexity will always be less than O (3 * n ^ 2), O (2 * n ^ 2 + 10 * n + 1000) < O (3 * n ^ 2). So the final time complexity of omitting the constant coefficient is also O (n ^ 2).

What is the base of log in O (logn)?

Usually, the time complexity of this algorithm is logn, so must it be the logarithm of log with 2 as the base n?

In fact, it can be the logarithm with 10 as the base n, or the logarithm with 20 as the base n. "but we uniformly say logn, that is, ignore the description of the base number."

Why can we do this? As shown in the following figure:

If the time complexity of two algorithms is log's logarithm with base 2 as n and log's logarithm with base 10 as logarithm, then if you still remember high school mathematics, you should not understand the logarithm with 2 as base 10 * the logarithm with base 10 as base n.

The logarithm of 10 based on 2 is a constant. As mentioned above, the time complexity of our calculation ignores the coefficient of the constant term.

Abstractly, that is, in the process of calculating the time complexity, the logarithm of log with I as base n is equal to the logarithm of log with j as base n, so it ignores I and says logn directly.

In this way, it should not be difficult to understand why the bottom number is ignored.

Give me an example.

Use this interview question to analyze the time complexity. Topic description: find two identical strings among n strings (assuming there are only two identical strings here).

If it is a violent enumeration, what is the time complexity? is it O (n ^ 2)?

Some students here will ignore the time consumption of string comparison. It is not as simple as int number comparison. In addition to n ^ 2 traversal times, string comparison still consumes m operations (m is the length of the letter string), so the time complexity is O (m * n * n).

Next, think of other ways to solve the problem.

First sort n strings in lexicographic order, and then n strings are ordered, which means that two identical strings are next to each other, and then iterate through n strings, so that two identical strings are found.

If you look at the time complexity of this algorithm, the time complexity of quick sorting is O (nlogn), and the length of the string is still m, so each comparison of fast sorting requires m character comparison operations, that is, O (m * n * logn).

After that, you have to traverse the n strings to find two identical strings, and don't forget to compare the strings when traversing, so the total time complexity is O (m * n * logn + n * m).

We simplify O (m * n * logn + n * m), extract m * n into O (m * n * (logn + 1)), and then omit the constant term. The final time complexity is O (m * n * logn).

Finally, it is obvious that O (m * n * logn) is better than O (m * n * n)!

So sorting the string set first and then traversing it again to find two identical strings is faster than a direct violent enumeration.

This is obtained by analyzing the time complexity of the two algorithms.

At this point, I believe you have a deeper understanding of "what are the knowledge points about time complexity?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.