algorithm - 无法理解算法的复杂性

Question

我正在学习算法，偶然发现了这篇顶级编码器的文章。

这是文章中的一个例子

int result=0;                           //  1
for (int i=0; i<N; i++)                 //  2
  for (int j=i; j<N; j++) {             //  3
    for (int k=0; k<M; k++) {           //  4
      int x=0;                          //  5
      while (x<N) { result++; x+=3; }   //  6
    }                                   //  7
    for (int k=0; k<2*M; k++)           //  8
      if (k%7 == 4) result++;           //  9
  }                                     // 10

第 6 行中 while 循环的时间复杂度显然是 O(N) - 它执行不超过 N/3 + 1 次。

我在这里很困惑，因为作者说时间复杂度是 O(N)。对我来说，这似乎是 O(N^4)。请解释一下，我忽略了什么。我只是开始算法。

Answer 1

第6 行中 while 循环的复杂度为 O(N)。