9. אלגוריתמים דינאמיים

מבנה נתונים ואלגוריתמים

 

 

9.1 מספרי פיבונאצ'י

לפעמים, גישת הפרד ומשול נראית מתאימה, אך נכשלת ביצירת אלגוריתם יעיל.

אנו מכירים את האלגוריתם לחישוב מספרי פיבונאצ'י:

 

        int fib( int n ) {

        if ( n < 2 ) return n;

        else

        return fib(n-1) + fib(n-2);

        }

 

באלגוריתם זה משתמשים פעמים רבות כדוגמא לאלגנטיות של רקורסיה כטכניקת תכנות. בכל אופן, כאשר בוחנים את זמן הסיבוכיות, מוצאים שהוא רחוק מלהיות אלגנטי...

 

ניתוח

אם t_n הוא הזמן הנדרש לחשב f_n, כאשר f_n  הוא המספר הפיבונאצ'י ה- n-י', אזי על ידי בחינת הפונקציה שלעיל ברור ש:

t_n = t_n-1 + t_n-2

 

וכמו כן:

t₁ = t₂ = c,

 

כאשר c, הוא קבוע. לכן:

t_n = cf_n

 

כעת:

 

ומכאן:

t_n = O(f_n) = O(1.618..ⁿ)

 

כך שפונקציה פשוטה זו דורשת זמן מעריכי! כפי שנראה בפירוט בהמשך, יש להימנע מלהשתמש

באלגוריתמים בעלי זמן מעריכי.

 

פתרון איטראטיבי

            זוהי אלטרנטיבה פשוטה הרצה בזמן של O(n):

 

int fib( int n ) {

        int k, f1, f2;

        if ( n < 2 ) return n;

        else {

           f1 = f2 = 1;

           for(k=2;k<n;k++) {

                f = f1 + f2;

                f2 = f1;

                f1 = f;

                }

        return f;

        }

 

 

אלגוריתם זה פותר תחילה את הבעיה של חישוב f₀ ו-  f₁, מחשב את f₂ מערכים אלו, אז הוא מחשב את f₃ מ-  f₂ ו-  f₁ וכך הלאה. כך, במקום חלוקת הבעיה הגדולה לתתי-בעיות קטנות יותר ופתרון תתי-בעיות אלו, האלגוריתם מתחיל עם הבעיות הקטנות ביותר, פותר אותן ושומר את התוצאות. תוצאות אלו משמשות לפתרון בעיות גדולות יותר, אשר פתרונן שוב מסייע לפתרון בעיות גדולות עוד יותר.

 

ארוחות חינם?

כפי שידוע אין דבר כזה ארוחות חינם! בעיות דינאמיות משיגות את יעילותן על ידי פתרון ואחסון התשובות לבעיות קטנות. לכן הן בדרך כלל מחליפות שטח זיכרון תמורת הגדלת המהירות. במקרה של פיבונאצ'י שטח הזיכרון הנוסף הוא זניח - שני המשתנים f₁ ו-  f₂, אך באלגוריתמים דינאמיים מורכבים יותר, כפי שנראה בהמשך, השטח הנוסף הוא משמעותי.

 

 

מושגים

 

אלגוריתם דינאמי

מחלקה כללית של אלגוריתמים הפותרים בעיות על ידי פתרון גרסאות קטנות יותר של הבעיה,     שמירת פתרונות אלה וצירופם יחד על מנת לפתור את הבעיה הגדולה.

 

 

המשך ל: מקדמים בינומיים                          חזור ל: תוכן עניינים