Test s'il existe un entier K pour ajouter à une séquence pour en faire une ultérieurement d'une autre séquence

Question

supposons que la séquence $ a $ contient $ n $ entiers $ a_1, a_2, a_3, \ ldots, a_n $ et séquence $ b $ contient M $ M $ nombres entiers $ b_1, b_2, b_3, \ ldots, b_m $ . Nous savons que $ m \ geq n $ . Nous supposons sans perte de généralité que les deux séquences $ a $ A $ et $ B $ sont triés par ordre croissant.

Quel est l'algorithme le plus rapide de déterminer s'il existe un entier $ k $ tel que la séquence $ A_1 + K, a_2 + k, a_3 + k, \ ldots, a_n + k $ est une recherchequence de la séquence $ B $

Voici un algorithme naïf, qui prendrait $ O (n (m-n)) $ temps. Stockez la séquence $ B $ en tant que hashtable. Pour chaque élément $ b_j $ de la $ B $ (à l'exception de la plus grande classe $ N $ éléments), utilisez $ b_j-a_1 $ comme vous devinez à $ k $ ; Vous pouvez vérifier cette hypothèse en vérifiant si chacun de $ a_1 + k, \ dots, a_n + k $ est dans la haquetable $ B $ . Cela prend $ o (n) $ temps attendu par maine à $ k $ , et vous faites $ Mn $ suppose, donc au total, le temps d'exécution attendu est $ o (n (mn)) $ . Pouvons-nous faire mieux?

Je suis tombé sur ce problème tout en essayant de faire correspondre deux images binaires (test si une image contient l'autre).

Answer 1

Voici une heuristique qui ne fonctionnera pas toujours, mais devrait fonctionner avec une probabilité élevée si les entiers des tableaux sont choisis de manière aléatoire d'un espace suffisant.

Initialiser une haquetable de comptes $ C $ à tous les zéros. Ensuite, répétez $ t $ fois: choisissez au hasard $ i, j $ , calcule $ b_j-a_i $ et incrément $ c [b_j-a_i] $ . Enfin, trier $ C $ C $ par comptes, du plus grand nombre de comptes au plus petit; Ensuite, pour chacune des plus grandes valeurs de $ c [k '] $ , essayez $ k' $ comme vous devinez à $ k $ et vérifiez chaque devinière.

Notez que dans chaque itération, la probabilité d'incrémenter $ c [k] $ est au moins 1 $ / M $ ; tandis que si $ l \ ne k $ k $ , nous attendons $ c [l] $ est incrémenté beaucoup plus rarement (en supposant que les entiers dans les matrices sont aléatoires et assez grandes). Ainsi, après $ t $ itérations, nous attendons $ \ mathbb {e} [c [k]] \ ge t / M $ mais $ \ mathbb {e} [c [l]] \ ll t / m $ . Donc, une fois $ t $ est assez grand, $ c [k] $ doit être plus grand que tous les autres entrée dans $ C $ .

Quelle est la taille $ t $ doit être? Je m'attends à ce que $ t= O (m \ log m) $ devrait suffire, basé sur une approximation du théorème limite central pour les comptes $ C [L] $ , en supposant que nous soyons disposés à accepter une petite probabilité d'erreur (pouvant être conduite de manière exponentielle). Le facteur constant caché par la notation Big-O pourrait être non trivial.

Ce n'est qu'une heuristique et il y aura certainement des intrants où il échoue.

Answer 2

Voici un algorithme exécuté dans $ \ mathcal {o} (n \ sqrt {n} + m \ log m) $

heure.

let $ w $ désigne la fonction que pour entier $ t $ , compte le nombre de paires que leur différence est $ t $ : $ w (t)=lverver \ {(x, y): x \ Dans A, y \ in b, yx= t \} \ rvvert $ . Si nous avions accès à $ w (t) $ nous pourrions simplement trouver son maximum et voir si c'est $ n $ ou non. L'idée principale est d'estimer $ w $ à l'aide de la transformée Fausse Fourier. Si les numéros sont limités, il produira la solution exacte, sinon, on peut utiliser un module à un chiffre suffisamment grand, puis vérifiez les solutions une fois qu'ils sont trouvés.

let $ n, m $ être entiers (à définir ultérieurement), et u, v \ in \ mathbb {r} ^ n $ soit des vecteurs définis comme $$ u [i]=lverver \ {x \ dans un \ colon m-x \ equiv i \ pmod n \} \ rvert $$ $$ v [i]=lverver \ {y \ in b \ colon m + y \ equiv i \ pmod n \} \ rvert $$ Laissez $ w= u * v $ désignant la convolution circulaire de ces deux vecteurs. Ensuite, s'il y a $ k $ tel que $$ \ Forall X \ \ existe y \ in b: y-x= k, $$ Ensuite, nous pouvons conclure $$ w [k \ bmod n]=sum_ {i: v [i] \ neq 0} v [i] u [ik \ bmod n]= n $$ Ce que, par construction, est la valeur maximale que $ w $ peut atteindre. Par conséquent, nous n'avons besoin que de vérifier si $ \ max_i w (i)= n $ ou non. Ensuite, nous vérifions l'exactitude de la solution en cochant les éléments d'origine. Computing $ w $ peut être effectué par FFT et FFT inverse dans $ \ mathcal {o} (n \ journal n) $ temps, puis trouvant l'élément maximum et vérifiant qu'il faut $ n $ étapes, donc globalement $ \ mathcal {O} (n \ journal n) $ temps et espace.

Si les chiffres des deux ensembles sont délimités par $ n $ ceci est une solution exacte. Mais si vous choisissez $ n $ trop petit, $ w (i)= n $ peut arriver à cause de collisions. Afin que nous puissions vérifier tous les éléments de tous les indices que $ w (i) \ ge n $ ; Il pourrait y avoir plusieurs d'entre eux, mais leur nombre peut être délimité. Avoir $ \ ell $ de tels indices, il faut avoir au moins 1 + 2 + \ dots + \ ell $ Collisions, qui implique $$ p [\ lverver \ {i \ colon w [i] \ ge n \ \ \ rvert \ ge \ ell] \ Le p [\ texte {# Collisions} \ ge ( \ ell + 1) \ ell / 2]. $$ Il y a $ nm $ des appariements d'éléments de $ A $ A $ et $ B $ . Si nous choisissons un nombre premier $ n $ tel que N> 2m $ et choisissez $ m $ uniformément au hasard à partir de $ \ {1, \ dots, n \} $ , la probabilité de collision est borné par 1 $ / 2m $ , donc par l'inégalité de Markov est donc $$ \ le \ frac {nm / n} {\ ell ^ 2/2} \ le \ frac {n} {\ ell ^ 2} $$ Donc, avec probabilité que près de 1 $ comme vous le souhaitez, $ \ ell=mathcal {o} (\ sqrt {n }) $ . Par conséquent, la complexité du temps global de l'algorithme est $$ \ mathcal {o} (n \ sqrt {n} + m \ log m) $$ dans lequel $ m \ journal m $ est l'étape FFT et IFFT (puisque nous définissons $ n= 2m $ ), et $ n \ sqrt {n} $ est l'étape de vérification.

Il y a deux façons de voir pour améliorer ceci:

1. on peut exécuter $ \ journal n $ des instances séparées de l'algorithme sans vérification et prenez l'intersection des indices maximaux que $ w [i] \ ge n $ (après le déplacement de $ M $ ). Si on peut montrer que le nombre de collisions partagées tombe par 1/2 $ ou une autre constante à chaque fois, cela montrerait une durée totale de $ \ mathcal {o} (m \ journal ^ 2 m) $ .
2. on peut construire un meilleur mécanisme de hachage pour $ u $ u $ et $ v $ et utilisation Moments plus élevés pour Markov et faire la concentration plus nette.

Néanmoins, si vous recherchez une solution pratique, cet algorithme pourrait bien fonctionner. Par exemple, le monde

T-Case Comportement $ \ ell \ envnrevement \ sqrt {n} $ $ ne se produit que lorsque les ensembles sont presque des progressions arithmétiques.Si vous choisissez des éléments presque au hasard, la garantie sera beaucoup plus forte.De plus, vous pouvez arrêter l'étape de vérification dès que vous trouverez une erreur.

Answer 3

C'est un algorithme complètement différent, que je crois fonctionne dans $ o (m \ log m) $ pire des cas et devrait fonctionner pour des nombres entier ou réel.

laissez-nous supposer que $ a $ a $ et $ B $ est déjà en ordre croissant, sinon dépenser $ O (n \ journal n + m \ journal m) $ Pour les trier. Nous renforçons légèrement l'exigence d'algorithme $ \ mathcal {a} (a, b) $ pour renvoyer tous les indices $ i $ tel que $ a $ peut être mappé sur $ b $ avec décalage $ k= b_i-a_1 $ , ce qui signifie que le mappage commence à $ b_i $ . L'idée de haut niveau consiste à résoudre les sous-problèmes correspondant à une sous-carrose de $ a $ et fusionner les indices d'une manière que seules des solutions valides subsistent.

La récursion dépend cependant de la fermeture $ a $ est à une progression arithmétique. Formellement, que la périodicité $ \ tau (a) $ soit définie comme suit: $$ \ tau (a)=min \ {s \ in \ mathbb {n} ^ +: a_ {i + s + 1} -a_ {i + s}= a_ {i + 1} - a_i \ texte {pour tous valide} i, s \} $$ En mots, cela signifie des éléments de $ a $ , sont périodiques avec un cycle minimum $ \ tau (a) $ , jusqu'à un certain décalage.

cas i ( $ \ tau (a) let $ S=tau (a) $ et $ \ ell= a_s - a_1 $ . Calculer de manière récursive $ i=mathcal {a} (a [1: s], b) $ . Une observation est que si i $ i, j \ in i $ , correspondant aux ensembles d'index $ j_i, j_j $ , et $ b_j - b_i=ell $ , l'index définit $ j_i, j_j $ peut être Concaténé pour montrer $ I \ IN \ MATHCAL {A} (A [1: 2S], B) $ . Ceci est une conséquence simple de $ a $ étant $ s $ périodique et $ b_j= b_I + \ ell $ garantit que l'index défini $ J_J $ commence où $ J_i $ se termine. Laisser $$ r [i]=lverver \ {j \ in i \ colon j> i, b_j - b_i \ texte {divisible par} \ ell \} \ rver $$ Alors, $ r [i] $ peut être calculé sur la base de $ r [i '] $ que < SPAN CLASS="MATH-CONTAINER"> I $ I '> I $ et le nouveau SET INDEX $ I' $ est les indices que $ R [I] \ ge n / s $ . Le coût de cette étape est délimité par $ o (m) $ .

cas ii ( $ \ tau (a)> n / 3 $ ) : par définition, pour $ s= n / 3 $ Il devrait y avoir un index $ i $ que $ a_ {i + 1} -a_i \ neq a_ {i + 1 + s} -a_ {i + s} $ . Si $ I \ le n / 3 $ , nous aurons $ i, i + s \ le 2n / 3 $ < / span> qui certifie que $ \ tau (A [1: 2N / 3])> N / 3 $ . Sinon, $ i> n / 3 $ implique que $ \ tau (A [n / 3: N])> n / 3 $ .

wlog suppose $ \ tau (a [1: 2n / 3)> n / 3 $ , puis choisissez la moitié inférieure $ A '= a [1: N / 2] $ pour recueil sur (Choisissez autrement la moitié supérieure, les mêmes arguments suivraient). Calculer de manière récursive $ I=MATHCAL {A} (A ', B) $ . Pour chaque index $ I \ in i \ in i $ , vérifiez si le reste de la séquence peut être trouvé dans $ B $ . Étant donné que les deux séquences sont triées, cela peut être effectué dans $ o (n) $ étape pour chaque index, qui implique une $ O (| i | \ CDOT N) $ Time pour calculer les indices valides et les renvoyer comme $ \ mathcal {A} (A, B) $ . L'efficacité de cette étape repose sur la revendication suivante:

réclamation: $ | I | \ LE 6M / N $ , ce qui signifie que les solutions ne se chevauchent pas trop.

Preuve de réclamation: Nous montrons $ | i |> 6m / n $ conduit à une contradiction. Chaque index $ i \ in i $ est le point de départ d'un ensemble d'indices $ j_i={i= j_1, \ dotes, j_ {n / 2} \} \ sous-étatsq b $ , cette carte $ a '$ to $ B $ jusqu'à certains offset. Col

Lectural, il y a au moins $ 3M $ indices: $$ \ sum_ {i \ in i} | J_I |= | I | N / 2 \ GE 6M / N \ CDOT N / 2= 3M $$ Puisque $ | b |= m $ , par principe de pigeonhole, il y a au moins un index $ x \ in b $ < / Span> apparaît dans 3 solutions distinctes: $$ \ existe x \ in b, r, s, p \ in i \ colon \; x \ in j_r \ cap j_s \ cap j_p $$

let $ S $ soit la médiane des trois $ r . Depuis $ x \ in j_s $ et $ | j_s |= n / 2 $ , $ x $ $ partitions $ j_s $ à deux parties, dont l'un devrait avoir moins de $ N / 4 $ indices, que nous supposons est la partie inférieure: $$ j_s={j_1= s, j_2, \ dots, j_ \ ell= x \}, \ ell \ le n / 4 $$ Par construction, $ s= j_1 $ est mappé sur $ a_1 $ , jusqu'à $ a_ \ ell $ jusqu'à certains offset. Mais nous avons aussi $ x \ in j_p $ , cela implique une période de moins de $ \ ell \ le n / 4 $ in $ a '$ , qui contredit $ \ tau (a')> n / 3 $ . (Il y a quelques détails que je vais ajouter plus tard)

complexité globale À chaque étape de la récursion, nous payons $ o (m) $ . La périodicité $ \ tau (a) $ peut également être calculée dans $ o (n) $ , par Calculer le suffixe le plus long qui est également préfixe, de $ \ mathrm {diff} (a) $ , c'est le tableau d'incrément $ A_2-A_1, \ points, a_n-a_ {n-1} $ . Cependant, la taille du problème diminue par au moins 1/2 $ dans chaque étape récursive. Il y aura $ \ journal n $ pas dans le pire des cas, ce qui implique la complexité de temps est délimitée par $ o (m \ Journal n) $ . Ajout des coûts de tri, et étant donné que $ m> n $ , la complexité globale est délimitée par l'heure de tri $ o (m \ journal m) $