数据结构与算法：Java嵌套循环时间复杂度分析：O(n^2*logn)是否正确？

你之前认为代码时间复杂度为O(n²*logn)的判断完全不正确，这段代码的实际渐近时间复杂度为O(n²)。

逐层拆解各层循环的执行规模 #

• 最外层i循环：迭代边界为变量n，共执行n次，执行次数与n线性正相关
• 中间层j循环：迭代边界同样绑定变量n，对每一次i的取值，j都会完整遍历0到n-1，两层循环叠加的执行次数为n*n = n²量级
• 最内层k循环：迭代边界为固定常量100000，完全不随输入n的变化而调整，无论n取何值，这层循环的执行次数永远固定为100000次，循环内的a++是单次固定操作

为什么不存在logn相关项 #

时间复杂度分析中出现logn项的典型场景，是循环的迭代步长为固定比例缩放（比如每次迭代将遍历规模折半、翻倍），迭代次数和n的对数直接相关。这段代码里所有循环的遍历边界都没有比例缩放逻辑，完全没有产生log项的来源。

实际复杂度的推导 #

整段代码的总操作次数为：n * n * 100000。
根据大O表示法的规则，不随输入规模n变化的固定常数因子可以直接省略——大O表示法描述的是输入规模增长时的渐近变化趋势，当n从100增长到1000时，总操作数会变为原来的100倍，完全符合n²的增长速率。哪怕最内层的固定循环次数是100万次、1亿次，只要它不随n的大小变化，就属于不影响增长量级的常数项，因此最终的时间复杂度为O(n²)。

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