Re: [問題] 請問關於find in sorted array 演算法問題

看板Prob_Solve作者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

推

seanwu

11/17 00:17, , 1^F

11/17 00:17, 1^F

→

a127a127

11/17 00:35, , 2^F

11/17 00:35, 2^F

→

a127a127

11/17 00:36, , 3^F

11/17 00:36, 3^F