|
|
صفحة: 342
בייצוג של קבוצות זרות על-ידי רשימות מקושרות סיבוביות זמן הריצה של הפעולות הבסיסיות המוגדרות על מבנה הנתונים יער היא כדלקמן ו עביר הפעולה טיבוכיות זמן הריצה במקרה הגרוע ביותר 0 ( 1 ) MAKE _ SET ( v ) 0 ( 1 ) FIND ( v ) 0 ( n log n ) SORT ( n ) O ( n 2 ) UNlON ( x , y ) בדוק ! לאור האמור לעיל , נוכל עתה לחקור את סיבוביות זמן הריצה של האלגוריתם של קרוסקל . לכן , סיבוביות זמן הריצה של האלגוריתם קרוסקל היא \ E \) . 0 {\ V \ 2 ניתן לייצג קבוצות זרות באמצעות מבנה נתונים מיוחד הנקרא "עצים . "מושרשים לא נדון כאן בנושא עצים מושרשים , כיוון שהנושא חורג מדרישות הקורס . נציין רק את העובדה , שבאמצעות מבנה נתונים זה ניתן לבצע את צעד 4 של האלגוריתם של קרוסקל בזמן , CK ^ I log \ E \) ולכן סיבוביות זמן הריצה של האלגוריתם היא . O (\ E \ log \ E \) [
|
|