Big-O(빅오) 표기법이란?
개요
알고리즘과 관련된 컨텐츠를 접할 때, 아마 Big-O 란 용어를 봤을 것인데, Big-O 표기법은 알고리즘의 비용을 분석하는 기본 도구 중 하나이다.
소프트웨어 개발자가 깊이 있게 이해한다는 것은 굉장히 중요한 일이다.
Wikipedia 에서는 Big-O 표기법에 대해서 이렇게 설명한다.
Big-O 표기법은 인수가 특정 값이나 무한대로 향하는 경향이 있을 때, 함수의 제한 동작을 설명하는 수학적 표기법이다.
간단히 말해서, Big-O 표기법은 대수 용어를 사용하여 코드의 복잡성을 설명한다.
알고리즘 복잡도 계산 항목
- 시간 복잡도 : 알고리즘의 실행 속도(주 계산 항목)
- 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈
알고리즘 시간 복잡도는 반복문이 핵심이고, 최악의 실행 시간을 표기하므로 아무리 최악이라도 이정도의 성능은 보장한다는 뜻이다.
Big-O 표기법 적용 예
Big-O 표기법의 이해를 위해 Big-O 의 제곱인 O(n²) 로 예를 들어보겠다.
여기서 문자 "n" 은 입력 크기를 나타내며 "O()" 내부의 함수 "g(n) = n²" 은 입력 크기와 관련하여 알고리즘이 얼마나 복잡한지 알려준다.
복잡도가 O(n²) 인 일반적인 알고리즘은 Selection Sort(선택 정렬) 알고리즘이 있겠다.
Selection Sort 알고리즘은 List 의 정렬되지 않은 부분에서 가장 작은(또는 큰) element 를 반복적으로 선택하여 List 의 정렬된 부분으로 이동하는 간단하고 효율적인 알고리즘이다.
- List 의 정렬되지 않은 부분에서 가장 작은(또는 큰) element 를 반복적으로 선택하고, 정렬되지 않은 부분의 첫 번째 element 와 교체한다.
- 전체 List 가 정렬될 때까지 목록의 정렬되지 않은 나머지 부분에 대해서 과정을 반복한다.
변형을 준 알고리즘으로 Bidirectional Selection Sort 가 있는데, 가장 작은 element 와 가장 큰 element 를 번갈아가며 List 를 통과하므로 경우에 따라 알고리즘이 더 빨라질 수 있다.
위 알고리즘은 주어진 배열에서 2가지의 subarray 를 유지해야 한다.
- 정렬된 subarray
- 정렬되지 않은 나머지 subarray
Selection Sort 알고리즘을 반복하면서, 정렬되지 않은 subarray 의 최소 element(오름차순 고려)가 선택되어 정렬되지 않은 subarray 의 시작 부분으로 이동된다.
반복할 때마다 정렬된 subarray 의 크기는 1씩 증가하고 정렬되지 않은 subarray 의 크기는 1씩 감소한다.
N(배열의 크기)번 반복 후에 정렬된 배열을 얻게 된다.
array[] = {55, 27, 15, 21, 12} 의 배열로 예를 들어 본다.
1차 시도
배열의 첫 번째 위치에 대해 전체 배열이 인덱스 0에서 4까지 순차적으로 순회한다.
현재 55가 저장된 첫 번째 위치는 전체 배열을 탐색한 후 12가 가장 낮은 값임을 알 수 있다.
| 55 | 27 | 15 | 21 | 12 |
따라서 55와 12의 자리를 바꾼다.
한 번 반복하면 배열에서 가장 작은 값인 값이 정렬된 목록의 첫 번째 위치에 나타나는 경향이 있다.
| 12 | 27 | 15 | 21 | 55 |
2차 시도
27이 있는 두 번째 위치의 경우 다시 배열의 나머지 부분을 탐색한다.
| 12 | 27 | 15 | 21 | 55 |
순회 후, 15가 배열에서 두 번째로 낮은 값이기에 배열의 두 번째 위치에 나타나야 한다는 것을 발견하고 자리를 교환한다.
| 12 | 15 | 27 | 21 | 55 |
3차 시도
이제 세 번째로 27이 있는 곳에서 다시 배열의 나머지 부분을 탐색하고 배열에 있는 세 번째로 작은 값을 찾는다.
| 12 | 15 | 27 | 21 | 55 |
순회하는 동안 21이 세 번째로 작은 값으로 나왔고, 배열의 세 번째 위치에 나타나야 한다.
| 12 | 15 | 21 | 27 | 55 |
4차 시도
네 번째 위치의 경우 배열의 나머지 부분을 탐색하고 배열에서 네 번째로 작은 element 를 찾는다.
27은 네번 째로 작은 값이므로 네번 째 자리에 위치한다.
| 12 | 15 | 21 | 27 | 55 |
5차 시도
마침내 배열에 존재하는 가장 큰 값이 배열의 마지막 위치에 자동으로 배치된다.
정렬된 배열이 완성되었다.
| 12 | 15 | 21 | 27 | 55 |
Java 로 작성한 코드
public class SelectionSort {
static int[] sort(int[] array) {
for (int count = 0; count < array.length - 1; count ++) {
int minId = count;
for (int count2 = minId + 1; count2 < array.length; count2++) {
if (array[minId] > array[count2]) minId = count2;
}
int temp = array[minId];
array[minId] = array[count];
array[count] = temp;
}
return array;
}
public static void main(String[] args) {
int[] array = {55, 27, 15, 21, 12};
for (int count = 0; count <= array.length - 1; count++) {
System.out.println(sort(array)[count]);
}
}
}두 개의 중첩 loop 가 있으므로 Time Complexity(시간 복잡도) 는 O(n²) 이다.
- 배열의 element 를 하나씩 선택하는 한 개의 loop 는 O(n)
- 해당 element 를 다른 모든 배열 element 와 비교하는 또 다른 loop 는 O(n)
그러므로 Time Complexity 는 O(n) * O(n) = O(n*n) = O(n²) 이다.
Big-O 간 Complexity 비교
예를 들어 n² 은 n 보다 빠르게 증가하므로 g(n) = n² + 5n + 6 이란 값이 있다고 가정한다면, 이는 Big-O 표현법으로 O(n²) 이 된다.이렇게 된 이유와 절차는 다음과 같다.
- 입력이 무엇이고 n 이 무엇을 나타내는지 알아본다.
- 최대 작업 수를 표현하면 알고리즘은 n 으로 수행된다.
- 최고차 항을 제외한 모든 항을 제거한다.
- 모든 상수 요소를 제거한다.
모든 알고리즘에 대해 가능한 가장 빠른 실행시간은 O(1) 이며 일반적으로 Constant Running Time 이라고 한다.
이 경우 알고리즘은 입력 크기에 관계없이 실행하는 데 항상 동일한 시간이 걸리는데, 이상적이긴 하지만 거의 달성할 수 없다.
실제 알고리즘의 성능은 입력의 크기 또는 각 입력 항목에 필요한 작업의 수인 n 에 따라 달라진다.
표기법 계산 하는 방법의 예시를 들면
다음 코드는 n 이 1 이든 100 이든, 10000 이든 무조건 실행을 상수로 실행하기에 O(1) 이다.
if (n > 15) {
System.out.prinln(n);
}이중 반복문이며 상위의 반복문이 상수로 반복하므로 5n 만큼 실행하지만, 영향을 미치지 않는 상수를 제거해 O(n) 이다.
for (int count = 0; count < 5 count++) {
for (int index = 0; index < n; index++) {
System.out.println(index);
}
}삼중 반복문이며 상위의 반복문이 상수를 반복하므로 5n² 만큼 실행하지만, 영향을 미치지 않는 상수를 제거해 O(n2) 이다.
for (int count = 0; count < 5; count++) {
for (int num = 0; num < n; num++) {
for (int index = 0; index < n; index++) {
System.out.println(index);
}
}
}
Time Complexity 에 따른 성능으로 best 와 worst 를 다음과 같이 분류할 수 있다.
(n 은 입력 크기이고 c 는 양의 상수)
- Logarithmic 알고리즘(대수 알고리즘) - O(log n) : runtime 은 n 에 비례하여 대수적으로 증가
예 : Binary Search(이진 탐색) - Linear 알고리즘(선형 알고리즘) - O(n) : runtime 은 n 에 비례하여 정비례하게 증가
예 : Linear Search(선형 탐색) - Superlinear 알고리즘(초선형 알고리즘) - O(n log n) : runtime 은 n 에 비례하여 증가
예 : Heap Sort(힙 정렬), Merge Sort(병합 정렬) - Polynomial 알고리즘(다항식 알고리즘) - O(n^c) : runtime 은 n 을 기반으로 이전보다 빠르게 증가
Bubble Sort(버블 정렬), Insertion Sort(삽입 정렬), Selection Sort(선택 정렬), Bucket Sort(버킷 정렬) - Exponential 알고리즘(지수 알고리즘) - O(c^n) : runtime 은 n 기반의 다항식 알고리즘보다 훨씬 빠르게 증가
Tower of Hanoi(하노이 탑) - Factorial 알고리즘(팩토리얼 알고리즘) - O(n!) : runtimer 은 가장 빠르게 증가하고, 사용할 수 없을 수도 있음
Runtime 분석의 수학적 예
알고리즘의 성능 순서는 n 이 커짐에 따라 꽤나 큰 차이를 보인다.
| n = 10 일 때 | n = 20 일 때 |
| log(10) = 1 | log(20) = 2.996 |
| 10 = 10 | 20 = 20 |
| 10log(10) = 10 | 20log(20) = 59.9 |
| 10^2 = 100; | 20^2 = 400 |
| 2^10 = 1024 | 2^20 = 1048576 |
| 10! = 3628800 | 20! = 2.432902e+1818 |
초당 100만 연산을 실행하는 컴퓨터에서 알고리즘 실행 시간
(1 sec = 106 μsec = 103 msec)
| Classes | n | Complexity number of operations (10) |
Execution TIme (1 instruction/μsec) |
| constant | O(10 | 1 | 1 μsec |
| logarithmic | O(log n) | 3.32 | 3 μsec |
| linear | O(n) | 10 | 10 μsec |
| O(n log n) | O(n log n) | 33.2 | 33 μsec |
| quadratic | O(n²) | 10^2 | 100 μsec |
| cubic | O(n^3) | 10^3 | 1 msec |
| exponential | O(2^n) | 1024 | 10 msec |
| factorial | O(n!) | 10! | 3.6288 sec |
- 끝 -