栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

什么是算法的摊销分析?

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

什么是算法的摊销分析?

摊销分析不会天真地将调用次数与一次调用的最坏情况相乘。

例如,对于需要时将大小增加一倍的动态数组,正常的渐近分析只会得出结论,将一个项目添加到该数组中会花费O(n),因为它可能需要增长并将所有元素复制到新数组中。摊销分析考虑到要进行增长,必须添加n / 2个项目,而自上一次增长以来就不会导致增长,因此添加项目实际上仅需O(1)(O(n)的成本为分摊到n / 2个操作中)。

摊销分析与“平均绩效”不同-摊销分析对如果您执行大量操作将对绩效产生什么影响提供了硬性保证。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/515155.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号