[理工] 時間複雜度 Huffman PTT批踢踢實業坊

作者: Huffman (HuffmanAlgorithm) 2017-05-09 14:01:31

for (i=0 to n )
{begin
j=i;
while j >0 do j=j/2;
end }
本題來自國考版
要求時間複雜度
在無條件捨去的情況下（j=j/2;)
小弟算的結果是
2*log n!+4*n-2
所以O(n*log n)
請問是這樣算嗎？

作者: brilliantl (brilliant) 2017-05-09 15:09:00

作者: shownlin (哈哈阿喔) 2017-05-09 18:47:00

這圖XDDD

作者: brilliantl (brilliant) 2017-05-09 19:18:00

手邊沒紙筆啦~

作者: Huffman (HuffmanAlgorithm) 2017-05-09 19:35:00

Brilliantl好猛!

作者: box38431 (旋風噴射阿姆斯特朗砲) 2017-05-09 20:14:00

熱心小畫家～

作者: mike31830 2017-05-10 00:34:00

請問j-i不用計算嗎

作者: brilliantl (brilliant) 2017-05-10 07:22:00

要，但是當n趨近無限大時，它就太小可以省略

作者: Huffman (HuffmanAlgorithm) 2017-05-10 10:24:00

繼續閱讀