Big O 표기법
빅오 표기법은 알고리즘의 실행 속도를 나타내는 표기법이다. 알고리즘이 결과를 계산하는데 얼마만큼의 시간이 걸리느냐가 아니라 입력 되는 데이터의 크기가 늘어날 때 알고리즘 실행 속도가 얼마나 증가하는가를 나타내는 표기법이다.
만약에 10개의 요소를 가진 리스트에서 요소들을 하나씩 돌면서 그 값을 확인하는 알고리즘이 있다면 그 알고리즘은 총 10번의 연산을 수행하게 될 것이다. 이 알고리즘으로 n 개의 요소를 가진 리스트의 값을 모두 확인하려면 총 n 번의 연산을 수행해야하고 이를 빅오 표기법으로 나타내면 아래와 같다.
\[ O(n) \]
이 경우 입력받는 리스트가 가지는 요소의 개수가 n 만큼 늘어나면 알고리즘이 답을 내는데 필요한 연산 횟수도 n 만큼 늘어난다는 것을 알 수 있다.
최악의 경우를 나타내는 Big O
빅오 표기법은 알고리즘이 연산을 수행하는 상황 중 최악의 상황에서의 연산 횟수를 표기한다.
예를 들어 아래와 같은 리스트가 있다고 가정해보자.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
이 리스트의 요소들을 하나씩 확인하면서 특정 값을 찾는 알고리즘이 있다고 해보자.
이 알고리즘으로 1을 찾아야 하는 경우 단 한번의 연산으로 답을 찾아낼 수 있을 것이다. 이 경우를 빅오 표기법으로 나타내면 \( O(1) \) 이 될 것이다.
만약 이 알고리즘으로 6을 찾아야 하는 경우는 \( O(6) \) 이 될 것이다.
이 알고리즘이 마주할 수 있는 최악의 상황은 리스트의 가장 마지막에 있는 요소를 찾는 경우일 것이다. 위의 리스트의 경우에는 10을 찾는 경우일 것이고 이를 빅오 표기법으로 나타내면 \( O(10) \) 이 될 것이다.
그렇다면 이 알고리즘으로 100개의 요소가 들어있는 리스트를 탐색한다면 어떻게 될까? 최악의 경우를 나타낸다고 했으므로 \( O(100) \) 이 될 것이다.
결국 이 알고리즘은 적어도 입력받는 리스트가 가지는 요소의 개수 만큼의 연산을 수행해야 모든 경우에서 답을 찾아낼 수 있는 알고리즘인 것이다.
따라서 리스트 내의 요소 개수를 n 이라고 할 때 이 알고리즘의 실행시간은 \( O(n) \)이 된다.
많이 사용하는 Big O의 예
다음은 자주 사용되는 Big O 표기를 속도가 빠른 순서로 정리한 것이다.
- \( O(log\, n) \), 로그 시간 ex) 이진 탐색
- \( O(n) \), 선형 시간 ex) 단순 탐색
- \( O(n * log\, n) \) ex) 퀵 정렬
- \( O(n^{2}) \) ex) 선택 정렬
- \( O(n!) \) ex) 외판원 문제
Reference
- Hello Coding 그림으로 개념을 이해하는 알고리즘, 한빛미디어