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

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

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

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

[עריכה] נוסחת נסיגה עם שורש

[עריכה] שאלה

בנוסחת הנסיגה $\displaystyle T(n) = T(\sqrt{n}) + \log(n)$ ,‏ $\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו. אנא פתור את הנוסחה.

[עריכה] תשובה

נשתמש בפרישה.בעץ המתאים לנוסחה:

צומת הראש מציין את $\displaystyle T(n)$ , והרמה הראשונה תורמת $\displaystyle \log(n)$ .
ברמה הבאה, הצומת מציין את $\displaystyle T(\sqrt{n}) = t(n^{1/2})$ , והרמה תורמת $\displaystyle \log(\sqrt{n}) = 1/2 \cdot \log(n)$ .
ברמה הבאה אחריה, הצומת מציין את $\displaystyle T(\sqrt{n^{1/2}}) = t(n^{1/4})$ , והרמה תורמת $\displaystyle \log(\sqrt{n^{1/2}}) = 1/4 \cdot \log(n)$ .

החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה $\displaystyle i$ (כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את $\displaystyle T(n^{1/2^i})$ , והרמה תורמת $\displaystyle 1/2^i \cdot \log(n)$ .

כדי למצוא את גובה העץ, $\displaystyle m$ , נפתור $\displaystyle n^{1/2^i} = 2$ : $\displaystyle n^{1/2^m} = 2$
$\displaystyle \log(n^{1/2^m}) = 1$
$\displaystyle 1/2^m \cdot \log(n) = 1$
$\displaystyle 2^m = \log(n)$
$\displaystyle m = \log(\log(n))$
כאמור, הרמה ה $\displaystyle i$ תורמת $\displaystyle 1/2^i \cdot \log(n)$ . נותר, לכן, לסכם את $\displaystyle \sum_{i = 1}^{\log(\log(n))}[1/2^i \cdot \log(n)]$ : $\displaystyle \sum_{i = 0}^{\log(\log(n))}[1/2^i \cdot \log(n)] =$
$\displaystyle \sum_{i = 0}^{\log(\log(n))}[1/2^i] \cdot \log(n) =$
$\displaystyle \Theta(1) \cdot \log(n) =$
$\displaystyle \Theta(\log(n))$

[עריכה] נוסחת נסיגה לבעיית "דג הסלמון"

[עריכה] שאלה

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם $\displaystyle T(n) = \sum_{i = 1}^{n - 1}[T(i)] + \Theta(n)$ אז $\displaystyle T(n) = \Omega(1.5^n)$ .

כדאי לדעת:

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

[עריכה] תשובה

הוכחה: נוכיח באינדוקציה שקיים $\displaystyle c > 0$ כך ש $\displaystyle T(n) \ge c \cdot 1.5^n$ .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n - 1$ , ונוכיח שהיא נכונה ל $\displaystyle n$ .‏ עפ"י נוסחת הנסיגה, $\displaystyle T(n) = \sum_{i = 1}^{n - 1} [T(i)] + \Theta(n) \ge \sum_{i = 1}^{n - 1} [T(i)] + c' \cdot n$
עבור $\displaystyle c'$ כלשהו. לכן, עפ"י הנחת האינדוקציה, $\displaystyle T(n) \ge \sum_{i = 1}^{n - 1} [c \cdot 1.5^i] + c' \cdot n$ .
עפ"י הנוסחה לטור הנדסי,

$\displaystyle \sum_{i = 1}^{n - 1} [c \cdot 1.5^i] + c' \cdot n =$
$\displaystyle c \cdot 1.5^1(1.5^{n - 1} - 1) / (1.5 - 1) + c' \cdot n =$
$\displaystyle 2 \cdot c \cdot 1.5^1(1.5^{n - 1} - 1) + c' \cdot n =$
$\displaystyle 2 \cdot c \cdot 1.5^n - 3 \cdot c + c' \cdot n.$
אם ניקח $\displaystyle c < c' / 3$ ,‏ אז הביטוי האחרון גדול מ $\displaystyle c \cdot 1.5^n$ .

(בסיס האינדוקציה) היות ש $\displaystyle T(1) = O(1)$ ,‏ אז $\displaystyle T(1) = c_0$ ,‏ עבור $\displaystyle c_0 > 0$ כלשהו. נפתור $\displaystyle T(1) = c_0 \ge c \cdot 1.5^1$ ,‏ ונקבל $\displaystyle c \le c_0 / 1.5$ .‏

האינדוקציה, לכן, נכונה עבור $\displaystyle 0 < c < \min\{c_0 / 1.5, c' / 3\}$ , החל מ $\displaystyle n = 1$ .

[עריכה] נוסחת נסיגה לאיחוד קבוצות זרות על פי גודל

[עריכה] שאלה

אנא הוכחה את המשפט הבא:

משפט:

פתרון $\displaystyle T(n) = \max_{1 \le i \le n / 2}[T(i) + T(n - i) + \Theta(i)]$
הוא $\displaystyle O\left( n \cdot \log(n) \right)$
.

כדאי לדעת:

נצטרך את פתרונה של בעיה זו כשנדבר על מבני נתונים לקבוצות זרות.

[עריכה] תשובה

נוכיח באינדוקציה שקיים $\displaystyle c > 0$ כך ש(עבור $\displaystyle n$ -ים מספיק גדולים) $\displaystyle T(n) \le c \cdot n \cdot \log(n)$ .

(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,

$\displaystyle T(n) = \max_{i = 1, \ldots, n / 2}[T(i) + T(n - i) + \Theta(i)] \le$
$\displaystyle \max_{i = 1, \ldots, n / 2}[c \cdot i \cdot \log(i) + c \cdot (n - i) \cdot \log(n - i) + c' \cdot i]$
עבור קבוע $\displaystyle c' > 0$ כלשהו.

נגזור את הביטוי שבתוך ה $\displaystyle \max$ , ונקבל $\displaystyle c \cdot \log(i) - c \cdot \log(n - i) + c'$

נגזור את הביטוי פעם שניה, ונקבל ביטוי חיובי. מכאן ברור שמקסימום הביטוי הוא כאשר $\displaystyle i = n / 2$ .

כאשר $\displaystyle i = n / 2$ , אז

$\displaystyle T(n) \le 2 \cdot c \cdot n / 2 \cdot \log(n / 2) + c' =$
$\displaystyle c \cdot n \cdot \log(n) - c \cdot n + c' \le$
$\displaystyle c \cdot n \cdot \log(n)$

(בסיס האינדוקציה) נפתור: $\displaystyle (c \cdot i \cdot \log(i))|^{i = 2, 3} = O(1)$
ונווכח שהדבר נכון עבור $\displaystyle c$ גדול מספיק.

[עריכה] נוסחות נסיגה פשוטות

[עריכה] שאלה

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו.

אנא הוכח שפתרון נוסחת הנסיגה $\displaystyle T(n) = T(n - 1) + 6$ הוא $\displaystyle T(n) = \Theta(n)$ .
אנא הוכח שפתרון נוסחת הנסיגה $\displaystyle T(n) = T(n - 1) + 6 \cdot n$ הוא $\displaystyle T(n) = \Theta(n^2)$ .

הנחיות

להלן הנחיות לסעיף הראשון:

אנא הסבר מדוע מותר לקבוע ש $\displaystyle T(10) = k$ עבור קבוע $\displaystyle k > 0$ כלשהו.
נניח שקיים קבוע $\displaystyle c > 0$ כך שלכל $\displaystyle i < n$ מתקיים ‎ $\displaystyle T(i) \le c \cdot i$ . אנא הסבר מדוע בהכרח $\displaystyle T(n) \le c \cdot (n - 1) + 6$ . אנא מצא תנאי על $\displaystyle c$ כך שבהכרח נובע מכך כי $\displaystyle T(n) \le c \cdot n$ .
אנא הסבר מדוע מהאמור עד כה נובע שבהכרח $\displaystyle T(n) = O(n)$ .
נניח שקיים קבוע $\displaystyle c > 0$ כך שלכל $\displaystyle i < n$ מתקיים ‎ $\displaystyle T(i) \ge c \cdot i$ . אנא הסבר מדוע בהכרח $\displaystyle T(n) \ge c \cdot (n - 1) + 6$ . אנא הסבר מה התנאי על $\displaystyle c$ כך שינבע מכך כי $\displaystyle T(n) \ge c \cdot n$ .
אנא הסבר מדוע מהאמור עד כה נובע שבהכרח $\displaystyle T(n) = \Omega(n)$ .
אנא הסבר מדוע מהאמור עד כה נובע שבהכרח $\displaystyle T(n) = \Theta(n)$ .

[עריכה] תשובה

[עריכה] 1

כרגיל, מותר לנו לקבוע ש $\displaystyle T(10) = k$ עבור קבוע $\displaystyle k$ כלשהו, וזאת משום ש $\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם.

נוכיח ש‎‎ $\displaystyle T(n) = O(n)$ . ליתר דיוק, נוכיח באינדוקציה שקיים $\displaystyle c > 0$ כך ש $\displaystyle T(n) \le c \cdot n$ .

הוכחה: (בסיס האינדוקציה) עבור $\displaystyle n = 10$ , נקבל $\displaystyle T(10) = k \le c \cdot 10$ , כלומר כל שצריך הוא לבחור $\displaystyle c$ המקיים $\displaystyle c \ge k / 10$ .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n - 1$ , ונוכיח שהיא נכונה עד (כולל) $\displaystyle n$ . מהצבה בנוסחת הנסיגה, נקבל $\displaystyle T(n) = T(n - 1) + 6 \le c \cdot n - c + 6.$
עבור $\displaystyle c \ge 6$ , נקבל $\displaystyle T(n) \le c \cdot n$ .

לסיכום, עבור $\displaystyle c \ge \max\{k / 10, 6\}$ , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

נוכיח ש‎‎ $\displaystyle T(n) = \Omega(n)$ . ליתר דיוק, נוכיח באינדוקציה שקיים $\displaystyle c > 0$ כך ש $\displaystyle T(n) \ge c \cdot n$ .

הוכחה: (בסיס האינדוקציה) עבור $\displaystyle n = 10$ , נקבל $\displaystyle T(10) = k \ge c \cdot 10$ , כלומר כל שצריך הוא לבחור $\displaystyle c$ המקיים $\displaystyle c \le k / 10$ .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n - 1$ , ונוכיח שהיא נכונה עד (כולל) $\displaystyle n$ . מהצבה בנוסחת הנסיגה, נקבל $\displaystyle T(n) = T(n - 1) + 6 \ge c \cdot n - c + 6.$
עבור $\displaystyle c \le 6$ , נקבל $\displaystyle T(n) \ge c \cdot n$ .

לסיכום, עבור $\displaystyle c \le \min\{k / 10, 6\}$ , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

[עריכה] 2

עלינו להוכיח שפתרון נוסחת הנסיגה $\displaystyle T(n) = T(n - 1) + 6 \cdot n$ הוא $\displaystyle T(n) = \Theta(n^2)$ . אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום $\displaystyle T(1) = O(1),$
$\displaystyle T(n) = T(n - 1) + 6 \cdot n = T(n - 2) + 6 \cdot (n + n - 1) = \ldots = T(1) + 6 \cdot (n + n - 1 + \ldots + 2) = \Theta(n^2)$

[עריכה] חסמים עליונים ותחתונים למספר נוסחאות נסיגה

[עריכה] שאלה

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

$\displaystyle T(n) = 3 \cdot T(n / 2) + n \cdot \log(n)$ .‏
$\displaystyle T(n) = T(n - 1) + \log(n)$ .‏
$\displaystyle T(n) = T(\alpha \cdot n) + T((1 - \alpha) \cdot n) + \Theta(n)$ , כאשר $\displaystyle 0 < \alpha < 1$ הוא קבוע כלשהו.‏

[עריכה] תשובה

[עריכה] 1

$\displaystyle T(n) = \Theta(n^{\log_2(3)})$ , עפ"י מקרה 1 של משפט המאסטר.

[עריכה] 2

נפרוש את הנוסחה: $\displaystyle T(n) =$
$\displaystyle T(n - 1) + \log(n) =$
$\displaystyle T(n - 2) + \log(n - 1) + \log(n) =$
$\displaystyle T(n - 3) + \log(n - 2) + \log(n - 1) + \log(n) =$
$\displaystyle \cdots$
$\displaystyle \sum_{i = 1}^n[\log(i)] =$
$\displaystyle \Theta(n \cdot \log(n)).$
(את המעבר האחרון ראינו בטורים שימושיים.)

[עריכה] 3

נגדיר $\displaystyle \alpha' = 1 - \alpha$ . בלי הגבלת הכלליות, נניח ש $\displaystyle \alpha < \alpha'$ . להלן עץ הפרישה המתקבל:

בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל $\displaystyle n'$ , אז הילד השמאלי מתאים ל $\displaystyle \alpha n'$ ,‏ והימני מתאים ל $\displaystyle \alpha' n'$ ,‏. מכאן אפשר לראות שמסלולים שמאליים בעץ קצרים יותר ממסלולים ימניים, כי $\displaystyle \alpha' = 1 - \alpha$ .‏ לא כל הרמות בעץ מלאות, אם כן, מה שמקשה מעט על ניתוח הסיבוכיות. נגדיר כ $\displaystyle h_{min}$ את אורך המסלול השמאלי ביותר, וכ $\displaystyle h_{\max}$ את אורך המסלול הימני ביותר.

קל לראות שכל רמה מלאה בעץ תורמת $\displaystyle \Theta(n)$ .‏ הרמה הראשונה תורמת $\displaystyle \Theta(n)$ ;‏ הרמה השניה תורמת $\displaystyle \Theta(\alpha n) + \Theta(\alpha' n) = \Theta(n)$ ,‏ הרמה השלישית תורמת $\displaystyle \Theta(\alpha^2 n) + \Theta(\alpha \alpha' n) + \Theta(\alpha' \alpha n) + \Theta(\alpha'^2 n) = \Theta(\alpha n) + \Theta(\alpha' n)\Theta(n)$ ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש $\displaystyle T(n)$ חסומה מלמטה ע"י $\displaystyle h_{min} \cdot \Theta(n)$ , וחסומה מלמעלה ע"י $\displaystyle h_{\max} \cdot \Theta(n)$ . אבל היות ש $\displaystyle h_{min} = \Theta(\log(n))$ וכן $\displaystyle h_{\max} = \Theta(\log(n))$ , אז $\displaystyle T(n) = \Theta(n \cdot \log(n))$ .

[עריכה] נוסחת נסיגה שאיננה מתאימה למשפט המאסטר

[עריכה] שאלה

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו, והיא פתרונה של נוסחת הנסיגה $\displaystyle T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$ .‏ בנוסחה זו, $\displaystyle a$ מספר שלם גדול ממש מ1, $\displaystyle b$ מספר גדול ממש מ1, ו $\displaystyle f(n)$ היא פונקציה המקיימת $\displaystyle f(n) = \Theta\left( n^{\log_b(a)}\log^k(n) \right)$ , עבור $\displaystyle k$ שלם גדול ממש מ1. אנא הוכח $\displaystyle T(n) = \Theta\left( n^{\log_b(a)}\log^{k + 1}(n) \right)$ .

[עריכה] תשובה

נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם $\displaystyle f(n)$ . ברמה השניה יש $\displaystyle a$ צמתים, וכל אחד מהם תורם $\displaystyle f\left(\frac{n}{b}\right)$ . ברמה ה $\displaystyle i$ (בהנחה שהרמה הראשונה היא ב $\displaystyle i = 0$ ), יש $\displaystyle a^i$ צמתים, וכל אחד מהם תורם $\displaystyle f\left(\frac{n}{b^i}\right)$ . אנו יודעים שגובה העץ הוא $\displaystyle h = \Theta(\log_b(n))$ . נפשט: $\displaystyle \sum_{i = 0}^h\left[ a^i \cdot f\left(\frac{n}{b^i}\right) \right] =$
$\displaystyle \sum_{i = 0}^h \left[ a^i \cdot \Theta\left( \left(\frac{n}{b^i}\right)^{\log_b(a)} \cdot \log^k \left(\frac{n}{b^i}\right) \right) \right] =$
$\displaystyle \Theta\left( \sum_{i = 0}^h \left[ a^i \cdot \frac {n^{\log_b(a)}} {b^{i \cdot \log_b(a)}} \cdot \log^k \left(\frac{n}{b^i}\right) \right] \right) =$
$\displaystyle \Theta\left( \sum_{i = 0}^h \left[ a^i \cdot \frac {n^{\log_b(a)}} {a^i } \cdot \log^k \left(\frac{n}{b^i}\right) \right] \right) =$
$\displaystyle \Theta\left( n^{\log_b(a)} \sum_{i = 0}^h \left[ \cdot \log^k \left(\frac{n}{b^i}\right) \right] \right) =$
$\displaystyle \Theta\left( n^{\log_b(a)} \sum_{i = 0}^h \left[ \left( \log(n) -i \cdot \log(b) \right)^k \right] \right) =$
$\displaystyle \Theta\left( n^{\log_b(a)} \log(b)^k \sum_{i = 0}^h \left[ \left( \frac{\log(n)}{\log(b)} -i \right)^k \right] \right)$
נשים לב שעפ"י חסמי האינטגרלים לטורים,‏ $\displaystyle \sum_{i = 0}^h \left[ \left( \frac{\log(n)}{\log(b)} -i \right)^k \right] = \Theta \left(\log^{k + 1}(n) \right)$ .