시간 복잡도에 대해서

 

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음.

 

 

목차 (눌러서 이동)

 

 

반복문이 지배

반복문은 알고리즘의 수행 시간을 지배한다. 따라서, 수행 시간은 보통 반복문의 수행

횟수로 측정한다.

선형 시간과 선형 이하 시간 알고리즘

선형 시간 알고리즘은 수행 시간이 입력 크기에 비례한다. 즉, 입력된 자료를 최소 한 번은
모두 훑어야 하는 프로그램이다. (e.g. 이동 평균 구하기)

 

선형 이하 시간 알고리즘은 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가한다.

(Logarithmic) (e.g. 이분 검색)

다항 시간과 지수 시간

다항 시간 알고리즘은 반복문 수행 횟수를 입력 크기에 대한  다항식으로 표현할 수 있는

알고리즘이다.

 

지수 시간 알고리즘은 입력이 증가할 때마다 걸리는 시간이 배수로 증가하는 알고리즘이다. 

지수 시간보다 빠르게 푸는 방법을 찾지 못한 문제들이 많다.

 

다항 시간 알고리즘이 있는 문제를 계산적으로 쉬운 문제, 없는 문제를 계산적으로 어려운

문제라고 이야기 한다.

시간 복잡도

가장 널리 사용되는 알고리즘의 수행 시간의 기준이다. 알고리즘이 실행되는 동안 수행하는

기본적인 연산(더 작게 쪼갤 수 없는 최소 크기의 연산으로 사칙연산, 대소 비교, 대입 연산

등이 있다.)의 수를 입력의 크기에 대한 함수로 표현한다.

 

시간 복잡도가 높다는 것은 입력의 크기가 증가할 때 알고리즘 수행 시간이 더 빠르게

증가한다는 의미이다. 입력의 크기가 충분히 작을 때는 시간 복잡도가 높은 알고리즘이

빠르게 동작할 수도 있다. 따라서, 시간 복잡도가 속도의 완전한 기준은 아니다.

점근적 시간 표기 ( Big-O 표기 )

가장 빨리 증가하는 항의 영향력에 대해서만 표기하는 방법으로 대략적인 함수의 상한을

알수있다. 즉, 알고리즘의 최악의 수행 시간을 알아내는 방법은 아니다. 아주 큰 N0와

C(N0, C > 0)를 적절히 선택하면 N0<=N인 모든 N에 대해 |f(N)| <= C * |g(N)|이

참이 되게 할 수 있다.

수행 시간 어림짐작하기

입력의 크기를 시간 복잡도에 대입해 얻은 반복문 수행 횟수에서 1초당 반복문이

1억(10^8)을 넘어가면 시간 초과의 가능성이 있다. 반복문에서 복잡한 연산(실수 연산,

파일 입출력 등)을 많이 할 경우 예상보다 오래 걸릴 수 있다. 이 외에 언어, 컴파일러,

하드웨어 성능에 따라 시간이 차이난다.