This is the 10th day of my participation in the August More Text Challenge

Why is complexity analysis needed?

If you publish it by running the code to check the efficiency, you will have the following problems:

  1. Test results are highly dependent on the test environment

Hardware differences in the test environment can have a significant impact on test results

  1. Test results are greatly influenced by the size of the data

If the test data size is too small, the test results may not truly reflect the performance of the algorithm

Therefore, we need a method that can roughly estimate the efficiency of the algorithm without using specific test data to test it. This is the time and space complexity analysis method we are going to talk about today.

Large O complexity notation

The execution efficiency of an algorithm, roughly speaking, is the execution time of the algorithm code. But how do you “visually” get the execution time of a piece of code without actually running it?

Let’s first try to analyze the execution time of two pieces of code:

Premise: Assume that each line of code executes at the same time, defined as unit_time

  1. For 1, 2, 3… The sum of n:
function sum(n) {
  var sum = 0;
  var i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}
Copy the code

Lines 2 and 3 are executed only once, so it takes 1 unit_time, respectively. Lines 4 and 5 are run n times, so it takes 2n *unit_time, so the total execution time is (2n+2)*unit_time

  1. Nested loop
function sum(n) {
  var sum = 0;
  var i = 1;
  var j = 1;
  for (; i <= n; ++i) {
    j = 1;
    for(; j <= n; ++j) {
      sum = sum + i * j
    }
  }
  return sum;
}
Copy the code

Lines 2, 3, and 4 are executed only once, so it takes 1 unit_time. Lines 5 and 6 are executed n times, so it takes 2n * unit_time. Lines 7 and 8 are executed n² times. So we need 2n² unit_time execution time, so the total execution time is 2n²+2n+3 unit_time

Through the analysis of the execution time of the two codes, it can be concluded that the execution time T(n) of all codes is proportional to the execution times n of each line of code, which can be expressed by a formula:

T(n) = O(f(n))

  1. T(n) : indicates the execution time of the code
  2. N: Indicates the size of the data
  3. F (n) : represents a formula, like the one above2n + 2 或 (2 n squared + 2 n + 3)Represents all code executedThe number of total
  4. O: indicates that the execution time of the code T(n) is proportional to the f(n) expression

The first example can be expressed as T(n) = O(2n+2), and the second example as T(n) = O(2n²+2n+3). This is the big O time complexity notation.

The maximum O time complexity does not specifically represent the real execution time of the code, but the trend of code execution time with the increase of data size. Therefore, it is also called the asymptotic time complexity (also called time complexity).

It can be seen from the formula that when n is very large, such as reaching 10000 or even 100000, the low-order, constant and coefficient parts in the formula can be ignored. Then the time complexity of the two examples can be simplified as T(n) = O(n); T (n) = O (n squared).

Time complexity analysis

How to analyze the time complexity of a piece of code?

  1. Focus only on the piece of code that loops the most times

When analyzing the time complexity of an algorithm or a piece of code, focus only on the piece of code that executes the most times. Take the previous example

function sum(n) {
  var sum = 0;
  var i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}
Copy the code

Lines 2 and 3 are constant-level execution times, independent of the size of n, so it has no effect on complexity. Lines 4 and 5 are the ones that loop the most, so focus on that. As we said earlier, these two lines of code are executed n times, so the total time is order n.

  1. Rule of addition: The total complexity is equal to the complexity of the code with the highest order of magnitude

For ease of understanding, the sample code is as follows:

function sum(n) {
  var sum_1 = 0;
  var i = 1;
  for (; i <= 100; ++i) {
    sum_1 = sum_1 + i;
  }
  var sum_2 = 0;
  var j = 1;
  for (; j <= n; ++j) {
    sum_2 = sum_2 + j;
  }
  var sum_3 = 0;
  var m = 1,
    q = 1;
  for (; m <= n; ++m) {
    q = 1;
    for(; q <= n; ++q) { sum_3 = sum_3 + i * j; }}return sum_1 + sum_2 + sum_3;
}

Copy the code

This code is divided into three parts, sum_1, sum_2, sum_3 respectively. Next, we will analyze the time complexity of each part separately, and then take the highest order of magnitude as the complexity of the whole code.

What is the time for sum_1 in the first paragraph?

This code executes 100 times, which is a constant execution time, independent of the size of n, so it’s negligible.

Let’s say 100 times, 100,000 times, as long as it’s a known number, it doesn’t matter what n is, it’s just a constant execution time, and when n is infinite, it’s negligible. In addition, time complexity represents the changing trend of the growth of an algorithm’s execution efficiency and data size. Therefore, no matter how long the execution time of constant is, we can ignore it. Because it has no effect on growth trends per se.

The second code is similar to the first example above, with O(n) time.

The third code is similar to the second example above, with O(n²) time.

After analyzing the time complexity of the three pieces of code, take the largest order of magnitude, which is clearly O(n²).

In other words, the total time complexity is equal to the time complexity of the code with the highest magnitude. This law can be abstracted into the following formula:

If T1(n)=O(f(n)), T2(n)=O(g(n)); Then T = T1 (n) (n) + T2 (n) = Max (O (f (n)), O (g (n))) = O (Max (f (n), g (n))).

  1. Product rule: The complexity of nested code is equal to the product of the complexity of both inside and outside the nested code

For ease of understanding, the sample code is as follows:

function sum(n) {
  var sum = 0;
  var i = 1;
  for (; i <= n; ++i) {
    sum = sum + extra(i);
  }
  return sum;
}
function extra(n) {
  var sum = 0;
  var i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  }
  return sum;
}

