作者seika555 (kakkoii)
看板Grad-ProbAsk
標題[理工] 資節heap題目的時間複雜度
時間Mon Aug 13 01:38:05 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1534095491.A.14B.html
1F：推 BroccolYee: 圓圈是內部節點 方形是外部節點 external = interna 08/13 03:18
2F：→ BroccolYee: l + 1 08/13 03:18
3F：→ BroccolYee: 最糟的情形是x為heap中的最小值 08/13 03:18
4F：→ BroccolYee: 因此要找比x大的值需要把整棵樹都翻一次 08/13 03:18
5F：→ BroccolYee: 但其實整個搜尋也只能地毯式 heap沒有規定說自己的孩 08/13 03:18
6F：→ BroccolYee: 子跟兄弟的孩子都要小於自己和兄弟 08/13 03:18
7F：→ BroccolYee: 遞迴方程式應該是T(n) = 2*T(n/2) + O(1) 08/13 03:18
8F：→ BroccolYee: 比較完當下的node與x後 大於:輸出並繼續遞迴 08/13 03:18
9F：→ BroccolYee: 小於或等於:停止 大概是這樣~ 08/13 03:18
謝謝樓上 所以O(1)是因為比較heap[i]>x的這行嗎
※ 編輯: seika555 (122.116.213.244), 08/13/2018 18:58:26
10F：推 BroccolYee: O(1)是指在常數時間內完成 因此停止應該也可以說是O 08/13 20:40
11F：→ BroccolYee: (1) 不用分那麼細XD 08/13 20:40
哦哦 原來哈哈 謝謝你
※ 編輯: seika555 (122.116.213.244), 08/13/2018 21:30:50