T(n) = n + (4/n)( T(1) + T(2) +...+ T(n-1)) 求时间复杂度 我把两边乘n 然後再代n=n+1 得两个式子 然後相减得 (n+1)T(n+1) = 2n+1 + 4T(n) + n T(n) 我在想在算下去就放榜了 於是.. 两边同除(n+1)(n+4)得 T(n+1)/(n+4) = 2n+1/(n+1)(n+4) + T(n)/(n+1) 此时假如当n很大时 或者是说他的复杂度小於下列式子 得T(n+1)/(n+1) = 1/n + T(n)/n 令An = T(n)/n 得A(n+1) = 1/n + An 解得An = O(log n) 所以T(n)=O(n log n) 不知道可不不可这样证 可以的话 快速排序的平均case复杂度也可以这样算... 请高手指导! --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.127.208.96