점근적 분석(Asymptotic Analysis)

1절. 점근적 분석

배경

입력 크기	효율성
작음	중요 X
큼	중요

점근적 분석

• 입력 크기가 큰 경우 분석
• $\displaystyle \lim_{ n\to \infty }f(n)$
• $Ο, Ω, Θ, ω, O$ 표기법

점근적 표기법 정리

• 주로 빅오($O$)와 세타($\Theta$) 사용

기호	명칭	부등호 비유	의미
$O$	빅오 (Big-O)	$\le$ (이하)	점근적 상한선 아무리 최악이어도 이 시간 이하 소모
$\Omega$	빅오메가 (Big-Omega)	$\ge$ (이상)	점근적 하한선 아무리 최선이어도 최소 이 시간 이상 소모
$\Theta$	세타 (Theta)	$=$ (동급)	정확한 범위 빅오와 빅오메가가 같을 경우 소모
$o$	리틀 오 (little-o)	$<$ (미만)	엄격한 상한선 빅오에서 등호가 빠진 개념으로 확실히 더 빠름
$\omega$	리틀 오메가 (little-omega)	$>$ (초과)	엄격한 하한선 빅오메가에서 등호가 빠진 개념으로 확실히 더 느림

2절. 점근법 표기

$O(g(n))$

• 점근적 증가율이 $g(n)$을 넘지 않는 모든 함수
• 상한이자 최악

예제	공식	표기법
ex 1	$2n^2+100n$	$O(n^2)$
ex 2	$5n$ $log$ $n$	$O(n^2)$
ex 3	$5n^3- 1000n$	$O(n^3)$

수학적 정의

${O(g(n))={f(n)

\exists c > 0, n_0 > 0, s.t.\forall n \geq n_0, f(n) \leq cg(n)}}$

$\Omega(g(n))$

• 점근적 증가율이 적어도 $g(n)$이 되는 모든 함수
• 하한이자 최선

예제	공식	표기법
ex 1	$2n^2+100n$	$Ω(n^2)$
ex 2	$5n$ $log$ $n$	$Ω(n)$
ex 3	$5n^3- 1000n$	$Ω(n^2)$

수학적 정의

${Ω(g(n))={f(n)

\exists c > 0, n_0 > 0, s.t.\forall n \geq n_0, f(n) \geq cg(n)}}$

$\Theta(g(n))$

• 점근적 증가율이 $g(n)$과 일치하는 모든 함수
• 점근적 동치(Asymptotically Tight Bound)
• $\Theta (g(n)) = O(g(n))\cap \Omega (g(n))$

예제	공식	표기법
ex 1	$2n^2+100n$	$\Theta(n^2)$
ex 2	$5n$ $log$ $n$	$\Theta(n log n)$
ex 3	$5n^3- 1000n$	$\Theta(n^3)$

수학적 정의

${\Theta(g(n))={f(n)

\exists c, d > 0, n_0 > 0, s.t.\forall n \geq n_0, cg(n) \leq f(n) \leq dg(n)}}$

점근적 표기 그래프

{ width=”100%” }

빅오(O) 복잡도 차트

{ width=”100%” }

정렬 알고리즘 복잡도

정렬 알고리즘	분류 (제자리 여부)	시간 복잡도	공간 복잡도
퀵 정렬 (Quick Sort)	In-place	최선 : $\Omega(n$ $log$ $(n))$ 평균 : $\Theta(n$ $log$ $(n))$ 최악 : $O(n^2)$	최악 : $O(n)$
병합 정렬 (Merge Sort)	Not In-place	최선 : $\Omega(n$ $log$ $(n))$ 평균 : $\Theta(n$ $log$ $(n))$ 최악 : $O(n$ $log$ $(n))$	최악 : $O(n)$
팀 정렬 (Tim Sort)	Not In-place	최선 : $\Omega(n)$ 평균 : $\Theta(n$ $log$ $(n))$ 최악 : $O(n$ $log$ $(n))$	최악 : $O(n)$
힙 정렬 Heap Sort	In-place	최선 : $\Omega(n$ $log$ $(n))$ 평균 : $\Theta(n$ $log$ $(n))$ 최악 : $O(n$ $log$ $(n))$	최악 : $O(1)$
버블 정렬 (Bubble Sort)	In-place	최선 : $\Omega(n)$ 평균 : $\Theta(n^2)$ 최악 : $O(n^2)$	최악 : $O(1)$
삽입 정렬 (Insertion Sort)	In-place	최선 : $\Omega(n)$ 평균 : $\Theta(n^2)$ 최악 : $O(n^2)$	최악 : $O(1)$
선택 정렬 (Selection Sort)	In-place	최선 : $\Omega(n^2)$ 평균 : $\Theta(n^2)$ 최악 : $O(n^2)$	최악 : $O(1)$
트리 정렬 (Tree Sort)	Not In-place	최선 : $\Omega(n$ $log$ $(n))$ 평균 : $\Theta(n$ $log$ $(n))$ 최악 : $O(n^2)$	최악 : $O(n)$
쉘 정렬 (Shell Sort)	In-place	최선 : $\Omega(n$ $log$ $(n))$ 평균 : $\Theta(n$ $(log$ $(n))^2)$ 최악 : $O(n$ $(log$ $(n))^2)$	최악 : $O(1)$
버킷 정렬 (Bucket Sort)	Not In-place	최선 : $\Omega(n + k)$ 평균 : $\Theta(n + k)$ 최악 : $O(n^2)$	최악 : $O(n)$
기수 정렬 (Radix Sort)	Not In-place	최선 : $\Omega(nk)$ 평균 : $\Theta(nk)$ 최악 : $O(nk)$	최악 : $O(n + k)$
계수 정렬 (Counting Sort)	Not In-place	최선 : $\Omega(n+k)$ 평균 : $\Theta(n+k)$ 최악 : $O(n+k)$	최악 : $O(k)$
큐브 정렬 (Cube Sort)	Not In-place	최선 : $\Omega(n)$ 평균 : $\Theta(n$ $log(n))$ 최악 : $O(n$ $log(n))$	최악 : $O(n)$

점근적 표기 예제

예제	공식	표기법
ex 1	$5n^2$	$O(n^2)$
ex 2	$5n + 3$	$O(n)$
ex 3	$5n^2$	$\Omega(n^2)$
ex 4	$5n^3 + 3$	$\Omega(n^3)$
ex 5	$5n^2$	$\Theta(n^2)$

3절. Summary

시간 복잡도 분석 정리

경우	표기법	설명
Worst Case	$O(g(n))$	비관적인 복잡도
Average Case	$\Theta(g(n))$	이상적인 복잡도
Best Case	$\Omega(g(n))$	낙관적인 복잡도

주의 : $O$, $\Omega$, $\Theta$는 본래 “함수의 점근적 상한·하한·동치”를 뜻하는 표기이지, 그 자체로 최악·최선·평균을 의미하지는 않는다. 위 표는 “최악의 경우 실행 시간의 상한을 $O$로, 최선의 경우 실행 시간의 하한을 $\Omega$로 즐겨 표기한다”는 관례를 정리한 것이다. 예를 들어 최선의 경우 실행 시간도 $O$로 상한을 표기할 수 있다.