Big-O complexity chart

Big-O : 입력값 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 표기하는 방법

• O(1) : 입력값이 증가하더라도 시간이 늘어나지 않음, 입력값의 크기와 관계없이 , 즉시 출력값을 얻어낼 수 있음

function algorithm(arr,index){
  let result = [];
  result.push(arr[index]);
  return result;
}

let arr = [0,1,2,3,4]

algorithm(arr,3);
// [3]

• O(n) : 입력값이 증가함에 따라 시간 또한 같은 비율로 증가

function algorithm(n){
  let result = [];

  for(let i = 0; i < n; i+=1){
    result.push(i)
  }
  return result;
}

algorithm(5);
// [0,1,2,3,4]

• O(log n) : O(1) 다음으로 빠른 시간 복잡도
• O(n²) : 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가

function algorithm(n){
  let result = [];
  for(let i = 0; i < n; i+=1){
    for(let j = 0; j < n; j+=1){
      result.push(j)
    }
  }
  return result;
}
algorithm(2);
// [0,1,0,1]

• O(2ⁿ) : 가장 느린 시간 복잡도

function fibonacci(n){
  if(n <= 1){
    return n;
  }
  return fibonacci(n-2) + fibonacci(n-1);
}