1. Time complexity

1)Constant order O (1)

No matter how many lines the code executes, the time complexity of the code is O(1) as long as there are no complex structures such as loops.

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
Copy the code

When the above code is executed, its consumption time does not increase with the growth of a variable, so no matter how long the code is, even if it has tens of thousands of lines, its time complexity can be expressed by O(1).

2) Linear order O (n)
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
Copy the code

This code, the code inside the for loop is going to execute n times, so the time it takes is going to change with n, so this kind of code can be expressed as O(n).

3) The logarithmic order O (logN)

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

As you can see from the code above, in the while loop, every time I is multiplied by 2, I gets closer and closer to n. Let’s try to solve for it, assuming that after x cycles, I is greater than 2, and then the cycle is out, which means that 2 to the x is equal to n, so x is equal to log base 2 to the n

So when I loop log2 to the n times, I’m done with this code. So the time complexity of this code is O(logn).

4) Linear log order O(nlogN)

Linear log order O(N logn) is actually very easy to understand, so if I loop O(logn) code N times, it’s N times O(logn), which is order N (logn).

Take the above code with a few modifications for example:

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2; }}Copy the code
5) Squared square order O (n)

Order O(n ^ 2) is easier to understand, because if you nested the code O(n) again, it would be O(n ^ 2) in time. For example:

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++) { j = i; j++; }}Copy the code

This code is actually nested with two layers of n loops, and its time complexity is O(n*n), namely O(n²). If n of one layer of the loop is changed to M, that is:


for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++) { j = i; j++; }}Copy the code

So the time is order m times n.

6) Cubic order O (n) after 、Order N to the K.

Just think of it as O(n ^ 2) up here, O(n ^ 3) equals three n cycles, and so on.

reference

  • zhuanlan.zhihu.com/p/50479555

conclusion