알고리즘 (1): 알고리즘 분석과 복잡도

---

알고리즘

특정 문제를 해결하기 위해 기술하는 명령문

알고리즘의 요건

1. 완전성과 명확성

• 수행결과의 순서가 완전하고 명확하게 명세되어야 한다.
• 알고리즘이 지시하는대로 실행하면 의도한 결과가 얻어져야 한다.

2. 입력과 출력

• 입력: 알고리즘이 처리해야 할 대상, 제공되는 데이터
• 출력: 입력 데이터를 처리하여 얻은 결과

3. 유한성

• 단계는 유한해야하며 마지막 단계는 종료여야 한다.

  ADL(Algorithm Description Language)

• 알고리즘 기술을 위해 정의한 언어
• 의사코드(pseudo-code): ADL과 자연어로 기술한 코드
• ADL알고리즘은 ADL변환기를 통해 각 언어의 프로그램으로 변환한다.
• ADL의 명령문의 끝에는 세미콜론(;)을 사용해야 한다.

알고리즘의 평가 기준

공간 복잡도

• 알고리즘을 실행하여 완료하는데 필요한 총 저장 공간
• 가변 공간
  • 런타임 스택을 위한 저장 공간(가변 데이터와 변수들이 필요로 하는 공간)
  • 공간 복잡도에서 가변 공간만을 고려한다.

시간 복잡도

• 알고리즘을 실행시켜 완료하는데 소요되는 시간
• 실행 시간
  • 단위 명령문 하나를 실행하는데 소요되는 시간
  • 시작 복잡도에서 컴파일 시간은 생각하지 않고 실행 시간만을 고려한다.

복잡도 분석

점근적 분석(Asymptotic Analysis)

• 변수의 개수 N이 증가할 때마다 실행시간이 점근적으로 증가한다 는 사실에 의한 분석법
• 알고리즘의 worst-case의 dominant factor가 알고리즘의 시간 복잡도를 결정한다. (실제 실행시간은 c*f(n))
• 대표적인 복잡도 카테고리
  1. $\theta (1)$: constant complexity, 입력 데이터 수에 무관하다.(ex 해쉬)
  2. $\theta (log n)$: logarithmic complexity, 대체적으로 divde & conquer로 이루어짐.(ex 이진검색)
  3. $\theta (n)$: linear complexity, (ex 검색)
  4. $\theta (n^{2})$: quadratic complexity(ex 이중 루프 삽입정렬, 선택정렬)
  5. $\theta (n^{3})$: cubic complexity(ex 삼중 루프, 행렬의 곱셈)
  6. $\theta (2^{n})$: exponential complexity, 시간복잡도가 거의 무한하다고 볼 수 있다.(ex Knapsack problem, Fibonacci, Hanoi)

$\theta (n^3)$ 이상의 시간복잡도를 가진 알고리즘은 좋지 않은 알고리즘이다.

Big O 표기법

• 점근적 상한(Asymptotic Tight Upper Bound)로 시간 복잡도를 파악한다
  • 주어진 복잡도 f(n)에 대해서 g(n) $\in$ O(f(n))이면 g(n)을 f(n)의 Big O라고 한다.
  • $n \geq N$인 모든 정수 n에 대해 $g(n) \leq c \times f(n)$이 성립하는 실수 c>0과 음이 아닌 입력의 크기 N이 존재
• 알고리즘의 시간 복잡도가 O(f(n))이라면 이 알고리즘의 수행시간은 아무리 늦어도 f(n)은 된다는 것을 뜻함(f(n)이 상한)
• 최악의 경우 이정도 시간이면 된다라는 것을 뜻함

Big O 찾기

1. 점화식을 통해 g(n)을 찾는다. $T_n \geq cf(n)$
2. c, N을 임의로 선택한다.
3. n>N임을 증명한다. (cf(n)이 항상 g(n)보다 크거나 같은지 확인한다.)

가급적이면 N=0이 성립하는 c를 찾는 것이 중요하다

Omega 표기법

