[time complexity and space complexity]

Time complexity and space complexity

Complexity analysis

Measure the advantages and disadvantages of different algorithms , It is mainly considered according to the space and time occupied by the algorithm . however , There will be no perfect code in the world , Neither consumes the most time , It doesn't take up the most space , You can't have both fish and bear paws , Then we need to find a balance , Make it possible to write a more perfect code .

Time complexity

Time complexity ： Analyze the efficiency of algorithm execution

Common time complexity

O(1) < O(nlogn)<O(n) < O(n2) < O(2^n) < O(n!)

1.O(1)

int fun(int n)
{
    
	int i = n;
	int j = 3*n;
	return i+j;
}

2.O(nlogn)

int fun(int n)
{
    
	int i = 1;
	while(i<= n)
	{
    
		i = i*2;
	}
	return i;
}

3.O(n)

int fun(int n)
{
    
	sum = 0;
	for(int i = 0;i<n;i++)
	{
    
		sum += i;
	}
	return sum;
}

4.O(mlogn)

int fun(int m,int n)
{
    
	sum = 0;
	for(int i = 0;i<m;i++)
	{
    
		for(int j = 0;j<n;j++)
		{
    
			sum+= i*j;
			j = j*2;
		}
	}
	return sum;
}

5.O(n2)

int fun(int n)
{
    
	sum = 0;
	for(int i = 0;i<n;i++)
	{
    
		for(int j =0;j<n;j++)
		{
    
			ssum+= i*j;
		}
	}
	return sum;
}

Spatial complexity

Size of memory space occupied by algorithm ： The variable statement does not occupy space
Common spatial complexity O(1) <O(n) < O(n2)

1.O(1)

int fun(int n)
{
    
	sum = 0;
	for(int i = 0;i<n;i++)
	{
    
		sum += i;
	}
	return sum;
}

2.O(n)

int fun(int n)
{
    
	int arr[N];
	int i = 0;
	while(i<= N)
	{
    
		i = i*2;
	}
	return i;
}

3.O(MN)

int fun(int m,int n)
{
    
	int arr[M][N];
	for(int i = 0;i<m;i++)
	{
    
		for(int j = 0;j>=n;j++)
		{
    
			sum += arr[i][j];
		}
	}
	return sum;
}