d라이브러리

으악! 전국 3대 흉가에 간 견우가 미션을 잘 수행할 수 있을까요? 실행 시간에 대해 미리 알려줬더라면 좋았을 텐데 걱정이에요. 최강도 기절한 마당에 견우 혼자 잘 해낼 수 있을지 지켜보며, 우리는 이참에 실행 시간을 배워봐요.

100개의 수 중 1개를 찾을 때 1부터 차례차례 찾아 나가는 ‘단순탐색법’과 반씩 나눠 답을 찾아가는 ‘이진탐색법’은 모두 탐색 알고리듬입니다. 하지만 효율성에는 큰 차이가 있죠. 

100개의 수 중에 하나를 고르는 문제처럼 단순한 경우에는 알고리듬의 효율성이 금방 드러나지만, 문제가 복잡할수록 어떤 알고리듬이 더 효율적인지 판단하기 쉽지 않습니다. 이럴 때 살펴봐야 하는 것이 알고리듬의 ‘실행 시간’입니다.

알고리듬의 실행 시간이란 그 알고리듬을 수행하는데 걸리는 시간을 뜻합니다. 이는 평소에 쓰는 초, 분 같은 개념과는 다른데, 컴퓨터가 문제를 처리하는데 걸리는 시간을 물리적으로 측정하면 어떤 컴퓨터, 어떤 프로그래밍 언어를 썼는지에 따라 시간이 달라질 수 있기 때문입니다. 따라서 알고리듬에서의 시간은 알고리듬이 문제를 해결하는데 걸리는 연산 횟수를 ‘함수’로 나타냅니다. 

예를 들어 위 상황에서 단순탐색법은 100개의 데이터가 있을 때 최대 100번이 걸리므로 n개의 데이터일 때의 실행 시간은 n, 이진탐색법은 100개의 데이터일 때 최대 7번이 걸리므로 n개일 때는 log₂n이 됩니다. 데이터 크기가 100일 때는 그 차이가 93밖에 되지 않지만 데이터가 10억 개, 100억 개로 늘어나면 인간의 수명보다 차이가 커질 수도 있지요. 그래서 알고리듬의 효율성을 따질 때는 데이터의 크기가 증가할 때 연산 횟수가 어떻게 증가하는지가 중요해요. 이것을 표현하는 방법 중 많이 쓰이는 것이 ‘빅오 표기법’이죠.

빅오 표기법은 대문자 알파벳 O 옆에 알고리듬 연산 횟수를 괄호 안에 넣어 표기하는 방법입니다. 즉 ‘O(연산 횟수)’로 쓰죠. 빅오 표기법을 보면 알고리듬에 걸리는 시간이 어떤 식으로 증가하는지 한눈에 알 수 있어 효율성을 파악할 수 있답니다. 

예를들어 같은 문제를 푸는 데 쓸 수 있는 두 알고리듬의 실행 시간이 O(n²)과 O(n!)이라면 당연히 O(n²)인 알고리듬을 골라야겠죠? 

빅오 표기법은 최악의 경우에 대한 함수입니다. 그러니까 100중에 1이 답일 때 단순탐색으로 1번 만에 답을 찾았다고 실행 시간이 O(1)이 되는 것은 아닙니다. 즉 어떤 알고리듬의 실행 시간은 항상 같으며, 어떤 경우에도 이 시간보다 오래 걸리지는 않는다는 보장이기도 하죠! 

참고자료

아디트야 바르가바 ‘그림으로 개념을 이해하는 알고리즘’, 양성봉 ‘알기 쉬운 알고리즘’