משפט המאסטר\שיטת האיטרציות

[דני מיכאלי]

משפט המאסטר\שיטת האיטרציות

שלום רב, אני מתקשה בפתרון 2 שאלות באלגוריתמים (נוסחאות נסיגה) אני מעלה את קובץ השאלות ואת דרך הפתרון שלי, אודה לכם באם תאירו את עיניי לשגיאות ולכוון אותי לפתרון. (הערה, איני מבקש פתרון לשאלה, אלא רק כיוון לפתרון).

 

[אמיתי ר]

לגבי השאלה השניה

(כי לא ממש הבנתי מה עשית בכלל בשאלה הראשונה). אין צורך בכל החישובים הללו. פשוט שיטת האב. שים לב: B=2, A=8 כלומר LOG בבסיס 2 של 8 --> 3. לכן אתה משווה N בחזקת 3, מול ערך הפונקציה (שהיה משהו N בריבוע כפול משהו), כלומר בוודאי N בחזקת 3 יותר גדול בסדר גודל (למקפידים, תראה שעבור אפסילון קבוע כלשהו קטן זה מתקיים). וע"פ משפט האב, זה אומר שהחסם האסימפטוטי ההדוק (תטא) הוא N בחזקת 3. כמובן שמה שכתבתי לעיל הוא "כיוון"/דרך, וצריך לנסח את הדברים באופן פורמלי (שידרוש לא יותר מ-3 שורות, ובטח לא חצי עמוד כמו שרשמת). בהצלחה

 

[אולף]

לדעתי

בשאלה ראשונה:כל מה שנשאר לך לעשות לאחר כל הפיתוח בהתחלה הוא לומר:האיטרציה תסתיים כאשר

i=log n (because then 2^i = n => T(n/2^i) = O(1) )​

הדרך עצמה נכונה וגם התשובה. רק לא ברור המעבר בין שני הפיתוחים עם ה"נניח שקיים K ..." - לא צריך להניח שקיים K כזה, צריך להשתמש בו. בשאלה שנייה:

T = 8T(n/2) + 3(n^2)logn logb(a) = log2(8) = 3 f =? O(n^(3-epsilon)) - yes f =? Theta(n^3) - no f =? Omega(n^(3+epsilon)) - no So we are with the first case. hence T = Theta(n^3) according to the master theorem. Can be found in http://www.cs.virginia.edu/~luebke/cs332.fall00/lecture3/sld038.htm​