3장 빅 오 표기법

빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.

3.1 빅 오: 원소가 N개일 때 몇 단계가 필요할까?

최악의 경우 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. 빅 오 표기법으로는 O(N) 이라고 표현한다.
O(N)은 데이터 원소가 N개일 때 알고리즘에 N단계가 필요하다는 의미이다.
O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 부른다.

배열 읽기에 필요한 단계 수는 배열의 크기와 상관없이 딱 하나다. 따라서 O(1) 이라고 표현한다.
즉, 데이터 원소가 몇 개가 있든 배열에서 읽기는 항상 한 단계이다. 이러한 이유로 O(1)을 가장 빠른 알고리즘 유형으로 분류한다.
O(1) 알고리즘을 상수 시간을 갖는 알고리즘이라고도 표현한다.

3.2 빅 오의 본질

데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 가정하자.
이 알고리즘의 빅 오 표기법은 O(3)이 아닌 O(1)이다.

빅 오의 본질: 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는가?

O(1)과 O(3)은 모두 데이터 증가에 영향을 받지 않는, 단계 수가 변하지 않는 유형이다.
본질적으로 같은 알고리즘 유형이다. 데이터와 관계 없이 단계 수가 일정하다.

O(N)은 데이터 증가가 성능에 영향을 미친다.
O(N)은 데이터가 늘어날 때 정확히 그 데이터에 비례해 단계 수가 증가하는 알고리즘 유형이다.

3.2.1 빅 오의 본질 더 파고들기

만일 데이터의 개수와 상관 없이 100단계가 걸리는 상수 시간 알고리즘이 있다고 가정하자.

원소가 100단계 이하인 데이터 세트에서는 100단계의 O(1) 알고리즘보다 O(N) 알고리즘이 단계 수가 적다.
하지만, 100보다 큰 모든 배열에서는 O(N) 알고리즘에 더 많은 단계가 걸린다.
100보다 큰 순간부터 무한대까지 O(N)은 O(1)보다 더 많은 단계를 필요로 한다.
100단계 뿐 아니라 백만 단계여도 마찬가지이다. 데이터가 증가할 수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 된다.

따라서, O(N)이 전반적으로 O(1)보다 덜 효율적이다.

3.2.2 같은 알고리즘, 다른 시나리오

선형 검색에서 찾고 있는 항목이 배열의 첫 번째 셀에 있다면 이때 선형 검색 사례는 O(1)이라 할 수 있다.
즉, 선형 검색의 효율성은 최선의 시나리오에서는 O(1), 최악의 시나리오에서는 O(N)이다.

빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다.

3.3 세 번째 유형의 알고리즘

이진 검색의 시간 복잡도는 O(logN) 이다.
이러한 유형의 알고리즘을 로그 시간의 시간 복잡도라고 말한다.
O(logN)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 빅 오의 방식이다.

O(1), O(logN), O(N)의 순서대로 효율적이다.

3.4 로가리즘

O(logN)에서의 log는 로가리즘의 줄임말이다.
로가리즘은 지수(exponent)와 역의 관계다. log₂8은 2³의 역이다. 즉, 2를 몇 번 곱해야 8을 얻을 수 있는지를 뜻한다. 2를 3번 곱해야 8이 나오므로 log₂8 = 3이다.

log₂8을 다른 방식으로 설명하면 다음과 같다:
1이 될 때까지 8을 2로 계속해서 나눌 때 등식에 얼마나 많은 2가 등장할까?
8 / 2 / 2 / 2 = 1 총 3번 등장하므로 log₂8 = 3이다.

3.5 O(logN)해석

컴퓨터 과학에서 O(logN)은 O(log₂N)을 줄여 부르는 말이다.
즉, O(logN)은 데이터 원소가 N개 있을 때 알고리즘에 log₂N단계가 걸린다는 의미이다.
간단히 말해, O(logN)은 원소가 하나가 될 때가지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.

3.6 실제 예제

다음은 리스트 내 모든 항목을 출력하는 코드이다.

const things = ["apples", "baboons", "cribs", "dulcimers"];

for (const thing of things) {
  console.log(`Here's a thing: ${thing}`);
}

복잡하지 않을지라도 뭔가를 하는 코드는 모두 엄밀히 알고리즘이다. 따라서 이 코드 역시 알고리즘 예제이다.
이 문제를 푸는 데 사용한 알고리즘은 console.log 문이 포함된 for 루프다.
for 루프에서 4단계가 걸리는데, 이 단계 수는 리스트의 원소 수와 동일하다. 즉, 이 알고리즘의 효율성은 O(N)이다.

const isPrime = (number) => {
  for (let i = 2; i < number; i++) {
    if(number % i === 0)  {
      return false;
    }
  }
  return true;
}

이 코드는 주어진 수가 2 이상일 때 소수인지 알아보는 알고리즘이다.

2부터 number까지의 모든 수로 number를 나눠서 나머지가 있는지 확인한다. 나머지가 없으면 소수가 아니므로 false를 반환하고, number까지 모두 나눴는데도 항상 나머지가 있으면 소수이므로 true를 반환한다.

여기서의 핵심 질문은 "number에 N을 전달할 때 알고리즘에 몇 단계가 필요할까?" 이다.

이 함수에서 for 루프는 함수로 전달된 수에 비례해 단계 수가 증가하므로 이 알고리즘의 효율성 역시 O(N)이다.

3.7 마무리

빅 오 표기법으로 실제 쓰이는 시나리오를 분석해서 다양한 자료 구조와 알고리즘 중 사용자의 코드를 더 빠르게 하고 더 큰 부하도 처리할 수 있는 방법을 고를 수 있다.