关于 recurrence relation ( 已解决 )

MyChat 数位男女

»
程式设计

手机版

地图

繁体

您是第 4473 个阅读者

可列印版加为IE收藏收藏主题上一主题 | 下一主题

youchun

级别: 小人物

x26

▼

关于 recurrence relation ( 已解决 )

因为不知道要在何处询问，暂且在此发问，如版主觉得不适合请直接删除

---------------------------------------------------
求以下演 ..

访客只能看到部份内容，免费加入会员或由脸书 Google 可以看到全部内容

[ 此文章被youchun在2005-12-25 15:13重新编辑 ]


x0 [楼主] From：台湾中华电信 \| Posted：2005-12-21 17:38 \|

唐老鸭

级别: 初露锋芒

x230

▲ ▼

我不晓得可不可以提出来....
不过应该不行吧= =....
要解决上面的问题....
只要把原式子的O(n^2)做个假设变成bn^2....
再去作递回求解就好....
变成T(n) = aT(n/70) + bn^2
a=143640
b为某常数变数...
这样就可以了....

没东西可以抓
x1 [1 楼] From：美国 \| Posted：2005-12-23 06:40 \|

youchun

级别: 小人物

x26

▲ ▼

感谢解答

那可以转换成 T(n) = aT(n/b) + cn^2, a = 143640 , b = 70, T(1) = 1
假设 n = b^m 来作展开吗？
复制程式

=> T(n) = cn^2 + a{c( n/b )^2 + a{c( n/b^2 )^2 + ... a{c( n/b^m )^2 + aT(1)}}}  
             = (cn^2 ) * {级数( a/b^2 )^i, i = 0 to m } + a^(m+1)
又令 c(a/b^2) = c1 且 m = log (n) 
                                          b

=> T(n) = c1 * n^2 * (m+1) + a^(m+1)
             = c1 * log (n) * n^2 + a^(log (n) + 1)
                           b                          b
             = O(n^2 * log(n)) ?

可是 a^(log (n) + 1) 能被当成一般常数忽略吗?


x0 [2 楼] From：台湾中华电信 \| Posted：2005-12-24 23:00 \|

唐老鸭

级别: 初露锋芒

x230

▲ ▼

下面是引用youchun于2005-12-24 23:00发表的 :
感谢解答

那可以转换成 T(n) = aT(n/b) + cn^2, a = 143640 , b = 70, T(1) = 1
假设 n = b^m 来作展开吗？
[code].......

这种题目是有公式的....
假设T(n)=cT(n/d)+bn^k
设n=d^i
推到最后....
前面的常数像把他消去...
会变成只有bn^k(1+c/d^k+c^2/d^2k+........)<=共i项
这样会有三种情况发生....

if(c>d^k)=>O(n^(logdC)

if(c<d^k)=>O(n^k)

if(c=d^k)=>O(n^klogn)

你的题目是属于第一种....
所以是O(n^log70143640)
你可以自己在推看看

....

[ 此文章被唐老鸭在2005-12-25 03:28重新编辑 ]

没东西可以抓
x2 [3 楼] From：美国 \| Posted：2005-12-25 03:23 \|

youchun

级别: 小人物

x26

▲

原来可以直接代入公式
谢谢不吝花时间指教！


x0 [4 楼] From：台湾中华电信 \| Posted：2005-12-25 15:12 \|



MyChat 数位男女 » 程式设计

Powered by PHPWind v1.3.6 Copyright © 2003-04 PHPWind	Processed in 0.017075 second(s),query:16 Gzip disabled 本站由瀛睿律师事务所担任常年法律顾问 \| 免责声明 \| 本网站已依台湾网站内容分级规定处理 \| 连络我们 \| 访客留言