210615_시간 복잡도(Time Complexity)

시간 복잡도

효율적인 알고리즘 : 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화

Big-O 표기법

Big-O, Big-Ω, Big-θ 표기법 각각 최악, 최선, 중간(평균)의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기

최악의 경우도 고려하여 대비하는 것이 바람직(Big-O)

O(1)

constant complexity
입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있습

O(n)

linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가

O(log n)

logarithmic complexity
Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도
ex) BST - 매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어듬

O(n2)

quadratic complexity
입력값이 증가함에 따라 시간이 그의 제곱수의 비율로 증가
n^3, n^5 도 모두 Big-O 표기법으로는 O(n2)

O(2n)

exponential complexity
가장 느린 시간 복잡도
재귀로 구현하는 피보나치 수열이 대표적인 O(2n) 시간 복잡도