X的期望值 钢医三刘-之 i=1j=i+1 = 22 Pr is compared toj i=1j=i+1 -D 2 i=1j=i+1 j-i+1 Proris first pivot chosen from E[X] 另2 Pris first pivot chosen from i=l i=it j-i+1 +Pr is first pivot chosen fromZ 1 -1 2 令kji 十 j-i+1'j-i+1 t=1k=1 2 j-i+1 -1 ougm O(nlogn):还能改进吗？ =1 O(nlgn).X 的期望值 令k=j-i O(nlogn)； 还能改进吗？