[理工] DS複雜度

看板Grad-ProbAsk作者 (麼六)時間8年前 (2017/12/11 17:48), 8年前編輯推噓4(4推 0噓 4→)
留言8則, 2人參與, 8年前最新討論串1/1
http://i.imgur.com/AlrmC3f.jpg
第一題我直接用離散的解法得到O(3^n)，請問我的算法哪裡有問題? ----- Sent from JPTT on my Asus ASUS_Z00ED. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.208.138 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512985735.A.F8B.html
推
12/11 17:55, 8年前 , 1F
題目是求時間複雜度嗎？
12/11 17:55, 1F
對
推
12/11 18:00, 8年前 , 2F
我印象中這題是求Running times(執行的次數）
12/11 18:00, 2F
推
12/11 18:00, 8年前 , 3F
那個2和3的意思是對算出來的值做運算，不是呼叫2次
12/11 18:00, 3F
→
12/11 18:00, 8年前 , 4F
跟3次的意思，當然不要乘到式子裡面
12/11 18:00, 4F
※ 編輯: mersix (101.12.208.138), 12/11/2017 18:00:36
→
12/11 18:00, 8年前 , 5F
而不是Time complexity(時間複雜度）
12/11 18:00, 5F
→
12/11 18:01, 8年前 , 6F
所以你可以想成這個程式是call兩個自己
12/11 18:01, 6F
推
12/11 18:03, 8年前 , 7F
12/11 18:03, 7F
→
12/11 18:03, 8年前 , 8F
要算函數值的話你的做法是對的
12/11 18:03, 8F
我了解了，感謝2位 ※ 編輯: mersix (101.12.208.138), 12/11/2017 18:06:55
‣ 更多 mersix 的文章
文章代碼(AID): #1QBbI7-B (Grad-ProbAsk)