提问者:小点点

具有恒定时间操作的数据结构


我需要使用一个可以用C实现的数据结构,它可以在固定时间内执行基本操作,比如查找、插入和删除。一、 然而,也需要能够在恒定时间内找到最大值。

这个数据结构可能应该被排序以找到最大值,我已经研究了红黑树,但是它们有对数时间运算。


共3个答案

匿名用户

我会提议

>

  • 您可以使用一个哈希表,该哈希表给出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次:

    1. 查找最大值
    2. 打印最大值
    3. 删除最大值

    因此,在一个不能以线性时间排序的计算模型中,也不能在O(1)时间内解决所有操作的问题。