online advertising

Friday, June 5, 2015

Haskell 99 Problem 23

Problem

Please find the problem here.

Solution:

Please see the solution as follow:

Moving forward, we are going to do something cool with random numbers. This problem is about generating a random selection without replacement. The original algorithm used a list to represent the remaining items, so every time we need to pick an item it takes $ O(n) $ time, and therefore a total of $ O(kn) $ time, if $ k = n $, then we have $ O(n^2) $ time. With the current version, I used an AVL tree to represent the items, so it takes an overall $ O(k \log n) $ time for the selection, but remember we need to populate the tree at the first place, so an overall $ O(n \log n) $ time.

No comments :

Post a Comment