[理工] 資結時間複雜度 brad84622 PTT批踢踢實業坊

作者: brad84622 (brad84622) 2016-08-15 03:06:52

各位早
http://i.imgur.com/p2mnjK9.jpg
http://i.imgur.com/Ao06nQL.jpg
想請問為什麼是2T而不是4T呢

作者: gary19941208 2016-08-15 07:40:00

四倍關係是程式跑出來的"結果"，但是題目問的是"時間"的關係，執行n的時候是執行了兩次n-1的時間，然後乘2再加1，所以是T(n)=2T(n-1)+常數，常數是乘法和加法所需的時間

作者: aa06697 (todo se andarà) 2016-08-15 11:47:00

程式碼的2*T(n/2)的2* 是算在常數時間裡面唷若改成return 4*T(n/2) 就會變成 T(n/2) + constant

作者: brad84622 (brad84622) 2016-08-15 15:14:00

懂了！！感謝樓上2位

繼續閱讀