[問題] call function的成本

看板C_and_CPP作者worcdlo時間6年前發表 (2019/01/09 13:29), 6年前編輯推噓5(5推 0噓 10→)

留言15則, 3人參與, 6年前最新討論串1/1

最近在練習演算法剛好寫到一個標準的硬幣問題 https://leetcode.com/problems/coin-change/ 本來用DP寫，發現只beat 70% 參考別人的寫法後，發現這題很多人都用DFS寫於是寫了一個版本(DFS)結果time limit exceeded 後來改了一個版本(DFS2) DFS2只是簡單的將原本的return判斷式移動到進入遞迴之前，結果時間卻差很多當然能理解多進一層遞迴確實成本有差但是從時間複雜度來看，order應該一致的？主要想請教原本寫法會time limit exceeded是否只是單純進遞迴成本差太多？或著有其他因素在？程式碼： https://goo.gl/e7ZEBq [額外請教一個github問題] 我每次編輯程式碼都會將tab的縮排長度設定為4 但是存檔後打開，看起來都自動跳回8 用筆電的話反而會自動跳為2 不知道要如何將它真的固定為4 ※ 編輯: worcdlo (42.73.253.241), 01/10/2019 06:41:56

推

kaneson

01/10 07:08, 6年前 , 1^F

01/10 07:08, 1^F

→

kaneson

01/10 07:08, 6年前 , 2^F

01/10 07:08, 2^F

我自己看起來是覺得都有剪，只是第一個版本要進入下一層function才剪另外因為連結更動用手機編輯，不知道為何就把更早的兩個回文刪了，真是抱歉 ※ 編輯: worcdlo (123.195.174.95), 01/10/2019 09:21:21

推

kaneson

01/10 12:02, 6年前 , 3^F