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

يحدد التحليل الاستهلاكي متوسط التكلفة لكل عملية على مدى تسلسل من العمليات في أسوأ الحالات، مما يوضح أن العمليات الباهظة الثمن أحيانًا يمكن أن تكون رخيصة عندما يتم توزيع تكلفتها على العديد من العمليات الرخيصة.

Definition

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

Scope

يغطي هذا الموضوع التقنيات القياسية الثلاث للتحليل الاستهلاكي — طريقة التجميع، وطريقة المحاسبة (المصرفي)، وطريقة الإمكانات — وتطبيقها على هياكل البيانات التي تختلف فيها تكلفة العمليات الفردية، مثل المصفوفات الديناميكية، والعدادات الثنائية، وأشجار التمدد (splay trees)، وهيكل المجموعات المنفصلة (union-find). ويميز بين التكلفة الاستهلاكية ومتوسط التكلفة في الحالة العامة وتكلفة أسوأ حالة لكل عملية.

Core questions

• كيف تختلف التكلفة الاستهلاكية عن تكلفة أسوأ حالة لكل عملية ومتوسط التكلفة في الحالة العامة؟
• كيف تحد طريقة التجميع التكلفة الإجمالية لتسلسل العمليات؟
• كيف تخصص طريقة المحاسبة أرصدة لدفع تكاليف العمليات الباهظة الثمن لاحقًا؟
• كيف تستخدم طريقة الإمكانات دالة إمكانات لتسوية التكاليف؟
• ما هي هياكل البيانات التي تعتمد على الضمانات الاستهلاكية بدلاً من الحدود لكل عملية؟

Key concepts

• التكلفة الاستهلاكية
• طريقة التجميع
• طريقة المحاسبة (المصرفي)
• طريقة الإمكانات
• دالة الإمكانات
• مضاعفة المصفوفة الديناميكية
• زيادة العداد الثنائي
• الاتحاد والبحث مع ضغط المسار

Key theories

طريقة الإمكانات

تخصص طريقة الإمكانات إمكانات غير سالبة لحالة هيكل البيانات؛ التكلفة الاستهلاكية للعملية هي تكلفتها الفعلية بالإضافة إلى التغير في الإمكانات، لذا فإن العمليات الرخيصة تبني إمكانات تدفع تكاليف العمليات الباهظة الثمن لاحقًا.

طريقة المحاسبة (المصرفي)

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

Clinical relevance

يشرح التحليل الاستهلاكي سبب كفاءة العديد من الهياكل المستخدمة على نطاق واسع في الممارسة العملية على الرغم من العمليات المكلفة أحيانًا: فالمصفوفات الديناميكية (القوائم القابلة لتغيير الحجم)، وجداول التجزئة التي تعيد التجزئة، وعمليات الاتحاد والبحث (union-find) المستخدمة في خوارزميات الاتصال وشجرة الامتداد الدنيا، والهياكل ذاتية التعديل مثل أشجار التمدد (splay trees) كلها تعتمد على ضمانات استهلاكية بدلاً من ضمانات لكل عملية.

History

تم تقديم المصطلح والإطار المنهجي للتحليل الاستهلاكي بواسطة روبرت تارغان في عام 1985، بالاعتماد على حجج مخصصة سابقة. وكانت هذه التقنية محورية في تحليل هياكل البيانات ذاتية التعديل (أشجار التمدد، أكوام فيبوناتشي) التي طورها تارغان وسليتور في الثمانينيات.

Key figures

• Robert Tarjan
• Daniel Sleator

Seminal works

• tarjan1985amortized
• cormen2009

Frequently asked questions

هل التكلفة الاستهلاكية هي نفسها متوسط التكلفة في الحالة العامة؟

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

لماذا تكون إضافة عنصر إلى مصفوفة ديناميكية O(1) استهلاكيًا بينما تكون إعادة التحجيم O(n)؟

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