※ 引述《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