Question

我认为这令人感兴趣,但我不相信我的解决办法。该算法计算了xⁿ

如果我使用主人的话,我的推理就是这样。

T(n) = 2 T(n/2) + f(n)

但是,本案中的(n)是1? 因为n <=4不变。我:

T(n) = Θ(n)

如果我使用替代方法,我就获得这一答案。

T(n) = Θ(n + log(n))

我认为,我做许多事情是错误的。谁能把我引向正确方向?

Answer 1

T(n) = Θ(n +log(n))仅为T(n)=Θ(n)。在使用“ta”时,可以省略较低的定级词(log(n)。

Also, f(n) is O(1) because you are only doing one multiplication (rek(x, n/2) * rek(x, (n + 1)/2)) for each recursion.

Answer 2

复杂程度为0(n)。解释: 你使使用简单周期的工作出现重复。你们没有任何行动,按人数分列的数字* 大于一个集团。因此,复杂性在于使0(n)的混凝土。