Common time complexity

O(1): No loops, no recursion, all O(1)

function test(){
   console.log('1111')
}
Copy the code

O(n): Only one loop or recursion, both O(n)

function test(n){ for(let i = 0; i<n; i++){ console.log('12121') } } function test2(n){ while(--n > 0){ console.log('22222') } }Copy the code

O(n²): n times in the inner loop, n times in the outer loop, the total number of times is n X n, the time complexity is n squared, which is O(n²).

Function test(n){for(let I = 0; i<n; i++){ for(let j = 0; j<n; J ++){console.log('111111')}}} function test(n){for(let j = 0; j<n; j++){ console.log('111111') } for(let i = 0; i<n; i++){ for(let j = 0; j<n; j++){ console.log('22222') } } }Copy the code

O(logn) : The influence of the number of cycles mainly comes from n/2, and the time complexity is O(logn).

function test(n){
  for (let i = 0; i < n; i *= 2){
    console.log('11111')
  }
}
test(16)
Copy the code

Spatial complexity

Definition: how much memory and space an algorithm needs

O(1)

function test(){
  console.log('11111')
}
Copy the code

O(n)

function test(n){ let arr = [] for(let i = 1; i < n; i++){ arr[i] = i } }Copy the code

O(n²): usually occurs in two-dimensional arrays, or matrices

Let arr = [1,2,3,4], [3,2,3,4]Copy the code