慕田峪9158850
2021-12-29 10:25:42
我得到了以下代碼,并被告知 func 函數(shù)的 Big O 是 Big O (n^2)。我相信它是大 O(n),因?yàn)樗鼞?yīng)該是大 O(n + n),我錯(cuò)了嗎?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)
2 回答

莫回?zé)o
TA貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊
該函數(shù)將是 O(n)。第一個(gè) while 循環(huán)的迭代次數(shù)少于n
次數(shù),因?yàn)樗纳舷奘?code>n( end
),并且每次迭代計(jì)數(shù)器都會(huì)增加 1 以上。
for 循環(huán)迭代res
,它是 的子集nums
。由于它是一個(gè)子集,它不會(huì)迭代n
多次,使其成為 O(n)。
O(n) + O(n) = O(n),所以你的評(píng)估是正確的。

函數(shù)式編程
TA貢獻(xiàn)1807條經(jīng)驗(yàn) 獲得超9個(gè)贊
事實(shí)上,這個(gè)函數(shù)的大 O 是 O(n)。假設(shè)代碼格式正確。
循環(huán)res
仍然具有線性運(yùn)行時(shí)間。不存在res
在第一個(gè)循環(huán)中添加足夠多的元素從而使第二個(gè)循環(huán)具有 O(n^2) 的大 O 的情況。
添加回答
舉報(bào)
0/150
提交
取消