代码之家  ›  专栏  ›  技术社区  ›  shinwari_afg

使用大Oh分析while(key<=N*N)循环的复杂性

  •  -2
  • shinwari_afg  · 技术社区  · 7 年前

    我对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(N2) 

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

    1 回复  |  直到 7 年前
        1
  •  1
  •   dEmigOd    7 年前

    你真正应该关心的是 k 更改。它在每次迭代中都会增长一次,这里没有捷径。

    所以这只是O(N 2. )。