Deep analysis of time complexity

For the comrades who study algorithms , There is no lack of learning about the complexity of time , The learning of time complexity is recorded here , If there is any mistake , Please comment .

Literally , Is the running time of an algorithm , Many little friends thought of running the algorithm program again , Then the time consumed will be known naturally , This way is possible , But there are many drawbacks , It is easily affected by the operating environment , The performance varies greatly , It also has a bearing on the size of the data used . So I still can't run it completely .

Such a universal way was born ,「 Big O Symbolic representation 」, stay Big O In symbolic representation , The formula of time complexity is ： T(n) = O( f(n) ), among f(n) Represents the sum of execution times per line of code , and O Represents a positive proportional relationship , The full name of this formula is ： Progressive time complexity of the algorithm . This method is not used to truly represent the execution time of the algorithm , Indicates the trend of the increase in execution time .

1. Constant order O(1)

int i = 1; int j = 2; ++i; j++; int m = i + j;

2. Linear order O(n)

for(i=1; i<=n; ++i)

{

j = i;

j++;

}

for The code in the loop will execute n All over , So it takes time to n Changed by , This kind of code can be used O(n) To represent its time complexity .

3. Logarithmic order O(logN)

int i = 1;

while(i<n)

{

i = i * 2;

}

stay while Inside the loop , Every time i multiply 2, After finishing ,i distance n It's getting closer . Hypothetical cycle x After that ,i Greater than 2 了 , At this point, the cycle exits , in other words 2 Of x The second power equals n, that x = log2^n That is to say, when the cycle log2^n Later , That's the end of the code . So the time complexity of this code is ：O(logn)

4. Linear logarithmic order O(nlogN)

for(m=1; m<n; m++)

{

i = 1;

while(i<n)

{

i = i * 2;

}

}

Linear logarithmic order O(nlogN) It's really easy to understand , Time complexity is O(logn) Code loop for N All over , So its time complexity is n * O(logN), That's it. O(nlogN).