[자료구조] 05. 알고리즘의 효율성 (최선, 평균,최악)

알고리즘의 효율성

1. 최선의 경우 (best case) : 수행 시간이 가장 빠른 경우. (운이 좋은 경우)

2. 평균의 경우 (average case) : 수행 시간이 평균적인 경우.

3. 최악의 경우 (worst case) : 수행 시간이 가장 늦은 경우. (운이 나쁜 경우)

 

▶ 예시 : 순차 탐색에서의 최선, 최악, 평균

<순차탐색에서의 최선, 최악의 경우>

  ▷ 최선의 경우 : 찾는 숫자가 맨 앞에 있는 경우. (입력에 무관해지므로, 의미 없는 경우가 많음.)

      → O(1)

 

  ▷ 최악의  경우 : 찾는 숫자가 맨 뒤에 있는 경우. (가장 널리 사용됨. 응용에 따라 중요한 의미를 가짐. 계산하기 쉬움.)

      → O(n)

         (O(10)이 아닌 이유 : 뒤에서부터 찾기 시작해도 제일 마지막에 찾아야 하기 때문이다.)

 

  ▷ 평균적인 경우 : 각 요소들이 균일하게 탐색된다고 가정할 경우.( 계산 시간 많이 걸리거나 불가능할 수 있음.) 

      → O(n)

         (모든 숫자들이 탐색될 가능성 = 1/n 이므로, (n + 1)/2가 된다. 최고차항만 따지면 n이 된다.)

---

참고 서적 : <C언어로 쉽게 풀어쓴 자료구조>