我想以盡可能多的方式解決塔漏斗問題，并計(jì)算每種方式的時(shí)間復(fù)雜度（僅供自我練習(xí)）。解決方案之一是這樣的：def is_hopable(arr): if len(arr) < 1 or arr[0] == 0: return False if arr[0] >= len(arr): return True res = False for i in range(1,arr[0]+1): res = res or is_hopable(arr[i:]) # This line return res我知道遞歸時(shí)間復(fù)雜度計(jì)算的一般思想，但我無法分析注釋行（在 for 循環(huán)內(nèi)）。T(n) = C + T(that line)通常我用通用表達(dá)式（例如 T(nk)）計(jì)算時(shí)間復(fù)雜度并減少它，直到達(dá)到基本情況并可以用 n 表示 k，但是 for 循環(huán)的時(shí)間復(fù)雜度是多少？
1 回答
莫回?zé)o
TA貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊
該循環(huán)的復(fù)雜性for可能高達(dá) ，O(n^2)因?yàn)檠h(huán)的每次迭代（最多 n 次迭代）都會執(zhí)行一個(gè)切片，該切片返回沒有第一個(gè)元素arr[i:]的副本。考慮到這一點(diǎn)，總時(shí)間是。arriO(n)O(n^3)
提到的上限是嚴(yán)格的。
示例：arr = [n-1, n-2, n-3, ..., 1, 1]
替代形式：arr[i] = n - 1 - i對于所有i,?0 <= i < n - 1，其中arr[n-1] = 1是n的長度arr。
添加回答
舉報(bào)
0/150
提交
取消