vorige nächste

Beispiele für Laufzeiten


Die folgende Tabelle gibt Beispiellaufzeiten für die "gute" Version an. Dabei wurde die Laufzeit gemessen, die das Programm brauchte, um eine (die erste) Lösung zu finden. Es sind signifikante Unterschiede für ungerade und gerade Anzahlen zu beobachten.

Anzahl Damen Laufzeit
4 0 ms
5 10 ms
6 10 ms
7 0 ms
8 30 ms
9 10 ms
10 20 ms
11 30 ms
12 110 ms
13 50 ms
14 901 ms
15 751 ms
16 5718 ms
17 3395 ms
18 28190 ms
19 1912 ms
20 156485 ms = 2 min 36 s 485 ms
21 7631 ms
22 1585430 ms = 26 min 25 s 430 ms
23 26979 ms
24 ???
25 61389 ms
26 ???
27 635404 ms = 10 min 35 s 404 ms

 

In jedem Fall ist der exponentielle Anstieg und seine Auswirkung auf die Laufzeiten deutlich erkennbar. Ohne an einem Beispiel wie dem hier untersuchten n - Damen - Problem einmal die Messungen selbst durchgeführt zu haben, wird kaum jemand wirklich verstehen, dass ein exponentieller Anstieg kein es wird irgendwie mehr bedeutet, sondern dass diese Art des Anstiegs zwar für die Frage der prinzipiellen Lösbarkeit belanglos sein mag, aber für die Frage der realen Lösbarkeit von zentraler Bedeutung ist.

 

Fazit
In der Informatik gilt ein Problem erst dann als gelöst, wenn es einen Algorithmus mit einer dem Problem angemessenen realistischen Laufzeit gibt, mit dem eine konkrete Lösung tatsächlich angegeben werden kann.