Hello readers! Now I will briefly talk about a basic knowledge point in data structure based on C language: the time complexity and space complexity of the algorithm. I hope it will be helpful to you.
Table of Contents
1. What is a data structure?
2. What is an algorithm?
3. Time complexity
3.1 The concept of time complexity
3.2 Asymptotic representation of Big O
3.3 Example analysis of common time complexity
4. Space complexity
4.1 The concept of space complexity
4.2 Analysis of common space complexity examples
5. Complex oj exercises
6.ending
Before we briefly talk about time complexity and space complexity, we can understand a few concepts:
1. What is data structure
Data structure is a way for computers to store and organize data. It refers to a collection of data elements that have one or more specific relationships with each other.
In fact, let’s put it simply. Data structures manage data in memory.
expand:
1. What is a database?
To put it simply: a database manages data on disk.
2. Similarities and differences between memory and disk
Same: Memory and disk are the two core storage media of the computer, and both are two pieces of hardware for storing data.
Difference: The memory is fast and needs to be stored with electricity; the disk is (relatively) slow and needs to be stored without electricity.
For example: we create a text document in the computer and enter data in the document. If the computer suddenly shuts down before the data is saved, then the data will be gone after we restart the computer because the data is stored in the memory. Memory needs to be stored with electricity. But if we save this data before shutting down the computer, we can still see the data when we open the text document after restarting, because the saved data has already been in the disk, and the disk does not need to be stored under power. (Disregarding automatic saving of text documents.)
2. What is an algorithm
Algorithm: It is a well-defined calculation process that takes one or a group of values as input and produces one or a group of values as output. Simply put, an algorithm is a series of calculation steps used to transform input data into output results.
Let’s put it simply. Algorithms are methods for processing data in various ways.
So how do we judge the quality of an algorithm?
After the algorithm is written into an executable program, it requires time resources and space (memory) resources to run. Therefore, measuring the quality of an algorithm is generally measured from the two dimensions of time and space, namely time complexity and space complexity (time complexity mainly measures the running speed of an algorithm, while space complexity mainly measures the running speed of an algorithm. the additional space required.).
3. Time complexity
3.1 Concept of Time Complexity
Definition of time complexity: In computer science, the time complexity of an algorithm is a function that quantitatively describes the running time of the algorithm. The time it takes to execute an algorithm cannot be calculated theoretically. You can only know it if you put your program on the machine and run it. But do we need to test every algorithm on a computer? It is possible to test everything on a computer, but this is very troublesome, so the time complexity analysis method is introduced. The time an algorithm takes is proportional to the number of executions of its statements. The number of executions of basic operations in the algorithm is the time complexity of the algorithm.
How to calculate the time complexity?
Let’s throw some light on the topic and analyze the time complexity of the following code:
void Func1(int N)//Calculate the total number of + + count executions in Fun1
{
int count = 0;
for (int i = 0; i < N ; + + i)
{
for (int j = 0; j < N ; + + j)
{
+ + count;
}
}
for (int k = 0; k < 2 * N ; + + k)
{
+ + count;
}
int M = 10;
while (M--)
{
+ + count;
}
printf("%d\\
",count);
For the convenience of introduction, let me reveal the answer directly. The time complexity of this function is O(N^2);
So why is it O(N^2)? What is O(N^2)? This depends on the following knowledge:
3.2 Asymptotic representation of Big O
In practice, when we calculate the time complexity, we do not actually have to calculate the exact number of executions, but only the approximate number of executions, so here we use the asymptotic representation of Big O.
Big O notation: is a mathematical notation used to describe the asymptotic behavior of a function.
Derive the Big O method:
1. Replace all additive constants in the run time with constant 1.
2. In the modified running times function, only the highest order term is retained.
3. If the highest-order term exists and is not 1, remove the constant multiplied by this term. The result is Big O order.
The above explanation actually means that we use the asymptotic representation of big O to calculate the time complexity. The time complexity is expressed by O(?). As for the question mark “?” in the brackets, what should we use? Instead, we will conduct a detailed analysis based on the derivation of the big O-order method. Let’s analyze the above code and take a look.
The basic number of operations of + + count in function Func1 is a function F(N)=N^2 + 2*N + 10. According to the derivation of the big O-order method, we can know that the time complexity of Func1 is O(N^2). In fact, deriving the big O-order method means removing those terms that have little impact on the results. The essence of deriving the big O-order method is estimation.
Let’s analyze the time complexity of a code and see:
int Func2(int*nums,int numsSize,int n)
{
int i=0;
for(i=0;i<numsSize;i + + )
{
if(*(nums + i)==n)
{
return i;
}
}
return -1;
}
Let’s take a look at this function Func2. It is impossible to write a function with that number of operations. There are three situations for the number of operations:
Worst case: maximum number of runs for any input size (upper bound)
Average case: expected number of runs for any input size
Best case: minimum number of runs (lower bound) for any input size
We see that this function Func2 is nothing more than an algorithm for traversing an array. It traverses and finds n among the numsSize elements of the array nums. If it finds it, it returns the subscript. If it cannot find it, it returns -1. Best case: found in 1 time; average case: found in numsSize/2 times; worst case: found in numsSize times. So the time complexity of this function is O(N), because the time complexity is a conservative estimate, taking the worst case scenario.
3.3 Common Time Complexity Example Analysis
The time complexity calculation of the above two codes depends on the content of the code. It seems that it is just counting the number of loops. In fact, it is not the case. The time complexity of an algorithm depends on the algorithm idea. There is no need to understand the code details. Let’s experience it in the following code.
Example 1:
// Calculate the time complexity of Func3?
void Func3(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; + + k)
{
+ + count;
}
int M = 10;
while (M--)
{
+ + count;
}
printf("%d\\
", count);
}
We see that the basic operation of this algorithm is executed 2N + 10 times, so the time complexity is O(N). Why not O(2N)? From the derivation of item 3 of the big O order method, we can know that the constant 2 needs to be removed. (For example: If there is a habitable planet 10 billion light years away from the earth and a habitable planet 20 billion light years away from the earth, there is no difference for humans, because the distance traveled by humans can reach tens of billions In light years, it doesn’t matter if there are ten billion more. This is the idea of removing the constant 2 here.)
Example 2:
// Calculate the time complexity of Func4?
void Func4(int N, int M)
{
int count = 0;
for (int k = 0; k < M; + + k)
{
+ + count;
}
for (int k = 0; k < N ; + + k)
{
+ + count;
}
printf("%d\\
", count);
}
The basic operation of this algorithm is performed M + N times. There are two unknowns M and N. The time complexity is O(N + M), which can also be written as O(max(N,M)).
Example 3:
// Calculate the time complexity of Func5?
void Func5(int N)
{
int count = 0;
for (int k = 0; k < 100; + + k)
{
+ + count;
}
printf("%d\\
", count);
}
The basic operation of this algorithm is executed 10 times, which is a constant number of times. By deriving the first item of the big O-order method, the time complexity is O(1).
Example 4:
// Calculate the time complexity of BubbleSort?
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( & amp;a[i-1], & amp;a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
Here is a bubble sort. This algorithm performs the basic operation N times at best and (N*(N + 1)/2 times at worst. By deriving the big O-order method + time complexity, the worst time is generally seen. The complexity is O(N^2).
Example 5:
// Calculate the time complexity of BinarySearch?
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
// [begin, end]: begin and end are left-closed and right-closed intervals, so there is an = sign
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;
}
Here is a binary search. The basic operation is performed once at best and O(logN) times at worst (half of it can be eliminated for each search. The best case is of course that it is found the first time. The worst case is that it is found for the last time. The last time is the first time. How many times? We searched a total of .) So the time complexity is O(logN).
ps: The default representation of logN in algorithm analysis is that the base is 2 and the logarithm is N. Therefore, the base 2 can be omitted, but it cannot be omitted when using other numbers as the base.
According to the time complexity of the binary search algorithm O(logN), binary search is a very good algorithm, because according to this algorithm, even if there are 1 million data, up to 20 searches are enough. But binary search is not very good, because this algorithm has a fatal flaw, which is that the data must be ordered.
Example 6:
/ What is the time complexity of calculating factorial recursion Fac?
long long Fac(size_t N)
{
if(0==N)
return 1;
return Fac(N-1)*N;
}
Let’s see that this is a function that finds the factorial. The idea of this function algorithm is nothing more than recursively calling the function itself when the passed parameter is not 0. The basic call is called N + 1 times, and the time is accumulated N + 1 times, so the time complexity is O(N).
Example 7:
//The time complexity of calculating Fibonacci recursion Fib?
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
This is a function that recursively finds Fibonacci numbers. The algorithm idea is a two-way recursion, similar to cell division: 1 gives birth to 2, 2 gives birth to 4… So the time complexity is O(2^N).
According to this time complexity O(2^N), we can know that this algorithm is not a good algorithm for finding Fibonacci numbers, because exponential explosion is too time-consuming. So what algorithm should we use to find Fibonacci numbers that is better? Shushu, let me write a code here:
int Fib(size_t N)
{
if (N == 1 || N == 2)
{
return 1;
}
int i1 = 1, i2 = 1, i3 = 0;
int j = 0;
for (j = 0; j < N - 2; j + + )
{
i3 = i1 + i2;
i1 = i2;
i2 = i3;
}
return i3;
}
The algorithm for finding Fibonacci numbers in our code is better than the above code. According to the idea, the time complexity of this algorithm is O(N). It greatly saves time compared to recursive algorithms. Therefore, before we write code, we need to consider the time complexity of various algorithms and then consider which algorithm to use to write code, which can make the code better.
4. Space complexity
4.1 Concept of Space Complexity
Space complexity is also a mathematical expression, which is a measure of the amount of storage space an algorithm temporarily occupies during operation.
Space complexity is not how many bytes of space the program occupies, because this is not very meaningful, so space complexity is calculated by the number of variables. The space complexity calculation rules are basically similar to the practical complexity, and the big O asymptotic notation is also used.
Note: The stack space required when the function is running (storing parameters, local variables, some register information, etc.) has been determined during compilation, so the space complexity is mainly determined by the additional space explicitly applied for by the function at runtime.
4.2 Analysis of common space complexity examples
Example 1:
// Calculate the space complexity of BubbleSort?
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( & amp;a[i-1], & amp;a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
We know this is a bubble sort! The above code needs to open up a constant (1) additional space (that is, exchange) to implement the algorithm logic, so the space complexity is O(1).
Example 2:
// Calculate the space complexity of Fibonacci?
// Return the first n terms of the Fibonacci sequence
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;
}
The implementation of this algorithm logic requires dynamically malloc n + 1 blocks of space, so the space complexity is O(N).
Example 3:
// Calculate the space complexity of factorial recursion Fac?
long long Fac(size_t N)
{
if(N==0)
return 1;
return Fac(N-1)*N;
}
This algorithm is called recursively N times, opening up N stack frames, and each stack frame uses a constant amount of space. The space complexity is O(N).
5. Complex oj exercises
Missing number OJ link: https://leetcode-cn.com/problems/missing-number-lcci/. Open the link to do this question!
This question requires time to be completed in O(N). There are two ways to solve this problem. Let’s write them in order:
Solution 1:
int missingNumber(int* nums, int numsSize){
int sum=(0 + numsSize)*(numsSize + 1)/2;
int i=0;
for(i=0;i<numsSize;i + + )
{
sum-=*(nums + i);
}
return sum;
}
The idea of solving this problem is to use the arithmetic sequence formula to find the sum of all integers from 0 to n, and then use this sum to subtract the array elements in sequence to get the disappearing number! The time complexity of this is O(N), the space complexity is O(1), oj can be passed, you can try it, I won’t show it!
Solution 2:
int missingNumber(int* nums, int numsSize){
int missnum=0,i=0;
for(i=0;i<=numsSize;i + + )
{
missnum^=i;
}
for(i=0;i<numsSize;i + + )
{
missnum^=nums[i];
}
return missnum;
}
This problem-solving idea is obtained by using the two characteristics of 0^any number=any number and any number^any number=0. This time complexity is also O(N), the space complexity is also O(1), and oj can also be passed!
6.ending
Shushu, I have little talent and little knowledge. If there are any shortcomings, please correct me!
You know what I mean!
