لنتحدث عن الخوارزميات. غالبًا ما ينظر إليها المبتدئون على أنها شيء صعب ومعقد وغير مفهوم ، وهذا صحيح جزئيًا ، لكن الخوارزميات هي الأساس. وكلما زادت معرفتك بأساسيات تخصصك ، زاد احتمال تفوقك فيه.
اليوم سنلقي نظرة على مشكلة خوارزمية جميلة. لن نخيف الناس من العمل مع الخوارزميات في البداية ، لذلك في تحليلنا لن يكون هناك انتشار لأشجار من المقاطع ، ولا تحسينات متنوعة لمشكلة الحقيبة ، أو اختبارات احتمالية للبساطة. الطحالب سهلة الاستخدام.
إليك التحدي: اعثر على أقصى فرق بين الجيران.
يتم إعطاء مجموعة من الأعداد الصحيحة N. لا يتم ترتيبها بأي شكل من الأشكال ، ويمكن تكرار الأرقام. افترض أننا قمنا بفرزها وحساب الفرق بين كل زوج من العناصر المتتالية. من الضروري إيجاد الحد الأقصى من هذا الاختلاف والقيام بذلك بالطريقة المثلى.
معقد؟ يمكنك محاولة القيام بذلك قبل النقر فوق "قراءة المزيد" ، ثم التحقق من الحل.
إذا هيا بنا. أقصى فرق بين الجيران.
لنأخذ مثالاً:
دعنا نعطي مصفوفة من N = 11 عنصرًا.
أولاً ، دعنا نحل المشكلة بسذاجة ، فهي تساعد غالبًا. يمكننا أن نفعل بالضبط ما تتطلبه المشكلة منا - فرز الأعداد وإيجاد الفرق بين العناصر المتجاورة. يختلف تعقيد الحل اعتمادًا على الفرز الذي نستخدمه.
إذا أردنا استخدام qsort أو تصنيف دمجي ، ثم في المرة التعقيد... إذا علمنا أن الأرقام موزعة بكثافة على مجموعة الأعداد الصحيحة ، فيمكننا استخدام فرز العد. ثم نحصل، حيث U هو الفرق بين الحد الأقصى والحد الأدنى للعنصر. الحالة نادرة نسبيًا ، لكن الأمر يستحق تذكر هذا الاحتمال.
بعد الفرز ، نحصل على مصفوفة:
دعنا نكتب مجموعة من الاختلافات:
لقد حصلنا
على أن الحد الأقصى للاختلاف هو 6. لنفكر الآن ، هل من الممكن حل المشكلة بشكل أسرع؟ عند التكرار على أزواج من العناصر المجاورة ، سننظر في العديد من الأزواج مع اختلاف بسيط. قد لا تتمكن مثل هذه الأزواج من إعطاء الفرق الأكبر. في الواقع ، في مجموعة مرتبة لدينا زوج من الأرقام المتجاورة ، دع الفرق بين الحد الأقصى والحد الأدنى يكون ... ثم يجب أن يكون الفرق الأكبر على الأقل... هذا التقدير صحيح من خلال مبدأ Dirichlet.
إذا وضع الحمام في أقفاص وكان عدد الحمام أكبر من عدد الزنازين ، فإن قفص واحد على الأقل يحتوي على أكثر من حمام.
9 خلايا تحتوي على 10 الحمام، وفقا لمبدأ ديريتشليت، على الأقل تحتوي على خلية واحدة حمامة أكثر من واحد ( ويكيبيديا )
دع، ... و- العنصر الأول في المصفوفة المرتبة. ثم...
إذا افترضنا أن الحد الأقصى لجميع D [i] أقلثم المبلغ بالكامل سيكون بدقة أقل من U ، وهو تناقض.
رائع ، لقد حصلنا على تقدير أقل للحد الأقصى للاختلاف! الآن دعنا نحاول توطين العناصر القريبة جدًا من بعضها البعض بطريقة أو بأخرى - نقسم المقطع من الحد الأدنى إلى العنصر الأقصى إلى نصف فترات من الطول... يقع كل عنصر في نصف فاصل زمني واحد بالضبط. سنحصل على قسم لجميع العناصر في مجموعات منفصلة ، وتسمى أيضًا دفعات.
من السهل جدًا تحديد العنصر x الذي وقع فيه - تحتاج إلى حساب 1 + int ((x - a_min) / L) (نرقم من واحد) ، حيث a_min هو الحد الأدنى للعنصر في المصفوفة A ، يمكن العثور عليه في مسار واحد المجموعة الأصلية. سيكون الاستثناء الوحيد هو الحد الأقصى للعنصر - من الأفضل إنشاء عناصر بهذه القيمة في دفعة منفصلة.
يوضح الشكل التوزيع من المثال الموضح أعلاه. من أجل الوضوح ، لنفعل ذلك بأيدينا:
يتم تنفيذ توزيع الدُفعات في الوقت الخطي ويتطلب ذلك ذاكرة إضافية. يرجى ملاحظة أن العناصر من دفعة واحدة لا يمكن أن تعطي أقصى فرق بين عنصرين. لقد اخترنا حجمها بشكل خاص بهذه الطريقة.
أين يمكن أن يكون هناك عنصرين متجاورين؟ بالطبع ، في الدُفعات المجاورة غير الفارغة! على سبيل المثال ، في الشكل ، يمكن أن تنتقل العناصر من الدُفعة الثالثة والسادسة في صف في مصفوفة مرتبة ، نظرًا لأن الدُفعات بينهما فارغة. من الواضح أن عنصرين فقط سيكونان متجاورين - الحد الأقصى من الدفعة الثالثة والحد الأدنى من الدفعة السادسة. وبالمثل ، سيكون المرشحون للزوج الذي لديه أقصى فرق هو الحد الأقصى لعنصر الدفعة الأولى والحد الأدنى للعنصر الثالث.
دعونا نكتب كل الأزواج الممكنة من العناصر التي يمكن أن تعطي الفرق الأكبر. دعنا نشير إلى min (i) - الحد الأدنى للعنصر في المجموعة i ، مثل max (i) - الحد الأقصى للعنصر.
الحد الأقصى (1) = -1 دقيقة (3) = 3
كحد أقصى (3) = 4 دقائق (6) = 10
كحد أقصى (6) = 10 دقائق (8) = 15
كحد أقصى (8) = 15 دقيقة (10) = 20
كحد أقصى (10) = 21 دقيقة (11) = 22
لقد حددنا الأزواج التي تستحق الدراسة. من الناحية العملية ، من الضروري إجراء مرور واحد عبر جميع الدُفعات ، والحفاظ على آخر دفعة غير فارغة والحد الأقصى للقيمة فيها. عندما نواجه الدفعة التالية غير الفارغة ، سنجد الحد الأدنى فيها ونحاول تحديث الإجابة.
سنكون سعداء - لقد حللنا المشكلة في الوقت المناسب...
في الواقع ، استخدمنا فكرة معروفة إلى حد ما ، وفي الواقع اتخذنا الخطوات الأولى لفرز الجيب ، في الأصل أطلقنا عليه اسم Bucket-Sort .
يتم ترتيب العناصر في سلال ، ثم يتم فرز العناصر الموجودة في كل سلة
في أسوأ الحالات ، فهي مناسبة، ولكن متوسط وقت التشغيل مع عدد كافٍ من الدُفعات وتوزيع منتظم للعناصر هو ...
"لكن انتظر ، ماذا عن القضية ومتى، لماذا لم تفكر في ذلك؟ "- سيسأل القارئ اليقظ. هذه الحالة متدهورة ، لذلك لم نفكر فيها ، لكن دعونا نفعل ذلك الآن للتأكد من اكتمالها.
إذا كان الفرق بين الحد الأدنى والحد الأقصى صفرًا ، فإن الحد الأقصى للفرق هو صفر أيضًا. في الواقع ، هذا كل شيء.