第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

Python - 如何計算這個遞歸函數(shù)的時間復(fù)雜度?

Python - 如何計算這個遞歸函數(shù)的時間復(fù)雜度?

斯蒂芬大帝 2023-09-12 20:10:25
我想以盡可能多的方式解決塔漏斗問題,并計算每種方式的時間復(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:]的副本??紤]到這一點,總時間是。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] = 1n的長度arr。

查看完整回答
反對 回復(fù) 2023-09-12
  • 1 回答
  • 0 關(guān)注
  • 96 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學習伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號