[Algo] 5.1 The hiring problem

hiring problem
假設你是老闆，而且現在有 n 個應徵者要來應徵工作，你的策略是永遠只錄取到目前為止最好的應徵者，注意的是：hire 一個應徵者的 cost 比 reject 一個應徵者的 cost 還高，也就是說你的演算法如下：

@{
\proc{Hire-Assistant}(n)
\li best = 0
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;\textup{interview candidate}\;i
\li \;\;\;\;\If \;\textup{candidate}\;i\;\textup{is better than candidate}\;\;best
\li \;\;\;\;\;\;\;\;best = i
\li \;\;\;\;\;\;\;\;\textup{hire candidate}\;i
}@
那我們想知道的是平均我們會花多少 cost 在 hire candidate 上面，
想當然爾，worst case 就是 hire 了 n 次。
因為應徵者是以 uniformly random 的方式前來應徵，
所以這個演算法的 running time 或者說 cost 是 depends on input，
這一類的演算法就是 randomized algorithm。


randomized algorithm: its behavior is determined not only by its input but also by vales produced by a random-number generator