algorithm - 下面这段代码的渐近运行时间是多少？

Question

下面这段代码的渐近运行时间是多少？

if (N % 2 == 0) // N is even
 for (int i = 0; i < N; i = i+1)
   for (int j = 0; j < N; j = j+1)
      A[i] = j;
else // N is odd
 for (int i = 0; i < N; i = i+1)
   A[i] = i;

如果 N 是偶数，我们看到运行时间是 O(n^2)，当 N 是奇数时，运行时间是 O(n)。但是我无法确定渐近运行时间是多少。

可能的答案是:

• ~ O(n)
• ~ O(n^2)
• ~ O(N * sqrt(N))
• ~ O(n log n)

Answer 1

没有可用于渐近紧密绑定(bind)运行时的简单函数。正如您所指出的，运行时在每一步都在线性和二次之间振荡。您可以说运行时间为 O(n²) 和 Ω(n)，但如果不定义分段函数，您就无法在此处给出 Θ 边界。