[알고리즘 기초] 01 알고리즘 정의 및 점근적 표기법

1. 알고리즘 정의

어떤 입력을 어떤 출력으로 변환하는 일련의 잘 정의된 계산과정

• 알고리즘은 원하는 입/출력 관계를 구하기 위한 구체적인 계산과정을 설명
• 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 타당하다(correct)고 함

---

2. 점근적 표기법(Asymptotic Notation)

• 알고리즘의 점근적 효율성 : 입력 크기가 극한으로 증가할 때 어떤 알고리즘의 수행 시간이 어떻게 증가하는지 관심
• 알고리즘의 점근적 수행시간은 자연수들의 집합에 한해서 N={0, 1, 2,...}인 함수들로 정의
• 점근적 표기는 주로 알고리즘의 수행시간을 나타내기 위해 사용

1) $O$-Notation(Big-oh)

• Worst case
• 점근적 상한, $f(n) = O(g(n))$
• 정의 : $O(g(n))$ $=$ {$f(n)$ : 모든 $n \ge n_{0}$에 대해 $0 \le f(n) \le c \cdot g(n)$인 양의 상수 $c$, $n_{0}$가 존재한다}

2) $\Omega$-notation(omega)

• Best case
• 점근적 하한, $f(n) = \Omega (g(n))$
• 정의 : $ \Omega (g(n))$ $=$ {$f(n)$ : 모든 $n \ge n_{0}$에 대해 $0 \le c \cdot g(n) \le f(n)$인 양의 상수 $c$, $n_{0}$가 존재한다}

3) $\Theta$-notation(theta)

• 정의 : $ \Theta(g(n))$ $=$ {$f(n)$ : 모든 $n \ge n_{0}$에 대해 $0 \le c_{1} \cdot g(n) \le f(n) \le c_{2} \cdot g(n) $인 양의 상수 $c_{1}$, $c_{2}$, $n_{0}$가 존재한다}
• 충분히 큰 n에 대해 f(n)이 c1g(n)과 c2g(n)사이에 양의 상수 c1과 c2가 존재하면 f(n)은 집합(g(n))에 속함

 

 

+) Worst case running time에 관심을 가지는 이유?

• 최악의 경우 수행시간이 모든 입력의 수행시간에 대한 상한이 된다
• 최악의 경우가 빈번히 발생할 수 있다.
• 평균적인 경우가 최악의 경우만큼 거의 좋지 못한 상황일 때가 종종 있다.