1. Analyzing Algorithms and Problems : Principles and Examples

1-1. Introduction

• 컴퓨터 알고리즘이란?
  : 유한 시간 내에 어떤 문제를 해결하기 위한 단계적인 절차
• 문제 해결의 절차

   1. 문제 정의 (define)
    	input과 output으로 문제를 정의한다
        ex) 3, 7, 20, 11을 정렬하는 문제
        input : 3, 7, 20, 11 (n개의 정수)
        output : 3, 7, 11, 20 (오름차순으로 정렬된 n개의 정수)
   2. 어떻게 문제를 풀 지에 관한 전략 작성
   3. 알고리즘 서술
        input, output, step을 슈도코드를 통해 서술
   4. 분석
        correctness(정확하게 작동하는가)
        time&space (효율성에 대한 분석)
        optimality (최적성에 대한 분석
        if 알고리즘의 복잡도 = 문제의 복잡도이면 Optimal Algorithm)
   5. 구현
   6. 확인, 검증         

• 알고리즘 분석

실험적 분석 vs 이론적 분석

- 실험적 분석의 단점, 한계
    1. 구현이 필수적
    2. 실험에 포함되지 않은 input에 대한 수행 시간을 알 수 없다
    3. 테스트를 할 때 HW, SW 환경이 모두 동일한 상태에서 진행하여야 한다.

- 이론적 분석의 장점
    1. 구현하지 않아도 상위레벨에서 슈도코드를 통해 알고리즘 서술 가능
    2. 수행 시간을 input size n에 대한 function으로 정의 가능
    => 모든 가능한 input에 대한 평가 가능
    3. HW, SW 환경에 구애 받지 않음
    
이 외에도 추가적인 방법으로 평균 수행시간 분석 등이 있다.

이론적 분석 방법 : Primitive operation의 개수를 count 한다.

Basic Operation : 알고리즘이 수행될 때 가장 기본이 되는 Operation
Worst-Case Analysis 
: input 사이즈 n에 대한 알고리즘에서 수행되는 Basic Operation의 최대 개수를 구한다.

1-2. Mathematical Background

Proof 방법의 종류
- Counterexample 반례
- Contraposition 대우
- Contradiction 모순법, 귀류법
  먼저 결론을 부정하고 그것에 대한 모순을 찾는다
- Mathematical Induction 수학적 귀납법
  Base case(n = 1)일 때 참임을 보여주고
  n = k일때 참으로 가정하고 n = k+1일 때도 참임을 증명

1-3. Analyzing Algorithms and Problems

• 알고리즘을 분석하는 이유?
  - 다양한 알고리즘 중에 어떤 알고리즘을 선택할 것인지에 대한 기준을 잡기 위해
  - 알고리즘을 개선하기 위해
  
  

• Correctness 분석
  - precondition이 만족 되었을 때, 알고리즘이 멈춘 후에 postcondition이 참인 경우 Correctness가 만족된 것으로 간주한다.
  - loop invariant ( 루프 불변성)
  loop가 iteration? 마다 알고리즘의 step으로 정의. 수학적 귀납법과 유사한 개념
  
  

• Work 측정법
  - Basic operation : primitive operation 중 알고리즘에서 가장 기본이 되는 연산을 선택한 것
  - work 측정법 : basic operation의 수를 세고 input size n에 대한 함수로 나타낸다 (n에 비례하는 정도로 나타낸다)
  - 알고리즘에 영향을 미치는 input에 대한 우선순위를 확인한다
  
  

• Worst-Case Complexity
  $D_n$

  
  

• Average-case analysis
  $Pr(I)$ : input $I$가 일어날 확률
  $A(n) = \sum_{I\in D_n} Pr(I)t(I)$

int seqSearch(int[] E, int n, int K)
    int ans, index;
    ans = -1; // Assume failure
    for(index = 0; index < n; index++)
    	if(K == E[index])
           ans = index; // Success!
           break; // Done!
    return ans;

• Space Usage (메모리 사용량)
  space 사용량 또한 input에 따라 사용량이 결정되는 경우가 있다.
  만약 int a[n]; 의 경우 O(n) space를 차지하여 n에 비례하여 사용량이 증가한다.
  
  
• Simplicity (간결성)
  1. 알고리즘 Correctness에 대한 증명이 더욱 쉬워진다.
  2. 프로그램 작성, 디버깅, 수정이 더욱 쉬워진다.
  
  
• Optimality
  Optimal Algorithm : the best possible
  개발 되지 않을수도 있지만 모든 알고리즘 중에서 가장 효율적인 알고리즘
  if $W_A(n) = F(n)$

1-4. Classifying Functions by Their Asymptotic Growth Rates

• Asymptotic growth rate, Asymptotic order, order of functions
  : n이 커졌을 때 어떤 증가율을 보이는지

• Classifying Functions
  $O(g)$ : g함수보다 증가율이 같거나 작은 함수들
  $Θ(g)$ : big-oh와 big-omega의 교집합, g함수와 증가율이 같은 함수들
  $Ω(g)$ : g함수보다 증가율이 크거나 같은 함수들

• The sets $O(g), Θ(g), Ω(g)$

• Comparing Asymptotic Growth Rates
  If $\lim_{n \to \infty} \frac{f(n)}{g(n)}$

• Asymptotic Growth Rates
  

• Properties of $O(g), Θ(g), Ω(g)$