• 점근적 하한(Asymptotic Tight Lower Bound)로 시간 복잡도를 파악한다.
  • 주어진 복잡도 f(n)에 대해서 g(n) $\in \Omega$(f(n))이면 g(n)을 f(n)의 Omega라고 한다.
  • $n \geq N$인 모든 정수 n에 대해 $g(n) \geq c \times f(n)$이 성립하는 실수 c>0와 음이 아닌 입력의 크기 N이 존재
• 알고리즘의 시간 복잡도가 $\Omega$(f(n))이라면 이 알고리즘의 수행시간은 아무리 빨라도 f(n)밖에 되지 않음을 뜻함(f(n)이 하한)
• 최소한 이정도 시간이 걸린다는 것을 뜻함

모든 정렬 알고리즘은 $\Omega$(N)이다. N개의 데이터를 정렬하는데 N개 데이터를 모두 읽지 않고 정렬 할 수는 없기 때문이다.

Omega 찾기 (모순 유도에 의한 증명)

1. $\Omega$(f(n))을 임의로 가정한다.
2. $n \geq N$인 모든 정수 n에 대해서 c>0, 음이 아닌 정수 N이 존재함을 확인한다.

Big Theta 표기법

• Asymptotic Tight Bound로 시간 복잡도를 파악한다.
  • 주어진 복잡도 f(n)에 대해서 g(n) $\in \Theta$(f(n))이면 g(n)은 f(n)의 차수(Order)라고 한다.
  • $c \times f(n) \geq g(n) \geq d \times f(n)$이 성립하는 실수 c>0과 d>0, 그리고 음이 아닌 입력의 크기 N이 존재
• 알고리즘의 시간 복잡도가 $\Theta$(f(n))이라는 것은 상한과 하한이 마주침으로서 더 이상 좋은 알고리즘이 존재하지 않음을 뜻함

Little-O 표기법

• 여유있는 상한(loose upper bound)를 나타낸다.
• 충분히 큰 n($n->\infty$)에 대해 g(n)이 큰 모든 함수의 집합

Little-$\omega$표기법

• 여유있는 하한(loose lower bound)를 나타낸다.
• 충분히 큰 n($n->\infty$)에 대해 f(n)이 큰 모든 함수의 집합

순환(recursion)

• 정의하려는 개념 자체를 정의 속에 포함
• 종류
  • 직접 순환: 함수가 직접 자신을 호출
  • 간접 순환: 다른 함수를 호출하고 그 함수가 다시 자신을 호출
• 순환 방식의 적용
  • 분할 정복(divide and conquer)의 특성을 가진 문제에 적합
  • 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하는 방법

순환 알고리즘의 시간 복잡도 분석

1. 첫 순환으로부터 점화식을 구한다.
2. 순환이 정지할 때까지의 시간 복잡도를 구한다.
3. 입력의 크기 n에 대한 총 순환 수 i를 구해 점화식을 일반화한다.

마스터 정리(Master Theorem)

• $T_n = aT(\frac{n}{b})+f(n)$, $n^{\log_{b}{a}}=h(n)$에 대해 h(n)과 f(n)의 무게를 비교하여 수행시간을 바로 분석할 수 있음
• 어떤 양의 상수 $\epsilon$에 대하여 $\frac{f(n)}{h(n)}=O(\frac{1}{n^{\epsilon}})$이면 $T(n) = \Theta (h(n))$이다. (h(n)이 수행시간을 결정)
• 어떤 양의 상수 $\epsilon$에 대하여 $\frac{f(n)}{h(n)}= \Omega (n^{\epsilon})$이고 c<1인 모든 상수 c와 모든 n에 대해 $af(\frac{n}{b}) \leq cf(n)$이면 $T(n)=\Theta (f(n))$이다. (f(n)이 수행시간을 결정)
• $\frac{f(n)}{h(n)}= \Theta (1)$이면 $T(n) = \Theta (\frac{f(n)}{log n})$이다. *(f(n)log n이 수행시간이 된다.)
• 단, f(n)과 g(n)이 log를 갖는 경우, log를 무시하여 비교한다.