[理工] 資節heap題目的時間複雜度

看板Grad-ProbAsk作者 (kakkoii)時間7年前 (2018/08/13 01:38), 7年前編輯推噓2(2推 0噓 9→)
留言11則, 1人參與, 7年前最新討論串1/1
https://imgur.com/BHWaRzE.jpg
想請問關於上述例題 3 該如何判斷time complexity 為 O(k) 呢 看不太懂之前抄的 k+(k+1) 是如何來的 還有如果要應用之前遞迴那邊學的公式 可以把他寫成 T(n) = 2* T(n/2)... 的這種形式嗎 要如何寫呢 突然不知道該如何轉換 還請幫忙解惑 謝謝 -- -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.213.244 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1534095491.A.14B.html
推
08/13 03:18, 7年前 , 1F
圓圈是內部節點 方形是外部節點 external = interna
08/13 03:18, 1F
→
08/13 03:18, 7年前 , 2F
l + 1
08/13 03:18, 2F
→
08/13 03:18, 7年前 , 3F
最糟的情形是x為heap中的最小值
08/13 03:18, 3F
→
08/13 03:18, 7年前 , 4F
因此要找比x大的值需要把整棵樹都翻一次
08/13 03:18, 4F
→
08/13 03:18, 7年前 , 5F
但其實整個搜尋也只能地毯式 heap沒有規定說自己的孩
08/13 03:18, 5F
→
08/13 03:18, 7年前 , 6F
子跟兄弟的孩子都要小於自己和兄弟
08/13 03:18, 6F
→
08/13 03:18, 7年前 , 7F
遞迴方程式應該是T(n) = 2*T(n/2) + O(1)
08/13 03:18, 7F
→
08/13 03:18, 7年前 , 8F
比較完當下的node與x後 大於:輸出並繼續遞迴
08/13 03:18, 8F
→
08/13 03:18, 7年前 , 9F
小於或等於:停止 大概是這樣~
08/13 03:18, 9F
謝謝樓上 所以O(1)是因為比較heap[i]>x的這行嗎 ※ 編輯: seika555 (122.116.213.244), 08/13/2018 18:58:26
推
08/13 20:40, 7年前 , 10F
O(1)是指在常數時間內完成 因此停止應該也可以說是O
08/13 20:40, 10F
→
08/13 20:40, 7年前 , 11F
(1) 不用分那麼細XD
08/13 20:40, 11F
哦哦 原來哈哈 謝謝你 ※ 編輯: seika555 (122.116.213.244), 08/13/2018 21:30:50
‣ 更多 seika555 的文章
文章代碼(AID): #1RS7235B (Grad-ProbAsk)