查找运行时间（函数的操作次数）并计算Big O

Question

对于下面给出的python函数，我必须找到操作数和大O。

def no_odd_number(list_nums):
    i = 0
    while i < len(list_nums):
        num = list_nums[i]
        if num % 2 != 0:
            return False
        i += 1
    return True

根据我的计算，操作数是 4 + 3n 但我不确定，因为我不知道如何处理 if...else 语句。

我还可以选择正确的 Big O，根据我的计算，我认为它应该是 d. O(n)，但我不确定。请帮忙！

a. O(n^2)

b. O(1)

c. O(log n)

d. O(n)

e. None of these

Answer 1

大 O 表示法通常考虑最坏的情况。您拥有的功能非常简单，但早期的 return 似乎使事情复杂化。但是，由于我们关心最坏的情况，您可以忽略 if 块。最坏的情况是你没有早 return。这将是一个类似于 [2,4,6,8] 的列表，它将运行循环四次。

现在，考虑到上述内容，看看 while 循环中的内容。 list_nums 有多大并不重要：在循环中，您只需递增 i 并在列表中查找内容。无论 list_nums 有多大，这两个都是相同的恒定时间操作。

你做这个循环的次数就是list_nums的长度。这意味着随着 list_nums 的增长，操作数量以相同的速度增长。这使得这个 O(n) 如您所料。

查找运行时间（函数的操作次数）并计算Big O

Find runtime (number of operations of function) and calculate Big O

python

time-complexity