تحليل استهلاك الدين

في علم الحاسوب، فإن عملية تحليل استهلاك الدين هي طريقة لتحليل ودراسة تعقيد خوارزمية معينة كحساب تكلفة تنفيذ الخوارزمية بناءً على معايير مختلفة مثل الوقت الذي تحتاجه الخوارزمية لإنهاء التنفيذ أو المساحة التي تحتاجها لتخزين قيم العناصر والمتغيرات أثناء التنفيذ. الهدف من استخدام تحليل استهلاك الدين هو أن في كثير من الأحيان تكون التكلفة الناتجة من تحليل أسوأ الحالات مبالغاً فيها جدا، ونادرا ما يتم الحاجة إلى هذه التكلفة لتنفيد الخوارزمية. ولذلك فإن تحليل استهلاك الدين تقوم على حساب متوسط الوقت الذي تحتاجه الخوارزمية لإنهاء تنفيذ مجموعة من العمليات التي يتم تنفيذها بشكل متسلسل.^[1] يجب الأخذ بعين الاعتبار بأن عملية تحليل استهلاك الدين تختلف عن عملية إيجاد متوسط التعقيد التي تعتمد على فرضية الاحتمالات لهياكل البيانات والعمليات التي تستخدمها الخوارزمية. ولهذا السبب فإن عملية تحليل استهلاك الدين تعتبر طريقة مهمة ومكملة لطريقتي التحليل بأسوأ الحالات وتحليل متوسط التعقيد.^[2]

تكلفة كل عملية من مجموعة متسلسلة من العمليات تختلف بناءً على مجموعة من العوامل مثل نوع هيكلة البيانات المستخدمة لتنفيذ الخوارزمية بحيث بعضها يتحاج إلى تكلفة أعلى من غيرها وبعضها الأخر يحتاج إلى تكلفة أقل. لذلك فإن إيجاد التكلفة باستخدام طريقة تحليل استهلاك الدين قائمة على تحديد العمليات الأكثر والأقل تكلفة من مجموعة متسلسلة من العمليات، وهذا قد يتطلب مراعاة طبيعة البيانات المدخلة وحجمها وغيرها من العوامل التي تؤثر على أداء الخوارزمية.^[2]

تاريخ طريقة تحليل استهلاك الدين

عملية تحليل استهلاك الدين مستوحاة من طريقة تحليل التجميع والتي تعتبر الاَن نوع من أنواع التحليل باستهلاك الدين. روبرت تارجان هو أول من قام بعرضها من خلال مقالته العلمية بعنوان التعقيد الحسابي المطفأ التي تم نشرها بتاريخ 1985,^[1] والتي توضح فيها الحاجة لإيجاد طريقة أفضل من الطرق الاحتمالية الشائعة المستخدمة. في البداية كانت مستخدمة لبعض الخوارزميات مثل الأشجار الثنائية ووعمليات الإتحاد. ومن ثم أصبحت تستخدم في الكثير والعديد من الخوارزميات وأصبح لها دور مهم في تحليل تعقيد الخوارزميات.^[2]

ألية عمل طريقة تحليل استهلاك الدين

طريقة التحليل باستهلاك الدين تتطلب المعرفة بسلسلة العمليات التي يمكن حدوثها، وغالبا ما تعتمد على نوع هيكلة البيانات المستخدمة. فكرتها قائمة على أن العملية التي تستهلك أكثر تكلفة تحتاج لوقت أطول ليتم تكرارها، وبالتالي يتم تجاهل تكلفتها (إطفائها) إلى حين استخدامها مرة أخرى. يوجد ثلاث أنواع لعملية تحليل استهلاك الدين: طريقة التجميع، طريقة المحاسبة ,الطريقة المحتملة. يتم استخدام إحدى هذه الطرق بناء على الطريقة الأنسب لحالة الخوارزمية.^[3]

طريقة التحليل التجميع تحدد الحد الأعلى للتكلفة الكلية لمجموعة متسلسلة من العمليات ثم يتم قسمتها على عدد هذه العمليات ^[3]
طريقة المحاسبة هي شكل من أشكال طريقة التحليل بالتجميع بحيث يتم تعيين تكلفة جديدة تختلف عن التكلفة الفعلية بحيث تكون قيمتها كبيرة نسبياً للعمليات التي تحدث أولا وتتكرر كثيرا وتسمى هذه العمليات بالعمليات البسيطة، بينما يتم تعيين تكلفة قليلة نسبيا للعمليات التي تتكر بشكل أقل ولها تكلفة فعلية أكبر وتسمى بالعمليات الباهظة. أثناء تنفيذ العمليات البسيطة يتم حساب تكلفة الائتمان الناتجة من جمع ما تبقى من تكلفة الدفعة لكل عملية من هذه العمليات البسيطة ودفعها لاحقا للعمليات الباهظة. وبما أن تكلفة الائتمان تبدأ من الصفر، فإن التكلفة الفعلية لمجموعة من العمليات المتسلسلة تساوي ناتج طرح تكلفة الدفعة من تكلفة الكلية. وبما أن تكلفة الائتمان لا يجب أن تكون أقل من صفر، لذلك يجب أن تكون أكبر من التكلفة الفعلية. وفي معظم الأحيان، فإن العمليات التي لها أقل تكلفة فعلية تزيد من قيمة تكلفة الدفعة بشكل تدريجي وبنسب قليلة، بينما العمليات التي لها تكلفة فعلية أكبر وتتكرر بشكل أقل فهي تقلل من تكلفة الدفعة بنسبة كبيرة ^[3]
الطريقة المحتملة هي شكل من أشكال طريقة المحاسبة بحيث يتم حساب تكلفة الائتمان كطريقة محتملة لحالة بنية البيانات. وهي عبارة عن التكلفة الحالية بالإضافة إلى التغيير بالاحتماليات ^[3]

