java - 下面递归方法的运行时分析

Question

有人可以帮我对以下代码进行运行时分析：

public static void f(int n) 
{
    for (int i = 0; i <= n; i++) 
    {
        System.out.print("+" + i);
    }
    if (n <= 1) 
    {
        return;
    } else 
    {
        f(n / 3);
        f(n / 3);
    }
}

据我说，代码递归公式的运行时间是：

T(n) = cn + 2T(n/3)

我认为答案应该是Θ(nlog(n))，但书上的解决方案显示它是Θ(n)。书中还说n = 3^k为了简单起见。

有人可以向我解释正确的答案吗？

Answer 1

考虑使用主定理。您的情况对应于案例 1，其中 f(n)=cn 为 O(n)。在 a=2 和 b=3 的情况下，应用定理，我们有 T(n) 是 bigTheta(n^log3(2))，即 BigTheta(n)。

希望能帮助到你 ...