代码片段的复杂性

Question

for(int i = 0; i < N; i++)
  if(i < 2 || i > N - 3)
    for(int j = 1; j <= 10N; j++)
      a[i] = a[j - 1] / 2;

所以答案是 N(1 + 10N(1)) = n + 10n^2 对吗？或者是n？ 请解释一下。

Answer 1

在我看来，这看起来O(N)。

if 语句对于 i = 0,1,N-1,N-2 成立，这是常数个情况。

Answer 2

你的结论是错误的。尽管外部 for 循环 N 次，但 if 条件仅在 4 种情况下为真（0、1、N >-2，N-1）。因此总运行时间为 N + 4·10·N，即 O(n)。

Answer 3

如果你想要一个渐近上限... O(n^2)。如果您想要比这更挑剔，我们需要为各个指令定义计算权重。

编辑：是的，它是 O(n)。我第一次读错了。