Time and space complexity of the algorithm

Post hoc analysis

Disadvantages: Different data scale, different machines under the algorithm running time is different, can not calculate the running time

Prior analysis

Large O time complexity

Progressive time complexity As n increases, the running time of the program follows the trend of n change

A few principles

Get rid of constant terms

2(n^2) =n^2

Take the one with the highest time complexity

Test (n) {// For (int I = 0; i < n ; i++){ for(int i = 0; i < n ; i++){ for(int i = 0; i < n ; i++){ print(n); N ^2 for(int I = 0; i < n ; i++){ for(int i = 0; i < n ; i++){ print(n); If (int I = 0; i < n ; i++){ print(n); }}Copy the code

This code has time complexity of n^3+n^2+n

When n is large enough, n^2 and n are too small to be ignored compared to n^3

Common complexity

o(1)

i = i + 1;
Copy the code

o(n)

test(n){ for(int i = 0 ; i < n; i++){ print(i); }}Copy the code

o(n^2)

test(n){ for(int i = 0 ; i < n; i++){ print(i); for(int j = 0 ; j < n; j++){ print(i); }}}Copy the code

o(log2n)

PS: If ax =N (a>0, and a≠1), then the number x is called the logarithm base A of N, denoted by x=logaN, and pronounced with base A of N, where a is called the base of the logarithm, and N is called the true number.

test(n) { int i = 1; while (i <= n) { i = 2 * i; }}Copy the code

As the number of cycles increases, the value of I changes as follows

So the logarithm function says 2 to the I is equal to n, and I is equal to log base 2n

Best case time complexity

The time complexity of the case where the data is relatively ordered

Worst-case time complexity

Complete data disorder

Spatial complexity

N-independent code space complexity can be ignored

Space complexity O(n)

Test (n) {// Create an array of length n in memory List array = List(n); print(array.length); }Copy the code