الالتقاء في المنتصف
تقسيم البحث إلى نصفين لتقليل الأس
الالتقاء في المنتصف درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
عندما تكون القوة الغاشمة بطيئة جدًا
تحتوي بعض المسائل على N قريب من 40، حيث تصبح تجربة جميع المجموعات الجزئية البالغ عددها 2^N مستحيلة عمليًا. تنقذ تقنية التقسيم إلى نصفين هذه الحالات متوسطة الحجم. 🤝
الفكرة الأساسية
قسّموا المدخل إلى نصفين. عالجوا كل نصف بالقوة الغاشمة، ثم ادمجوا النتيجتين الجزئيتين بذكاء.
تقليص الأس
يكلف النصفان، وكل منهما بحجم N/2، مقدارًا قدره 2^(N/2) بدلًا من 2^N إجمالًا. ويحوّل هذا التقليص بمقدار الجذر التربيعي 2^40 إلى 2^20 يسهل التعامل معه.
هدف كلاسيكي: مجموع مجموعة جزئية
اسألوا ما إذا كانت هناك مجموعة جزئية يساوي مجموعها هدفًا قدره T. وتُعد مسألة مجموع المجموعة الجزئية عندما تكون N قريبة من 40 المثال القياسي للتقسيم إلى نصفين.
تعداد النصف الأول
أدرجوا مجموع كل مجموعة جزئية من النصف الأيسر وخزنوها. ومع وجود N/2 عنصرًا، لا يتجاوز ذلك 2^(N/2) مجموعًا.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []تعداد النصف الثاني
افعلوا الشيء نفسه مع النصف الأيمن، وأنشئوا قائمته الكاملة من مجموعات المجموعات الجزئية. أصبح لديكم الآن قائمتان يمكن التعامل معهما.
الدمج باستخدام بحث
لكل مجموع أيمن r، تحتاجون إلى مجموع أيسر يساوي T ناقص r. وتجعل المجموعة أو القائمة المرتبة هذا الفحص سريعًا.
need = T - r
found = need in left_setطريقتان للمطابقة
للأهداف الدقيقة، استخدموا مجموعة تجزئة. أما للعدّ أو للعثور على أقرب مجموع، فرتبوا أحد النصفين وأجروا بحثًا ثنائيًا فيه.
كلفة الزمن
يبلغ إجمالي العمل تقريبًا 2^(N/2) مضروبًا في عامل لوغاريتمي ناتج عن البحث أو الترتيب. وهذا التعقيد هو ما يجعل التعامل مع N القريبة من 40 ممكنًا.
الذاكرة هي المقايضة
تخزنون نصفًا كاملًا، لذا تنمو الذاكرة إلى 2^(N/2). احتفظوا بما تحتاجونه فقط للبقاء ضمن الحد المسموح.
تطبيقات أخرى تتألق فيها
إلى جانب مجموع المجموعة الجزئية، استخدموها لتعظيم مجموعة جزئية ضمن حد، وعدّ الأزواج، ومسائل شبيهة باللوغاريتم المتقطع. فهي تناسب التقسيم الواضح.
تحقق سريع
تطبقون تقنية التقسيم إلى نصفين على مسألة مجموعات جزئية تحتوي على N عنصرًا. ما كلفة الزمن التقريبية؟
مراجعة
قسّموا المسألة إلى نصفين، وطبّقوا القوة الغاشمة على كل منهما، ثم طابقوا بين المجاميع اليسرى واليمنى. لقد ضحيتم بقدر صغير من الذاكرة مقابل تسريع هائل. 🚀
الأسئلة الشائعة
هل درس «الالتقاء في المنتصف» مجاني؟
نعم — نص درس «الالتقاء في المنتصف» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «الالتقاء في المنتصف»؟
تقسيم البحث إلى نصفين لتقليل الأس تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «الالتقاء في المنتصف»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حالات الفوز والخسارة في الألعاب
- لعبة Nim وعدد Grundy
- الالتقاء في المنتصف
- تصحيح الأخطاء بسرعة: اختبارات الضغط والفرز