求解代码的Big O运行时间：嵌套循环复杂度判断存疑

先把你的代码整理成更清晰的格式方便分析：

i = 0
sum = 0
while i < n:
    sum += 1
    if i == 3 or i == 5 or i == 7:
        j = 0
        while j < n:
            sum += 1
            j += 1
    i += 1

咱们一步步拆解：

• 首先看外层的while i < n循环：i从0一直走到n-1，总共会执行n次，每次循环里至少会做一次sum++，这部分的时间复杂度是O(n)。
• 再看内层的while j < n循环：它只有在i等于3、5、7这三个固定值的时候才会触发——不管n变得多大，触发的次数都是固定的3次，每次内层循环会执行n次sum++。所以内层循环的总操作次数是3*n，时间复杂度也是O(n)。

把两部分加起来，总操作数是n + 3n = 4n，而Big O表示法只看最高阶项，常数系数可以忽略，所以整体的时间复杂度还是O(n)。

你一开始的判断其实是对的，内层循环虽然看起来吓人，但它的触发次数是固定的，不会随着n的增大而增加，所以不会让复杂度升级到O(n²)~

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