Big O 표기법과 알고리즘 복잡성 이해하는 방법

빅오 표기법 쉽게 이해하기: 알고리즘 복잡도 가이드

모든 프로그래머는 한 번쯤 이런 경험을 한다. 코드가 테스트 데이터에서는 완벽하게 작동하지만, 실제 데이터셋을 입력하면 멈춰버리는 것이다. 알고리즘이 입력 크기에 따라 어떻게 확장되는지 이해하는 것은 '동작하는 코드'와 '어떤 규모에서도 동작하는 코드'의 차이를 만든다. 핵심적으로 빅오 표기법은 알고리즘의 실행 시간이나 메모리 사용량이 입력 크기가 증가함에 따라 어떻게 증가하는지를 설명하는 수학적 언어이며, 한 번 이해하면 코드를 보는 시각이 완전히 달라진다.

배울 내용

빅오 표기법을 사용해 모든 알고리즘의 효율성을 분석하는 방법, 실제 애플리케이션에서 최악의 경우 성능이 중요한 이유, 그리고 일반적인 복잡도 클래스를 한눈에 인식하는 방법을 배우게 된다. 단 한 번의 테스트도 실행하지 않고 코드가 1,000개 또는 1,000,000개의 항목을 처리할 수 있을지 예측할 수 있게 된다. 이 가이드는 코드를 작성하기 전에 올바른 알고리즘을 선택할 수 있는 사고 프레임워크를 제공하여, 치명적인 성능 문제를 미리 방지할 수 있게 해준다.

작동 원리

알고리즘을 요리법에 비유해보자. 요리법에 "야채를 하나씩 썰어라"라고 되어 있으면, 시간은 야채의 개수에 비례한다. "소금을 넣어라"라고 되어 있으면, 두 사람을 위해 요리하든 200명을 위해 요리하든 시간은 동일하다. 빅오 표기법은 이러한 관계를 수학적으로 표현한다.

핵심 메커니즘

알고리즘 복잡도 분석은 입력 크기(n)가 증가함에 따라 연산 횟수가 어떻게 변하는지에 초점을 맞춘다. 정확한 실행 시간은 하드웨어와 구현 세부 사항에 따라 달라지므로 중요하지 않다. 대신 성장률을 살펴본다. 입력 크기를 두 배로 늘리면 실행 시간도 두 배가 되는가? 그대로인가? 네 배가 되는가?

MIT 컴퓨터 과학 프로그램은 빅오 표기법을 알고리즘의 자원 사용량에 대한 점근적 상한, 즉 알고리즘에 필요한 시간이나 메모리의 '최악의 시나리오'를 설명하는 것으로 정의한다. 공식적으로, 함수 T(n)이 O(f(n))이라는 것은 모든 n ≥ n₀에 대해 T(n) ≤ c·f(n)을 만족하는 상수 c와 n₀가 존재한다는 뜻이다. 쉽게 말해, 특정 입력 크기 이상에서는 알고리즘의 실행 시간이 f(n)의 상수 배를 절대 넘지 않는다는 의미다.

일반적인 복잡도 클래스

각 복잡도 클래스는 서로 다른 성장 패턴을 나타낸다:

• O(1) – 상수 시간: 입력 크기와 관계없이 실행 시간이 일정하다. 배열 요소에 접근하거나 해시 테이블에서 값을 조회하는 것이 대표적인 예시다.

• O(log n) – 로그 시간: 실행 시간이 느리게 증가한다. 입력이 두 배가 되어도 단계가 하나만 추가된다. 이진 탐색이 이에 해당하며, 각 비교마다 탐색 공간이 절반으로 줄어든다.

• O(n) – 선형 시간: 실행 시간이 입력 크기에 비례하여 증가한다. 각 요소를 한 번씩 처리하는 단순한 루프가 선형 시간이다.

  Google AdInline article slot

• O(n log n) – 선형 로그 시간: 병합 정렬, 힙 정렬과 같은 효율적인 정렬 알고리즘이 여기에 속한다. 이차 시간보다는 빠르지만 선형 시간보다는 느리다.

• O(n²) – 이차 시간: 입력이 두 배가 되면 실행 시간이 네 배가 된다. 중첩 루프는 종종 이차 복잡도를 나타내며, 선택 정렬과 버블 정렬에서 볼 수 있다.

• O(2ⁿ) – 지수 시간: 입력 요소가 하나 추가될 때마다 실행 시간이 두 배가 된다. 메모이제이션 없이 재귀적으로 피보나치 수를 계산하는 경우가 이에 해당하며, n이 약 30을 넘으면 실질적으로 사용할 수 없다.

분석 규칙

컴퓨터 과학 교과 과정에 문서화된 대로, 몇 가지 규칙이 복잡도 분석을 단순화한다:

