Analysis of the Algorithm 3

Worst-Case Complexity

Average Complexity

 - Pr(I): input I가 발생할 확률

 - t(I)는 알고리즘 분석으로 결정할 수 있지만, Pr(I)는 분석적으로 계산 불가능

 

Optimality

  - 알고리즘 복잡도 <= 문제 복잡도

  - 문제의 복잡도를 분석하기 위해서는, 알고리즘을 고른 뒤 basic operation 수를 계산한다.

  - 문제 복잡도: Lower Bound

 

ex) 정렬되지 않은 n개의 숫자 배열에서 가장 큰 수 찾기

• 알고리즘 A: for문 돌려서 끝까지 비교한 다음 최댓값 리턴.
• WA(n)  = n-1
• F(n) 구하기: ‘내가 최댓값인가’가 아니라, ‘내가 (누구보다 작기 때문에) 최댓값이 아니다’의 관점. 그 숫자가 최댓값이 아님을 보이기 위해선 최소 하나의 숫자보다 작아야 한다. 그러려면 최소 한 번의 비교가 필요하다. 따라서 최소 n-1 번의 basic operation이 수행되어야 한다. F(n) = n-1
• WA(n)=F(n)  이므로 알고리즘 A는 optimal.