推 fenglih:嗯，瞭了。感謝你~~ 原來我一直漏忘了n=2^k 04/11 01:33
※ 引述《fenglih (～ 塵埃 ～)》之銘言：
: 我是一個演算法的初學者
: 由於正在看講議上寫的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-1)*(2^k)+1+k(2^k+1))/(2n+1)
= ((k-1)*n+1+k(n+1))/(2n+1)
= (kn-n+1+kn+k)/(2n+1)
= (2kn+k-n+1)/(2n+1)
= k - (n+1)/(2n+1)
≒ k - 1/2
: ≒ k as n is very large ------就是變到這行我看不懂
: = log n
: = O(log n)
: 拜託給點指示吧 Orz
中間計算一下就出來了
--
**** 說:
不要期望一個精神力差不多已經見底的人阿Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.54