كتاب "الخوارزمية المثالية. الأساسيات

مرحبا ، habrozhiteli! يعتمد هذا الكتاب على الدورات الخوارزمية عبر الإنترنت التي يقودها تيم رافجاردن في كورسيرا وستانفورد لاجونيتا ، وقد جاءت هذه الدورات الدراسية بفضل المحاضرات التي ألقاها للطلاب في جامعة ستانفورد لسنوات عديدة.

الخوارزميات هي قلب وروح علوم الكمبيوتر. لا يمكنك الاستغناء عنها ، فهي موجودة في كل مكان - بدءًا من توجيه الشبكة وحسابات الجينوم إلى التشفير والتعلم الآلي. ستحولك "الخوارزمية المثالية" إلى محترف حقيقي سيحدد المهام ويحلها ببراعة في الحياة وفي مقابلة عند التعاقد مع أي شركة لتكنولوجيا المعلومات. سيتحدث تيم رافغاردن عن التحليل المقارب ، وتدوين كبير-أو ، خوارزميات الفجوة والقهر ، والعشوائية ، والفرز والاختيار. الكتاب موجه إلى أولئك الذين لديهم بالفعل خبرة في البرمجة. سوف تنتقل إلى مستوى جديد لرؤية الصورة الكبيرة ، لفهم المفاهيم المنخفضة المستوى والفروق الدقيقة الرياضية.

* 6.3. DSelect خوارزمية

يتم تنفيذ خوارزمية RSelect في الوقت الخطي لكل إدخال ، حيث يرتبط التوقع الرياضي باختيارات عشوائية تؤديها الخوارزمية. هل العشوائية مطلوبة للاختيار الخطي؟ في هذا القسم وما بعده ، يتم حل هذه المشكلة باستخدام خوارزمية خطية حتمية لمشكلة الاختيار.

بالنسبة لمهمة الفرز ، يكون متوسط ​​وقت تشغيل خوارزمية QuickSort العشوائية O (n log n) هو نفس خوارزمية MergeSort القطعية ، وكلتا الخوارزميات QuickSort و MergeSort خوارزميات مفيدة للاستخدام العملي. من ناحية أخرى ، على الرغم من أن خوارزمية التحديد الخطي الحتمية الموصوفة في هذا القسم تعمل بشكل جيد في الممارسة ، فإنها لا تنافس خوارزمية RSelect. يحدث هذا لسببين: بسبب العوامل الثابتة الكبيرة في وقت خوارزمية DSelect والعمل الذي تقوم به الخوارزمية المرتبطة بتخصيص وإدارة ذاكرة الوصول العشوائي الإضافية. ومع ذلك ، فإن الأفكار الموجودة في الخوارزمية رائعة لدرجة أنني لا أستطيع أن أخبرك بها.

6.3.1. فكرة رائعة: الوسيط

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

الفكرة المبدعة في اختيار خطي حاسم هي استخدام "وسيط الوسطاء" كبديل عن الوسيط الحقيقي. تعتبر الخوارزمية عناصر مجموعة المدخلات كفرق رياضية وتحمل بطولة خروج المغلوب في جولتين ، بطلها هو العنصر الداعم ؛ انظر أيضا التين. 6.1.


الجولة الأولى هي مرحلة جماعية مع عناصر في المواضع من 1 إلى 5 من مجموعة الإدخال كمجموعة أولى ، وعناصر في المواضع من 6 إلى 10 كمجموعة ثانية ، وهكذا. يتم تعريف الفائز بالجولة الأولى من مجموعة مكونة من خمسة عناصر على أنها الوسيط للعنصر (أي الأصغر الثالث). لأن هناك مجموعات من خمسة عناصر ، هناك الفائزين الأول. (كالعادة ، نتجاهل الكسور بسبب البساطة.) يتم تعريف بطل البطولة بأنه الوسيط للفائزين في الجولة الأولى.

6.3.2. الكود الكاذب ل DSelect خوارزمية

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


تتطابق الأسطر 1-2 و 6-13 مع خوارزمية RSelect. الخطوط 3-5 هي الجزء الجديد الوحيد من الخوارزمية ؛ يقومون بحساب متوسط ​​وسيط صفيف الإدخال ، مع استبدال الخط في خوارزمية RSelect ، التي تحدد العنصر المرجعي عشوائيًا.

