Re: [問題] 請問關於find in sorted array 演算法問題
看板Prob_Solve (計算數學 Problem Solving)作者a127a127 (TDYa127)時間16年前 (2009/11/16 23:58)推噓3(3推 0噓 2→)留言5則, 4人參與討論串2/2 (看更多)
┌─┐
│ │
└─┘
／ ＼
／ ＼
┌─┐ ┌─┐
│ │ │ │
└─┘ └─┘
／ ＼ ／ ＼
┌─┐ ┌─┐ ┌─┐ ┌─┐
│ │ │ │ │ │ │ │
├─┤ ├─┤ ├─┤ ├─┤
│ │ │ │ │ │ │ │
上半是個heap，下面是m個array。
每次取最小值的時候，把root拿走。
然後一路把比較小的往上拿，花剛好lg(m)的時間。
總共取n次就好了。
時間複雜度Θ(m+n*lg(m))
空間複雜度Θ(m)
跟array拿值次數Θ(m+n)
不知道這樣講你看不看得懂 XD。
（它有個名字，不過我忘了@@a。）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 115.43.146.11
推
11/17 00:17, , 1F
11/17 00:17, 1F
→
11/17 00:35, , 2F
11/17 00:35, 2F
→
11/17 00:36, , 3F
11/17 00:36, 3F
推
11/17 21:52, , 4F
11/17 21:52, 4F
推
11/18 12:03, , 5F
11/18 12:03, 5F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
