알고리즘 복잡도

알고리즘 복잡도 정리

시간 복잡도¶

알고리즘의 실행 속도를 말하며 반복문에 큰 영향을 받는다. 주요 표기법은 아래와 같다.

Big O 표기법(Big O notation)
- \(O(N)\), 알고리즘 최악의 실행 시간을 표기. 가장 일반적으로 사용
오메가 표기법(Big Omega notation)
- \(\Omega(N)\), 알고리즘 최상의 실행 시간을 표기
세타 표기법(Big Theta notation)
- \(\Theta(N)\), 알고리즘 평균 실행 시간을 표기
- 알고리즘의 상/하한 실행 시간에 대한 점근적 접근을 통한 평균 시간 복잡도 도출

아래와 같은 형태의 함수로 알고리즘 실행 시간을 표기하며 \(\lim_{x \to \infty} f(x)\) 인 것을 전제로 계산하기 때문에 의미 없는 상수 및 배수는 표기하지 않는다.

\[f(x) = O(g(x))\]

입력된 \(N\)의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있으며, 속도의 순위는 아래와 같다.

\[O(1) < O(log_2N) < O(N) < O(Nlog_2N) < O(N^2) < O(2^N) < O(n!)\]

알고리즘이 사용하는 메모리 크기를 말한다. 최근에는 컴퓨터의 하드웨어 성능이 매우 강력해짐에 따라 특수한 환경이 아니라면 잘 사용하지 않는다.