Frage: Hat jemand eine Idee für den Folgenden Algorithmus mit ! sublinearer ! Laufzeit?
Es geht konkret um ein Regal mit der Höhe n ∈ ℕ.
In jede Höhe kann ein Brett eingefügt werden und es soll die maximale Fallhöhe r ermittelt werden, wo ein Brett nicht kaputt geht.
Es stehen zwei Bretter zur Verfügung die kaputt gehen dürfen. Ein Brett geht erst kaputt, sobald es die Höhe (r+1) erreicht hat (heißt: oberhalb der max. Fallhöhe ist). Vorher darf man mit einem Brett so oft testen wie man möchte.
Es gilt zusätzlich:
- Wenn ein Brett nicht bei Höhe x bricht, bricht es auch bei keiner Höhe x' < x.
- Ein Fall aus Höhe 0 führt nicht zum zerbrechen.
- Es gibt keine Materialermüdung, unterschiedliche Fall-/Aufprallverhalten o.Ä.
- Ein Regal kann beliebig hoch werden
Theoretisch könnte man einfach linear von unten nach oben suchen und sobald ein Brett kaputt geht impliziert das die max. Fallhöhe r = (h-1).
Jedoch soll der Suchalgorithmus eine sublineare Laufzeit haben, heißt: f ∉ Ω(g) mit g(n) = n.
Bin dankbar für jede Hilfe!:)
