python - 嵌套 while 循环的运行时间

Question

求内层while循环的迭代次数，和求内层循环的运行时间一样吗？此外，由于内循环依赖于外循环，我知道我应该将内循环的运行次数与外循环的运行次数相乘以获得迭代次数，对吗？我对如何计算 while 循环的迭代次数感到困惑。任何帮助，将不胜感激。谢谢!

def nested(n):
    b = 1 
    while b <= n:
        i = 1
        while i < b:
            print(i)
            i = i*3
        b += 1

感谢大家的帮助!

我想我明白答案是什么了。因此，由于我们试图找到内循环迭代的次数(n-1)，我还需要考虑外循环迭代内循环的次数(n)。因此，我们将迭代内部循环 (n-1)，n 次，如果我们使用求和符号，则得到 (n(n-1))/2。希望这是对的。

Answer 1

你有两个问题，所以我把它们分开了。

To find the number of iterations of the inner while loop, is it the same as finding the run time of inner loop?

没有。我冒昧地修改了您的代码以使用 time.process_time在不受操作系统调度程序干扰的情况下测量运行时间，并消除内部 print 语句(I/O 调用看似昂贵)。

import time

def nested(n):
    loops = list()

    #Start outer timer
    func_start = time.process_time()

    b = 1 
    while b <= n:

        #Start loop timer
        loop_start = time.process_time()

        i = 1
        while i < b:
            #print(i)
            i = i*3
        b += 1

        #Finish loop timer
        loop_finish = time.process_time()
        loops.append(loop_finish - loop_start)

    #Finish outer timer
    func_finish = time.process_time()

然后我添加一个日志语句:

print("Function time: %f, Sum loop times: %f, iterations: %i, iterations by runtime: %.0f" 
        % (func_finish - func_start, 
            sum(loops), 
            len(loops), 
            (func_finish - func_start) / (sum(loops)/len(loops)))  )

最后，我运行了几次。以下是结果:

Function time: 0.000019, Sum loop times: 0.000010, iterations: 10, iterations by runtime: 19
Function time: 0.000135, Sum loop times: 0.000102, iterations: 100, iterations by runtime: 132
Function time: 0.001461, Sum loop times: 0.000875, iterations: 1000, iterations by runtime: 1670
Function time: 0.017174, Sum loop times: 0.011532, iterations: 10000, iterations by runtime: 14892
Function time: 0.193567, Sum loop times: 0.133996, iterations: 100000, iterations by runtime: 144457

如您所见，随着迭代次数的增加，使用相对运行时间来尝试估计迭代次数变得不太准确。

Also since, the inner loop is dependent on on the outer loop,I know I should multiply the number of times the inner while loop runs with the outer while loop to get the number of times it is iterated, right?

理论应用也是如此。如果我在内循环中有 n 条指令，并且内循环运行了 m 次，我预测总运行时间实际上是 mn 。但是，您必须记住，一行代码不等于一条指令。事实上，甚至某些指令在执行时间方面也不等于其他指令(例如，浮点运算与整数运算)。我们在定时示例中看到了这一点。

为了计算 Big-O 运行时边界，您建议的将内部循环语句计数乘以循环次数的技术是可行的。在现实世界中，它变得更加复杂，对于像 Python 这样的解释型语言来说更是如此。