问题标签 [amortized-analysis]

假设整数表示为斐波那契数的总和而不是 2 的幂，所以100101表示F(6)+F(3)+F(1)=8+2+1=11（我们假设F(1)=F(2)=1）。我想在 O(1) 摊销时间内在这个表示下增加一个整数。

我有递增算法：直觉是不应该有两个连续的 1 位。所以我首先将最低有效位 0 设置为 1，然后从最高有效位开始，如果数字有两个连续的 1 位，例如位 i 和 i-1，将它们都设置为 0 并设置 i+1位为 1。递归执行此操作，直到没有两个连续的 1 位。

我使用会计方法进行摊销分析。因此，对于每个增量操作，我将授予 k 美元，并且每个位翻转将花费 1 美元。但是，我无法设置和证明 k 的正确值。从经验上我认为k=3可以工作，但我不知道如何去证明这一点。

我正在为我的一门课程做作业，一个问题要求显示减少键操作，对于配对堆，需要 O(1) 时间。

显然，如果您有一个指向要减少的键的指针，那么该操作将花费 O(1) 时间（只需删除链接，更改键值，然后合并）。

但是，在分配中没有任何地方说我们得到了一个指向键的指针。如果我们没有得到一个指针，那么 reduce-key 就不可能花费 O(1) 时间（你必须先在堆中查找键，这不会花费恒定时间）。我看了文献，都说减少键需要 O(logn) 时间。

我在这里错过了什么吗？

在第 5 课中的数据结构课程中给出的摊销分析的聚合方法中 O(n)/n=1 的情况如何 - 摊销分析：聚合方法？

假设您使用一个数组实现了一个堆，并且每次数组已满时，您将其复制到一个大小为两倍的数组中。将元素插入堆的摊销时间复杂度（最坏情况下）是多少？

我认为我们有T(n) = n * n（这是在最坏情况下一系列 n 操作的总成本的上限），然后根据一个公式的摊销复杂度是T(n) / n = n^n / n = n。

但是我认为这是非常错误的，因为直觉很清楚我应该得到log(n)或更低......那么我应该如何计算呢？

我正在寻找有关如何设计实验以比较queue一个使用基准完成的实现的行为python list和另一个python queue abstract data type使用基准的实现的行为的指针。

这是我可以根据我的理解提出的一些代码amortized testing

结果：

在斐波那契堆中，所有操作分析本质上都是摊销的。为什么我们不能像二项式堆那样进行正常分析。

在Data.List模块中，使用了以下数据结构

片段上方的评论提到如下：

队列保证（摊销） O(1)snoc和 O(1) uncons，这意味着我们可以toListSB将 O(1) 转换为类似列表的结构比普通列表慢的常数因子——我们支付 O(n ）随着我们使用列表而增加成本。

我不明白为什么toListSB在 O(1) 中工作是摊销的。右列表的长度不是在 2 的连续幂之间越来越大吗？

维基百科说二项式堆中的插入操作的摊销时间为 O(1)。对于单个插入操作，时间复杂度为 O(log n)。但是它的摊销时间如何变成 O(1) 呢？

我正在审查决赛并偶然发现以下问题：

二叉堆默认具有优先级队列语义：如果我们将某个元素插入 n 次，则需要在它“消失”之前将其移除 n 次。想象一下，你想用集合语义来实现二进制堆。在这种情况下，插入和删除操作的速度有多快？

(a) 插入：O(n) 删除：O(logn)

(b) 插入：O(log n) 删除：O(n)

(c) 插入：O(log n) 删除：O(log n)

(d) 插入：O(1) 删除：O(n2)

(e) 以上都不是。

要插入使用优先队列语义实现的堆，它将是 O(logn)，删除也是如此。但是对于集合，插入和删除取决于集合本身的许多因素。你认为答案应该是什么？

关于调整动态数组大小（作为 ArrayList ADT 的一部分）的问题让我很困惑。

文本设置了将元素添加到数组末尾的场景。当数组达到其容量时，它的大小会增加一倍。新的较大数组使用旧数组的元素进行初始化。该过程的摊销分析给出了 O(n) 的复杂度。

然后提出以下问题：

当容量为 N 的数组已满时，不是将 N 个元素复制到容量为 2N 的数组中，而是将它们复制到具有 N/4 个附加单元的数组中，即容量为 (N + N/4) 的数组。证明对数组执行 n 次加法的序列仍然在 O(n) 中运行。

任何提示，如何解决这个问题的帮助都非常感谢。我不知道如何处理这样一个事实，即满容量的数组的大小增加了其当前大小的一小部分，而不是当前大小的倍数。