Preface

This paper introduces the problems related to time complexity and space complexity , Use common examples to analyze , loop 、 recursive 、 Fibonacci 、 Factorial 、 Bubble sort 、 Binary search, etc .

One 、 Algorithm efficiency

After the algorithm is written into an executable program , The runtime needs time and space resources. Generally, the quality of an algorithm is measured , Generally, time complexity is measured from the two dimensions of time and space. Time complexity mainly measures the speed of an algorithm , The spatial complexity mainly measures the additional space required for the operation of an algorithm . But with the development of computers , The storage capacity has reached a high level , So we don't pay much attention to spatial complexity now , Often trade space for time .

Two 、 Time complexity

1. Definition of time complexity

In computer science , The time complexity of the algorithm is a function . It quantitatively describes the running time of the algorithm . The time that an algorithm takes to execute , In theory , It can't be worked out , Only you put the program on the machine and run , To know . But do we need to test every algorithm ？ This is not too much trouble , That's why we have the time complexity analysis . The time taken by an algorithm is directly proportional to the number of executions , The number of basic operations executed in the algorithm , Time complexity of the algorithm .

2. A representation of time complexity

We usually use big O The time complexity of progressive representation is simple 0 The representation is , The highest order term of the calculated number of operations .
In general, we focus on the worst-case operation of the algorithm .

3. FAQ time complexity analysis

void test1(int N)
{
    
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
    
		++count;
	}
	int M = 10;
	while (M--)
	{
    
		++count;
	}
	printf("%d\n", count);

}

Yes 2*N+10 Time , Time complexity O(N)

void test2(int M,int N)
{
    

	int count = 0;
	for (int k = 0; k < M; ++k)
	{
    
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
    
		++count;
	}
	printf("%d\n", count);
}

Time complexity O(M+N)

void test3(int N)
{
    
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
    
		++count;
	}
	printf("%d\n", count);
}

Time complexity O(1)( Yes 100 Time )

long long Fib(size_t N)
{
    
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}

This is a Fibonacci sequence , The time complexity is very large O（2^N)
This algorithm actually has only theoretical significance , It has little practical significance , The complexity of the algorithm is too large
There are many ways to replace this , For example, loop iteration , Dynamic planning, etc

void BubbleSort(int* a, int n)
{
    
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
    
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
    
			if (a[i - 1] > a[i])
			{
    
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

Obviously, this is a bubble sort with a time complexity of O(N^2)

int BinarySearch(int* a, int n, int x)
{
    
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin and end It's a left closed right closed interval , So there is = Number 
	while (begin <= end)
	{
    
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

Obviously, it's a binary search , The time complexity is O(logN)
Binary search is a very powerful algorithm ,
But the disadvantages are obvious ,
Sort before searching , Also, ensure that the data address is continuous

3、 ... and 、 Spatial complexity

1. Spatial complexity definition

Spatial complexity is also a mathematical expression , It is a measure of the amount of storage space temporarily occupied by an algorithm during operation .
Space complexity is not how much the program takes up bytes Space , Because it doesn't make much sense either , So spatial complexity is the number of variables .
Spatial complexity calculation rules are basically similar to practical complexity , Also use large O Progressive representation .

2. Characteristics of spatial complexity

Be careful ： Stack space required for function runtime
( Store parameters 、 local variable 、 Some register information, etc ) It has been determined during compilation ,
Therefore, the spatial complexity is mainly determined by the additional space explicitly requested by the function at run time .

3. Frequently asked questions: space complexity analysis

void BubbleSort(int* a, int n)
{
    
	assert(a);// Pointer dereference must first assert , Prevent pointer from being null 
	for (size_t end = n; end > 0; --end)
	{
    
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
    
			if (a[i - 1] > a[i])
			{
    
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
    
			break;
		}
	}
}

Spatial complexity O(1) Constant

long long* Fibonacci(size_t n)
{
    
	if (n == 0)
		return NULL;

	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
    
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

Opens the N Space , Time complexity O(N)

// How to calculate factorial recursion Fac Spatial complexity of ？
long long Fac(size_t N)
{
    
	if (N == 0)
		return 1;

	return Fac(N - 1) * N;
}

Time complexity O(N), Recursively called N Time , Opens the N Stack frame , Each stack frame uses a constant space .

notes ： The author's level is limited , If there is a mistake , Please correct me ！！！