作者swon ()
看板Grad-ProbAsk
标题Re: [理工] [DS]-时间复杂度
时间Fri Jan 8 02:13:35 2010
※ 引述《doom8199 (～口卡口卡 修～)》之铭言：
: ※ 引述《yesa315 (XD)》之铭言：
: : T(n) = 3T(n/4) + nlog n 使用Θ表示
: : 2
: : 这有比较快速的算法吗? 例如代换法??
: : 用暴力法求解我也求不太出来 有请高手给个方向
: : 谢谢!
: ---
: 令 T(n) + f(n) = 3[T(n/4) + f(n/4)]
: with f(n) = a*nlogn + b*n + c*logn + d
: → T(n) = 3T(n/4) + 3f(n/4) - f(n)
: = 3T(n/4) + (-a/4)nlogn - (3a/2 + b/4)n + 2c*logn + (2d-6c)
: 与原式比较系数後可得:
: ┌ (-a/4) = 1 ┌ a = -4
: │ 3a/2 + b/4 = 0 → │ b = 24
: │ 2c = 0 │ c = 0
: └ 2d-6c = 0 └ d = 0
: 所以 f(n) = -4nlogn + 24n ____(1)
: 因此 T(n) + f(n) = 3[T(n/4) + f(n/4)]
: = 3^[log_4 (n)] * [T(1) + f(1)]
: = n^(log√3) * [T(1) + f(1)]
: → T(n) = T(1)*n^(log√3) + f(1)*n^(log√3) - f(n)
: = T(1)*n^(log√3) + 24*n^(log√3) + 4nlogn - 24n
: or T(n) = Θ{ nlogn }
[挖以前的文章]
如果要纯解题的话，你可以套下面这个方法，当然也是从 Master 定理整理出来的：
要诀就是在比大小就对了…大的就赢了 >////<
给题目： T(n) = aT(n/b) + f(n)
log a
b
Step 1：计算 n
Step 2：比较一下 Step 1 与 f(n) 值谁的复杂度大
则 T(n) = Θ(复杂度大的那个)
Step 3：Step 1 的值与 f(n) 的复杂度相同的话
则 T(n) = Θ( f(n) * lgn)
(多乘一个 lgn)
Step 4：处理一下例外情形，就是当 f(n) 比 Step 1 的值少 lgn 倍时。
不能使用 Master Theorem。
也就是说看到 f(n) 有 lgn 时就要小心一下就对了。
For Example
---------------------------------------------------------------------
T(n) = 3T(n/4) + nlog n
2
log 3
4
n < n log n
2
所以 T(n) = Θ(大的那个) = Θ(nlog n)
2
---------------------------------------------------------------------
T(n)=T(n/2)+O(1)
log 1
2
n = n^0 = 1 跟 f(n) 一样
所以 T(n) = O(1) * lgn = Θ(lgn)
---------------------------------------------------------------------
T(n)=4T(n/2)+n
log 4
2
n = n^2 > n = f(n)
所以 T(n) = Θ(大的那个) = Θ(n^2)
---------------------------------------------------------------------
T(n) = 3T(n/4) + n
log 3
4
n < n = f(n)
所以 T(n) = Θ(大的那个) = Θ(n)
---------------------------------------------------------------------
T(n) = 2T(n/2) + n / lg n
log 2
2
n = n > n / lgn = f(n)
这时发现 f(n) 少了 lgn 倍，所以就不能套 Master Theorem了...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.136.5.68
1F：推 FRAXIS:最後一个可以用Master Theorem.. 01/08 09:39
感谢，修正了 XD
2F：推 yesa315:f(n) 有log 不是要用extend master 吗 01/08 13:24
3F：→ yesa315:为什麽你用普通的Master Theorem就可以了!? 01/08 13:25
4F：→ yesa315:n^log 4 3 =n^0=1不是吗 要套用extend master也不行 01/08 13:26
5F：→ yesa315:我的问题点就是在这里 01/08 13:26
6F：推 FRAXIS:n^(log 4 3)比nlg n小.. 01/08 17:32
7F：推 yesa315:我了解了 观念上得错误 谢谢Y 01/08 21:37
※ 编辑: swon 来自: 220.136.9.218 (01/09 02:09)