The fundamental purpose of complexity study is to reduce complexity and find an optimal solution between time complexity and space complexity.

1. What is time complexity

  • A function is denoted by big O, such as O(1), O(n), O(logN).
  • Qualitatively describe the running time of the algorithm

Time complexity diagram

1 < log2n < √n < n < nlog2n < n2 < 2n < n!
Copy the code

O(1)

O (1) No loop is executed only once

let i = 0;
i +=1
Copy the code

O(n)

The loop executes n times

for (let i = 0; i < n; i += 1) {
    console.log(i)
}
Copy the code

O(1) + O(n) = O(n)

If O(n) is large enough, O(1) is ignored

let i = 0;
i +=1

for (let i = 0; i < n; i += 1) {
    console.log(i)
}
Copy the code

O(n) * O(n) = O(n^2)

Multiply the same

for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
        console.log(i, j)
    }
}
Copy the code

O(logN)

Log base 2 of N how many times does 2 go N

I keep taking 2 to the first power of 2 to the second power of 2 and I know that this is greater than or equal to n how many logn times does the code in the while loop execute

let i = 1;
while (i < n) {
    console.log(i)
    i * 2;
}
Copy the code
  1. Spatial complexity
  • A function is denoted by big O, such as O(1), O(n), O(logN).
  • A measure of the amount of storage temporarily occupied by an algorithm while it is running

O(1)

The value of each base type is a spatial computation unit

let i = 0;
i +=1
Copy the code

O(n)

Because there are n Spaces in the array

const list = []
for(let i = 0; i< n; i++){
  list.push(i)
}
Copy the code

O(n^2)

Because a matrix stores multidimensional values and the essence of a matrix is a two-dimensional array

const matrix = []
for(let i = 0; i < n; i++){
  matrix.push([])
  for(let j = 0; j < n; j++){
    matrix[i].push(j) 
  }
}
Copy the code

To consider

1. If a piece of code has 3 cycles with n cycles, is the time complexity of the code O (3n) or O (n)?

  • If three loops are side-by-side blocks, the time is order n.
  • If three loops are nested blocks, the time complexity is O(n^3).
  • If three loops have only two nested, the time complexity is O(n^2) + O(n) = O(n^2).

2. Suppose every night before you go to sleep, you count 2 to the power of 1, 2, 4, 8… Every time you count to n before falling asleep, how many do you count? What is the time complexity?

  • That’s log n plus one number
  • The time is order log n.

The time and space complexity of common data structure operations

Link to the original image above:From [yefeng bosses] : https://zhuanlan.zhihu.com/p/143358017

Welcome to the comments section