Time and Space Complexity
الدرس 7 من 9 في دورة خوارزمية كروسكال - خوارزميات الرسوم البيانية على Coddy.
تعقيد الوقت:
- فرز الحواف E هو O(E log E)؛ كل عملية union-find هي تقريبًا O(1) مع path compression، لذا فإن خوارزمية Kruskal الكلاسيكية هي O(E log E). نسخة اختيار الحد الأدنى التي نبنيها هنا هي O(E2)، وهو أمر جيد للرسوم البيانية الصغيرة.
تعقيد المساحة:
- O(V) لمصفوفة parent (بالإضافة إلى حواف الإدخال).
ملخص:
- تقوم خوارزمية Kruskal بتنمية MST عن طريق إضافة أرخص حافة خالية من الدورات في كل خطوة، باستخدام union-find لاختبار الدورات.
- تشترك جميع أشجار MST في نفس الوزن الإجمالي، لذا فإن الإجابة فريدة.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس خوارزمية كروسكال - خوارزميات الرسوم البيانية
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity