这个问题的时间复杂度答案让我感到困惑 - n^(2/3)

Question

我想弄明白为什么这段代码的时间复杂度是n^2/3。 space复杂度是log n，但是我不知道如何继续计算时间复杂度（或者是否正确）。

int g2 (int n, int m)
{
  if (m >= n)
  {
    for (int i = 0; i < n; ++i)
      printf("#");
    return 1;
  }
  return 1 + g2 (n / 2, 4 * m);
}

int main (int n)
{
  return g2 (n, 1);
}

Answer 1

只要m < n，你执行一个O(1)操作：进行递归调用。你减半 n 和四倍 m，所以在 k 步之后，你得到

n(k) = n(0) * 0.5^k
m(k) = m(0) * 4^k

您可以将它们设置为彼此相等以发现

n(0) / m(0) = 8^k

记录日志

log(n(0)) - log(m(0)) = k log(8)

或

k = log_8(n(0)) - log_8(m(0))

在第 k 次递归中执行 n(k) 次循环迭代。

您可以将 k 插回 n(k) = n(0) * 0.5^k 以估计迭代次数。让我们暂时忽略 m(0)：

n(k) = n(0) * 0.5^log_8(n(0))

再取双方的log，

log_8(n(k)) = log_8(n(0)) + log_8(0.5) * log_8(n(0))

从log_8(0.5) = -1/3开始，你得到

log_8(n(k)) = log_8(n(0)) * (2/3)`

再次取指数：

n(k) = n(0)^(2/3)

由于任何正指数都会压倒 O(log(n)) 递归，因此您最终的复杂度确实是 O(n^(2/3)).

让我们看看如果 m(0) > 1.

会发生什么

n(k) = n(0) * 0.5^(log_8(n(0)) - log_8(m(0)))

再次获取日志：

log_8(n(k)) = log_8(n(0)) - 1/3 * (log_8(n(0)) - log_8(m(0)))
log_8(n(k)) = log_8(n(0)^(2/3)) + log_8(m(0)^(1/3))

所以你得到

n(k) = n(0)^(2/3) * m(0)^(1/3)

或

n(k) = (m n^2)^(1/3)

关于起始条件中极端情况的快速说明：

对于m > 0:

如果n <= 0：，n <= m立即为真，递归终止，没有循环。

对于m < 0：

如果n <= m，则递归立即终止，没有循环。如果n > m，n会收敛到零，而m会发散，算法会永远运行。

唯一有趣的情况是 m == 0。不管n是正数还是负数，因为是整数t运行cation，所以都会归零，所以复杂度取决于它什么时候到1：

n(0) * 0.5^k = 1
log_2(n(0)) - k = 0

所以在这种情况下，递归的运行时间还是O(log(n))。循环不运行.

Answer 2

m 从 1 开始，每一步 n -> n/2 and m -> m*4 直到 m>n。在 k 步之后，n_final = n/2^k 和 m_final = 4^k。所以 k 的最终值是 n/2^k = 4^k 或 k = log8(n).

当达到这个时，内循环执行n_final（约等于m_final）步，导致复杂度为O(4^k) = O(4^log8(n)) = O(4^(log4(n)/log4(8))) = O(n^(1/log4(8))) = O(n^(2/3)).

这个问题的时间复杂度答案让我感到困惑 - n^(2/3)

The time complexity answer to the question confuses me - n^(2/3)

c

recursion

time-complexity