Re: Benchmarks
On Nov 11, 4:30 pm, c...@tiac.net (Richard Harter) wrote:
I'd vaguely thought of something like this. But it doesn't
really help for creating a test case. Especially if you use
rand() to choose the pivot.
--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On Nov 11, 4:30 pm, c...@tiac.net (Richard Harter) wrote:
On Tue, 11 Nov 2008 06:15:20 -0800 (PST), James Kanze
<james.ka...@gm ail.comwrote:
On Nov 11, 11:54=A0am, Pete Becker <p...@versatile coding.com>
wrote:
wrote:
It's well understood what sort of input causes O(n^2) behavior.
Really? If I post a quicksort implementation here, could you
give me an algorithm which would generate the worst case? (I
guess there should a smiley here, because I don't think that
that's really what you meant. But just a half of one,
because I'd really like to find such. There are times where
you do want to test worst case.)
give me an algorithm which would generate the worst case? (I
guess there should a smiley here, because I don't think that
that's really what you meant. But just a half of one,
because I'd really like to find such. There are times where
you do want to test worst case.)
There is a published procedure that is very general that is one
the web somewhere that I can't find at the moment. The essence,
though, is that you use an oracle. It works like this: At each
step you tell me how you're going to pick your pivot, i.e., what
O(1) elements you are going to look at to choose the pivot. I
get to choose the values of the all of the rest. I choose them
so that they are all bigger (smaller) than your pivot. I don't
actually have to set their values until you look at them; I just
have to place bounds on them.
the web somewhere that I can't find at the moment. The essence,
though, is that you use an oracle. It works like this: At each
step you tell me how you're going to pick your pivot, i.e., what
O(1) elements you are going to look at to choose the pivot. I
get to choose the values of the all of the rest. I choose them
so that they are all bigger (smaller) than your pivot. I don't
actually have to set their values until you look at them; I just
have to place bounds on them.
really help for creating a test case. Especially if you use
rand() to choose the pivot.
--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Comment