تدوين كبير من الخوارزمية تتكون من خوارزميات أصغر

Question

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

الخوارزميات المستخدمة لها متطلبات التشغيل / المساحة:

giveacodicetagpre.

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

o (v + ev + ev log v) من شأنه أن يبسط إلى o (eV سجل v)

سيتم احتساب متطلبات الفضاء بطريقة مماثلة.أنا أفكر في هذا بشكل صحيح؟شكرا!

Answer 1

بالضبط، "قاعدة الإبهام" هي أنه، في سلسلة من كتل التعليمات البرمجية، يهيمن على التعقيد الشامل من قبل الكتلة بأكبر التعقيد (غير مشروط)

matematically، عندما يميل V إلى أعداد كبيرة جدا، فإنه أصغر من EV، وهو أصغر من EVLOGV.لذلك، بالنسبة ل V كبيرة، يتم تقريب تعقيد خوارزمية الخاص بك جيدا بواسطة EVLOGV