大哦嵌套，而

我有一些大oh问题的挑战。这些不是家庭作业问题。我写这些问题是为了更好地理解这里的概念。大哦嵌套，而

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; 
     } 
     }   
}

我真的喜欢它，如果你能向我解释什么是在内环怎么回事，怎么你的逻辑在大O符号，你终于在最后结束。

来源

2012-10-30 bluejamesbond

'k = n + 2'不应该是：'k = k + 2'还是类似的东西？现在你的外层循环不会迭代多次。 – Joost

我估计时间复杂度仍然停留在O（n * m）。内部循环是O（m），外部循环，就像你提到的那样，是O（n/2）。总结它是O（n * m）/ 2。 2是一个常数，随着投入量的增加，它将与比率无关。我正在学习自己。所以，我可能是错的。 –

您可能对[此问题]感兴趣（http://cs.stackexchange.com/questions/4800/the-order-of-growth-analysis-of-simple-for-loop）[cs.se]和这些问题与Raphael的评论有关。 – Gilles

虽然@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-30 17:25:30

我同意内部循环的复杂度是O（log log N）。由于（...（（（1 + 1）^ 2 + 1）^ 2 + 1）^ 2 + ...）^ 2增长速度显着快于exp，我不知道它是否是θ（log log N）（exp（p/2））p –

@ jwpat7：是的，我想过试图更彻底地分析它，但结果是迭代次数接近常数，我很难真正关心它。 .. –

第二个循环的值为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-30 16:34:51 alestanis

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

内环具有测试(i < k)这就是说(i < n+2)，且具有步骤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-30 17:15:34

大哦嵌套，而

回答

相关问题