※ 引述《FRAXIS (喔喔)》之铭言： : ※ 引述《NOtWorThy ()》之铭言： : : 问题1 : : 为什麽形如 : : T(n) = aT(n/b) + n^logab * (logn)^k , k >= 1 : : 不能直接用 Master thm : : 这不是可以用 case 1 吗? : : ex. : : T(n) = 2T(n/2) + nlogn : : sol: : : n^log2 2 = n = O(nlogn) : : by case 1 不是可以解吗?? : Case 1的条件 : f(n) = O(n^(log_a b - e)) for some constant e > 0 : f(n) = nlogn != O(n^(log_2 2)) = O(n) 所以不适用 Case 3的条件其中有一个是 f(n) = Ω(n^(log_b a + e)) for some e > 0 题目中 f(n) = n log n 和 n^(log_b a + e) = n^(1+e)相比 又 log n = o(n^e) != Ω(n^e) for all e > 0，所以条件永远不会成立 另外一个问题，你的f(n)和T(n)的定义好像没搞清楚.. Master Theorem可以套用的形式是 T(n) = aT(n/b) + f(n) 所以f(n)才会是n^3 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.119.162.50 ※ 编辑: FRAXIS 来自: 140.119.162.50 (11/17 21:28)