第k小元素(Las Vegas) 随机算法 o在n个数中随机的找一个数A[i=x,然后将其余n-1 个数与x比较,分别放入三个数组中: oS(元素均<x),S2(元素均=x),S3(元素均>x) >若S≥k则调用 Select(,k) 若S<k但(+2)≥k,则第k小元素就是x; >否则有(s<k,调用Select(s,k-s-2)。 16
第k小元素(Las Vegas) ◼ 随机算法 在n个数中随机的找一个数A[i]=x, 然后将其余n-1 个数与x比较，分别放入三个数组中： S1 (元素均 < x), S2 (元素均=x), S3 (元素均 > x) ➢ 若|S1 |≥k 则调用Select(S1 ,k)； ➢ 若|S1 |<k 但(|S1 |+|S2 |)≥k，则第k小元素就是x； ➢ 否则有(|S1 |+|S2 |)< k，调用Select(S3 ,k-|S1 |-|S2 |)。 16
第k小元素(Las Vegas) 定理 o若以等概率方法在n个数中随机取数,则该算法用 到的比较次数的期望值不超过4n o证明: >设C(n)是输入规模为n时,算法比较次数的期望值, 并设取到任一个数的概率相同。假定取到第小的数 >若j>k,则需要调用 Select(s,k) o∵s=j-1(因为x是第j小的数),∴调用 Select(k,S)的比较 次数的期望值为C(j-1) 若j=k,则直接返回第j个元素,无需继续进行比较。 ,3 >若j<k,则需要调用 Select(s,k-)=sl+2) o∵3=n-j,∴本次调用的比较次数的期望值是C(n-j)
第k小元素(Las Vegas) ◼ 定理 若以等概率方法在n个数中随机取数，则该算法用 到的比较次数的期望值不超过4n 证明： ➢ 设C(n)是输入规模为n时，算法比较次数的期望值， 并设取到任一个数的概率相同。假定取到第j小的数 ➢ 若j＞k，则需要调用Select(S1 ,k)。 ∵|S1 |= j-1(因为x是第j小的数)，∴调用Select(k,S1 )的比较 次数的期望值为C(j-1)。 ➢ 若j = k，则直接返回第j个元素，无需继续进行比较。 ➢ 若j＜k，则需要调用Select(S3 ,k-j)(j=|S1 |+|S2 |)。 ∵|S3 | = n-j，∴本次调用的比较次数的期望值是C(n-j)