关于某个算法，甲证明“其平均时间复杂度为O(n)”，乙证明“

[问答题]

关于某个算法，甲证明“其平均时间复杂度为O(n)”，乙证明“其分摊时间复杂度为O(n)”。若他们的结论均正确无误，则是甲的结论蕴含乙的结论，乙的结论蕴含甲的结论，迓是互不蕴含？

查看答案及解析

王大牛

两个结论之间不存在蕴含关系，但相对而言，后一结论更为可靠和可信。
所谓平均复杂度，是指在假定各种输入实例的出现符合某种概率分布之后，进而估算出的加
权复杂度均值。比如在教材的第12.1.5节中，将基于“待排序的元素服从独立均匀随机分布”
这一假设，估算出快速排序算法在各种情况下的加权平均复杂度。
所谓分摊复杂度，则是纵观连续的足够多次操作，并将其间总体所需的运行时间分摊至各次
操作。与平均复杂度的本质不同在于，这里强调，操作序列必须是的确能够真实发生的，其中各
次操作之间应存在前后连贯的时序关系。比如在参考文献[41]中， Tarjan采用势能分析法对伸
展树所有可能的插入、删除操作序列进行分析，并估算出在此意义下单次操作的分摊执行时间。
由此可见，前者不必考查加权平均的各种情况出现的次序，甚至其针对概率分布所做的假设
未必符合真实情况；后者不再割裂同一算法或数据结构的各次操作之间的因果关系，更加关注其
整体的性能。综合而言，基于后一尺度得出的分析结论，应该更符合于真实情况，也更为可信。
以教材2.4节中基于容量加倍策略的可扩充向量为例。若采用平均分析，则很可能因为所做
的概率分布假定与实际不符，而导致不准确的结论。比如若采用通常的均匀分布假设，认为扩容
与不扩容事件的概率各半，则会得出该策略效率极低的错误结论。实际上，只要假定这两类事件
出现的概率各为常数，就必然导致这种误判。而实际情况是，采用加倍扩容策略后，在其生命期
内随着该数据结构的容量不断增加，扩容事件出现的概率将以几何级数的速度迅速趋近于零。对
于此类算法和数据结构，唯有借助分摊分析，方能对其性能做出综合的客观评价。

发表于 2019-09-28 15:04:53 回复(0)

提交观点

问题信息

上传者：小小

难度：

1条回答 1收藏 466浏览

关于某个算法，甲证明“其平均时间复杂度为O(n)”，乙证明“

问题信息

热门推荐

相关试题