我想在 O(1) 而不是 O(n) 中检查一个元素是否存在于列表中（一个非常大的 10,000,000 顺序）。带 O(n)的列表elem x ys所以我想使用另一种数据类型/构造函数，但它必须在Prelude（不是数组）中；有什么建议么？如果我必须构建我的数据类型，它会是什么样子？
还可以以相同的顺序（10,000,000）对大量数字进行排序，并在尽可能短的时间内索引一个元素。
问问题
190 次
2 回答
6
在 O(1) 时间内在数据集中搜索项目的唯一方法是，如果您已经知道它在哪里，但您不需要搜索它。对于未排序的数据，搜索是 O(n) 时间。对于排序的数据，搜索是 O(log n) 时间。
于 2012-11-21T22:12:20.383 回答
4
You should use either Bloom filter or Hashtable. Neither of them is in Prelude; moreover, both rely on Array to be available.
The only left option is some kind of tree; I would suggest heap. It’s not hard to implement and it also gives you sorting for free.
UPDATE: oops! I have forgotten that heap doesn’t provide lookup. BST is your choice, then.
于 2012-11-21T22:17:30.523 回答