알고리즘에 대한 점근적 분석

🐣 T(n) : 입력 크기 n에 대한 시간을 나타내는 함수로, 시간 복잡도를 나타냄!

🐣 S(n) : 입력 크기 n에 대한 메모리 사용을 나타내는 함수로, 공간 복잡도를 나타냄!

🌟점근적 분석 Asymptotic Analaysis

• 데이터 집합이나 프로그래밍 언어와 관계없이 알고리즘 자체의 효율성을 비교하기 위해 사용되는 분석 방법으로, 증가차수*에 초점이 맞추어져 있음

• * 증가차수 : "△(입력 양 증가 정도) ➡️ 알고리즘 수행 시간" 경향성을 나타내는 지표

• 점근적 실행 시간 Asymptotic Running Time : 입력 양이 증가하는 정도에 따라 변화하는 알고리즘의 수행 시간! 정확한 시간은 아님!

1. 🌟빅오 표기법 Big-O Notation

∀ $n$ ≥ $n_0$에 대해서 조건 $f(n)$ ≤ $cg(n)$ ➡️ $f(n)=복잡도=O(g(n))$ ↔️ f(n)= g(n)의 빅오(Big-O)[f(n): 내가 설정했던 복잡도] (단, $n_0>0, c>0$ ) ( ↔️즉, 입력크기 n이 커질 수록, 이에 대한 복잡도를 나타내는 f(n)함수에 대해서 cg(n)이 상한이 되는 조건!)

↔️ 입력크기 n이 충분히 크면, f(n)의 증가 속도 ≤ cg(n)

• 상한 : 실행 시간이 최악일 경우, 상한 시간과 같거나 빠름

예시)

↔️ 이 경우, 양수 n에 대해서

$f(n)=n^2+n$ , $g(n)=n^2$

와 같이 두 함수 f(n), g(n)이 있을 때, c를 6 으로 선택(가정)해보고, 양수값 n에 대해서

$f(n)$ ≤ $6*g(n)$ 이 되는 경우가 존재하는 지 확인해보자

$n^2+n$ ≤ $6*n^2$ ↔️ 0 ≤$5n^2 -n$

∴ $f(n)=O(g(n))=n^2$

2. 오메가 표기법 Omega Notation

∀ $n$ ≥ $n_0$에 대해서 조건 $f(n)$ ≥ $cg(n)$ ➡️ f(n)= Ω(g(n)) ↔️ f(n)= g(n)의 Ω(Omega)[f(n): 내가 설정했던 복잡도] (단, $n_0>0, c>0$ ) ( ↔️즉, 입력크기 n이 커질 수록, 이에 대한 복잡도를 나타내는 f(n)함수에 대해서 cg(n)이 하한이 되는 조건!)

↔️ 입력크기 n이 충분히 크면, f(n)의 증가 속도 ≥ cg(n)

• 하한 : 실행 시간이 최악일 경우, 하한 시간과 같거나 느림

예시)

f(n) = $n^2+n$ , g(n) =$n^2$, c = 1 로 가정하자

$n^2+n$ ≥ $n^2$

↔️ n ≥ 0 이면 f(n)≥g(n)이 성립!

∴ $f(n)=Ω(g(n))=Ω(n^2)$

3. 세타 표기법 Theta Notation

∀ $n$ ≥ $n_0$에 대해서 조건 $c_1g(n)$ ≤ $f(n)$ ≤ $c_2g(n)$ ➡️ f(n)= Θ(g(n)) ↔️ f(n)= g(n)의 Θ(Theta)[f(n): 내가 설정했던 복잡도] (단, $n_0>0, c_1>0, c_2>0$ ) ( ↔️ g(n) = f(n)에 대해 점근적 근접 한계값* Asymptotically Tight Bound) ↔️ f(n)은 g(n)과 같은 비율로 증가

• * 점근적 근접 한계값 Asymptotically Tight Bound

: 점근적 상한과 점근적 하한의 교집합