作者AGENTofAQUA (Matrix)
看板Grad-ProbAsk
標題[理工] 資料結構 時間複雜度
時間Wed Apr 1 22:25:14 2020
http://i.imgur.com/IQ1UM4w.jpg
http://i.imgur.com/HSYQdki.jpg
例5我知道x=x+1總共要跑k+1次，因為2的0次方時x=x+1有執行一次，所以從2的0次方到2的k次方總共執行k+1次。而我不懂的點在於Ex1的a++在沒有for loop的情況下應當是執行(n/i)+1次才對(x=n-0i時a++就執行一次，到了x=n-ki時a++執行(n/i)+1)，為何會是執行n/i次?
-----
Sent from JPTT on my Asus ASUS_Z01GD.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.214.176.39 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1585751117.A.5D9.html
推 mi981027: 你算的沒錯 這是精確值 但題目這樣問的話 通常會用asymp 04/01 22:53
→ mi981027: totic notation表示估計值 所以筆記上有寫“大約” 否則 04/01 22:53
→ mi981027: 調和級數也寫不出closed form sol. 04/01 22:53
→ yobdc3692581: "大約"跑n/i次 04/01 22:53
→ AGENTofAQUA: 喔喔 謝謝 所以在多層迴圈情況下如果內層迴圈是log的 04/01 23:09
→ AGENTofAQUA: 話，那+1直接省略就行了 04/01 23:09
