Sublineare Laufzeit eines Algorithmus (Knobelaufgabe)

Question

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 Algorithmus eine sublineare Laufzeit haben, heißt: f ∉ Ω(g) mit g(n) = n.

Bin dankbar für jede Hilfe!:)

Answer 1

Das erste Brett wird im k-ten Schritt in Höhe k² angebracht.

Wenn es auf Höhe k² kaputt geht, dann ist (k-1)² ≤ r < k².

Wegen k² - (k-1)² = 2k-1 werden für eine maximale Fallhöhe von (k-1)²+1 nicht mehr als k+(2k-1) Versuche benötigt. Also ist f ∈ O(√r).

Comments

Erstmal vielen Dank für die Antwort. Ich verstehe nicht ganz, warum die Laufzeit maximal O(√r) ist. "nicht mehr als k+(2k-1)" hört sich für mich nach einer linearen Laufzeit an ( Θ(k) ), aufgrund des k.

---

werden für eine maximale Fallhöhe von (k-1)²+1 nicht mehr als k+(2k-1) Versuche benötigt.

        \(\begin{aligned} &  & (k-1){{}^2}+1 & =r\\ & \implies & (k-1){{}^2} & =r+1\\ & \implies & k-1 & =\sqrt{r+1}\\ & \implies & 3k-3 & =3\sqrt{r+1}\\ & \implies & 3k-1 & =3\sqrt{r+1}+2\\ & \implies & k+\left(2k-1\right) & =3\sqrt{r+1}+2 \end{aligned}\)

        \(3\sqrt{r+1}+2 \leq3\sqrt{r+r}+\sqrt{2r} =\left(3+\sqrt{2}\right)\sqrt{r}\)