• 단순문(할당, 산술 연산 등)은 O(1)이다.
• 루프: 루프의 실행 시간은 루프 본문의 실행 시간에 반복 횟수를 곱한 값이다.
• 중첩 루프: 각 중첩 수준의 복잡도를 곱한다. 두 개의 중첩 루프는 일반적으로 O(n²)을 생성한다.
• 순차문: 합계가 아닌 최대 복잡도를 취한다.
• If/else문: 최악의 경우 분기를 가정한다.

빅오를 계산할 때는 상수와 낮은 차수의 항을 버린다. 5n + 3 연산은 O(n)이고, n² + n은 O(n²)이다. 큰 입력에서는 지배적인 항만 중요하다.

왜 중요한가

실제 영향

빅오 표기법과 알고리즘 복잡도를 이해하는 것은 단순한 학문적 지식이 아니라 소프트웨어가 실제 환경에서 작동하는지에 직접적인 영향을 미친다. 이미지 처리를 생각해보자. 1메가픽셀 이미지에는 약 100만 개의 픽셀이 있다. 각 픽셀을 처리하는 O(n²) 알고리즘은 연산당 1마이크로초가 걸린다고 가정할 때 완료하는 데 1주일 이상이 걸린다. 3메가픽셀 이미지의 경우 3개월 이상으로 늘어난다.

마찬가지로 125,000개 단어가 있는 사전을 검색하는 경우를 생각해보자. 선형 탐색(O(n))은 일치하는 항목을 찾을 때까지 모든 항목을 검사한다. 이진 탐색(O(log n))은 약 17번의 비교로 단어를 찾는다. 이 차이는 반응성이 좋은 애플리케이션과 멈춰버리는 애플리케이션의 차이를 만든다.

최악의 경우 vs. 평균적인 경우 분석

위스콘신 대학교의 컴퓨터 과학 교과 과정에 따르면, 대부분의 컴퓨터 과학 분석은 최악의 경우 성능에 초점을 맞춘다. 이는 알고리즘이 특정 시간을 초과하지 않음을 보장하기 때문이다. 퀵 정렬과 같은 일부 알고리즘은 평균적인 경우 O(n log n)으로 뛰어나지만 최악의 경우 O(n²)으로 성능이 저하된다. 이러한 트레이드오프를 알면 사용 사례에 적합한 알고리즘을 선택하는 데 도움이 된다.

공간 복잡도

빅오는 시간뿐만 아니라 메모리 사용량도 설명한다. 일부 알고리즘은 더 많은 메모리를 사용하여 시간을 절약하고(해시 테이블은 공간을 희생하여 O(1) 조회를 제공), 다른 알고리즘은 속도를 희생하여 메모리를 최소화한다. 두 가지 차원을 이해하면 정보에 기반한 트레이드오프를 할 수 있다.

수치로 보기

다음 표는 입력 크기가 증가함에 따라 다양한 복잡도 클래스가 어떻게 확장되는지 보여준다. 표준 계산 복잡도 분석에 따르면, 비효율적인 알고리즘의 경우 연산 횟수가 극적으로 증가한다:

입력 크기 (n)	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)
10	1	4	10	33	100	1,024
100	1	7	100	664	10,000	1.27×10³⁰
1,000	1	10	1,000	9,966	1,000,000	(범위 초과)
10,000	1	14	10,000	132,878	100,000,000	(범위 초과)

참고: n=100을 초과하는 O(2ⁿ) 값은 천문학적으로 커서, 지수 알고리즘이 실질적인 작업에 비실용적인 이유를 보여준다.

알고리즘 분석의 주요 이정표

• 1945년: 존 폰 노이만이 최초의 컴퓨터 알고리즘을 기술하여 알고리즘 분석의 기초를 확립했다.
• 1965년: 도널드 커누스가 "The Art of Computer Programming"을 집필하기 시작하여 알고리즘 분석을 체계화했다.
• 1971년: 스티븐 쿡이 P vs. NP 문제를 소개하여 복잡도 클래스를 컴퓨터 과학의 근본적인 질문과 연결했다.
• 현재: 복잡도 분석은 MIT, 스탠퍼드, 케임브리지 등 전 세계 모든 컴퓨터 과학 교과 과정에 포함되어 있다.

일반적인 오해와 사실

