האלגוריתם של פרים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט החלפות: לינארי; |
|||
שורה 6:
בעת מימוש האלגוריתם נעשה שימוש ב[[ערימה]] שמתוכה מוציאים בכל פעם את הצלע המינימלית. אם להשתמש ב[[ערימה בינארית]] סיבוכיות האלגוריתם תהיה <math>\ O(E \log V)</math> (כאשר <math>\ E</math> הוא מספר הקשתות ו-<math>\ V</math> הוא מספר הקודקודים). ניתן לשפרה מעט באמצעות שימוש ב[[ערימת פיבונאצ'י]] ולהגיע ל-<math>\ O(E + V \log V)</math>.
באופן כללי [[יעילות אלגוריתמית|היעילות]] של האלגוריתם של פרים טובה מזו של [[האלגוריתם של קרוסקל]]. למרות זאת, אם הקלט כבר ממויין לפי משקלי הקשתות או כאשר ניתן [[מיון (מדעי המחשב)|למיין]] אותם בזמן
| |||