找到 CN 和时间复杂度

Question

通过对复发的研究，我试图解决这个复发 你能帮我查一下吗

public static int java(int N) {
  if (N == 1) 
    return 1; 
  return (java(N/2) + java(N/2)); 
}

我认为这是等式

C(1) = 1
CN = 2CN/2 + 1

复杂度为 O(log N)

你能帮我查一下吗

Answer 1

public static int java(int N) {
  if (N == 1) 
    return 1; 
  return 2 * java(N/2); 
}

与其调用相同的两次，只需将其乘以2。对于相同的输入无需再次计算。

复杂度为 O(log N)，因为您每次都将问题除以 2 的因数。