这段代码的时间复杂度是O(n^2)还是O(nlogn)？

Question

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j += i) {
       // some code
   }
}

外循环肯定会运行n多次。对于内循环，假设 n = 8，

我	j
1	1, 2, 3, 4, 5, 6, 7, 8 ---> 跑了N次
2	1, 3, 5, 7 ---> 运行 N/2 次
3	1, 4, 7
4	1, 5
5	1, 6
6	1, 7
7	1, 8
8	1

我很困惑复杂性应该是复杂性logn还是n内部循环。任何帮助将不胜感激！

Answer 1

外循环从i = 1到进行迭代n，步长为1。因此，外层循环执行n次数 - 线性时间复杂度。

内循环从j = 1到进行迭代n，步长为i。步长i取决于i外循环中的值。

正如你的表所示；

• 当iis时1，内循环执行n次。
• 当iis时2，内循环执行n/2次。
• 当iis时3，内循环执行n/3次。
• ...
• 当i为 时n，内循环执行n/n次数为1。

这些迭代的总和变为：

n + n/2 + n/3 + ... + 1

如果我们分解出n，我们就得到调和级数：

1 + 1/2 + 1/3 + ... 1/n

其时间复杂度近似于log(n)。您可以在这里看到更详细的解释/sf/answers/1813383211/

因此，总的来说，您的代码具有O(n log(n))时间复杂度。