يحسب الخطان 3 و 4 الفائزين في الجولة الأولى من دورة الإقصاء ، حيث يتم احتساب العنصر الأوسط لكل مجموعة مكونة من خمسة عناصر باستخدام طريقة القوة الغاشمة أو خوارزمية الفرز ، ونسخ هؤلاء الفائزين إلى الصفيف الجديد C. الخط 5 يحسب بطل الدورة عن طريق حساب وسيط الصفيف C ؛ لأن C لها طول (مبدئيًا) إحصائيات ترتيبية من الصفيف C. لا يتم استخدام العشوائية في أي خطوة من الخوارزمية.

6.3.3. فهم خوارزمية DSelect

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


الجواب الصحيح هو: (ج). تجاهل الحالة الأساسية والحالة السعيدة التي يكون فيها العنصر المرجعي هو إحصائيات الطلب المطلوبة ، تقوم خوارزمية DSelect بإجراء مكالمتين متكررتين. لفهم السبب ، لا تبالغ به ؛ مجرد التحقق من DSelect خوارزمية رمز خوارزمية سطرا سطرا. يحتوي الخط 5 على مكالمة متكررة واحدة ومكالمة أخرى على الخط 11 أو 13.

هناك نوعان من الأسئلة الشائعة المربكة حول هاتين النداءات المتكررة. أولاً ، أليست حقيقة أن خوارزمية RSelect تقوم بإجراء مكالمة متكررة واحدة فقط ، والسبب في أنها تعمل بشكل أسرع من خوارزميات الفرز لدينا؟ ألا يتخلى DSelect عن هذا التحسين بإجراء مكالمتين متكررتين؟ يوضح القسم 6.4 أنه نظرًا لأن الاستدعاء التكراري الإضافي على السطر 5 يجب أن يحل فقط مهمة فرعية صغيرة نسبيًا (مع 20٪ من العناصر في الصفيف الأصلي) ، لا يزال بإمكاننا حفظ التحليل الخطي.

ثانياً ، تلعب نداءتان متكررتان أدوارًا مختلفة تمامًا. الغرض من المكالمة العودية على السطر 5 هو تحديد عنصر مرجع جيد للمكالمة العودية الحالية. الهدف من المكالمة العودية على السطر 11 أو 13 هو الهدف المعتاد - حل متكرر للمهمة الأصغر المتبقية التي خلفتها المكالمة العودية الحالية. ومع ذلك ، فإن البنية العودية في خوارزمية DSelect تتبع تمامًا تقليد جميع خوارزميات الفجوة والقهر الأخرى التي درسناها: كل مكالمة عودية تقدم عددًا صغيرًا من المكالمات العودية اللاحقة ذات المهام الفرعية الدقيقة بدقة وتقوم ببعض الأعمال الإضافية. إذا لم نكن قلقين من أن الخوارزميات مثل MergeSort أو QuickSort ستعمل إلى الأبد ، فعندئذ لا ينبغي لنا القلق بشأن خوارزمية DSelect.

6.3.4. DSelect خوارزمية وقت التشغيل

ليست خوارزمية DSelect مجرد برنامج مفصل بوضوح يكمل في فترة زمنية محدودة - إنه يعمل في وقت خطي ، ويقوم بعمل أكثر فقط على عامل ثابت أكثر مما هو ضروري لقراءة بيانات الإدخال.

النظرية 6.6 (وقت تشغيل خوارزمية DSelect). لكل صفيف إدخال طوله length 1 ، يكون وقت تشغيل خوارزمية DSelect هو O (n).

على عكس وقت تشغيل خوارزمية RSelect ، والتي لا يمكن أن تكون من حيث المبدأ أكثر من Θ (n2) ، فإن وقت تشغيل خوارزمية DSelect يساوي دائمًا O (n). ومع ذلك ، في الممارسة العملية ، يجب أن تفضل RSelect على خوارزمية DSelect ، لأن الأولى تعمل في نفس المكان ، والثابت المخفي في متوسط ​​وقت التشغيل "O (n)" في Theorem 6.1 أصغر من الثابت المخفي في Theorem 6.6.

»يمكن الاطلاع على مزيد من المعلومات حول الكتاب على موقع الناشر
» المحتويات
» مقتطفات

ل Khabrozhiteley خصم 20 ٪ على القسيمة - الخوارزميات

عند دفع النسخة الورقية من الكتاب ، يتم إرسال نسخة إلكترونية من الكتاب عن طريق البريد الإلكتروني.

ملاحظة: 7٪ من تكلفة الكتاب ستذهب إلى ترجمة كتب الكمبيوتر الجديدة ، قائمة الكتب التي سلمت إلى المطبعة هنا .