PS: Recently, the requirements for opening a WeChat official account have been lowered from 5000 followers to 500 followers. Do you remember WeChat's slogan: "Even the smallest individual has their own brand"? I believe that those who were hesitant to open an official account before will also open one in the future. Of course, Tencent is doing this because the current open rate of official accounts is very low, and they also face control over information flow from platforms like Baidu and Toutiao. It is necessary to make changes.
Time complexity and space complexity can help us choose suitable algorithms based on specific platforms. We should learn to design algorithms by trading space for time or time for space. For example, in microcontrollers where memory space is limited, when pursuing optimal algorithms, we can design them by trading time for space. Of course, on devices with large memory, we can choose to design optimal algorithms by trading space for time. Therefore, time and space complexity can be used as a way to judge the speed of execution of an algorithm or code block under certain conditions. The main aspects to understand and learn about time and space complexity are as follows:
- Relationship between data structures and algorithms
- Time complexity
- Space complexity
- Summary
Relationship between data structures and algorithms:
Data structures refer to the storage structure of a group of data, while algorithms are a set of methods for manipulating data. Therefore, data structures serve algorithms, and algorithms operate on specific data structures.
Big O notation:
Big O notation can roughly estimate the time efficiency of code execution. For example, consider the following code:
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
If the execution time of each line of effective code (with assignment operations) is considered as one unit of time, then the execution time of the above code can be represented as 2n + 2 units of time. Here, it can be seen that the execution time of the code is directly proportional to the number of times the effective code is executed.
If we consider the following code:
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
Under the assumption mentioned above, the execution time of the above code can be represented as 2n*n + 2n + 3. Here, it can also be seen that the execution time of the code is directly proportional to the number of times the effective code is executed. Using the formula, it can be represented as:
T(n) = O(n)
Therefore, the time complexity of the above two code snippets can be represented using Big O notation as O(n) and O(n*n).
When the data size increases, the constant terms at the end do not affect the change in execution time with the increase in data size. It is clear that one is a linear function and the other is a quadratic function. As n increases, the value of the quadratic function will eventually exceed that of the linear function. Therefore, we consider the highest order for comparison and simplify it as follows:
T(n) = O(n)
T(n) = O(n*n)
Now we can say that the time complexity of the above two code snippets can be represented using Big O notation as O(n) and O(n*n).
Time complexity:
Time complexity reflects the change in code execution time with the increase in data size, as indicated by the Big O notation. The premise of Big O notation is that with the increase in data size, only the highest order term needs to be considered to estimate the code's execution time. Therefore, when analyzing complexity, we only need to focus on the highest order time complexity.
The common time complexity levels from smallest to largest are:
Constant time complexity (O(1)) < Logarithmic time complexity (O(logn)) < Linear time complexity (O(n)) < Linear logarithmic time complexity (O(nlogn)) < Quadratic time complexity (O(n^2)) < Cubic time complexity (O(n^3)) < Factorial time complexity (O(n!)) < Exponential time complexity (O(n^n))
Among the above levels, factorial and exponential time complexities belong to non-polynomial levels. As the data size increases rapidly, the execution time of non-polynomial time complexity algorithms becomes longer and these algorithms are the least efficient. The following special cases of complexity analysis are also explained:
O(n): Regardless of the number of lines of code, if only the number of executions is known, the time complexity level is represented as O(1). There will not be cases like O(2) or O(3).
O(logn): Logarithmic time complexity calculation mainly involves finding the condition that satisfies the code's execution by calculating the number of times the code is executed. For example:
i=1;
while (i <= n) {
i = i * 2;
}
In the above code, we only need to know how many times this code is executed. We can see that the values of i are 1, 2, 8, 16, etc., which are 2^0, 2^1, 2^3, 2^4, etc. So, the relationship between i and n is 2^t = n. Then, calculate the value of t and remove irrelevant terms to determine the time complexity. The linear logarithmic time complexity O(nlogn) is the result of looping the above code n times.
O(m+n): In the following code, we cannot directly add the time complexities together and take the highest order:
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
Here, m and n represent two data sizes, and we cannot determine which one has a larger order. In this case, the time complexity is represented as O(m) + O(n) for the code that calculates the product of sum_1 and sum_2, the time complexity is represented as O(m) * O(n).
The basic process of time complexity analysis has been explained above. Now let's continue to look at some special cases of complexity analysis. Analyze the time complexity of the following code:
// n represents the length of the array 'array'
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) pos = i;
}
return pos;
}
Analysis process: The assignments of i and pos occur only twice and do not affect the trend of code execution time with the increase in data size, so they can be ignored. In the for loop, if i increases to m when the if statement condition is satisfied, the time complexity of this code segment is (1+m)n. Therefore, the time complexity of this code is definitely O(n) because the if statement does not exit the for loop even when a value equal to x is found. Modify the code as follows:
// n represents the length of the array 'array'
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
If the loop is exited when a value equal to x is found in the array, then for the time complexity (1+m)n, there are two possibilities. One is when a value satisfying the if statement condition is found and the loop is exited. In this case, m is definitely a constant value that can be ignored, and the time complexity of this code is O(1). Of course, if it is known that the if statement condition is not satisfied, the loop will continue for n times, and in this case, the time complexity of this code is still O(n). It can be seen that the same code may have different time complexities under different conditions. Considering this situation, the time complexity can be further divided into three types:
- Best-case time complexity: Represents the ideal time complexity of executing a code segment. For the above code, when a value satisfying the if statement condition is found in the array, the time complexity is O(1), which is the best-case time complexity.
- Worst-case time complexity: Represents the worst time complexity of executing a code segment. For the above code, when a value satisfying the if statement condition is never found in the array, the time complexity is O(n), which is the worst-case time complexity.