X的期望值 西-尼2=之 =1j=i+1 m-1 = ∑ Pr is compared toj} i=1i三i+1 n-1 n -∑ 2 i=1=+ ,j-i+1 = Proris first pivot chosen from E[X]= 2 2 Pr{亿，is first pivot chosen from} +Pr is first pivot chosen fromZ =1f=i+ j-i+1 1 2 令k=j-i 十 j-i+1'j-i+1 i=1k=1 2 j-i+1 < 一1 o(gn) O(nlogn)；还能改进吗？ i=1 O(nlg n).X 的期望值 令k=j-i O(nlogn)； 还能改进吗？