Randomized algorithms

In a randomized algorithm (probabilistic algorithm), we make some random choices.


2 types of randomized algorithms:

1. For an optimization problem, a randomized algorithm gives an optimal solution.

The average case time-complexity is more important than the worst case time-complexity.

2. For a decision problem, a randomized algorithm may make mistakes.

The probability of producing wrong solutions is very small.




This problem can be solved by the divide-and- conquer approach in O(nlogn) time.

The randomized algorithm: partition the points into several clusters:

We only calculate distances among points within the same cluster.

Similar to the divide-and-conquer strategy. There is a dividing process,

but no merging process.








An example











分类: 算法


电子邮件地址不会被公开。 必填项已用*标注