N'abend
"- Jeder kennt die Schwierigkeit, in einer Werkbank zu einer Schraube die passende Mutter zu finden.
Wir gehen hierbei von n Schrauben unterschiedlicher Größe und von n korrespondierenden Muttern aus. -"
(a) Zeigen Sie, dass jeder Algorithmus zur Lösung des Problems Omega(n log n) viele Vergleiche benötigt.
Naja, knapp vorbei ist auch daneben.
Wenn ein absolut ungeordneter Haufen mit der beschriebenen Eigenschaft vorliegt, braucht's im
allerschlimmsten Fall 2(n-1) Vergleiche, um zu einer Schraube die passende Mutter zu finden.
Etwas anderes ist es, wenn n Schrauben von beliebiger Größe vorkommen können, oder wenn
n Schrauben beliebiger Größe und m Muttern von ebenfalls beliebiger Größe vorkommen können,
oder wenn zu allen Schrauben die passenden Muttern gefunden werden sollen, oder etcppuswusf.
Sollte allerdings eben das gemeint sein, nämlich zu allen Schrauben die passenden Muttern zu
finden, dann kann das durch eine Sortierung erfolgen, und das kann wiederum mit der
geforderten Lösung n log n zu tun haben.
Einen Beweis hierzu findest Du zB. hier - auf Seite 2 (Das Sortierproblem) -:
http://www.stud.uni-karlsruhe.de/~uagg/ … ium_01.pdf
(b) Geben Sie einen Algorithmus an, der für die Suche nach der kleinsten Schraube
und Ihrer passenden Mutter 2n-2 Vergleiche benötigt!
Das ist unter den gegebenen Bedingungen auch keine Hexerei - man müßte sich schon ziemlich
verrenken, wenn man mehr Vergleiche benötigen wollte.
Im Computer liegen die Schrauben und Muttern ja nun nicht als solche vor (sonst wärnse
locker, und das wollen wir nicht hoffen), sondern als irgendwelche Objecte, in diesem
Fall als solche, die jeweils zumindest eine Eigenschaft 'Größe' und eine Eigenschaft
'Männlein oder Weiblein' haben.
Im Fall Aufgabe (b) intressiert von diesen beiden Eigenschaften lediglich die erste, die Größe.
Man wähle einen beliebigen Gegenstand (Mutter oder Schraube, ist wurscht), und dann den nächsten.
Ist die Größe gleich, hat man das einzig existierende Paar dieser Größe gefunden - aufheben.
Ist die Größe ungleich, nimmt man für den weiteren Fortgang den Gegenstand, der kleiner ist.
Selbst wenn der vorletzte Gegenstand sich im letzten Vergleich (der logischerweise der höchstens
2(n-1)te sein kann) als kleiner als das bisher aufgehobene Paar entpuppt, so ist dieser vorletzte
Gegenstand das Gegenstück zum letzten verbliebenen Gegenstand - gemeinsam sind die also das kleinste Paar.
gruß
matho
