如何应用2二进制搜索的主定理？

Question

为了计数排序数组中出现的数字，我使用了两次二进制搜索

二元搜索的递推关系是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

Answer 1

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))中。

总之，您在递归公式中犯了一个错误，因为它们不是递归调用。因此，您不应该使用主定理，因为它不能在您的情况下应用(只适用于分析每个Bg和Bd函数中的二进制搜索，具体取决于它们的实现)。