משפט מסטר

מנהל: TA_Isana

משפט מסטר

הודעהעל ידי Hagit » 15:12 20/03/2010

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

שאלה --- כיצד ניתן לאתר בנוסחאות אלמנטים שירמזו לנו לאיזה מקרה יש להתאימם.
כנל לגבי מקרים שאינם מתאימים למסטר ומתאימים לאיטרציה -- הראתם דוגמא 1 לכך היכן ניתן למצוא דוגמאות נוספות לכך? (או מה הם התנאים לפיהם נדע כי יש לעבור לאיטרציה )
הדוגמא עליה אני מדברת:
T(n) = 2T(n/2)+n*logn

תודה:))
Hagit
 
הודעות: 7
הצטרף: 18:36 21/12/2009

Re: משפט מסטר

הודעהעל ידי Ramzi » 00:53 21/03/2010

לא הבנתי את כל השאלות שלך, אבל את השאלה הזו אי אפשר לפתור עם המאסטר, צריך בדרך הארוכה.. וכן צריך לחשב מקרה מקרה כדי לדעת, אבל זה לא כזה קשה, כל מה שצריך לעשות זה לחשב את הlog(a) בבסיס b ואז זה כבר בדיקה די פשוטה (חוץ ממקרה 3). בכל מקרה את זה צריך לפתור על איטרציה ארוכה..

(אמרו לי שיש איזה דרך עם הצבה כדי לפתור את זה עם המאסטר, אבל לא ממש הבנתי אותה..)
Ramzi
 
הודעות: 23
הצטרף: 18:37 08/03/2010


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד

cron