알고리즘 달리기 속도 재기
탐색 글의 선형 탐색과 이진 탐색은 둘 다 옳지만 빠르기가 크게 달랐습니다. “빠르다”는 정확히 무슨 뜻일까요?
직접 돌려 시간을 재면 될까요? 같은 프로그램도 CPU가 빠른지, 데이터가 캐시에 있었는지에 따라 시간이 달라집니다. 잰 시간은 알고리즘만의 성질이 아닙니다.
그래서 시간 대신 연산을 몇 번 하는지 셉니다. 탐색이라면 값을 확인한 횟수입니다. 데이터 개수를 n이라 하면 선형 탐색은 n번, 이진 탐색은 n을 1이 될 때까지 반으로 나누는 횟수인 log₂ n번쯤 확인합니다.
이처럼 입력 크기 n에 따라 연산 횟수를 n의 식 T(n)으로 나타낸 것을 시간 복잡도(time complexity)라 합니다.
그런데 크기가 같아도 입력에 따라 횟수가 다릅니다. 선형 탐색은 찾는 값이 맨 앞에 있으면 1번, 없으면 n번입니다. 그래서 보통 가장 운이 나쁜 최악의 경우를 셉니다. 어떤 입력이 와도 그보다 오래 걸리지 않는다고 장담할 수 있고, 찾는 값이 없는 일처럼 최악은 자주 일어납니다. 최악이 드문 알고리즘은 평균을 따로 말하기도 합니다.
정확한 T(n)은 식이 복잡해지기 쉽습니다. 알고리즘 글의 선택 정렬은 T(n) = ½n² − ½n입니다. 작은 항 ½n과 앞에 곱한 ½을 떼면 어떻게 되는지 살펴봅시다.
n이 커질수록 ½n이 정확한 식에서 차지하는 비율은 0%에 가까워집니다. 앞에 곱한 ½처럼 n과 상관없는 수(상수)는 n이 늘어날 때 횟수가 몇 배로 늘어나는지에 영향을 주지 않습니다. 그래서 가장 빨리 자라는 항 하나만 남기고 상수를 떼어 n이 클 때의 꼴만 적습니다. 이것을 빅오 표기(big-O notation)라 하고 선택 정렬은 O(n²), 선형 탐색은 O(n), 이진 탐색은 O(log n)이라 씁니다.
1초에 연산을 10억 번 한다고 치고 시간을 비교해 봅시다.
n을 10억까지 올려 봅시다.
O(n²)만 수십 년이 걸리고, O(log n)은 10억에서도 약 30번입니다. 배열의 i번째 칸 읽기처럼 n과 상관없이 횟수가 일정하면 O(1)입니다.
컴퓨터를 10배 빠르게 해도 앞에 곱한 상수가 바뀔 뿐이라 O(n²)은 몇 년이 걸립니다.
이번 파트에서는 할 일을 알고리즘으로 적고, 같은 일도 알고리즘과 자료구조에 따라 빠르기가 달라지는 것을 보고, 그 빠르기를 시간 복잡도로 쟀습니다. 하지만 데모 몇 번으로는 알고리즘이 어떤 입력에도 옳은지 장담할 수 없고, 평균을 따지려면 경우를 빠짐없이 세고 확률을 계산해야 합니다. 그래서 다음 파트에서는 증명하고 세고 나누는 수학, 이산수학을 다룹니다. 첫 글은 증명입니다.
다음 코드가 count를 늘리는 횟수를 빅오로 나타내면 무엇일까요? for j in range(i)는 i번 돌고, //는 나눈 몫입니다.
count = 0
i = n
while i >= 1:
for j in range(i):
count += 1
i = i // 2