关于二项式队列性能
以下文本来自二项式队列文章。
虽然左堆和斜堆都支持合并、插入和 每次操作的delete_min都在O(log n)时间内有效，有 改进的空间，因为我们知道二进制堆支持 每次操作的平均插入时间恒定。二项式队列 在 O(log n) 最坏情况下支持所有三个操作 操作，但插入平均需要恒定时间。
在上面的文本中，作者所说的每次操作的平均平均时间恒定是什么意思？以及它与二项式队列的不同之处在于插入需要常数 平均时间？
每次操作的恒定平均时间和平均恒定时间有什么区别？
Below text is from binomial queues article.
Although both leftist and skew heaps support merging, insertion, and
delete_min all effectively in O(log n) time per operation, there is
room for improvement because we know that binary heaps support
insertion in constant average time per operation. Binomial queues
support all three operations in O(log n) worst-case time per
operation, but insertions take constant time on average.
In above text what does author mean by constant average time per operation? and how it is different from for binomial queues insertion takes constant
time on average?
What is difference between constant average time per operation and constant time on average?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
没有什么区别。作者一方面对比左堆和倾斜堆，另一方面对比二项堆，以表明二项式堆具有二项堆（预期 O(1) 插入）左堆和倾斜堆所没有的一些优点（它们只有摊销 O(1) 插入）。
There is no difference. The author is contrasting leftist and skew heaps on the one hand, and binary heaps on the other, to show that binomial heaps have some of the advantages of binary heaps (expected O(1) insert) that leftist and skew heaps do not have (they only have amortized O(1) insert).