Personal views on time complexity

Concept

In computer science , time complexity , also called Time complexity , Algorithm Time complexity It's a function , It qualitatively describes the running time of the algorithm . This is a function of the length of the string representing the input value of the algorithm . Time complexity is often large O Symbolic representation , The lower order and first term coefficients of this function are not included . When using this method , Time complexity can be called asymptotic , That is, the size of the input value is approaching infinity .

Constant order

for example :

#include <cstdio>
using namespace std;

int main () {
    
    int a, b;
    scanf ("%d %d", &a, &b);
    int c = a + b;
    printf ("%d", c);
    return 0;
}

This code , No matter what you enter a and b What is the value of , Will only run once , So write it down as Constant order : $O(1)$

Linear order

for example :

#include <cstdio>
using namespace std;

int main () {
    
    int n, sum = 0;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
    
        sum += n;
    }
    printf ("%d", sum);
    return 0;
}

This code , The number of runs is determined by n decision , So write it down as Linear order : $O(n)$

Square order

for example :

#include <cstdio>
using namespace std;

int main () {
    
    int n, sum = 0;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
    
        for (int j = 1; j <= n; j ++) {
    
        	sum += i * j;
		}
    }
    printf ("%d", sum);
    return 0;
}

This code , The number of runs is determined by n decision , But there are two nested loops , So write it down as Square order : $O(n^2)$

Similarly , If nested k Secondary cycle , Write it down as k Order of second order : $O(n^k)$

Logarithmic order

for example :

#include <cstdio>
using namespace std;

int main () {
    
    int n, sum = 0;
    scanf ("%d", &n);
    while (n != 0) {
    
		n /= 2, sum ++;
	}
    printf ("%d", sum);
    return 0;
}

This code , The number of runs is calculated n How many of them 2, So write it down as Logarithmic order : $O(\log n)$

Similarly , If we combine linear order and logarithmic order , Write it down as Linear logarithmic order : $O(n\log n)$

Exponential order

for example :

#include <cstdio>
using namespace std;

long long digui (int n) {
    
	if (n == 1 || n == 2) {
    
		return 1;
	}
	return digui (n - 1) + digui (n - 2);
}

int main () {
    
    int n, sum = 0;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
    
        sum += n;
    }
    printf ("%d", sum);
    return 0;
}

This code , Fibonacci series , Need to compute $2^n$ Time ( No explanation here ), Write it down as Exponential order : $O(2^n)$

summary

About the analysis of time complexity, the author is here , If there are mistakes or omissions , Please bosses Don't hesitate to correct .