Time complexity and space complexity

Time complexity

When doing algorithm analysis , Usually we should consider the time and space used by the algorithm .
The time complexity of the algorithm is generally recorded as ：O( f(n)), Called big O Notation .
f(n) The size of the problem solved for this algorithm n A function of , It can also be regarded as the number of times the function runs .

Common time complexity

Common time complexity ：

Number of executions	rank	Informal terms
8	O(1)	Constant order
n+1	O(n)	Linear order
log2^n + 2n + 1	O(log n)	Logarithmic order
n2 + log2^n + 2n + 1	O(n2)	Square order
n log2^n + 2n	O(n log n)	n log n rank
4n3 + 2n + 1	O(n3)	Cubic order
2n	O(2n)	Exponential order

Time complexity sort

O(1)<O(log n)<O(n)< O(n log n) < O(n²) < O(n³)< O(2ⁿ)< O(n !)< O(nⁿ)

---

Derivation time complexity O Methods

Derivation is great O Methods ：

1. With constant 1 Replace all the addition constants in runtime .
2. In the modified run times function , It retains the highest order .
3. If the highest order is not 1, Remove the constant of the highest order term .

At this time, the value obtained is the maximum O rank .

---

Several common time complexities

1. Constant order

int main()
{
    
      int i=0,j=0; 
      i=i+1;
      j=J+1;
      i=i+j;
}

As shown in the code above , A total of three statements are executed , The number of runs function is f(n)=3. According to the derivation time complexity O The method of calculation , The available time complexity is O(1).

int sum = 0,n = 10000;
sum = n/2;
sum = n/2;
sum = n/2;
sum = n/2;
sum = n/2;
sum = n/2;
sum = n/2;
sum = n/2;
printf("%d",sum);

In the top code , No matter what n What is the size of ,sum = n/2 Yes 8 Time , Number of executions and n It's not about size , For algorithms with constant execution time .
For this kind of time constant Algorithm , We call it having O(1) Time complexity of , Constant order .

2. Linear order

Usually by analyzing the operation of the cycle structure , To find the time complexity .

int nums[]={
    1,2,3,4,5,6,7,8,9} , n=0;
n = sizeof(nums)/sizeof(nums[0]);// seek nums Size of array 

for(int i = 0;i<n;i++)
{
    
  nums[i]+=1;
}

In this function , sentence nums[i]+=1 The time complexity is O(1), Yes n Time , Number of executions and n of .
Combined with the derivation time complexity O Methods available , The time complexity is O(n).

3. Logarithmic order

int count = 1;
while(count<n)
{
    
count = count *2;
}

if n=10, Function execution 5 Time ;
if n=100, Function execution 10 Time ;
if n=10000, Function execution 100 Time ;
The number of executions varies with n Change by change .
The time complexity is O(lon2^n), After derivation, the O The time complexity of the method is O(log n).

Two points search ：

while (left < right) {
    	
        int mid = left + (right - left) / 2;
        if (nums[middle] > target) {
    
            right = middle - 1;
        } else if (nums[middle] < target) {
    
            left = middle + 1;
        } else {
    	
            return mid;
        }
    }

Binary search is a common time complexity of O(log n) The algorithm of .

4. Square order

The code below is loop nesting , If the statement time complexity in the loop is O(1), The number of times the whole function is executed is n, The overall time complexity is O(n).
If the statement in the loop is also time complexity O(n) The loop statement of , The number of times the whole function is executed is n*n=n^2, Then the overall time complexity is O(n ^ 2).

int i,j;
for(i=0;i<n;i++)
{
    
   for(j=0;j<n;j++)
  {
    
     j+=1;
  }
}

The common time complexity is O(n^2) The algorithm of
Bubble sort （ The time complexity is O(n^2)）：

void bubbleSort(int* arr, int arrSize)// Array   The length of the array 
{
    
	int i, j;  
	for (i = 0; i < arrSize; i++)
	{
       if (!b){
     break; }
		for (j = 0;j<arrSize-i-1;j++) 
		{
    
			int temp;
			if (arr[j] > arr[j + 1])
			{
    
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

Spatial complexity

The spatial complexity of the algorithm is realized by calculating the storage space required by the algorithm , The calculation formula of algorithm space complexity : S(n)= O(f(n)), among ,n For the scale of the problem ,f(n) For the statement about n The function of the storage space occupied .

In general , When a program is executed on the machine , In addition to the need to store the instructions of the program itself 、 constant 、 Variables and input data , It also needs to store the storage unit for data operation . If the space occupied by the input data only depends on the problem itself , It's not about algorithms , In this way, we only need to analyze the auxiliary units needed in the implementation of the algorithm . If the auxiliary space needed by the algorithm is a constant relative to the amount of input data , This algorithm is called in situ work , The space complexity is O(1).

Usually , We all use “ Time complexity ” To refer to the need for runtime , Use “ Spatial complexity ” It refers to the demand for space . When using... Without qualifiers “ Complexity ” when , It's usually time complexity .