정보관리기술사 · 알고리즘 복잡도와 O-Notation

정의

알고리즘 복잡도는 입력 크기 n이 커질 때 시간과 메모리가 얼마나 늘어나는지를 나타낸다.

점근 표기법으로 나타내며, 정확한 초 단위 시간 대신 증가 모양을 본다.

복잡도 분석은 기본 연산 횟수 T(n)을 세고 최고차항만 남기는 것에서 시작한다.

시간과 공간 복잡도

시간 복잡도는 기본 연산 횟수 T(n)으로 나타낸다.

공간 복잡도는 메모리 사용량 S(n)으로 나타내며 보통 보조 공간 기준으로 본다.

정확히 세기 어려우므로 최고차항만 남기는 점근 표기로 단순화한다.

최고차항과 계수 제거

복잡도 분석은 기본 연산 횟수 T(n)을 세운 뒤 최고차항만 남긴다.

T(n)=5n³+3n이면 최고차항은 5n³이고, 계수 5를 제거하면 O(n³)이다.

계수와 낮은 차수항은 n이 커질수록 영향이 작아 버린다.

n=100이면 5n³은 5,000,000이고 3n은 300이라 3n은 무시해도 된다.

O, Ω, Θ 세 가지 표기

점근 표기는 세 가지다. Big-O는 상한, Big-Ω는 하한, Big-Θ는 상한과 하한이 같은 경우다.

Big-O는 최악 경우의 보장에 주로 쓰고, Big-Ω는 최선 경우의 하한에 쓰인다.

Big-Θ는 상한과 하한이 일치할 때만 쓸 수 있어 가장 정확하지만 증명이 어렵다.

표기와 경우는 다른 축이므로 섞지 않고 분리해 쓴다.

차수별 연산 횟수 비교

같은 문제라도 증가율에 따라 연산 횟수 차이가 크게 벌어진다.

n이 10에서 1,000으로 커지면 O(n²)의 연산 수는 100에서 1,000,000이 된다.

실무에서는 O(n log n) 이하인지가 판단의 기준이 된다.

입력이 커질수록 상수 계수보다 점근 차수가 처리 시간을 좌우한다.

계산 예제

n이 10⁶인 데이터에서 두 알고리즘의 연산 횟수를 비교해 보자.

A는 약 10¹² 회, B는 약 1.99×10⁷ 회로 계산된다.

차이는 약 5만 배이며, 10⁶ 이상에서 O(n²)은 실용적이지 않다.

1초에 10⁹회 연산하는 장비라면 A는 약 1,000초, B는 0.02초다.

정리

시간과 공간 복잡도는 입력 크기 n에 대한 점근 증가율로 나타낸다.

표기는 Big-O 상한, Big-Ω 하한, Big-Θ 정확한 경계 세 가지다.

답안에는 정의, 세 표기의 역할, 최고차항 규칙을 함께 쓴다.