[理工] 103成大程式設計 st474ddr PTT批踢踢實業坊

[理工] 103成大程式設計

作者: st474ddr (hikke) 2019-01-19 23:04:57

https://i.imgur.com/VwTE6qR.jpg
小弟要問一下是非第三題的答案
我不是很確定worst case用chain能不能到O(log n)
https://i.imgur.com/q2m1gHX.jpg
演算法是非2、3小題
不確定答案我都不知道怎麼解釋
第3小題之前板上有
只是我不太懂
還有第二大題他有兩個條件
這要怎麼去算他的時間複雜度啊
謝謝各位大大

作者: yp195126 (我睡故我在) 2019-01-19 23:48:00

1.3 F 如果每個數都對應到同一格這樣chain長度為n 最長搜尋時間為O(n)演算法1.2 如果是skew-tree 需要O(n) 可以畫圖實作看看演算法1.3 merge A1A2A3成一個sort list需要O(n+n+n)=O(n) 因為是balance bst 所以root需為中間值在list找到中間值的時間為O(1) 用遞迴概念 T(n)=2T(n/2)+O(1)=O(n)兩者相加為O(n)

作者: dumpling1234 (dumpling) 2019-01-20 00:38:00

想問ㄧ下第三題如果list用AVL tree去maintain的話不是可以達到O(logn)嗎?

作者: yp195126 (我睡故我在) 2019-01-20 00:46:00

logn是單項操作的時間吧要再乘上n 因為題目給的是low bound 但有辦法在小於O(nlogn)的時間求出所以答案是F

作者: dumpling1234 (dumpling) 2019-01-20 01:09:00

我說的是DS Hash 那題

作者: yp195126 (我睡故我在) 2019-01-20 01:15:00

Chaining mouther是以link list的方式去串聯同一格的值搜尋時間比照link list是chaining method...選錯字

作者: moriahyen (阿克西斯) 2019-01-20 09:26:00

演算法2 https://i.imgur.com/3GPZVos.jpg

作者: st474ddr (hikke) 2019-01-20 11:24:00

感謝大大們

作者: alen0303 (艾倫零參智商負三) 2019-01-20 14:18:00

關於那個M 台大考過類似題是當變數來看

繼續閱讀

[理工] 計組的問題重要觀念kaidi620 [理工] 100台大電信線代fmtshk [理工] 特徵值奇怪求法cvn21 [理工] 107台科OS第5題Hertzfeld 107中央資演wilson50101 [理工] 107交大資結AAQ8 [理工] 105交大資結AAQ8 Re: [理工] 107 中央資結演算法對答案dumpling1234 [理工] 106中央計系hanhancute [理工] 106清大計科！Aa841018

[理工] 103成大 程式設計

[理工] 103成大程式設計