3 ms·
optimizing the average case is (in my experience) more common in optimization problems ... the author should say is that the number of floors required to break
by sampo 14y ago
optimizing the average case is (in my experience) more common in optimization problems ... the author should say is that the number of floors required to break the egg follows a uniform distribution
Then again, optimizing the worst case performance can be done without worrying about the underlying, and unknown, distribution of the lowest egg breaking drop.
If we start optimizing the average performance, then we need to assume something about the distribution (is it uniform? exponential? is there a bump in the middle?), and different distribution will have different optimal search strategies.
Looking at the worst case keeps the problem algorithmic, the version you propose would be more an exercise in probability calculus.
- SlowButEffectiv 14y agoThat may be true. Lunchbox's point holds true regardless: the problem statement is ambiguous, and is easy to correct so that it is not so.
- Fargren 14y agoWell, the standard in computer science is to optimize algorithms and discuss their performance for the worst case, so if we assume he's talking from a CS perspective, I find it natural to assume he's talking about that. There are a few exceptions, like QuickSort, but if some tells me to optimize some algorithm, I'll assume he's asking for optimization of the worst case unless he says otherwise or it's clear that the worse case is much rarer than some other case (I'd ask if I think that).
- dwc 14y agoThese considerations certainly exist in every day code as well. If you change the daily reporting process to have a worst case run time of 25 hours then you lose, even if the mean run time is cut in half.