algorithm - 内循环依赖于外循环的复杂性

Question

对于以下伪代码，在将其放入Big-O-Notation 之前，我想计算出作为输入大小 n 的函数的操作数:

for i ← 1 to n do
    for j ← 3 to 3i+n do
        // operation 

到目前为止，我认为对于外层循环 n 的每次迭代，内层循环等于 3i + n - 2 操作。屈服

n (3i + n - 2) = n^2 - 2n + 3ni

这简化为 O(n^2)。

但我不确定我是否在正确的轨道上，因为我还没有看到任何这样的问题，其中外循环的索引用于内循环。

Answer 1

正确，在O(n^2) .不仅如此，它在 Theta(n^2) 中.

---

解释

唯一重要的是频率// operation正在执行。循环本身的计算，比如索引都在 Theta(1) 中。 , 所以我们可以忽略它们。

因此，计算 // operation 的频率被执行。即n * (3i + n - 2) ，就像你说的。

然而，i变化。所以你实际上需要把它完整地写出来:

简化这个:

这显然在 Theta(n^2) 中.

---

形式定义证明

您可以通过正式定义轻松证明这一点。因此，让我们调用函数 f .我们有

所以它在O(n^2) .我们有

屈服 Omega(n^2) .这意味着 f in Theta(n^2) .

我随机选择了常量。您可以将它收得更紧，但您只需要找到一个它可以固定的，所以没关系。

---

极限定义证明

当然我们也可以使用极限定义轻松地显示它:

这是> 0和 < inf , 所以 f in Theta(n^2) (参见 Wikipedia:Big-O-notation)。

结果表是

• < inf是O(g)
• > 0是Omega(g)
• = 0是o(g)
• = inf是omega(g) .
• > 0 and < inf是Theta(g)

对于限制，我们使用了 L'Hôpital 的规则(参见 Wikipedia)，它非正式地说:

The limit of f/g is the same as the limit of f'/g', supposed the limit even exists.

---

注意事项

分析假设 // operation在Theta(1) ，否则您显然也需要考虑其复杂性。