问题标签 [amortized-analysis]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
arrays - 使用链表和数组实现堆栈时的加倍和增量策略？
摊销复杂度和平均复杂度有什么区别？在使用链表和数组实现堆栈时，什么是加倍和增量策略？
amortized-analysis - 递增和递减二进制计数器的摊销成本是否相同？
递增和递减二进制计数器的摊销成本是否相同？即 O(n) 用于 n 增量或减量？也有人可以解释如何使用潜在方法计算二进制递减计数器的摊销成本。
c++ - 寻找摊销时间复杂度
所以我push_back为向量类编写了一个函数，现在我正在尝试计算摊销时间复杂度。我对编程的理论方面还很陌生，所以如果有人能引导我完成它，那就太棒了。
这是我的功能：
这是我的allocate_new功能：
arrays - 每次将动态数组增长固定常数的效率？
因此，当每次添加元素时动态数组的大小加倍时，我了解扩展的时间复杂度是 O(n) n 是元素。如果数组被复制并移动到一个新数组，当它已满时，它只大 1 大小怎么办？（而不是加倍）当我们通过某个常数 C 调整大小时，时间复杂度总是 O(n)？
algorithm - 求哈希函数的摊销复杂度
当我遇到这个问题时，我正在准备期末考试。
对于 1a，我认为它的 O(1) 用于摊销复杂性，因为它执行足够稀疏的 x mod N 并且线性探测以防它失败但是我不确定如何准确地陈述或证明这一点。
对于 1b，它会散列到同一个地方，因此每次插入时它都会线性探测更多，但我也不确定如何从中派生运行时。
arrays - 当应用相邻转置时，在次线性时间内更新数组中的最大和 subinteral
我问了这个关于一般换位的问题，这似乎太难了，我只得到了一个似乎不能保证渐近加速的答案。因此，假设我们将一系列相邻转置应用于数值数组（相邻转置交换两个相邻数字），并且我们希望在每个相邻转置之后保持最大和子区间的解。我们可以在每个相邻的转置之后在整个阵列上从头开始重复 Kadane 的线性时间解。所以这就是我想要击败的。这可以在每个相邻转置的亚线性时间内完成吗，例如，如果我们对大小为 N 的数组进行 N 或 N^2 个相邻转置，并且只要摊销的预处理时间对于整个集合是亚线性的，我们就可以进行预处理应用转置？
algorithm - 摊销和平均运行时复杂度
这不是作业，我正在研究摊销分析。有些事情让我感到困惑。我无法完全理解摊销和平均复杂性之间的含义。不确定这是否正确。这是一个问题：
--
我们知道程序的运行时复杂度取决于程序输入的组合——假设程序运行时复杂度为 O(n) 的概率为 p，其中 p << 1，而在其他情况下（即对于 (1 -p) 可能的情况），运行时复杂度为 O(logn)。如果我们使用 K 个不同的输入组合运行程序，其中 K 是一个非常大的数字，我们可以说这个程序的摊销和平均运行时复杂度为：
--
第一个问题是：我在这里读过这个问题：Difference between average case and amortized analysis
所以，我认为平均运行时复杂度没有答案。因为我们不知道平均输入是多少。但它似乎是 p*O(n)+(1-p)*O(logn)。哪个是正确的，为什么？
二是摊销部分。我已经阅读了恒定摊销时间，我们已经知道摊销分析与平均情况分析的不同之处在于不涉及概率；摊销分析保证了在最坏情况下每个操作的平均性能。
我可以说摊销运行时间是 O(n)。但答案是 O(p n)。我对为什么涉及概率有点困惑。虽然 O(n)=O(p n)，但我真的不知道为什么 p 会出现在那里？我改变思维方式。假设我们确实损失了时间，那么 K 变得非常大，因此摊销运行时间为 (K p O(n)+K*(1-p) O(logn))/k = O(p n)。这似乎与平均情况下的想法相同。
给我添麻烦了，麻烦帮帮我，先谢谢了！
c - 在动态数组的摊销分析中考虑 malloc 是否错误？
在动态数组的摊销分析中，我在作业作业中计算了错误的总成本。我认为评分者可能只看总数而不是我采取的步骤，我认为我考虑了 malloc 而他们的答案键没有。
以下是我分析的一部分：
我们看到的例子没有考虑malloc，但我看到一个视频，它很有意义，所以我把它放在那里。我意识到虽然 malloc 是一个相对昂贵的操作，但在这里它可能是 O(1)，所以我可以省略它。
但我的问题是：进行此类分析时是否只有一种方法可以计算成本？是否存在客观的对错成本，或者得出的结论是否真正重要？
algorithm - 使用 3 个堆栈实现 Deque（摊销时间 O(1)）
我对howmework有这个问题：
使用 3 个堆栈实现双端队列。Deque 有这些操作：InsertHead、InsertTail、DeleteHead、DeleteTail。证明每个操作的摊销时间为 O(1)。
我尝试将问题视为河内问题。因此，让我们将堆栈称为：L（左），M（中），R（右）。
伪代码实现：
InsertTail 和 DeleteTail 与上述实现原理相同。如何证明摊销时间为 O(1)？因为 L 中可以有 N 个元素，并且 wile 循环将花费 O(n)，现在如果我调用 deleteHead N 次来计算摊销时间，复杂度不会是 O(n^2)？
有人可以帮助我如何证明上述实现在摊销时间内需要 O(1) 吗？
algorithm - 随机算法
我遇到了一个随机问题。:)
A，一种随机算法，确定输入 x 是否为素数。
该算法的工作方式如下：
1- 如果 x 是素数，则 A 输出 YES
2- 如果 x 不是素数，则 A 以 3/4 的概率输出 NO。
如果我们想让算法 A 以至少 1- (1/k) 的概率输出 NO，我们至少应该运行 A 多少次？
注意：一个“否”的答案意味着给定的输入 x 不是素数。
任何想法？