算法导论思考题[6-2]

MINIMUM(A)
1 min ← A[1]
2 for i ← 2 to length[A]
3 do if min > A[i]
4 then min ← A[i]
5 return min

求第四行的期望值O(lgn)

当i = j时，它可能的位置为<A0, A[0]-A[1],A[1]-A[2],......>A[j-1] 而是>A[j-1]的概率也就是需要执行第四行的概率是1/j

1/2+1/3+..........1/n = O(lgn)