[理工] 時間複雜度

[Huffman (HuffmanAlgorithm)]

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)

請問是這樣算嗎？


-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.92.206
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1494309694.A.8BD.html
→ brilliantl: http://i.imgur.com/VHo5AJ6.jpg
→ brilliantl: O(lgn)做n次所以變O(nlgn)
推 shownlin: 這圖XDDD
→ brilliantl: 手邊沒紙筆啦~
→ Huffman: Brilliantl好猛!
推 box38431: 熱心小畫家～
推 mike31830: 請問j-i不用計算嗎
→ brilliantl: 要，但是當n趨近無限大時，它就太小可以省略
→ Huffman: http://i.imgur.com/02BMcTg.jpg