알고리즘 시간복잡도 분석

 

input n에 대하여 가장 높은 차수

 

O(1) 상수 시간 constant time

O(n) 선형 시간 linear time

ex) 반복문, 반복문이 여러개(O(n)에 수렴)

O(n^2) quadratic time 

ex) 반복문이 중첩

O(log n) 로그 시간 log time 

: 입력 크기에 따른 실행 횟수의 변화가 다양한 경우. 

ex) 이진 탐색, for (int i = 1; i <= n; i *= 2) : i = 1, 2, 4, 8, … => \(log_2n\) 

O(n log n) 선형 로그 시간

: 입력 크기의 변수가 여러 개인 경우 : O(n log m) 

ex) O(n) 반복문 + log m 반복문 중첩 => n log m 

 

재귀 함수의 시간 복잡도 분석

쉬운 경우 : 팩토리얼, 합병 정렬(merge sort)
- 팩토리얼: T(n) = T(n - 1) + 1 ∈ O(n)
n, n-1, n-2, ... , 1
- 합병 정렬: T(n) = 2 × T(n/2) + n ∈ \(nlog_2n\) 

어려운 경우 ??

마스터 정리 Master Theorem

: 재귀함수의 시간복잡도를 쉽게 분석할 수 있는 마법의 정리

 

 

 

 

* log 로그는 지수 함수의 역함수. 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다. 

---

참고 : youtube - 주니온TV 아무거나연구소,