1. 빅 O란?
입력 크기 n이 커질 때 알고리즘의 실행 시간 또는 추가 메모리 사용량이 얼마나 빠르게 증가하는지 나타내는 점근적 상한입니다. 보통 최악의 경우 시간 복잡도를 분석하지만, 빅 O 자체가 최악의 경우를 뜻하지는 않습니다.
상수 배수와 낮은 차수 항을 생략합니다. 예: 3n² + 5n + 7 = O(n²). 시간 복잡도와 공간 복잡도는 구분해야 합니다. 아래 코드는 파이썬의 실제 연산 비용을 고려해 설명합니다.
2. 대표 복잡도 비교
| 복잡도 | 대표 알고리즘 | n=10일 때 성장 함수값 |
|---|
성장률 비교 (개념 그래프)
그래프는 함수값의 상대적 증가를 보여 주는 개념도이며 실제 실행 시간을 측정한 결과가 아닙니다. 값이 급격히 증가하는 함수는 세로축 상단에서 잘라 표시합니다.
3. 분석할 때 주의할 점
연속된 반복문은 보통 횟수를 더하고, 중첩 반복문은 곱합니다. 단, 범위가 서로 의존하면 실제 반복 횟수를 합산해야 합니다. 재귀 함수는 호출 횟수와 각 호출의 작업량을 함께 따집니다.
부분집합과 순열처럼 결과를 모두 출력하는 프로그램은 출력 자체의 비용도 있습니다. 위 예제의 O(2ⁿ), O(n!)는 대표적인 결과 개수에 따른 분류이며, 리스트 복사·출력 문자열 길이까지 고려한 엄밀한 시간 상한은 더 커질 수 있습니다.