Re: [理工] [DS] 98-台大資工
線代離散快看不完了，來這裡先回個演算法問題qqqqqqq
※ 引述《christianSK (AG)》之銘言：
: 先附個題目
: http://www.lib.ntu.edu.tw/exam/graduate/98/98404.pdf
: 1. 想請問大家第一題是怎麼看的 ?!
: 我的方法錯了一半 好像不太對 = =
我的想法如下：
1. t 完全是故弄玄虛。
仔細檢查一下程式碼，無輪 t 的值是多少都不會影響兩個For迴圈的執行次數。
所以我們可以大膽假設他時間複雜度的遞迴只跟n有關，為T(n)。
2. 既然根據上面的假設，加上對程式碼的觀察，我們可以得到以下遞迴式：
T(n) = X * T(Y) + Θ(Z) if n > 1
Θ(1) if n <= 1
3. 雖然他有Floor和Ceil，但我選擇無視他，雖然這有可能導致錯誤的結果就是。
(1)(2)(3) 應該都可以用 Master Theorem 來解決。
對答案協力：我自己亂作的答案是
(1) G --- Case 3
(2) H --- Case 2 (更正 Orz
(3) L --- Case 2 ... 再更正，沒錯，是Case 2
(4) E --- 重猜，用離散的遞迴想確實是這樣沒錯 Orz
(5) H --- 畫Recursion Tree，第1層n^2logn，第2層2n^2logn/2，第3層2n^2logn/4
因此應該是O(n^2logn)
: 5. "The Huffman encoding algorithm emoloyed a priority queue of binary search
: tree" T or F (目前查到的答案是FALSE)
: 翻了一下書 priority 的定義應該是 :
: a collection of item each associative the priority.
: 想請問這兩者的關係是? (感覺這問題問的有點怪?!)
: 謝謝大家 :)
應該是False，但我認為原因可能是這樣：
The Huffman encoding algorithm emoloyed:
(錯) a priority queue of binary search tree
(正）a priority queue of heap
重新檢視一次他的問題：
首先，「Priority Queue」是一個資料結構，你可能需要查一下課本
在Huffman code的求解中，我們需要每次拿到「權重值最小的兩個節點」
而這個步驟就要用Priority Queue來做，因此Priority Queue為止都對
但Priority Queue因為效率的關係，一般都是用Heap來實作
（雖然可以用Balanced Binary Search Tree來做，但時間複雜度會高出不少）
因此應該是錯在這一點上面
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.177.56
→
01/26 07:36, , 1F
01/26 07:36, 1F
→
01/26 07:37, , 2F
01/26 07:37, 2F
※ 編輯: ybite 來自: 122.127.177.56 (01/26 21:38)
※ 編輯: ybite 來自: 122.127.177.56 (01/26 21:42)
※ 編輯: ybite 來自: 122.127.177.56 (01/26 21:44)
※ 編輯: ybite 來自: 122.127.177.56 (01/27 00:11)
→
01/27 00:11, , 3F
01/27 00:11, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：