big O vs big Ω vs big Θ

O (Big O)

학계에서 big-O 는 시간의 상한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 O(N) 으로 표현할 수도 있지만, 이 외에 N 보다 큰 big-O 시간으로 표현할 수도 있다.

예를 들어, $O(N^2), O(N^3), O(2^N)$ 도 모두 옳은 표현이다. 다시 말해 실제 알고리즘의 수행시간은 적어도 이들 중 하나보다 빠르기만 하면 된다.

Ω (Big Omega)

학계에서 Ω 는 하한을 나타낸다. 해당 알고리즘은 Ω 수행 시간보다 빠를 수 없다.

Θ (Big Theta)

학계에서 Θ 는 O 와 Ω 둘다를 의미한다. 즉, 어떤 알고리즘의 수행시간이 O(N) 이면서 Ω(N) 이라면, 이 알고리즘의 수행 시간을 Θ(N) 으로 표현할 수 있다.

업계에서는 (즉, 면접에서는) 보통 Θ 와 O 를 하나로 합쳐 표현한다. 즉, 업계에서 big-O 의 의미는 학계에서 Θ의 의미와 가깝다.

때문에 배열을 출력하는 알고리즘을 $O(N^2)$ 으로 표현하기보다는 그냥 O(N) 으로 표현한다.

많이 사용되는 big-O 시간

왼쪽으로 갈수록 시간이 적게 걸린다. 즉, 더 빠르다.

$O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)$

상수항은 무시하라.

big-O 는 단순히 증가하는 비율을 나타내는 개념이므로, 특수한 입력에 한해 O(N) 코드가 O(1) 코드보다 빠르게 동작하는 것은 매우 가능성 있는 얘기이다.

이런 이유로 우리는 수행 시간에서 상수항을 무시해 버린다. 즉, O(2N) 으로 표기되어야 할 알고리즘을 실제로는 O(N) 으로 표기한다.

아래의 코드를 살펴보자.

//
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// O(N)
for (int x : array) {
	if (x < min) min = x;
	if (x > max) max = x;
}

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// O(2N)

for (int x : array) {
	if (x < min) min = x;
}

for (int x : array) {
	if (x > max) max = x;
}

왼쪽의 코드는 O(N) 짜리 코드이고, 오른쪽의 코드는 O(2N) 짜리 코드이다. 어느것이 더 빠른가?

실행되는 실제 instruction 의 개수를 직접 세어 보려면, assembly 단계에서 곱셈이 덧셈보다 더 많은 명령어를 사용한다는 점, 컴파일러가 나름의 최적화를 한다는 점, 그리고 모든 다른 종류의 세부사항들 또한 고려해야 한다.

이런 작업은 몹시 복잡하므로 위 두개의 코드 중 코드만 보고 실제로 어떤 것이 더 빠른지 알기란 어렵다.

big-O 표기법은 수행 시간이 어떻게 변화하는지를 표현해주는 도구이다. 따라서 O(N) 이 언제나 O(2N) 보다 나은 것이 아니라는 사실만 받아들이면 된다.

지배적이지 않은 항은 무시하라

수식에서 지배적이지 않은 항은 무시해도 된다.

• $O(N^2 + N)$ 은 $O(N^2)$이 된다.

• $O(N + logN)$ 은 $O(N)$ 이 된다.

• $O(5 * 2^N + 1000N^100)$ 은 $O(2^N)$ 이 된다.

단, 여기서 주의할 점은 변수가 여러개인데, 변수들간의 특별한 관계를 알지 못하는 경우는 하나의 항으로 줄일 수 없다.

예를 들어, $O(B^2 + A)$ 는 하나의 항으로 줄일 수 없다. (A 와 B 사이에 존재하는 특별한 관계를 알고 있지 않는 이상 ..)

상환시간 (Amortized time)

최악의 경우는 가끔 발생하지만, 한 번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용(수행 시간) 을 분할 상환 한다는 개념이다.

ArrayList 를 예로 봐보자.

ArrayList 는 배열로 구현되어 있다. 배열의 용량이 꽉 찼을 때, ArrayList 클래스는 기존보다 크기가 두 배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사한다.

즉, 배열의 크기가 2의 승수가 되었을 때 원소를 삽입하면 용량이 두 배로 증가한다.

예를 들어, 배열의 크기가 1, 2, 4, 8, 16, ... X 일 때, 새로운 원소를 삽입하면 배열의 용량이 두배로 증가하고, 이때 기존의 1, 2, 4, 8, 16, 32, 64, ... X 개의 원소 또한 새로운 배열로 복사를 해줘야 한다.

즉, 배열의 크기가 X 개일때 새로운 원소를 삽입하게 되면, 그 전 배열의 크기는 X 의 절반이었을 것이므로, X/2 만큼 원소를 복사해야 한다.

따라서, 위의 경우 복사해야 하는 원소의 총 개수는 X/2 + X/4 + X/8 + ... + 2 + 1 이 된다. 이 수열의 합은 N 에 근접하게 되는데 다음과 같은 상황을 상상해 보면 쉽다.

1km 떨어진 상점에 걸어가려고 한다. 0.5 km 를 걷고 난 뒤, 또 다시 0.25 km 를 걷고, 다음에는 0.125 km 를 걷는다. 이렇게 길이를 반씩 줄이는 행위를 무한정으로 하더라도 1km 에 아주 가까워질 수는 있지만 절대 1km 이상 걸을 수는 없다.

따라서 N 개의 원소를 삽입할 때 걸리는 시간은 O(N) 이 된다. 그렇기 때문에 각 삽입이 걸리는 시간은 O(1) 이 된다.

Log N 수행시간

어떤 문제의 탐색공간 (원소의 개수) 가 절반씩 줄어든다면 그 문제의 수행시간은 $O(log N)$ 이 될 가능성이 크다.

재귀적으로 수행시간 구하기

다음 코드를 살펴보자

int f(int n) {
	if (n <=1) {
		return 1;
	}

	return f(n-1) + f(n-1);
}

함수 f 가 두번 호출된 것을 보고 많은 사람들은 성급하게 이 코드의 시간 복잡도를 $O(N^2)$ 로 결론 내릴 수 있지만, 이것은 틀렸다.

이 코드에서는 재귀를 트리로 표현하였을때, 트리의 깊이가 N 이고, 각 노드는 두 개의 자식 노드를 갖고 있다. 따라서 깊이가 한 단계 깊어질 때마다 이전보다 두 배 더 많이 호출하게 된다.

피보나치 재귀 코드의 깊이와 노드의 갯수

깊이	노드의 갯수	노드의 개수의 다른 표현
0	$2^0$	1
1	$2^1$	2
2	$2^2$	4
3	$2^3$	8
4	$2^4$	16

위와 같이 재귀 함수에서 보통(항상은 아니다) $O(분기^{깊이})$ 로 표현되곤 한다. 여기서 분기란 재귀 함수가 자신을 재호출하는 횟수를 뜻한다.