예전에는 "이 코드의 Big-O 표기법이 뭐예요?"라는 질문만 들어도 소름이 돋았습니다. 학교에서 배운 기억은 나지만, 수학(제가 가장 약했던 과목)과 관련된 내용이라 아예 머릿속에서 지워버렸거든요.
하지만 커리어를 쌓아가면서 어느새 저는 이런 상황에 자주 직면하게 되었습니다:
- 성능 차트를 분석할 때
- 느린 쿼리의 원인을 찾을 때
- "트래픽이 늘어나면 이 코드가 버틸 수 있을까요?"라는 질문을 받을 때
드디어 Big-O를 다시 배우기로 마음먹었을 때, 그 개념이 생각보다 단순하다는 사실에 놀랐습니다. 이 글에서 제가 배운 내용을 공유하려고 합니다. 여러분도 면접에서 좋은 결과를 얻는 것은 물론, 성능 좋고 확장 가능한 시스템을 만들 수 있기를 바랍니다.
약속하건대, Big-O는 생각만큼 무섭지 않습니다. 한 번 익히고 나면 프로파일링 도구를 실행하지 않고도 알고리즘의 효율성을 눈으로 쉽게 파악할 수 있게 됩니다!
Big-O 표기법이란?
Big-O 표기법은 "이 알고리즘의 최악의 경우 성능은 어떨까?"라고 묻는 세련된 방식입니다. O(n)이나 O(1) 같은 표현을 본 적이 있을 겁니다. 각각의 의미는 다음과 같습니다:
- O(n) - 입력 크기(n)가 증가함에 따라 최악의 경우 실행 시간이 선형적으로 증가
- O(1) - 입력 크기와 상관없이 최악의 경우 실행 시간이 일정
그리고 이것을 제대로 이해하려면 점근선(asymptote)에 대해 알아야 합니다.
점근선(Asymptotes)이란?
고등학교 대수학 시절로 잠시 돌아가, 교과서에서 극한과 점근선 관련 장을 펴봅시다.
- 극한 분석(Limit analysis): 함수가 특정 값에 가까워질 때 어떻게 변하는지 살펴보는 것
- 점근 분석(Asymptotic analysis): f(x)가 무한대에 가까워질 때 어떻게 되는지 살펴보는 것
예를 들어 함수 f(x) = x² + 4x를 그래프로 그려본다고 합시다.
다음과 같은 분석을 할 수 있습니다:
- 극한 분석: x가 증가하면 f(x)도 무한대로 발산합니다. 따라서 x가 무한대에 가까워질 때 f(x) = x² + 4x의 극한은 무한대라고 말할 수 있습니다.
- 점근 분석: x가 매우 커지면 4x 항은 x² 항에 비해 미미해집니다. 따라서 x가 무한대에 가까워질 때 f(x) = x² + 4x는 사실상 f(x) = x²와 거의 동일해진다고 말할 수 있습니다.
함수의 일부가 어떻게 "미미해지는"지 이해하려면, 원래 함수에 실제 숫자를 대입해 보세요. 예를 들어 x = 1일 때 함수는 1 + 4(즉 5)를 반환합니다. 하지만 x = 2,000일 때는 4,000,000 + 8,000(즉 4,008,000)을 반환합니다. x² 항이 전체 값에 기여하는 비중이 4x보다 훨씬 큰 것이죠.
Big-O 표기법은 입력 크기가 변화함에 따라 알고리즘의 실행 시간이 어떻게 달라지는지 설명하는 방법 중 하나입니다.
알고리즘의 실행 시간은 무엇이 결정할까?
건초 더미에서 바늘을 찾는 데 얼마나 걸리냐고 물으면, 아마 건초가 얼마나 많은지 궁금해할 겁니다. "10개"라고 하면 1~2분 안에 찾을 수 있을 것이라 자신할 테지만, "1,000개"라고 하면 그렇게 반갑지 않겠죠.
여기서 한 가지 정보를 더 알아야 합니다. 건초가 하나 추가될 때마다 검색 시간이 얼마나 더 걸리는지, 그리고 건초의 양이 무한대에 가까워질 때 어떤 일이 벌어지는지 말입니다.
이는 위의 점근 분석 예시와 매우 유사합니다. 확실히 이해하기 위해 하나 더 예시를 들어보겠습니다. 함수 f(x) = 5x² + 100x + 50을 고려하고, 이 함수의 두 부분을 각각 그래프로 그려봅시다.
이전 예시와 마찬가지로, 결국 5x² 항이 100x + 50 항보다 커지므로 후자는 생략하고, f(x) = 5x² + 100x + 50의 실행 시간은 x²에 비례해 증가한다고 말할 수 있습니다.
물론 프로그램을 실행하는 실제 컴퓨터의 속도나 사용된 프로그래밍 언어처럼 실행 시간에 영향을 미치는 다른 요소들도 있다는 점을 언급할 필요가 있습니다.
선형 검색의 Big-O 구하기
선형 검색(linear search) 알고리즘의 Big-O를 분석해 봅시다. 선형 검색은 데이터셋의 처음부터 시작해 목표 요소를 찾을 때까지 순차적으로 탐색합니다.
Ruby 구현은 다음과 같습니다.
def find_number_via_linear_search(array, target)
counter = 0
# 인덱스 0부터 시작해 배열 끝까지 반복
while counter < array.length
if array[counter] == target
# 목표 요소를 찾으면 종료
return "linear search took: #{counter} iterations"
else
counter += 1
end
end
return "#{target} not found"
end
이 메서드는 다음과 같이 실행해 볼 수 있습니다:
# 정수 50개로 이루어진 배열을 만들고
# 흥미롭게 만들기 위해 순서를 섞어봅니다
array = [*1..50].shuffle
find_number_via_linear_search(array, 24)
몇 번 실행해본 결과는 다음과 같습니다:
=> "linear search took: 10 iterations"
=> "linear search took: 11 iterations"
=> "linear search took: 26 iterations"
함수의 Big-O 표기법을 분석할 때 우리는 최악의 경우(즉, 상한 점근 경계)에 주목합니다.
직관적으로 생각해보면, 최소 반복 횟수는 1입니다. 목표 요소가 배열의 0번째 위치에 있을 때 발생합니다. 최대 반복 횟수(즉, 최악의 경우)는 50입니다. 이는 목표 요소가 배열에 없을 때 발생합니다.
배열에 요소가 100개 있다면 최악의 경우 100번 반복됩니다. 200개라면? 200번입니다. 따라서 선형 검색의 Big-O 표기법은 간단히 O(n)이며, n은 요소의 개수입니다.
조금 더 복잡한 예시: 이진 검색!
이번에는 이진 검색(binary search)을 살펴보겠습니다. 사전에 정렬된 배열을 이진 검색하는 방법은 다음과 같습니다:
- 가운데 요소를 확인한다
2.element == target이면 탐색을 종료한다
3.element > target이면 배열의 윗부분을 버린다
4.element < target이면 배열의 아랫부분을 버린다
5. 남은 배열로 1번부터 다시 시작한다
참고: Ruby 사용자라면 이 알고리즘이 이미 구현되어 있는 내장 bsearch 메서드를 활용할 수 있습니다!
예를 들어 사전에서 "pineapple"이라는 단어를 찾는다고 합시다. 사전의 중간 페이지를 펼칩니다. 운 좋게 그 페이지에 "pineapple"이 있다면 끝난 것입니다!
하지만 아마 사전 중간은 아직 "p" 부분이 아니라서 "llama"라는 단어를 찾게 될 겁니다. "L"이 "P"보다 앞에 있으므로 사전의 아랫부분 전체를 버립니다. 그다음 남은 부분으로 같은 과정을 반복합니다.
선형 검색과 마찬가지로 이진 검색의 최선의 경우 실행 시간은 1회 반복입니다. 하지만 최악의 경우는 어떨까요? 요소 16개를 가진 배열 예시가 있습니다. 이진 검색으로 23을 찾고 싶다고 해봅시다:
[2, 3, 15, 18, 22, 23, 24, 50, 65, 66, 88, 90, 92, 95, 100, 200]
첫 단계는 인덱스 7의 숫자, 즉 50을 확인하는 것입니다. 50이 23보다 크므로 오른쪽을 모두 버립니다. 이제 배열은 다음과 같습니다:
[2, 3, 15, 18, 22, 23, 24, 50]
이제 가운데 요소는 18이고, 23보다 작으므로 이번에는 아랫부분을 버립니다.
[22, 23, 24, 50]
그다음:
[22, 23]
마지막으로:
[23]
결국 길이 16짜리 배열에서 목표 숫자를 찾기 위해 배열을 절반으로 나누는 작업을 총 4번 해야 했습니다.
이를 일반화하면, 이진 검색의 최악의 경우는 배열을 절반으로 나눌 수 있는 최대 횟수와 같다고 말할 수 있습니다.
수학에서 로그는 "그 숫자를 얻으려면 이 숫자를 몇 번 곱해야 할까?"라는 질문에 답하는 데 사용됩니다. 문제에 로그를 적용하는 방법은 다음과 같습니다:
따라서 이진 검색의 Big-O, 즉 최악의 경우 실행 시간은 log₂ n이라고 말할 수 있습니다.
마무리
Big-O 표기법은 "이것의 최악의 경우는 어떨까?"라고 묻는 세련된 방식입니다. 컴퓨터 과학을 잠시 접어두고 현실 세계의 예를 들어볼까요? 망가진 수도꼭지 수리 비용이 얼마나 들지 배관공에게 물었다고 합시다. 그는 "음, 2,000달러를 넘지 않을 거라고 보장할 수 있어요"라고 답할 수 있습니다. 이것이 상한이며, 다소 쓸모없는 정보죠.
그렇기 때문에 다른 Big-O 계열 표기법들이 활용되곤 합니다. 예를 들어 빅세타(Big-Theta)는 하한과 상한을 모두 고려합니다. 이 경우 배관공은 "1,000달러보다는 적지만 2,000달러보다는 많지 않을 거예요"라고 답할 것입니다. 이게 훨씬 유용하죠.
읽어주셔서 감사합니다. 이 글이 Big-O 표기법을 조금이라도 덜 어렵게 느끼는 데 도움이 되었기를 바랍니다!