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. |