Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: binary search with arbitrary or random split
Posted:
Aug 7, 2012 8:22 PM
|
|
[Followups-to set since I don't think sci.math.num-analysis is topical
anymore.]
Ralph Hartley <hartley@aic.nrl.navy.mil> writes:
> On 07/24/2012 06:02 PM, Ben Bacarisse wrote:
>> What's going on here? If there were any down side at to using n/2 I can
>> see why one might consider alternatives -- even random ones (some people
>> do for quicksort, partitioning for example) --- but since n/2 is simple,
>> easy to calculate and optimal you can't be proposing an alternative.
>
> For searching a sorted list, I agree it doesn't make much sense, but
> consider sorting.
>
> Quicksort is a simple algorithm, and is close to O(n log(n)) for most
> inputs, but you can't use it when the input is chosen by an adversary
> because in worst case it is O(n^2).
>
> It is reasonable to use quicksort with each pivot point chosen
> randomly from a uniform distribution over the list. Unlike search,
> there is no consistently good choice, and any deterministic rule could
> be exploited to give O(n^2) cost *every* time.
That's not true. You can pick the median in O(n) time and that means
(if you're careful about a few other details) that you can have a
deterministic quicksort that is O(n log(n)) in the worst case. It's not
really practical, but that's not the point.
> Worst case is *still* O(n^2), but that's ok. What you really care
> about is that the average over your random choices is O(n log(n)),
> even for the worst possible input.
Depends on who "you" refers to! People interested in complexity theory
(this is comp.theory after all) are more likely to be interested in
worst-case analysis. This is not to deny the large body of theory on
probabilistic analysis -- it's just not the majority concern for
complexity theorists.
> I think you can actually say something slightly stronger than that,
> and show that the probability of very bad cases is small.
Yes, I think so too, but I don't know if there is an agreed measure for
"bad cases are sufficiently rare". The one paper cited in this thread,
proposed one, but I had trouble getting me head around it.
> It's OK to assume that your random choices follow a known
> distribution, you can make them so, but it can be a disaster to assume
> that the input array is anything but worse case.
>
> There are sorting algorithms with better worst case, but they are
> often not worth the trouble.
>
> None of this is *remotely* new.
No, but probabilistic measures of "almost always" O(f) are newer (if not
actually new). I'd be interested to hear from anyone who know what
recent thinking is about such things.
--
Ben.
|
|
|
|
