0. Prologue

효율적인 알고리즘에 대해 알아보자.

0.1. Books and algorithms

과학기술적 혁신의 많은 부분은 알고리즘에서 왔다.

0.2. Enter Fibonacci

피보나치 수열을 구하는 여러 방법을 알아보자.

An exponential algorithm

가장 단순한 법은 다음과 같다.

function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)

이는 지수 시간이 걸린다.

A polynomial algorithm

더 좋은 방법을 알아보자.

function fib2(n)
if n = 0: return 0
create an array f[0..n]
f[0] = 0, f[1] = 1
for i = 2...n:
    f[i] = f[i - 1] + f[i - 2]
return f[n]

수행 시간은 얼마일까?

More careful analysis

fib2의 수행 시간은 O(n^{2})이다.

0.3. Big-O notation

f(n), g(n)이 양의 정수에서 양의 실수로 가는 함수들이라 하자. 어떤 c > 0이 있어서 f(n) ≤ c g(n)이면 f = O(g)라 한다. g = O(f)라면 f = Ω(g)라 한다. f = O(g), g = O(f)이면 f = Θ(g)라 한다.