關於 recurrence relation ( 已解決 )

MyChat 數位男女

»
程式設計

手機版

地圖

簡體

您是第 4481 個閱讀者

可列印版加為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.073681 second(s),query:16 Gzip disabled 本站由瀛睿律師事務所擔任常年法律顧問 \| 免責聲明 \| 本網站已依台灣網站內容分級規定處理 \| 連絡我們 \| 訪客留言