与关于Python函数的最佳/最坏情况时间的答案相混淆 [英] Confused with answer about best/worst case time for Python function

问题描述

这是edx的课程使用Python进行计算机科学和编程简介"中的一个简短问题.

This is a short problem from edx's course Introduction to Computer Science and Programming using 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的大小

Question : What is the number of steps it will take to run Program 1 in the best case? Express your answer in terms of n, the size of the input x

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

Answer : Best case : 3003 and Worst Case : 5n+3003

我对答案3003感到困惑，因为根据我的观点，问题的最佳情况是如果x = -1且执行的其他语句具有固定的时间量，因此 声明

I am confused with the answer 3003 because according to me the problem's best case would be if x =-1 and other statements execute which have a constant amount of time .hence statement

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

Hence the answer should be 1000+2=1002

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

Any help with proper explanation will be highly appreciated ..

推荐答案

如果我正确理解了您的问题，我认为理解答案的关键是for i in range(1000):行正在执行两项 [ ed:请参阅下面的更新]每次通过您忽略的循环进行计数:首先，它将变量i递增，其次，将其与最大值(1000)进行比较以达到查看循环是否完成.因此，每次通过循环都应算作3次操作.

If I understand your question correctly, I think the key to understanding the answer is that the line for i in range(1000): is doing two things [ed: see update below] each time through the loop that you neglected to count: first, it is incrementing the variable i and second, it is checking it against the maximum value (1000) to see if the loop is finished. So each pass through the loop should count as 3 operations.

最后，即使跳过循环，仍然需要执行一个操作来决定执行此操作，即在while x > 0:行中将x与0进行比较.

Finally, even if the loop is skipped, it still takes one operation to decide to do this, that is to check x against 0 in the line: while x > 0:.

这是在最佳情况下的处理方式:

This is how it would be accounted in the best case:

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.

...which adds up to 3003.

更新:

鉴于提供给您的最糟糕的案例答案是5n + 3003，我必须修改答案.

Given that the worst case answer provided to you is 5n + 3003, I must modify my answer.

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

That means that the -= and += operations within the while loop must be being counted as two separate operations (the increment or decrement and the assignment). If so, then the += operation within the for loop must also count as 2 operations. And if that is the case, the only way to make the numbers agree with the provided answer is if the accounting is like this:

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个答案.)

I personally disagree with counting the += and -= as two things, in the abstract sense, because I know that they can be done as a single operation in assembly (assuming all values are in registers), but in Python they are actually two operations. (See the 4th answer in the link below for more on this.)

要接受这种核算，您还必须接受每次循环时，行for i in range(1000):仅算作 one 操作.在意识到我在上面是错的之后，我找到了这个答案

To accept this accounting, you must also accept that the line for i in range(1000): only counts as one operation each time through the loop. Upon realizing that I was wrong above, I found this answer here which helps with understanding that. Basically, this is because the upper bound as well as the iterated elements themselves of the loop are fixed.

这篇关于与关于Python函数的最佳/最坏情况时间的答案相混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！