<分区>
我正在学习算法并在 top coder 中偶然发现了这篇文章。
这是来自 article 的示例
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)。请解释一下，我忽略了什么。我只是开始算法。