python - 如何使用 while + for 循环计算 Big O

Question

我得到了以下代码，并被告知 func 函数的 Big O 是 Big O (n^2)。我相信它是 Big O(n)，因为它应该是 Big O(n + n)，我错了吗？

what is Big O of following func?
nums = list(range(1, 11))
K = 4
def func(nums: list, K:int):         
    i, end = 0, len(nums)         
    res = []         
    x = []         
    while i < end:             
        res.append(nums[i:i+K])             
        i += K         
    for i in res:
        x += i[::-1]
    return x
func(nums, K)

标签： pythonpython-3.x

Answer 1

该函数将是 O(n)。第一个 while 循环的迭代次数少于n次数，因为它的上限是n( end)，并且每次迭代计数器的增量都超过 1。

for 循环遍历res，它是 的子集nums。由于它是一个子集，它不会迭代超过n多次，使其成为 O(n)。

O(n) + O(n) = O(n)，所以你的评估是正确的。