طريقة محتملة

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 9 صور
الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعدّ طريقة الجهد طريقةً تُستخدم لتحليل التعقيد الزمني والمكاني المُستهلك لبنية بيانات ، وهو مقياس لأدائها على تسلسلات العمليات يُخفف من تكلفة العمليات غير المتكررة ولكنها مكلفة. [ 1 ] [ 2 ]

تعريف الوقت المستهلك

في طريقة الجهد، تُختار دالة Φ تربط حالات بنية البيانات بأعداد غير سالبة. إذا كانت S حالة من حالات بنية البيانات، فإن Φ( S ) تمثل العمل الذي تم احتسابه ("دفعه") في التحليل المُستهلك ولكنه لم يُنفذ بعد. بالتالي، يمكن اعتبار Φ( S ) بمثابة حساب مقدار طاقة الوضع المخزنة في تلك الحالة. [ 1 ] [ 2 ] تُعرَّف قيمة الجهد قبل عملية تهيئة بنية البيانات بأنها صفر. بدلاً من ذلك، يمكن اعتبار Φ( S ) بمثابة تمثيل لمقدار الفوضى في الحالة S أو بُعدها عن الحالة المثالية.

لنفترض أن o هي أي عملية فردية ضمن سلسلة من العمليات على بنية بيانات ما، حيث تشير S قبل إلى حالة بنية البيانات قبل العملية o، وتشير S بعد إلى حالتها بعد اكتمال العملية o . بمجرد اختيار Φ ، يُعرَّف الوقت المستهلك للعملية o على النحو التالي:

تيأمoرتأناzهـد(o)=تيأجتuأل(o)+ج⋅(Φ(Sأوتهـر)-Φ(Sبهـوoرهـ))،{\displaystyle T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} })),}

حيث C ثابت تناسب غير سالب (بوحدات الزمن) يجب أن يظل ثابتًا طوال فترة التحليل. أي أن الزمن المستهلك يُعرَّف بأنه الزمن الفعلي الذي تستغرقه العملية مضافًا إليه C مضروبًا في الفرق في الجهد الناتج عن العملية. [ 1 ] [ 2 ]

عند دراسة التعقيد الحسابي التقاربي باستخدام ترميز Big O ، فإن العوامل الثابتة غير ذات صلة، وبالتالي يتم حذف الثابت C عادة.

العلاقة بين الوقت المستهلك والوقت الفعلي

على الرغم من مظهرها المصطنع، فإن إجمالي الوقت المستهلك لتسلسل العمليات يوفر حدًا أعلى صالحًا للوقت الفعلي لنفس تسلسل العمليات.

لأي تسلسل من العملياتيا=o1،o2،...،oن{\displaystyle O=o_{1},o_{2},\dots ,o_{n}}، يُعرِّف:

  • إجمالي المدة المستهلكة:تيأمoرتأناzهـد(يا)=∑أنا=1نتيأمoرتأناzهـد(oأنا)،{\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}T_{\mathrm {amortized} }(o_{i}),}
  • إجمالي الوقت الفعلي:تيأجتuأل(يا)=∑أنا=1نتيأجتuأل(oأنا).{\displaystyle T_{\mathrm {actual} }(O)=\sum _{i=1}^{n}T_{\mathrm {actual} }(o_{i}).}

ثم:

تيأمoرتأناzهـد(يا)=∑أنا=1ن(تيأجتuأل(oأنا)+ج⋅(Φ(Sأنا)-Φ(Sأنا-1)))=تيأجتuأل(يا)+ج⋅(Φ(Sن)-Φ(S0))،{\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {actual} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),}

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

تيأجتuأل(يا)=تيأمoرتأناzهـد(يا)-ج⋅(Φ(Sن)-Φ(S0)).{\displaystyle T_{\mathrm {actual} }(O)=T_{\mathrm {amortized} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).}

منذΦ(S0)=0{\displaystyle \Phi (S_{0})=0}وΦ(Sن)≥0{\displaystyle \Phi (S_{n})\geq 0}،تيأجتuأل(يا)≤تيأمoرتأناzهـد(يا){\displaystyle T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)}لذلك يمكن استخدام الوقت المستهلك لتوفير حد أعلى دقيق للوقت الفعلي لتسلسل العمليات، على الرغم من أن الوقت المستهلك لعملية فردية قد يختلف اختلافًا كبيرًا عن وقتها الفعلي.

تحليل استهلاك المدخلات في أسوأ الحالات

