討論區快速選單
知識庫快速選單
討論區最近新進100則主題 CSSLP認證,將資安落實在軟體開發中
[ 回上頁 ] [ 討論區發言規則 ]
遞迴方程式的時間複雜度計算
更改我的閱讀文章字型大小
作者 : justdaniel(水餃)
[ 貼文 5 | 人氣 2435 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/6/9 上午 11:31:32
分析一個遞迴程式的時間複雜度,寫為式子:
W(n) = 2W(n/2) + n -1 ;當n>1且n為2的乘冪時
W(1) = 0

如何求出一般解呢?????

我算出來的答案好像怪怪的
T(n) = 2(n - 1) - lgn #

抱歉...暫時沒多餘的點數回饋!!!
作者 : frankfkc(長長) 程式設計甘苦談卓越專家C++優秀好手貼文超過1000則人氣指數超過50000點
[ 貼文 1148 | 人氣 62194 | 評價 4640 | 評價/貼文 4.04 | 送出評價 108 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/9/12 下午 07:01:09
在此,log都是以2為底,因為是n/2。^表示冪次方。

令 k = log(n),n = 2^k。
所以
W(2^k) = 2W(2^k/2) + 2^k - 1


Y(k) = W(n)
可得

Y(k) = 2*Y(k-1) + 2^k - 1
Y(1) = 1 <-- 為什麼?

這樣就變成線性了,而sum(2^i) from 0~k-1 = 2^k - 1
得到,2^k + 2^(k+1) - 3 - k - 1
整理一下得:
3n - log(n) - 4

跟你的式子蠻像的。搞不好我過程哪兒出錯,使得係數常數不太一樣,請再檢查一下。

>分析一個遞迴程式的時間複雜度,寫為式子:
>W(n) = 2W(n/2) + n -1 ;當n>1且n為2的乘冪時
>W(1) = 0
>
>如何求出一般解呢?????
>
>我算出來的答案好像怪怪的
>T(n) = 2(n - 1) - lgn #
>
>抱歉...暫時沒多餘的點數回饋!!!
作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/9/12 下午 09:34:40
參考:

http://www.programmer-club.com/pc2020v5/Forum/ShowSameTitleN.asp?URL=N&board_pc2020=general&id=2765

T(n) = aT(n/c) + bn

T(n) = O(n), if a < c
T(n) = O(nlogn), if a = c
T(n) = O(n^logca), if a > c

你列的

W(n) = 2W(n/2) + n-1, 最後一定是O(nlogn). 解開方式如下:

W(n) = 2W(n/2) + n-1 =
2(2W(n/4) + n/2 - 1) + n-1
= 4W(n/4) + (n-2) + (n-1)
= 4(2(W(n/8) + n/4 - 1) + (n-2) + (n-1)
= 8W(n/8) + (n-4) + (n-2) + (n-1)

看出什麼規則了嗎? 當n=2^k時, 變成

n*W(1) + k*n - (1+2+4+...2^(k-1))

令W(1) = 常數c, 則全式可化成:

n*logn + c*n - (n - 1)
作者 : frankfkc(長長) 程式設計甘苦談卓越專家C++優秀好手貼文超過1000則人氣指數超過50000點
[ 貼文 1148 | 人氣 62194 | 評價 4640 | 評價/貼文 4.04 | 送出評價 108 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/9/13 下午 12:43:44
謝謝!
看來要好好複習了。

>參考:
>
>http://www.programmer-club.com/pc2020v5/Forum/ShowSameTitleN.asp?URL=N&board_pc2020=general&id=2765
>
>T(n) = aT(n/c) + bn
>
>T(n) = O(n), if a < c
>T(n) = O(nlogn), if a = c
>T(n) = O(n^logca), if a > c
>
>你列的
>
>W(n) = 2W(n/2) + n-1, 最後一定是O(nlogn). 解開方式如下:
>
>W(n) = 2W(n/2) + n-1 =
>2(2W(n/4) + n/2 - 1) + n-1
>= 4W(n/4) + (n-2) + (n-1)
>= 4(2(W(n/8) + n/4 - 1) + (n-2) + (n-1)
>= 8W(n/8) + (n-4) + (n-2) + (n-1)
>
>看出什麼規則了嗎? 當n=2^k時, 變成
>
>n*W(1) + k*n - (1+2+4+...2^(k-1))
>
>令W(1) = 常數c, 則全式可化成:
>
>n*logn + c*n - (n - 1)
>
作者 : frankfkc(長長) 程式設計甘苦談卓越專家C++優秀好手貼文超過1000則人氣指數超過50000點
[ 貼文 1148 | 人氣 62194 | 評價 4640 | 評價/貼文 4.04 | 送出評價 108 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/9/13 下午 12:46:15

>在此,log都是以2為底,因為是n/2。^表示冪次方。
>
>令 k = log(n),n = 2^k。
>所以
>W(2^k) = 2W(2^k/2) + 2^k - 1
>
>令
>Y(k) = W(n)
>可得
>
>Y(k) = 2*Y(k-1) + 2^k - 1
>Y(1) = 1 <-- 為什麼?
>
>這樣就變成線性了,而sum(2^i) from 0~k-1 = 2^k - 1
>得到,2^k + 2^(k+1) - 3 - k - 1

應該是得到 k*2^k + 2^(k+1) - 3 - k - 1

>整理一下得:
>3n - log(n) - 4
>
>跟你的式子蠻像的。搞不好我過程哪兒出錯,使得係數常數不太一樣,請再檢查一下。
>
作者 : justdaniel(水餃)
[ 貼文 5 | 人氣 2435 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/9/14 上午 10:08:23
n*W(1) + k*n - (1+2+4+...2^(k-1))
>
>令W(1) = 常數c, 則全式可化成:
>
>n*logn + c*n - (n - 1)

抱歉....你最後(n-1)怎麼導出來的

書上的算法:
T(2^K)=2T(2^K/2) + 2^K -1
= 2T(2^(k-1)0 + 2^k -1
令tk = T(2^k)
代入得
tk= 2tk-1 +2^k -1

書上球出的一般解為
tk =c1 + 2^k*c2 + c3*k2^k
我求出來跟書上不一樣
所以最後帶回原遞迴方程式的一般解就有問題
謝謝上面兩位大大....不吝和我討論




作者 : chiuinan2(青衫)討論區板主 Visual C++ .NET卓越專家VC++一代宗師Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手上班族的哈拉園地優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 貼文 3732 | 人氣 170106 | 評價 34520 | 評價/貼文 9.25 | 送出評價 125 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2006/9/14 下午 06:51:03
1+2+4+...+2^(k-1) = 2^k - 1 = n - 1
作者 : bjk(Up2u) 貼文超過1000則人氣指數超過50000點
[ 貼文 1047 | 人氣 64249 | 評價 730 | 評價/貼文 0.7 | 送出評價 196 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/4 上午 10:14:29
99 成大資工 time

t(n) = t(n-2) + 2lgn

網路上解答給 theta(nlgn)

請問是

代代代代..

2lgn + 2lg(n-2) + 2lg(n-4) + ... + 2 <= nlgn

是這樣嗎??
作者 : ozzy123(ozzy) 資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4464 | 人氣 37262 | 評價 10860 | 評價/貼文 2.43 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/4 上午 10:49:40

>99 成大資工 time
>
>t(n) = t(n-2) + 2lgn
>
>網路上解答給 theta(nlgn)
>
>請問是
>
>代代代代..
>
>2lgn + 2lg(n-2) + 2lg(n-4) + ... + 2 <= nlgn
>
>是這樣嗎??

this is a general recursive expression. using a little skill to solve it.
t(n) = t(n-2) + 2lgn
t(n-2) = t(n-4) + 2lg(n-2)
t(n-4) = t(n-6) + 2lg(n-4)
...
t(n-k) = t(n-k-2) + 2lg(n-k)
...
t(2) = t(0) + 2lg(2)
+______________________
t(n) = 2lg(n)+2lg(n-2)+2lg(n-4)+...+2lg(2) = 2 (lg(n)+....+lg(2))+t(0) , t(0) is base condition and t(0) = k , k is a constant
 

作者 : ozzy123(ozzy) 資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4464 | 人氣 37262 | 評價 10860 | 評價/貼文 2.43 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/4 上午 11:00:32
t(n) = 2lg(n)+2lg(n-2)+2lg(n-4)+...+2lg(2) = 2 (lg(n)+....+lg(2))+t(0)

when you get the above expression , we may evaluate each item.
 
2lg(n) < n lg(n) , when n > 2
2lg(n-2) < n-2 lg(n), when n > 4
2lg(n-4) < n-4 lg(n) , when n > 6
.....

so the above expression can be expressed as below.
q*nlg(n) < 2 (lg(n)+....+lg(2)) < n (lg(n)+....+lg(2)) < p*nlg(n) , p,q are constants; so its complexity is θ (nlg(n))
作者 : bjk(Up2u) 貼文超過1000則人氣指數超過50000點
[ 貼文 1047 | 人氣 64249 | 評價 730 | 評價/貼文 0.7 | 送出評價 196 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/4 下午 07:28:09
感恩~~~
 板主 : simula , 小朱
 > 資訊工程與科學 - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - 資訊工程與科學 - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
資訊工程與科學
1 長長 240 
2 HKLN.net 240 
3 青衫 210 
4 速定 150 
5 simula 150 
6 aming 110 
7 arios 90 
8 80 
9 DEMO999 70 
10 Raymond 60 
資訊工程與科學
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2018 程式設計俱樂部 http://www.programmer-club.com.tw/
0.0625