算法导论7.3 Exercises 答案

7.3-1

正如平均时间复杂度的意义所在，随机算法的平均时间复杂度更能反映出其期望的运行时间。分析随机算法的时间复杂度过程中，我们预测了各种可能的随机行为，并最终通过这些所有的随机行为计算出一个总的期望值。不过，由于上述过程是随机进行的，我们不能直接以恶意地干扰这些随机行为。相反，分析最坏时间复杂度时，没有任何的随机行为，我们可以根据算法本身构造出一个恶意的输入使其时间复杂度最大化。

7.3-2

当达到最差情况时，随机算法恰好将区间划分成一空一满的状态，此时算法RANDOM调用次数满足\(C(n)=C(n-1)+1\)，即\(C(n)=\Theta(n)\)。

当达到最好情况时，随机算法恰好将区间划分成两半的状态，此时算法RANDOM调用次数满足\(C(n)=2C(n/2)+1\)，即\(C(n)=\Theta(n)\)。

也就是说，无论什么情况，算法RANDOM将会被调用\(\Theta(n)\)次。