Java 与for循环的递归关系

Question

public int algo(int n) {
    if (n == 1) {
        return 1;
    }
    algo(n/2);
    for (int i = 0; i < 4; i++) {
        System.out.print(i);
    }
    return 0;
}

我知道递归调用意味着它是T(n/2)但是for循环将如何影响递归关系？

编辑：我的尝试。

我认为 for 循环将运行 log n 次，因为每次 algo(int n) 是运行时它都是运行。 algo 是运行 log n 次，因为 n 一直被 2 除。此外，for 循环运行s 进行 4 次迭代。所以我认为它会在循环中增加一个额外的 4 log n 所以它将是 O(n) = T(n/2) + 4 log n.

Answer 1

在这里你在每次递归调用中将 n 除以 2，for loop 不依赖于输入 n，所以时间复杂度是 O(logn)。 for loop 增加的时间复杂度是常量，因此将被丢弃。

在计算时间复杂度时，你必须担心 input.Here 的变化，你的 for loop 不依赖于输入 n，因此在计算时间复杂度时不符合条件.

Answer 2

因为 for 循环是常数时间，并且不随 n 变化。应该不会影响时间复杂度。

Answer 3

具体来说，for 循环对递归关系的影响充其量是微不足道。如果没有 for 循环，您的递归关系将是：

T_n = T_n/2 + c

其中 c 是检查 n==1 和方法调用以及 returns 的开销。 for 循环始终恰好打印 4 次，因此始终在 k 操作中执行。新的递推关系为：

T_n = T_n/2 + c + k

令人兴奋的是...我们仍然有一个常量 (c+k) 我们有 c 之前所以我们会得到相同的 O(log n).

Java 与for循环的递归关系

Java recurrence relation with for loop

java

recurrence