如何使用 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 = 4def 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 xfunc(nums, K)

Answer 1

该函数将是 O(n)。第一个 while 循环的迭代次数少于n次数，因为它的上限是n( 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 的情况。