代码的时间复杂度分析

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

让

L3 =登录基地3 L2 =登录基地2

然后正确的答案是 O（L3（L2（n））和NOT 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的幂，但是因为你正在拿立方体在每次迭代中，你必须将log记录到它的基数3，以找出正确的迭代次数。

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

概括这一点，如果 x = x * x * x * x * ..（k次），那么时间复杂度为 O（log-to-base-k（log） -to基-2（n）的

Answer 2

将其视为递归函数：

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))

所以要达到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 3

考虑x如何随着循环中的迭代次数而变化。每一次，你都是立方体。因此，在迭代之后，该值将是2立方，再次立方......依此类推，我的时间。我们用x（i）来表示这个表达式。假设x（0）= 2，x（1）= 2 3等（我使用 b表示提升到b次幂）。

我们在x（i）<！> gt; = n时完成。多久时间？让我们为我解决。

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

我们可以忽略常数因素，我们得出的结论是我们将采用log（log（n））步骤。这就是算法的复杂性。

希望打破这样的所有步骤会有所帮助。

Answer 4

如果while循环中的代码是

x = 2*x;

x将在O（log（n））次迭代中达到n。由于你是立方x而不是将它乘以常数，你会更快达到n。

Answer 5

给出

log ( A * x )     == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )

所以

log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
                          == log ( 3 ) + log ( log ( x ) )

这个函数比你的函数更快或更慢（通过循环的迭代次数来衡量）？

int log_foo ( int n ) 
{
    double          log_x = log ( 2 );
    const double    log_n = log ( n );

    while ( log_x < log_n )
    {
        log_x = 3 * log_x;
    }

    return exp ( log_x );
}

这个功能比你的功能更快或更慢？

int log_log_foo ( int n ) 
{
    double          log_log_x = log ( log ( 2 ) );
    const double    log_log_n = log ( log ( n ) );
    const double    log_3     = log ( 3 );

    while ( log_log_x < log_log_n )
    {
        log_log_x += log_3;
    }

    return exp ( exp ( log_log_x ) );
}

但是这个函数只增加log_log_x一个常数，所以很容易计算它做了多少迭代。

Answer 6

让i成为迭代步骤的数量，x(i) x步骤之后x(i) < n的值。我们有

x(0) = 2
x(i) = x(i-1)³

步骤总数最大<=>以便<=>。

我们有

log x(i) = log x(i-1)³
         = 3·log x(i-1)
         = 3·log x(i-2)³
         = 3²·log x(i-2)
         = 3^i·log x(0)
         = 3^i·log 2

⇒  log log x(i) = log (3^i·log 2)
                 = log 3^i + log log 2
                 = i·log 3 + log log 2

对数严格增加，所以

x(i) < n ⇔        log log x(i) < log log n
         ⇔ i·log 3 + log log 2 < log log n
         ⇔                   i < (log log n - log log 2) / log 3 ∈ O(log log n)

Answer 7

为什么不添加计数器变量来计算循环的迭代次数。在函数返回之前将其打印出来。

然后调用函数以获取一系列值，例如3到1,000,000开始。然后使用 GNUPlot 等内容绘制结果。

然后查看图表是否与已知曲线匹配。