PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 算法复杂度
楼主:
gz9548171
(疯狂阿笨狗)
2019-03-26 15:45:13
https://i.imgur.com/LuBRwcW.jpg
想问这两题要怎么证,我的想法是用
master theorem推第一题,但是卡在
Case3的条件二,他的f(n)是在theta 里,
我不确定能不能直接固定theta里c1,c2
来做推导,麻烦大家了
作者:
wilson50101
(我觉得我还不错啊)
2019-03-26 20:31:00
感觉两个都是true把f(n)带进去解mt就好了吧两边差距差蛮多的
作者:
kyrie77
(NTU KI)
2019-03-27 01:01:00
和麟的作业题目XD应该第一题True,第二题False
作者:
wilson50101
(我觉得我还不错啊)
2019-03-27 18:09:00
楼上可以说为什么第二题false吗?没feel
作者:
kyrie77
(NTU KI)
2019-03-27 19:40:00
因为如果要用master theorem还有一个条件是af(n/b)<=cf(n), for some c<1,∀n,这样才能适用case3
作者:
wilson50101
(我觉得我还不错啊)
2019-03-27 23:15:00
如果f(n)假设成n平方 a=2 b=2的话不就是1/2n平方<=cn平方c就可以取1/2 for all n这样就可以用case 3了不是吗?还是我这做法哪里有问题?
作者:
kyrie77
(NTU KI)
2019-04-08 20:21:00
噢噢,问题应该就是出在这题不能一开始就假设f(n)是n^2之类的函数,因为题目是给你一个集合,而如果要套用master theorem的话要for all n都符合下面那个式子,因此可以造出非常人工的函数使得每2次迭代都让f(n)变成不一样的函数(比如说n^2和n^4)
继续阅读
[自控] 最大超越量
m24825147
[理工] 计组pipeline
tank123zzz
[理工] 算法复杂度
gz9548171
[理工] 计组第二章
tank123zzz
[理工]线代_p5-15_范例2
fmtshk
[理工] 线代课本(上)p.3-101 第2题
boxunlu
[理工] 计组第二章
tank123zzz
[理工] 线代_4-128范例6
fmtshk
[理工] 线性代数 3-52 向量空间 请教
mistel
[理工] 108台大土木工数请教
ucdrtz
Links
booklink
Contact Us: admin [ a t ] ucptt.com