اختبار إذا كان هناك عدد صحيح ك لإضافة إلى تسلسل واحد لجعله لاحقا تسلسل آخر

Question

لنفترض أن التسلسل $ A $ يحتوي على $ n $ أعداد صحيحة $ a_1، a_2، a_3، \ Ldots، a_n $ وتسلسل $ B $ يحتوي على $ m $ أعداد صحيحة $ b_1، b_2، b_3، \ ldots، b_m $ . نحن نعرف أن $ m \ geq n $ . نحن نفترض دون فقدان عمومية أن كلا التسلسلين $ $ و $ B $ يتم فرزها بترتيب تصاعدي.

ما هي أسرع الخوارزمية لتحديد ما إذا كان هناك عدد صحيح $ K $ مثل التسلسل $ a_1 + k، a_2 + k، a_3 + k، \ ldots، a_n + k $ هو لاحق التسلسل $ B $ ؟

هنا خوارزمية ساذجة، والتي ستأخذ $ O (n (m-n)) $ الوقت. قم بتخزين التسلسل $ B $ كقابل. لكل عنصر $ b_j $ من $ B $ (باستثناء أكبر $ N $ عناصر)، استخدم $ b_j-a_1 $ كما تخمين في $ k $ ؛ يمكنك التحقق من هذا التخمين من خلال التحقق مما إذا كان كل من $ a_1 + k، \ dots، a_n + k $ موجود في $ B $ . هذا يأخذ $ O (n) $ الوقت المتوقع لكل تخمين في $ K $ ، وأنت تصنع $ MN $ التخمينات، لذلك في إجمالي وقت التشغيل المتوقع هو $ O (n (mn)) $ . هل يمكننا أن نفعل أفضل؟

صادفت هذه المشكلة أثناء محاولة مطابقة صورتين ثنائية (اختبار ما إذا كانت صورة واحدة تحتوي على الآخر).

Answer 1

هنا هو مزعجة لن تعمل دائما، ولكن يجب أن تعمل مع احتمال كبير إذا تم اختيار الأعداد الصحيحة في الصفائف بشكل عشوائي من مساحة كبيرة بما فيه الكفاية.

