题目内容
(请给出正确答案)
[主观题]
针对如教材第290页代码10.7所示的percolateUp()上滤算法,10.2.2节曾指出其执行时间为O(logn)。然而,这只是对其最坏情况的估计;在通常的情况下,实际的效率要远高于此。试通过估算说明,在关键码均匀独立分布时,最坏情况极其罕见,且插入操作平均仅需常数时间。
查看答案
如果结果不匹配,请 联系老师 获取答案
教材81页代码3.20中的List::selectionSort()算法,通过selectMax()在前缀子序列中定位的最大元素max,有可能恰好就是tail的前驱——自然,此时“二者”无需交换。针对这一“问题”,你可能会考虑做些“优化”,以期避免上述不必要的交换,比如将
a)以序列(1980,1981,1982,...,2011,2012;0,1,2,...,1978,1979)为例,这种情况共发生多少次?
b)试证明,在各元素等概率独立分布的情况下,这种情况发生的概率仅为1nn/n→0——也就是说,就渐进意义而言,上述“优化”得不偿失。