Copy the code

In the sum function, lines 2 and 3 are executed only once and are of constant level and are ignored, focusing on lines 4 and 5.

If extra were just an ordinary operation (noncyclic), then lines 4 and 5 would show the time complexity T1(n) = O(n),

But extra is a cyclic operation, and the time complexity T2(n) = O(n).

So the time complexity of the sum function is T(n) = T1(n) * T2(n) = O(n*n) = O(n²).

Analysis of several common time complexity examples

Common complexity levels are as follows:For the complexity levels just listed, we can roughly divide them into two categories, polynomial and non-polynomial. There are only two non-polynomial magnitude-o (2n) and O(n!). .

When the data size n becomes larger and larger, the execution time of the non-polynomial scale algorithm will increase sharply, and the execution time of solving the problem will increase indefinitely. Therefore, non-polynomial time complexity algorithms are actually very inefficient algorithms.

The following focuses on analyzing common polynomial time complexity.

O(1)

O(1) does not mean that only one line of code is executed, but is a way of expressing constant time complexity, such as O(1) instead of O(3).

function sum() {
  var i = 0;
  var j = 1;
  var sum = i + j;
}
Copy the code

As long as the execution time of the code does not increase with n, such code time complexity is O(1).

Generally, the time complexity of this algorithm is equal to two o (1), even if there are thousands of lines of code, as long as there are no circular or recursive statements in the algorithm.

O (logn), O (nlogn)

For ease of understanding, add the following sample code:

function calc() {
  var i = 1;
  while (i <= n) {
    i = i * 2; }}Copy the code

The fourth line of code is the one that executes the most times, and the time complexity of the calC function is known by counting the number of times this line of code is executed. As you can see from the code, the value of variable I starts at 1 and is multiplied by 2 on the first loop until it is greater than n.

In mathematics, the geometric sequence is as follows:So, we just need to knowxThat tells us how many times this line of code has been executed. By 2x= n solvingx, and x = are obtained
log ⁡ 2 n \log_2 n , so the time complexity of this code is O(
log ⁡ 2 n \log_2 n ). In fact, whether O(
log ⁡ 2 n \log_2 n ) or O (
log ⁡ 3 n \log_3 n ), as long as it is logarithmic, then its time complexity isO(logn)Why?

Because log⁡3n\log_3 nlog3n = log⁡32\log_3 2log32 * log⁡2n\log_2 nlog2n, So O(log⁡3n\log_3 nlog3n) = O(C * log⁡2n\log_2 nlog2n), where C = log⁡32\log_3 2log32 is a constant, according to the previous analysis, when using large O notation complexity, We can ignore the coefficient, that is, O(Cf(n)) = O(f(n)). So O(log⁡3n\log_3 nlog3n) is equal to O(log⁡2n\log_2 nlog2n). Therefore, in the expression method of logarithmic order time complexity, we ignore the “base” of logarithm and uniformly express it as O(logn).

And O(nlogn) is essentially O(logn) code for a period of time, and it loops n times, so it’s O(nlogn).

For example:

function sum(n) {
  var sum = 0;
  var i = 1;
  for (; i <= n; ++i) {
    sum = sum + extra(i);
  }
  return sum;
}
function extra(n) {
  var i = 1;
  while (i <= n) {
    i = i * 2;
  }
  return i
}
Copy the code

In addition, the time complexity of merge sort and quicksort is O(nlogn).

O (m + n), O (m * n)

For ease of understanding, add the following code:

function sum(n, m) {
  var sum_1 = 0;
  var i = 1;
  for (; i <= n; ++i) {
    sum_1 = sum_1 + i;
  }
  var sum_2 = 0;
  var j = 1;
  for (; j <= m; ++j) {
    sum_2 = sum_2 + j;
  }
  return sum_1 + sum_2;
}
Copy the code

The previous time complexity is determined by the size (n) of a single data. However, there are two data sizes m and N in this example. Since it is impossible to evaluate the magnitude of m and n in advance, we cannot simply reuse the addition rule, omit one of them and take the maximum value. So, the time complexity of the code above is O(m+n).

When there are multiple data sizes, the addition rule is expressed as T1(m) + T2(n) = O(f(m) + g(n)), and the multiplication rule still holds: T1(m)*T2(n) = O(f(m) * f(n)).

Spatial complexity analysis

The full name of time complexity is progressive time complexity, which represents the increasing relationship between the execution time of an algorithm and the size of data.

By analogy, the full name for the parabolic space complexity is the increasing relationship between the storage space of an algorithm and the data size of the algorithm.

Add the following sample code:

function sum(n) {
  var i = 0;
  var arr = new Array(n);
  for (; i < n; ++i) {
    arr[i] = i * i;
  }
  return arr;
}
Copy the code

In line 2, I request a space to store variable I, but it is of constant order and has nothing to do with data size N, so I can ignore it. In line 3, I request an array of size N. Otherwise, the rest of the code doesn’t take up much space, so the space complexity of the whole code is O(n).

The common space complexity is O(1), O(n), O(n ^ 2), logarithmic complexity like O(logn), O(nlogn) is not used in ordinary times.

Spatial complexity analysis is much simpler than temporal complexity analysis.

conclusion

Complexity is also called progressive complexity, including time complexity and space complexity, which is used to analyze the growth relationship between algorithm execution efficiency and data size. It can be roughly expressed as: The higher the algorithm of order complexity, the lower the execution efficiency. There are not many common complexities, ranging from low to high:O(1),O(logn),O(n),O(nlogn),O (n squared).

Refer to the link

The beauty of data structures and algorithms