Computational Complexity

알고리즘의 효율성을 표기해주는 표기법
알고리즘의 효율성 : 데이터 개수(n)가 주어졌을 때 기분 연산의 횟수
시간복잡도 : 알고리즘 연산수
공간복잡도 : 계산에 필요한 기억영역의 크기
빅오(Big-O), 빅오메가(Big-Ω), 빅세타(Big-Θ)

Big-O

점근적 상한
최소의 증가율
T(n) = O(f(n)) ← T(n) ≤ c⋅f(n)
(n > k한 모든 n에 대해)

빅오 크기 비교
O(1) < O(log n) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Big-Ω

점근적 하한
최대의 증가율
T(n) = Ω(f(n)) ← T(n) ≥ c⋅f(n)

Big-Θ

상한과 하한이 같은지 아닌지
T(n) = Θ(f(n)) ← c₁⋅ f(n) ≤ T(n) ≤ c₂⋅ f(n)