Running Time은 어떻게 측정되는지?

• 알고리즘은 입력을 받아들여 출력으로 변환함.
• 입력의 수에 따라 수행시간은 증가!
• 평균 수행 시간은 측정하기 매우 어려움.

→ 따라서 worst-case 실행시간을 알고리즘 수행시간으로 간주함.

Expeirmental analysis

• 수많은 종류의 input에 대해 알고리즘을 실행 후 수행시간을 기록하고 분석
  • clock(), timeGetTime(),QueryPerfomanceCounter() 이용
• 알고리즘을 실제로 구현해야하고, 컴퓨팅 환경에 따라 다른 결과를 가져오므로 정확한 비교가 어려운 문제점이 존재...

Theoretical analysis

• 알고리즘 자체를 가지고 수학적 분석을 함.
• 기본 연산의 수행횟수를 셈(count, 기본적 명령들의 복잡도는 같다고 가정)
• Counting 방법
  • 구현된 코드에 기본 연산량을 count하는 코드를 삽입하고 실행함.
    • 실제 구현을 해야하는 단점
  • line별 반복횟수 이용.
    • 실제 구현없이 pseudo-code를 이용해 분석 가능
    • Asymptotic Analysis 에 유용함.

Pseudo Code (의사 코드)

• Pseudo(가짜의) 코드 , 알고리즘이 수행될 내용을 인간의 언어로 간략히 설명해 놓은 것을 말한다.

  

• 영어보다는 더 구조적 / C++보다는 덜 자세하다.