|
|
עמוד:197
המטריצה Mat תכיל מטריצת מסלולים באורך k + 1 בדיוק . המטריצה P תכיל מטריצת מסלולים באורך k + 1 לכל היותר . להלן השגרה בשם , MasM המקבלת את המטריצה A והמחשבת ומחזירה את A- " לתוך המשתנה : / void maslul ( matrix A , matrix P ) { matrix temp , Mat ; Hazev ( A , temp ) ; /* temp <—A */ Hazev ( A , P ) ; rp ^—A */ for ( i = 1 ; i < = n-1 ; i ++ ) { kefel ( temp , A , Mat ) ; Chibur ( P , Mat , P ) ; Hazev ( Mat , temp ) ; } } מטריצת המסלולים מכונה בספרות גם סגור טרנזיטיבי . ניתוח היעילות של האלגוריתם למציאת מטריצת מסלולים אם בגרף n קדקודים , אזי במטריצת הסמיכות n * n = n איברים . פעולת hazev מבצעת השמה של מטריצה אחת בשנייה , וסיבוכיות זמן הריצה של השגרה הזאת היא : . 0 ( n ) פעולת kefel מכפילה שתי מטריצות , וסיבוכיות זמן הריצה של הפעולה הזאת היא ! . O (/ 7 ) פעולת chibur מחברת שתי מטריצות , ולכן סיבוביות זמן הריצה של הפעולה הזאת היא ? . . 0 ( n 2 ) הפעולה סדר הגודל של זמן הריצה temp < = A { Hazev ) ( מחוץ ללולאה ) 0 ( n ) P < = A { Hazev ) ( תתבצע פעם אחת בלבד ) O ( n 2 ) לולאת 0 ( n ) f ar 0 ( n ) kefel
|
|