为何这段Java代码的时间复杂度为O(n)？求复杂度判断技巧

先拆解你给出的这段Java代码，搞清楚为什么它的时间复杂度是O(N)而非O(N³)：

代码逐段分析 #

1. 第一段嵌套循环

   • 外层循环：for(int i=0; i<N; i=i+2)，这个循环会执行约N/2次，属于**O(N)**量级的迭代次数，但重点在它的循环体：
   • 中间层循环：for(int j=N; j<N; j++)，初始化j=N后，判断条件j<N从一开始就不成立，所以这层循环一次都不会执行，里面的最内层循环自然也不会运行。
   • 所以这段嵌套循环的实际有效操作，只是外层循环的条件判断和迭代，总次数是O(N)。

2. 第二段独立循环
   for(int k=0; k<100; k++)是固定执行100次的循环，属于常数时间O(1)，在时间复杂度分析中会被忽略，因为它不会随着N的增大而增长。

综上，整段代码的时间复杂度由外层循环的O(N)主导，最终结果是O(N)。

快速判断时间复杂度的实用技巧 #

• 先查循环的执行有效性：如果循环的终止条件永远不满足（比如上面的中间层循环），直接跳过这层，不用考虑它的嵌套量级。
• 抓增长主导项：只保留随着N增大，执行次数增长最快的部分，常数项、低阶项全部忽略（比如O(N)+O(1)→O(N)，O(N²)+O(N)→O(N²)）。
• 看循环的步长与终止逻辑：步长为固定值（比如i=i+2）的循环，次数是O(N)；如果是指数级增长（比如i*=2），则是对数级O(logN)。
• 跳过无效代码：空循环、永远不触发的分支，对时间复杂度没有影响，直接忽略。
• 嵌套循环看实际执行次数：只有当每层循环都能完整执行，且次数和N相关时，才会将各层的复杂度相乘（比如三层都执行N次，才是O(N³)）。

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