我需要使用一个可以用C实现的数据结构,它可以在固定时间内执行基本操作,比如查找、插入和删除。一、 然而,也需要能够在恒定时间内找到最大值。
这个数据结构可能应该被排序以找到最大值,我已经研究了红黑树,但是它们有对数时间运算。
我会提议
>
您可以使用一个哈希表,该哈希表给出O(1)的预期时间
关于最大值,您可以将其存储在属性中,并在每次插入时注意最大值是否更改。删除会更复杂一些,因为如果删除最大值,则必须执行线性搜索,但只有删除最大值时才会发生这种情况。任何其他元素都可以在O(1)预期时间内删除
是的,我同意Irleon的观点。你可以使用哈希表来执行这些操作。让我们一步一步地分析这个:
1.如果我们采取数组,插入的时间复杂度将是O(1)在最后。
2.采取链表,由于你需要做的遍历,它将是O(n)。
3.采取二叉搜索树,它将是O(logn)其中logn是树的高度。
4.现在我们可以使用哈希表。我们知道它在键和值上工作。所以,这里的关键是“number_to_be_inserted%n”,其中“n”是我们拥有的元素数量。
但是当列表在同一个索引上增长时,您将需要遍历列表。所以它将是O(numbers_at_that_index)。
删除操作也是如此。
当然,在冲突的情况下还有其他情况需要考虑,但是我们现在可以忽略它,我们将得到基本的哈希表。
如果你可以做这样的事情,那么你可以在线性时间内排序:只需插入所有项目,然后执行以下n次:
因此,在一个不能以线性时间排序的计算模型中,也不能在O(1)时间内解决所有操作的问题。