内循环的时间复杂度是如何计算的？

Question

for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        System.out.println(j);
      }
 }

上述代码的时间复杂度是多少？

假设n=10： 对于外循环的每次迭代，内循环运行 n 次，即 10*10 = 100 次。而外循环运行 n 次，即 10 次。那么不是很大哦，O(n)*O(n2)=O(n3) 吗？我认为它是 O(n2)。

Answer 1

我认为它是 O(n2)。

O(𝑛²) 是正确的（但请参阅下文了解细微差别）。

外循环确实有 𝑛 次迭代，但如果您已经将 𝑛² 计算为内循环迭代的 total，那么它是加法，而不是乘法。因此，通过这种方法，您可以说它是 O(𝑛 + 𝑛²)，即 O(𝑛²)。

但是由于数字的打印，情况变得复杂了。如果我们只是忽略这一点，并考虑打印一个数字的时间复杂度为 O(1)，那么我们就完成了。但事实是，打印工作量取决于要打印的字符数。打印五位数字比打印一位数字需要更长的时间。

数字𝑛中的位数是O(log𝑛)，因此打印调用的时间复杂度是O(log𝑗)。因此，总共我们有 O(𝑛(log1 + log2 + ... + log𝑛))，即 O(𝑛(𝑛log𝑛))，即 O(𝑛²log𝑛)。