Einfache Algo-Spiel

Question

Angenommen, ich habe Array mit Null und Einsen: die ersten n (vielleicht n = 0) Elemente ist 0s und andere ist 1s (Beispiel [0,0,1,1,1]). Aber ich kann keine Elemente sehen. Ich kann bitten, das Element in einer bestimmten Position zu zeigen. Wenn es sich herausstellte, dass ich zwei 1s (zu jeder Zeit) geöffnet habe, muss ich aufhören. Welcher Algorithmus führt mich dazu, die letzte Position von 0 mit der kleinsten Anzahl von Öffnungselementen zu finden?

Answer 1

Eine erste Schätzung könnte etwas wie binäre Suche sein: Versuchen Sie das mittlere Element, um den Suchraum in zwei Hälften zu schneiden. Es stellt sich jedoch heraus, dass dies angesichts der begrenzten Anzahl verfügbarer Fehler keine gute Strategie ist; Wenn sich herausstellt, dass Ihre erste Schätzung eine 1 ist, ist die einzige sichere Strategie, linear von der größten bekannten sicheren Position aus zu suchen, was der Anfang wäre. Dies ist ein Worst-Case von O (n), den Sie auch eindeutig durch das Scannen von vorne bekommen. Sicher können wir es besser machen.

Was passiert, wenn wir die Elemente an den Positionen sqrt (n), 2sqrt (n), ..., n stattdessen versuchen, nur dann linear zu iterieren, wenn wir an einem Punkt eine 1 finden?

• Wir prüfen höchstens sqrt (n) Werte, bevor Sie eine 1 oder Ausschöpfung aller Möglichkeiten
• finden Wenn wir eine 1 zu finden, überprüfen wir höchstens sqrt (n) mehr Optionen vor dem zu finden, was wir geben müssen Antworten.

Beispiel mit n = 100, Split bei 27.

check array[10]; value 0, so continue. 
check array[20]; value 0, so continue. 
check array[30]; value 1, so switch to linear. 
check array[21]; value 0, so continue. 
check array[22]; value 0, so continue. 
check array[23]; value 0, so continue. 
check array[24]; value 0, so continue. 
check array[25]; value 0, so continue. 
check array[26]; value 0, so continue. 
check array[27]; value 1, so answer 26. 

Für n = 100, der schlimmste Fall ist die Spaltung bei 99, und prüfen Sie 10 + 9 = 19 Werte. Eine Obergrenze für die Anzahl der überprüften Werte ist 2sqrt (n), was O (sqrt (n)) ist, asymptotisch besser als O (n) für die naive lineare Methode.

Können Sie es besser machen? Ich bin skeptisch. Diese Methode erreicht eine Beschleunigung durch Ausgleich der Komplexität der schnellen Methode (um mehr als eine zu springen) und der langsamen Methode (lineare Abtastung), so dass sie im schlimmsten Fall die gleiche Anzahl von Schritten aufweisen. Da die Gesamtkomplexität die Summe dieser beiden ist und da alles ziemlich symmetrisch erscheint, vermute ich, dass dies optimal ist - jede andere Art, um zu springen und dann linear zu scannen, könnte in einigen Fällen besser sein, muss sich aber in anderen verschlechtern. Zum Beispiel hat das Überspringen um jedes Mal - das Versuchen von 2, 4, 8, ..., n - O (n) worst-case-Komplexität, da Sie log (n) Werte im schnellen Schritt und ~ n/2 Werte in der langsame Schritt (wenn Sie beim Versuch von n fehlschlagen, müssen Sie alles über ~ n/2 überprüfen).

Answer 2

Öffnen Sie die Elemente nacheinander mit einer Schleife und verwenden Sie dann eine if-Anweisung, um den Wert des Elements zu überprüfen. Wenn das Element an Position j 1 ist, die Schleife verlassen und die letzte 0 ist an Position j-1