[python] 알고리즘 및 자료구조 정리 -1- 시간복잡도

시간 복잡도

시간 및 공간 복잡도는 알고리즘을 실제로 실행하지 않고도 대규모 입력에 대한 성능을 예측하는 데 사용되는 공식적인 도구이다

 

점근적 표기법 해독

Big-O (O): 상한선

코딩 테스트에서 가장 중요한 표기법으로, 최악의 경우 성능을 설명하여 크기 n의 입력에 대해 알고리즘이 이 한계보다 느리게 수행되지 않음을 보장

공식적인 정의는

f(n) = O(g(n))

$n이 무한대로 갈 때의 "성장률"에 초점을 맞추므로, 상수와 낮은 차수의 항은 무시

Big-Omega (Ω): 하한선

최상의 시나리오를 설명하며 성능의 하한을 제공합니다.

Big-Theta (Θ): 엄밀한 경계
최상과 최악의 복잡도가 동일할 때 사용되며, 정확한 평균 사례를 설명합니다.

 

Big-O 계층 구조

O(1) - 상수 시간

복잡도의 정점으로, 입력 크기에 관계없이 알고리즘이 동일한 시간을 소요

배열 인덱스로 요소에 접근하거나 해시 맵에서 키로 값에 접근하는 것(평균적인 경우)이 대표적인 예

O(log n) - 로그 시간

일반적으로 각 단계에서 탐색 공간을 절반으로 줄이는 알고리즘에서 발견

이진 탐색이 대표적인 예

O(n) - 선형 시간

실행 시간이 입력 크기에 따라 선형적으로 증가합니다

컬렉션에 대한 단일 루프가 전형적인 예

O(n log n) - 선형 로그 시간

병합 정렬이나 힙 정렬과 같은 비교 기반 정렬 알고리즘의 표준입니다

이는 종종 분할 정복 알고리즘에서 발생

O(n²) - 이차 시간

일반적으로 동일한 컬렉션에 대한 중첩 루프를 포함합니다

종종 최적화가 필요한 무차별 대입 접근 방식

O(2ⁿ) - 지수 시간

모든 부분 집합 생성과 같이 문제의 모든 가능한 조합을 해결하는 재귀적 솔루션에서 종종 발생

 

복잡도 분석의 실제

알고리즘의 성능을 예측하는 과정은 다음과 같은 논리적 흐름을 가지고 있음

먼저, 코딩 테스트 문제에는 보통 1초의 시간 제한이 주어지며, 이는 대략 1억 번의 연산을 처리할 수 있는 시간

주어진 입력의 최대 크기(예: N=1,000,000)에 대해 코드가 이 제한을 통과할 수 있는지 예측해야 함

Big-O 표기법은 이러한 예측을 위한 수학적 공식을 제공

N=1,000,000일 때 O(N^2) 알고리즘은 약 10^{12}번의 연산을 수행해야 하므로 시간 초과가 발생

반면, O(N log N) 알고리즘은 약 2 * 10^7번의 연산을 수행하므로 허용 가능한 범위 내에 있음

따라서 Big-O는 알고리즘의 초기 유효성을 검증하는 핵심 도구

 

그러나 두 개의 O(N) 알고리즘이 실제 실행 속도에서 큰 차이를 보일 수 있음

sys.stdin.readline()과 같은 실용적인 최적화로 결과가 달라질 수 있음

이러한 최적화는 Big-O 복잡도를 변경하지 않지만, 상수 시간을 줄여 실제 실행 시간을 단축시킴