Analyzing Algorithms and Problem Principles

Problem Solving Using Computers

컴퓨터를 사용해서 문제를 풀기 위해선 다음과 같은 절차를 거친다.

1. Problem (문제)
2. Strategy (문제 해결 전략)
3. Algorithm (알고리즘) : Input (입력값), Output (결과값), Step (단계)
4. Analysis (알고리즘 분석) : Correctness (정확도), 시간 및 공간 복잡도, Optimality (최적성)
5. Implementation (알고리즘 구현)
6. Verification (알고리즘 검증)

 

Proof

어떠한 논리를 증명하기 위한 방법으로 주로 4가지를 사용한다.

1. Counter Example (반례)
2. Contraposition (대우)
3. Contradiction (귀류법)
4. Mathematical Induction (수학적 귀납법)

 

Analyzing Algorithms and Problems

알고리즘과 문제를 분석하기 위해선 세 가지를 고려해야 한다.

1. Correctness (알고리즘의 정확성)
2. 문제를 해결했을때의 시간 및 공간 사용량
3. 최적성 및 단순성 : Worst-Case 복잡도, 평균 복잡도를 활용하여 Optimality를 판단한다.

 

Classifying Functions

알고리즘을 분석하기 위해선 입력값 $n$에 따라 해당 알고리즘이 어떠한 성능을 내는지 분류할 필요가 있다. 이를 점근 표기법이라고 한다.

• $\Omega (g)$ : $f(n) \le c * g(n)$
• $\Theta (g)$ : $\Omega (g) \cap O(g)$
• $O(g)$ : $f(n) \ge c * g(n)$

 

Searching an Ordered Array

예제로 정렬된 배열에서 어떠한 원소를 찾는 문제를 해결해 보자.

 

1. Strategy

• 배열의 가운데 원소인 $K$와 비교한다.
• 한 번의 비교마다 배열의 절반을 제거한다.
• 똑같은 전략을 재귀적으로 적용한다.

 

2. Algorithm : Binary Search

• 입력값 : $E$ (정렬된 배열), $first$ (첫 요소의 인덱스), $last$ (마지막 요소의 인덱스), $K$ (찾아야 하는 값)
• 결과값 : $K$가 $E$에 존재한다면 $index \ (E[index] = K)$, 그렇지 않을 경우 $-1$

int binarySearch(int[] E, int first, int last, int K)
	if(last < first)
		index = -1;
	else
		int mid = (first + last) / 2;
		if(K == E[mid])
			index = mid;
		else if(K < E[mid])
			index = binarySearch(E, first, mid-1, K);
		else
			index = binarySearch(E, mid+1, last, K);

	return index

 

3. Analysis : Binary Search

• Worst-Case 
  • $K$를 찾지 못한 경우 : $A_{fail}(n) = \log{(n + 1)} \in \Theta (\log{n})$
• Average-Case
  • $K$를 찾은 경우 : $A_{succ}(n) = \log{(n + 1)} - 1 + \log{(n + 1)} \ / \ n$
  • 평균값 : $A(n) = (1 - q)A_{fail}(n) + qA_{succ}(n) \approx \log{(n + 1)} - q \ (q : probability \ of \ successful \ search)$
• Binary Search의 Optimality
  • 알고리즘 분류 : Comparision (비교 연산)
  • 문제의 복잡도 (Decision Tree로 증명 가능)
    1. $N \le 1 + 2 + 4 + \ \cdots \ + 2^{p-1} = 2^p - 1$
    2. $p \ge \log{(N + 1)} \ge \log{(n + 1)} \ if \ N \ge n$
    3. $p \ : \ a \ longest \ path \ from \ the \ root \ to \ a \ leaf$
    4. $N \ : \ the \ number \ of \ node \ of \ Decision \ tree, \ n \ : \ the \ number \ of \ input \ data$
  • 결과
    • 문제의 복잡도 : $\log{(n + 1)} \in \Theta (\log{n})$
    • 따라서 Binary Search 알고리즘은 Worst-Case에서 $\log{(n + 1)}$만큼의 비교 연산을 수행하기 때문에 Optimal 알고리즘이다.