Testen Sie, wenn eine Ganzzahl K vorhanden ist, um eine Sequenz hinzuzufügen, um es zu einer anderen Sequenz zu schaffen

Question

Angenommen, diese Reihenfolge $ A $ enthält $ N $ ganzgeräte $ a_1, a_2, a_3, \ ldots, a_n $ und sequenz $ b $ enthält $ m $ integers $ B_1, B_2, B_3, \ LDOTs, B_M $ . Wir wissen, dass $ m \ geq n $ . Wir nehmen ohne Verlust der Allgemeinheit an, dass beide Sequenzen $ A $ und $ B $ B $ in aufsteigender Reihenfolge sortiert werden.

Wie hoch ist der schnellste Algorithmus, um festzustellen, ob ein Integer $ K $ existiert, so dass die Sequenz $ A_1 + K, A_2 + K, A_3 + K, \ ldots, a_n + k $ ist eine Anderwirkung der Sequenz $ B $ ?

Hier ist ein naiver Algorithmus, der $ O (n (m-n)) $ -Zeit dauern würde. Speichern Sie die Sequenz $ B $ als Hashtable. Für jedes Element $ B_J $ von der $ B $ (außer dem größten $ N $ Elements), Verwenden Sie $ B_J-A_1 $ als Ihre Vermutung bei $ K $ ; Sie können diese Vermutung überprüfen, indem Sie prüfen, ob jeder der $ A_1 + K, \ DOTS, A_N + K $ in der Hashtable ist> $ B $ . Dies dauert $ o (n) $ erwartete Zeit pro Erraten bei $ k $ , und Sie machen $ MN $ Vermutungen, sodass die erwartete Laufzeit somit $ O (N (Mn)) $ ist. Können wir es besser machen?

Ich kam auf dieses Problem, während ich versuchte, zwei binäre Bilder mitzuteilen (Prüfung, ob ein Bild den anderen enthält).

Answer 1

Hier ist eine Heuristik, die nicht immer funktioniert, sondern mit hoher Wahrscheinlichkeit arbeiten sollte, wenn die Ganzzahlen in den Arrays zufällig von einem großen Speicherplatz ausgewählt werden.

