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.

 
 

 
 




 
 

 
 



T1,T2,T3,T4是四种增大的方形

 


 
 

An example


 






 
 

 
 

 
 


 
 

 
 

 
 

 
 

 
 

 
 



分类: 算法

发表评论

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