Die k-ten Quantile einer n-Elementmenge sind die k-1-Ordnungsstatistiken, die die sortierte Menge in k gleichgroße Mengen (innerhalb von 1) aufteilen. Geben Sie einen O (n lg k) -Zeitalgorithmus an, um die k-ten Quantile einer Menge aufzulisten.
Die einfache Lösung wäre, jedes k, 2k, 3k .. ik das kleinste Element auszuwählen, dessen Laufzeit O (kn) ist (k ruft zur Auswahl der Prozedur von O (n) auf). Aber das kann optimiert werden, um besser zu werden als O (kn). Nach dem Auffinden des Median der Mediane bei dem Index 'i' in der Auswahlprozedur machen wir den folgenden rekursiven Aufruf.
wenn der Index des Medians von Medianen i & gt; k, rekursiv wählen Sie das k-te kleinste Element im linken Teilarray A [0 ... i]
auswenn das i & lt; k, rekursiv das n - i + kth kleinste Element im rechten Teilarray A [i + 1 ... n] auswählen.
Können die obigen rekursiven Aufrufe wie unten geändert werden, was den Faktor 'k' auf 'log k' reduzieren würde?
wenn der Index des Medians von Medianen i & gt; k, rekursiv das k-te kleinste Element im linken Teilarray A [0 ... i] auswählen und auch rekursiv das n-k-te kleinste Element im rechten Teilarray A [i + 1 ... n] auswählen.
wenn das i & lt; k, rekursiv das n - i + k-te kleinste Element in dem rechten Teilarray A [i + 1 ... n] auswählen und auch rekursiv das k-te kleinste Element in dem linken Teilarray A [0 ... i] auswählen.
Der Hauptaufruf würde nur gewählt werden (A, k, n).
Beachten Sie, dass wir eine modifizierte PARTITION verwenden, der ein Index für den Pivot als letzten Eingabeparameter zugewiesen wird.
Sie beginnen mit KTH-QUANTILES(A, 1, n, 1, k-1, k)
Die Tiefe des Rekursionsbaums ist lg k , da die Partition um den Median der angegebenen Ordnungsstatistik (von i bis j) erstellt wird.
Auf jeder Ebene des Rekursionsbaums gibt es Θ (n) -Operationen, so dass die Laufzeit Θ (nlgk) ist.
Ich habe Ihren Ansatz nicht durchgegangen, aber das ist eine Frage von Int. zu Algorithmen von Cormen. Jedenfalls suchte ich selbst nach einer Lösung, und ich würde gerne meine Version des Algorithmus teilen. Versuchen Sie es zu widerlegen:
Ich gehe davon aus, dass wir einen O (n) -Statistikfindungsalgorithmus haben. So kann ich k-te Statistik in O (n) Zeit finden. Angenommen, ich sage, dass ich alle n / k k-ten Quantile finden werde, indem ich Teile-und-herrsche, so dass:
Wenn ich n 'Elemente habe, teile ich das Array in n' / 2 Teile auf, melde die Grenze k-te Quantile für beide n '/ 2 Partitionen. Und melden Sie die verbleibenden Quantile rekursiv. Im Wesentlichen mache ich nach der Partitionierung mit Median das rechteste Quantil aus dem linken Array, das linke Quantil aus der rechten Partition und führe nach dem Trimmen dieser Arrays den Algorithmus rekursiv aus. Meine Komplexitätsanalyse lautet:
T (n, k) = 2 · T (n / 2, k / 2) + O (n).
Dies stellt sich als O (nlogk) heraus, da der k / 2-Teil schneller konvergiert, obwohl Sie dies vielleicht noch rigoroser lösen möchten. Wir haben auch dieses n & gt; k verwendet (offensichtlich aufgrund des Problems. Beachten Sie, dass die Aufgabe, 2 Quantile zu extrahieren und das Array zu trimmen, in O (n)
erfolgtTags und Links algorithm