作者polomoss (小泽)
看板Grad-ProbAsk
标题[理工] [DS]-时间复杂度
时间Sun Jan 10 15:56:09 2010
总共五小题，想看我有没有算错
一个配分2分，
题目有一句叙述:Assume that T(n) is constant for sufficiently small n
a)T(n) = 3T(n/2) + nlogn
→直接带master，算出θ(n^log 3)
2
b)T(n) = 5T(n/5) + n/logn
→叠代法，算出θ(nloglogn)
c)T(n) = T(3n/4) + T(n/5) + n
→画TREE，得θ(n)
d)T(n) = 3T(n/3 + 5) + n/2
→这题不会算，我是省略+5，可是题目给足够小n
是否代表不能省略? 省略後得θ(nlogn)
e)T(n) = n^1/2 T(n^1/2) + n^1/2
→这题完全没头绪@@
谢谢
--
学长学长!那边有飙车族 学长学长!那边刚好像有女生 学长学长~那边有人红灯右转
砍人 被压上车 ψQSWEET
鸽 ◥ 鸽 ◥ 鸽 ◥ 鸽 ◥ 鸽 ◥他妈的◤ 鸽
◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 喔~~ ◤︶ ︶ ◤◎ ◎ 拦下来呀!⊙ ⊙◥
◥ ◤ ◥ █◤ ◥ ◤ ◥ 3◤╯ξ
◥ ◤没王法了◥皿 ◤
◥ ◥◥ (哈欠)◤ ◥◤ ◥ ◥◥ (烟~) ◤ ◥ ◤￣ ◥ ◥◥是不是?!(
◥ ◤ ◤)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.14.2
1F：推 FRAXIS:(b)是不能代Master Theorem的 (e)两边同除n再用代换法 01/10 16:00
2F：→ polomoss:b)带完左边n比右边大~不能这样比吗? 01/10 17:59
自问自答，用叠代法算出 nloglogn，不过我算好久，才2分@@
※ 编辑: polomoss 来自: 122.116.14.2 (01/10 19:20)
3F：→ polomoss:感觉n/lgn就会比n小，但是居然等於nlglgn，真奇妙 01/10 19:43