首先,這裡的程式碼比較像是 Pseudocode , 所以不會宣告任何變數。
再來解決這三個題目,時間複雜度如果不太會算的話,可以用迴圈最裡面的片段執行次數
來推應該要填什麼時間複雜度。不過這種方法比較偷吃步,有少部分題目還是會出錯,當參考就好。
以A這題來說:
假設 n 是 4。 i 等於 0 ,s++ 不會執行; i 等於 1 ,s++ 執行1次; i 等於 2 ,s++ 執行2次; i 等於 3 ,s++ 執行3次;
可以看出來次數大概是 n^2/2 次,但時間複雜度不會有常數項。所以會變成 O(n^2)
其他兩題就練習看看吧 d(`・∀・)b
非本科系的疑問:
該跑就是要跑,效能不佳時就思考其他方式,
算時間複雜度的意義在?
理解為什麼效能不佳,學術方面。
恩~
學術本身很重視科學依據,你必須有一個明確的論述、數據來量化,這段演算法的效能是好是壞。這就是為什麼學術做演算法的,都要算時間複雜度。做學術研究總不能用「感覺」來判定演算法的好壞。
在工作上,時間複雜度我們是當作是一個Sense,大概從那段程式碼會執行多少次,底層做多少處理,判斷這段程式碼的效能
我覺得很實用呀, 在後面學習演算法跟資料結構時就會告訴你在不同情況下的複雜度是多少, 要看得懂這些才幫助你在不同情況下怎麼處理跟計算, 而不是在那邊瞎測試哪個有效率。但平常實際在寫code的時候大部份會像是通靈王講的Sense的感覺, 不太會真的下去算複雜度有多少, 不過我想很多人寫code沒在管有沒效率..程式會跑就好, 出事再說XD