什么是算法的摊销分析？
与渐进分析有何不同？您何时使用它，为什么？
我读过一些写得不错的文章，例如：
http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
但我仍然没有完全理解这些概念。
那么，有人可以为我简化一下吗？
问题答案：
摊销分析不会天真地将调用次数与一次调用的最坏情况相乘。
例如，对于需要时将大小增加一倍的动态数组，正常的渐近分析只会得出结论，将一个项目添加到该数组中会花费O（n），因为它可能需要增长并将所有元素复制到新数组中。摊销分析考虑到要进行增长，必须添加n / 2个项目，而自上一次增长以来就不会导致增长，因此添加项目实际上仅需O（1）（O（n）的成本为分摊到n / 2个操作中）。
摊销分析与“平均绩效”不同-摊销分析对如果您执行大量操作将对绩效产生什么影响提供了硬性保证。
-
Edit：您可以假设hashtable使用基本链接，其中元素位于相应链表的末尾。我的真正问题是关于概率算法的摊销分析。 编辑2：我在quicksort上发现了这篇文章，“摊销运行时间和预期运行时间之间有一个微妙但重要的差异。使用随机枢轴的quicksort的预期运行时间为O（n log n）,但其最坏的运行时间为θ(n^2)。这意味着quicksort的成本很小，但随着n的增加，这种可能性接近于零
-
展开树中的每个字典操作都使用一个展开操作将节点带到树的根。这种散放操作的摊销效率通常使用潜在方法进行分析，并在许多在线资源（包括维基百科）页面中进行了描述。然后将该散放操作的摊销时间报告为O（m lg n）。 然而，我没有找到对完整字典操作的实际分析，例如插入、删除。。。这些操作中的每一个操作除了使用splay操作外，还使用向下搜索树来找到要插入或删除的节点的正确位置。只有找到该节点后，才能开始展
-
主要内容：算法是什么,伪代码描述算法要想成为一名合格的程序员，除了至少掌握一门编程语言，更重要的是多动手实践，积累足够的代码量，提升自己“遇到问题，解决问题”的能力。任何一门编程语言的学习，本质就是学习它规定的语法，整个过程只能死记硬背，几乎没有捷径。但是，提高“解决问题”的能力是有捷径可寻的，比如掌握一些算法。 提到“算法”，很多人都觉得它高深莫测、晦涩难懂。事实上的确存在一些算法，学员必须具备优秀的数学基础和编程能力才能驾驭。但
-
根据下面引号中的规范，实现了一个队列（该语言使用Ruby，但希望每个人都能读懂）。 使用堆栈实现队列。也就是说，只使用push和pop操作来写入队列和出队列。 就性能而言，enqueue应该是O(1)，但dequeue在最坏的情况下可能是O(n)。从时间上看，出队时间应为O(1)。证明您的解决方案实现了这一点。 我在想，你怎么证明排队的摊销时间？谢了！
-
本文向大家介绍什么是A*算法？相关面试题，主要包含被问及什么是A*算法？时的应答技巧和注意事项，需要的朋友参考一下 个人感觉类似最佳优先算法，都是维护一个优先队列或堆，将结点按照某个值优先的情况放进去，不同的是这次需要一个估计函数h(n) 算法思想：对于优先队列，每取出一个结点n，将他的所有儿子结点n'放入优先队列，优先级由函数f(n)计算出 g(n)：起点到结点n的代价 h(n)：结点n到终点的
-
本文向大家介绍什么是RSA算法？相关面试题，主要包含被问及什么是RSA算法？时的应答技巧和注意事项，需要的朋友参考一下 回答：RSA（Rivest-Shamir-Adelman）算法是用于签名数据和加密的第一个算法。它最广泛用于保护敏感数据。它也被称为非对称密码算法，它对两个不同的密钥（即公共密钥和私有密钥）起作用。公开密钥可以与任何人共享，并且私有密钥必须保密。