[理工] 資料結構 時間複雜度
作者: 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直接省略就行了