代码的时间复杂度分析

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它的takes 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中的单个对数.

我的数学不是很严格,但我希望你能得到这个想法.

Answer 2

让

L3 = 以 3 为底的对数 L2 = 以 2 为底的对数

那么正确答案是O(L3(L2(n))而不是 O(L2(L2(n))。

从x = x * 2开始。x 将呈指数增长，直到达到 n，从而使时间复杂度为 O(L2(n))

现在考虑x = x * x。x 的增加速度比上面的要快。在每次迭代中，x 的值都会跳转到其前一个值的平方。做一些简单的数学计算，我们得到以下结果：

对于 x = 2 n = 4，进行的迭代 = 1 n = 16，进行的迭代 = 2 n = 256，进行的迭代 = 3 n = 65536，进行的迭代 = 4

因此，时间复杂度为O(L2(L2(n))。您可以通过将值置于 n 值之上来验证这一点。

现在来解决你的问题，x = x * x * x。这将比 x = x * x 增长得更快。这是表格：

对于 x = 2 n = 8，迭代次数 = 1 n = 512，迭代次数 = 2 n = (512*512*512)，迭代次数 = 3 依此类推

如果你仔细看一下，结果是O(L3(L2(n))。 L2(n) 将为你提供 2 的幂，但由于你在每次迭代中都取 x 的立方，所以你必须取以 3 为底的对数，找出正确的迭代次数。

所以我认为正确的答案是O(log-to-base-3(log-to-base-2(n))

概括地说，如果x = x * x * x * x * .. (k times)，那么时间复杂度为O(log-to-base-k(log-to-base-2(n)