Das drittgrößte Element in der Anordnung der Größe finden (2^k +1) in n + 2k-3 Vergleiche

Question

"Finden Sie das drittgrößte Element in der Anordnung der Größe (2^k +1) in n + 2k-3 Vergleiche . "

Das war eine Frage, die ich in einer Algorithms-Kurs-Abschlussprüfung hatte, für die ich nicht alle Punkte bekommen habe. Ich bin immer noch nicht sicher, was die richtige Antwort nach einer gründlichen Suche im Internet ist.

Ich weiß, es ist eine erweiterte Version des gleichen Problems mit der zweitgrößten, aber die enge Vergleichsgrenze, die angefordert wurde, machte die Frage schwierig. Ich fand auch eine mathematische Erklärung, um das K-te Element zu finden here, aber es war zu kompliziert für mich zu verstehen.

bezeichne die Größe des Arrays zu n = 2^k + 1.

In der Prüfung selbst meine Antwort so etwas wie das war:

Wir werden einen Turnierbaum verwenden. Zuerst lassen wir ein beliebiges Element aus.
Dann bauen Sie den Baum, der aus 2^k Elementen bestehen wird. Daher gibt es K-Ebenen im Baum (log (2^k)).

Den Gewinner zu finden, wird uns n-2 Vergleiche nehmen.

Finden Sie das größte Element unter denen, die an den Gewinner verloren haben. (K-1 komp.)

Finden Sie das größte Element unter denen, die Verlierer des Finales verloren haben. (K-2 komp.)

Wir vergleichen diese und die, die wir am Anfang ausgelassen haben. (2 Komp.)

Der größte der 3 ist der drittgrößte des Arrays.

Gesamt Vergleiche: n - 2 + k - 1 + k - 2 + 2 = n + 2k - 3.

Ich habe 10 Punkte aus 25

I 2 Fehler gemacht habe. Der wichtigste ist, wenn das gewünschte Element im Unterbaum des Gewinners ist, wird meine Antwort falsch sein. Auch die richtige Antwort soll die zweitgrößte der 3 sein, die ich letztendlich am Ende verglichen habe.

Ein anderer Algorithmus I ist wie folgt bestimmt:
-Gebäude ein Turnierbaum und die Suche nach den Gewinner (n - 2)
-Finding die zweitgrößte durch alle Verlierer dem Gewinner zu vergleichen. (auch durch einen Turnierbaum) (k - 1)
-Die Antwort liegt unter den größten der Verlierer der zweitgrößten und der Verlierer derjenigen, die im Finale im ersten Baum verloren haben. (log (k + 1) + K-1-1)

-Diese Lösung setzt voraus, dass das Element, das wir weggelassen haben, nicht das größte im Array ist. Wenn es so ist, bin ich mir nicht sicher, wie es sich verhält. Auch habe ich die Anzahl der Vergleiche wahrscheinlich nicht richtig verstanden.

Ich bin glücklich herauszufinden, ob es einen besser erklärten Algorithmus gibt. Ich werde auch gerne wissen, ob es eine verallgemeinerte für L-ten größten gibt (K wurde genommen ..).

Dank im Voraus, Itay

Answer 1

1. ein Turnier Baum auf n Konstrukt - 1 = 2 k der Elemente, willkürlich gewählt. (n - 2 Vergleiche)

2. Am Blatt das Maximum der ausgewählten Elemente durch das nicht ausgewählte Element ersetzen. Erstelle den Turnierbaum neu. (k Vergleiche)

3. Nehmen Sie das Maximum der Elemente, die auf das neue Maximum verloren, wie im Algorithmus für die zweitgrößte. (k - 1 Vergleiche)

Ich überlasse den Korrektheitsbeweis als Übung.