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

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

כדאי לדעת: בספר הקורס, הפרק "Recurrences" דן בנושאים אלה.

מהן נוסחאות נסיגה?

הגדרה: נניח ש$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם (או חלקו) על קלט בגודל $\displaystyle n$. נוסחת נסיגה על $\displaystyle T(n)$ מתארת את $\displaystyle T(n)$ בעזרת $\displaystyle T(n')$ עבור ערכי $\displaystyle n'$ קטנים מ$\displaystyle n$.

בעיות טכניות

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

שימו לב: אנו עוסקים בנוסחאות נסיגה של פונקציות המתארות זמני ריצה של אלגוריתמים או חלקיהם.

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

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

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

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

עכשיו תורכם: $\displaystyle k$הוא מספר שלם חיובי, ו$\displaystyle T(k)$ מתארת את זמן הריצה של אלגוריתם כלשהו על קלט בגודל $\displaystyle k$. מדוע בהכרח $\displaystyle T(k)=O(1)$?

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

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

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

פרישה

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

דוגמה: נפרוש את נוסחת הנסיגה $\displaystyle T(n)=T(n/2)+O(1)$. עץ הפרישה. ט"ו בשבט שמח. מהפרישה ברור שהתוצאה היא $\displaystyle O(1)\cdot h$, כאשר $\displaystyle h$ הוא גובה העץ. נוכל לפתור את התרגיל ברגע שנדע את גובה העץ (מיד נעסוק בכך).

דוגמה: נפרוש את נוסחת הנסיגה $\displaystyle T(n)=2\cdot T(n/3)+O(1)$. עץ הפרישה. ט"ו בשבט שמח. מהפרישה ברור שהתוצאה היא $\displaystyle \sum _{i=1}^{h}[\Theta (2^{i-1})]$, כאשר $\displaystyle h$ הוא גובה העץ. נוכל לפתור את התרגיל ברגע שנדע את גובה העץ (מיד נעסוק בכך).

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

משפט: נתון $\displaystyle T(n)=a\cdot T(n/b)+f(n)$, עבור שלם $\displaystyle a\geq 1$ וקבוע $\displaystyle b>1$ כלשהם. יהי $\displaystyle h$ גובה העץ המתאים. אז $\displaystyle h=\log _{b}(n)\pm O(1)$.

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

דוגמה: אם $\displaystyle T(n)=T(n/2)+O(1)$, אז $\displaystyle T(n)=\Theta (\log(n))$. הוכחה: ראינו שאם $\displaystyle T(n)=T(n/2)+O(1)$, אז $\displaystyle T(n)=O(1)\cdot h$, כאשר $\displaystyle h$ גובה העץ, אבל מהמשפט האחרון, $\displaystyle h=\log _{2}(n)\pm O(1)$.

דוגמה: אם $\displaystyle T(n)=2\cdot T(n/3)+O(1)$, אז $\displaystyle T(n)=\Theta (n^{\log _{3}(2)})$. הוכחה: ראינו שאם $\displaystyle T(n)=2\cdot T(n/3)+O(1)$, אז $\displaystyle T(n)=\sum _{i=1}^{h}[\Theta (2^{i-1})]=$ $\displaystyle \Theta (\sum _{i=1}^{h}[2^{i-1}])=$ $\displaystyle \Theta (2^{h}-1),$ כאשר $\displaystyle h$ גובה העץ, אבל מהמשפט האחרון, $\displaystyle h=\log _{3}(n)\pm O(1)$. נקבל, לכן, $\displaystyle T(n)=\Theta (2^{h}-1)=$ $\displaystyle \Theta (2^{\log _{3}(n)\pm O(1)}-1)=$ $\displaystyle \Theta (2^{\log _{3}(n)}2^{\pm O(1)}-1)$ כעת משתמש בזהות הלוגריתמית האומרת שלכל $\displaystyle a,b,c>0$ ,‏$\displaystyle a^{\log _{b}(c)}=c^{\log _{b}(a)}$. נקבל $\displaystyle T(n)=\Theta (n^{\log _{3}(2)}2^{\pm O(1)}-1)$ כל שנותר הוא לשים לב ש$\displaystyle n^{\log _{3}(2)}2^{\pm O(1)}-1$ הוא פולינום ב$\displaystyle n$ בדרגה $\displaystyle \log _{3}(2)$. נובע, לכן, מכלל הגבול בסדרי גדילה, $\displaystyle T(n)=\Theta (n^{\log _{3}(2)})$

משפט המאסטר

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

משפט: נתון $\displaystyle T(n)=a\cdot T(n/b)+f(n)$, עבור שלם $\displaystyle a\geq 1$ וקבוע $\displaystyle b>1$ כלשהם. אז: $\displaystyle \exists _{\epsilon >0}f(n)=O(n^{\log _{b}(a)-\epsilon })\Rightarrow T(n)=\Theta (n^{\log _{b}(a)})$ $\displaystyle f(n)=\Theta (n^{\log _{b}(a)})\Rightarrow T(n)=\Theta (n^{\log _{b}(a)}\log(n))$ $\displaystyle \exists _{\epsilon >0}f(n)=\Omega (n^{\log _{b}(a)+\epsilon })\bigwedge \exists _{c<1,n_{0}>0}\forall _{n>n_{0}}a\cdot f(n/b)\leq c\cdot f(n)\Rightarrow T(n)=\Theta (f(n))$

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

דוגמה: הוכח שאם $\displaystyle T(n)=2\cdot T(n/3)+O(1)$, אז $\displaystyle T(n)=\Theta (n^{\log _{3}(2)})$. הוכחה: כאן $\displaystyle a=2$, $\displaystyle b=3$, ו$\displaystyle f(n)=O(1)$. נבחר $\displaystyle \epsilon =\log _{3}(2)/2$. אז $\displaystyle f(n)=O(1)=O(n^{\log _{b}(a)-\epsilon })=O(n^{\log _{3}(2)-(\log _{3}(2)/2)})$. מכאן אפשר לראות שמקרה 1 מתקיים, ולכן $\displaystyle T(n)=\Theta (n^{\log _{b}(a)})=\Theta (n^{\log _{3}(2)})$ (מה שמתאים למה שראינו לפני כן).

שימו לב: משפט המאסטר חל אך ורק על נוסחאות מהצורה $\displaystyle T(n)=a\cdot T(n/b)+f(n)$, אולם ייתכנו מצבים בהם לנוסחת הנסיגה ישנה הצורה $\displaystyle T(n)=a\cdot T(n/b)+f(n)$, אך אף אחד מהתנאים בסעיפים אינו מתקיים. יש מצבים שבהם פשוט אי אפשר להשתמש במשפט המאסטר.

אינדוקציה

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

דוגמה: נוכיח שאם $\displaystyle T(n)=T(n/2)+n$, אז $\displaystyle T(n)=O(n\cdot \log(n))$. הוכחה: נראה (באינדוקציה) שקיימים $\displaystyle c$, $\displaystyle n_{0}$, כך שלכל $\displaystyle n\geq n_{0}$,‏ $\displaystyle T(n)\leq c\cdot n\cdot \log(n)$. (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונראה שהיא נכונה גם עבור $\displaystyle n$: $\displaystyle T(n)=T(n/2)+n\leq$ $\displaystyle c\cdot n\cdot \log(n/2)+n=$ $\displaystyle c\cdot n\cdot \log(n)-c\cdot n+n=$ $\displaystyle c\cdot n\cdot \log(n)-n\cdot (c-1).$ לכל $\displaystyle c\geq 1$ שנבחר, הביטוי האחרון קטן או שווה ל$\displaystyle c\cdot n\cdot \log(n)$. (בסיס האינדוקציה) ננסה להראות שהטענה נכונה עבור $\displaystyle n=1$: $\displaystyle T(1)=O(1)\leq c\cdot 1\cdot \log(1)=0$. כאן נתקלנו בבעיה, כי $\displaystyle O(1)$ חיובי ממש (בקורס זה). ננסה שוב.(בסיס האינדוקציה) ננסה להראות שהטענה נכונה עבור $\displaystyle n=2$ ו$\displaystyle n=3$: $\displaystyle T(2)\leq c\cdot 2\cdot \log(2)$ $\displaystyle T(3)\leq c\cdot 3\cdot \log(3)$ כלומר, בסיס האינדוקציה יחזיק אם נבחר $\displaystyle c\geq \max\{T(2)/(2\cdot \log(2)),T(3)/(3\cdot \log(3))\}$. לסיכום, הוכחנו את הטענה לכל $\displaystyle n\geq 2$, עבור איזה $\displaystyle c\geq \max\{1,T(2)/(2\cdot \log(2)),T(3)/(3\cdot \log(3))\}$ שנבחר.

דוגמה: נוכיח שאם $\displaystyle T(n)=T(n/2)+1$, אז $\displaystyle T(n)=O(\log(n))$. הוכחה: נראה (באינדוקציה) שקיימים $\displaystyle c$, $\displaystyle n_{0}$, כך שלכל $\displaystyle n\geq n_{0}$,‏ $\displaystyle T(n)\leq c\cdot \log(n)$. (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונראה שהיא נכונה גם עבור $\displaystyle n$: $\displaystyle T(n)=T(n/2)+1\leq$ $\displaystyle c\cdot \log(n/2)+1=$ $\displaystyle c\cdot \log(n)-c+1=$ $\displaystyle c\cdot \log(n)-(c-1).$ לכל $\displaystyle c\geq 1$ שנבחר, הביטוי האחרון קטן או שווה ל$\displaystyle c\cdot \log(n)$. (בסיס האינדוקציה) ננסה להראות שהטענה נכונה עבור $\displaystyle n=1$: $\displaystyle T(1)=O(1)\leq c\cdot \log(1)=0$. כאן נתקלנו בבעיה, כי $\displaystyle O(1)$ חיובי ממש (בקורס זה). ננסה שוב.(בסיס האינדוקציה) ננסה להראות שהטענה נכונה עבור $\displaystyle n=2$ ו$\displaystyle n=3$: $\displaystyle T(2)\leq c\cdot \log(2)$ $\displaystyle T(3)\leq c\cdot \log(3)$ כלומר, בסיס האינדוקציה יחזיק אם נבחר $\displaystyle c\geq \max\{T(2)/\log(2),T(3)/\log(3)\}$. לסיכום, הוכחנו את הטענה לכל $\displaystyle n\geq 2$, עבור איזה $\displaystyle c\geq \max\{1,T(2)/\log(2),T(3)/\log(3)\}$ שנבחר.

הפרק הקודם: סדרי גדילה

נוסחאות נסיגה תרגילים

הפרק הבא: מציאת סיבוכיות פסוודו-קוד