عادةً ما يُستخدم تحليل الاستهلاك مع افتراض أسوأ حالة لتسلسل الإدخال. بناءً على هذا الافتراض، إذا كان X نوعًا من العمليات التي يمكن أن تُنفذها بنية البيانات، و n عددًا صحيحًا يُحدد حجم بنية البيانات المُعطاة (على سبيل المثال، عدد العناصر التي تحتويها)، فإن الوقت المُستهلك للعمليات من النوع X يُعرَّف بأنه الحد الأقصى، من بين جميع تسلسلات العمليات الممكنة على هياكل البيانات ذات الحجم n وجميع العمليات o i من النوع X ضمن التسلسل، للوقت المُستهلك للعملية o i .

وبناءً على هذا التعريف، يمكن تقدير الوقت اللازم لتنفيذ سلسلة من العمليات عن طريق ضرب الوقت المستهلك لكل نوع من أنواع العمليات في التسلسل بعدد العمليات من ذلك النوع.

أمثلة

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

المصفوفة الديناميكية هي بنية بيانات تُستخدم لإدارة مجموعة من العناصر، وتتيح الوصول العشوائي إلى مواقعها داخل المصفوفة، بالإضافة إلى إمكانية زيادة حجمها بمقدار عنصر واحد. وهي متوفرة في لغة جافا بنوع "ArrayList"، وفي لغة بايثون بنوع "list".

يمكن تمثيل المصفوفة الديناميكية ببنية بيانات تتكون من مصفوفة A من العناصر، بطول N ، بالإضافة إلى عدد n  ≤ N يمثل المواضع المستخدمة داخل المصفوفة حتى الآن. باستخدام هذه البنية، يمكن الوصول العشوائي إلى المصفوفة الديناميكية بالوصول إلى نفس الخلية في المصفوفة الداخلية A ، وعندما يكون n < N ، يمكن زيادة حجم المصفوفة الديناميكية ببساطة عن طريق زيادة n . أما عندما يكون n = N ، فمن الضروري تغيير حجم A ، وتتمثل إحدى الاستراتيجيات الشائعة في مضاعفة حجمها، باستبدال A بمصفوفة جديدة بطول 2n . [ 3 ]       

يمكن تحليل هذا الهيكل باستخدام دالة الجهد:

Φ  =  2 n − N  

بما أن استراتيجية تغيير الحجم تتسبب دائمًا في أن يكون A ممتلئًا بنسبة النصف على الأقل، فإن دالة الجهد هذه تكون دائمًا غير سالبة، كما هو مطلوب.

عندما لا تؤدي عملية زيادة الحجم إلى عملية تغيير الحجم، تزداد قيمة Φ بمقدار 2، وهو ثابت. لذلك، فإن ثبات الوقت الفعلي للعملية والزيادة الثابتة في الإمكانات يجتمعان لإعطاء وقت استهلاك ثابت لهذا النوع من العمليات.

مع ذلك، عندما تؤدي عملية زيادة الحجم إلى تغيير الحجم، تنخفض القيمة المحتملة لـ Φ إلى الصفر بعد تغيير الحجم. يستغرق تخصيص مصفوفة داخلية جديدة A ونسخ جميع القيم من المصفوفة الداخلية القديمة إلى الجديدة وقتًا فعليًا قدره O( n )، ولكن (مع اختيار مناسب لثابت التناسب C ) يتم تعويض ذلك تمامًا بانخفاض الدالة المحتملة، مما يترك مرة أخرى وقتًا إجماليًا ثابتًا للعملية.

أما العمليات الأخرى لبنية البيانات (قراءة وكتابة خلايا المصفوفة دون تغيير حجم المصفوفة) فلا تتسبب في تغيير دالة الجهد ولها نفس الوقت الثابت المستهلك مثل وقتها الفعلي. [ 2 ]

لذلك، باختيار استراتيجية تغيير الحجم ودالة الجهد هذه، تُظهر طريقة الجهد أن جميع عمليات المصفوفة الديناميكية تستغرق وقتًا مستهلكًا ثابتًا. وبدمج ذلك مع المتباينة التي تربط بين الوقت المستهلك والوقت الفعلي على تسلسلات العمليات، يتضح أن أي تسلسل من n عملية مصفوفة ديناميكية يستغرق O( n ) من الوقت الفعلي في أسوأ الحالات، على الرغم من أن بعض العمليات الفردية قد تستغرق بدورها وقتًا خطيًا. [ 2 ]

عندما تتضمن المصفوفة الديناميكية عمليات تُقلل حجمها بالإضافة إلى زيادته، يجب تعديل دالة الجهد لمنعها من أن تصبح سالبة. إحدى طرق القيام بذلك هي استبدال الصيغة المذكورة أعلاه لـ Φ بقيمتها المطلقة .

