master-theorem - 很难计算出这个递归函数的时间复杂度

Question

我认为这很有趣，但我不确定我的解决方案。该算法计算 x ⁿ

如果我使用主定理，我的推理是这样的

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

但是在这种情况下 f(n) 是 1？因为 n <= 4 是常数。给我：

T(n) = Θ(n)

如果我使用替代，我会得到这个答案

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

我觉得我做错了很多事情。有人可以指出我正确的方向吗？

Answer 1

T(n) = Θ(n + log(n)) 就是 T(n) = Θ(n)。使用 theta 时可以省略低阶项 (log(n))。

此外，f(n) 是 O(1)，因为每次递归只进行一次乘法 (rek(x, n/2) * rek(x, (n + 1)/2))。

Answer 2

复杂度为 0(n)。说明：您可以像使用简单循环一样进行所有乘法运算。而且您没有任何操作，即数字除以 * 的数字大于 const。因此，复杂度大约是 const*0(n)，它使得 0(n)。