[자료구조] 시간복잡도(time complexity)와 공간복잡도(space complexity)

#시간복잡도(time complexity)

: 알고리즘을 프로그램으로 실행하여 완료하기까지 소요되는 시간(속도)

: 컴파일타임과 런타임의 합

 

1) Big-Oh 표기법

"n>=0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n) <= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면, f(n)의 Big-Oh는 O(g(n))이다."

 

• 즉, 시간의 상한선을 표현한다. (worst case)  

• 해당 알고리즘은 Big-Oh보다 오래 걸릴 수 없다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ)

 

 

2) Big-Omega 표기법

"n>=0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n) >= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면, f(n)의 Big-Omega는 Ω(g(n))이다."

 

• 즉, 시간의 하한선을 표현한다. (best case)

• 해당 알고리즘은 Big-Omega보다 빠를 수 없다.

Ω(2ⁿ) < Ω(n³)< Ω(n²) < Ω(nlogn) < Ω(n) < Ω(logn) < Ω(1)

 

 

3) Big-Theta 표기법

"n>=0, f(n)>=0, g(n)>=0에 대해서 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 C₁g(n) <= f(n) <= C₂g(n)을 만족하는 세 개의 상수 C₁, C₂와 K가 존재하면, f(n)의 Big-Theta는 θ(g(n))이다."

 

• 즉, 시간의 평균을 표현한다. (average case)

• Big-Oh와 Big-Omega을 동시에 만족한다. 

---

#공간복잡도(space complexity)

: 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장공간(메모리의 사용량)

: 고정공간과 가변공간의 합