[알고리즘] 시간 복잡도

<시간 복잡도>

-       프로그램을 실행시켜 완료하는데 걸리는 시간

-       알고리즘의 일반적인 시간 복잡도는 명령어의 실행 횟수를 고려한다.

n  for 문을 반복한 횟수, 일반 연산을 처리한 횟수 등의 합에서 상수는 제외하고 최고차항만 생각

 

<시간 복잡도의 형태>

 

시간	이름	bit 별 처리 시간
1	상수형	1, 1, 1, 1, 1, 1
log n	로그형	0, 1, 2, 3, 4, 5
n	선형	1, 2, 4, 8, 16, 32
n log n	선형 로그형	0, 2, 8, 24, 64, 160
n^2	평방형	1, 4, 16, 64, 256, 1024
2^n	지수형	2, 4, 16, 256
n!	계승형	1, 2, 24, 40326

 

-       로그형 < 선형 < 선형 로그형 < 평방형 순으로 갈수록 복잡해진다.

 

<시간 복잡도 표현법>

-       빅오[O(N)]: 알고리즘 실행시간의 상한을 나타내는 표기법, 최악의 경우, 가장 많이 사용

-       오메가 표기법[Ω(N)]: 실행시간의 하한을 나타내는 표기법, 최선의 경우

-       세타 표기법[Θ(N)]: 실행시간의 평균을 나타내는 표기법, 평균의 경우

 

<참고>

http://skmagic.tistory.com/164 http://ora-sysdba.tistory.com/entry/Algorithmic http://cafielo.tistory.com/26