随机算法的一般性原理

The General Principles of Randomized Algorithms

最近十几年来,国际上对随机算法(randomized algorithm)的研究有了巨大进展.在此期间,随机算法从一个计数理论的工具发展到今天在许多类型的算法中都得到了广泛应用,显示了随机算法本身强大的生命力.

The last decade has witnessed a tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread application in many types of algorithms. Two benefits of randomization have spearheaded this growth: simplicity and speed. For many applications, a randomized algorithm is the simplest algorithm available, or the fastest, or both. A handful of general principles lie at the heart of almost all randomized algorithms, despite the multitude of areas in which they find application. We briefly survey these here in order to draw about the method of studying randomized algorithms.