Big O 和 Theta for 循环

Question

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

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

Answer 1

我的基础知识有点偏了，所以请对以下内容持保留态度。

原始主题：

您的迭代器形成系列 2, 2², 2²^², 2²^²^{^²}...
这被称为 Tetration.
Tetration有两个反函数，分别是超根和super-logarithm。后者在这里是相关的，因为我们有外循环的 slog₂(n²) 次迭代。

但我认为不需要使用它。我们最后要做的是总结内循环的步骤，除了最后一个总结的所有步骤加起来都比最后一个少，因为四次循环以极快的速度增长（如果我们' d 只是价值的两倍）。这给了我们一个因子 2，我们可以在 Landau 表示法中忽略它。
因此，重要的只是最后一个内部循环，它受 n² 约束。这是一个上限（总共少于 2n² 个内部步骤）也是一个下限，假设实际命中了 n²。因此我的答案是 Θ(n²)，但我不确定我在思考过程中是否没有犯错。
如果有人发表意见，如果他认为我在这里是对还是错，那将是很好的。

编辑：根据 SomeWittyUsername 的评论，这里是证明的草稿：

让我们用 f(t), t = 1..t_max

表示迭代器 i 经历的系列

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

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

的元素

Big O 和 Theta for 循环

Big O and Theta for loop

c++

big-o

for-loop

time-complexity