시간 복잡도

• 알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산횟수의 상한을 의미
• 예상 처리 시간을 측정
  • 수만개 혹은 수 억개의 데이터를 처리해야 한다면? 과연 어느정도 시간이 걸릴까?
• 지연 장애가 발생했을 때 왜 발생했는지 찾을 수 있는 근거

성능을 측정할 때 보는 두가지

• 최악의 경우를 고려해라
  • 코딩 테스트에서는 아주 다양한 조합으로 입력값을 넣어 코드를 평가하게 되는데 그 중 최악의 입력값도 있기 때문에 최악의 경우를 기준으로 복잡으룰 분석해야 함
• 알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용한다
  • 예를 들어서 친구와 10시에 만나기로 했을 때 친구가 "언제쯤 도착해"라고 물었을 때 100분의 1초, 1000분의 1초까지 엄밀하게 고민해서 도착시간을 말하는 경우는 없다.
    대략 "5분 전쯤 도착해"라고 말한다. 즉 위 예시와 같이 대략적인 연산 횟수의 추이만 알고 있어도 성능을 충분히 가능할 수 있다.

big-O 표기법

• O(1)

  • 입력 데이터 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘
  • ex) 배열, Hash
    

  function O_1_algorithm(arr, index) {
    return arr[index];
  }

• O(n log n)

  • 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
  • 이진 검색

  function O_log_n_algorithm(n) {
    let a = b = 0;
    while (a < n) {
      b += 1
      a = a * 2
    }
    return b;
  }

• O(n)

  • 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘
  • for문
    

  function O_n_algorithm(n) {
    for (let i = 0; i < n.length; i++) {
      // do something
    }
  }

• O(n²)
  • 입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘
  • 중첩 for문

   function O_quadratic_algorithm(n) {
     for (let i = 0; i < n; i++) {
       for (let j = 0; j < n; j++) {
         // do something
       }
     }
   }