In the New Year, I would like to share with you a simple but important knowledge point: time complexity and space complexity. Because in the previous several articles, mentioned the time complexity, perhaps some friends are not clear. (PS: I hope those who left comments on my previous post aren’t disappointed. Take your time.)
Sum = 1+2+3+… Plus n, sum.
Why is complexity analysis needed
- The point of learning about data structures and algorithms is to learn about “fast” and “frugal” problems — how to design your code to be faster and take up less space. So how do you calculate code execution efficiency? That’s where the complexity analysis comes in.
- While it is possible to calculate execution time accurately with code, there are limitations.
- The difference in data size will directly affect the test results. For example, the same sorting algorithm, sorting order is different, then the final calculation efficiency will be different; If the array happens to already be sorted, the execution time is even shorter. For example, if the data size is relatively small, the test results may not reflect the performance of the algorithm.
- The test environment will also affect the test results. For example, if the same set of code is tested on the i3 processor and the i7 processor, the test time on the I7 processor will be shorter than that on the I3 processor.
So you need a way to roughly estimate code execution time without having to measure it with accurate test results. That’s complexity analysis.
Large O complexity notation
To start with an example, estimate the execution time of the following code
functiontotal(n) { // 1 var sum = 0; / / 2for(var i = 0; i < n; i++) { // 3 sum += i; //5} //6Copy the code
Assuming that each line of code takes the same time to execute, called t, then line 2 in the above function takes 1 T, and line 3 and line 4 take n t, the total execution time of this code is (2n+1)*t.
Estimate the execution time of the following code according to the analysis method above
functiontotal(n) { // 1 var sum = 0; / / 2for (var i = 0; i < n; i++) { // 3
for(var j = 0; j < n; j++) { // 4 sum = sum + i + j; // 5}}}Copy the code
Line 2 takes one T, line 3 takes n t, and lines 4 and 5 take N2, so the total execution time of this code is (2n2+n+1)* T.
From a mathematical point of view, we can derive a rule: the total execution time of code T(n) is proportional to the number of times per line of code is executed
T(n) = O(f(n))
In this formula, T(n) represents the execution time of the code; N indicates the data size. F (n) represents the sum of times of execution of each line of code; O indicates that the execution time of the code T(n) is proportional to the f(n) expression.
So the execution times of the above two functions can be labeled as T(n) = O(2n+1) and T(n) = O(2n2+n+1). This is the big O time complexity notation, which does not represent the actual execution time of the code, but represents the trend of the code as the data size increases, called time complexity for short.
And when n is large, we can ignore the constant term and just keep the maximum order. So the above code execution times can be simply labeled as T(n) = O(n) and T(n) = O(n2).
Time complexity analysis
So how to analyze the time complexity of a piece of code, can use the following methods
1. Focus only on the piece of code that loops the most
When we analyze the time complexity of a piece of code, we just focus on the piece of code that has the most cycles. For example, in the first piece of code
functiontotal(n) { // 1 var sum = 0; / / 2for(var i = 0; i < n; i++) { // 3 sum += i; //5} //6Copy the code
Only line 3 and line 4 are executed the most, n times each, so constant terms are ignored, so the time complexity of this code is O(n).
2. Rule of addition: The total complexity is equal to the complexity of the code with the highest order of magnitude.
For example, look at the time complexity of this code.
functionTotal (n) {// The first oneforVar sum1 = 0;for (var i = 0; i < n; i++) {
for(var j = 0; j < n; j++) { sum1 = sum1 + i + j; }} // The secondforVar sum2 = 0;for(var i=0; i<1000; i++) { sum2 = sum2 + i; } // The third oneforVar sum3 = 0;for(var i = 0; i < n; i++) { sum3 = sum3 + i; }}Copy the code
We first analyze the time complexity of each for loop separately, and then take the highest order of magnitude as the time complexity of the entire code.
The time complexity of the first for loop is O(n2).
The second for loop executes 1000 times, which is a constant order of magnitude, and although it has an effect on the execution time of the code, it can be ignored when n is infinite. Because it has no effect on the growth trend, the time complexity of this code is negligible.
The time complexity of the third for loop is O(n).
In general, take the maximum order of magnitude, so the time complexity of the whole code is O(n2).
3. Multiplication rule: The complexity of nested code is equal to the product of the complexity of both inside and outside of the nested code.
For example, look at the time complexity of this code
function f(i) {
var sum = 0;
for (var j = 0; j < i; j++) {
sum += j;
}
return sum;
}
function total(n) {
var res = 0;
for(var i = 0; i < n; i++) { res = res + f(i); // Call f function}}Copy the code
The time complexity of the total function alone is T1(n)=O(n), but considering that the time complexity of the F function is also T2(n)=O(n). So the time complexity of the whole piece of code for T = T1 * T2 (n) (n) (n) = O (n * n) = O (n2).
Several common time complexity analyses
Looking only at the highest order of complexity, the efficiency is decreasing in the figure below
Polynomial magnitude
Nonpolynomial magnitude
Nonpolynomial magnitude
n
Nonpolynomial magnitude
Nonpolynomial magnitude
1. O(1)
O(1) is just a constant-level representation of time complexity, not a one-line code, such as the one below
function total() {
var sum = 0;
for(var i=0; i<100; i++) { sum += i; }}Copy the code
With so many lines, even if the for loop executes 100 times, the code execution time does not increase with n, so the code complexity is O(1).
(2) O (logn), O (nlogn)
Common code for logarithmic time complexity is as follows
function total1(n) {
var sum = 0;
var i = 1;
while(i <= n) { sum += i; i = i * 2; }}function total2(n) {
var sum = 0;
for(var i = 1; i <= n; i = i * 2) { sum += i; }}Copy the code
The above two functions have one thing in common: the variable I is evaluated at 1, multiplied by 2 each time, and when greater than n, the loop ends. In fact, the value of I is just a geometric sequence, like this
20, 21, 22… 2k… 2x =n;
So if we know x, we know how many times these two functions are executed. So 2x is equal to n tells us x is equal to log base 2n, so the time of these two functions is order log base 2n.
Let’s look at the time complexity of the following two functions
function total1(n) {
var sum = 0;
var i = 1;
while(i <= n) { sum += i; i = i * 3; }}function total2(n) {
var sum = 0;
for(var i = 1; i <= n; i = i * 3) { sum += i; }}Copy the code
It can be seen from the above that the time complexity of these two functions is O(log3n).
Since we can ignore constants and the base in logarithms, the logarithmic complexity is uniformly expressed as O(logn); So, O(nlogn) is pretty clear, O(logn) code executes n times.
(3) O (m + n), O (m * n)
Let’s look at the time complexity of a particular piece of code, for example
function total(m,n) {
var sum1 = 0;
for (var i = 0; i < n; i++) {
sum1 += i;
}
var sum2 = 0;
for (var i = 0; i < m; i++) {
sum2 += i;
}
return sum1 + sum2;
}
Copy the code
Since we cannot evaluate the magnitude of m or n, we cannot ignore one of them. The complexity of this function is determined by the magnitude of two data, so the time complexity of this function is O(m+n); So O of m times n has a similar time complexity.
Spatial complexity analysis
The space complexity is similar to the time complexity. The so-called spatial complexity is the relationship between the storage space and the data size of the algorithm.
For example, analyze the spatial complexity of the following code:
function initArr(n) {
var arr = [];
for(var i = 0; i < n; i++) { arr[i] = i; }}Copy the code
According to the calculation of time complexity, ignoring the constant order of magnitude, each array assignment will apply for a space to store the variable, so the space complexity of this function is O(n).
Common space complexity is O(1), O(n), O(n2). Other words are rarely used.
Think of problem solutions
Now back to the original thought, the code implementation is simple:
function total(n) {
var sum = 0;
for (var i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
Copy the code
The time complexity of this function, which you should be able to easily see by now, is order n.
I think the time complexity is a little high, and I want the time complexity function of O(1) to implement this algorithm, ok?
Yes, little math wizard Gauss taught us a trick. Here it is
function total(n) {
var sum = n*(n+1)/2
return sum;
}
Copy the code
The time complexity of this function is only O(1). When the data scale is relatively large, is the following function obviously more efficient than the above function?
conclusion
Complexity is also called progressive complexity, including time complexity and space complexity. One represents the speed of execution, and the other represents the memory consumption. It is used to analyze the growth relationship between algorithm execution efficiency and data size.
Can you avoid writing inefficient code after learning complexity analysis? Let’s do an analysis of your code.
Focus on
If there are mistakes or typos, please give me a message pointed out, thank you.
We’ll see you next time.