알고리즘의 시간 복잡도 분석 - 5. 시간 복잡도

시간 복잡도 (time complexity)

"알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것"

(기본적인 연산 : 더 작게 쪼갤 수 없는 최소 크기의 연산. 사칙연산, 대소 비교, 변수 대입 등)

 

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

 

ex) 수행 시간 비교 A 알고리즘의 수행 시간 : 10240 + 35*logNB 알고리즘의 수행 시간 : 2N^2

 

=> A는 N에 대해 선형 시간, B는 전형적인 다항 알고리즘이다. 입력의 크기가 증가할수록 B의 수행 시간은 매우 큰 값이 된다.

 

점근적 시간 표기 : O 표기

시간 복잡도는 알고리즘의 수행 시간을 표기하는 방법이지만, 계산하기 힘들다는 문제가 있다.=> 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려한다.

 

O 표기법 (Big-O Notation)

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법

 

문제	반복문의 수행 횟수	O 표기
이동 평균 구하기	N	O(N)
이진 탐색	logN	O(logN)
집합 덮개	N*M*2^M	O(N*M*2^M)