تهيئة hashtable من التهم $ C $ إلى جميع الأصفار. ثم، كرر $ t $ times: اختيار عشوائيا $ i، j $ ، حساب $ b_j-a_i $ ، والزيادة $ c [b_j-a_i] $ . أخيرا، فرز $ C $ حسب التهم، من أكبر عدد إلى الأصغر؛ ثم لكل من أكبر قيم قليلة ل $ c [k '] $ ، حاول $ k' $ كما تخمينك في $ k $ ، والتحقق من كل تخمين.

لاحظ أنه في كل تكرار، احتمال زيادة $ c [k] $ هو على الأقل $ 1 / m $ ؛ في حين أنه $ l \nk $ ، نتوقع $ c [l] $ ليتم زيادة المزيد نادرا (على افتراض أن الأعداد الصحيحة في الصفائف عشوائية وكبيرة بما فيه الكفاية). وبالتالي، بعد $ T $ التكرار، نتوقع $ \ mathbb {e} [c [k]] \ ge t / M $ ولكن $ \ mathbb {e} [c [l]] \ ll t / m $ . لذلك، بمجرد $ T $ كبير بما فيه الكفاية، يجب أن تكون $ c [k] $ أكبر من كل شيء آخر الدخول في $ c $ .

كيف كبيرة $ t $ تحتاج إلى أن تكون؟ أتوقع أن $ t= o (m \ log m) $ يجب أن يكفي، استنادا إلى نظرية النظرية المركزية تقريبية للتهم $ c [l] $ ، على افتراض أننا على استعداد لقبول احتمال حدوث خطأ صغير (والتي يمكن أن تكون مدفوعة صغيرة بشكل كبير). قد يكون العوامل المستمرة المخفية من قبل التدوين Big-o غير تافهة.

هذا هو مجرد إرشادي، وسوف يكون هناك بالتأكيد مدخلات حيث يفشل.

Answer 2

هنا هي خوارزمية تعمل في $ \ mathcal {o} (n \ sqrt {n} + m \ log m) $ الوقت.

دع $ W $ تدل على الوظيفة التي لحقت عددا صحيحا $ T $ ، تحسب عدد الأزواج أن اختلافهم هو $ T $ : $ w (t)=lvert \ {(x، y): x \ في A، Y \ في B، YX= T \} \ Rents $ . إذا تلقينا الوصول إلى $ w (t) $ يمكننا ببساطة العثور على الحد الأقصى لمعرفة ما إذا كان $ n $ أم لا. الفكرة الرئيسية هي تقدير $ W $ باستخدام تحويل fourier سريع. إذا تم حدوبة الأرقام، فسوف تنتج الحل الدقيق، وإلا، يمكن للمرء استخدام المعدض إلى رقم كبير بما فيه الكفاية ثم تحقق من الحلول بمجرد العثور عليها.

دع $ n، m $ تكون أعداد صحيحة (يتم تعريفها لاحقا)، و $ u، v \ in \ Mathbb {r} ^ n $ يكون ناقلات محددة $$ U [i]=lvert \ {x \ {{x \ in a \ colon m-x \ equiang i \ pmod n \} \ chvert $$ $$ v [i]=lvert \ {y \ in b \ colon m + y \ pmod n \} \ chvert $$ دع $ w= u * v $ تشير إلى التنزل الدائري لهذين الموعودين. ثم إذا كان هناك $ k $ مثل ذلك $$ \ forall x \ in a \ at \ in b: y-x= k، $ ثم يمكننا أن نستنتج $$ ث [k \ bmod n]=sum_ {i: v [i] \ neq 0} v [i] u [ik \ bmod n]= n $ الذي عن طريق البناء هو الحد الأقصى للقيمة التي $ W $ يمكن تحقيقها. لذلك، نحن نحتاج فقط إلى التحقق مما إذا كانت $ \ max_i w (i)= n $ أم لا. بعد ذلك، نتحقق من صحة الحل عن طريق التحقق من العناصر الأصلية. الحوسبة $ W $ يمكن القيام بها بواسطة FFFT والكفطاء FFT في $ \ mathcal {o} (n \ log n) $ الوقت، ثم العثور على العنصر الأقصى والتحقق من أنه يأخذ $ N $ الخطوات، لذلك بشكل عام $ \ mathcal {o} (n \ log n) $ الوقت والمساحة.

إذا كانت الأرقام الموجودة في كلا المجموعتين تحدها $ n $ هذا هو الحل الدقيق. ولكن إذا اخترت $ n $ صغير جدا، $ w (i)= n $ يمكن أن يحدث بسبب الاصطدامات. حتى نتمكن من التحقق من جميع العناصر لجميع المؤشرات التي $ w (i) \ ge n $ ؛ قد يكون هناك العديد منهم، ولكن عددهم يمكن حدودا. أن يكون لديك $ \ ell $ مثل هذه المؤشرات، يجب أن يكون لدى المرء على الأقل $ 1 + 2 + dots + \ ELL $ الاصطدام، مما يعني $$ p [\ lvert \ {i \ colon w [i] \ ge n \} \ rvert \ ge \ ell] \ le p [\ text {# التصادم} \ ge ( \ ell + 1) \ ell / 2]. $$ هناك $ NM $ الاقتران عن عناصر $ $ و $ B $ . إذا اخترنا الرقم الأول $ n $ مثل $ n> 2m $ ، والاختيار $ m $ بشكل موحد عشوائي من $ \ {1، \ dots، n \} $ ، يحد احتمال الاصطدام بواسطة $ 1 / 2m $ ، لذلك بقلم عدم المساواة ماركوف $$ \ le \ frac {nm / n} {nm / n ^ 2/2} \ Le \ frac {n} {\ ell ^ 2} $ لذلك مع احتمال قريبة من $ 1 $ كما تريد، $ \ ell=mathcal {o} (\ sqrt {n }) $ . لذلك، فإن التعقيد الزمني الشامل للخوارزمية $$ \ mathcal {o} (n \ sqrt {n} + m \ log m) $ حيث $ m \ log m $ هو خطوة fft و ifft (نظرا لأننا وضعنا $ n= 2m $ )، و $ n \ sqrt {n} $ هي خطوة التحقق.

هناك طريقتان أرى لتحسين هذا:

1. يمكن للمرء تشغيل $ \ log n $ منفصلة من حالات الخوارزمية دون التحقق، واتخاذ تقاطع الأقصى من المؤشرات التي $ w [i] \ ge n $ (بعد التحول حسب $ m $ ). إذا كان أحد يستطيع أن يظهر أن عدد الاصطدامات المشتركة قطرات $ 1/2 $ أو بعض الثابت الآخر في كل مرة، فسيظهر هذا وقت التشغيل الإجمالي $ \ mathcal {o} (m \ log ^ 2 m) $ .
2. يمكن للمرء إنشاء آلية تجزئة أفضل ل $ u $ و $ v $ واستخدام لحظات أعلى ماركوف وجعل تركيز أكثر وضوحا.

مع ذلك، إذا كنت تبحث عن حل عملي قد تعمل هذه الخوارزمية على ما يرام. على سبيل المثال، والقلبات

سلوك T-Case $ \ ell \ appally \ sqrt {n} $ يحدث فقط عندما تكون المجموعات تقديرات حسابية تقريبا.إذا اخترت العناصر بشكل عشوائي تقريبا، فسيكون الضمان أقوى بكثير.علاوة على ذلك، يمكنك إيقاف خطوة التحقق بمجرد أن تجد خطأ.

Answer 3

هذه خوارزمية مختلفة تماما، والتي أعتقد أن أعمال $ O (M \ Log M) $ أسوأ الحالات، وينبغي أن تعمل لأعداد عدد صحيح أو حقيقي.

دعونا نفترض أن $ $ و $ B $ بالفعل في ترتيب تصاعدي، وإلا تنفق $ O (n \ log n + m \ log m) $ لفرزها. نحن نعزز قليلا متطلبات الخوارزمية $ \ mathcal {a} (a، b) $ لإرجاع جميع المؤشرات $ i $ $ مثل يمكن تعيين $ إلى $ B $ مع إزاحة $ k= b_i-a_1 $ ، مما يعني أن التعيين يبدأ في $ b_i $ فصاعدا. تتمثل الفكرة الرفيعة المستوى في حل المشكلات الفرعية المقابلة لضغوط صحيحة من $ $ ودمج المؤشرات بطريقة لا تزال حلول صالحة فقط.

العودية، ومع ذلك، تعتمد على مدى قريبة $ $ في تقدم حسابي. رسميا، دع الدورية $ \ Tau (a) $ يعرف على النحو التالي: $$ \ TAU (A)=min \ {s \ in \ mathbb {n} ^ +: a_ {i + s + 1}-{i + s}= a_ {i + 1} - a_i \ text {for كل صالح} i، s \} $$ بالكلمات، وهذا يعني عناصر $ $ ، هي دورية مع الحد الأدنى لدورة $ \ Tau (a) $ حتى بعض الإزاحة.

case i ( $ \ Tau (a) دع $ s=tau (a) $ و $ \ ell= a_s - a_1 $ . حساب Offely $ i=mathcal {a} (a [1: s]، b) $ . ملاحظة واحدة هي أنه في حالة $ i، j \ in i $ ، المقابلة لمجموعات الفهرس $ j_i، j_j $ ، و $ b_j - b_i=ell $ ، يقوم الفهرس بمجموعات $ J_I، j_j $ يمكن أن يكون متسلسل لإظهار $ i \ in \ mathcal {a} (a [1: 2s]، b) $ . هذه نتيجة بسيطة ل $ A $ كونها $ S $ devidential، و $ b_j= b_i + \ ell $ يضمن أن مجموعة الفهرس $ j_j $ يبدأ حيث $ J_I $ ينتهي. يترك $$ ص [i]=lvert \ {j \} \ colon j> i، b_j - b_i \ text {قابل للقسمة بواسطة} \ ell \} \ rvert $$ ثم، $ r [i] $ يمكن حسابها بناء على $ r [i '] $ Span Class="Math-Container"> $ i '> i $ ، ومجموعة الفهرس الجديد $ i' $ ، هي المؤشرات التي $ r [i] \ ge n / s $ . تحد التكلفة لهذه الخطوة بواسطة $ O (m) $ .

case ii ( $ \ Tau (a)> n / 3 $ ) : بحكم التعريف، ل $ s= n / 3 $ يجب أن يكون هناك فهرس $ i $ $ that $ a_ {I + 1} -A_I \ NEQ A_ {I + 1 + S} -A_ {I + S} $ . إذا $ i \ le n / 3 $ ، سيكون لدينا $ i، i + s \ le 2n / 3 $ < / span> التي تشير إلى أن $ \ Tau (A [1: 2N / 3])> N / 3 $ . خلاف ذلك، $ I> N / 3 $ يعني أن $ \ Tau (a [n / 3: n])> n / 3 $ .

wlog افترض $ \ tau (a [1: 2n / 3)> n / 3 $ ، واختر أقل النصف $ a '= a [1: n / 2] $ لإعادة التواصل (خلاف ذلك اختيار النصف العلوي، ستتبع نفس الحجج). حساب جديد $ i=mathcal {a} (a '، b) $ . لكل فهرس $ I \ IN I $ ، تحقق مما إذا كان يمكن العثور على بقية التسلسل في $ B $ . نظرا لأن كلا التسللين يتم فرزها، فيمكن القيام بذلك في $ O (n) $ (n) $ خطوة لكل فهرس، مما يعني أنه $ o (| i | \ cdot n) $ الوقت لحساب المؤشرات الصحيحة، وإرجاعها ك $ \ mathcal {a} (a، b) $ . تعتمد كفاءة هذه الخطوة على المطالبة التالية:

المطالبة: $ | أنا | \ Le 6m / n $ ، وهذا يعني أن الحلول ليست متداخلة كبيرة جدا.

دليل على المطالبة: نعرض $ | I |> 6m / n $ يؤدي إلى تناقض. كل فهرس $ I \ IN I $ هو نقطة انطلاق مجموعة من المؤشرات $ j_i={i= j_1 \ النقاط، J_ {n / 2} \} \ subseteq B $ خريطة $ a '$ إلى $ B $ حتى بعض الإزاحة. كولب

بشكل مباشر، هناك على الأقل $ 3m $ المؤشرات: $$ \ sum_ {i \ in i} | J_I |= | أنا | N / 2 \ GE 6M / N \ CDOT N / 2= 3M $ منذ $ | b |= m $ ، بواسطة مبدأ pigeonhole، هناك فهرس واحد على الأقل $ x \ in b / span> يظهر في 3 حلول منفصلة: $$ \ exists x \ in b، r، s، p \ in i \ colon \؛ X \ in J_R \ CAP J_S \ CAP J_P $$

دع $ S $ تكون الوسيط من الثلاثة $ r . منذ $ x \ in j_s $ ، و $ | j_s |= n / 2 $ ، $ X $ الأقسام $ j_s $ يجب أن يكون واحدا منها أقل من $ N / 4 $ المؤشرات، والتي نفترض أنها الجزء السفلي: $$ j_s={j_1= s، j_2، \ dots، j_ \ ell= x \}، \ ell \ le n / 4 $$ بواسطة البناء، $ s= j_1 $ تم تعيينها إلى $ a_1 $ ، ما يصل إلى $ a_ \ ell $ حتى بعض الإزاحة. ولكن لدينا أيضا $ x \ في j_p $ ، وهذا يعني حصولا أقل من $ \ ell \ le n / 4 $ in $ A '$ ، مما يتناقض مع $ \ Tau (a')> n / 3 $ . (هناك عدد قليل من التفاصيل سأضيفها لاحقا)

التعقيد الشامل في كل خطوة من الخطوة، ندفع $ O (m) $ . يمكن أيضا حساب الدورية $ \ Tau (a) $ أيضا في $ O (n) $ ، بواسطة الحوسبة أطول لاحقة التي هي أيضا بادئة، من $ \ mathrm {diff} (a) $ ، وهذا هو مجموعة الزيادة $ a_2-a_1، \ dots، a_n-a_ {n-1} $ . ومع ذلك، تقلل حجم المشكلة عن طريق الأقل $ 1/2 $ في كل خطوة متكررة. سيكون هناك $ \ Log N $ الخطوات في أسوأ الحالات، مما يعني أن تعقيد الوقت يحدها $ o (m \ سجل ن) $ . إضافة تكاليف الفرز، ومنذ $ m> n $ ، يتم حدة التعقيد العام بواسطة وقت الفرز $ o (m \ Log M) $