algorithm - 任何循环的实际时间复杂度是多少，比如 for 循环？

Question

当我们必须计算一个循环的复杂度时，比如说一个 FOR 循环（它说需要运行 n 次），我们是否还应该计算 FOR 循环的条件失败并中断时的迭代？

这是一个例子：

i并且n是正整数

for(i=0;i<n;i++)
{
   //some code. All are constant expressions and there are no break statements.
}

现在内部代码将运行 0 到 n-1 次，即 n 次。当 i = n 时，循环中断，但这仅在检查 for 循环条件后发生。最后一次检查是否应该计算时间复杂度，因为如果计算它，那么 FOR 循环实际上将运行 n+1 次？我不确定我在这里是否有意义。我想应该算了吧。我仍然需要一些明确的答案。请建议！

score 3 · Accepted Answer

如果您真的需要精确，请引入一些常量。让a检查一次循环条件b的时间和运行循环中所有命令的时间。该循环将在以下总时间内运行：

a(n+1) + bn = (a+b)n + a

由于其他答案解释的原因，您很少需要如此精确。什么时候比做一次的时间n大得多与大局无关。这就是为什么我们放弃所有低阶项和常数并说：aa

(a+b)n + a ∈ Θ(n)

score 1 · Accepted Answer

计算函数的计算复杂度的要点是确定该函数是否会随着n的增加而很好地扩展，而不是确定对于特定的n值它将运行多少次。例如，当n为 1 时，您的循环可能运行得非常快，但如果 n 突然变为 1000，它会以（大约）原始时间的 1000 倍运行，还是您正在寻找更高的因素？

像您提供的那样的 for 循环将始终运行 - 最坏的情况 - n次。无论n是 100 还是 10^30，循环都会涉及n次迭代。考虑到更大的图景，对该循环的额外比较是无关紧要的。如果您要处理 10^30 次迭代，那么一次额外的迭代不会产生任何影响。

score 1 · Accepted Answer

如前所述，时间复杂度是渐近的——这意味着如果你有一个从 1 到 n 的循环，那么你在循环中做了多少操作并不重要——只要它们是最终的，复杂度就会是O(n)，因为O(10000n) = O(n)

score 0 · Accepted Answer

考虑常数，不测量时间复杂度。正如 MZF 所说。 O(an+c)=O(n) 其中 'a' 和 'c' 是常数。但是如果在那个 for 循环中还有一个循环，那么时间复杂度将是 O(a(n^2) +c) 等等......

4 回答 4