看板Programming
标 题Re: [问题] 请问insertion, find均为O(1)的资料结构
发信站枫桥驿站 (Sun Jan 18 22:04:57 2009)
转信站ptt!news.ntu!news.au!zoonews.ee.ntu!Leo.mi.chu!news.NHCUE!ctu-peer!new
若Collection 没你要的
善用 DataTable的功能
你可以自订资料表 栏位 用 find 或是 select 去取出你要的资讯
不管什麽资料结构基本上都可以用 dataTable 模拟出作法
※ 引述《[email protected] (OK的啦～我都可以接受)》之铭言：
> ※ [本文转录自 Prob_Solve 看板]
> 作者: king19880326 (OK的啦～我都可以接受) 看板: Prob_Solve
> 标题: [问题] 请问insertion, find均为O(1)的资料结构
> 时间: Sat Nov 29 19:47:47 2008
> 是这样的
> 小弟最近写的一个程式
> 需要一种能动态增减的资料结构.
> 需要提供的operation有
> insert(insert一个新的data进去该data structure)
> find(判断data是否在该data structure里, 若是, 则提供data所在的position)
> 因为该程式几乎不会用到deletion(自data structure里delete data)
> 所以不在意deletion的效能
> 目前我是使用linked list来实作这个部分
> 可是linsked list的find的time complexity为O(n)
> (即使是amortized下依然是O(n))
> 想请问有没有一个资料结构的insert和find的time complexity是O(1)
> (或是amortized後为(1)的??)
> 感谢感谢 <(_ _)>
> ps. hash table虽然可以办到, 可是在collision的时候就不能保证O(1)了 @@>
> 感谢大家 <(_ _)>
--
◤ ◣
─ 枫桥艺文站正式开张！─˙─˙─▍ 枫桥驿站˙
竟然不是 ‵ ◣︹▉
▋ │▉▄▅▆
红萝卜！▄▅▇
;
快来寻找你爱的作家。 ▃▆◤ ／＼ ◢ ◥
◣▃▅ ◢为你呕心沥血的作品找个窝。 ◣ ◣ ◢＝＝＝ ◆
◥ 文学版＋美工板，强烈邀请您。 ◣▁▂ ▆ ◢
◣ ●.● clamping从118.161.186.29 ◢◢ ◥