أطول بعد شائع

Question

النظر في 2 تسلسل x [1..m] و y [1..n]. ستحسب خوارزمية Memoization LCs في الوقت O (M*n). هل هناك أي خوارزمية أفضل لمعرفة وقت LCS WRT؟ أعتقد أن المذكرة التي تم إجراؤها قطريًا يمكن أن تعطينا التعقيد الزمني (M (M ، N)).

Answer 1

توصل جين مايرز في عام 1986 إلى خوارزمية لطيفة للغاية لهذا الغرض ، الموصوفة هنا: خوارزمية اختلاف O (ND) وتغيراتها.

تستغرق هذه الخوارزمية وقتًا يتناسب مع مسافة التحرير بين التسلسلات ، لذلك يكون أسرع بكثير عندما يكون الفرق صغيرًا. إنه يعمل عن طريق الحلق على جميع مسافات التحرير الممكنة ، بدءًا من 0 ، حتى يجد مسافة يمكن بناء برنامج تحرير (في بعض النواحي عبارة عن LCS). هذا يعني أنه يمكنك "الإنقاذ مبكرًا" إذا كان الفرق يزيد عن بعض العتبة ، وهو ما يكون مريحًا في بعض الأحيان.

أعتقد أن هذه الخوارزمية لا تزال تستخدم في كثير diff التطبيقات.

Answer 2

إذا كنت تعرف مسبقًا حدًا علويًا على الحد الأقصى للحجم ك أنت تهتم ، يمكنك فرض خوارزمية LCS للخروج مبكرًا عن طريق إضافة فحص إضافي في الحلقة الداخلية. هذا يعني بعد ذلك متى k << min (m ، n) يمكنك الحصول على أوقات تشغيل صغيرة على الرغم من حقيقة أنك تقوم بـ LCS.

Answer 3

نعم ، يمكننا إنشاء خوارزمية أفضل من الطلب o (m*n) --- أي (دقيقة (م ، ن)). للعثور على طول ..... فقط قارن العناصر القطرية. وكلما تم القيام بالزيادة ، افترض أنها حدثت في C [2،2] ثم زيادة كل القيمة من C [2،2 ++] و C [2+ +، 2] بحلول 1 .. وتابع حتى c [m ، m] .. (افترض M