我是一個演算法的初學者
由於正在看講議上寫的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