Time complexity

When we usually program, how to determine which code blocks have the shortest running time, and how to reflect the speed of the algorithm?

That’s where the time complexity comes in. Time complexity is a measure, or a formula, used to evaluate the efficiency of an algorithm.

Let’s look at the following example:

Example 1: Time complexity O(1)

print("Hello World")
Copy the code

Example 2: Time complexity O(n)

for i in range(n):
    print("Hello World")
Copy the code

Example 3: Time complexity O(n2n^2n2)

for i in range(n):
    for j in range(n):
        print("Hello World")
Copy the code

Example 4:

n = 64
while n > 1:
    print(n)
    n = n // 2   N goes into 2
Copy the code

Let’s look at example 4, based on the code algorithm, for example: 26=642^6=6426=64, log264=6{log_2{64}}=6log264=6, so the time complexity here is denoted as O(log2n{log_2{n}}log2n) or O(logn{log_{n}}logn).

Summary of time complexity

  • Time complexity is a measure or unit used to estimate the running time of an algorithm
  • In general, algorithms with high time complexity are slower than algorithms with low complexity
  • Common time complexity (in order of efficiency)
O(1) > O(${log_{n}}$) > O(n) > O(n${log_{n}}$) > O($n^2$) > O($n^3$)
Copy the code

Quick judgment of algorithm complexity

For most simple cases:

  • Let’s say the problem size n, for example for sorting a list, the problem size is the length of the list
  • Cyclic halving logn, see if the algorithm has cyclic halving
  • The cycle of the k layer with respect to n n to the k

Complexity: Judge according to the execution process and meaning of the algorithm

Spatial complexity

Space complexity: A measure used to evaluate the size of memory footprint when using an algorithm.

Space complexity is expressed in exactly the same way as time complexity:

  • The algorithm uses several variables: O(1)
  • The algorithm uses a one-dimensional list of length N: O(n)
  • The algorithm uses a two-dimensional list of m rows and n columns: O(mn)

When we say algorithm complexity in peacetime development, it often refers to time complexity. It is necessary to consider using space for time. Most of them are considering that time is more important than space, because space can be maintained by machines and equipment, for example; Add memory, add disk, etc., and time is limited and can’t wait.