Bestimmung des Medians < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:53 Mi 23.11.2011 | | Autor: | Blubie |
| Aufgabe | Gegeben seien n verschiedene Elemente [mm] x_{1},...,x_{n} [/mm] mit Gewichten [mm] w_{1},...,w_{n} \in \IR^{+}, [/mm] n ungerade. Der gewichtete Median ist das Element [mm] x_{k}, [/mm] das folgende Eigenschaften erfüllt:
[mm] \summe_{x_{i}
[mm] \summe_{x_{i}>x_{k}}^{}w_{i} [/mm] <= [mm] 0.5*\summe_{i=1}^{n}w_{i}
[/mm]
(a) Erläutern Sie, warum der Median der Elemente [mm] x_{1},...,x_{n} [/mm] gleich dem gewichteten Median der gleichen Elemente [mm] x_{1},...,x_{n} [/mm] mit Gewichten [mm] w_{i}=1/n [/mm] ist.
(b) Zeigen Sie, wie der gewichtete Median von Elementen in O(nlog(n)) Sschritten mittels Sortieren gefunden werden kann.
(c) Zeigen Sie, wie der gewichtete Median deterministisch in Theta(n) Schritten gefunden werden kann. Verändern sie dazu den in der Vorlesung vorgestellten select-Algorithmus. |
Hallo,
mir geht es eigentlich nur um Teil (c), den Rest kriege ich hin. Der select-Algorithmus ist ein Quicksort gewesen, mit dem man das k-kleinste Elemente bestimmen kann. Ich habe jedoch keine Ahnung wie man das in einer Laufzeit von n schaffen soll. (Ist hier eigentlich immer worst-case oder average-case gemeint?)
Ich bin für jeden Tipp sehr sehr dankbar.
Grüße
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 20:01 Mi 23.11.2011 | | Autor: | Blubie |
Hier scheint wohl auch keiner mit dem (c)-Teil klarzukommen :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 25.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Fr 25.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
