Algorithm Analysis
1. Algorithm Efficiency
- A, B 두가지 알고리즘이 있을 때 알고리즘을 선택하는 기준은?
컴퓨터 프로그램 디자인의 목표
1) 알고리즘을 이해하기 쉽게, 코딩하기 쉽게, 디버그하기 쉽게 디자인하는 것
2) 컴퓨터의 resources를 효율적으로 활용할 수 있게 하는 것
2)이 자료구조와 알고리즘 분석의 주요 관심사!
알고리즘 cost를 어떻게 측정할 것인가?
2. Measure Efficiency
2-1. Measuring Efficiency의 정의
: running time depends on "size" of the input(n) : T(n)
- we count the number of basic operations
T(n) : n! > 2^n > 2n^2 > 5nlogn > 20n > 10n>...
n의 함수 종류에 따라 증감률(growth rate)이 달라짐!
cf) Stirling's Approximation
$n! ~ \sqrt {2 \pi n}(\frac{n}{e})^n$
2-2. Best, Worst, Average Cases
인풋에 따라 다른 결과의 running time이 걸릴 수 있다.
Best case cost, Worst case cost, Average case cost
Average time : worst case의 경우 예상치 못한 resource를 사용할 수 있음.
Best case : input이 정리된 상태로 들어올 때 최상의 case로 가정하고 time을 산출 할 수 있음
worst case :input에 대해 명확히 알지 못하지만 resource가 제한적일 때, 보수적인 기준을 잡고 알고리즘을 선택해야 함
2-3. Faster Computer or Algorithm
Faster Algorithm이 중요한가 Faster Computer가 중요한가?
Algorithm이 n이거나 nlogn 정도일 때는 빠른 컴퓨터가 더많은 input을 다룰 수 있지만, n!일 때는 별 차이가 없을 수 있다.
n: 1초에 다룰 수 있는 old computer의 input size
n' : 1초에 다룰 수 있는 new computer의 input size
3. Asymptotic Analysis
3-1. Big-oh
O(f(n)) = T(n) <= cf(n)가 모든 n>n0 범위에서 성립하는 경우
ex) T(n) = 5n -> O(n)
T(n) = 4n^2 + 3n + 7 -> O(n^2)
...
각 시간의 upper bound(T(n)보다 큰 범위에서의 최솟값)
O(n)이 O(n^2) or O(n!)보다 모든 n에서 항상 빠른 것은 절대 아님!
(5n + 7), (n^2 + 3), (n!) n은 1일 때 제일 왼쪽이 제일 느리다.
Big-oh에서는 n을 infinite로 생각
3-2. Big-omega
Ω(g(n)) = T(n) >= cg(n)가 모든 n>n0 범위에서 성립하는 경우
lower bound!
3-3. Big-theta
Θ(h(n)) = O(h(n))과 Ω(h(n))을 동시에 만족하는 경우 표시!
3-4. Simplifying Rules
(1) f(n)이 O(g(n)), g(n)이 O(h(n))이면, f(n)은 O(h(n))이다.
(2)f(n)이 O(k * g(n)), k > 0이면, f(n)은 O(g(n))이다.
(3)f1(n)이 O(g1(n)), f2(n)이 O(g2(n))이면, (f1+f2)(n)은 O(max(g1(n), g2(n)))이다.(theta와 omega도 마찬가지로 max를 사용한다.)
(4)f1(n)이 O(g1(n)), f2(n)이 O(g2(n))이면, f1(n) * f2(n)은 O((g1(n)* g2(n))이다
ex) Binary Search
worst case 때 Θ(logn)의 시간 복잡도를 가진다.
Asymptotic Analysis도 n이 클 때 의미가 있음. n이 작으면 theta notation과 반대로 시간이 소요될 수 있음.
4. Problem & Algorithm, Program
Problem : 수행되어야 하는 task
input과 output의 형태로 주어진다.
input이 동일하면 output도 동일함(randomized algorithm 제외)
Algorithm : 문제를 푸는 방법이나 과정
하나의 문제는 여러개의 algorithm을 가질 수 있다.
5. Space/Time Tradeoff Principle
특정 경우 시간을 빠르게 하기 위해 메모리 공간을 희생해야하는 경우가 있을 수 있음.
ex) factorial의 경우 결과값을 저장하고 있다가 바로 알려주면 됨
swap : tmp 없이 구현 가능.
a += b;
b = a - b;
a -= b;
근데 시간이 오래 걸림
disk storage를 작게 만들면 program이 쓸 수 있는 메모리가 많아져서 프로그램 수행 시간이 빨라진다.
multiple parameter: 한 알고리즘에 두 개 이상의 parameter가 쓰일 수도 있다.
공간 복잡도도 asymptotic하게 표현 가능하다.