PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 资结 计算复杂度的一题
楼主:
iloveconic
(乐陶陶)
2014-11-12 12:06:17
这是题目和解答
我先把通式写成log(n/2^0 + n/2^1 + n/2^2 + ......n/2^k)
= (logn-log2^0)+(logn-log2^1)+(logn-log2^2)+....(logn+log2^k)
问题1. 他这边直接跳到(K+1)logn-(1+2+...k)
是表示log2^1可以直接表示成1,log2^2=2这样吗?
问题2. 再来就是倒数第2行怎么变最后一行的...看不懂@@
还请各位替小弟解惑~谢谢了!
作者:
j897495
(咪咪)
2014-11-12 12:52:00
问题ㄧ只是把log n 全部加在一起而已问题二不就乘进去然后取BigO吗= ="
作者: herpinm (yuan)
2014-11-12 16:07:00
先回答二 因为复杂度的概念是建立在n够大的情况所以会取n多项式的最高次项 就是答案一的话 你的sigma公式代错了所以你的"通式"本身就不对..应该是log (n/2^0) +log (n/2^1)......+log (n/2^k)
作者:
j897495
(咪咪)
2014-11-12 16:16:00
通式有错吗0.0 我算起来是这样没错耶喔对 楼上好细心 给你推XD 我完全没注意到:(
继续阅读
Re: [理工] 工数问题 化简
Honor1984
[理工] 半导体物理
gauss760220
[理工] 工数问题 化简
codyman
[资工]离散 文法/语言
qoojordon
[理工] 极零点对消损失控制or观察性
asanick
[理工]售考古题 <高分子> <物化> 北科97.98.99.100.
mixchasm
[理工]售考古题 <应化> < 物化> 交大97.98.99
mixchasm
[理工] [计组]关于CLA的Add小疑惑
Moonshark
[资工] 代数系统 子群/order/循环群
qoojordon
[理工] OS
AgentSkye56
Links
booklink
Contact Us: admin [ a t ] ucptt.com