Big-O(빅오) 표기법이란?

개요

알고리즘과 관련된 컨텐츠를 접할 때, 아마 Big-O 란 용어를 봤을 것인데, Big-O 표기법은 알고리즘의 비용을 분석하는 기본 도구 중 하나이다.

소프트웨어 개발자가 깊이 있게 이해한다는 것은 굉장히 중요한 일이다.

 

Wikipedia 에서는 Big-O 표기법에 대해서 이렇게 설명한다.

Big-O 표기법은 인수가 특정 값이나 무한대로 향하는 경향이 있을 때, 함수의 제한 동작을 설명하는 수학적 표기법이다.

간단히 말해서, Big-O 표기법은 대수 용어를 사용하여 코드의 복잡성을 설명한다.

 

알고리즘 복잡도 계산 항목

1. 시간 복잡도 : 알고리즘의 실행 속도(주 계산 항목)
2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

알고리즘 시간 복잡도는 반복문이 핵심이고, 최악의 실행 시간을 표기하므로 아무리 최악이라도 이정도의 성능은 보장한다는 뜻이다.

 

Big-O 표기법 적용 예

Big-O 표기법의 이해를 위해 Big-O 의 제곱인 O(n²) 로 예를 들어보겠다.

여기서 문자 "n" 은 입력 크기를 나타내며 "O()" 내부의 함수 "g(n) = n²" 은 입력 크기와 관련하여 알고리즘이 얼마나 복잡한지 알려준다.

 

복잡도가 O(n²) 인 일반적인 알고리즘은 Selection Sort(선택 정렬) 알고리즘이 있겠다.

Selection Sort 알고리즘은 List 의 정렬되지 않은 부분에서 가장 작은(또는 큰) element 를 반복적으로 선택하여 List 의 정렬된 부분으로 이동하는 간단하고 효율적인 알고리즘이다.

1. List 의 정렬되지 않은 부분에서 가장 작은(또는 큰) element 를 반복적으로 선택하고, 정렬되지 않은 부분의 첫 번째 element 와 교체한다.
2. 전체 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²) 이 된다.이렇게 된 이유와 절차는 다음과 같다.

1. 입력이 무엇이고 n 이 무엇을 나타내는지 알아본다.
2. 최대 작업 수를 표현하면 알고리즘은 n 으로 수행된다.
3. 최고차 항을 제외한 모든 항을 제거한다.
4. 모든 상수 요소를 제거한다.

모든 알고리즘에 대해 가능한 가장 빠른 실행시간은 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 를 다음과 같이 분류할 수 있다.

Big-O 성능 비교

(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

 

- 끝 -