
Kapitel 4
Suchen, Sortieren und Algorithmenanalyse
Skript Informatik · Grundkurs
Notebooks in diesem Kapitel NB04
Alle Notebooks der Klasse · Das grüne Schild an einer Überschrift zeigt, zu welchem Notebook der Abschnitt gehört.
PDF zum Ausdrucken zusammenstellen
Kreuze an, welche Abschnitte du brauchst. Die PDF hat dasselbe Aussehen wie das gedruckte Skript, mit Platz zum Schreiben. Jeden Abschnitt gibt es auch einzeln unter seiner Überschrift, das ganze Kapitel unten auf der Seite.
Zwanzig Zahlen der Größe nach zu ordnen ist keine Kunst. Sie können es, ein Grundschulkind kann es, und Ihr Rechner sowieso. Interessant wird die Aufgabe erst durch drei Fragen, die dahinter liegen: Wie genau gehen Sie dabei vor? Gibt es ein Verfahren, das besser ist als Ihres? Und wie weist man so etwas nach, ohne einfach zwei Programme laufen zu lassen und zu stoppen?
Dieses Kapitel beantwortet die Fragen in dieser Reihenfolge. Zuerst das Suchen — die Aufgabe, derentwegen überhaupt sortiert wird. Dann vier Sortierverfahren, die dieselbe Aufgabe auf sehr verschiedene Weise lösen. Dann das Werkzeug, mit dem man sie vergleicht, ohne Rechner und Stoppuhr zu bemühen. Und am Ende die Frage, die die Informatik von der Programmierung trennt: Gibt es Probleme, für die es überhaupt kein Verfahren gibt?
Am Ende dieses Kapitels können Sie
- die sequentielle und die binäre Suche auf einem Feld erklären, von Hand durchführen und programmieren,
- begründen, warum die binäre Suche ein sortiertes Feld voraussetzt,
- die Verfahren Selection Sort, Insertion Sort, Bubble Sort und Quicksort erklären, von Hand durchführen und programmieren,
- das Prinzip „Teile und herrsche” und den Zusammenhang zur Rekursion beschreiben,
- die Zeitkomplexität eines Algorithmus abschätzen und in der Landau-Notation angeben,
- bester, schlechtester und mittlerer Fall an einem Beispiel unterscheiden,
- begründen, warum kein allgemeines Sortierverfahren schneller als sein kann,
- erklären, was ein Test über die Korrektheit eines Programms aussagt — und was nicht,
- entscheidbare, partiell entscheidbare und unentscheidbare Probleme unterscheiden,
- den Beweis zur Unentscheidbarkeit des Halteproblems nachvollziehen und seine Bedeutung für die Praxis erklären.
4.1Suchen
Diesen Abschnitt als PDF (S. 2–5)
Sortiert wird selten um des Sortierens willen. Sortiert wird, damit man nachher schneller findet. Deshalb steht das Suchen hier vorn.
Die Aufgabe: In einem Feld mit Einträgen soll festgestellt werden, ob ein gesuchter Wert vorkommt — und wenn ja, an welcher Position.
Alle Pascal-Fassungen in diesem Kapitel arbeiten auf demselben
Feldtyp. Er wird einmal vereinbart und danach stillschweigend
vorausgesetzt; die Positionen laufen von 1 bis n:
type
TFeld = array [1..100] of integer;In Python übernimmt eine gewöhnliche Liste diese Rolle; dort laufen
die Positionen von 0 bis len(feld) - 1.
4.1.1Sequentielle Suche
Das naheliegende Verfahren: von vorn durchgehen, bis der Wert auftaucht oder das Feld zu Ende ist.
Python
def sequentielle_suche(feld, ziel):
for pos in range(len(feld)):
if feld[pos] == ziel:
return pos
return -1 # nicht gefundenObject Pascal
function SequentielleSuche(var feld: TFeld; n, ziel: Integer): Integer;
var
pos: Integer;
begin
Result := -1;
for pos := 1 to n do
if feld[pos] = ziel then
begin
Result := pos;
Exit; { gefunden, Schluss }
end;
end;Der Aufwand ist leicht abzuzählen:
| Fall | Vergleiche |
|---|---|
| bester Fall (Wert steht vorn) | 1 |
| schlechtester Fall (Wert steht hinten oder fehlt) | |
| mittlerer Fall (Wert ist vorhanden) | etwa |
Die sequentielle Suche hat einen großen Vorzug: Sie stellt keine Bedingung an das Feld. Es darf unsortiert sein, und sie funktioniert auf einer verketteten Liste ebenso wie auf einem Feld.
4.1.2Binäre Suche
Ist das Feld sortiert, geht es sehr viel schneller. Jeder kennt das Verfahren vom Nachschlagen im Telefonbuch: Man schlägt in der Mitte auf und weiß danach, in welcher Hälfte weitergesucht werden muss.
Man betrachtet den Eintrag in der Mitte des Suchbereichs.
- Ist er der gesuchte Wert, ist man fertig.
- Ist er größer, wird in der linken Hälfte weitergesucht.
- Ist er kleiner, wird in der rechten Hälfte weitergesucht.
Das wiederholt man, bis der Wert gefunden oder der Suchbereich leer ist.
Position: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Feld: 3 7 12 18 23 29 34 41 47 52 58 63 71 76 84 92
| Schritt | links | rechts | Mitte | Wert dort | Vergleich | weiter |
|---|---|---|---|---|---|---|
| 1 | 1 | 16 | 8 | 41 | 47 > 41 | rechts |
| 2 | 9 | 16 | 12 | 63 | 47 < 63 | links |
| 3 | 9 | 11 | 10 | 52 | 47 < 52 | links |
| 4 | 9 | 9 | 9 | 47 | gefunden | — |
Vier Vergleiche. Die sequentielle Suche hätte neun gebraucht.
Python
def binaere_suche(feld, ziel):
links = 0
rechts = len(feld) - 1
while links <= rechts:
mitte = (links + rechts) // 2
if feld[mitte] == ziel:
return mitte
if feld[mitte] < ziel:
links = mitte + 1 # linke Hälfte entfällt
else:
rechts = mitte - 1 # rechte Hälfte entfällt
return -1Object Pascal
function BinaereSuche(var feld: TFeld; n, ziel: Integer): Integer;
var
links, rechts, mitte: Integer;
begin
links := 1;
rechts := n;
Result := -1;
while links <= rechts do
begin
mitte := (links + rechts) div 2;
if feld[mitte] = ziel then
begin
Result := mitte;
Exit;
end;
if feld[mitte] < ziel then
links := mitte + 1
else
rechts := mitte - 1;
end;
end;Die binäre Suche setzt ein sortiertes Feld voraus. Auf einem unsortierten Feld liefert sie keine Fehlermeldung — sie liefert eine falsche Antwort, und zwar lautlos. Das ist die unangenehmste Sorte Fehler.
4.1.3Was die Halbierung bringt
Jeder Vergleich halbiert den Suchbereich. Nach Schritten bleiben noch etwa Einträge übrig; die Suche endet, wenn dieser Rest 1 erreicht. Daraus ergibt sich die Zahl der Schritte: etwa .
| sequentiell (schlechtester Fall) | binär (schlechtester Fall) | |
|---|---|---|
| 16 | 16 | 5 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
| 1 000 000 000 | 1 000 000 000 | 30 |
titel: Binäre Suche im sortierten Feld werte: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 gesucht: 23
Suchen Sie im Bedienfeld auch nach einer Zahl, die nicht vorkommt — etwa 40. Die Suche endet trotzdem nach wenigen Schritten, und der Zähler zeigt, wie viele die sequentielle Suche gebraucht hätte.
Eine Milliarde Einträge, dreißig Vergleiche. Eine Verdoppelung der Datenmenge kostet die binäre Suche einen einzigen Vergleich zusätzlich — die sequentielle Suche dagegen doppelt so viele.
Das ist der Grund, warum Sortieren sich lohnt: Einmal sortieren, danach beliebig oft billig suchen.
Suchen Sie im Feld oben die 71 und die 50. Notieren Sie jeden Schritt wie in der Tabelle:
- Führen Sie die binäre Suche nach der 92 von Hand durch. Wie viele Vergleiche brauchen Sie — und warum ist es einer mehr als bei der 47?
- Suchen Sie die 50, die nicht im Feld steht. Woran merkt das Verfahren, dass es abbrechen muss?
- Programmieren Sie beide Verfahren und lassen Sie sie die Zahl der Vergleiche mitzählen. Prüfen Sie die Tabelle aus Abschnitt 4.1.3 für nach.
- Begründen Sie: Ab welcher Zahl von Suchvorgängen lohnt es sich, ein unsortiertes Feld erst zu sortieren, statt sequentiell zu suchen?
- Schreiben Sie die binäre Suche rekursiv (siehe Abschnitt 3.1). Was ist der Basisfall?
4.2Sortieralgorithmen
Diesen Abschnitt als PDF (S. 6–14)
4.2.1Zwei Versuche zum Einstieg
Jede Gruppe erhält zwanzig gemischte Karten und bringt sie in die richtige Reihenfolge.
Notieren Sie anschließend in zwei, drei Sätzen, wie Sie dabei vorgegangen sind — nicht was herausgekommen ist.
Unser Vorgehen beim Sortieren der Karten:
Vergleichen Sie die Beschreibungen in der Klasse. Fast alle lassen sich einem der vier Verfahren zuordnen, die in diesem Abschnitt folgen. Sie unterscheiden sich nicht im Ergebnis — sortiert ist sortiert — sondern im Aufwand.
Vor Ihnen stehen acht 3D-gedruckte Zylinder. Sie sind gleich groß und sehen gleich aus, wurden aber mit unterschiedlicher Dichte gedruckt und sind deshalb verschieden schwer. Ordnen Sie die Zylinder vom leichtesten zum schwersten.
Dafür gilt eine Einschränkung: Das einzige erlaubte Hilfsmittel ist die Balkenwaage, und sie beantwortet immer nur eine Frage — welcher von genau zwei Zylindern ist der schwerere. Sie dürfen nicht abwiegen, nicht schätzen, nicht in die Hand nehmen.
Machen Sie für jede Wägung einen Strich und versuchen Sie, mit möglichst wenigen auszukommen.
Strichliste der Wägungen — insgesamt: ……..
Der Unterschied zwischen beiden Versuchen ist der eigentliche Inhalt dieses Kapitels. Bei den Karten sehen Sie alle Werte auf einen Blick; „such die kleinste Karte” ist für Sie eine einzige Handlung. Ein Rechner kann das nicht. Er sieht das Feld nie als Ganzes, sondern kann immer nur zwei Einträge miteinander vergleichen — genau wie die Waage. Was bei den Karten unsichtbar bleibt, wird an der Waage zur zählbaren Arbeit.
Deshalb messen wir den Aufwand eines Sortierverfahrens nicht in Sekunden, sondern in Vergleichen.
Ein Sortierverfahren verändert ein Feld nur über zwei Operationen: vergleichen und vertauschen. Wenn wir im Folgenden vom Aufwand sprechen, zählen wir genau diese beiden — nicht Sekunden. Sekunden hängen vom Rechner ab, Vergleiche nur vom Verfahren.
Halten Sie Ihre Strichliste fest. Mit acht Zylindern braucht man mindestens 16 Wägungen; kein Verfahren der Welt kommt mit weniger aus. Warum das so ist und wie man solche Grenzen ausrechnet, klärt Abschnitt 4.3 — vergleichen Sie Ihr Ergebnis dann noch einmal mit dieser Zahl.
Alle vier Verfahren arbeiten im Folgenden auf derselben Ausgangslage, damit Sie die Abläufe vergleichen können:
7 2 9 4 11 1 8 5 12 3 10 6
Jedes Verfahren wird dreifach angegeben: als Pseudocode, in Python
und in Object Pascal (Delphi/Lazarus). Die Pascal-Fassungen arbeiten auf
dem Feld feld: TFeld aus Abschnitt 4.1 mit den Positionen 1
bis n.
4.2.2Sortieren durch direktes Auswählen (Selection Sort)
Idee. An der ersten Position muss die kleinste Zahl stehen. Also durchsucht man das ganze Feld nach dem Minimum und vertauscht es mit dem ersten Element. Danach ist die erste Position endgültig besetzt, und man wiederholt das Verfahren mit dem Rest des Feldes.
7 2 9 4 11 1 8 5 12 3 10 6 Ausgangslage
1 2 9 4 11 7 8 5 12 3 10 6 Minimum 1 mit der 7 getauscht
1 2 9 4 11 7 8 5 12 3 10 6 2 steht bereits richtig
1 2 3 4 11 7 8 5 12 9 10 6 3 mit der 9 getauscht
1 2 3 4 11 7 8 5 12 9 10 6 4 steht bereits richtig
1 2 3 4 5 7 8 11 12 9 10 6 5 mit der 11 getauscht
1 2 3 4 5 6 8 11 12 9 10 7 6 mit der 7 getauscht
1 2 3 4 5 6 7 11 12 9 10 8 7 mit der 8 getauscht
1 2 3 4 5 6 7 8 12 9 10 11 8 mit der 11 getauscht
1 2 3 4 5 6 7 8 9 12 10 11 9 mit der 12 getauscht
1 2 3 4 5 6 7 8 9 10 12 11 10 mit der 12 getauscht
1 2 3 4 5 6 7 8 9 10 11 12 11 mit der 12 getauscht
Auffällig ist, wie wenig sich pro Zeile ändert: Höchstens zwei Zahlen wechseln den Platz. Selection Sort tauscht sparsam — aber es sucht teuer, denn für jede Position wird der gesamte Rest durchgesehen.
Algorithmus
für i von 1 bis n-1:
minpos := i
für j von i+1 bis n:
wenn feld[j] < feld[minpos] dann minpos := j
vertausche feld[i] und feld[minpos]
Python
def selection_sort(feld):
n = len(feld)
for i in range(n - 1):
minpos = i
for j in range(i + 1, n):
if feld[j] < feld[minpos]:
minpos = j
feld[i], feld[minpos] = feld[minpos], feld[i]
return feldObject Pascal
procedure SelectionSort(var feld: TFeld; n: integer);
var i, j, minpos, hilf: integer;
begin
for i := 1 to n - 1 do
begin
minpos := i;
for j := i + 1 to n do
if feld[j] < feld[minpos] then
minpos := j;
hilf := feld[i]; { Ringtausch ueber Hilfsvariable }
feld[i] := feld[minpos];
feld[minpos] := hilf;
end;
end;- Führen Sie Selection Sort von Hand auf
9 4 7 1 5 2durch und notieren Sie jede Zwischenzeile. - Zählen Sie: Wie viele Vergleiche braucht Selection Sort bei Elementen? Stellen Sie eine Formel auf. (Hinweis: Vergleiche im ersten Durchlauf, im zweiten, …)
- Programmieren Sie das Verfahren so, dass nach jedem Durchlauf der Zustand des Feldes ausgegeben wird. Behalten Sie diese Ausgabefunktion bei — die folgenden Verfahren nutzen sie ebenfalls.
- Begründen Sie: Selection Sort braucht immer gleich viele Vergleiche, egal wie die Eingabe aussieht. Welchen Vorteil und welchen Nachteil hat das?
4.2.3Sortieren durch direktes Einfügen (Insertion Sort)
Idee. So sortieren die meisten Menschen ein Blatt Spielkarten: Man nimmt eine Karte heraus und schiebt sie an der richtigen Stelle in den bereits sortierten Teil ein. Der Anfang des Feldes ist dabei immer sortiert und wächst mit jedem Schritt um ein Element.
7 2 9 4 11 1 8 5 12 3 10 6 Ausgangslage, die 7 gilt als sortiert
2 7 9 4 11 1 8 5 12 3 10 6 2 vor die 7 geschoben
2 7 9 4 11 1 8 5 12 3 10 6 9 bleibt, wo sie ist
2 4 7 9 11 1 8 5 12 3 10 6 4 zwischen 2 und 7 eingefügt
2 4 7 9 11 1 8 5 12 3 10 6 11 bleibt, wo sie ist
1 2 4 7 9 11 8 5 12 3 10 6 1 ganz nach vorn
1 2 4 7 8 9 11 5 12 3 10 6 8 zwischen 7 und 9
1 2 4 5 7 8 9 11 12 3 10 6 5 zwischen 4 und 7
1 2 4 5 7 8 9 11 12 3 10 6 12 bleibt, wo sie ist
1 2 3 4 5 7 8 9 11 12 10 6 3 zwischen 2 und 4
1 2 3 4 5 7 8 9 10 11 12 6 10 zwischen 9 und 11
1 2 3 4 5 6 7 8 9 10 11 12 6 zwischen 5 und 7
Hier ist es umgekehrt zu Selection Sort: Gesucht wird wenig, denn die Suche bricht ab, sobald der Platz gefunden ist. Dafür wird viel geschoben.
Algorithmus
für i von 2 bis n:
wert := feld[i]
j := i
solange j > 1 und feld[j-1] > wert:
feld[j] := feld[j-1] (nach rechts schieben)
j := j - 1
feld[j] := wert
Python
def insertion_sort(feld):
for i in range(1, len(feld)):
wert = feld[i]
j = i
while j > 0 and feld[j - 1] > wert:
feld[j] = feld[j - 1]
j -= 1
feld[j] = wert
return feldObject Pascal
procedure InsertionSort(var feld: TFeld; n: integer);
var i, j, wert: integer;
begin
for i := 2 to n do
begin
wert := feld[i];
j := i;
while (j > 1) and (feld[j - 1] > wert) do
begin
feld[j] := feld[j - 1]; { nach rechts schieben }
j := j - 1;
end;
feld[j] := wert;
end;
end;- Führen Sie Insertion Sort von Hand auf
9 4 7 1 5 2durch. - Wie verhält sich das Verfahren, wenn das Feld bereits sortiert ist? Wie viele Vergleiche sind dann nötig? Vergleichen Sie mit Selection Sort.
- Programmieren Sie Insertion Sort. Zählen Sie Vergleiche und Verschiebungen mit.
- Warum steht in der Bedingung
j > 1 und feld[j-1] > wertdie Prüfung aufj > 1vor dem Vergleich? Was passiert bei umgekehrter Reihenfolge? Prüfen Sie außerdem nach, was die Delphi-Einstellung Complete Boolean Evaluation ({$B+}bzw.{$B-}) damit zu tun hat.
4.2.4Sortieren durch Vertauschen (Bubble Sort)
Idee. Das einfachste Verfahren überhaupt: Man vergleicht benachbarte Zahlen und vertauscht sie, wenn die größere vorn steht. Das wiederholt man so lange, bis ein kompletter Durchlauf ohne Vertauschung bleibt. Große Zahlen steigen dabei wie Blasen nach hinten — daher der Name.
7 2 9 4 11 1 8 5 12 3 10 6 Ausgangslage
2 7 4 9 1 8 5 11 3 10 6 12 nach Durchlauf 1: die 12 steht hinten
2 4 7 1 8 5 9 3 10 6 11 12 nach Durchlauf 2: die 11 sitzt
2 4 1 7 5 8 3 9 6 10 11 12 nach Durchlauf 3
2 1 4 5 7 3 8 6 9 10 11 12 nach Durchlauf 4
1 2 4 5 3 7 6 8 9 10 11 12 nach Durchlauf 5
1 2 4 3 5 6 7 8 9 10 11 12 nach Durchlauf 6
1 2 3 4 5 6 7 8 9 10 11 12 nach Durchlauf 7
1 2 3 4 5 6 7 8 9 10 11 12 Durchlauf 8 ohne Vertauschung: fertig
Nach jedem Durchlauf steht mindestens eine weitere Zahl endgültig am Ende. Der nächste Durchlauf darf deshalb einen Schritt früher aufhören — das spart die Hälfte der Vergleiche und ist in Aufgabe 16 gefragt.
Algorithmus
wiederhole
getauscht := falsch
für j von 1 bis n-1:
wenn feld[j] > feld[j+1] dann
vertausche feld[j] und feld[j+1]
getauscht := wahr
bis getauscht = falsch
Python
def bubble_sort(feld):
n = len(feld)
for i in range(n - 1):
getauscht = False
for j in range(n - 1 - i):
if feld[j] > feld[j + 1]:
feld[j], feld[j + 1] = feld[j + 1], feld[j]
getauscht = True
if not getauscht:
break
return feldObject Pascal
procedure BubbleSort(var feld: TFeld; n: integer);
var i, j, hilf: integer;
getauscht: boolean;
begin
for i := 1 to n - 1 do
begin
getauscht := false;
for j := 1 to n - i do
if feld[j] > feld[j + 1] then
begin
hilf := feld[j];
feld[j] := feld[j + 1];
feld[j + 1] := hilf;
getauscht := true;
end;
if not getauscht then
break;
end;
end;- Führen Sie Bubble Sort von Hand auf
5 3 4 1 2durch. Wie viele Durchläufe brauchen Sie? - Warum ist die Abfrage
getauschtsinnvoll? Konstruieren Sie eine Eingabe, bei der sie viel spart, und eine, bei der sie nichts bringt. - Programmieren Sie Bubble Sort in zwei Fassungen: einmal mit fester
Schleifengrenze, einmal mit dem verkürzten Bereich
n-1-i. Zählen Sie jeweils die Vergleiche und vergleichen Sie. - Bubble Sort und Selection Sort brauchen etwa gleich viele Vergleiche, Bubble Sort aber deutlich mehr Vertauschungen. Begründen Sie das anhand der Abläufe oben.
4.2.5Quicksort
Quicksort gehört zu den höheren Sortierverfahren und steht nur im LK-Lehrplan (dort zusammen mit Mergesort). Verbindlich für den Grundkurs sind Bubble-, Selection- und Insertion Sort. Quicksort taucht auch im Vergleich in Abschnitt 4.3.3 wieder auf.
Die ersten drei Verfahren arbeiten das Feld Position für Position ab. Quicksort verfolgt eine andere Strategie: Teile und herrsche (divide and conquer). Statt das Problem direkt zu lösen, zerlegt man es in zwei kleinere Probleme derselben Art — und wendet darauf dasselbe Verfahren an. Quicksort ist damit rekursiv.
Idee. Man wählt ein Element als Pivot (hier: das letzte des Bereichs) und sortiert das Feld so um, dass links vom Pivot nur kleinere und rechts nur größere Zahlen stehen. Das Pivot steht danach an seiner endgültigen Position — ohne dass der Rest sortiert wäre. Anschließend behandelt man den linken und den rechten Teilbereich auf dieselbe Weise.
7 2 9 4 11 1 8 5 12 3 10 6 Ausgangslage
2 4 1 5 3 6 8 7 12 11 10 9 Pivot 6 aus [1..12] landet auf Position 6
2 1 3 5 4 6 8 7 12 11 10 9 Pivot 3 aus [1..5] landet auf Position 3
1 2 3 5 4 6 8 7 12 11 10 9 Pivot 1 aus [1..2] landet auf Position 1
1 2 3 4 5 6 8 7 12 11 10 9 Pivot 4 aus [4..5] landet auf Position 4
1 2 3 4 5 6 8 7 9 11 10 12 Pivot 9 aus [7..12] landet auf Position 9
1 2 3 4 5 6 7 8 9 11 10 12 Pivot 7 aus [7..8] landet auf Position 7
1 2 3 4 5 6 7 8 9 11 10 12 Pivot 12 aus [10..12] landet auf Position 12
1 2 3 4 5 6 7 8 9 10 11 12 Pivot 10 aus [10..11] landet auf Position 10
Acht Zerlegungen statt elf Auswahlrunden bei Selection Sort — und in jeder Zeile ist deutlich mehr in Bewegung. Der Grund: Jede Zerlegung halbiert die Arbeit ungefähr, statt sie nur um ein Element zu verkürzen.
Algorithmus
quicksort(links, rechts):
wenn links < rechts:
p := zerlege(links, rechts)
quicksort(links, p-1) (linker Rekursionsaufruf)
quicksort(p+1, rechts) (rechter Rekursionsaufruf)
zerlege(links, rechts):
pivot := feld[rechts]
i := links - 1
für j von links bis rechts-1:
wenn feld[j] <= pivot:
i := i + 1
vertausche feld[i] und feld[j]
vertausche feld[i+1] und feld[rechts]
gib i+1 zurück
Python
def quicksort(feld, links=0, rechts=None):
if rechts is None:
rechts = len(feld) - 1
if links < rechts:
p = zerlege(feld, links, rechts)
quicksort(feld, links, p - 1)
quicksort(feld, p + 1, rechts)
return feld
def zerlege(feld, links, rechts):
pivot = feld[rechts]
i = links - 1
for j in range(links, rechts):
if feld[j] <= pivot:
i += 1
feld[i], feld[j] = feld[j], feld[i]
feld[i + 1], feld[rechts] = feld[rechts], feld[i + 1]
return i + 1Object Pascal
function Zerlege(var feld: TFeld; links, rechts: integer): integer;
var pivot, i, j, hilf: integer;
begin
pivot := feld[rechts];
i := links - 1;
for j := links to rechts - 1 do
if feld[j] <= pivot then
begin
i := i + 1;
hilf := feld[i];
feld[i] := feld[j];
feld[j] := hilf;
end;
hilf := feld[i + 1]; { Pivot an seinen Platz }
feld[i + 1] := feld[rechts];
feld[rechts] := hilf;
Result := i + 1;
end;
procedure QuickSort(var feld: TFeld; links, rechts: integer);
var p: integer;
begin
if links < rechts then
begin
p := Zerlege(feld, links, rechts);
QuickSort(feld, links, p - 1); { linker Rekursionsaufruf }
QuickSort(feld, p + 1, rechts); { rechter Rekursionsaufruf }
end;
end;Rekursion braucht zwei Dinge: einen
Rekursionsschritt, der das Problem verkleinert, und
einen Abbruchfall, der ohne weiteren Aufruf auskommt.
Bei Quicksort ist der Abbruchfall die Bedingung
links < rechts — ein Bereich mit einem oder null
Elementen ist bereits sortiert.
- Zerlegen Sie
8 3 11 5 1 9 4von Hand mit dem letzten Element als Pivot. Wo landet das Pivot? - Zeichnen Sie für das Beispiel oben einen Baum der Rekursionsaufrufe. Wie tief ist er?
- Programmieren Sie Quicksort. Lassen Sie nach jeder Zerlegung das Feld ausgeben.
- Was passiert, wenn das Feld bereits sortiert ist und man immer das
letzte Element als Pivot wählt? Rechnen Sie den Fall für
1 2 3 4 5durch. (Diese Beobachtung wird in Abschnitt 4.3 wichtig.) - Ändern Sie Ihr Programm so, dass als Pivot das mittlere Element gewählt wird. Prüfen Sie, ob das Problem aus Aufgabe 21 verschwindet.
4.2.6Werkzeug: die Sortier-Visualisierung
Die Abläufe oben stehen still auf Papier. In der Webfassung dieses Skripts steht an dieser Stelle der Sortier-Visualizer: Sie können die Anzahl der Elemente einstellen, die Ausgangslage wählen, Schritt für Schritt vorgehen oder im Modus Rennen die Verfahren gegeneinander antreten lassen. Vergleiche und Vertauschungen werden mitgezählt, und daneben steht der Quelltext des gerade laufenden Verfahrens.
titel: Sortier-Visualizer datei: sortier-visualizer.html hoehe: 1250
- Lassen Sie im Modus Rennen alle vier Verfahren auf 40 zufälligen Zahlen antreten. Notieren Sie die Vergleichszahlen. In welcher Reihenfolge werden die Verfahren fertig?
- Wiederholen Sie das Rennen mit der Ausgangslage fast sortiert. Ein Verfahren gewinnt jetzt deutlich, ein anderes verliert stark. Welche? Erklären Sie beides mit den Abläufen aus Abschnitt 4.2.
- Stellen Sie umgekehrt sortiert ein und beobachten Sie Quicksort. Verbinden Sie Ihre Beobachtung mit Ihrem Ergebnis aus Aufgabe 21.
- Verdoppeln Sie die Anzahl der Elemente von 20 auf 40 und notieren Sie die Vergleiche für Selection Sort. Um welchen Faktor wächst die Zahl? Was sagt das über den Zusammenhang zwischen und dem Aufwand?
4.3Algorithmenanalyse
Diesen Abschnitt als PDF (S. 15–17)
4.3.1Zuverlässigkeit
Die wichtigste Forderung an ein Programm ist nicht Schnelligkeit, sondern dass es tut, was es soll. Dass auch jahrelang scheinbar zuverlässige Software plötzlich falsche Ergebnisse liefert, zeigen diese Fälle:
- Ariane 5, 1996. Vierzig Sekunden nach dem Start zerstörte sich die Rakete selbst. Ursache war eine aus der Ariane 4 übernommene Routine, die eine 64-Bit-Gleitkommazahl in eine 16-Bit-Ganzzahl umwandelte. Für die schnellere Ariane 5 war der Wert zu groß. Der Code funktionierte fehlerfrei — nur für die falsche Rakete.
- Jahr-2000-Problem. Um teuren Speicherplatz zu sparen, wurde die Jahreszahl jahrzehntelang zweistellig gespeichert. Datumsvergleiche konnten 1900 und 2000 nicht unterscheiden. Die weltweite Umstellung kostete geschätzt mehrere hundert Milliarden Dollar.
- Boeing 737, Startabbruch bei 60 Knoten. Das Startprogramm behandelte die Fälle und — nicht aber . Meldeten die Sensoren genau diesen Wert, erkannte das Programm einen undefinierten Zustand und brach ab.
Der letzte Fall ist der lehrreichste, weil er keine exotische Technik voraussetzt: Ein einziger vergessener Randfall genügt. Als Faustzahl rechnet man in der Softwaretechnik mit mindestens einem Fehler je 10 KByte Quelltext.
Definitionen. Der Nachweis, dass ein Informatiksystem zuverlässig arbeitet, heißt Validierung. Man unterscheidet dabei zwei Wege:
- Bei der Verifikation wird formal, also durch logische Herleitung bewiesen, dass der Algorithmus seine Bedingungen einhält.
- Beim Testen wird das Programm mit ausgewählten Daten erprobt, deren Ergebnis bekannt ist.
Ein Algorithmus heißt korrekt, wenn er seiner Spezifikation genügt: Zu allen Eingabedaten, die eine bestimmte Vorbedingung erfüllen, liefert er Ausgabedaten, die eine bestimmte Nachbedingung erfüllen.
Testen kann nur die Anwesenheit von Fehlern zeigen, nie ihre Abwesenheit (Edsger Dijkstra). Wer alle Eingaben durchprobieren wollte, müsste bei einem Programm mit zwei 32-Bit-Zahlen als Eingabe rund Fälle prüfen.
- Erklären Sie den Unterschied zwischen Verifikation und Testen an Ihrem Sortierprogramm: Was ließe sich beweisen, was nur testen?
- Formulieren Sie Vor- und Nachbedingung für ein Sortierprogramm möglichst genau. Achtung: „Die Ausgabe ist aufsteigend sortiert” allein genügt nicht — warum?
- Welche Testfälle würden Sie für ein Sortierprogramm wählen? Nennen Sie mindestens fünf und begründen Sie jeden.
4.3.2Effizienz und Größenordnung
Zwei Algorithmen heißen äquivalent, wenn sie gleichen Eingabedaten gleiche Ausgabedaten zuordnen. Von zwei äquivalenten Algorithmen ist derjenige effizienter, der mit weniger Laufzeit und/oder weniger Speicherplatz auskommt. Beides zugleich lässt sich meist nicht beliebig verbessern: Ab einer gewissen Schwelle wird Geschwindigkeit mit Speicher erkauft und umgekehrt.
Die Laufzeit in Sekunden zu messen, hilft beim Vergleich von Algorithmen wenig. Sie hängt vom Prozessor ab, vom Compiler, vom Cache, vom Betriebssystem und davon, was sonst noch läuft. Deshalb zählt man stattdessen Elementarschritte — bei Sortierverfahren die Vergleiche.
Bezeichnung. Ein Problem der Größe ist ein Problem, dessen Eingabe aus Elementen besteht. Die Zahl der Rechenschritte, die ein Algorithmus dafür benötigt, heißt Zeitkomplexität.
Zur Ermittlung nimmt man drei Vereinfachungen vor:
- Man betrachtet nur die dominante Operation, von der die Laufzeit wesentlich abhängt.
- Man unterscheidet besten, schlechtesten und mittleren Fall.
- Man lässt additive und multiplikative Konstanten weg und geht zur Größenordnung über.
Der dritte Punkt ist der wichtigste und beim ersten Lesen der befremdlichste. Er besagt: Ob ein Verfahren oder Schritte braucht, ist für große gleichgültig — entscheidend ist das Wachstum. Notiert wird das in der Landau-Notation:
- — lineares Wachstum. Doppelt so viele Daten, doppelte Laufzeit.
- — quadratisches Wachstum. Doppelt so viele Daten, vierfache Laufzeit.
- — dazwischen, und für Sortierverfahren die entscheidende Klasse.
- — exponentielles Wachstum. Ein Element mehr verdoppelt die Laufzeit. Schon bei kleinen Eingaben praktisch unbrauchbar.
4.3.3Unsere vier Verfahren im Vergleich
Die folgende Tabelle enthält gemessene Vergleichszahlen: Mittelwerte über 300 zufällige Felder. Die letzte Spalte ist mit den Formeln hochgerechnet.
| Verfahren | Zeitkomplexität | (gerechnet) | ||
|---|---|---|---|---|
| Selection Sort | , genau | 190 | 499 500 | |
| Bubble Sort | , etwa | 181 | 498 530 | |
| Insertion Sort | , im Mittel etwa | 113 | 250 315 | |
| Quicksort | , etwa | 71 | 10 947 |
Der Sprung in der letzten Spalte ist der eigentliche Punkt dieses Abschnitts: Bei hunderttausend Elementen trennt Quicksort von den anderen drei Verfahren nicht ein Faktor 2 oder 10, sondern ein Faktor von über tausend — gegenüber Selection und Bubble Sort sogar mehr als zweitausend. Ein Rechner, der die quadratischen Verfahren in einer Stunde schafft, wäre mit Quicksort nach wenigen Sekunden fertig. Kein Hardwarekauf der Welt gleicht das aus — der Unterschied liegt im Algorithmus.
Wichtig ist dabei die Unterscheidung der Fälle:
| Verfahren | bester Fall | mittlerer Fall | schlechtester Fall |
|---|---|---|---|
| Selection Sort | |||
| Bubble Sort | (sortiert) | ||
| Insertion Sort | (sortiert) | ||
| Quicksort | (ungünstiges Pivot) |
Quicksort ist also nicht in jedem Fall schnell: Wählt man stets das
letzte Element als Pivot und ist das Feld bereits sortiert, zerlegt jede
Runde das Feld in einen leeren und einen fast vollständigen Teil — das
Verfahren wird quadratisch. In Python macht sich dieser Fall sogar
doppelt bemerkbar: Die Rekursion wird dann
Ebenen tief, und ab etwa tausend Elementen bricht das Programm mit
RecursionError ab, lange bevor die Laufzeit auffällt. Genau
das haben Sie in den Aufgaben 21 und 25 beobachtet. Abhilfe schafft eine
bessere Pivotwahl, etwa das mittlere von drei Elementen.
Kein allgemeines Sortierverfahren, das nur vergleicht, kommt mit weniger als Vergleichen aus. Begründung: Bei Elementen gibt es mögliche Reihenfolgen. Jeder Vergleich hat zwei Ausgänge und kann die Zahl der in Frage kommenden Reihenfolgen also höchstens halbieren. Man braucht deshalb mindestens Vergleiche, um eine einzige übrig zu lassen. Quicksort liegt im Mittel in dieser Größenordnung — besser geht es nicht.
- Ein Algorithmus braucht für genau 2 Sekunden. Wie lange braucht er für , wenn er linear, quadratisch bzw. exponentiell wächst?
- Begründen Sie mit der Formel , warum Selection Sort bei Verdoppelung der Elementzahl etwa viermal so viele Vergleiche braucht. Prüfen Sie es mit der Visualisierung nach.
- Warum hat Bubble Sort einen besseren besten Fall als Selection Sort, obwohl beide im Mittel gleich viele Vergleiche brauchen?
- Erweitern Sie Ihre Sortierprogramme um Zähler für Vergleiche und Vertauschungen. Sortieren Sie damit Felder der Größe 100, 200, 400 und 800 und tragen Sie die Werte in eine Tabelle ein. Bestätigen Sie das quadratische Wachstum.
- Ein Verfahren mit schafft in einer Stunde. Schätzen Sie die Laufzeit für . Kommentieren Sie das Ergebnis.
- Diskutieren Sie: Für ist Insertion Sort in der Praxis schneller als Quicksort, obwohl die Größenordnung schlechter ist. Wie passt das zusammen? (Stichwort: weggelassene Konstanten.)
4.4Grenzen der Berechenbarkeit
Diesen Abschnitt als PDF (S. 18–22)
Der ganze Abschnitt gehört zum LK-Themenfeld Berechenbarkeit und ihre Grenzen. Für den Grundkurs ist er nicht verbindlich — er beantwortet aber die Frage, die sich nach jedem Laufzeitvergleich aufdrängt: Gibt es Probleme, für die gar kein Verfahren existiert?
Lange hielt man jedes mathematische Problem für lösbar, wenn man sich nur genug anstrengt. David Hilbert (1862–1943) formulierte diese Überzeugung so: Jedes bestimmte mathematische Problem müsse einer strengen Erledigung fähig sein — entweder durch eine Antwort oder durch den Nachweis, dass eine Lösung unmöglich ist.
Im 20. Jahrhundert stellte sich heraus: Das stimmt nicht. Es gibt Probleme, die sich computergerecht aufschreiben lassen und trotzdem von keinem Algorithmus gelöst werden können. Und zwar nicht, weil die Rechner zu langsam wären — sondern grundsätzlich.
Definition. Eine Menge natürlicher Zahlen heißt entscheidbar, wenn es einen Algorithmus gibt, der für jede natürliche Zahl nach endlich vielen Schritten feststellt, ob sie zu gehört oder nicht. Man nennt ihn ein zweiseitiges Entscheidungsverfahren.
Sie heißt partiell entscheidbar, wenn es einen Algorithmus gibt, der nur die Zugehörigkeit feststellt: Gehört die Zahl dazu, hält er mit „ja” an; gehört sie nicht dazu, läuft er möglicherweise ewig. Das ist ein einseitiges Entscheidungsverfahren.
4.4.1Das Goldbach-Problem: entscheidbar
Die Goldbachsche Vermutung (1742) lautet: Jede gerade Zahl lässt sich als Summe zweier Primzahlen schreiben.
Bis heute ist sie weder bewiesen noch widerlegt. Für die Informatik stellen wir eine schwächere Frage: Gibt es einen Algorithmus, der für eine gegebene gerade Zahl entscheidet, ob sie die Goldbach-Eigenschaft hat?
Den gibt es — und er ist einfach:
Python
def prim(zahl):
if zahl < 2:
return False
i = 2
while i * i <= zahl:
if zahl % i == 0:
return False
i += 1
return True
def goldbach(n):
for k in range(2, n // 2 + 1):
if prim(k) and prim(n - k):
return True
return FalseObject Pascal
function Prim(zahl: integer): boolean;
var i: integer;
begin
Result := zahl >= 2;
i := 2;
while i * i <= zahl do
begin
if zahl mod i = 0 then
begin
Result := false;
exit;
end;
i := i + 1;
end;
end;
function Goldbach(n: integer): boolean;
var k: integer;
begin
Result := false;
for k := 2 to n div 2 do
if Prim(k) and Prim(n - k) then
begin
Result := true;
exit;
end;
end;Die Schleife läuft höchstens bis , endet also garantiert. Damit ist die Goldbach-Eigenschaft entscheidbar. Beachten Sie den Unterschied: Für jede einzelne Zahl ist die Frage beantwortbar. Ob die Vermutung für alle Zahlen gilt, beantwortet der Algorithmus nicht — dafür müsste er unendlich viele Zahlen prüfen.
4.4.2Wundersame Zahlen: partiell entscheidbar
Die Collatz-Funktion (L. Collatz, um 1930) ist definiert durch
Betrachtet werden dabei nur natürliche Zahlen . Eine solche Zahl heißt wundersam, wenn wiederholtes Anwenden von irgendwann bei 1 ankommt. Für ergibt sich die Folge
Die 5 ist also wundersam. Der naheliegende Algorithmus:
Python
def wundersam(n):
while n > 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
return TrueObject Pascal
function Wundersam(n: integer): boolean;
begin
while n > 1 do
if n mod 2 = 0 then
n := n div 2
else
n := 3 * n + 1;
Result := true;
end;Ist wundersam, hält er nach endlich vielen Schritten und antwortet „ja”. Ist es nicht, läuft er ewig — und wir erfahren nie, ob er noch anhält oder nicht. Er ist also nur ein einseitiges Entscheidungsverfahren.
::: stolperstein Der Rumpf prüft n > 1 und meldet
alles andere ungeprüft als wundersam — für
oder
antwortet er also sofort „ja”, obwohl diese Zahlen die 1 nie erreichen.
Das Programm setzt den Definitionsbereich
stillschweigend voraus. Wer es ernst meint, fängt den Fall ab: In Python
if n < 1: raise ValueError(...), in Pascal eine Prüfung
vor der Schleife. Dieselbe Lücke steckt in sehr vielen Programmen, die
„für die sinnvollen Eingaben” geschrieben wurden. ::: Ein zweiseitiges
ist bis heute nicht bekannt; Collatz vermutete, dass jede Zahl wundersam
ist, bewiesen ist auch das nicht.
4.4.3Game of Life: nachweislich unentscheidbar
Im Spiel des Lebens (J. Conway) lebt jede Zelle eines Gitters oder ist tot. Eine tote Zelle wird lebendig, wenn genau drei ihrer acht Nachbarn leben. Eine lebende Zelle stirbt, wenn mindestens vier Nachbarn leben (Übervölkerung) oder höchstens einer (Vereinsamung).
Gesucht ist ein Algorithmus, der für eine beliebige Anfangsgeneration entscheidet, ob sie irgendwann ausstirbt. Man kann die Generationen einfach nachrechnen: Stirbt die Population, ist die Antwort da. Stirbt sie nicht, rechnet der Algorithmus ewig. Wieder nur ein einseitiges Verfahren — mit einem Unterschied zur Collatz-Frage: Für das Game of Life ist bewiesen, dass es kein zweiseitiges Verfahren geben kann.
4.4.4Das Halteproblem
Der wichtigste Satz dieses Abschnitts geht auf Alan Turing (1936) zurück — auf dieselbe Arbeit, die die Turingmaschine aus Abschnitt 1.2 einführte. Turing brauchte die Maschine genau dafür: um überhaupt sagen zu können, was „es gibt kein Verfahren” bedeutet.
Der Satz lässt sich für jede Programmiersprache formulieren:
Es gibt kein Programm, das für ein beliebiges Programm und eine beliebige Eingabe entscheidet, ob angewendet auf nach endlich vielen Schritten anhält. Die Halte-Eigenschaft ist unentscheidbar und nur partiell entscheidbar.
Beweis durch Widerspruch. Nehmen wir an, es gäbe
eine Funktion haelt(P, x), die für den Quelltext
P und die Eingabe x den Wert True
liefert, wenn P bei Eingabe x anhält, und
sonst False.
def haelt(P, x):
# Annahme: liefert True, falls P bei Eingabe x anhaelt, sonst False
...function Haelt(P, x: string): boolean;
begin
{ Annahme: liefert true, falls P bei Eingabe x anhaelt, sonst false }
end;Mit dieser Funktion bauen wir ein zweites Programm:
def seltsam(P):
if haelt(P, P):
while True: # Endlosschleife
pass
return "fertig"procedure Seltsam(P: string);
begin
if Haelt(P, P) then
while true do ; { Endlosschleife }
writeln('fertig');
end;seltsam tut also genau das Gegenteil dessen, was
haelt vorhersagt: Hält P bei Eingabe des
eigenen Quelltextes an, so läuft seltsam ewig weiter; hält
P nicht an, so hält seltsam an.
Da P beliebig ist, dürfen wir P = seltsam
einsetzen. Dann gilt:
- Ist
haelt(seltsam, seltsam) = True, so gerätseltsamin die Endlosschleife — hält also nicht an. Widerspruch. - Ist
haelt(seltsam, seltsam) = False, so überspringtseltsamdie Schleife und gibt „fertig” zurück — hält also doch an. Widerspruch.
seltsam hält bei Eingabe des eigenen Quelltextes genau
dann an, wenn es nicht anhält. Beides ist unmöglich. Also war die
Annahme falsch: Die Funktion haelt kann es nicht geben.
Der Beweis sagt nichts über fehlende Rechenleistung. Er zeigt, dass die Annahme selbst widersprüchlich ist. Kein schnellerer Rechner, keine bessere Programmiersprache und keine künstliche Intelligenz ändern daran etwas.
4.4.5Was folgt daraus für die Praxis?
Das Halteproblem ist kein Kuriosum für Theoretiker, sondern die Ursache für eine Reihe sehr praktischer Grenzen:
- Kein Werkzeug kann für beliebige Programme zuverlässig entscheiden, ob sie sich aufhängen. Entwicklungsumgebungen warnen vor erkennbaren Endlosschleifen — mehr ist nicht möglich.
- Kein Virenscanner kann durch reine Programmanalyse für jedes Programm entscheiden, ob es sich schädlich verhält. Deshalb arbeiten Scanner mit Signaturen, Heuristiken und Beobachtung zur Laufzeit.
- Allgemein gilt (Satz von Rice): Jede nichttriviale Frage über das Verhalten eines beliebigen Programms ist unentscheidbar. Fragen über seinen Text — Zeilenzahl, benutzte Schlüsselwörter — sind dagegen problemlos beantwortbar.
- Bestimmen Sie die Collatz-Folge für und . Wie viele Schritte brauchen Sie jeweils?
- Programmieren Sie den Goldbach-Test und prüfen Sie alle geraden Zahlen von 4 bis 10 000.
- Programmieren Sie einen Collatz-Rechner, der die Folge und ihre Länge ausgibt. Suchen Sie die Zahl unter 1000 mit der längsten Folge.
- Erklären Sie mit eigenen Worten den Unterschied zwischen entscheidbar und partiell entscheidbar. Ordnen Sie Goldbach-Eigenschaft, Wundersamkeit und Halte-Eigenschaft zu.
- Warum genügt es für den Beweis des Halteproblems nicht zu sagen,
haeltsei „zu schwer zu programmieren”? Was leistet der Widerspruchsbeweis stattdessen? - Ein Mitschüler schlägt vor: „Man lässt das Programm einfach eine Stunde laufen. Läuft es dann noch, hält es nicht an.” Nehmen Sie Stellung.
- Erklären Sie in fünf Sätzen, warum Turing für diesen Beweis die Maschine aus Abschnitt 1.2 brauchte — warum also die Aussage „es gibt kein Verfahren” ohne einen festgelegten Verfahrensbegriff gar nicht prüfbar wäre.
4.5Zusammenfassung
Diesen Abschnitt als PDF (S. 23)
- Die sequentielle Suche braucht im schlechtesten Fall Vergleiche und stellt keine Bedingung an das Feld. Die binäre Suche kommt mit etwa Vergleichen aus, setzt dafür aber ein sortiertes Feld voraus — und genau darum wird überhaupt sortiert.
- Sortierverfahren unterscheiden sich nicht im Ergebnis, sondern im Aufwand. Gezählt werden Vergleiche und Vertauschungen, nicht Sekunden.
- Selection Sort sucht teuer und tauscht sparsam, Insertion Sort umgekehrt. Bubble Sort ist am einfachsten und am langsamsten. Alle drei sind .
- Quicksort zerlegt das Problem rekursiv (Teile und herrsche) und erreicht im Mittel — bei ungünstiger Pivotwahl aber .
- Die Landau-Notation beschreibt das Wachstum der Laufzeit und lässt Konstanten weg. Für große entscheidet allein die Größenordnung.
- Kein vergleichendes Sortierverfahren kann besser als sein.
- Testen zeigt die Anwesenheit von Fehlern, nie ihre Abwesenheit.
- Entscheidbar heißt: Ein Algorithmus antwortet immer mit ja oder nein. Partiell entscheidbar heißt: Er antwortet nur im Ja-Fall zuverlässig.
- Das Halteproblem ist unentscheidbar. Daraus folgen harte Grenzen für Werkzeuge, die das Verhalten fremder Programme beurteilen sollen.
Wiederholungsaufgaben
- Ein sortiertes Feld enthält eine Million Einträge. Wie viele Vergleiche braucht die binäre Suche im schlechtesten Fall, wie viele die sequentielle? Begründen Sie, warum sich das Sortieren trotz seines Aufwands lohnt, sobald mehrfach gesucht wird.
- Beschreiben Sie die vier Sortierverfahren in je zwei Sätzen, ohne Quelltext zu benutzen.
- Sortieren Sie
6 1 9 3 7 2mit allen vier Verfahren von Hand und zählen Sie jeweils die Vergleiche. Welches Verfahren gewinnt bei so kleinen Feldern? - Erklären Sie, warum die Aussage „Quicksort ist schneller als Bubble Sort” ohne Zusatz unvollständig ist.
- Ein Programm braucht bei 1000 Datensätzen 1 Sekunde, bei 2000 Datensätzen 4 Sekunden. Welche Zeitkomplexität vermuten Sie? Wie lange dauert es bei 10 000 Datensätzen?
- Begründen Sie, warum die Grenze nur für vergleichende Verfahren gilt. Recherchieren Sie ein Verfahren, das schneller ist, und erklären Sie, was es anders macht.
- Nehmen Sie Stellung: „Mit genug Rechenleistung lässt sich jedes Problem lösen.”