algorithm - 递归函数的执行次数

Question

我有这个递归算法，T(n) 是执行 P(a, b) 的次数，n := b - a

int foo[] = ... // array of big enough size
function P(int a, int b) 
    if (a+1 < b) {
       int h = floor((a+b)/2)
       if foo[h] >= 0 then P(a, h)
       if foo[h] <= 0 then P(h, b)
    }
end function

我如何计算 T(1)、T(2)、T(3) 和 T(4)

标签： algorithmrecursioncomplexity-theorydivide-and-conquer

Answer 1

由于每次a和b（作为函数的输入）之间的距离减半，时间复​​杂度为Theta(log(b-a))。