3장 빅 오 표기법

컴퓨터 과학자는 서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다.

이러한 개념을 형식화한 표현을 빅 오 표기법이라고 부른다. 빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.

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

빅 오는 특정 방식으로 알고리즘에 필요한 단계 수를 고려함으로써 일관성을 유지한다. 최악의 경우 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. 빅 오 표기법으로는 O(N)이라 표기한다.

O(N)은 데이터 원소가 N개일 때 알고리즘에 N단계가 필요하다.

배열에 원소가 N개일 때 선형 검색에 몇 단계가 필요할까? 선형 검색에는 N단계가 필요하므로 O(N)으로 표현한다. 그래서 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 부른다

배열 읽기에 필요한 단계 수는 배열에 크기와 상관없이 딱 하나 따라서 O(1)이라 표현하고 “오 1” 이라고 발음한다. 즉, 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.

이러한 이유로 O(1)을 “가장 빠른" 알고리즘 유형으로 분류한다. 데이터가 늘어나도 O(1) 알고리즘의 단계 수는 증가하지 않는다.

O(1) 알고리즘을 상수 시간을 갖는 알고리즘이라고도 표현한다.

3-2 빅 오의 본질

빅 오 표기법은 머릿속에 새겼던 핵심 질문. 즉, 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가에 대한 답이다.

데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 가정해보면 원소가 N개일 때 알고리즘에 항상 3단계가 필요하다 이를 빅 오로 표현하면 O(3)이 아니라 O(1)이다.

빅 오의 본질이란 빅 오가 진정으로 의미하는 것 즉, 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 말한다. 빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다. 데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.

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(log₂N)은 데이터 원소가 N개 있을 때 알고리즘에 O(log₂N)단계가 걸린다는 의미.

원소가 8개면 O(log₂8) = 3 이므로 이 알고리즘은 3단계가 걸린다.

간단히 말해, 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 루프에서 원소 수만큼 단계가 걸리므로 이 알고리즘의 효율성은 O(N)이다.

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

}

이 코드는 number를 인수로 받아 2부터 number까지의 모든 수로 number를 나눠서 나머지가 있는지 확인한다. 나머지가 없으면 당연히 이 수는 소수가 아니므로 바로 false를 반환한다. number까지 모두 나눴는데도 항상 나머지가 있으면 이 수는 당연히 소수이므로 True를 반환한다.

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

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

3-7 마무리

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