[자료구조]시간복잡도(Time Complexity)와 알고리즘, 자료구조

big- O 표기법

• 입력값에 따른 연산에 걸리는 시간을 변수에 따라 표기

O(1)

• 간단한 인덱싱

  function O_1_algorithm(arr, index) {
   return arr[index];
  }
  let arr = [1, 2, 3, 4, 5];
  let index = 1;
  let result = O_1_algorithm(arr, index);
  console.log(result); // 2

O($n$)

• 시간복잡도가 linear하게 증가
• range 길이가 n개인 for문이 대표적

O($logn$)

• 업다운 게임을 생각
• BFS 알고리즘이 대표적

O($n^2$)

• 이중 for문

O($2^n$)

• 재귀함수가 대표적(피보나찌)

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

시간복잡도를 구하는 요령

하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n m) -> O (n²)
컬렉션 정렬을 사용하는 경우 : O(nlog(n))

정렬 알고리즘 시간복잡도 비교

자료구조 시간복잡도 비교

[https://blog.chulgil.me/algorithm/]