التنشيط الديناميكي

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

نُعرّف المشكلة${\displaystyle P}$البحث عن المسند${\displaystyle M}$مباراة في المجموعة${\displaystyle S}$مثل${\displaystyle P(M,S)}$. مشكلة${\displaystyle P}$تكون قابلة للتحليل إذا كانت المجموعة${\displaystyle S}$يمكن تقسيمها إلى مجموعات فرعية${\displaystyle S_{i}}$وهناك عملية${\displaystyle +}$من توحيد النتائج بحيث${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}$.

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

في حالة استخدام النظام الثنائي، مجموعة من${\displaystyle n}$يتم تقسيم العناصر إلى مجموعات فرعية من الأحجام مع

${\displaystyle 2^{i}*n_{i}}$

العناصر حيث${\displaystyle n_{i}}$هو ${\displaystyle i}$الجزء رقم -th من${\displaystyle n}$بالنظام الثنائي. هذا يعني أنه إذا${\displaystyle n}$لديه${\displaystyle i}$إذا كانت البتة رقم n تساوي صفرًا، فإن المجموعة المقابلة لا تحتوي على أي عناصر. تتمتع كل مجموعة فرعية بنفس خصائص بنية البيانات الثابتة الأصلية. قد تتضمن العمليات التي تُجرى على بنية البيانات الديناميكية الجديدة اجتيازًا.${\displaystyle \log _{2}\left(n\right)}$المجموعات التي تتشكل عن طريق التفكيك. ونتيجة لذلك، سيضيف هذا${\displaystyle O(\log \left(n\right))}$ على عكس عمليات بنية البيانات الثابتة، سيسمح هذا بإضافة عمليات الإدراج/الحذف.

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

لو

• ${\displaystyle P_{S}\left(n\right)}$حان الوقت لبناء بنية البيانات الثابتة
• ${\displaystyle Q_{S}\left(n\right)}$حان الوقت للاستعلام عن بنية البيانات الثابتة
• ${\displaystyle Q_{D}\left(n\right)}$حان الوقت للاستعلام عن بنية البيانات الديناميكية التي تشكلت عن طريق التفكيك
• ${\displaystyle {\overline {I}}}$هو وقت الإدخال المستهلك

ثم

• ${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\cdot \log \left(n\right)\right)}$
• ${\displaystyle {\overline {I}}=O\left(\left(P_{S}\left(n\right)/n\right)\cdot \log \left(n\right)\right).}$

لو${\displaystyle Q_{S}\left(n\right)}$إذا كانت على الأقل متعددة الحدود ، فإن${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)}$.

• كورت ميلهورن، هياكل البيانات والخوارزميات 3، سلسلة EATCS، المجلد 3، سبرينغر، 1984.