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)

Answer 1

该函数的复杂度为 O(n)。第一个 while 循环的迭代次数少于 n 次，因为其上限为 n (end)，并且计数器每次迭代都会增加超过 1 。

for 循环迭代 res，它是 nums 的子集。由于它是一个子集，因此它不会迭代超过 n 次，从而使其复杂度为 O(n)。

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