PS: Recently, the conditions for opening a WeChat public 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 hesitated to open a public account before will also open one in the future. Of course, Tencent is doing this because the current open rate of public accounts is very low, and there is also the challenge of facing Baidu, Toutiao, and other platforms that control information flow. Change is necessary.
Time complexity and space complexity can help us choose the appropriate algorithm 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 the optimal algorithm, we can design it by trading time for space. Of course, on devices with large memory, we can choose to design the optimal algorithm 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 assumed conditions, 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 segments 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 function is linear and the other is quadratic. As n increases, the value of the quadratic function will eventually exceed that of the linear function. Therefore, we compare the highest order terms and simplify them as follows:
T(n) = O(n)
T(n) = O(n*n)
Now we can say that the time complexity of the above two code segments 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 assumption of Big O notation is that as the data size increases, 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 these levels, factorial and exponential time complexity belong to non-polynomial levels. As the data size increases, the execution time of non-polynomial time complexity algorithms becomes longer and longer, making them the least efficient algorithms. The following special cases need to be considered for complexity analysis.
O(n): Regardless of the number of lines of code, if the number of executions can be determined, 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 conditions that satisfy the code and calculating the number of times the code needs to be 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 needs to be executed, which means finding the relationship between i and n. 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, and then we can 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 choose 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 the sizes of two data sets, and we cannot determine which one has a larger order. In this case, the time complexity is represented as O(m) + O(n). If sum_1 * sum_2, the corresponding time complexity is represented as O(m) * O(n).
The basic process of time complexity analysis is as described above. Next, let's continue to look at the time complexity analysis of special cases. 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 change in execution time with the increase in data size, so they can be ignored. In the for loop, if i reaches m while satisfying the condition in the if statement, the time complexity is (1+m)n. Therefore, the time complexity of this code segment 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, there are two possibilities for the time complexity (1+m)n. One possibility is that if the if statement condition is satisfied and the loop is exited, m is a constant value that can be ignored, and the time complexity of this code segment 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 the time complexity of this code segment is still O(n). It can be seen that the same code segment may have different time complexities under different conditions. In view of 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.
Space complexity:
Space complexity reflects the trend of storage space with the increase in data size. Consider the following code:
void print(int n) {
int i = 0; // stack memory
int[] a = new int[n]; // heap memory
for (i; i <n; ++i) {
a[i] = i * i;
}
}
In the above code, there are only two memory allocation operations. The memory space occupied by the variable i is fixed and can be ignored. The declaration and allocation of the array occupy memory space, and the size is n times the memory occupied by an int type. Therefore, the space complexity of this code segment is O(n).
Summary:
Time complexity reflects the change in code execution time with the increase in data size, with a focus on nested loops, etc. Space complexity reflects the change in storage space with the increase in data size. Time complexity is more commonly used than space complexity, and when developers talk about complexity without specifying, they usually refer to time complexity. In addition, for a specific code segment, it can be further divided into best-case time complexity, worst-case time complexity, average time complexity, and amortized time complexity. The analysis process is similar, but the limiting conditions are different.