أمثلة

مصفوفة ديناميكية

عملية تحليل استهلاك الدين لعملية ادخال البيانات في المصفوفة الديناميكية

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

${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$ ^[3]

بحيث ان:

n: الحجم

$\Theta (1)$ : وقت ثابت

طابور البيانات

تكلفة إضافة عنصر جديد إلى طابور البيانات هي تكلفة ثابتة بسبب أنه لا تعتمد على حجم المدخلات أو المخرجات. بينما عملية حذف عنصر من طابور البيانات تعد عملية مكلفة في حال كانت فارغة من العناصر وذلك بسبب أنه يجب إضافة كل العناصر الموجودة في مصفوفة الإدخال إلى مصفوفة الإخراج. وبالتالي التكلفة تساوي حجم مصفوفة الإدخال. وبعد ذلك يتم حذف العناصر المراد حذفها من طابور البيانات بحيث كل عنصر يحتاج إلى تكلفة ثابته لحذفه. فتكلفة تنفيذ مجموعة متسلسلة من حذف العناصر يحتاج إلى تكلفة تساوي الحجم فالبتالي قيمة تحليل استهلاك الدين أو متوسط التكلفة هي قيمة ثابتة O(1).^[4] ويمكن إيجاد تكلفة الدفعة من خلال استخدام تكلفة الائتمان التي تكون قيمتها ضعف التكلة الفعلية لكل عملية نسخ عنصر من المصفوفة المدخلات إلى مصفوفة المخرجات. ومن ثم تقل هذه التكلفة عند البدء بحذف العناصر فالبتالي متوسط التكلفة هي تكلفة ثابتة.

تطبيقاتها

خوارزمية فورية

المراجع

^ ^ا ^ب Tarjan، Robert Endre (أبريل 1985). "Amortized Computational Complexity" (PDF). SIAM Journal on Algebraic and Discrete Methods. ج. 6 ع. 2: 306–318. DOI:10.1137/0606031. مؤرشف من الأصل (PDF) في 2022-10-30.
^ ^ا ^ب ^ج Rebecca Fiebrink (2007)، Amortized Analysis Explained (PDF)، مؤرشف من الأصل (PDF) في 2013-10-20، اطلع عليه بتاريخ 2011-05-03
^ ^ا ^ب ^ج ^د ^ه Kozen، Dexter (Spring 2011). "CS 3110 Lecture 20: Amortized Analysis". جامعة كورنيل. مؤرشف من الأصل في 2022-11-23. اطلع عليه بتاريخ 2015-03-14.
^ Grossman، Dan. "CSE332: Data Abstractions" (PDF). cs.washington.edu. مؤرشف من الأصل (PDF) في 2022-10-30. اطلع عليه بتاريخ 2015-03-14.

مراجعة الأدبيات

"Lecture 7: Amortized Analysis" (PDF). جامعة كارنيغي ميلون. مؤرشف من الأصل (PDF) في 2022-10-30. اطلع عليه بتاريخ 2015-03-14.
ألان بورودين and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. ص. 20, 141. مؤرشف من الأصل في 2022-10-30.

[tarjan-1] ا ^ب Tarjan، Robert Endre (أبريل 1985). "Amortized Computational Complexity" (PDF). SIAM Journal on Algebraic and Discrete Methods. ج. 6 ع. 2: 306–318. DOI:10.1137/0606031. مؤرشف من الأصل (PDF) في 2022-10-30.

[fiebrink-2] ا ^ب ^ج Rebecca Fiebrink (2007)، Amortized Analysis Explained (PDF)، مؤرشف من الأصل (PDF) في 2013-10-20، اطلع عليه بتاريخ 2011-05-03

[Lecture_20-3] ا ^ب ^ج ^د ^ه Kozen، Dexter (Spring 2011). "CS 3110 Lecture 20: Amortized Analysis". جامعة كورنيل. مؤرشف من الأصل في 2022-11-23. اطلع عليه بتاريخ 2015-03-14.

[Grossman4-4] Grossman، Dan. "CSE332: Data Abstractions" (PDF). cs.washington.edu. مؤرشف من الأصل (PDF) في 2022-10-30. اطلع عليه بتاريخ 2015-03-14.

[1]

[2]

[3]

[4]