[理工] 資結 時間複雜度

看板Grad-ProbAsk作者 (DAY)時間6年前 (2017/08/01 22:09), 6年前編輯推噓4(4推 0噓 7→)
留言11則, 4人參與, 最新討論串7/12 (看更多)
大家好 對不起我問題有點多 先想請問這兩個例題 第一張是題目，第二張鉛筆寫的是我算的 http://i.imgur.com/OWdeXce.jpg
http://i.imgur.com/O169qJD.jpg
想問的是這兩題都沒有給邊界，所以就想說既然例題1是T(n/2)那就代代T(1)，但由於程式碼說n=1時會進入else那邊循環，這樣就不知道T(1)是多少了，例題2也是一樣的疑惑，懇請解釋 第二個 http://i.imgur.com/Atm8grf.jpg
不懂的是最後一項 ( lgn - (k-1) )為什麼會等於1呢，不是應該是( lgn - k )才會等於1嗎?還是說為了方便帶公式才加1上去的 ----- Sent from JPTT on my Samsung SM-J710GN. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.124.77 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1501596552.A.C13.html
推
08/01 23:15, , 1F
第一個是n!=0時進else，n=0時return 1
08/01 23:15, 1F
→
08/02 07:48, , 2F
謝謝回答! 但我想問的是他的邊界條件是什麼，我是想T(
08/02 07:48, 2F
→
08/02 07:48, , 3F
1)是他的邊界條件，但T(1)代入原程式碼中並不等於一個
08/02 07:48, 3F
→
08/02 07:48, , 4F
常數，所以不知道big O是多少，謝謝!
08/02 07:48, 4F
推
08/02 09:12, , 5F
T(1)可以繼續代下去 通常遞迴除法取floor
08/02 09:12, 5F
→
08/02 09:24, , 6F
請問樓上，那麼T(1)要代什麼值呢，取floor是什麼意思~
08/02 09:24, 6F
→
08/02 09:24, , 7F
?
08/02 09:24, 7F
推
08/02 11:45, , 8F
第一題 邊界條件是 T(0)
08/02 11:45, 8F
→
08/02 11:48, , 9F
第二題 實際上式子表示的是(lgn)-(k-1)
08/02 11:48, 9F
→
08/02 11:49, , 10F
然後遞迴 最後一層的 k = lg n，所以就變成 1 了
08/02 11:49, 10F
謝謝回答!第二題我懂了!! 不過第一題如果他的邊界條件是T(0)的話 那照我推倒的方式好像不會達到T(0)欸，可以解釋的更詳細一點嗎，謝謝!! ※ 編輯: justlike68 (101.10.18.104), 08/02/2017 13:35:04
推
08/02 20:48, , 11F
除法要取 floor 也就是只看商數的整數部分 已經有人解釋了
08/02 20:48, 11F
我好像理解了 謝謝回答 ※ 編輯: justlike68 (101.12.181.89), 08/04/2017 11:50:31
‣ 更多 justlike68 的文章
文章代碼(AID): #1PW8k8mJ (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 7 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 justlike68 的文章
文章代碼(AID): #1PW8k8mJ (Grad-ProbAsk)