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

בחיפוש בינרי ראינו פונקציה (במובן פונקציית תוכנה) שזמן הריצה שלה היה נתון על ידי הנוסחה $T(n)=T(\lfloor (n-1)/2\rfloor )+\mathrm{\Theta }(1)$. דף זה עוסק בפתרון סדרי גדילה לנוסחאות נסיגה - נוסחאות בהן פונקציה (מתמטית) מוגדרת בעזרת מופעים קטנים יותר שלה. אנו נתמקד בנוסחאות נסיגה של פונקציות המתארות את זמני הריצה של אלגוריתמים או חלקיהם.

בעיות טכניות

נניח שנתונה נוסחת נסיגה, נניח $T(n)=T(n/2)+O(1)$. לפני שנעסוק בפתרון משוואות מעין זו, ישנן שתי בעיות טכניות שאתן עלינו להתמודד.

1. שגיאות עיגול - עפ"י הנוסחה הנ"ל יוצא שזמן הריצה של האלגוריתם על קלט בגודל 13, הוא זמן הריצה של האלגוריתם על קלט בגודל 6.5 פלוס משהו. אבל מה משמעות קלט בגודל 6.5?
2. תנאי עצירה - עפ"י הנוסחה הנ"ל נוכל, ללא תנאי עצירה, להגיע למסקנה שזמן הריצה אינסופי:

$T(13)=T(13/2)+O(1)$
$T(13)=T(13/4)+O(1)+O(1)$
$T(13)=T(13/8)+O(1)+O(1)+O(1)$
$T(13)=T(13/16)+O(1)+O(1)+O(1)+O(1)$
$\cdots$

נתמודד עם שתי הבעיות כך:

1. שגיאות עיגול - מבעיה זו פשוט נתעלם. (בכלל, בנושא זה של נוסחאות נסיגה נתעלם משגיאות עיגול.) למעשה, אם נקבל נוסחה כגון $T(n)=2\cdot T(\lceil n/2\rceil )+\mathrm{\Theta }(n)$, אז נהפוך אותה ל$T(n)=2\cdot T(n/2)+\mathrm{\Theta }(n)$.
2. תנאי עצירה - כאן נקבע איזשהו ארגומנט עצירה כרצוננו, נניח 1 (או 2, או 1000), ונוכיח את הטענה החל מאותו ארגומנט עצירה. בעשותנו זאת, נוכל להסתמך על כך ש$T(1)=O(1)$ (או $=O(1)$, או $T(1000)=O(1)$).

הגישות לפתרון

ישנן שתי שיטות (עיקריות) לפתור נוסחאות נסיגה:

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

פרישה

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

תבנית:מבנה תבנית

תבנית:מבנה תבנית

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

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

תבנית:מבנה תבנית

משפט המאסטר

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

הנה דוגמה לשימוש במשפט המאסטר.

תבנית:מבנה תבנית

תבנית:שימו לב

אינדוקציה

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

תבנית:מבנה תבנית