2回答
在我看到的任何地方(在SO和其他来源上)，摊销分析通常只适用于数据结构。例如用于dynamic array或splay tree。然而，我还没有看到纯算法的分期分析的应用。关于算法的摊销分析有意义吗？摊销分析假设了一系列操作，这对于数据结构是正确的，但对于算法则不是。
浏览 29提问于2021-10-13得票数 0
回答已采纳
2回答
什么是摊销分析？它如何帮助我在我的程序中实现最坏的性能保证？操作序列(我们的分析必须同时考虑到数据和客户端执行的操作顺序)作者将调整数组数据结构作为如何实现摊销分析的一个例子，但我仍然不明白什么是摊销分析，以及如何实现它(数据结
浏览 0提问于2012-08-18得票数 14
回答已采纳
2回答
更新：这个问题是我们如何对不可变集合使用摊销分析？Scala的不可变队列只是一个例子。从源中可以清楚地看到这个不可变队列是如何实现的。摊销分析最初是为可变集合而发明的。如何将它应用于Scala的可变队列是很清楚的。但是，我们如何将其应用于这一系列操作，例如？没有这样的框架，没有对结构部件的延迟评估和对结果的记忆，我们就无法将摊销分析应用于完全持久不变的数据结构。但是，如果一个数据结构具有O(1)时间复杂性的克隆，我们可以打破摊销时间<
浏览 10提问于2022-09-19得票数 -2
回答已采纳
3回答
我正在读一篇关于算法摊销分析的文章。下面是一个文本片段。在第一段中，平均案例分析如何“依赖于关于数据结构和操作的概率假设？”我知道平均情况分析取决于输入的概率，但上面的陈述是什么意思？
浏览 0提问于2011-09-07得票数 57
回答已采纳
“摊销”是指也就是说，在一段时间内定期分期偿还债务。
在算法的摊销分析中，“摊销”是否也意味着通过定期搁置的其他东西来减少一些东西？
浏览 0提问于2015-09-11得票数 1
1回答
要支持这样的数据集，拥有二进制搜索树或数组是否更有效。 Array BST
Search O(log(1) O(1) *Delete O(n) O(n)
*：最大/最
浏览 1提问于2016-06-25得票数 0
1回答
我刚开始接受摊销分析。我注意到，动态数组的一个常见做法是在空间不足时将其大小加倍。我们选择翻倍的尺寸有什么特别的原因吗？为什么不三倍或四倍？是否有一个具体的解释选择加倍使用摊销分析？
浏览 2提问于2020-04-23得票数 2
回答已采纳
1回答
一组整数的有效数据结构
、、、
我正在处理一组间隔为0，m的n个整数，我需要以下操作：
是否有任何数据结构需要小于O(m)空间，同时仍然保持(摊销)最坏的情况复杂性O(1)用于查找/删除/插入和O(n)用于枚举/清除？请注意:摊销如下：“给定n次运算，我们总共有常数*n次运算，所以摊销的最坏情况是O(1)
浏览 3提问于2017-05-24得票数 0
1回答
当将摊销成本分配给数据结构上的操作时，您需要确保，对于执行的任何操作序列，摊销成本的总和总是至少与这些操作的实际成本之和一样大。，我认为摊销是(n*实际成本)。
( B)是否有任何例子可以让我更清楚明白？一个真实而简短的例子？
浏览 3提问于2021-01-06得票数 1
回答已采纳
我正在寻找一个静态数据结构与摊销的恒定时间关联查找。我要执行的唯一操作是查找和构造。此外，发挥作用也是必须的。我看过手指树，但我似乎不能把头绕在它们周围。是否有好的文档，或者更好的，更简单的静态功能数据结构？
浏览 5提问于2015-02-24得票数 1
回答已采纳
1回答
这个问题似乎有点迂腐，但我一直在尝试深入研究摊销分析，并对为什么为散列表插入是O(1)摊销感到有点困惑。(注意:我不是在说表加倍，我理解这一点)从技术上看，哈希表的插入的average 摊销分析是O
浏览 5提问于2017-09-04得票数 4
6回答
有没有人能用外行的话解释一下摊销的复杂性？我一直很难在网上找到一个准确的定义，我不知道它如何完全与算法分析相关。任何有用的东西，即使是外部引用的，都将受到高度赞赏。
浏览 2提问于2013-02-26得票数 78
我意识到Vector是同步的，并且具有继承优势(和开销)，但我觉得不仅这些数据结构通常在文本中是基于链表的结构，而且LL避免了在填充底层数组时代价高昂的大小调整。我确实理解，使用摊销分析，即使使用大小，Vectors也是O(1)。因此，也许考虑到这一点并没有太大的不同，但我仍然很好奇地想了解其中的原理。
浏览 2提问于2012-07-07得票数 2
回答已采纳
我正在阅读Cormen et al.In的算法介绍，这一章的标题是摊销分析，会计方法和潜在方法的区别如下将超额收费作为“预付信用证”存储在数据结构
浏览 0提问于2013-08-15得票数 6
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
