빅오 표기법

알고리즘이 얼마나 빠른지 표시하는 방법이다. 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정한다. 이렇게 하면 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지 알 수 있다.

빅오 표기법은 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타낸다. 이 연산 횟수 앞에 커다란(Big) 알파벳을 쓰기 대문에 빅오 표기법이라고 한다. 괄호 안에 있는 건 연산 횟수를 의미한다.

1. 빅오 표기법은 왜 사용할까

원소 하나를 확인하는 데 1밀리초가 걸린다고 가정해 보자. 100개의 원소를 단순 탐색과 이진 탐색을 사용해 걸리는 시간은 다음과 같다.

• 단순 탐색(n): 100밀리초
• 이진 탐색(log2 n): 7밀리초

참고로, 여기서 로그(log)는 거듭제곱의 반대말이다. log 10 100이라는 수는 “10을 몇 번 곱해야 100이 될까?”하고 묻고 있는 것이다. 10*10이니까 답은 2이다. 따라서 log 10 100 = 2가 되는 것이다.

실제로는 리스트에 10억개 이상의 원소가 있을 수도 있다. 10억개의 원소에 대해 이진 탐색을 실행한 결과는 30밀리초이다.

100개의 원소로 실행했을 때 이진 탐색은 7밀리 초가 걸리고, 단순 탐색이 100밀리 초가 걸렸으니까 이진 탐색이 단순 탐색보다 15배 빠르다고. 따라서 단순 탐색을 실행하면 30*15 = 450밀리초가 걸릴 것이라고 생각할 수 있다. 하지만 이건 틀린 생각이다.

10억 개의 원소에 대한 단순 탐색 시간은 10억 밀리 초, 대략 11일이 걸린다. 이진 탐색과 단순 탐색 시간이 같은 비율로 증가하지 않기 떄문이다.

원소의 개수가 증가해도 이진 탐색에 걸리는 시간은 얼마 늘어나지 않는다. 하지만 단순 탐색의 시간은 엄청나게 증가한다. 그러니까 원소의 개수가 커질수록 이진 탐색은 단순 탐색보다 훨씬 빨라지는 것이다. 그래서 알고리즘의 실행 시간이 얼마나 걸리는지만 고려할 것이 아니라, 리스트의 크기가 증가할 때 어떻게 증가하는지 파악할 필요가 있다. 빅오 표기법을 사용하는 이유가 바로 이것 때문이다.

2. 많이 사용하는 빅오 실행 시간의 예

2-1. 예시로 계산하는 실행 시간

16개의 네모 칸이 생기도록 격자(grid)를 그려야 한다고 가정해 보자. 빅오 표기법은 연산 횟수를 나타낸다고 했으니까 네모 칸 하나를 만드는 것을 한 번의 연산이라고 한다. 1초에 10번의 연산을 할 수 있다.

예를 들어 O(log n)의 경우, 4(log 16 = 4)번의 연산이면 되므로 0.4초가 걸린다. 만약 1024개의 네모 칸을 그려야 한다면 10(log 1024 = 10)번의 연산이 필요하므로 1초가 걸린다.

3. 시간 복잡도와 공간 복잡도

3-1. 시간 복잡도 (수행시간)

• big-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타낸다.
• 시간, 메모리를 둘 다 따지는데 시간이 더 중요하다.
• 가장 오래 걸리는 시간이 얼마나 걸리냐? -> 이게 시간 복잡도이다.
• 제일 좋은 시간 복잡도는 O(1)이다.
• 시간 제한을 보고 문제를 꼭 풀도록 하자. (시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 약 1억이 1초 정도이다. 절대적인 건 아니고, 애매할 때는 실제로 구현해봐야 함)
• Big O Notation에서 상수는 버린다.(중요)

3-2. 공간 복잡도 (메모리)

• 공간에 대한 개념으로 알고리즘이 공간을 얼마나 필요로 하는지를 나타낸다.
• 딱히 신경 안 써도 된다. 메모리는 대부분 적게 나오고 메모리 제한은 대부분 넉넉하다.
• 단, 배열을 쓸 때 가끔 신경써줘야 된다.

참고 자료

• 그림으로 개념을 이해하는 알고리즘
• big O cheat sheets