c - 代码时间复杂度分析

Question

int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

我需要分析它的时间复杂度。我注意到它到达 n 的速度比 log(n) 快得多。我的意思是，它比 O(log(n)) 做的步骤少。我阅读了答案，但不知道他们是如何得出答案的:它是 O(log(log(n))。现在，您如何处理这样的问题？

Answer 1

将其视为递归函数:

f(i) = f(i-1)^3

如果你展开它:

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

函数随着幂次方的增长而增长...所以达到一定数量(即计算函数的倒数)的时间(迭代次数)是对数的对数。

在您的示例中 f(0) = 2，我们想知道什么时候 f(i) >= n 是 n输入参数(和 i 迭代次数):

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

因此，要达到 n 的值，它需要 log_3(log_2(n)) 次迭代(在处理超过它的整数时四舍五入)。

如果函数是:

f(i) = 2*f(i-1) //e.g. x=2*x

那么模式就是:

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

在这种情况下，函数的反函数将是一个以 2 为底的对数。

我的数学不是很严谨，但我希望你能明白。