算法(4th ed)(184):基础——算法分析 6.8.3

阅读数:7 2019 年 11 月 9 日 15:38

算法(4th ed)(184):基础——算法分析 6.8.3

(处理对于输入的依赖:随机化算法)

为性能提供保证的一种重要方法是引入随机性。例如,我们将在 2.3 节中学习的快速排序算法(可能是使用最广泛的排序算法)在最坏情况下的性能是平方级别的,但通过随机打乱输入,根据概率我们能够保证它的性能是线性对数的。每次运行该算法,它所需的时间均不相同,但它的运行时间超过线性对数级别的可能性小到可以忽略。与此类似,我们将在 3.4 节中学习的用于符号表的散列算法(同样也可能是使用最广泛的同类算法)在最坏情况下的性能是线性级别的,但根据概率我们可以保证它的运行时间是常数级别的。这些保证并不是绝对的,但它们失效的可能性甚至小于你的电脑被闪电击中的可能性。因此,这种保证在实际中也可以用来作为最坏情况下的性能保证。

评论

发布