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

Question

我得到了以下代码，并被告知 func 函数的 Big O 是 Big O (n^2)。我相信它是大 O(n)，因为它应该是大 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(&nbsp;end)，并且每次迭代计数器都会增加 1 以上。for 循环迭代res，它是 的子集nums。由于它是一个子集，它不会迭代n多次，使其成为 O(n)。O(n) + O(n) = O(n)，所以你的评估是正确的。

Answer 2

事实上，这个函数的大 O 是 O(n)。假设代码格式正确。循环res仍然具有线性运行时间。不存在res在第一个循环中添加足够多的元素从而使第二个循环具有 O(n^2) 的大 O 的情况。