Skip to main content
 首页 » 编程设计

python之对关于 Python 函数的最佳/最坏情况时间的回答感到困惑

2024年10月25日14lidabo

这是 edx 类(class)“计算机科学简介和使用 Python 编程”中的一个小问题。

def program1(x): 
    total = 0 
    for i in range(1000): 
        total += i 
 
    while x > 0: 
        x -= 1 
        total += x 
 
    return total 

问题:在最佳情况下运行程序 1 需要多少步?用 n 表示你的答案,输入 x 的大小

答案:最佳情况:3003 最坏情况:5n+3003

我对答案 3003 感到困惑,因为根据我的说法,问题的最佳情况是如果 x =-1 并且其他语句执行的时间量是恒定的。因此 声明

total =0   // takes a constant amount of time 1 
 
for i in range(1000): 
    total += i        // takes 1000*1 amount of time 
 
 
return total   // takes constant of time 1  

因此答案应该是1000+2=1002

任何有正确解释的帮助将不胜感激..

请您参考如下方法:

如果我正确理解你的问题,我认为理解答案的关键是行 for i in range(1000): 正在做两个事情[< em>ed:请参阅下面的更新] 每次通过您忽略计数的循环:首先,它递增变量 i,其次,它根据最大值检查它( 1000) 以查看循环是否完成。所以每次通过循环都应该算作 3 次操作。

最后,即使跳过循环,仍然需要一个操作来决定执行此操作,即检查 x 与 0 在行中: while x > 0:.

这是最好情况下的计算方式:

def program1(x): 
    total = 0                  // counts as 1 
    for i in range(1000):      // counts as 2 * 1000 
        total += i             // counts as 1 * 1000 
 
    while x > 0:               // counts as 1 + N  (note: so when x <= 0, still counts as 1) 
        x -= 1 
        total += x 
 
    return total               // counts as 1 

...加起来是 3003。


更新:

鉴于提供给您的最坏答案是5n + 3003,我必须修改我的答案。

这意味着 while 循环中的 -= 和 += 操作必须算作两个独立的操作(递增或递减和赋值)。如果是这样,则 for 循环中的 += 操作也必须计为 2 个操作。如果是这样的话,使数字与提供的答案一致的唯一方法是会计是这样的:

def program1(x): 
    total = 0                  // counts as 1 
    for i in range(1000):      // counts as 1 * 1000 
        total += i             // counts as 2 * 1000 
 
    while x > 0:               // counts as 1 + N 
        x -= 1                 // counts as 2 * N 
        total += x             // counts as 2 * N 
 
    return total               // counts as 1 

我个人不同意将 += 和 -= 算作抽象意义上的两个东西,因为我知道它们可以作为一个操作来完成程序集(假设所有值都在寄存器中),但 在 Python 中 它们实际上是两个操作。 (有关更多信息,请参阅下面链接中的第 4 个答案。)

要接受此计算,您还必须接受 for i in range(1000): 行每次通过循环仅计为 一个 操作。在意识到上面我错了之后,我找到了这个答案 here这有助于理解这一点。基本上,这是因为上限以及循环的迭代元素本身是固定的。