我想以盡可能多的方式解決塔漏斗問題,并計算每種方式的時間復(fù)雜度(僅供自我練習)。解決方案之一是這樣的: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我知道遞歸時間復(fù)雜度計算的一般思想,但我無法分析注釋行(在 for 循環(huán)內(nèi))。T(n) = C + T(that line)通常我用通用表達式(例如 T(nk))計算時間復(fù)雜度并減少它,直到達到基本情況并可以用 n 表示 k,但是 for 循環(huán)的時間復(fù)雜度是多少?
1 回答

莫回無
TA貢獻1865條經(jīng)驗 獲得超7個贊
該循環(huán)的復(fù)雜性for
可能高達 ,O(n^2)
因為循環(huán)的每次迭代(最多 n 次迭代)都會執(zhí)行一個切片,該切片返回沒有第一個元素arr[i:]
的副本??紤]到這一點,總時間是。arr
i
O(n)
O(n^3)
提到的上限是嚴格的。
示例: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
。
添加回答
舉報
0/150
提交
取消