נוסחאות נסיגה וחסם הדוק.

[pain_killer12]

שלום חברים, קיבלתי בתרגיל בית שאלה די מסובכת

שצריך לפתור את נוסחת הנסיגה (להעביר לנוסחה רגילה שתלויה בn)

ואז למצוא לנוסחה הזאת חסם הדוק.

הנוסחה היא:

T(n) = T(0.13n) + T(0.87n) + 3n

הבעיה היא שאותנו לימדו גם בהרצאה וגם בתרגיל לפתור שאלות בסגנון Tn = T(n/x) + Fn

בלי משפט האב או משהו. פשוט אמרו לנו להמשיך לפתוח את הT הפנימי ואז "לנחש" פתרון

עם i ואז להוכיח באינד' שזה נכון ובסוף לפתור עם תנאי ההתחלה. לא משנה.

העניין הוא שלא הראו לנו דבר כזה וכמעט אף אחד לא הצליח.

תודה רבה מראש לעוזרים.

[miaoo673]

אם משרטטים את יחס הנסיגה כעץ בינארי, מקבלים משהו שנראה ככה:

טענת עזר: בהינתן צומת כלשהו בעץ עם ערך K ושני ילדים, אזי סכום הערכים של הילדים שווה לK (נובע ישירות מיחס הנסיגה).

טענה: סכום הצמתים בכל רמה הוא (O(n

הוכחה באינדוקציה:

הטענה נכונה עבור השורש. נניח נכונות עבור הרמה הi.

לכל צומת ברמה הi יש לכל היותר שני ילדים, ולכן סכום הצמתים ברמה הi+1 שווה לכל היותר לסכום הצמתים ברמה הi.

טענה: עומק העץ הוא (O(logn

הוכחה:

העלה העמוק ביותר הוא העלה הימני ביותר. נסמן את עומקו ב-h

3n*(0.87)^h = 1

עבור n גדול מאוד h = logn

משתי הטענות נובע שסכום הצמתים בכלל העץ הוא (O(nlogn, וזה (T(n

עריכה: לגבי חסם תחתון נחכה לתשובה מעוד מישהו.