三层嵌套while循环原语操作计数疑问（大O符号相关）

代码片段 #

def question1(n):
    n = n           # 1 ops
    i = 0           # 1 ops
    a = 0           # 1 ops
    while i < n:            # n ops
        j = 0               # n ops
        while j < n:        # n * n ops
            k = 0           # n * n ops
            while k < 60:                   # 存疑：n * n * 60 还是 n * n * n * 60？
                a = i * j - i * 2 + k       # 对应操作计数
                k += 1                      # 对应操作计数
            j += 1          # n * n ops
        i += 1              # n ops

# total sum of prim operations = (n * n * 483) + (3 * n) + 3

核心疑问 #

计算最内层while k < 60循环的操作计数时，不确定该循环相关操作的总次数系数是n * n还是n * n * n，即总次数是n * n * 60还是n * n * n * 60。

结论与分析 #

最内层循环的总操作次数系数是n * n，即相关操作总次数为n * n * 60（对应循环体执行次数），而非n * n * n * 60，原因如下：

• 外层i循环执行n次，每次i循环中，j循环执行n次，因此i和j的组合总共有n * n次迭代。
• 每次进入j循环的迭代后，k循环的执行次数是固定的60次（k从0到59，循环体执行60次），和n的取值完全无关。
• 因此，最内层循环的所有操作（包括循环判断、循环体内的计算和k自增），都是基于n * n次的基础上，再乘以60次循环体执行次数，不会引入第三个n的系数。

以你标注的操作计数为例：

• while k < 60的判断（仅统计进入循环体的判断次数）总次数为n * n * 60
• 循环体内的a = i * j - i * 2 + k和k += 1，总次数分别为n * n * 60 * 5和n * n * 60 * 2，和你之前的计算逻辑一致。

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