Wikipedia listet den Median-of-Medians-Algorithmus so auf, dass er @ erforderO(1) Hilfsraum.

In der Mitte des Algorithmus rufen wir jedoch ein Subarray der Größe r, ecursive aufn/5, um den Median der Mediane zu finden. Wenn dieser rekursive Aufruf zurückgegeben wird, verwenden wir den zurückgegebenen Median der Mediane als Pivot, um das Array zu partitionieren.

Drückt dieser Algorithmus nichtO(lg n) -Aktivierungsdatensätze im Laufzeitstapel als Teil der Rekursion? Soweit ich sehen kann, können diese rekursiven Aufrufe zum Auffinden aufeinanderfolgender Medianwerte von Medianwerten nicht nachträglich optimiert werden, da wir nach der Rückkehr der rekursiven Aufrufe zusätzliche Arbeit leisten. Daher scheint es, als ob dieser Algorithmus @ erforderO(lg n) Auxiliary Space (genau wie Quicksort, das Wikipedia als erfordert @ auflisteO(lg n) Auxiliary Space aufgrund des vom Runtime-Stack belegten Speicherplatzes.

ehlt mir etwas oder ist der Wikipedia-Artikel falsc

(Hinweis: Der rekursive Aufruf, auf den ich mich beziehe, istreturn select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) auf der Wikipedia-Seite.)