内循环依赖于外循环的复杂性
Complexity where inner loop depends on outer loop
对于以下伪代码，在将其放入 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)。
但我不确定我是否在正确的轨道上，因为我还没有看到任何这样的问题，其中外循环的索引用于内循环。
正确，在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）。
结果的table是
< 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) 中，否则您显然也需要考虑其复杂性。
对于以下伪代码，在将其放入 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)。
但我不确定我是否在正确的轨道上，因为我还没有看到任何这样的问题，其中外循环的索引用于内循环。
正确，在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）。
结果的table是
< 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/gis the same as the limit off'/g', supposed the limit even exists.
备注
分析假设 // operation 在 Theta(1) 中，否则您显然也需要考虑其复杂性。