Initialisieren Sie einen Hashtable von Zählungen $ C $ an alle Nullen. Wiederholen Sie dann $ T $ mal: Zufällig auswählen $ i, j $ , berechnen $ b_j-a_i $ und inkrementieren Sie $ C [B_J-A_I] $ . Sortieren Sie schließlich $ C $ nach Zählungen, von größter Zählung bis zum Kleinsten; Dann probieren Sie für jeden der größten Werte von $ C [k '] $ , probieren Sie $ k' $ Als Erraten bei $ K $ und bestätigen Sie jede Vermutung.

Beachten Sie, dass in jeder Iteration die Wahrscheinlichkeit der Inkrementierung von $ C [k] $ mindestens $ 1 / M $ ist ; Wenn $ l \ ne K $ , erwarten wir $ c [l] $ , um viel mehr inkrementiert zu werden selten (anzunehmen, dass die Ganzzahlen in den Arrays zufällig und groß genug sind). Somit, nach dem $ t $ iterationen, erwarten wir $ \ mathbb {E} [c [k]] \ ge / M $ aber $ \ mathbb {e} [c [l]] \ ll t / m $ . Sobald $ T $ groß genug ist, $ C [k] $ sollte größer als jeder andere sein Eintrag in $ C $ .

Wie groß muss $ T $ sein? Ich erwarte, dass $ t= o (m \ log m) $ $ C [L] $ , vorausgesetzt, wir sind bereit, eine kleine Fehlerwahrscheinlichkeit zu akzeptieren (die exponentiell angetrieben werden kann). Der konstante Faktor, der von der Big-O-Notation verbirgt, könnte nicht trivial sein.

Dies ist nur eine Heuristik, und es wird sicherlich eingaben, in denen es fehlschlägt.

Answer 2

Hier ist ein Algorithmus, der in $ \ Mathcal {O} ausgeführt wird (n \ sqrt {n} + m \ log m) $ Time.

$ W $ Bezeichnen Sie die Funktion, die für Integer $ T $ , zählt die Anzahl der Paare dass ihr Unterschied $ T $ : $ w (t)=land \ {(x, y): x \ In a, y \ in b, yx= t \ \} \ rutzet $ . Wenn wir Zugriff auf $ w (t) $ hätten, können wir einfach sein Maximum finden und sehen, ob es $ n $ ist oder nicht. Die Hauptidee ist, $ W $ mit der Fast Fourier-Transformation zu schätzen. Wenn die Zahlen begrenzt sind, ergibt er die genaue Lösung, andernfalls kann man Modul mit einer ausreichend großen Anzahl verwenden und dann die Lösungen überprüfen, sobald sie gefunden wurden.

lass $ n, M $ Ganzzungen sein (später definiert) und $ u, v \ in \ mathbb {r} ^ n $ Seien Sie als Vektoren definiert als $$ u [i]=land \ {x \ in A \ Colon M-X \ EQUIV I \ PMOD N \ \ \ rvert $$ $$ V [I]=LEVERT \ {y \ in B \ Colon M + y \ Equiv i \ pmod n \ y \ Equiv i \ pmod n \ y \ rvert $$ Lassen Sie $ W= U * V $ die kreisförmige Faltung dieser beiden Vektoren bezeichnen. Wenn dann $ K $ so ist, dass $$ \ fürall x \ in A \ existiert \ in B: y-x= k, $$ Dann können wir abschließen $$ W [k \ bmod n]=sum_ {i: v [i] \ neq 0} v [i] u [ik \ bmod n]= n $$ Welcher durch die Konstruktion ist der Maximalwert, den $ W $ erreichen kann. Daher müssen wir nur überprüfen, ob $ \ max_i w (i)= n $ oder nicht. Dann überprüfen wir die Richtigkeit der Lösung, indem wir die ursprünglichen Elemente überprüfen. Computing $ W $ kann von FFT und inversen FFT in $ \ Mathcal {O} (n \ log n) $ erfolgen Uhrzeit, und dann das Maximalelement finden und prüfen, dass er $ N $ Schritte dauert, so insgesamt $ \ Mathcal {O} (n \ log n) $ Zeit und Speicherplatz.

Wenn die Zahlen in beiden Sätzen von $ N $ begrenzt sind, ist dies eine genaue Lösung. Wenn Sie jedoch $ N $ zu klein auswählen, $ W (i)= n $ kann wegen Kollisionen. So können wir alle Elemente für alle Indizes überprüfen, die $ W (i) \ ge n $ ; Es kann mehrere von ihnen geben, aber ihre Anzahl kann begrenzt werden. Um $ \ ell $ solcher Indizes zu haben, muss man mindestens $ 1 + 2 + \ dots + \ ell $ Kollisionen, die impliziert $$ P [\ land \ {I \ Colon W [I] \ GE N \ \ \ \ REVERT \ GE \ ELL] \ le p [\ text {# Collisions} \ ge ( \ ell + 1) \ ell / 2]. $$ Es gibt $ nm $ Paare von Elementen von $ A $ und $ B $ . Wenn wir eine Prime-Nummer auswählen $ N $ , so dass $ n> 2m $ und wählen Sie $ M $ Gleichmäßig zufällig von $ \ {1, \ dots, n \} $ , ist die Kollisionswahrscheinlichkeit begrenzt von $ 1/2m $ , so von Markovs Ungleichung ist $$ \ le \ frac {nm / n} {\ ell ^ 2/2} \ le \ frac {n} {\ \ \ frac {n} {\ ell ^ 2} $$ Also mit der Wahrscheinlichkeit wie in der Nähe von $ 1 $ wie gewünscht, $ \ ell= matcal {o} (\ sqrt {n }) $ . Daher ist die Gesamtkomplexität des Algorithmus $$ \ Mathcal {O} (n \ sqrt {n} + m \ log m) $$ In welcher $ m \ log M $ ist der FFT- und IFFT-Schritt (da wir $ n= 2m $ ), und $ n \ sqrt {n} $ ist der Überprüfungsschritt.

Es gibt zwei Möglichkeiten, um dies zu verbessern:

.
1. man kann $ \ log n $ separate Instanzen des Algorithmus ohne Überprüfung ausführen, und nehmen Sie die Kreuzung der maximalen Indizes, die $ W [I] \ GE N $ (nach dem Verschieben von $ M $ ). Wenn man zeigen kann, dass die Anzahl der gemeinsam genutzten Kollisionen von $ 1/2 $ jedes Mal fällt, zeigt dies eine Gesamtlaufzeit von $ \ mathcal {O} (m \ log ^ 2 m) $ .
2. man kann einen besseren Hash-Mechanismus für $ U $ und $ V $ und verwenden Höhere Momente für Markov und machen den Konzentrationsscheider.

Trotzdem, wenn Sie nach einer praktischen Lösung suchen, könnte dieser Algorithmus gut funktionieren. Zum Beispiel die Früchte

T-Case-Verhalten $ \ \ \ \ \ ca. \ SQRT {n} $ erfolgt nur, wenn die Sets nahezu arithmetische Fortschritte sind.Wenn Sie fast zufällig Elemente auswählen, wird die Garantie viel stärker sein.Außerdem können Sie den Überprüfungsschritt aufhalten, sobald Sie einen Fehler finden.

Answer 3

Dies ist ein völlig unterschiedlicher Algorithmus, den ich glaube, dass Arbeiten in $ O (m \ log M) $ schlechteste Fall und sollte für ganzzahlige oder reelle Zahlen arbeiten.

lassen Sie uns annehmen, dass $ A $ und $ B $ bereits in aufsteigender Reihenfolge vorhanden sind, sonst ausgeben $ o (n \ log n + m \ log m) $ , um sie zu sortieren. Wir stärken die Anforderung für den Algorithmus $ \ Mathcal {A} (A, B) $ , um alle Indizes $ I $ zurückzugeben so, dass $ A $ auf $ B $ mit Offset $ k= B_I-A_1 $ , was bedeutet, dass das Mapping bei $ B_i $ beginnt. Die hochrangige Idee ist es, die Unterprobleme zu lösen, die einem Unterarray von $ A $ entsprechen, und die Indizes in einer Weise zusammenführen, dass nur gültige Lösungen bleiben.

Der Rekursion hängt jedoch davon ab, wie eng $ A $ zu einem arithmetischen Fortschritt ist. Lassen Sie förmlich per Periodizität $ \ tau (a) $ definiert als: $$ \ tau (a)=min \ {s \ in \ mathbb {n} ^ +: a_ {i + s + 1} -a_ {i + s}= A_ {i + 1} - A_i \ Text {für alle gültigen} i, s \} $$ In Worten bedeutet dies Elemente von $ A $ , sind periodisch mit einem Mindestzyklus $ \ tau (a) $ bis zu einem Versatz.

case i ( $ \ tau (a) let $ s=tau (a) $ und $ \ ell= a_s - A_1 $ . Rekursiv berechnen $ i=Mathcal {A} (A [1: S], B) $ . Eine Beobachtung ist, dass, wenn $ i, j \ in i $ , entsprechend Index-Sets $ j_i, j_j $ , und $ b_j - b_i=ell $ , die Index-Sets $ j_i, j_j $ kann sein Verkettet, um $ i \ in \ matcal {a} (A [1: 2S], B) $ zu zeigen. Dies ist eine einfache Folge von $ A $ Sein $ S $ periodic und $ b_j= b_i + \ ell $ stellt sicher, dass der Index-Set $ j_j $ beginnt, wo $ J_i $ endet. Lassen $$ R [I]=LEVERT \ {J \ in i \ colon j> i, b_j - b_i \ text {teilbar von} \ \ \ \} \ rvert $$ Dann $ r [i] $ kann basierend auf $ r [i '] $ so berechnet werden < Span-Klasse="Math-Container"> $ i '> i $ , und der neue Indexsatz $ I' $ , ist die Indizes, die $ R [I] \ ge n / s $ . Die Kosten für diesen Schritt werden von $ O (m) $ begrenzt.

case ii ( $ \ tau (a)> n / 3 $ ) : per Definition, für $ s= N / 3 $ Es sollte einen Index $ i $ diese $ A_ geben {i + 1} -a_i \ neq a_ {i + 1 + s} -A_ {i + s} $ . Wenn $ I \ le n / 3 $ , haben wir $ i, i + s \ le 2n / 3 $ < / span> das bestätigt, dass $ \ tau (A [1: 2n / 3])> N / 3 $ . Andernfalls bedeutet $ i> n / 3 $ impliziert, dass $ \ tau (a [n / 3: n])> n / 3 $ .

wlog übernehmen $ \ tau (A [1: 2n / 3)> N / 3 $ , und wählen Sie die untere Hälfte $ A '= a [1: n / 2] $ Um einzukommen (Andernfalls wählen Sie die obere Hälfte aus, die gleichen Argumente würden folgen). Rekursiv berechnen $ i=Mathcal {A} (A ', B) $ . Für jeden Index $ i \ in i $ prüfen Sie, ob der Rest der Sequenz in $ B $ . Da beide Sequenzen sortiert sind, kann dies in $ O (N) $ für jeden Index erfolgen, der einen Gesamtbereich $ impliziert O (| i | \ cdot n) $ Zeit, um die gültigen Indizes zu berechnen und sie als $ \ Mathcal {a} (a, b) $ . Die Effizienz dieses Schritts ist auf den folgenden Anspruch angewiesen:

claim: $ | I | \ le 6m / n $ , was bedeutet, dass Lösungen nicht zu viel überlappen sind.

Nachweis des Anspruchs: wir zeigen $ | i |> 6m / n $ führt zu einem Widerspruch. Jeder Index $ i \ in i $ ist der Startpunkt eines Satzes von Indizes $ j_i= {i= j_1, \ dots, j_ {n / 2} \} \ SubseteQ B $ , diese Karte $ A '$ bis $ B $ bis zu einem Versatz. Spalte

Vortragsweise gibt es mindestens $ 3M $ Indizes: $$ \ SUM_ {I \ in i} | j_i |= | I | n / 2 \ ge 6m / n \ cdot n / 2= 3m $$ Seit $ | B |= M $ , durch Pigeonloch-Prinzip gibt es mindestens einen Index $ x \ in B $ < / span> erscheint in 3 separaten Lösungen: $$ \ existiert X \ in B, R, S, P \ in I \ Colon \; x \ in j_r \ cap j_s \ cap j_p $$

Lassen Sie $ S $ Seien Sie der Median der drei $ R . Da $ X \ in J_S $ und $ | j_s |= n / 2 $ , $ x $ Partitionen $ J_S $ bis zwei Teile, von denen eines weniger als $ N / 4 $ Indizes, die wir annehmen, ist der untere Teil: $$ J_S={j_1= s, j_2, \ \ dots, j_ \ ell= x \}, \ ell \ le n / 4 $$ Durch den Bau, $ s= j_1 $ wird auf $ A_1 $ bis zu $ a_ \ ell $ bis zu einem Versatz. Wir haben aber auch $ x \ in j_p $ , dies impliziert einen perforitor weniger als $ \ ell \ le n / 4 $ in $ A '$ , das $ \ tau (A')> N / 3 $ . (Es gibt ein paar Details, die ich später hinzufügen werde)

Gesamtkomplexität Bei jedem Schritt des Rekursion zahlen wir $ o (m) $ . Die Periodizität $ \ tau (a) $ kann auch in $ o (n) $ berechnet werden Berechnen des längsten Suffix, das auch Präfix von $ \ mathrm {diff} (a) $ ist, dh der Inkrementarray $ a_2-a_1, \ dots, a_n-a_ {n-1} $ . Die Größe des Problems verringert jedoch von mindestens $ 1/2 $ in jedem rekursiven Schritt. Es gibt $ \ log N $ Schritte im schlimmsten Fall, in dem die Zeitkomplexität von $ O (M \ log n) $ . Hinzufügen der Sortierkosten, und da $ M> N $ , wird die Gesamtkomplexität durch die Sortierzeit $ O (M \ log m) $