[理工] 资结时间复杂度 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位

继续阅读