1. Einführung
Ein Blatt Papier ist bekanntlich \(0.1\)mm dick. Immer dann, wenn du ein Papier faltest, verdoppelt sich die Dicke des resultierenden Papiers. Doch wie oft lässt sich ein Papier sinnvoll falten? Und wie oft müsste man falten, damit das Ergebnis so dick ist, dass es von der Erde bis zur Sonne reichen würde? Nun, seltener als du vielleicht denkst.
2. Falten, falten und wieder falten ...
Gegeben sei für unser Gedankenexperiment ein Blatt Papier.
- Dieses wird nun einmal gefaltet. Das resultierende Papier ist \(0.2\)mm dick.
- Nach einem weiteren Mal falten ergibt sich eine Dicke von \(0.4\)mm. Dies entspricht etwa dem Durchmesser eines menschlichen Haars.
- Wir falten das Blatt erneut und erhalten eine Dicke von \(0.8\)mm, also bereits fast einem ganzen Millimeter.
- Nach dem vierten Falten sind wir bereits bei \(1.6\)mm.
- Danach bei \(3.2\)mm.
- Und so geht das jetzt eine ganze Zeit lang weiter, bis wir nach dem \(7.\) Mal bei über einem Zentimeter angekommen sind.
- Nach dem \(8.\). Mal sind es ca. \(2.5\)cm, danach ca. \(5\)cm, dann ca. \(10\)cm und immer so weiter, bis wir nach dem \(14.\) Mal falten bei der Größe eines Menschen \(1.64)m angekommen sind.
- Mit dem fünfzehnten Mal durchbrechen wir bereits die \(3\)m-Marke. So groß ist kein Mensch mehr.
- Danach sind wir bei ca. \(6.6\)m und mit dem \(17.\) Mal liegen wir mit ca. \(13\) Metern über einem Einfamilienhaus.
- Nach dem \(22.\) Mal falten haben wir den Eiffelturm mit über \(400\) Metern eingeholt.
- Mit dem \(24.\) Mal knacken wir schon den ersten Kilometer!
Du merkst bereits, dass wir immer schnelleren Schrittes foranschreiten. Das liegt daran, dass sich die Dicke mit jedem Faltschritt verdoppelt! Hier liegt also ein exponentielles Wachstum vor!
- Nach dem \(30.\) Mal ist unser Blatt Papier dicker als die Länge zwischen München und Ausgburg.
- Nach dem \(31.\) Mal haben wir die Strecke München-Nürnberg errreicht.
- Das \(32.\) Mal führt uns von München bis nach Frankfurt.
- Mit dem \(33.\) Mal kommen wir von München bis Hamburg.
- Nach dem \(34.\) Mal kämen wir von München nach Stockholm.
- Nach dem \(35.\) Mal hat unser Papier den Durchmesser des Jupiter-Monds IO erreicht.
- Wenn wir das Papier \(37\) Mal gefaltet haben, ist es dicker als die Erde!
Nächstes Ziel: Der Mond. Dieser ist \(400.000\)km (also etwas über einer Lichtsekunde) von der Erde entfernt.
- Den Mond erreichen wir nach dem \(42.\) Mal falten. Ist das Zufall?
Unser menschlicher Verstand ist im Denken linear und nicht exponentiell ausgelegt. So dürfte dich die Erkenntnis, dass du mit dem \(42-\)maligen Falten eines einfachen Blatt Papiers den Mond erreichen könntest sehr überraschen. Nächstes (und letztes) Ziel für diesen Artikel: die Sonne. Diese ist \(149.600.000\)km von uns entfernt und wird mit dem \(51.\) Mal falten erreicht und sogar weit überholt. Wow! Das \(50.\) Mal hätte hingegen noch nicht ausgereicht, da du noch etwa eine weitere Lichtsekunde bis zur Sonne zurücklegen müsstest. Dass du ein Papier nicht so oft falten kannst, dürfte mittlerweile klar sein, oder?
3. Was hat das nun mit Algorithmen zu tun?
Algorithmen haben immer eine bestimmte Laufzeit. Das ist die Zeit, die der Algorithmus zur Lösung eines bestimmten Problems benötigt. Wenn du z. B. das größte Element in einer Liste suchen willst, brauchst du im Worst-Case genauso viele Versuche wie die Liste Elemente enthält. Die Laufzeit ist also linear, d. h. sie steigt linear mit der gegebenen Länge \(n\) der Liste, in der gesucht werden soll.
Schlimmer sieht es hingegen bei z. B. dem rekursiven Berechnen von Fibonacci-Zahlen. Hier wächst die Laufzeit exponentiell. Während du für kleine \(n\), d. h. weit vorne stehende Glieder in der Fibonacci-Folge, kaum Laufzeitprobleme bekommen wirst, wird es für größere Werte recht schnell kaum mehr lösbar (bzw. nur mit einem nach dem aktuellen Stand der Technik nicht zu leistenden Rechenaufwand). Ohne eine explizite Formel, mit der eine Berechnung in konstanter Zeit, d. h. direkt durch z. B. einfaches Einsetzen, möglich ist, wirst du deines Lebens nicht mehr froh.
Das Mitglied hat durch den Artikel 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
