<分区>
这不是作业，我正在研究摊销分析。有些事情让我感到困惑。我无法完全理解摊销和平均复杂性之间的含义。不确定这是对还是错。这是一个问题:
--
我们知道程序的运行时复杂度取决于程序的输入组合——假设程序运行时复杂度为 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 变得非常大，所以摊销运行时间为 (KpO(n)+K*(1-p)O(logn))/k = O (pn)。这似乎与平均情况相同。
抱歉造成混淆，请帮助我，先谢谢了!