Komplexität < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 23:35 Di 10.03.2015 | | Autor: | evinda |
Hallo!!!
Der folgende Algorithmus SELECT wird gegeben.
1. Divide the n elements of the input array into [mm] \lfloor \frac{n}{5} \rfloor [/mm] groups of 5 elements each and at most one group made up of the remaining n [mm] \mod [/mm] 5 elements.
2. Find the median of each of the [mm] \lfloor \frac{n}{5} \rfloor [/mm] groups by first insertion-sorting the elements
of each group (of which there are at most 5) and then picking the median
from the sorted list of group elements.
3. Use SELECT recursively to find the median x of the [mm] \lfloor \frac{n}{5} \rfloor [/mm] medians found in step 2. (If there are an even number of medians, then by our convention, x is the lower median.)
4. Partition the input array around the median-of-medians x using the modified
version of PARTITION. Let k be one more than the number of elements on the
low side of the partition, so that x is the kth smallest element and there are n-k
elements on the high side of the partition.
5. If i=k, then return x. Otherwise, use SELECT recursively to find the ith
smallest element on the low side if i<k, or the i-k th smallest element on
the high side if i>k.
Ich habe gesehen dass der Kosten im Schritt 2, c [mm] \cdot \lceil \frac{n}{5} \rceil [/mm] ist. Wie kann der Kosten der sein obwohl wir die Insertion Sort anwenden?
Wie kann man den Kosten vom Schritt 5 finden?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Fr 13.03.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
