内层循环仅执行一次时嵌套循环的时间复杂度分析

嘿，你的判断完全正确！这段代码的时间复杂度确实是O(n + m)，我来给你一步步拆解原因：

• 外层循环的开销：外层for循环会执行n次，每次迭代只做了i++和s += i这两个简单操作，这部分的时间复杂度是O(n)，这个你已经找对了。
• 内层循环的开销：内层for循环只会执行一次。因为K%2的结果是固定的（要么是0，要么是1），在外层循环的n次迭代里，只有当i等于这个固定值的时候，才会触发内层循环。内层循环执行m次，这部分的时间复杂度是O(m)。
• 总复杂度的计算：时间复杂度关注的是最坏情况下的总操作数的量级。这里总操作数是外层的n次加上内层的m次（总共n + m次左右），所以总复杂度是两者的线性和，也就是O(n + m)。

那什么时候会是O(nm)呢？如果内层循环是每次外层循环都执行（比如把if条件去掉，或者条件每次都成立），那总操作数就是n*m次，这时候复杂度才是O(nm)。但显然你的代码里内层只跑一次，完全达不到这个量级。

举个实际的例子：假设n=1000，m=1000，你的代码总操作数大概是1000+1000=2000次；如果是O(nm)的情况，总操作数会是1000*1000=1,000,000次，差距非常大，这也能直观说明两者的区别。

内容的提问来源于stack exchange，提问作者Vinh Quang Tran