절대적 비용이 아닌 성장률
Big O: 비용이 얼마나 빠르게 증가하는지 측정하기
Big O 표기법은 알고리즘의 성장률을 측정합니다 — 절대적 비용이 아닙니다.
Big O가 답하는 질문: 입력 크기 N이 두 배가 되면, 작업도 두 배가 될까? 네 배가 될까? 그대로 유지될까?
'O'는 '크기 순서'를 의미합니다. 괄호 안의 식은 성장 곡선의 모양을 설명합니다.
주요 복잡도 클래스:
- O(1) — 상수: 비용이 증가하지 않습니다. 예: 배열에서 인덱스로 값을 조회하는 것. 배열이 10개의 항목을 가지든 1천만 개를 가지든, 한 번의 조회는 여전히 한 번의 조회입니다.
- O(N) — 선형: 비용은 입력과 함께 증가합니다. 예: 목록의 모든 항목을 한 번씩 읽는 것. 목록을 두 배로 늘리면, 읽기도 두 배가 됩니다.
- O(N²) — 제곱: 비용은 입력의 제곱으로 증가합니다. 예: 모든 항목을 다른 모든 항목과 비교하는 것. N을 두 배로 늘리면 작업은 네 배가 됩니다.
성장 비교 표:
| N | O(1) | O(N) | O(N²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
N=10에서 차이는 작아 보입니다. N=1,000에서 간격은 엄청나게 커집니다.
O(N)과 O(N²) 비교하기
위의 성장 비교 표를 사용하세요.
N=1,000일 때: O(N)은 1,000개의 연산이 필요합니다. O(N²)은 1,000,000개의 연산이 필요합니다.
코드 구조가 복잡도를 어떻게 드러내는가
코드에서 Big O를 식별하는 방법
Big O는 당신의 코드의 모양에 숨어있습니다. 네 가지 패턴이 대부분의 경우를 다룹니다:
N개 항목에 대한 단일 루프: O(N)
# O(N): 리스트를 한 번 통과
for item in list_of_n_items:
process(item)각각 N개 항목에 대한 중첩 루프: O(N²)
# O(N²): 모든 항목이 다른 모든 항목과 쌍을 이룸
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)상수 시간 조회: O(1)
배열 인덱스 액세스, 해시 테이블 조회 — 크기와 무관하게 한 단계.
분할 정복(매 단계마다 문제를 반으로 자르기): O(log N)
이진 검색: 각 확인이 남은 항목을 절반으로 줄입니다.
---
숨겨진 O(N²): 루프 안의 리스트
# 이것은 O(N)처럼 보이지만 실제로는 O(N²)입니다
visited = []
for item in list_of_n_items:
if item not in visited: # 방문한 모든 항목을 스캔: O(N)
visited.append(item) # 전체 루프: O(N²)if item not in visited 줄이 각 반복에서 visited의 모든 요소를 스캔합니다. 리스트 스캔은 O(N)의 비용이 듭니다. N번 실행되는 루프가 각각 O(N)의 작업을 수행합니다: O(N) × O(N) = O(N²).
이 패턴은 1,000개 이상의 오픈 소스 프로젝트에 나타납니다. 해결책은 한 글자입니다: visited = []를 visited = set()으로 바꾸세요. Set 멤버십 테스트는 O(N)이 아닌 O(1)의 비용이 듭니다. 한 번의 변경. 같은 결과. N=1,000일 때 1,000배 더 빠름.
이 코드를 분류하고 수정하기
이 코드를 읽어보세요:
result = []
for name in student_names:
if name not in result:
result.append(name)이론이 실제를 만날 때
현실 속의 Big O
Big O는 단지 이론이 아닙니다. 정확히 같은 작업에서 초 단위로 끝나는 프로그램과 17분이 걸리는 프로그램을 구분합니다.
실제 예: 빌드 시스템의 의존성 순환 감지.
소프트웨어를 설치할 때, 컴퓨터는 의존성 그래프를 해결합니다: 패키지 A는 B가 필요하고, B는 C가 필요하고, 이런 식으로 계속됩니다. 빌드 시스템은 이 그래프에서 순환을 확인합니다.
O(N²) 순환 감지 알고리즘은 N=100개 패키지일 때 잘 작동합니다. N=50,000개 패키지일 때 (실제 프로젝트): 17분이 걸립니다. O(N) 해결책: 10초.
이 정확한 결함은 GHC (Haskell 컴파일러), pip (Python 패키지 관리자), Maven (Java 빌드 시스템), Cargo (Rust 패키지 관리자), & 1,000개 이상의 다른 프로젝트에 존재합니다.
그들의 저자들이 부주의해서가 아닙니다. visited = []는 N이 작을 때 작성되었습니다. 코드가 굳어졌습니다. N이 증가했습니다. 아무도 빌드가 30분이 걸릴 때까지 눈치채지 못했습니다.
Big O는 무슨 일이 일어났는지 이름을 붙일 수 있게 해주는 어휘입니다 — & 그것을 수정합니다.
---
더 깊이 있는 학습을 원하세요? 우리 unhamming 과정은 Big O에 대한 완전한 장, MOAD-0001 (1,000개 이상의 오픈 소스 프로젝트에서 발견된 실제 O(N²) 결함), & 패턴의 이름을 붙이면 어디서나 찾을 수 있는 이유를 포함합니다. 누락된 장: 알고리즘 복잡도를 참조하세요.
빌드 시간 예측하기
빌드 시스템은 O(N²) 순환 감지를 사용합니다.
측정된 빌드 시간:
- N=100개 패키지: 0.01초
- N=1,000개 패키지: 1초
O(N²)의 경우: 시간은 (N_new / N_old)²로 조정됩니다.
O(N)의 경우: 시간은 (N_new / N_old)로 조정됩니다.