习题[2-1]~[2-3] 第2章 向量
[2-1] 关二某个算法，甲证明“其平均时间复杂度为 O(n)”，乙证明“其分摊时间复杂度为 O(n)”。
若他们癿结讳均正确无误，则是甲癿结讳蕴含乙癿结讳，乙癿结讳蕴含甲癿结讳，迓是互丌蕴含？
【解答】
两个结论之间不存在蕴含关系，但相对而言，后一结论更为可靠和可信。
所谓平均复杂度，是指在假定各种输入实例的出现符合某种概率分布之后，进而估算出的加
权复杂度均值。比如在教材的第12.1.5节中，将基于“待排序的元素服从独立均匀随机分布”
这一假设，估算出快速排序算法在各种情况下的加权平均复杂度。
所谓分摊复杂度，则是纵观连续的足够多次操作，并将其间总体所需的运行时间分摊至各次
操作。与平均复杂度的本质不同在于，这里强调，操作序列必须是的确能够真实发生的，其中各
次操作之间应存在前后连贯的时序关系。比如在参考文献[41]中，Tarjan采用势能分析法对伸
展树所有可能的插入、删除操作序列进行分析，并估算出在此意义下单次操作的分摊执行时间。
由此可见，前者不必考查加权平均的各种情况出现的次序，甚至其针对概率分布所做的假设
未必符合真实情况；后者不再割裂同一算法或数据结构的各次操作之间的因果关系，更加关注其
整体的性能。综合而言，基于后一尺度得出的分析结论，应该更符合于真实情况，也更为可信。
以教材2.4节中基于容量加倍策略的可扩充向量为例。若采用平均分析，则很可能因为所做
的概率分布假定与实际不符，而导致不准确的结论。比如若采用通常的均匀分布假设，认为扩容
与不扩容事件的概率各半，则会得出该策略效率极低的错误结论。实际上，只要假定这两类事件
出现的概率各为常数，就必然导致这种误判。而实际情况是，采用加倍扩容策略后，在其生命期
内随着该数据结构的容量不断增加，扩容事件出现的概率将以几何级数的速度迅速趋近于零。对
于此类算法和数据结构，唯有借助分摊分析，方能对其性能做出综合的客观评价。
[2-2] 教材 32 页代码 2.2 癿 copyFrom()算法中，目标数组_elem[]是通过 new 操作由系统另行分配癿，
故可保证在物理上不来源数组 A[]相互独立。若丌能保证返种独立性，该算法需要做哪些调整？
【解答】
若不能保证目标数组与来源数组之间的独立性，则二者可能在空间上有所重叠，出现所谓的
“搭接”现象。此时，需要区分两种情况分别处理。若目标数组的某一后缀与来源数组的某一前
缀重叠搭接，则需要按“从前到后”的次序逐一转移各元素；反之，若目标数组的某一前缀与来
源数组的某一后缀重叠搭接，则应改用“从后到前”的次序。
[2-3] 假讴将教材 34 页代码 2.4 中 expand()算法癿扩容策略改为“每次追加固定数目癿单元”。
a） 试证明，在最坏情冴下，单次操作中消耗二扩容癿分摊时间为(n)，其中 n 为向量觃模；
【解答】
假定每次追加d个单元。于是，只要每隔固定的常数k次操作就发生一次扩容，则初始容量
为n
0
的向量在经过连续的N >> k次操作之后，容量将增加至：
评论0
最新资源