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

Question

这是 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

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

Answer 1

如果我正确理解你的问题，我认为理解答案的关键是行 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这有助于理解这一点。基本上，这是因为上限以及循环的迭代元素本身是固定的。