algorithm - 确定递归函数的 CN 和时间复杂度

Question

public static int test(int N) {
  if (N == 1) return 1; 
  return (3 * (test(N/2) + test(N/2)) + f(N)) 
}

public static void f(int a) {
  for (int i = 1; i <= a; i++) 
  System.out.println(“algo rocks”);
}

我试图确定上述代码的 CN 和复杂度

我得出这个结论

• C₁ = 0 --> 终止条件
• C_N = 2C_N/2 + N

我迷失了这 3 个功能相乘的，你能检查我的工作并指导我错在哪里吗。

Answer 1

你声称 C(1) = 0 是错误的，它实际上是 1。

所以，C(1) = 1。

此外，函数 f() 的时间复杂度在最坏情况下为 O(N)，因为 N 被传递给函数。

所以，你的递推关系变成了:

T(N) = 3 * 2 * T(N/2) + O(N)
     = 6 T(N/2) + O(N).

我把递归关系留给你解决。这很容易。如果您无法计算，请至少在尝试一次后在此答案下方执行 ping 操作。