Finde die zwei kleinsten Elemente mit 1,5n - 2 Vergleichen?
Hallo allerseits,
heute habe ich in meiner Berufsschule die Aufgabe bekommen, in einem Array / Liste die zwei kleinsten Zahlen zu finden mit maximal 1,5n - 2 Vergleichen.
Mein erster Gedanke war, ein Sortieralgorithmus drüber laufen zu lassen und dann einfach die ersten beiden Elemente zu returnen. Das Problem ist, dass mir kein Algorithmus mit nur 1,5n -2 Vergleichen einfällt und ich keine andere effiziente Lösung finde.
Hat jemand eventuell eine gute Lösung? Gerne iterativ und rekursiv.
Danke!
2 Antworten
Bei ungeradem n musst du aufrunden (n=3 geht nur mit 3 Vergleichen).
Idee: Zerlege das Array in zwei Teile und bestimme die Minima a1<=a2 für den einen und b1<=b2 für den anderen. Jetzt reichen 2 weitere Vergleiche (a1 mit b1, dann je nach Ergebnis a1 mit b2 oder b1 mit a2).
Und wenn ein Teil immer die Länge 2 hat, kann man leicht sehen, dass der Algorithmus passt: Du brauchst für n+2 genau 3 Vergleiche mehr als für n.
Vielen Dank!
Habe vergessen zu sagen, dass n einfachheitshalber eine Zweierpotenz ist.
Gibt es noch einen Algorithmus, welcher evtl. nicht Divide & Conquer ist und durchaus schneller ist? Wäre die nächste Aufgabe bei der ich keine Ahnung habe wie ich sie lösen soll.
Ich liebe zwar Rekursion, aber hier erscheint mir eine Schleife sinnvoller:
def min2 ( x ):
assert len(x) >= 2
# Startwerte:
if x[0]<x[1]: # 1 Vergleich fuer n=2
m1, m2 = x[0], x[1]
else:
m1, m2 = x[1], x[0]
# paarweise erweitern:
for i in range(2, len(x)-1, 2):
# neues Paar:
if x[i]<x[i+1]: # (n-2)/2 Vergleiche
b1, b2 = x[i], x[i+1]
else:
b1, b2 = x[i+1], x[i]
# zusammenfassen:
if m1 < b1: # (n-2)/2 Vergleiche
# m1 bleibt
if m2 > b1: # (n-2)/2 Vergleiche HIER
m2 = b1
else:
# m1 <-- b1
if m1 < b2: # oder HIER
m1, m2 = b1, m1
else:
m1, m2 = b1, b2
# ggf. letztes Element untersuchen:
if len(x) % 2:
if m1 < x[-1]: # 1 Vergleich
if m2 > x[-1]: # und manchmal noch einer :-(
m2 = x[-1]
else:
m1, m2 = x[-1], m1
return m1, m2
Wenn Du die Elemente in der Schleife einzeln dazunimmst, kostet das 1-2 Vergleiche pro Element (siehe "letztes Element"). Im Worst-Case braucht man so leider 2 Vergleiche pro Element.
Durch die Paarbildung schaffst Du zwei neue Elemente mit 3 Vergleichen, also effektiv 3/2 Vergleiche pro Element.
In Dreierschritten braucht man je 3 Vergleiche für b1, b2 plus die beiden Vergleiche zum Zusammenfassen, also effektiv 5/3 Vergleiche pro Element. Das ist schlechter.
In Viererschritten braucht man 4 Vergleiche für b1, b2 plus die 2 zum Zusammenfassen, also effektiv wieder 6/4 Vergleiche pro Element (wie bei der Paarbildung).
Bei Fünferschritten müssten (v+2)/5<3/2 ⇔ v≤5 Vergleiche immer reichen, um die beiden kleinsten von 5 Elementen zu bestimmen. Ich befürchte, dass das nicht geht (auch nicht bei größeren Schritten), kann es aber nicht beweisen.
Alternativ könnte man überlegen, wie viele Vergleiche nötig sind, um die beiden kleinsten von 3 (oder mehr) Paaren a1≤a2, b1≤b2, c1≤c2 zu finden. Aber auch hier sehe ich schwarz.
Ich vermute daher, dass die nächste Aufgabe mit Nein beantwortet werden muss. Der Beweis dazu greift aber tief in die Trickkiste der theoretischen Informatik. Hast Du da vielleicht ein Theorem aus der Vorlesung, das man hier anwenden könnte?
Danke vielmals!
Habe jetzt an dem Ansatz 4 Stunden gehockt und es nicht hinbekommen (um überhaupt einen Ansatz zu finden noch wesentlich länger).
Die nächste Aufgabe werde ich dann einfach ohne Beweis verneinen, mir würde jetzt kein Theorem einfallen und ich habe mittlerweile auch echt keine Motivation mehr. Kann gerne die Lösung übernächste Woche mitteilen.
Aber wirklich Danke für die ausführliche Hilfe, hat mir den Tag etwas gerettet.
Schön, dass ich etwas helfen konnte!
Kann gerne die Lösung übernächste Woche mitteilen.
Darauf bin ich gespannt. Womöglich ist die Lösung so banal, dass es schon weh tut :-/
Also eine etwas verspätete Antwort aber ich habe die Lösung der Teilaufgabe b nun bekommen.
Ich verstehe die Lösung selber nicht ganz genau, deswegen schreibe ich sei einfach mal ab (bzw. hatte ich keine Motivation mehr mich mit ihr weiter zu beschäftigen) :
Alg.:
1. Falls n = 2 -> 1 Vgl.
2. n >2:
vergleichen a(2k-1) und a(2k) für k = 1, ..., n/2
--> o.B.d.A. sei a(2k) <= a(2k-1) (ggf. tauschen) -> n/2 Vergleiche
3. bestimme rekursiv min u. 2-min von
(a(2), a(4), ..., a(n/2)) ---> a(2i) <= a(2j)
4. Vgl. a(2i-1) <= a(2j)
wenn true:
a(2i) <= a(2i-1)
wenn false:
a(2i) <= a(2j)
Damit kam dann mein Prof durch Induktionsbeweis auf n + log(n) - 1 Vergleiche.
Ach du grüne Neune, ist das krass:
Dein Prof bildet Paare und verteilt die in einen kleinen und einen großen Topf, sodass jedes Element e im kleinen Topf einen Partner e'≥e im großen Topf hat (Schritt 2).
Nun bestimmt er m₁ (=a(2i)) und m₂ (=a(2j)) aus dem kleinen Topf (Schritt 3). m₁ ist sicher das globale Minimum, aber für den global zweit-kleinsten Wert kandidieren:
- m₂
- der kleinste Wert aus dem großen Topf
Wenn man das Minimum aus dem großen Topf sucht, versaut man sich die Laufzeit. Der Algorithmus macht sich stattdessen Folgendes zu nutze:
- Alle Werte im großen Topf – außer der Partner von m₁ – sind sicher ≥m₂, weil sie einen Partner ≥m₂ im ersten Topf haben.
Damit ist nur der Partner von m₁ (a(2i-1)) eine mögliche Konkurrenz für m₂. Das wird in Schritt 4 geprüft.
Das ist schon sehr dreist: Der große Topf bleibt total unsortiert, und der Partner von m₁ kann beliebig schlecht sein. Trotzdem reicht es aus, nur ihn zu betrachten, denn alle anderen aus dem großen Topf scheiden per Konstruktion aus.
Danke fürs Hochladen. Vielleicht kann ich es mal direkt anwenden, aber diesen Trick mit dem „Kandidat durch Ausschluss“ werde ich bestimmt noch irgendwo anders einsetzen können.
Ich könnte 2 mal linear scannen, dann läge ich aber höher. Bei etwa 2n.
Ja, leider zu hoch. Darauf würde ich keine Punkte bekommen
Ich sehe keienn Weg, wie man den Faktor von 1.5 garantieren kann. Auch ein Min-Heap benötigt mehr Vergleiche.
Ok, ich bekomme es doch noch nicht hin. Deinen Ansatz habe ich komplett verstanden und kann ihn nachvollziehen, aber wie bekomme ich das in Pseudo-Code oder Python umgesetzt?
Mein Ansatz war ein abgespecktes MergeSort zu schreiben um die Arrays in Tupel umzuwandeln, weiter weiß ich aber nicht.