内部循环取决于外部循环的复杂性

Question

对于下面的伪代码，我想在输入大小为n之前计算出操作数量，然后再将其放入Big-O-Notation：

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

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

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），该规则非正式地说：

f/g的限制与f'/g'的限制相同，假设限制甚至存在。

---

注意

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