מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/חסמים עליונים ותחתונים למספר נוסחאות נסיגה/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

1[עריכה]

, עפ"י מקרה 1 של משפט המאסטר.

2[עריכה]

נפרוש את הנוסחה:






(את המעבר האחרון ראינו בטורים שימושיים.)

3[עריכה]

נגדיר . בלי הגבלת הכלליות, נניח ש. להלן עץ הפרישה המתקבל:

עץ הפרישה.

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

קל לראות שכל רמה מלאה בעץ תורמת .‏ הרמה הראשונה תורמת ;‏ הרמה השניה תורמת ,‏ הרמה השלישית תורמת ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש חסומה מלמטה ע"י , וחסומה מלמעלה ע"י . אבל היות ש וכן , אז .