我想以盡可能多的方式解決塔漏斗問題，并計算每種方式的時間復雜度（僅供自我練習）。解決方案之一是這樣的：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我知道遞歸時間復雜度計算的一般思想，但我無法分析注釋行（在 for 循環內）。T(n) = C + T(that line)通常我用通用表達式（例如 T(nk)）計算時間復雜度并減少它，直到達到基本情況并可以用 n 表示 k，但是 for 循環的時間復雜度是多少？
1 回答
莫回無
TA貢獻1865條經驗 獲得超7個贊
該循環的復雜性for可能高達 ，O(n^2)因為循環的每次迭代（最多 n 次迭代）都會執行一個切片，該切片返回沒有第一個元素arr[i:]的副本。考慮到這一點，總時間是。arriO(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
提交
取消