big-O 시간은 알고리즘의 효율성을 나타내는 지표 혹은 언어다. 이를 제대로 이해하지 못하면 알고리즘을 개발하는 데 큰 고비를 겪을 수 있다.
비유하기
디스크에 있는 파일을 다른 지역에 살고 있는 친구에게 가능하면 빨리 보내려고 한다고 가정할 때, 파일의 크기가 작다면 온라인을 통한 전송이 빠를 것이다. 하지만 파일이 1TB라면 하루이상 걸릴 수 있다. 그럴땐 직접 차를 타고 가는 것이 빠를지도 모른다.
시간 복잡도
위 내용이 바로 점근적 실행 시간, 또는 big-O 시간에 대한 개념이다. 위의 데이터 전송 예시의 알고리즘 실행 시간을 다음과 같이 설명할 수 있다.
- 온라인 전송 : O(s), s는 파일의 크기가 된다. 따라서 파일의 크기가 증가함에 따라 전송 시간 또한 선형적으로 증가한다.
- 직접 전송 : 파일의 크기와 관계없이 O(1), 상수 시간만큼 소요된다.
상수가 얼마나 큰지 또는 선형식이 얼마나 천천히 증가하는지에 관계없이 숫자가 커지다 보면 선형식은 언젠가 상수를 뛰어 넘게 된다.
big-O, big-ϴ, big-Ω
- O(big-O) : 학계에서 big-O는
시간의 상한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있지만, 이외에 N보다 큰 big-O 시간으로 표현할 수도 있다. - Ω(big-Omega) : 학계에서 Ω는
등가 개념 혹은 하한을 나타낸다. 알고리즘은 Ω 수행시간보다 빠를 수 없게 된다. - ϴ(big-theta) : 학계에서는 ϴ는
O와 Ω 둘 다를 의미한다. 어떤 알고리즘의 수행 시간이 O(N)이면서 Ω(N)이라면, 이 알고리즘의 수행 시간을 ϴ(N)로 표현할 수 있다.
최선의 경우, 최악의 경우, 평균적인 경우 : 알고리즘의 수행시간을 세 가지 다른 방법으로 나타낼 수 있다. 퀵 정렬의 관점에서 보면 퀵 정렬은 축이 되는 원소 하나를 무작위로 뽑은 뒤 이보다 작은 원소들은 앞에, 큰 원소들은 뒤에 놓이도록 원소의 위치를 바꾼다. 그 결과 부분 정렬이 완성되고, 그 뒤 왼쪽과 오른쪽 부분을 이와 비슷한 방식으로 재귀적으로 정렬해 나간다.
- 최선의 경우 : 만약 모든 원소가 동일하다면 퀵 정렬은 평균적으로 단순히 배열을 한 차례 순회하고 끝날 것이다. 즉 수행시간이 O(N)이 된다.
- 최악의 경우 : 운이 없게 배열에서 가장 큰 원소가 계속해서 축이 된다면 이런 경우에 수행시간은 O(N²)으로 악화된다.
- 평균적인 경우 : 보통 최선의 경우와 최악의 경우가 반복적으로 일어나는 일은 많지 않다. 따라서 수행시간은 평균적으로 O(N log N)이라고 말할 수 있다.
공간 복잡도
알고리즘에서는 시간뿐 아니라 메모리 또한 신경 써야 한다. 공간 복잡도는 시간 복잡도와 평행선을 달리는 개념이다. 크기가 n인 배열을 만들고자 한다면 O(n)의 공간이 필요하다. n * n 크기의 2차원 배열을 만들고자 한다면 O(n²)의 공간이 필요하다.
상수항은 무시하라
big-O는 단순히 증가하는 비율을 나타내는 개념이므로 특수한 입력에 한해 O(N)코드가 O(1) 코드보다 빠르게 동작하는 것은 매우 가능성 있는 얘기다. 이런 이유로 우리는 수행시간에서 상수항을 무시해 버린다. 즉 O(2N)으로 표기되어야 할 알고리즘을 실제로는 O(N)으로 표기한다.
big-O 표기법은 수행 시간이 어떻게 변화하는지를 표현해주는 도구이다. 따라서 O(N)이 언제나 O(2N)보다 나은 것은 아니라는 사실만 받아드리자
지배적이지 않은 항은 무시하라
수식에서 지배적이지 않은 항은 무시해도 된다.
- O(N² + N)은 O(N²)
- O(N + logN)은 O(N)
- O(5 * 2ᴺ + 1000N¹⁰⁰)은 O(2ᴺ)
여러 부분으로 이루어진 알고리즘 : 덧셈 vs 곱셈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//덧셈 수행 시간 O(A+B)
for(int a: arrA) {
print(a);
}
for(int b: arrB) {
print(b);
}
//곱셈 수행 시간 O(A*B)
for(int a: arrA) {
for(int b: arrB) {
print(a + ", " + b);
}
}
만약 알고리즘이 A 일을 모두 끝마친 후에 B 일을 수행하라의 형태라면 A와 B의 수행 시간을 더해야 한다.
만약 알고리즘이 A 일을 할 때마다 B 일을 수행하라의 형태라면 A와 B의 수행 시간을 곱해야 한다.
상환 시간
ArrayList는 배열의 역할을 함과 동시에 크기가 자유롭게 조절되는 자료구조이다. ArrayList는 배열로 구현되어 있다. 배열의 용량이 꽉 찼을 때 ArrayList 클래스는 기존보다 크기가 두 배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사한다.
배열이 가득 차 있는 경우, 배열에 N개의 원소가 들어 있을 때 새로운 원소를 삽입하려면 O(N)이 걸린다. 왜냐하면 크기가 2N인 배열을 새로 만들고 기존의 모든 원소를 새 배열로 복사해야 하기 때문이다. 따라서 이 경우에 삽입 연산은 O(N) 시간이 소요된다.
대다수의 경우, 배열에 가용 공간이 존재하고 이때의 삽입 연산은 O(1)이 걸린다.
상환 시간이라는 개념은 최악의 경우는 가끔 발생하지만 한 번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용을 분할 상환한다는 개념이다.
배열의 크기가 2의 승수가 되었을 때 원소를 삽입하면 용량이 두 배로 증가한다. 배열의 크기가 1, 2, 4, 8, 16, 32, ….X 일 때, 새로운 원소를 삽입하면 배열의 용량이 두 배로 증가하고, 이때 기존의 1, 2, 4, 8, 16, 32, …X개의 원소 또한 새로운 배열로 복사해줘야 한다. X개의 원소를 삽입할 때 필요한 시간은 O(2X)이고, 이를 분할 상환해보면 삽입 한 번에 필요한 시간은 O(1)이다.
log N 수행 시간
이진 탐색의 경우 N개의 정렬된 원소가 들어있는 배열에서 원소 X를 찾을 때 사용한다. 먼저 원소 x와 배열의 중간 값을 비교하고, x == 중간값 을 만족하면 이를 반한한다. x < 중간값일 때는 배열의 왼쪽 부분을 재탐색하고, x > 중간값일 경우에는 배열의 오른쪽 부분을 재탐색한다.
처음에 원소 N개가 들어있는 배열에서 시작해서 한 단계가 지나면 탐색해야 할 원소의 개수가 N /2로 줄어들고, 한 단계가 더 지나면 N /4 개로 줄어든다. 그러다 원소를 찾았거나 탐색해야할 원소가 하나만 남으면 탐색을 중지한다. 총 수행시간은 N을 절반씩 나누는 과정에서 몇 단계 만에 1이 되는지에 따라 결정된다. 이 때 사용되는 것이 log이다.
재귀적으로 수행시간 구하기
1
2
3
4
5
int f(int n) {
if(n <= 1)
return 1;
return f(n-1) + f(n-1);
}
f 함수가 두 번 수행된다고 해서 O(N²)라고 생각할 수 있다. 코드를 하나씩 읽어보면 f(4)는 f(3)을 두 번 호출하고, f(3)은 f(2)를 거쳐서 f(1)까지 호출한다.
트리의 깊이가 N이고 각 노드는 두 개의 자식 노드를 갖고 있다. 따라서 깊이가 한 단계 깊어질 때마다 이전보다 두 배 더 많이 호출하게 된다. (2ᴺ⁺¹ -1 이 됨) 이처럼 재귀함수에서 수행시간은 보통 O(깊이)로 표현되고는 한다. 위 예제의 경우 수행시간은 O(2ᴺ)이 된다.
예제 및 연습문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//1) O(N)
void foo(int[] array) {
int sum = 0;
int product = 1;
for(int i = 0; i < array.lengh; i++) {
product *= array[i];
}
System.out.println(sum + ", " + product);
}
//2) 안쪽 루프의 반복 횟수는 O(N)이고, 루프가 N번 반복되기 때문에 수행시간은 O(N²)이 된다.
void printPairs(int[] array) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length; j++) {
System.out.println(array[i] + ", " + array[j]);
}
}
}
//3) 2번 예제와 비슷하나 j가 i+1로 시작한다는 것이 차이가 있다. ==> O(N²) 걸린다. 72~73p
void printUnorderedPairs(int[] array) {
for(int i = 0; i < array.length; i++) {
for(int j = i+1; j < array.length; j++) {
System.out.println(array[i] + ", " + array[j]);
}
}
}
1
2
3
4
5
6
7
8
//4)
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for(int i = 0; i < arrayA.length; i++) {
for(int j = 0; j < arrayB.length; j++) {
//O(1) 시간이 걸리는 작업
}
}
}
arrayA의 원소 하나당 안쪽에 for 루프는 b(arrayB.length)회 반복된다. 따라서 arrayA.length일 때 수행시간은 O(ab)가 된다. O(N²)이라 생각할 수 있겠지만 서로 다른 두 개의 입력이 주어지므로 O(N²)이 아니다.
1
2
3
4
5
6
7
8
9
10
//5)
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for(int i = 0; i < arrayA.length; i++) {
for(int j = 0; j < arrayB.length; j++) {
for(int k = 0; k < 100000; k++) {
System.out.println(arrayA[i] + ", " + arrayB[j]);
}
}
}
}
위 경우에도 크게 달라질거 없다. 100,000은 상수항으로 간주되므로 수행 시간은 O(ab)가 된다.
1
2
3
4
5
6
7
8
9
//6)
void reverse(int[] array) {
for(int i = 0; i <array.length / 2; i++) {
int other = array.length - i - 1;
int temp = array[i];
array[i] = array[other];
array[other] = temp;
}
}
위 예제는 O(N) 시간에 동작한다. 배열의 절반만 살펴본다고 해서 big-O 시간에 영향을 끼치는 것은 아니다.
7)
다음 중 O(N)과 같은 것은?
- O(N+P), P < N/2 -> O
- O(2N) -> O
- O(N + logN) -> O
- O(N+M) -> X
8)
여러 개의 문자열로 구성된 배열이 주어졌을 때 각각의 문자열을 먼저 정렬하고 그 다음에 전체 문자열을 사전순으로 다시 정렬하는 알고리즘이 있을때 이 알고리즘의 수행 시간은?
틀린답변)
대부분 각 문자열을 정렬하는데 O(NlogN)이 소요되므로 모든 문자열을 정렬하는데 O(N * NlogN)이 소요되고, 그 다음 전체 문자열을 다시 사전순으로 정렬해야 하므로 O(NlogN)이 추가로 필요할 것이다. 따라서 전체 수행시간은 O(N²logN + NlogN)이 되고, 이를 정리하면 O(N²logN)이 될 것이라 생각한다.
위 답이 틀린 이유는 N을 서로 다른 두 가지 경우에 혼용(문자열의 길이를 나타낼 때, 배열의 길이를 나타낼 때)해서 사용했다는 점이다. 이와 같은 실수를 방지하기 위해서 변수 N을 아예 사용하지 않거나 N이 가리키는 것이 명백한 경우에만 사용하는 것이 좋다.
[정리]
- 각 문자열을 정리하는데 O(slogs) 소요
- a개의 문자열을 모두 정렬해야 하므로 총 O(a * slogs) 소요
- 전체 문자를 사전순으로 정렬, 문자열 두개를 비교하는데 O(s) 시간 소요, 총(aloga)번을 비교해야 하므로 결론적으로 O(a * sloga)가 소요된다.
위 두부분을 더해주면 전체 시간복잡도는 O(a * s(loga + logs))가 된다.
1
2
3
4
5
6
7
//9) 균형 이진 탐색 트리에서 모든 노드의 값을 더하는 코드
int sum(Node node) {
if(node == null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
위 코드는 트리의 각 노드를 한 번씩 방문한 뒤 각 노드에서(재귀호출 제외) 상수 시간에 해당하는 일을 수행한다. 따라서 수행 시간은 노드의 개수와 선형 관계에 있다. 즉 N개의 노드가 있을 때 수행시간은 O(N)이 된다.
재귀 함수에 분기가 여러 개 존재하는 경우 수행 시간은 일반적으로 O(분기^깊이)가 된다. 만약 분기가 두 개 존재하면 O(2^깊이)가 될 것이다. 지수 시간 알고리즘으로 표현되기는 했지만 결과적으로 보면 생각보다 나쁜 알고리즘은 아니다.
위 예제에서 나온 트리는 균형 이진 탐색 트리로 총 N개의 노드가 있다면 깊이는 대략 logN이 된다. 위의 수식에 따르면 수행시간은 O(2^logN)이 된다.
1
2
3
4
5
6
7
8
9
//10) 현재의 값보다 작은 수들로 나누어 떨어지는지 확인함으로써 현재 값이 소수인지 아닌지를 판별하는 코드
boolean isPrime(int n) {
for(int x =2; x * x <= n; x++;) {
if(n % x == 0) {
return false;
}
}
return true;
}
for 루프의 내부 코드는 상수 시간에 동작한다. 최악의 경우에 for 루프가 몇 번 반복하는지만 세어 보면 시간 복잡도를 구할 수 있다.
위 코드에서 루프는 x=2부터 x*x=n까지 반복한다. 즉 X=√n까지 반복한다는 뜻이다. 시간복잡도는 O(√n)
1
2
3
4
5
6
7
8
9
10
//11) n의 계승(factorial)을 구하는 코드
int factorial(int n) {
if(n < 0) {
return -1;
}else if(n == 0) {
return 1
}else {
return n * factorial(n-1);
}
}
단순히 n부터 1까지 반복하는 재귀함수이므로 O(n)이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//12) 문자열로 나타낼 수 있는 순열의 개수를 구하는 코드
void permutation(String str) {
permutation(str, "");
}
void permutation(String str, String prefix) {
if(str.length() == 0) {
System.out.println(prefix);
}else {
for(int i = 0; i < str.length; i++) {
String rem = str.substring(0, i) + str.substring(i + 1) ;
permutation(rem.prefix + str.charAt(i));
}
}
}
permutation 함수가 얼마나 많이 호출되는지, 각 호출마다 걸리는 시간이 얼마나 되는지 살펴보면 알 수 있다.
- 순열이 완성되는 시점에 permutation 함수가 몇 번이나 호출되는가 : 길이가 7인 문자열이 주어졌을 때 첫번째 자리는 7개의 선택권이 있다. 문자 하나를 선택했다면 그다음 자리는 6개의 선택권, 그 다음은 5개의 선택권…이 있다. 즉 7!(7의 계승)이 된다. => permutation 함수는 n!번 호출
- 순열 생성이 완성되기 전에 permutation 함수는 몇 번이나 호출되는가 : 1에서 말한대로 말단 노드는 n!이 되고 루트에서 말단 노드까지의 거리는 n이 될 것이다. 따라서 전체 노드의 개수는 n*n!개를 넘지 못한다.
- 각 함수 호출을 처리하는 데 얼마나 오래 걸리나 : 문자열을 연결해주는 연산을 수행하므로 O(n) 시간이 걸릴 것이다. 또 rem, prefix, str.charAt(i)의 길이의 합은 항상 n이 되는 것을 알 수 있다. 따라서 호출 트리의 각 노드가 처리하는 일은 O(n)이 된다.
- 총 수행 시간은 어떻게 되는가? : permutation 함수는 O(n*n)번(상한) 호출되고 한 번 호출될 때마다 O(N) 시간이 걸리므로 총 수행 시간은 O(nen)을 넘지 않을 것이다.
1
2
3
4
5
//13) n번째 피보나치 수를 구하는 코드
int fib(int n) {
if(n <= 0) return 1;
return fib(n-1) + fib(n-2);
}
재귀 호출의 패턴을 이용하면 O(분기^깊이)가 된다. 각 호출마다 분기가 2개 존재하므로 깊이가 N일 떼 수행 시간은 O(2ᴺ)이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
//14) 0부터 n까지의 피보나치 수열 전부를 출력하는 코드
void allFib(int n) {
for(int i = 0; i < n; i++) {
System.out.println(i + ":" + fib(i));
}
}
int fib(int n) {
if(n <= 0) return 0;
else if(n == 0) return 1;
return fib(n-1) + fib(n-2);
}
여기서는 n이 변한다는 점이 중요하다. fib(n)은 O(2ᴺ)이 걸리지만 n번의 호출이 모두 다른 n을 사용하므로 이를 반영해서 계산하는 것이 중요하다.
- fib(1) : 2¹번 호출
- fib(2) : 2²번 호출
- fib(3) : 2³번 호출
- fib(4) : 2⁴번 호출
81~88p