匹配数据的最高效数据结构是什么?例如,假设我提出与后续的情景:数据匹配的高效数据结构
<time available> <buy or sell> <company name> <buy or sell price> <amount to buy or sell>
所以,一个文件可能包含:
0 sell yahoo $100 #1
2 sell yahoo $14 #1
2 sell yahoo $28 #1
.. 95 other yahoo sells <$125 and amount #1
3 sell yahoo $17 #1
5 sell yahoo $33 #1
9 buy yahoo $125 #100
是否有可能这最后买与前100搭配销售的为O(n )时间,其中n = 100,如果购买与其想要购买的公司相对应的最低销售价格相匹配(或者配对时排在第一位)。
我知道一个天真的解决方案将排序列表,并按顺序,但这需要比O(n)时间更长。处理这个问题和类似的问题最有效的数据结构是什么?
你能对你想要做的更具体吗?也就是说,你能否明确说明你希望能够支持哪些操作以及(相对而言)他们发生的频率? – templatetypedef 2013-03-24 20:15:47
如果您反转您的初始想法,假设您保留一个有序的销售价格清单,您的插入将增加到O(log n),但您可以在O(1) – Alexander 2013-03-24 21:53:14