递归算法在大O条件下的运行时间

Question

根据大O，以下递归算法的运行时间是多少[假设f1（n）=O（log n）]

function Recurse(A[1..n])
        f1(n)
        m <-- n/3
        t1 <-- Recurse(A[1..m])
        t2 <-- Recurse(A[(m+1)..2m])
        t3 <-- Recurse(A[(2m+1)..3m])
        return (t1+t2+t3)/3
end function

会是O（logn）吗？如果没有，那么准确的结果是什么？

Answer 1

通过使用主定理

T（n）=aT（n/b）+f（n），其中a>=1 b>1

n是问题的大小。a是递归中子问题的数量。n/b是每个子问题的大小。（这里假设所有子问题的大小基本相同。）f（n）是在递归调用之外完成的工作的成本，包括划分问题的成本和合并子问题的解决方案的成本。

T（n）=对数n*（3*n/3）T（n）=nLog（n）

http://en.wikipedia.org/wiki/Master_theorem