테이프에 노래를 기록한 후에 맨 앞에서부터 원하는 노래를 찾는 평균 비용을 최소화하려면 어떤 순으로 기록해야 할까요? 평균 검색 비용을 최소화하려면 길이가 작은 노래를 먼저 기록합니다. 이를 증명해 봅시다.
n번째 기록한 노래의 길이를 An이라고 한다면 모든 노래를 찾는데 걸리는 비용은 다음과 같습니다.
A1 + (A1 + A2) + (A1 + A2 + A3) + … + (A1+A2+A3+…+An) = nA1 + (n-1)A2 + (n-2)A3 + … +An
i>j>0이고 Ai<Aj 인 부분이 있을 때 평균 검색 비용이 최소라고 가정합시다.
전체 노래 검색 비용은 Sa = nA1 + (n-1)A2 + …+ (n-(j-1))Aj +… +(n-(i-1))Ai +…+An 입니다.
그런데 Ai와 Aj의 순서를 바꾸면 전체 검색 비용은 다음과 같습니다.
Sb = nA1 + (n-1)A2 + … + (n-(j-1))Ai + … + (n-(i-1))Aj+…+An
Sa – Sb = (i-j)Aj + (j-i)Ai = (i-j)(Aj – Ai)<0 이므로 가정은 거짓인 명제입니다.
따라서 i>j>0이고 Ai<Aj인 부분이 없어야 합니다. 이처럼 탐욕 알고리즘을 이용하여 전체 문제의 최적해를 구할 수 있다고 증명할 수 있다면 가치 높은 탐욕 알고리즘이라 할 수 있습니다.
이와 같은 원리로 작은 작업을 먼저 수행하게 하는 스케쥴러를 Shotest Job First 스케쥴러라 부릅니다.