algorithm - 如何解决这个任务 ()=4(/4)+√n？

Question

我是分而治之的新手。我想知道如何找出这个计算的运行时间？

我究竟需要注意什么以及如何进行？

n=1 运行时间 = O(1)

标签： algorithmdivide-and-conquermaster-theorem

Answer 1

所以让我们看看这个计算：

T(n) = 4T(n/4) + n * sqrt(n)
扩展为总和 k 步它会像
T(n) = 4^k[T(n/4^k)] + n * sqrt( n) * {sqrt(1/4)+sqrt(1/16)....}
这里 {sqrt(1/4)+sqrt(1/16)....} 是几何级数
，如果我们取k= log4(n) //这里的基数是 4
T(n) = n * [T(1)] + n * sqrt(n)*{1-[2/sqrt(n)]}
T(n) = n * [T(1)] + n * sqrt(n) -2 * n

你仍然可以使用

主定理

T(n) = aT(n/b) + f(n)。

如果 f(n) = Θ(n^d)，其中 d ≥ 0，则

T(n) = Θ(n^d) 如果 a < bd,
T(n) = Θ((n^d)log n) 如果 a = bd,
T(n) = Θ(n^(logba)) 如果a > bd

是的 ans 是 O(n^3/2)
{抱歉，由于声誉低，无法发表评论}