Introduction to Algorithms

Algorithm

• Sequence of instructions to solve a computational problem
• 문제 해결을 위한 계산을 수행하는 과정

알고리즘은 문제 풀이에 필요한 계산절차나 논리적인 처리과정을 의미한다. 쉽게 생각해서 음식의 레시피라고 생각하면 된다.

Characteristics of an Algorithm

몇가지 중요한 특징들이 있다.

• Correcteness
• Effectiveness
  • Time & Space complexities
• Definiteness
• Finitness
• Algorithm Independence
• Optimality
• Simplicity
  
  

Analyzing Algorithms

알고리즘을 분석하기 위해 다음의 요소들을 확인한다.

• Correcteness
• Effectiveness
• Optimality
  
  

Correctness

알고리즘이 참임을 증명하기 위해 사용되는 것은 "Loop Invariant"이다. Loop Invariant란 반복되는 과정에서 변하지 않는 것을 의미한다. 이 성질을 이용해 알고리즘의 correctness를 증명할 수 있다. 쉽게 말하면 귀납법이다.

개념만 보면 이해가 어려우니 간단한 예제를 통해 correctness를 증명해본다. Algorithm은 다음과 같다. 다음의 알고리즘을 증명해보자.

Problem : set A에서 largest number 찾기
Algorithm(A[1...n])
1.    i=1
2.    ln = A[i]
3.    while i < n do
4.        i = i + 1
5.        if A[i] > ln, then ln = A[i]
6.    end while
7.    return ln

증명과정은 3단계를 통해 이루어진다.
0. Loop Invariant 설정
1. Initialization
2. Maintenance
3. Termination

Loop Invariant

• k가 1에서 n까지 변하는 동안, i=k이고 ln은 A[1...k] 중에서 가장 큰 숫자이다.

알고리즘이 돌아가면서 위 내용은 항상 만족해야 한다.

Initialization

1. k=1, 즉 i=1인 경우 ln=A[1]으로 loop invariant를 만족한다.

Maintenance

1. Loop invariant가 참이라 가정했을 때, k=t-1 시점에서 ln은 A[1...t-1] 중 가장 큰 값이다.
2. k=t 시점에서 A[t] > ln의 비교를 통해 만약 ln이 더 작은 값이라면 ln을 A[t]로 교체한다.
3. 이 경우, ln이 가장 큰 값이었으므로 A[t]가 A[1...t]에서 가장 큰 값이 되고, ln=A[t]이므로 ln은 다시 가장 큰 값이 된다.
4. Loop invariant가 성립한다.

Termination

1. k=n인 경우에서도 loop invariant는 성립한다.
2. 따라서 주어진 알고리즘의 correctness는 성립한다.