作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1585751117.A.5D9.html
1F：推 mi981027: 你算的没错 这是精确值 但题目这样问的话 通常会用asymp 04/01 22:53
2F：→ mi981027: totic notation表示估计值 所以笔记上有写“大约” 否则 04/01 22:53
3F：→ mi981027: 调和级数也写不出closed form sol. 04/01 22:53
4F：→ yobdc3692581: "大约"跑n/i次 04/01 22:53
5F：→ AGENTofAQUA: 喔喔 谢谢 所以在多层回圈情况下如果内层回圈是log的 04/01 23:09
6F：→ AGENTofAQUA: 话，那+1直接省略就行了 04/01 23:09