내가 공부하기 위한 공간 - [알고리즘] 2 - 차수표기법

[분석]

최악 경우 분석 : 수행시간이 최대

평균 경우 분석 : 입력의 확률 분포를 가정하여 분석(대부분 균등 분포)

최선 경우 분석 : 수행시간이 최소(최적 알고리즘 참고로 사용)

 

 

[수행시간 계산법]

 

sum←0;

for i ← 1 to n do

sum ←sum + n;

 

대입연산 횟수 : n+1

덧셈연산 횟수 : n

합 : 2n+1

 

 

sum ← 0;

for I ←1 to n do

for ←1 to n do

sum ← sum + 1;

 

대입연산 횟수 : n*n + 1

덧셈연산 횟수 : n*n

합 : 2n^2+1

 

 

[차수 표기법]

빅오 : 점근적 상한

오메가 : 점근적 하한

세타 : 동시

 

<빅오>

상수 c를 곱한 n에 대한 함수가 n이 증가함에 따라 f(n)이 g(n)보다 커질 수 없을 때

f(n)=O(g(n))

예) 4logn - 9=O(logn)

 

<오메가>

상수 c를 곱한 n에 대한 함수가 n이 증가함에 따라 g(n)이 f(n)보다 커질 수 없을 때

f(n)=Ω(g(n))

예) 3n^3 + 5n - 7n + 16=Ω(n^3)

 

<세타>

모든 n에 대해 상한과 하한을 동시에 만족

f(n)=θ(g(n))

예) 2n^2 8n + 3=θ(n^2)