作者fenglih (～ 尘埃 ～)
看板CSSE
标题[问题] Binary search
时间Tue Apr 11 01:13:33 2006
我是一个演算法的初学者
由於正在看讲议上写的Binary search的average case看不懂
所以就上来请益(希望不厌其烦帮我回答 Orz)
--------------------------------------------------------
要证明Binary search的average case = O(log n)
证明如下：
where k= log n +1 (取下界的意思)
└ ┘
┌─────────────┐
│Assume n=2^k │
│ k │
│Σ i*2^(i-1) = 2^k(k-1)+1 │
│i=1 │
└─────────────┘
A(n)= 1/(2n+1) *( (k-1)*2^k+1+k(2^k+1) )
≒ k as n is very large ------
就是变到这行我看不懂
= log n
= O(log n)
拜托给点指示吧 Orz
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.163.149.246