Closed. This question needs details or clarity. It is not currently accepting answers. Learn more。
想改进这个问题吗？添加细节并通过editing this post澄清问题。
这不是作业，我在学习摊销分析。我有点困惑，我不能完全理解摊销和平均复杂度之间的含义。不确定这是否正确。这里有一个问题：
--
我们知道程序的运行时复杂度取决于程序的输入组合---假设程序具有运行时复杂度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）。哪个是正确的，为什么？
二是摊销部分。我已经阅读了Constant Amortized Time并且我们已经知道，摊销分析不同于平均案例分析，因为不涉及这种可能性；摊销分析保证了最坏情况下每个操作的平均性能。
我可以说摊销运行时是o（n）。但答案是o（pn）。我有点搞不懂为什么会有这种可能性。虽然o（n）=o（pn），但我真的不知道为什么p会出现在那里？我改变了思维方式。假设我们确实损失了时间，那么K就变得很大，所以摊销运行时间是（K p O（n）+K*（1-p）O（logn））/K=O（pn）这似乎和一般的情况是一样的。
很抱歉搞糊涂了，请帮帮我，首先谢谢！
最佳答案
对于“平均”或“预期”的复杂性，你在假设问题的概率分布。如果你不走运（或者如果你的问题生成器恶意地不符合你的假设8^），那么你的所有操作都将非常昂贵，而且你的程序可能需要比你预期的多得多的时间。
摊销复杂性是对任何操作序列的总成本的保证。这意味着，无论问题生成器有多恶意，您都不必担心一系列操作所花费的时间比您预期的要长得多。
（取决于算法，偶然发现最坏的情况并不难。典型的例子是naive Quicksort，它对大多数排序的输入都很糟糕，即使“平均”的情况很快）
关于algorithm - 摊销和平均运行时复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21420341/