当n为常量时，嵌套循环的时间复杂度是O(n²)还是O(1)？

首先看你给出的伪代码：

int n = 100
for (int i = 1; i<=n; i++)
 System.out.println("Hello!");
  for (int j = 1; j<=n; j++)
   System.out.println("World!!!");
  end
end

这段代码的时间复杂度是O(1)，原因如下：

• 时间复杂度的本质是描述算法运行时间随输入规模的增长趋势。这里的n是直接赋值为100的固定常量，不是由外部输入决定的可变规模参数。
• 程序执行的操作次数是固定的：外层循环执行100次，每次外层循环里内层循环执行100次，总操作次数是100 + 100*100 = 10100次，是一个确定的常数。无论运行多少次，这个次数都不会变化，不存在随某个变量规模增长而变化的情况。

至于有人认为是O(n²)，是混淆了“作为输入规模的n”和“作为常量的n”。通常我们说嵌套循环的时间复杂度为O(n²)，是当n代表输入的规模（比如处理一个长度为n的数组，n可以是任意正整数）时，循环次数会随n的平方增长。但在这段代码里，n是固定值，不存在规模增长的可能，所以不能套用这个结论。

内容的提问来源于stack exchange，提问作者ALFIAN BIN ABDUL HALIN FSKTM