시간복잡도

알고리즘의 시간 복잡도

알고리즘의 수행 시간을 지배하는 것은 반복문이다. 입력의 크기가 커질수록 반복문이 알고리즘의 수행 시간을 지배한다. 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현한다.

시간 복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다. 기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산이다.

시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미이다. 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다. 입력의 크기가 작을땐 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다. 시간 복잡도가 낮은 알고리즘은 입력이 커지면 커질수록 더 효율적이다.

입력의 크기 말고도 입력의 종류에 따라서 수행 시간이 달라지는 경우가 있으므로 최악의 수행 시간 혹은 수행 시간의 기대치를 사용한다.

Big-O Notation은 간단하게 말해 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다. 각 경우의 수행 시간을 간단히 나타내는 표기법이지만, 최악의 수행 시간과 관련이 있는 것은 아니다. 퀵 정렬의 경우 최악의 수행 시간은 O-N제곱이다. 그러나 평균 수행 시간을 계산하면 최고차항이 NlogN이고, 퀵 정렬의 평균 시간 복잡도는 최악의 경우와 달리 O(NlogN)이 된다.

시간 복잡도의 분할 상환 분석

문제의 조건에 따라 더 정확한 시간 복잡도를 계산하는 것도 가능한데, 그 예가 분할 상환 분석을 사용하는 것이다. ex) N개의 작은 작업들을 순서대로 할 때, 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 적용할 수 있다. 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다.