含随机性的三层嵌套循环时间复杂度问询：内层是否为O(1)？

先贴出你的代码：

for i in range(m):
    for j in range(n):
        r = random(0, l)
        for k in range(r):
            # 内层循环体
        l = l - r

最内层循环是否等价于O(1)？ #

答案是否定的。最内层循环的执行次数是随机生成的r（范围为[0, l]），单次迭代的复杂度为O(r)。r并非固定常数，它会随l的变化而改变，且每次取值具有随机性，因此不能将单次最内层循环等价于O(1)。

整体时间复杂度分析 #

需要结合l的初始值（记为L）与m*n的大小关系讨论：

• 当L ≤ m*n时：l最多在L次外层循环迭代中被减至0（若r多次取正值，这个过程会更快），之后所有外层循环迭代里r只能为0，内层循环不再执行。总操作次数为外层循环的m*n次O(1)操作，加上内层循环的总次数（最多为L），整体复杂度为O(max(m*n, L))。
• 当L > m*n时：外层循环会完整执行m*n次，每次内层循环执行r次，所有内层循环的总执行次数最多为L（因为每次l都会减少r，m*n次后l剩余值L - sum(r) ≥ 0）。总操作次数为m*n次外层迭代操作加上最多L次内层循环操作，整体复杂度同样为O(max(m*n, L))。

你提到“前两层循环的复杂度应为O(mn)”，这个说法仅在L是常数（即L不随m、n变化）时成立——此时内层循环总次数为O(1)，整体复杂度由前两层的m*n次迭代主导，为O(mn)。但如果L是与m、n同量级或更大的变量，就不能忽略内层循环的总次数，整体复杂度需考虑max(m*n, L)。

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