為了計算排序陣列中某個數字的出現次數，我使用了兩次二分搜索
二分查找的遞推關系是 T(N/2) 1 通過呼叫它兩次，說它是2T(N/2) 2是否正確？
但是使用主定理我得到的結果是 O(n) 這是錯誤的
def NbOcc(T,v) :
bg=Bg(T,0,len(T)-1,v) // T(N/2) 1
bd=Bd(T,0,len(T)-1,v) // T(N/2) 1
if bg>bd :
return 0
else :
return bd-bg 1
uj5u.com熱心網友回復：
Bg和Bd函式不是函式的遞回呼叫NbOcc。因此，時間復雜性NbOcc的功能是T(n) = TBG(n-1) TBD(n-1) 1使得TBG和TBD是時間復雜性Bg和Bd分別的功能。
現在，如果Bg和Bd函式都是二分查找函式，則它們的時間復雜度為O(log(n))。因此，我們可以說T(n)是在O(log(n))。
總之，您在回圈公式中犯了一個錯誤，因為它們不是遞回呼叫。因此，您不應該使用主定理，因為它不能應用于您的情況（僅適用于分析 eachBg和Bd函式內部的二分搜索，具體取決于它們的實作）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/354371.html
下一篇：通過匹配屬性值對值求和