Time and Space Complexity
الدرس 7 من 9 في دورة خوارزمية Prim - خوارزميات المخططات على Coddy.
تعقيد الوقت:
- إصدار فحص الحواف هنا هو O(V * E): V-1 جولة، كل منها يفحص جميع الحواف E. باستخدام كومة ثنائية (binary heap) وقوائم التجاور (adjacency lists)، تعمل خوارزمية Prim في O((V + E) log V).
تعقيد المساحة:
- O(V) لمصفوفة
inTree(بالإضافة إلى حواف الإدخال).
ملخص:
- تقوم خوارزمية Prim بتنمية شجرة واحدة، مع إضافة أرخص حافة تخرج منها دائمًا، حتى يتم تضمين كل رأس.
- تنتج نفس الوزن الإجمالي الأدنى مثل خوارزمية Kruskal، باستخدام استراتيجية مختلفة.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس خوارزمية Prim - خوارزميات المخططات
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity