TIL 35 자료구조와 알고리즘 - 시간 복잡도

1. 점근 표기법

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.
출처 - 위키백과

점근 표기법은 시간복잡도를 근사치로 표현한 것과 같다. 그리고 시간복잡도는 크게 3가지의 종류가 있다.

1. 빅-오(Big O : Ο) : 최악의 경우(Worst Case)의 시간 복잡도
2. 빅-오메가(Big Omega : Ω) : 최선의 경우(Best Case)의 시간 복잡도
3. 빅-세타(Big Theta : Θ) : 평균적인 경우(Average Case)의 시간 복잡도

시간 복잡도를 계산할 때 가장 좋은 경우를 생각해야하니 빅 오메가를 사용하는 것이 좋다고 착각할 수 있다. 하지만 보통은 빅-오 표기법을 사용하는데 알고리즘이 가장 최악의 경우에 어느 정도의 성능이 나오는지를 측정하는 것이 더 정확하기 때문이다.

언제 어느 상황에서 최고의 상황일지 최악의 상황일지 모른다. 그래서 최악일 때 측정한 성능이 최고라고 생각할 수 있다. 예를 들어보겠다.

두 가지의 알고리즘이 있는데 A 알고리즘은 최고의 상황일 때 10의 수행시간이 걸리지만 최악일 때 100의 수행시간이 걸린다. 여기서 최고의 경우일 때가 빅 오메가이고, 최악의 경우가 빅 오이다. 그렇다면 최악의 경우일 때 걸린 수행 시간이 이 알고리즘의 수행 시간의 상한선이다.

결론은 빅오 표기법은 주어진(최악) 경우의 수행 시간의 상한을 나타낸다.

2. 빅-오(Big-O) 표기법의 종류

빅-오 표기법 성능

O(1) < O(log n) < O(n) < O(n * log n) < O(n²) < O(n³) < O(2^n) < O(n!)

O(1)

• 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘이다.

const arr = [1,2,3];

function test(arr) {
  console.log(arr[0]);
}

test(arr);

O(log n)

• 로그는 매우 큰 입력값에서도 크게 영향을 받지 않는 편이다. 매우 견고한 알고리즘으로 이진 탐색의 경우가 이에 해당한다. 오름차순으로 정렬되어 있는 배열에서만 사용할 수 있다.
  비교를 1회 할 때마다 탐색 범위가 절반으로 줄어들어 검색 기능을 구현할 때 유용하다.

function solution(element, arr) {
  let firstIndex = 0;
  let lastIndex = arr.length - 1;
  
  while(firstIndex <= lastIndex) {
      let centerIndex = Math.floor((firstIndex + lastIndex) / 2);

      if (element === arr[centerIndex]) {
          return centerIndex;
      }
      else if (element < arr[centerIndex]) {
          lastIndex = centerIndex - 1;
      }
      else {
          firstIndex = centerIndex + 1;
      }
  }

  return false;
}

console.log(solution(2,[1,2,3,4,5,6,7]))

O(n)

• 입력 데이터의 크기만큼 처리시간이 늘어나는 알고리즘이다. 이러한 알고리즘을 선형 시간 알고리즘이라 부른다. 정렬되지 않은 리스트에서 최대 또는 최솟값을 찾는 경우가 해당되며 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

const arr = [1,2,3];

function test(arr) {
  let sum = 0;
  
  for(let i=0; i<arr.length; i++) {
    sum += arr[i];
  }
  
  return sum;
}

test(arr);

O(n log n)

• 병합 정렬등의 대부분 효율이 좋은 알고리즘이 이에 해당 한다. 아무리 좋은 알고리즘이라 할지라도 n log n 보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수 있다.

O(n^2)

• 입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘이다. 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당 한다. 가장 쉽게 마주할 수 있는 상황이 이중 for문을 사용했을 때이다. n * n만큼 걸리기 때문에 숫자가 조금만 커져도 비효율적이게 된다.

const arr = [1,2,3];

function test(arr) {
  for(let i = 0; i < arr.length; i++) {
  	for(let j = 0; j < arr.length; j++) {
      console.log(arr[i],arr[j]);
    }
  }
}

test(arr);

O(2^n)

• 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 한다. n^2와 혼동되는 경우가 있는데 2^n이 훨씬 더 크다.

O(n!)

• 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.