|
With tournament sort, get an nlogn – n/2 bound on the number of comparisons all together, if done right. What bound does this give you?
My Answer: With n = number of moves, a tournament sort algorithm uses O(n log n) comparisons. However, in order to approximate a bound, we know that it must be less than (n log n) by a factor of n. The comparison bound for a Heap Sort algorithm is O(n log n), while the Tournament Sort is a tighter version of the Heap sort, having a bound less than “n log n”.
The height of the tournament tree is log(n). However, we can reduce one of the initial keys because we ONLY need to re-compare the keys along the path from the key we just took out to the winner’s slot.
Thus, the height of the tree is log(n) – 1. This Sort initially does (n – 1) comparisons given “n” keys. So the total number of comparisons needed for the tournament sort turns out to be: (n – 1) + (n – 1)(log(n) – 1) = (n – 1)(1 + log(n) – 1) Which then simplifies to become: =(n – 1)log(n) = n log(n) – log(n)
---- My solution is incorrect by very little.... I know there are a couple applied students (or a graduate, I think) on this site. I don't know who they are, so if you come across this thread, please help me.
What is wrong with my bound? Why is does it come out to be smaller than it is supposed to? I need a tighter bound on the # of comparisons.
|
= (n – 1) + (log(n) – 3/2 + 1/n)*n = (n – 1) + n log(n) – 3n/2 + 1 = n log(n) – n/2
That is what probably should be right, but I cannot come up with an explanation for it... since I worked backwards to get there.
|
har har... i only come here to be confused.
|
you can extend your argument a bit to get the required bound.
you've already gotten most of the way there. you counted n-1 initial comparisons, and (logn - 1)(n-1) comparisons after that. now to extend it a bit... the (logn - 1)(n-1) can actually be reduced a bit.
to illustrate, suppose n = 4, like the MSL right now.
nal_ra (1) savior (3) silver (2) jju (4)
now we counted that as n-1 + (logn - 1)(n-1)... but the second part is counting more than we need, because once we've taken ra, silver, and savior out, there's no need to do a comparison for jju in the finals when it's his turn, because his contestants have already been removed from consideration.
so in general, think about each of the matches other than at the leaf nodes. so if n=16... this includes the round of 8, the round of 4, and round of 2. when we're doing the second-step of tournament sort for the WORST player that was competing for this spot... we don't need to do a comparison because all the other players better than him have already been removed from contention. so we're overcounting by the number of matches after the initial round by at least (n/2 - 1)
so you can subtract off (n/2 - 1) from your initial (n-1) + (logn - 1)(n-1) = nlogn - logn leaving you with nlogn - n/2 - logn + 1
which is <= nlog - n/2 whenever n >=2
edit: this could be written up more elegantly if you clean up the way you deal with the initial round of comparisons (ro16) in the (logn - 1)(n-1) and special case analysis
|
thedeadhaji
39487 Posts
o shit someone answered it.
|
ANyone care to tell me what math is this? Stats? xD
|
Osaka27059 Posts
(i didnt close this, no idea why it was bumped but...)
I like this one because it has room for discussion and most of the work is already done. It makes me smile
|
MURICA15980 Posts
Yeah, I saw it and didn't close it. It actually demonstrated intelligent effort.
|
Netherlands13554 Posts
Didn't close it either :p
|
|
|
|