Analysis of the Algorithm 2

Proof (증명법

  1. Counterexample - 반례

  2. Contraposition - 대우

  3. Contradiction - 모순, 귀류: 결론을 부정하고 모순임을 보임

  4. Mathematical Induction - 수학적 귀납법

   : i가 초기값에 대해 참, i가 k에 대해 참이라고 가정할 때 k+1일 때도 참임을 증명

 

Analyzing Algorithms and Problems

 - Correctness 증명하기

  1. if the precondition(input data) are satisfied,   ex) 정수정렬문제면 인풋이 정수인지

  2. then the postcondition(output data) will be true,

  3. whe the algorithm terminates

 

Amount of work done

  - 주로 input 사이즈에 의존하여 일의 양을 측정한다.

  - 수행된 operation의 총 수는 basic operation의 수에 근사하게 비례하도록.

  - input의 특성을 확인하는 것은 알고리즘의 behavior에 영향을 줌   ex) 정렬된 input