关于嵌套for循环时间复杂度：为何误判为O(n!)而非O(n²)？

嘿，这个问题问得挺典型的，我来帮你捋清楚你哪里想岔了～

首先，你最大的误区是把迭代次数的求和当成了求积！我们来仔细算一遍修改后循环的总迭代次数：

• 当i=0时，j从0到n-1，一共执行n次
• 当i=1时，j从1到n-1，一共执行n-1次
• ...
• 当i=n-1时，j只能取n-1，一共执行1次

所以总次数是一个等差数列的和：n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2，这可不是阶乘n!哦！

接下来再看时间复杂度：大O表示法关注的是随着n增大时，运行时间的增长趋势，会忽略低阶项和常数系数。n*(n+1)/2展开后是(n² + n)/2，最高次项是n²，所以它的时间复杂度依然是O(n²)，和原来的双层循环属于同一个量级。

你觉得“复杂度反而更差”是混淆了两个概念：

• 一个是实际迭代次数：修改后的循环确实比原来少（比如n=10时，原来100次，修改后55次）
• 另一个是时间复杂度量级：两者的增长速率都是和n²成正比的，当n趋近于无穷大时，常数系数的差异会被忽略，所以复杂度并没有变“差”

简单说，你把加法算成乘法导致误以为是阶乘，又混淆了具体次数和复杂度量级的区别，这就是你忽略的关键点啦～

内容的提问来源于stack exchange，提问作者SDG