作者:
sooge (老衲)
2018-10-12 22:39:28https://i.imgur.com/ZYTZ4ya.jpg
請問這題要如何下手 題目看不太懂....
答案就只給一個O(n^2)而已
拜託了
一個loop call funtion，function裡也有一個loop
作者:
befdawn (橙花雨露)
2018-10-12 23:48:00後面還有題目嗎？
作者:
skyHuan (Huan)
2018-10-13 00:22:00compute_value()副程式是O(k)主程式迴圈i從1開始跑到ni小於1000的時候是O(1)i很大的時候(超過1000)就是O(i)複雜度=1+1+...+1+1000+1001+1002+...+n=O(n^2)喔喔喔我看錯題目，那還是一樣在n很大的時候迴圈O(n)跑n次，所以O(n^2)複雜度是討論n很大的時候。還有這題程式s沒設初值跑應該會出錯雖然跟這題無關XD
作者:
befdawn (橙花雨露)
2018-10-13 14:16:00請問s大(可惜這邊不能直接tag哈哈)，複雜度跟 input data 大小有關，是指 input 值大小嗎？(這樣是算 bits？)
作者:
skyHuan (Huan)
2018-10-13 14:48:00我說錯了應該要說資料量大小影響到執行"次數"，比如資料量是n，迴圈跑到n，資料量就有影響到複雜度，像上面test()函式如果只是算數"值"就不會影響複雜度int test(int k){ return k*k; } => O(1)int test(int k){for(i=0;i<k;i++) printf("hello!"); } => O(k)
作者:
befdawn (橙花雨露)
2018-10-13 15:10:00了解，謝謝s大解說