[알고리즘 기초] 알고리즘의 시간 복잡도 계산법

1) O(1)

 입력 데이터의 양에 상관 없이 항상 일정한 실행 시간을 갖는 알고리즘

 

2) Olog2N 

 실행 시간은 입력 데이터의 수 (N)에 대하여 log2N으로 비례한다. 보통, 효율이 좋은 검색 알고리즘이 이와 같다. 

 

3) O(N) 

 입력 데이터의 수와 시간 복잡도가 비례.

 

4) O(NlogN)

 

5) O(N^2) 이중 포문 도는 경우

 

6) O(N^3) 삼중 포문

 

7) O(2^n) 데이터 증가에 따라 2^n승 만큼 시간이 늘어남 

 

* 거의 대부분의 경우에 반복의 중첩 수가 알고리즘 복잡도를 결정함