問題詳情
19. 霍夫曼碼 (Huffman Codes) 的演算法主要是採用下列何種設計策略？
(A)分而治之法 (Divide-and-Conquer)
(B)動態規劃法 (Dynamic Programming)
(C)貪婪演算法 (Greedy Algorithms)
(D)回溯法 (Backtracking)
參考答案
答案：C
難度：計算中-1
書單：沒有書單，新增
用户評論
【小彥子老師】評論
霍夫曼編碼「貪婪」的部分到底在哪裡呢？在於每一步都盡可能讓樹的高度最少地增加。樹的高度越高，整體編碼會越長，可以想像當樹都只在同一邊合併的話，就會變得很高，雖然也可以得到無前綴碼，但不是最有效率解。霍夫曼編碼透過每一次合併權重和最小的樹，讓平均樹高的增加減到最小，也確保運算出平均長度最短的無前綴碼。