[理工] DS時間複雜度

看板Grad-ProbAsk作者 (汪汪)時間12年前 (2012/02/02 00:29), 編輯推噓6(6推 0噓 11→)
留言17則, 9人參與, 最新討論串1/1
小弟不才,想請問一題,及一個觀念 (1)這題是要算tight asymptotic upper bounds for T(n) T(n)= 4T(n/4) + n/lgn ANS為O(n*lglgn) (交大97DS) ================================================ (2)第2個我想問一個觀念,有關時間複雜度的. (a) T(n)=2T(n/2)+1 T(n)=T(n/2)+T(n/2)+1 這2個時間複雜度是不是 不一樣 (b) T(n)=2T(n/2)+1 T(n)=2T(n/2)+n 這2個時間複雜度是不是 會一樣 先謝謝各位了 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.117.87.164
推
02/02 00:38, , 1F
(2)(a) 當然一樣啊 (b)上面是 O(n) 下面是O(nlogn)
02/02 00:38, 1F
→
02/02 00:42, , 2F
我的想法是(a)上面的只遞迴一次*2,下面的是遞迴2次,所以
02/02 00:42, 2F
→
02/02 00:43, , 3F
下面的時間復雜度會較大????
02/02 00:43, 3F
→
02/02 00:45, , 4F
(b)我是想說只跟他的遞迴次數有關,後面的數字不影響??
02/02 00:45, 4F
推
02/02 01:10, , 5F
(1) n = 4^k 代入
02/02 01:10, 5F
推
02/02 01:10, , 6F
(1)畫遞迴樹 (2)a.一樣 b. O(logn) 跟 O(nlogn)
02/02 01:10, 6F
→
02/02 01:11, , 7F
(2)用master method
02/02 01:11, 7F
→
02/02 02:04, , 8F
炯了沒想好 是(b)上面是O(logn)沒錯
02/02 02:04, 8F
→
02/02 09:56, , 9F
疑,我下面那題(a)用master theorem上面是O(n)
02/02 09:56, 9F
→
02/02 09:57, , 10F
下面用遞迴樹是O(nlogn)不一樣阿
02/02 09:57, 10F
推
02/02 13:00, , 11F
仔細考慮了 (a)不一樣沒錯 (b)上面是 O(n)下面是O(nlogn)
02/02 13:00, 11F
→
02/02 14:11, , 12F
a怎麼會不一樣?
02/02 14:11, 12F
推
02/02 14:40, , 13F
2a一樣 2b不一樣
02/02 14:40, 13F
推
02/02 16:50, , 14F
同意樓上
02/02 16:50, 14F
→
02/02 22:05, , 15F
放在程式裡的話 2a是不一樣沒錯啊
02/02 22:05, 15F
→
02/02 23:52, , 16F
阿其實是我題目沒說清楚,我現在搞懂了,同Di大,謝謝各位
02/02 23:52, 16F
→
09/11 14:50, , 17F
阿其實是我題目沒說清楚 https://daxiv.com
09/11 14:50, 17F
‣ 更多 wong0101 的文章
文章代碼(AID): #1FAMXor3 (Grad-ProbAsk)