2

我在大问题方面遇到了一些挑战。这些不是作业问题。我写这些问题是为了更好地理解这里的概念。

function func(n)
{
     int k,i = 0;
     while(k < n){ < --- Guessing this outer loop is O(n/2)
        k = n + 2
        i = 0;
        while(i < k){ <--- Not sure what this is?
            i ++;
            i = i * i;
         }
      }         
}

如果你能向我解释内部循环中发生了什么，以及你的逻辑如何以你最终得到的 big-o 符号结束，我真的很高兴。

4

3 回答 3

4

外部循环及其测试(k < n)及其步骤k = n + 2将运行一次，提供 O(1) 的复杂性因子。

内部循环有 test (i < k)，也就是(i < n+2)，最后有 steps i++; i=i*i; ，

i = (...(((1+1)^2+1)^2+1)^2+ ... )^2 > n+2`

这使得i超指数的价值。也就是说，i在 p 次传递中比 exp(exp(p)) 增长得更快，因此总体复杂度小于 O(log log n)。这是一个比前面提到的 O(log n) 更严格的界限，后者也是一个上限，但没有那么严格。

于 2012-10-30T17:15:34.050 回答
2

第二个循环对 的值进行平方，i直到达到k。如果我们忽略常数项，这个循环会O(log k)及时运行。

为什么？因为如果你解决了i^m = k，你就会得到m = constant * log(k).

正如您所说，外循环O(n)及时运行。

由于更大的值k取决于n，您可以说内部循环运行在O(log n)其中给您一个整体的复杂性O(n log n)。

于 2012-10-30T16:34:51.210 回答
2

虽然@alestanis 提供的内容在我看来比评论中的分析更准确，但我仍然认为这不太正确。

让我们创建一个小测试程序，打印出i内部循环产生的值：

#include <iostream>

void inner(double k) {
    double i;

    i = 0.0;
    while(i < k) {
        i ++;
        i = i * i;
        std::cout << i << "\n";
     }
}

int main() {
    inner(1e200);
    return 0;
}

当我运行它时，我得到的结果是：

1
4
25
676
458329
2.10066e+011
4.41279e+022
1.94727e+045
3.79186e+090
1.43782e+181
1.#INF

如果迭代次数是对数的，那么达到特定数字的迭代次数应该与限制中的位数成正比。例如，如果它是对数的，它应该需要大约 180 次迭代才能达到 1e181，给定或取一些（相当小的）常数因子。这显然不是这里的情况——通过查看科学记数法中结果的指数很容易看出，这大约是每次迭代的数字数量的两倍，其中对数意味着每次迭代大约增加一个数字。

我不是很确定，但我相信这会将内部循环置于 O(log log N) 之类的位置，而不仅仅是 O(log N)。我认为很容易同意外循环可能打算为 O(N) （尽管它目前被编写为只执行一次），将整体复杂性置于O(N log log N).

我觉得有必要补充一点，从实用的角度来看，O(log log N)通常可以将其视为基本恒定的——如上所示，您可以使用典型的双精度浮点数指定的最高限制仅在 11 次迭代中达到。因此，对于大多数实际目的，整体复杂性可以被视为O(N).

[哎呀——在我写这篇文章的时候没有注意到他已经回答了，但看起来@jwpat7 已经得出了与我相同的结论。向他/她致敬。]

于 2012-10-30T17:25:30.923 回答