Finding the Median of n Numbers in O(n) Time
Vložit
- čas přidán 30. 09. 2013
- The famous and surprising result that the median
of n numbers can be found in linear time, by a divide
and conquer method. Time analysis by setting up a recurrence relation and solving it. - Věda a technologie
Great lesson, thank you
What a great academic & entertaining lecture
Does anybody know the name of the lecturing professor if you don't mind?
amazing
Why does finding the median of the n/5 subgroups take O(1) for each group?
crypticnonsense because we know what n is equal to. It is equal to 5. So it is constant time for any sorting algorithm.
How did the n/5 sets become sorted from the smallest to the biggest ?
as mentioned, we found the median of each set but we haven't sorted the sets.
jmargieh You can sort the sets with any given sorting algorithm, but you should choose one that performs well with small arrays. Let's say Insertionsort or Selection sort. Since every group is of constant size
when do you sort the sets?
You split the array into sets (of say 5 numbers) & then sort it. For each sorted set, find the median of each sorted set & save it in a separate array. This new array would only have medians you found for each set. Now, sort the medians array to find its MEDIAN.
yes, you take group of fives and sort them recursively
@@charismaticaazim This new array you are sorting has n/5 medians, sorting that new array is just 5 times smaller than the original array which means you are dividing the running time by a constant. That definitely isnt linear.
Why 3n/10?
we split the n sized set into groups of 5. so how many "columns" do we got? n/5 now out of those we take half of them so n/5/2 =n/10 we take for each column only (in case of B) only the bottom 3 values cause they're higher so it's 3n/10
Adding to the previous comment:
Say in the average case we will have 4 set of 25% each (Set A < median, set B > median, and two other sets we don't know well). If we want to divide all the elements in the two sets A and B, what is the absolute minimum of elements that can go to set B? : 25% => 3n/10 (in this particular case). Inversely what is the maximum elements that can go to set A? : 75% => 7n/10 in other word , in the worst case scenario 75% of all elements will goes to set A during the partitions. remember time analysis is all about worst case.
There is no way to understand this so chaotically. Spend less time writing by using a presentation and more time explaining...
czcams.com/video/EzeYI7p9MjU/video.html
he actually explains it very well
This is typical of academia to take a simple idea make it much more complicated than it actually is.
Finding the median requires sorting at some point, unless someone can point me to an example where this isn't the case?
Once sorted, finding the median is pretty simple, especially if you use a convenient size for your small arrays, like five.
You missed the whole point.. sorting takes O(nlogn) time, whereas this solution takes O(n) time.
You are correct that it is trivial once you have a sorted list. Which takes Theta(nlgn) time. However, with this method you can on average find the median of an unsorted list in O(n) time. In the worst-case, this solution has a running time of Theta(n^2) just like Quicksort.