مجموعة متعددة الفتحات

لنفترض وجود مكدس يدعم العمليات التالية:

  • التهيئة - إنشاء مكدس فارغ.
  • الدفع - إضافة عنصر واحد أعلى المكدس، مما يؤدي إلى زيادة حجم المكدس بمقدار 1.
  • Pop( k ) - إزالة k عنصرًا من أعلى المكدس، حيث لا يتجاوز k حجم المكدس الحالي

يتطلب Pop( k ) وقتًا قدره O( k )، لكننا نرغب في إظهار أن جميع العمليات تستغرق وقتًا مستهلكًا قدره O(1).

يمكن تحليل هذا الهيكل باستخدام دالة الجهد:

Φ  =  عدد العناصر في المكدس

هذا الرقم يكون دائمًا غير سالب، كما هو مطلوب.

تستغرق عملية الدفع وقتًا ثابتًا وتزيد قيمة Φ بمقدار 1، لذا فإن وقتها المستهلك ثابت.

تستغرق عملية سحب البيانات وقتًا قدره O( k ) ولكنها تقلل أيضًا من Φ بمقدار k ، لذا فإن وقتها المستهلك ثابت أيضًا.

يثبت هذا أن أي تسلسل من m عملية يستغرق O( m ) من الوقت الفعلي في أسوأ الحالات.

عداد ثنائي

لنفترض وجود عداد ممثل برقم ثنائي ويدعم العمليات التالية:

  • التهيئة: إنشاء عداد بقيمة 0.
  • زيادة: أضف 1 إلى العداد.
  • اقرأ: أعد قيمة العداد الحالية.

في هذا المثال، لا نستخدم نموذج الآلة ثنائية التفرع ، بل نطلب وحدة زمنية واحدة لكل عملية بت في الزيادة. نريد أن نبين أن عملية الزيادة تستغرق زمنًا ثابتًا O(1).

يمكن تحليل هذا الهيكل باستخدام دالة الجهد:

Φ  =  عدد البتات التي تساوي 1 = وزن هامينغ (العداد)

هذا الرقم دائماً غير سالب ويبدأ من 0، كما هو مطلوب.

تقوم عملية الزيادة (Inc) بقلب البت الأقل أهمية . فإذا انقلب هذا البت من 1 إلى 0، يُقلب البت التالي أيضًا. ويستمر هذا حتى يُقلب بت من 0 إلى 1، وعندها تتوقف عملية القلب. إذا كان العداد ينتهي مبدئيًا بـ k بتًا قيمتها 1، فإننا نقلب إجمالًا k + 1 بتًا، ويستغرق ذلك وقتًا فعليًا قدره k + 1، مع تقليل الوقت الفعلي بمقدار k - 1، وبالتالي يكون الوقت المُستهلك هو 2. ومن ثم، فإن الوقت الفعلي لتنفيذ m عملية زيادة هو O( m ).

التطبيقات

تُستخدم طريقة دالة الجهد عادةً لتحليل أكوام فيبوناتشي ، وهي نوع من طوابير الأولوية حيث يستغرق حذف عنصر ما وقتًا مُستهلكًا لوغاريتميًا، بينما تستغرق جميع العمليات الأخرى وقتًا مُستهلكًا ثابتًا. [ 4 ] كما يمكن استخدامها لتحليل أشجار التفرع ، وهي شكل ذاتي التعديل من أشجار البحث الثنائية ذات وقت مُستهلك لوغاريتمي لكل عملية. [ 5 ]

مراجع

  1. 1 2 3 جودريتش، مايكل تي .؛ تاماسيا، روبرتو (2002)، "1.5.1 تقنيات الاستهلاك"، تصميم الخوارزميات: الأسس والتحليل وأمثلة الإنترنت ، وايلي، ص 36-38 .
  2. 1 2 3 4 5 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "17.3 طريقة الجهد". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 412-416 . ISBN   0-262-03293-7.
  3. ↑ جودريتش وتاماسيا، 1.5.2 تحليل تنفيذ المصفوفة القابلة للتمديد، ص 139-141؛ كورمن وآخرون، 17.4 الجداول الديناميكية، ص 416-424.
  4. ↑ كورمن وآخرون، الفصل 20، "أكوام فيبوناتشي"، الصفحات 476-497.
  5. ↑ جودريتش وتاماسيا، القسم 3.4، "الأشجار المتفرعة"، الصفحات 185-194.