大O和Theta的循环

Question

for(int i = 2; i < n*n; i = i*i)
    for(int j = 1; j < i; j++)

我真的很困惑，如何在 n*n 和 i*i 互相影响我的假设是，它是O(n^2loglogn)，但我真的不知道如何推导它。

Answer 1

我的基础知识有点倾斜，所以对以下内容持怀疑态度。

对于生题。

你的迭代器形成了系列2, 2...², 2²², 2²²²... 这就是所谓的 渗透率. Tetration有两个反函数，分别是超根和。超对数. 后者在这里是相关的，因为我们有慢吞吞的。₂(n²)外循环的迭代。

但我认为用这个是不需要的。我们最后要做的是将内循环的步数相加，所有这些步数除了最后一个相加的步数外，所有这些步数相加的步数都小于最后一个步数，因为tetrations以极快的速度增长（如果我们只将值增加一倍就已经成立了）。这就给了我们一个2的系数，在Landau符号中我们可以忽略它。因此，重要的是只有最后一个内循环，它被 n². 这是一个上限（小于2n）。² 内步共），也有一个下限，假设n² 是真正的命中。因此我的答案是Θ(n²)，但我不确定我的思路是否没有犯错。如果能有另一种意见就更好了，比如有人评论说他认为我在这里是对还是错。

编辑：根据SomeWittyUsername的评论，这里是一个粗略的证明草稿。

让我们用迭代器来表示这个数列 i 经由 f(t), t = 1..t_max

首先，我们有 f(t) >= 2 每一步，因为它是这样初始化的，而且只会增加。

内循环对外循环的第t次迭代有f(t)次。因此总步数为 sum (t = 1..t_max) f(t) <= 2 * f(t_max). f(t_max) <= n*n ->总步数小于2n² 它是Θ(n)的元素²)