In the last article, we saw two solutions to a simple algorithmic problem, and we used complexity analysis to determine which solution was more appropriate. Here, complexity is an important metric used to measure the efficiency of the program.

Although there is an old saying “it doesn’t matter if a cat is white or black, a cat that catches mice is a good cat”, this saying is results-oriented, yes. But if you have a program that needs to process a lot of data, and one programmer writes a program that takes two days to execute, and another programmer runs it in half an hour, then the second one is obviously more suitable for our actual needs.

What is complexity

Complexity is a function of the amount of input data n.

It’s easy to express complexity by wrapping it around a capital O and parentheses O(). For example, if the complexity of this code is f(n), it can be written as O(f(n)).

There are three things to keep in mind when calculating complexity:

  • The complexity is independent of the specific constant coefficients
  • Add polynomial-level complexity and choose the higher one as the result
  • O(1)Denotes special complexity

1. Complexity is independent of specific constant coefficients

For example, reverse a list instead of reverse().

Def demo_1(): a = [1, 2, 3, 4, 5] b = [0 for x in range(0,5)] # the second for loop b = [n - I - 1] a [I] print (b) if __name__ = = "__main__" : Demo_1 () = = = = = = = = = = = = = = = run results = = = = = = = = = = = = = = = = = = D: \ \ designed \ Python Python36 \ Python exe D: / practice/leecode fuzadu. Py [5, 4, 3, 2, 1] Process finished with exit code 0Copy the code

So you can see that I started with a for loop to create a list that’s the same length as the A list, with all zeros. A for loop is then used to put elements from A into B in reverse order, resulting in a list in reverse order of A.

The time complexity of each for loop is O(n), and the sum of the two loops is O(n)+O(n), which is also O(n+n), which is also O(2n). That is, a piece of code of O(n) complexity is executed twice, and the complexity is the same.

2. Add polynomial-level complexity and choose the higher one as the result

With the example above, this makes a lot of sense. If the complexity of an algorithm is O(n ^2)+O(n), then we know that as n gets bigger and bigger, that is, as the input gets bigger and bigger, the rate of change of n^2 is much higher than that of n, so we just take the rate of change of n^2, which is O(n ^2)+O(n) is the same thing as O(n ^2).

O(1) denotes special complexity

Again, using the inversion problem above, let’s use the second solution.

def demo_2(): a = [1, 2, 3, 4, 5] tmp = 0 n= len(a) for i in range(n//2): # / / said integer division, to return to one of the biggest integer no greater than the results of TMP = a [I] a [I] = a [n - I - 1] a [n - I - 1] = TMP print (a) if __name__ = = "__main__" : Demo_2 () = = = = = = = = = = = = = = run results = = = = = = = = = = = = = = D: \ \ designed \ Python Python36 \ Python exe D: / practice/leecode fuzadu. Py [5, 4, 3, 2, 1] Process finished with exit code 0Copy the code

The second solution has one less for loop than the first one, and the number of loops is only half that of the list, so the time complexity is O(n/2). Because complexity is independent of specific constant coefficients, the time complexity of this code is still O(n).

But in terms of spatial complexity, the second solution opens up a new variable TMP, which is independent of the array length. The input is an array of 5 elements, which requires a TMP variable and the input is an array of 50 elements, which again requires only one TMP variable.

Therefore, the space complexity is independent of the length of the input array, which is O(1).

Analyze complexity

Here are some empirical conclusions that can be used directly:

  • A sequential structure of code, time complexity isO(1).
  • A simple for loop, time complexity isO(n).
  • The time complexity of two sequential for loops is zeroO(n)+O(n)=O(2n)In fact, it isO(n).
  • Two nested for loops, the time complexity isO (n squared).
  • Binary search, both in timeO(logn).

To strike while the iron is hot, consider the following code:

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        for (k = 0; k < n; k++) {
        }
        for (m = 0; m < n; m++) {
        }
    }
}
Copy the code

If you look at the innermost layer, the innermost layer is a for loop with two sequential structures, order n. The middle layer has a nested for loop, so it’s O(n^2). Finally, the outermost layer has a nested for loop, so the final complexity is O(n^3).

Although the test engineer’s code is not high or even very low on complexity, I feel it is necessary to understand complexity and be able to do some simple analysis.