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

This article introduces the knowledge of "how to understand time complexity and space complexity". In the operation of actual cases, many people will encounter such a dilemma. Next, 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!

We can often see such a description: software = data structure + algorithm, which shows the importance of algorithm foundation to a programmer. There are two basic concepts in the algorithm: time complexity and space complexity.

Time complexity: describe the time it takes to execute the algorithm. The shorter the time, the lower the time complexity, and the better the algorithm is.

Space complexity: describe the memory space occupied by the algorithm. The less the memory is, the lower the space complexity is, and the better the algorithm is.

Therefore, time complexity and space complexity are the main indicators to evaluate the performance of an algorithm. So how to calculate the time complexity and space complexity of an algorithm?

Simply understand, computing time complexity is to evaluate how many lines of code have been executed after an algorithm is completed, that is, the time consumed by the algorithm, but how to express it mathematically?

Suppose there is an algorithm that needs to perform n operations, and we use T (n) to denote the size of the algorithm (for example, when you loop 10 times, when you loop out 10 times Hello World;n=100, you loop out Hello World 100 times). If there is a function f (n), which represents the number of times the algorithm needs to be executed with the change of n, then O (f (n)) is the time complexity of the algorithm when T (n) = O (f (n)).

For example, a normal loop:

Public int calc (int n) {int total = 0; for (int I = 0; I < n; iTunes +) {total + = I;} return total;}

The greater the n, the more the number of cycles, the more time it takes, that is, f (n) increases linearly with n. Then the execution time of the algorithm T (n) = O (n), that is, the time complexity is O (n).

Or, for example, a double-layer loop:

Public int calc (int n) {int total = 0; for (int I = 0; I < n; iTunes +) {for (int j = 0; j < n; Jake +) {total + = j;}} return total;}

Every time the outer loop is looped, the inner loop is looped n times, so the total number of code loops is n. Then the execution time of the algorithm T (n) = O (n ^ 2), that is, the time complexity is O (n ^ 2).

Generally speaking, the time complexity is used to evaluate the growth rate of the time consumed by the algorithm as n increases, rather than accurately calculate the time consumed, in fact, it can not be accurately calculated. Since it is an evaluation, we only need to keep the factor that has the greatest impact on the consumption time of the f (n) function.

For example, if there is a function f (n) = 2 * n ^ 3, coefficient 2 has little effect on the growth rate of f (n) function, so the time complexity of the algorithm T (n) = O (n ^ 3), that is, ignore the influence of constant coefficient on the growth rate.

For example, in a block of code without a loop, there are only three lines of output code:

Public void print () {System.out.println ("Hello River Xiansen");}

That is, T (n) = 3, is a constant, and the effect of the constant on the growth rate can be ignored, then the time complexity of the code block is O (1).

Looking at another example, calculate the time complexity of the following code block:

Public void print (int n) {for (int I = 0; I < n; iTunes +) {for (int j = I; j < n; jade +) {System.out.println ("Hello Hsiansen");}

The inner layer circulates n times when the iTunes 0, and the inner layer circulates once when the iTunes 1, so as to extrapolate it, and when the iTunes-1, the inner layer circulates once. Then the total number of cycles T (n) = n + (n Mel 1) + (n Mel 1) +. + 1% n (n ^ 1) / 2 = n ^ n / 2+n/2, ignoring the constant term and the factors that have little influence on the growth rate, and leaving only the factor with the greatest influence, then the time complexity of the algorithm is O (n ^ 2).

Common order of magnitude of time complexity:

Constant order O (1)

Logarithmic order O (logN)

Linear order O (n)

Linear logarithmic order O (nlogN)

Square order O (n ²)

Cubic order O (n ³)

O (n ^ k) to the power of K

Exponential order (2 ^ n)

In the time complexity of the above algorithm, with the increase of n, the faster the growth rate of f (n), the lower the efficiency of the algorithm. That is, the time consumed by the algorithm O (1) < O (logN) < O (n) < O (nlogN) < O (n ²) < O (n ³) < O (n ^ k) < O (2 ^ n).

If you want to find a number in an array, the easiest way is to loop through it:

Public boolean search (int m) {int [] arr = new int [] {3, 5, 7, 1, 2, 6, 4, 9}; for (int I = 0; I < arr.length; I +) {if (m = = arr [I]) {return true;}} return false;}

If you are looking for the first number of an array (3 in this example), you only need a loop to find it, with a time complexity of O (1). But if the number you are looking for is at the end of the array (9 in this example), you must go through an arr.length loop with a time complexity of O (n), where n is the length of the array. So what is the time complexity of this code block?

Generally speaking, in the absence of special instructions, time complexity refers to the worst time complexity, because there is no worse situation. So the time complexity of this code block is O (n).

Time complexity describes the time consumption trend of the algorithm, similarly, space complexity describes the trend of temporary memory consumption of the algorithm while running, which is generally defined by S (n), recorded as S (n) = O (fn).

As for the specific quality of the evaluation algorithm, it is necessary to analyze the specific situation. Sometimes we trade time for space, sometimes we trade space for time, and sometimes we need to consider both time and space complexity.

In short, the specific analysis of specific problems, but we must understand the analysis process of time complexity and space complexity.

This is the end of "how to understand time complexity and space complexity". 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.