[알고리즘] 알고리즘 효율성 - 최선, 평균, 최악의 경우

최악의 경우(worst case) ★

알고리즘의 수행 시간이 가장 오래 걸리는 경우 => 시간 복잡도의 척도

최선의 경우(best case)

알고리즘의 수행 시간이 가장 적게 걸리는 경우

평균적인 경우(average case)

알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 수행 시간

 

EX) 순차 탐색(sequential search)의 경우

※ 순차탐색 : 찾고자 하는 항목을 배열의 첫 번째부터 마지막까지 비교하면서 찾아내는 탐색방법

 

• 최선의 경우 : 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우 : 비교 횟수가 1번이므로 O(1)

5

9

10

17

21

29

33

37

38

43

• 최악의 경우 : 찾고자 하는 숫자가 배열의 맨 끝에 있는 경우 : 비교 횟수가 n번이므로 O(n)

5

9

10

17

21

29

33

37

38

43

• 평균적인 경우 : 첫 번째 항목부터 n번째 항목까지 차례대로 비교 횟수가 1+2+....n이고 전체 자료의 개수는 n이므로 평균적인 비교 연산의 횟수는 (n+1)/2 즉, O(n)