作者a127a127 (TDYa127)
看板Prob_Solve
标题Re: [问题] 请问关於find in sorted array 演算法问题
时间Mon Nov 16 23:58:27 2009
┌─┐
│ │
└─┘
／ ＼
／ ＼
┌─┐ ┌─┐
│ │ │ │
└─┘ └─┘
／ ＼ ／ ＼
┌─┐ ┌─┐ ┌─┐ ┌─┐
│ │ │ │ │ │ │ │
├─┤ ├─┤ ├─┤ ├─┤
│ │ │ │ │ │ │ │
上半是个heap，下面是m个array。
每次取最小值的时候，把root拿走。
然後一路把比较小的往上拿，花刚好lg(m)的时间。
总共取n次就好了。
时间复杂度Θ(m+n*lg(m))
空间复杂度Θ(m)
跟array拿值次数Θ(m+n)
不知道这样讲你看不看得懂 XD。
（它有个名字，不过我忘了@@a。）
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 115.43.146.11
1F：推 seanwu:selection tree ? 11/17 00:17
2F：→ a127a127:楼上强者 //原来原本那些node是虚拟的啊@@a 11/17 00:35
3F：→ a127a127: //难怪当初看到的时候觉得怪怪的XD 11/17 00:36
4F：推 DJWS:winner tree 11/17 21:52
5F：推 command:喔喔! 好方法! 感谢感谢! 11/18 12:03