[理工] 资料结构 时间复杂度
楼主: AGENTofAQUA (Prometheus _D_Aqua) 2020-04-01 22:25:14
例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次?
作者: mi981027 (呱呱竹) 2020-04-01 22:53:00
你算的没错 这是精确值 但题目这样问的话 通常会用asymptotic notation表示估计值 所以笔记上有写“大约” 否则调和级数也写不出closed form sol.
作者: yobdc3692581 (jade) 2020-04-01 22:53:00
"大约"跑n/i次
楼主: AGENTofAQUA (Prometheus _D_Aqua) 2020-04-01 23:09:00
喔喔 谢谢 所以在多层循环情况下如果内层循环是log的话，那+1直接省略就行了