使用 Big-Oh 分析 while(key <= N*N) 循环的复杂度

Question

我对这个 while 循环的 Big-O 表示法感到困惑，其中 N 是输入大小：

 int array[0][(N-1)/2] = 1;
 int key = 2,k,l;
 i = 0;
 int j = (N-1)/2;
 while(key <= N*N)
  {
   if(i <= 0)
    k = N-1;
   else
    k = i-1;
   if(j <= 0)
    l = N-1;
   else
    l = j-1;
  if(array[k][l])
    i = (i+1)%N;
  else
    {
      i = k;
      j = l;
     }
  array[i][j] = key;
  key++;
   }

I concluded it as O(N<sup>2</sup>) 

因为当 N=5 时，它会迭代直到 N*N，即 5*5=25 次，但我仍然对循环内的其余代码感到困惑。如果有人能一步一步地解释代码，我将不胜感激，这个循环只是一个更大的函数的一部分，它有 4 个循环，我理解但不是这个循环。

Answer 1

你真正应该关心的是，k如何变化。它在每次迭代中增长 1，这里没有捷径。

所以它只是 O(N²).