Ich arbeite durch die Analyse des deterministischen Medianbefundes unter der Annahme, dass die Eingabe in drei Teile statt in fünf geteilt ist und die Frage ist: Wo bricht es zusammen?
der deterministische Medianwert-Algorithmus:
SELECT (i, n)
Teilen Sie die n Elemente in Gruppen von 5. Finde den Median jeder 5-Elemente-Gruppe per Auswendig.
Rekursiv SELECT den Median x von ⎣n / 5⎦ Gruppenmediane sollen der Drehpunkt sein.
Partition um den Drehpunkt x. Sei k = rank (x)
4.wenn i = k, dann gebe x zurück
elseif & lt; k
dann rekursiv SELECT die ith kleinstes Element im unteren Teil
sonst rekursiv SELECT die (i-k) th kleinstes Element im oberen Teil
Ich ging durch die Analyse des Algorithmus und ich glaube, dass Schritt 1 und 3 O (n) nehmen wird, wo es nur gerade konstante Zeit braucht, um den Median von 5 Elementen zu finden, und Schritt2 braucht T (n / 5) .so mindestens 3/10 der Elemente sind ≤ p und mindestens 3/10 der Anordnung ist ≥ p, daher wird Schritt 4 T (7n / 10) und wird die Wiederholung erhalten. T (n) ≤ cn + T (n / 5) + T (7n / 10), aber wenn ich die Elemente in gorup von 3 teile, sagen wir mal die 9 Elemente und teile sie in Gruppen so auf:
{1,2,10} {4,11,14}, {15,20,22}
Ich habe die Mediane 2,11,20 und die p = 11.
im Allgemeinen in Gruppe von fünf sagen wir g = n / 5 Gruppen und mindestens ⌈g / 2⌉ von ihnen (jene Gruppen, deren Median ≤ p ist) sind mindestens drei der fünf Elemente ≤ p. Die Gesamtzahl der Elemente ≤ p beträgt also mindestens 3⌈g / 2⌉ ≥ 3n / 10. ABER in der Gruppe von 3 können wir alle drei Elemente erhalten, die WENIGER als p sein können. und hier denke ich, dass der Algorithmus zusammenbrechen wird!
Habe ich die Idee richtig verstanden ???
In einer Gruppe von 3, wie für die Gruppen von 5, wird etwa die Hälfte der Gruppen ihr Median-Element kleiner als der Median-von-Median haben, so dass Sie in diesen Gruppen Elemente weniger als ihren Median ablegen können. In Ihrem Fall hat (1,2,10) einen Median von weniger als 11, also können Sie 1 und 2 verwerfen.
Wo ich denke, dass Dinge für Gruppen von 3 zusammenbrechen, ist in der Kalkulation. 3 (Boden (Boden (n / 5) / 2 - 2) was ungefähr 3n / 10 ist, wird 2 (Boden (Boden (n / 3) / 2 -2) oder so, was ungefähr n / 3 ist. Das bedeutet, dass 7n / 10 wird 2n / 3. floor (n / 5) wird floor (n / 3), statt 7cn / 10 + 2cn / 10 = 9cn / 10 erhalten Sie nur 2cn / 3 + cn / 3 = cn, und anstelle von T (n) & lt; = cn wirst du etwas haben, bei dem du die Begriffe, die nicht c betreffen, genau betrachten musst, und du könntest am Ende zeigen, dass es schließlich nicht linear ist.
Es sieht so aus, als würden Sie in jeder Phase der Rekursion tatsächlich etwas mehr Elemente wegwerfen, aber die Rekursion teilt die Menge der verbleibenden Arbeit durch 3, nicht 5, und dies ist nicht genug, um die Even-Zahl zu brechen.
Tags und Links algorithm selection complexity-theory big-o