أطول متتالية جزئية متزايدة (LIS)
اختر أعدادًا من قائمة، من اليسار إلى اليمين، كل منها أكبر من الذي قبله. إلى أي حد يمكن أن تطول هذه السلسلة؟ السؤال بسيط بما يكفي ليظهر في كتاب ألغاز، وجوابه يربط بين لعبة ورق، وجدول كلاسيكي في البرمجة الديناميكية، وواحدة من أجمل النتائج عن الخلط العشوائي.
المسألة
إذا كانت لدينا قائمة من الأعداد، فالمتتالية الجزئية تحتفظ ببعضها بترتيبها الأصلي. وتكون متزايدة إذا كانت كل قيمة أكبر من التي قبلها. أطول متتالية جزئية متزايدة، أو LIS، هي أطول اختيار من هذا النوع. للقائمة ذات n من القيم 2ⁿ متتالية جزئية، لذا لا ينجح فحصها كلها إلا مع القوائم القصيرة جدًا.
الجدول
ليكن len[i] طول أطول متتالية جزئية متزايدة تنتهي عند الموضع i بالضبط. وهو 1 للقيمة وحدها، أو 1 + len[j] لموضع سابق j قيمته أصغر، أيهما أكبر. ينظر كل موضع إلى كل المواضع السابقة، لذا يحتاج الجدول إلى n·(n − 1)/2 مقارنة. الجواب هو أكبر len[i]، وتسجيل الموضع j الذي أعطى كل len[i] يتيح قراءة المتتالية الجزئية رجوعًا.
مثال
خذ 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. الأطوال موضعًا بموضع هي 1, 2, 1, 1, 3, 2, 3, 4, 3 و5: العدد 20 يمدّ 3, 10؛ والعدد 4 يمدّ 3؛ والعدد 6 يمدّ 4، و7 يمدّ 6، و9 يمدّ 7. القراءة رجوعًا من 9 تعطي 3, 4, 6, 7, 9، وهي متتالية جزئية متزايدة طولها 5.
طريقة أسرع: فرز الصبر
وزّع القيم كأوراق اللعب على أكوام: توضع كل قيمة على أقصى كومة إلى اليسار لا تكون ورقتها العليا أصغر منها، أو تبدأ كومة جديدة على اليمين. عدد الأكوام هو طول LIS. ولأن الأوراق العليا للأكوام مرتبة دائمًا، يمكن إيجاد الكومة الصحيحة بالبحث الثنائي، فتستغرق الطريقة كلها O(n log n) خطوة. وقد سُمّيت باسم لعبة الورق الفردية (الصبر أو السوليتير) التي تشبهها.
شيء من الرياضيات
في عام 1935 أثبت بول إردوش وجورج سيكيريش أن أي قائمة من n² + 1 عددًا مختلفًا فيها متتالية جزئية متزايدة أو متناقصة طولها n + 1. وفي عام 1961 سأل ستانيسواف أولام عن طول LIS لخلط عشوائي لـ n من الأعداد. والجواب، القريب من 2√n عندما يكون n كبيرًا، حُسم في عام 1977 على يد أناتولي فيرشيك وسيرغي كيروف، وكذلك بن لوغان ولاري شيب، وفي عام 1999 وجد جينهو بايك وبيرسي ديفت وكورت يوهانسون الشكل الدقيق لتذبذباته: توزيع تريسي–ويدوم من نظرية المصفوفات العشوائية.
استكشفها
افتح التطبيق واضغط «خطوة». العمود البرتقالي هو الموضع الذي يجري حسابه، والعمود الأزرق هو الموضع السابق الذي يُقارن به. يكبر صف «الطول» كلما وُجدت سلاسل أطول، ويتذكر صف «يأتي بعد» من أين جاءت، وفي النهاية يُقرأ الجواب رجوعًا باللون البرتقالي ويُعرض أسفل الجدول.
الأسئلة المتداولة
ما التعقيد الزمني لـ LIS؟
O(n²) بالجدول، لأن كل موضع ينظر إلى كل موضع قبله، وO(n log n) بفرز الصبر والبحث الثنائي. وكلاهما يحتاج إلى ذاكرة O(n).
كيف أجد أطول متتالية جزئية غير متناقصة؟
اسمح للقيمة بأن تأتي بعد قيمة مساوية لها: قارن باستخدام ≤ بدلًا من <. في التطبيق، حدّد خانة «السماح بالقيم المتساوية». وفي فرز الصبر، ضع كل قيمة على أقصى كومة إلى اليسار تكون ورقتها العليا أكبر منها تمامًا.
ما أطول متتالية جزئية متناقصة؟
هي المسألة نفسها مع عكس المقارنة، أو LIS للقائمة بعد قلب إشارة كل قيمة. ووفق مبرهنة إردوش–سيكيريش، تحتوي القائمة الطويلة بما يكفي دائمًا على متتالية جزئية متزايدة طويلة أو متناقصة طويلة.
ما طول LIS لقائمة عشوائية؟
لخلط عشوائي لـ n من الأعداد المختلفة، يقترب من 2√n عندما يكون n كبيرًا. ويكبر التصحيح مثل الجذر السادس لـ n، لذا فالمتوسط لألف عدد نحو 58، أي أقل قليلًا من 2√1000 ≈ 63.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب أطول متتالية جزئية متزايدة