علاقات التكرار
تعبر علاقات التكرار عن زمن تشغيل خوارزمية تكرارية بدلالة زمن تشغيلها على مدخلات أصغر؛ ويؤدي حلها إلى الحصول على الحدود التقاربية ذات الشكل المغلق المستخدمة لتحليل خوارزميات فرق تسد وغيرها من الخوارزميات التكرارية.
Definition
علاقة التكرار هي معادلة تُعرّف قيمة دالة عند مدخل ما بدلالة قيمها عند مدخلات أصغر؛ في تحليل الخوارزميات، تعبر عن تكلفة خوارزمية على مدخل بحجم n بدلالة تكلفتها على مشكلات فرعية أصغر.
Scope
يغطي هذا الموضوع صياغة وحل علاقات التكرار التي تنشأ في تحليل الخوارزميات: طريقة الاستبدال، طريقة شجرة التكرار، ونظرية ماستر لعلاقات التكرار من نوع فرق تسد بالصيغة T(n) = aT(n/b) + f(n). يشرح كيف تؤدي كل خوارزمية تكرارية إلى علاقة تكرار وكيفية ترجمة علاقة التكرار هذه إلى حد بيغ-ثيتا (big-Theta). يستثني هذا الموضوع الترميز التقاربي نفسه، والذي يُعالج بشكل منفصل، وطرق الدوال المولدة التوافقية من الرياضيات المتقطعة.
Core questions
- كيف تؤدي الخوارزمية التكرارية إلى علاقة تكرار لزمن تشغيلها؟
- كيف تُستخدم طريقة الاستبدال لإثبات والتحقق من حل مُفترض؟
- كيف تكشف طريقة شجرة التكرار عن إجمالي العمل عبر مستويات التكرار؟
- متى تنطبق نظرية ماستر، وماذا تعني حالاتها الثلاث؟
- كيف تُعالج علاقات التكرار التي تقع خارج صيغة نظرية ماستر؟
Key concepts
- علاقة التكرار
- طريقة الاستبدال
- طريقة شجرة التكرار
- نظرية ماستر
- علاقة تكرار فرق تسد
- الحالة الأساسية والحالة التكرارية
- الحل ذو الشكل المغلق
- طريقة أكرا-بازي
Key theories
- نظرية ماستر
- بالنسبة لعلاقات التكرار من نوع فرق تسد T(n) = aT(n/b) + f(n)، تقدم نظرية ماستر الحل التقاربي بمقارنة f(n) بـ n مرفوعة للقوة لوغاريتم الأساس b لـ a، وتغطي الحالات الثلاث التي تهيمن فيها الأوراق أو الجذر أو المستويات المتوازنة.
- طرق شجرة التكرار والاستبدال
- تقوم طريقة شجرة التكرار بجمع العمل المنجز في كل مستوى من مستويات التكرار لاقتراح حد، والذي تثبته طريقة الاستبدال بعد ذلك بدقة عن طريق الاستقراء؛ وتتعاملان مع علاقات التكرار التي تتجاوز نطاق نظرية ماستر.
Clinical relevance
يُعد حل علاقات التكرار المسار القياسي لتحديد زمن تشغيل الخوارزميات التكرارية، من خوارزميات الدمج السريع (mergesort) والفرز السريع (quicksort) إلى الضرب السريع والعديد من البرامج الديناميكية. يستخدم المهندسون والباحثون نظرية ماستر بشكل روتيني لاشتقاق وتبرير ادعاءات التعقيد التقاربي المرتبطة بهذه الخوارزميات.
History
تم تنظيم تحليل التكرار في الخوارزميات في كتاب كنوت (Knuth) "فن برمجة الحاسوب" (The Art of Computer Programming). أصبحت نظرية ماستر عنصرًا أساسيًا في الكتب المدرسية من خلال كتاب CLRS، وقامت طريقة أكرا-بازي (Akra-Bazzi) (1998) بتعميمها لتشمل فئة أوسع من علاقات التكرار من نوع فرق تسد مع تقسيمات غير متساوية.
Key figures
- Donald Knuth
- Mohamad Akra
- Louay Bazzi
Related topics
Seminal works
- cormen2009
- knuth1997vol1
Frequently asked questions
- متى يمكنني استخدام نظرية ماستر؟
- تنطبق نظرية ماستر على علاقات التكرار بالصيغة T(n) = aT(n/b) + f(n) حيث a >= 1 و b > 1، وحيث يقسم كل مستوى المشكلة إلى a مشكلة فرعية بحجم n/b. قد تتطلب علاقات التكرار ذات التقسيمات غير المتساوية، أو أحجام المشكلات الفرعية المتغيرة، أو تكاليف الدمج غير متعددة الحدود، استخدام طرق شجرة التكرار أو الاستبدال أو أكرا-بازي بدلاً من ذلك.
- لماذا تعطي علاقة تكرار الدمج السريع (mergesort) O(n log n)؟
- ينتج عن الدمج السريع T(n) = 2T(n/2) + O(n): مشكلتان فرعيتان بنصف الحجم بالإضافة إلى دمج خطي. هنا، يكون العمل لكل مستوى هو نفسه عبر جميع مستويات شجرة التكرار البالغ عددها log n، لذا فإن الإجمالي هو n مضروبًا في log n، وهو ما تؤكده نظرية ماستر على أنه ثيتا (n log n).