Randomized algorithm

• Bloom filter
• Count sketch
• Count–min sketch
• Quotient filter
• Skip list

• Random binary tree
• Treap
• Rapidly exploring random tree

• Randomized algorithm
• HyperLogLog

This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is

findingA_MC(arrayA,n,k) begin i:=0 repeat Randomlyselectoneelementoutofnelements. i:=i+1 untili=kor'a'isfound end

If an 'a' is found, the algorithm succeeds, else the algorithm fails. After k iterations, the probability of finding an 'a' is:

---

View original on Wikipedia | Back | FazBrowse Home