[理工] 資結 複雜度
作者: gary19941208 2016-08-14 18:26:03
請問第一小題怎麼算，答案是O(2^n)
我列的時間方程式是T(n)=T(n-1)+T(n-2)+3，3是兩個乘和一個加
不知道有沒有列錯，謝謝
作者: A4P8T6X9 (殘廢的名偵探) 2016-08-14 22:57:00
沒列錯，用夾的看看？上限是 T(n)=2T(n-1)+3下限是T(n)=2T(n-2)+3,會在這兩個中間，這兩個都是2^n吧
作者: yorunohoshi (夜の星) 2016-08-14 23:58:00
" target="_blank" rel="nofollow"> 用遞迴樹加猜測可以得出O(2^n) 但是用離散的做法應該才叫最tight的
" target="_blank" rel="nofollow"> 離散算出來的bounded跟原本的費氏數列一樣就是黃金比例的n次方所以我覺得答案有瑕疵0.0作者: gary19941208 2016-08-15 00:20:00
謝謝樓上兩位！