題組內容

四、霍夫曼碼（Huffman code）是具有最佳編碼的資料壓縮方法之一，今有下列的訊息欲以霍夫曼碼編碼傳遞以節省訊息量

“PAPAYA_AND_BANANA_ARE_YUMMY”

其中空格 ‘_’ 亦需計算在訊息量內。

(二)依步驟說明所使用演算法的時間複雜度（time complexity）。

詳解 (共 1 筆)

詳解提供者：114年高考上榜

1.先將字串一一丟入計數算出比重，時間複雜度為O(n)
2.選出兩個最低的比重進行結合直到全部結合，所需的時間複雜度為O(n^2)
故時間複雜度為n+n^2 n若為無限大時常數省略，故為O(n^2)