Time Complexity and Space Complexity

#algorithm

Introduction

When we practice LeetCode algorithm problems, we often need to calculate the time complexity and space complexity. We learn how to calculate time complexity and space complexity from a simple case.

Time Complexity

Calculation principle:

  • No bottom-order terms
  • Ignore coefficients for higher order terms

Give a few simple examples

  1. Sorting an unordered array

Assume unordered array of length n

An unordered array [6,5,1,3,4,2] can be assumed for experimentation

  • Traverse from position 0 to position n - 1, take the minimum value and put it at position 0, it takes time n
  • Traverse from position 1 to position n - 1, take the minimum value and put it at position 1, it takes time n - 1
  • Traverse from position 2 to position n - 1, take the minimum value and put it at position 2, it takes time n - 2
  • so loop to the last position, it takes time 1

The following traversal process

Position            0   1   2   3   4 ... (n - 3) (n - 2) (n - 1)
                    ⊢---------------------------------------⊣
Traverse n times   min
                        ⊢-----------------------------------⊣
traverse n - 1 times   min
                            ⊢-------------------------------⊣
traverse n - 2 times       min
                                ⊢---------------------------⊣
traverse n - 3 times           min
.
.
.
                                                             ‖
traverse once                                               min

Finally add up the time

n + (n - 1) + (n -2) + ... + 1

Sum formula based on arithmetic progression

n * a1 + n * (n-1) / 2 * d

convert to

n * a1 + d / 2 * n^2 - d / 2 * n

Where a1,d / 2,d / 2 are constant coefficients, n is used to calculate

The constants of this formula can also be simplified to

a * n ^ 2 + b * n + c

According to the principle of time complexity, do not use the low-order items b * n and c, ignore the coefficient a of the high-order item a * n ^ 2, and get its time complexity as O(n ^ 2)

  1. Dichotomy of sorted array to find elements

Assuming a sorted array [1,2,3,4,5,6,7,8], find the position of the number 7

  • Get the middle position for the first time Math.floor((0 + 7) / 2) = 3, judge the number 4 < 7, continue to find
  • Get the middle position for the second time Math.floor((3 + 7) / 2) = 5, judge the number 6 < 7, continue to find
  • Get the middle position for the third time Math.floor((5 + 7) / 2) = 6, judge the number 7 == 7, find the position 7
Position        1   2   3   4   5   6   7   8
The first time              ▲
The second time                     ▲
The third time                          ▲

The length of the array is 8, and the result can be obtained by using the dichotomy method at most 3 times. We find that log2(8) = 3, so the time complexity is O(log2(n)), usually abbreviated as O(log( n))

  1. Intersection of two sorted arrays A, B

A array length n, B array length m, because the size of n and m cannot be compared, it is impossible to determine which is higher order, so the time complexity is brought with n and m m

There are three algorithms

  • Traverse all A, traverse all B, time complexity O(n * m)
  • Traverse all A, bisection traverse B, time complexity O(n * log(n))
  • Double pointer traversal A, B, time complexity O(n + m)

Space Complexity

Calculation principle:

Refers to extra space, space used for input and output is not counted

For a simple example, reverse an ordered array

  • The first method: create a new auxiliary array of the same size, traverse the array backwards, insert all the contents into the auxiliary array, and then return the auxiliary array, then the space complexity is O(n)
  • The second method: traverse the array, directly swap the numbers of the two pointers at the head and tail, without creating a new auxiliary array, but directly operate on this array, then the space complexity is O(1)

Expand Learning

The meaning of the optimal solution of an algorithm for a program problem: Except for special declarations, the smallest space is used when the time complexity is optimal first.

Conclusion

The above is what the I have learned from learning an introductory algorithm video course recently. Simply make a programming study note, and more in-depth algorithm complexity calculation needs to be further studied. The follow-up I will learn and update new content, including some algorithm solutions, leetcode study notes, classic algorithm explanations, etc. If you have any questions, please comment.

Comments