Tür in einem unendlichen Wandalgorithmus
Frage:
Tür in einer Wand Sie stehen vor einer Wand, die sich unendlich in beide Richtungen erstreckt. Es gibt eine Tür in der Wand, aber Sie wissen weder, wie weit noch in welche Richtung. Sie können die Tür nur sehen, wenn Sie direkt daneben stehen. Entwerfen Sie einen Algorithmus, der es Ihnen ermöglicht, die Tür zu erreichen, indem Sie in den meisten O (n) Schritten gehen, wobei n die (Ihnen unbekannte) Anzahl von Schritten zwischen Ihrer Ausgangsposition und der Tür ist.
Antwort im Buch:
Der Schlüsselgedanke ist hier, dass man mit jedem Mal nach rechts und links gehen muss, und zwar jedes Mal exponentiell weiter von der Ausgangsposition. Eine einfache Umsetzung dieser Idee ist es, folgendes zu tun, bis die Tür erreicht ist: Für i = 0,1, ..., mache 2 i Schritte nach rechts, kehre zur ursprünglichen Position zurück, mach 2 i schreitet nach links und kehrt zur ursprünglichen Position zurück. Sei 2 (k-1) & lt; n ≤ 2 k . Die Anzahl der Schritte, die dieser Algorithmus benötigt, um die Tür zu finden, kann wie folgt geschätzt werden:
Folglich ist die Anzahl der Schritte, die durch den Algorithmus gemacht werden, in O (n). (Anmerkung: Es ist nicht schwierig, die multiplikative Konstante mit einem besseren Algorithmus zu verbessern.
Wo ich verloren gehe:
Ich verliere mich, wenn es zur Summe kommt. Kann mir bitte jemand erklären wie die Summe funktioniert ?? Warum haben sie die 2 k und die 2 i mit 4 und 3 multipliziert? Warum vergleichen sie es mit & lt; 7 · 2 k ? Wie war es 14 · 2 (k-1) was mit & lt; 14n. Ich denke, ich bekomme die Tatsache, dass n = 2 (k-1) was die letzte Vergangenheit der Summe erklären würde, aber so viele Fragen.
2 Antworten
Die 4 soll die Anzahl der vollständigen Schritte berechnen, die eine vollständige Suche darstellen. Also sagen wir, wir sind bei i = 1.
Wir beginnen bei x = 0. Wir gehen zu 2 ^ 1 = 2. Das sind 2 Schritte. Dann zurück zu 0. Weitere 2 Schritte. Dann zu -2, dann zurück zu 0. Insgesamt 8 Schritte oder 4 x 2 ^ 1
4 x 2 ^ i = Anzahl der Schritte bei einer fehlgeschlagenen Suche, bei der wir zum Ausgangspunkt zurückkehren, um eine größere Suche zu starten, da wir nur nach links und rechts gehen und nicht teleportieren können
Die kth Iteration ist, wenn wir unsere Tür finden. Der schlimmste Fall ist, wenn die Tür bei n nach links steht, wo n = 2 ^ k Schritte.
Was passiert also, wenn wir in diese Iteration kommen?
Wir beginnen bei x = 0, wir gehen zu 2 ^ k nach rechts, dann zurück zu 0, dann nach links zu -2 ^ k. Eine Gesamtüberschreitung von 3 x 2 ^ k Schritten.
Warum es mit 7 * 2 ^ k verglichen wird, wissen wir, dass der ith Suchbegriff 2 ^ (k - 1) oder alles vorher ist. Wir können 7 * 2 ^ k mit 7n ersetzen, basierend auf unserer vorherigen Definition bezüglich k - 1 vs k
Und wir können auch die Tatsache verwenden, dass 2^k = 2 x 2^(k-1) in unseren Abstraktionen ist.
Per @AbcAeffchen 2^(k−1) < n wird angenommen, also können Sie 2^(k−1) durch n ersetzen und 14*2^(k−1) < 14n
Zusätzlich zu @ Compass's Antwort müssen wir 2 ^ (k-1) durch n ersetzen, nicht die 2 ^ k, da die Frage danach fragt, die Tür zu erreichen / zu finden, die Tür könnte überall in der Linke sein Gehen von Anfangspunkt in kth Iteration. Also haben wir 2 ^ (k-1)
Tags und Links algorithm