알고리즘 복잡도 분석

알고리즘 복잡 분석은 코드를 직접 구현하지 않고도 모든 입력을 고려하는 방법이다. 실행 하드웨어나 소프트웨어 환경과는 관계 없이 알고리즘의 효율성을 평가할 수 있다.

시간 복잡도 함수

알고리즘의 수행 시간 분석을 시간 복잡도(time complexity) 라고 한다.

연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n) 이라고 표기한다.

시간 복잡도 함수에서는 차수가 가장 큰 항만을 고려하면 충분하다.

T(n) = n^2 + n + 1

여기서 n = 1000 일 때 T(n) 의 값은 1,001,001이고 이중에서 첫 번째 항이 전체의 약 99.9%를 차지한다.

따라서 입력 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도함을 알 수 있다.

따라서 시간 복잡도 함수에서 중요한 것은 n이 증가하였을 때에, 연산의 총횟수가 n에 비례하여 증가하는지, 아니면 n^2의 비례하여 증가하는지, 아니면 다른 증가추세를 가지는지가 더 중요하다.

빅오 표기법

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다.

빅오 표기법은 n의 값에 따른 함수의 상한값을 나타내는 방법이다.

다음은 빅오 표기법에 의한 알고리즘의 수행시간을 비교한 것이다.

O(1) < O(log n) < O(n) < O( n * log n) < O(n^2) < O(2^n) < O(n!)

여기서 알고리즘이 지수형이나 팩토링얼형의 시간복잡도를 가진다면 사실상 사용할 수 없는 알고리즘이다.
그 이유는 입력의 개수가 30을 넘으면 현재의 가장 강력한 super computer를 동작시켜도 우주가 탄생되어 지금까지 흘러온 시간보다 더 많은 수행 시간을 요구 하기 때문이다.

그 외 시간복잡도 표기법

Big-Ω(빅 오메가) 표기법 : 알고리즘 최상의 실행 시간을 표기한다.
Big-θ(빅 세타) 표기법 : 알고리즘 평균 실행 시간을 표기한다.