gpt4 book ai didi

algorithm - Queue 实现的插入操作的时间复杂度/性能(在 Java 中)

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:59:55 28 4
gpt4 key购买 nike

实现为 Queue 的插入操作的性能如何:

(a) 一个数组,元素未排序

(b) 一个数组,其中的项目按排序顺序排列

(c) 一个链表,其中的项目未排序。

对于每个操作和每个实现,以大 Oh 表示法给出性能并解释足够的算法以证明您的答案是正确的。 (例如,它需要 O(n) 次,因为在最坏的情况下......算法会做这样......)。

请详细解释,这对我有很大帮助!

最佳答案

简短回答:这取决于您的数据结构。

在一个简单的基于数组的实现中(假设大小固定),我认为很明显插入是一个常量操作(即 O(1)),假设你没有跑到数组的末尾.这在循环数组中是相似的,具有相似的假设。

动态数组稍​​微复杂一点。动态数组是一个固定大小的数组,一旦它被填充到某个点就可以放大。因此,对于一个在达到长度 k 时调整大小的动态数组,第一个 k-1 插入是常量(就像插入普通数组一样)并且 k 次插入需要 O(k+1) - 将数组内容复制到更大的容器中,然后插入元素的成本。您可以证明插入时间为 O(1),但这可能超出您类(class)的范围。

正如其他人所指出的,排序顺序不会影响标准队列。如果您实际上是在处理优先级队列,那么有很多可能的实现方式,我会让您自己研究。最佳插入时间为 O(1),但该实现有一些缺点。标准实现是 O(log n) 插入。

对于链表,插入时间将取决于链表的头部是否是队列的头部(即,您是添加到头部还是尾部)。

如果要在头部添加,则很容易看出插入的复杂度为 O(1)。如果要添加到尾部,那么也很容易看出对于长度为 n 的列表,插入的时间复杂度为 O(n)。要点是,无论您选择哪种实现方式,插入始终是 O(1) 或 O(n) 之一,而删除始终是另一个。

但是,有一个简单的技巧可以让您在任何一种情况下都以 O(1) 的时间进行插入和删除。我将留给您考虑如何做到这一点。

关于algorithm - Queue 实现的插入操作的时间复杂度/性能(在 Java 中),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24522338/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com