오해	사실
"빅오는 내 코드가 얼마나 빠른지 정확히 알려준다."	빅오는 성장률을 설명할 뿐 실제 실행 시간을 알려주지 않는다. 두 개의 O(n) 알고리즘도 상수 요소로 인해 실제로는 수십 배 차이가 날 수 있다.
"O(n)이 항상 O(n²)보다 낫다."	작은 입력에서는 잘 최적화된 O(n²) 알고리즘이 최적화가 덜 된 O(n) 알고리즘보다 더 나은 성능을 낼 수 있다. 복잡도는 대규모 데이터셋으로 확장할 때 중요하다.
"평균적인 경우 성능만 분석하면 된다."	최악의 경우 분석은 보장을 제공한다. 평균적인 경우 성능은 실제로 성립하지 않을 수 있는 입력 분포에 대한 가정에 의존하는 경우가 많다.
"이진 탐색은 O(log n)이므로 모든 탐색이 빠르다."	이진 탐색은 정렬된 데이터가 필요하다. 먼저 정렬해야 한다면 전체 복잡도는 O(n log n)이 된다. O(n²)보다는 낫지만 공짜는 아니다.
"같은 빅오를 가진 알고리즘은 동일하게 효율적이다."	실제로는 상수 요소가 매우 중요하다. 10배 빠르지만 여전히 O(n)인 알고리즘은 느린 형제보다 성능이 뛰어나다.
"복잡도 분석은 학자들만을 위한 것이다."	소프트웨어 충돌에서 수백만 달러의 예산 초과에 이르기까지 실제 재해는 종종 알고리즘 복잡도를 무시한 결과 발생한다.

이 지식을 활용하는 방법

1. 작성하기 전에 분석하라: 알고리즘을 구현하기 전에 복잡도를 추정하라. 성장할 것으로 예상되는 데이터셋에 대해 중첩 루프를 고려하고 있다면 다시 생각하라.

2. 데이터를 알아라: 실제 제약 조건에 따라 알고리즘을 선택하라. 작은 리스트를 정렬한다면 버블 정렬도 괜찮다. 1천만 개의 항목을 정렬한다면 병합 정렬이나 퀵 정렬이 필요하다.

3. 측정하라, 가정하지 마라: 빅오는 설계를 안내하지만, 실제 성능은 상수, 캐싱, 하드웨어에 따라 달라진다. 실제 데이터 크기로 코드를 프로파일링하라.

4. 라이브러리 구현을 사용하라: 표준 라이브러리는 일반적인 연산에 대해 효율적인 알고리즘을 구현한다. 대부분의 언어에서 sort() 함수는 O(n log n) 알고리즘을 사용한다. 바퀴를 다시 발명하지 마라.

5. 복잡도 클래스를 시각적으로 인식하라: n개 항목에 대한 단일 루프는 O(n)을 암시한다. 두 개의 중첩 루프는 O(n²)을 암시한다. 입력을 반복적으로 반으로 나누는 것은 O(log n)을 암시한다. 이러한 패턴을 발견하는 눈을 훈련하라.

6. 공간도 고려하라: 시간만이 유일한 자원이 아니다. 특히 대규모 데이터셋을 처리할 때 메모리 사용량에 주의하라.

자주 묻는 질문

빅오, 빅세타, 빅오메가의 차이는 무엇인가요?

빅오(상한)는 최악의 경우 성장률을 설명한다. 빅오메가(하한)는 최선의 경우 성장률을 설명한다. 빅세타(죄은 경계)는 알고리즘이 정확히 그 비율로 증가한다는 것을 의미하며, 점근적으로 더 빠르지도 느리지도 않다.

왜 빅오에서 상수와 낮은 차수의 항을 버리나요?

상수는 하드웨어와 구현에 따라 달라지며, 기본적인 성장 패턴을 바꾸지 않는다. 충분히 큰 입력에 대해서는 가장 높은 차수의 항이 지배적이다. 상수를 버리면 분석이 더 간단해지고 기계에 독립적이게 된다.

재귀 알고리즘의 빅오는 어떻게 결정하나요?

재귀 알고리즘의 경우, 재귀 호출의 수와 호출당 수행되는 작업을 분석한다. 예를 들어, 재귀적 피보나치는 각 수준에서 두 번의 호출을 하므로 O(2ⁿ)이 된다. 이진 탐색은 입력이 절반으로 줄어들면서 한 번의 호출을 하므로 O(log n)이 된다.

O(n²) 알고리즘이 실용적일 수 있나요?

네, 작은 입력이나 상수가 매우 낮은 경우 가능하다. 고도로 최적화된 O(n²) 정렬이 n < 1000일 때 최적화가 덜 된 O(n log n) 정렬보다 더 나은 성능을 낼 수 있다. 핵심은 문제의 크기를 아는 것이다.

빅오는 실제 시간 측정과 어떤 관련이 있나요?

빅오는 시간이 어떻게 확장되는지 예측할 뿐, 절대적인 시간을 알려주지는 않는다. 실제 시간을 얻으려면 하드웨어에서 벤치마킹해야 한다. 빅오는 n이 두 배가 되면 O(n) 코드는 약 두 배의 시간이 걸리고, O(n²) 코드는 네 배의 시간이 걸린다는 것을 알려준다.

— Editorial Team