2

我有以下代码，我必须计算“Big-O”：

def f3(lst):
    i = len(lst)
    while i>0:
        for j in range(i):
            for k in range(j, 10**5):
                print(i)
        i -= 2

假设lst是一个长度为 n 的列表，操作 take O(1)，这就是我得出的结论：第二个for是一个常数，因为它每次迭代到 10**5 ，所以我们可以“忽略”它（就像O(1)）。

while 运行 n 次，第一个 for 循环运行 n/2 次，所以一般来说复杂度应该是O(n^2).

那是对的吗？我的朋友认为是O(n^4)。

谢谢。

4

2 回答 2

0

答案不是 O(n^3) 吗？因为内部循环仍然需要运行时间来检查 j 从某个地方开始的线性函数的条件，因此 j 乘 i 乘 n 的总和是 O(n^3) ？

于 2013-04-11T19:10:03.613 回答
0

您已正确确定 while 循环是迭代n/2次数。其中包含的外部循环在后续迭代for中执行j = 1, 2, ... i，其中i设置为len(lst), len(lst) - 2, ...。所以，外循环是针对, , ...,执行的。总的来说，这是外循环的迭代。虽然内部循环的执行次数不是恒定的，但它最多迭代，这是恒定的。因此，是此函数运行时的正确上限。1whileforj = 1, 2, ..., len(lst)j = 1, 2, ..., len(lst) - 2j = 1O(n^2)forfor10**5O(n^2)

这里有一个稍微不同的解释。我希望您同意以下代码在计算时间方面与您的代码等效：

def f3_simple(n):
    i = n                         
    condition = i>0               
    while condition:              
        r1 = range(i)             
        for j in r1:              
            r2 = range(j, 10**5)  
            for k in r2:          
                print(i)          
        i -= 2                    
        condition = i>0

这是相同的代码，带有注释：

def f3_simple(n):
    i = n                         # "length": O(1)
    condition = i>0               # comparison: O(1)
    while condition:              # executed O(n) times per function call
        r1 = range(i)               # range(i): O(i)
        for j in r1:                # executed O(n) times per WHILE iteration
            r2 = range(j, 10**5)      # range(j, 10**5): O(10**5 - j) = O(1)
            for k in r2:              # executed O(1) times per OUTER FOR iteration
                print(i)                # print: O(1)
        i -= 2                      # decrement: O(1)
        condition = i>0             # comparison: O(1)

因此，总运行时间确实是O(n^2).

于 2013-04-10T18:45:55.473 回答