Time Complexity

시간복잡도(Time Complexity)

입력값의 변화에 따라 연산 실행시, 연산 횟수와 관련해서 시간이 얼마나 걸리는지를 표현한 것

 

표기법 

• Big-O(빅-오) - 최악의 경우 고려
• Big-Ω(빅-오메가) - 최선의 경우 고려
• Big-θ(빅-세타) - 평균적인 경우  고려

이 중 Big - O 표기법이 가장 자주 사용된다

 

O(1)

constant complexity라고 하며 입력값이 증가해도 시간이 늘어나지 않는다.

 

O(log n)

logarithmic complexity라고 하며 O(1)다음으로 빠른 시간 복잡도를 가진다

Binary Search Tree 구조가 대표적

 

O(n)

linear complexity 라고 하며 입력값이 증가함에 따라 시간도 같은 비율로 증가한다

 

 

O(n^2)

quadratic complexity라고 하며 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다

 

 

O(2^n)

exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다

재귀로 구현하는 피보나치 수열이 대표적이다

 

코딩 테스트에서는 제한된 시간 내에 값을 반환해야 한다.

따라서 입력되는 데이터 값의 크기에따라 필요한 시간 복잡도를 예측해서 그에 맞는 알고리즘으로 코드를 구성해야 한다.