摊销和平均运行时复杂性

Question

这不是功课,我正在研究摊销分析.有些事让我感到困惑.我无法完全理解摊销和平均复杂性之间的含义.不确定这是对的.这是一个问题:

-

我们知道程序的运行时复杂性取决于程序输入组合---假设具有运行时复杂度O(n)的程序的概率是p,其中p << 1,在其他情况下(即对于(1) -p)可能的情况),运行时复杂度为O(logn).如果我们使用K个不同的输入组合运行程序,其中K是一个非常大的数字,我们可以说这个程序的摊销和平均运行时复杂度是:

-

第一个问题是:我在这里读到了这个问题:平均案例和摊销分析之间的差异

所以,我认为平均运行时复杂性没有答案.因为我们不知道平均投入是多少.但似乎是p*O(n)+(1-p)*O(logn).哪个是正确的,为什么？

第二,摊销部分.我读过Constant Amortized Time,我们已经知道Amortized分析与平均案例分析的不同之处在于概率不涉及; 摊销分析保证了最坏情况下每项操作的平均表现.

我可以说,分摊的运行时间是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).它似乎与平均情况相同.

对不起,请帮帮我,先谢谢!

Answer 1

对于"平均"或"预期"复杂性,您正在假设问题的概率分布.如果您运气不好,(或者如果您的问题生成器恶意地无法与您的假设相匹配8 ^),您的所有操作都将非常昂贵,并且您的程序可能会花费比您预期更长的时间.

摊销复杂性是任何操作序列总成本的保证.这意味着,无论您的问题生成器有多恶意,您都不必担心一系列操作会花费比预期更长的时间.

(根据算法的不同,在最坏的情况下不小心偶然发现.经典的例子是天真的Quicksort,即使"平均"情况很快,它对主要排序的输入也很糟糕)