시간복잡도 Time Complexity

시간복잡도는
알고리즘 로직을 코드로 구현할 때 
문제를 해결하는 데 걸리는 시간과 입력의 함수 관계이다.



Big-O 표기법
시간복잡도를 표기하는 방법들이다.


1. Big-O (오) - 상한(최악의 경우)
2. Big-Ω (오메가) - 하한(최선의 경우)
3. Big-Θ (세타) - 평균(중간의 경우)

 

 

 

https://www.bigocheatsheet.com/

 

O(1)

constant complexity : 입력값이 증가하더라도 시간이 늘어나지 않는다.  (입력 크기 상관없이 즉시 출력)

 

O(n)

linear complexity : 입력값이 증가함에 따라 시간 또한 같은 비율로 증가 (n앞에 있는 계수는 무시)

 

O(log n)

logarithmic complexity : 빅오 표기법 중 O(1) 다음으로 빠름 Binary Search같이 절반씩 줄어드는 경우

 

O(n^2)

quadratic complexity : 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가

 

O(2^n)

exponential complexity : 빅오 표기법 중 가장 느린 시간복잡도 (ex. 재귀로 구현한 피보나치수열)