[理工] 时间复杂度 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

继续阅读