随机算法 RANDOMIZED-HIRE-ASSISTANT(n) 1 randomly permute the list of candidates 2 best =0 /candidate 0 is a least-qualified dummy candidate 3 for i 1to n 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 问题7： 这个算法还有“最好坏/平均情况”吗？ 该如何分析这个算法的性能呢？
随机算法
随机算法 RANDOMIZED-HIRE-ASSISTANT(n) 1 randomly permute the list of candidates 2 best =0 /candidate 0 is a least-qualified dummy candidate 3 fori =1to n 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 问题8： 什么叫：RANDOMLY PERMUTE?
随机算法
生成序列的“随机”排列 PERMUTE-BY-SORTING(A) RANDOMIZE-IN-PLACE(A) 1 n =A.length 2letP[l.川be a new array 1 n A.length 3 fori =lton 2fori=1to月 P[i]RANDOM(1.n3) 3 swap Ali]with A[RANDOM(i,n) 5 sort A,using P as sort keys O(nlogn) O() 对两个算法都必须回答同样的问题： 是否得到任意可能的排列的机会是一样的 (uniformly distribution)? 前提是p[门唯一
生成序列的“随机”排列 O(nlogn) O(n) 对两个算法都必须回答同样的问题： 是否得到任意可能的排列的机会是一样的 (uniformly distribution)? 前提是p[i]唯一