Sickern lassen

vor allem die schöne aufschlüsselung finde ich prächtig

 

Ist doch vollkomen logisch. Der Arbeitsvorgang gliedert sich in mehrere Teile:

- Brett vorbereiten
- Kaffee trinken
- Bretter nachzählen
- gegebenfalls sägen

Maria ist wohl von schwacher Statur und braucht etwa 1 Minute zur Manipulation des Brettes. Anschließend ist sie so erschöpft, dass sie dringend einen Kaffee braucht. Während sie den Kaffee schlürft, zählt sie nochmals alle Bretter nach. Sind es noch zu wenige Teile, dann wird mit der (elektrischen) Kappsäge in 10 Sekunden geschnitten; sind es bereits ausreichend viele Teile, dann wird sich 10 Sekunden gefreut.

Somit ergibt sich pro Teil eine Arbeitsdauer von 5 Minuten. Dem aufmerksamen Leser ist dabei sicher nicht entgangen, dass Maria bei einer gewünschten Anzahl von 1 Brett dieses völlig überflüssigerweise herumschleppt, weil sie erst beim Kaffee trinken draufkommt, dass sie eigentlich schon fertig ist. Ein solches Verhalten ist suboptimal, kommt aber gelegentlich auch in Software vor.

Weiterhin fällt auch auf, dass die benötigte Zeit direkt proportional zur Anzahl der gewünschten Bretter ist. Mathematisch gesprochen ist der Algorithmus von der ordnung n, was man üblicherweise als O(n) schreibt. Hat man eine große Anzahl von Brettern zu schneiden, dann wird das mühsam. Glücklicherweise existiert ein anderer Algorithmus, der logarithmischer Zeit fertig wird, geschrieben O(log n), der wie folgt aussieht:

1) Bei n <= 1 ist man fertig.
2) Ist n gerade, dann schneidet man in der Mitte durch, legt die Teile übereinander, halbiert n und geht zu Schritt 1
3) ist n hingegen ungerade, dann schneidet man 1/n tel ab, reduziert n um 1 und geht zu Schritt 1

Das mag recht kompliziert erscheinen, die Ersparnis ist aber um so größer, je größer n ist.

Beispiel n = 5 (lineare Zeit 25 Minuten):

1. Schnitt bei 1/5, rest 4
2. Schnitt halbiert, Stapelhöhe 2 mit Länge 2
3. Schnitt halbiert, Stapelhöhe 4 mit Länge 1

=> 15 Minuten

Beispiel n= 50 (lineare Zeit 250 Minuten = 4:10):

1. Schnitt halbiert, Stapelhöhe 2 Länge 25
2. Schnitt bei 1/25, Stapelthöhe 2 Länge 24 + 2 fertige Bretter
3. Schnitt halbiert, Stapelhöhe 4 Länge 12
4. Schnitt halbiert, Stapelhöhe 8 Länge 6
5. Schnitt halbiert, Stapelhöhe 16 Länge 3
6. Schnit bei 1/3, Stapelhöhe 16 Länge 2 + 16 fertige Bretter
7. Schnitt halbiert, 32 fertige Bretter

=> 35 Minuten

Voraussetzung ist allerdings, dass das Ausgangsmaterial ausreichend lang ist und die Säge ausreichend groß. Das erklärt auch, warum Maria so lange braucht, um das Brett in Position zu rücken...

 

hehe
..aber erst, wenn der Groschen gefallen ist.