Roh*_*han 4 algorithm amortized-analysis
存在n个操作的序列,如果i是2的精确幂,则第i个操作花费2i,如果i是3的精确幂,则花费3i,并且对于所有其他操作则花费1.
嗨,首先,我想说这是一个家庭作业问题,我不希望你为我解决它.我用聚合方法解决了它.为此,我总结了2系列的权力和3的一系列权力并得到了10的摊销成本.然后我使用会计方法检查了它,对于很长的序列并且它没有失败.但我的问题是如何证明它永远不会失败,我可以显示我想要的长序列,但它仍然不能保证它不会失败一段时间后.
我也尝试使用潜在的函数方法解决它,这是我真的陷入困境,设置一个潜在的函数,我认为你需要真正的创造性,我找不到一些条件,表明在这一点上这将永远成立,需要也有一些帮助.
关于如何在会计方法中证明它以及如何设置潜在功能的一些想法应该足够了.谢谢
首先,忘记"1为所有其他操作"和"精确的3"位一分钟.如果我的精确功率为2,那么成本只是2i怎么办？
好吧,假设我们假装每个运营成本为四.也就是说,对于每个操作,我们将四个硬币放入我们的"IOU堆"......然后当我们达到2的实际功率时,我们使用这些硬币"支付".(这是描述潜在功能方法的一种方式.)
第1步:存入四枚硬币.需要支付2*1 = 2,所以我们的硬币堆是两个.
第2步:存入四枚硬币.需要支付2*2 = 4,所以我们的桩又是两个.
第3步:存入四枚硬币.桩现在有六个硬币.
第4步:存入四枚硬币.桩现在有十个硬币,但4是2的幂,所以是时候支付4*2 = 8,所以我们的桩再次下降到两个硬币.
步骤5-7:每个存入四个硬币.总计现在是14个硬币.
步骤8:存入四个硬币(总数= 18),花费8*2 = 16,再次留下两个硬币.
很容易证明这里的稳定状态是我们继续将我们的硬币耗尽到恒定(2),但我们永远不会低于.因此,摊销成本为每个操作四个单位.
现在,假设当i是2的幂时,操作X花费2i(否则为零).假设当i是3的幂时操作Y花费3i(否则为零).并且假设操作Z成本为1,除非i是2的幂或3的幂.观察到你的问题等同于每次迭代执行操作X 和 Y 和 Z ...所以如果你能算出摊销的成本分别为X,Y和Z,您可以将它们相加以获得总体摊销成本.
我刚给你X; 我把Y和Z作为练习.(虽然我不相信最终答案是10.接近10,也许......)