Andrei Alexandrescu Wrote: > Ok, following Leonardo's and Denis' ideas on covering an immutable array > in random order, I thought about it and came up with one algorithm, in > addition to the obvious one that stores one integer per element (see > Denis' code). > > Here's the algorithm. It stores one bit per element and takes O(n log n) > time to cover a range of length n. > > 1. Given a random-access range r of length n, create a bitmap with one > bit per element in r. The range is initially all zeros. > > 2. At each step, select a random index in the _original_ array, i.e. a > random number in 0 .. r.length. Then walk upwards (with wrapping at the > end of the range) until you find a bit = 0 in the bitmap. Mark that bit > = 1 and return the found element. > > 3. The cover ends when all bits in the bitmap are 1.
So far so good. > I did a ballpark complexity estimate by approximating the average number > of steps in (2) with n / (n - k), where k is the number of 1s in the > bitmap. IIRC the average number of steps to hit a 1 in a binomial > distribution with p = (n - k) / n is 1/p. Right? In that case, the total > number of steps taken by the algo above is: > > N = n / 1 + n / 2 + ... + n / (n - 1) = n * (1 + 1/2 + 1/3 + ... + 1/(n > - 1)) < O (n log n) > > Makes sense? No. Your wording sounds like you're doing stuff that's way off, but the resulting math is correct. My calculation would be based on the average length of a sequence of 1's (k/(n-k)). That means the work is 1+k/(n-k) = n/(n-k). Given that O(n*log(n)) is the theoretical best you can do, having a result that is < O(n*log(n)) is highly suspect. The sum 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + ... is in fact O(log(n)). > If the range does not offer random access, I think this algorithm will > have quadratic complexity because it needs to make a number of steps > proportional to n at each iteration. That's when copying may be the best implementation
