알고리즘 시간복잡도

시간복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준

기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것

 

알고리즘의 수행시간을 지배하는것은 반복문

 

 

선형 시간 알고리즘

시간복잡도가 N으로 실행되는 알고리즘

 

선형이하 시간 알고리즘

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

이진 탐색

 

지수 시간 알고리즘

다하시간 알고리즘

N보다 더 오래걸리는 알고리즘

 

 

대문자 O 표기법 (Big-O Notation)

O표기법은 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법

만약에 3*5*N 이라고 되있으면 3과 5를 때어낸 N 즉 O(N)이라고 쓴다.

항상 같은 시간이 걸린다면 (즉 50번만 하면 답이 나오는 문제) O(1)이라고 쓰고 상수 시간 알고리즘 이라고 부른다.

 

시간복잡도를 항상 반복문으로 결정하지는 않는다. 가끔 더 정확한 시간복잡도가 필요한데

분할 상환 분석을 사용하면 된다. 하지만 코테만 볼거면 공부할 필요는 없는듯...