8-1(比较排序的概率下界) 在这一问题中，我们将证明对于给定的n个互异的输入元素，任何确定或随机的比较排序算法，其概率运行时间都有下界Ω(nlgn)。首先分析一个确定的比较排序算法A，其决策树为Ta，假设A的输入的每一种排列情况都是等可能的。8-1(比较排序的概率下界) 在这一问题中，我们将证明对于给定的n个互异的输入元素，任何确定或
阅读背景：
算法导论第八章思考题
来源：互联网
分享到：
