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

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

תרגום ביטויים מפורשים לסדרי גדילה

שאלה

נתונות שתי פונקציות:

$f (n) = n + c_{1} n \log^{2} (n)$
$g (n) = n + c_{2} n^{2}$
כאשר $c_{1} > c_{2} > 0$ .

האם $f (n) = O (g (n))$ ?
האם $g (n) = O (f (n))$ ?

תשובה

ראשית נראה ש $f (n) = O (g (n))$ .

הוכחה: $lim_{n \to \infty} \frac{f (n)}{g (n)} =$
$lim_{n \to \infty} \frac{n + c_{1} n \log^{2} (n)}{n + c_{2} n^{2}} =$
$lim_{n \to \infty} \frac{\frac{1}{n} + c_{1} \frac{1}{n} \log^{2} (n)}{\frac{1}{n} + c_{2}} =$
$0$

הטענה נובעת, לכן, מכלל הגבולות בסדרי גדילה.

כעת נראה כי $g (n) \neq O (f (n))$

הוכחה: נניח בשלילה כי $g (n) = O (f (n))$ . אז קיים $c > 0$ כך שעבור ערכי $n$ גדולים מספיק, $g (n) \leq c \cdot f (n)$ .

נחלק את שני האגפים ב $f (n)$ (נזכר שהוא חיובי), ונקבל $\frac{g (n)}{f (n)} \leq c$ עבור ערכי $n$ גדולים מספיק.

ניקח גבול של שני האגפים, ונקבל $lim_{n \to \infty} \frac{g (n)}{f (n)} \leq lim_{n \to \infty} c = c$ .

אבל במקרה כאן, קל לראות שהגבול שואף לאינסוף, ולכן אין קבוע שחוסם אותו מלמעלה.

שאלה בסיסית ביחסים

שאלה

אנא הוכח או הפרך את הטענות הבאות:

$80 = O (3 \cdot n)$ .
$2^{n + 1003} + 30 = O (2^{n})$ .
$2 \cdot n + 7 = O (2 \cdot n + 3)$ .
$3 \cdot n = O (1)$ .
$\log_{2} (n) = O (\log_{10} (n))$ .

שימו לב:

הכוונה בסעיף הראשון לפונקציה הקבועה

f (n) = 80

,‏ ולא לקבוע 80.

תשובה

1

נכון.

הוכחה: נבחר $c = 1$ ‏ ו $n_{0} = 100$ ‏,‏ ונוודא $\forall_{n \geq 100} 80 \leq 1 \cdot 3 \cdot n$ .

2

נכון.

הוכחה: נבחר $c = 2^{1008}$ ‏ ו $n_{0} = 1$ ‏,‏ ונוודא $\forall_{n \geq 1} 2^{n + 1003} + 30 = 2^{1003} \cdot 2^{n} + 30 \leq 2^{1008} \cdot 2^{n}$ .

3

נכון.

הוכחה: נבחר $c = 3$ ‏ ו $n_{0} = 1$ ‏,‏ ונוודא $\forall_{n \geq 1} 2 \cdot n + 7 \leq 3 \cdot (2 \cdot n + 3) = 6 \cdot n + 9$ .

4

לא נכון.

הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור $c > 0$ ו $n_{0} > 0$ כלשהם, $\forall_{n \geq n_{0}} 3 \cdot n \leq c \cdot 1$ . אם נציב $n = n_{0} + ⌈ c ⌉,$ נקבל

$(3 \cdot n) |^{n_{0} + ⌈ c ⌉} = 3 \cdot n_{0} + 3 \cdot ⌈ c ⌉ \leq$
$(c \cdot 1) |^{n_{0} + ⌈ c ⌉} = c,$
שאינו הגיוני.

5

נכון.

הוכחה: באופן כללי, $\log_{b} (a) = \log_{c} (a) / \log_{c} (b)$ , ולכן הביטויים הם למעשה אותו ביטוי עד כדי הכפלה בקבוע.

הוכחת אדיטיביות

שאלה

אנא הוכח את כלל האדיטיביות ל $Ω$ : לכל $f (n), g (n)$ ,‏

$Ω (f (n)) + Ω (g (n)) = Ω (f (n) + g (n))$ .

תשובה

ההוכחה דומה למדי להוכחת האדיטיביות שראינו בהרצאה:

הוכחה: (1) עפ"י ההגדרה:

$f_{1} (n) = Ω (f (n))$ משמעו שלכל $n \geq n_{0, f}$ ,‏ $f_{1} (n) \geq c_{f} \cdot f (n)$ ,‏ עבור $c_{f}, n_{0, f} > 0$ כלשהם.
$g_{1} (n) = Ω (g (n))$ משמעו שלכל $n \geq n_{0, g}$ ,‏ $g_{1} (n) \geq_{g} \cdot g (n)$ ,‏ עבור $c_{g}, n_{0, g} > 0$ כלשהם.

לכן:

לכל $n \geq max {n_{0, f}, n_{0, g}}$ ,‏ $f_{1} (n) \geq max {c_{f}, c_{g}} \cdot f (n)$ .
לכל $n \geq max {n_{0, f}, n_{0, g}}$ ,‏ $g_{1} (n) \geq max {c_{f}, c_{g}} \cdot g (n)$ .

מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.

הוכחת טרנזיטיבות

שאלה

אנא הוכח את טרנזיטיביות ל $Ω$ :

לכל $f (n), g (n)$ ,

‏ $f (n) = Ω (g (n)) \land g (n) = Ω (h (n)) \Rightarrow f (n) = Ω (h (n))$ .

תשובה

ההוכחה דומה למדי להוכחת הטרנזיטיביות שראינו:

(1) עפ"י ההגדרה:

$f (n) = Ω (g (n))$ משמעו שלכל $n \geq n_{0, f}$ ,‏ $f (n) \geq c_{f} \cdot g (n)$ ,‏ עבור $n_{0, f}, c_{f} > 0$ כלשהם.
$g (n) = Ω (h (n))$ משמעו שלכל $n \geq n_{0, g}$ ,‏ $g (n) \geq c_{g} \cdot g (n)$ ,‏ עבור $n_{0, g}, c_{g} > 0$ כלשהם.

לכן:

לכל $n \geq max {n_{0, f}, n_{0, g}}$ ,‏ $f (n) \geq c_{f} \cdot f (n)$ .
לכל $n \geq max {n_{0, f}, n_{0, g}}$ ,‏ $g (n) \geq c_{g} \cdot g (n)$ .

מקבלים את התוצאה ע"י הצבת שני האי-שוויונים האחרונים אחד בשני:

לכל $n \geq max {n_{0, f}, n_{0, g}}$ ,‏‏ $f (n) \geq c_{f} \cdot c_{g} \cdot h (n)$ .

עוד כללים בסדרי גדילה

שאלה

$f (n), g (n)$ הן פונקציות חיוביות ממש. אנא הוכח או הפרך כ"א מהכללים הבאים:

$f (n) = O (g (n)) \Rightarrow g (n) = O (f (n))$
$f (n) + g (n) = Θ (m i n {f (n), g (n)})$
$f (n) = O (g (n)) \Rightarrow 2^{f (n)} = O (2^{g (n)})$
$f (n) + Θ (f (n)) = Θ (f (n))$
$f (n) = 2^{\log (n)}, g (n) = (\log (n))^{\log (n)} \Rightarrow f (n) = O (g (n))$

כדאי לדעת:

משמעות הביטוי בצד שמאל של סעיף 4 הוא הפונקציה

f (n)

פלוס פונקציה כלשהי ששייכת ל

Θ (f (n))

.

תשובה

(לתזכורת, $f (n), g (n)$ הן פונקציות חיוביות ממש.)

לא נכון. נפריך ע"י $f (n) = n^{2}, g (n) = n^{3}$ .
לא נכון. נפריך ע"י $f (n) = n^{2}, g (n) = n^{3}$ .
לא נכון. נפריך ע"י $f (n) = 2 \cdot n, g (n) = n$ .
לכל פונקציה $g (n) = Θ (f (n))$ מתקיים ש $c^{″} \cdot f (n) \leq g (n) \leq c^{'} \cdot f (n)$ , עבור $c^{″}, c^{'} > 0$ כלשהם, החל מ $n_{0} > 0$ כלשהו. לכן, החל מאותו $n_{0}$ ,‏‏ $(1 + c^{″}) \cdot f (n) \leq f (n) + g (n) \leq (1 + c^{'}) \cdot f (n),$
‏ מה שמוכיח את הטענה.
$l i m_{n \to \infty} [f (n) / g (n)] = 0$ (לפי כללים פשוטים מחדו"א),

ולכן עפ"י כללי הגבולות שראינו, הטענה נכונה.

כללים לגבי מקסימום

שאלה

אנא הוכח או הפרך כ"א מהכללים הבאים:

$f (n) + g (n) = Θ (max {f (n), g (n)})$
$f (n) - g (n) = Θ (max {f (n), g (n)})$

תשובה

1

נשים לב שתמיד מתקיים:

$f (n) + g (n) \geq max {f (n), g (n)}$ ,
$f (n) + g (n) \leq 2 \cdot max {f (n), g (n)}$ .
הטענה, לכן, נכונה.

2

ניקח $f (n) = n + 1$ , ו $g (n) = n$ . קל לראות ש $f (n) - g (n) = 1 \neq Θ (n) = Θ (max {f (n), g (n)})$ :‏ הוכחנו בכיתה ש $n^{2} \neq O (n)$ , ובאותו אופן בדיוק אפשר להראות ש $1 \neq Ω (n)$ . הטענה, לכן, איננה נכונה.

כלל שלילי בגבולות

שאלה

$f (n)$ ו $g (n)$ הן פונקציות חיוביות ממש, והגבול $l i m_{n \to \infty} [f (n) / g (n)]$ קיים ושווה ל $l i m_{n \to \infty} [f (n) / g (n)] = c$ . אנא הוכח או הפרך את הטענה הבאה: אם $c = 0$ או $c = \infty$ ,‏ אז $f (n) \neq Θ (g (n))$ .

תשובה

הטענה נכונה.

הוכחה: נניח בשלילה שהטענה מוטעית, ואכן $f (n) = Θ (g (n))$ . עפ"י ההגדרה, לכן, קיימים שני קבועים $c^{″} > 0$ ו $c^{'} > 0$ כך שלערכי $n$ גדולים מספיק, $c^{″} \cdot g (n) \leq f (n) \leq c^{'} \cdot g (n)$ . נחלק ב $g (n)$ (שימו לב שאין צורך להפוך את סימני $\leq$ ), ונקבל $c^{″} \leq f (n) / g (n) \leq c^{'}$ . מכללים ידועים בחדו"א, הוכחנו כעת שגבול המנה (אם הוא קיים) חסום בין $c^{″}$ ל $c^{'}$ , בסתירה לנתון בשאלה.

באופן דומה למדי, נוכל להוכיח את המשפט הבא:

משפט:

$f (n)$ ו $g (n)$ הן פונקציות חיוביות ממש, והגבול $l i m_{n \to \infty} [f (n) / g (n)]$ קיים ושווה ל $l i m_{n \to \infty} [f (n) / g (n)] = c$ .

אם $c = 0$ אז $f (n) \neq Ω (g (n))$ .
אם $c = \infty$ אז $f (n) \neq O (g (n))$ .

יחסים בין פולינומים

שאלה

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

תשובה

נניח ש $f (n)$ פולינום מדרגה $f$ , ו $g (n)$ פולינום מדרגה $g$ . אז:

$f < g \Rightarrow f (n) = O (g (n))$
$f = g \Rightarrow f (n) = Θ (g (n))$
$f > g \Rightarrow f (n) = Ω (g (n))$

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

הכוון השני לכללי הגבולות

שאלה

$f (n)$ היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה $g (n)$ כך שמתקיים $f (n) = Θ (g (n))$ אבל הגבול $f (n) / g (n)$ אינו קיים.

תשובה

נבנה את הפונקציה $g (n)$ כך:

ראשית נקבע צמדים של נקודות.
1. נקבע $n_{0} = 1$ ,‏ ו $n_{1}$ כנקודה הקטנה ביותר בה $f (n_{1}) \geq 2 \cdot f (n_{0})$ ‏(חייבת להיות נקודה כזו, כי $f (n)$ שואפת לאינסוף)‏‏.
2. נקבע $n_{2} = n_{1} + 1$ ,‏ ו $n_{3}$ כנקודה הקטנה ביותר בה $f (n_{3}) \geq 2 \cdot f (n_{2})$ (חייבת להיות נקודה כזו, כי $f (n)$ שואפת לאינסוף)‏.
3. נמשיך כך הלאה: נקבע $n_{4} = n_{3} + 1$ ,‏ ו $n_{5}$ כנקודה הקטנה ביותר בה $f (n_{5}) \geq 2 \cdot f (n_{4}$ ) (חייבת להיות נקודה כזו, כי $f (n)$ שואפת לאינסוף)‏, וכולי.
כעת נגדיר את g(n) בעזרת הזוגות:
1. עבור $n_{0} \leq n < n_{1}$ ,‏ $g (n) = f (n_{0})$ ;‏ $g (n_{1}) = f (n_{1}) / 2$ .
2. עבור $n_{2} \leq n < n_{3}$ ,‏ $g (n) = f (n_{2})$ ;‏ $g (n_{3}) = f (n_{3}) / 2$ .
3. עבור $n_{4} \leq n < n_{5}$ ,‏ $g (n) = f (n_{4})$ ;‏ $g (n_{5}) = f (n_{5}) / 2$ . נמשיך כך הלאה והלאה.מהבניה קל לראות את הדברים הבאים:
4. $g (n)$ פונקציה מונוטונית עולה.
5. בכל נקודה ונקודה, $g (n)$ נמצאת בין $f (n)$ ל $f (n) / 2$ . לכן $g (n) = Θ (f (n))$ בהכרח.
6. יש אינסוף נקודות בהן $f (n) = g (n)$ , אבל גם אינסוף נקודות בהן $g (n) = f (n) / 2$ , ולכן לא ייתכן שהגבול $f (n) / g (n)$ קיים.

כדאי לדעת:

לכאורה אפשר לבנות פונקציה

g_{1} (n)

פשוטה הרבה יותר מהמוצגת כאן, לדוגמה:

$g_{1} (n) = f (n)$ אם $n$ זוגי.
$g_{1} (n) = f (n) / 2$ אם $n$ אי זוגי.

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

טור פולינומים

שאלה

$n_{0}, k$ הם שני קבועים שלמים גדולים ממש מ1. אנא הוכח שמתקיים $\sum_{i = n_{0}}^{n} [i^{k}] = Θ (n^{k + 1})$ .

תשובה

היות ש $n_{0}, k$ הם שני קבועים שלמים גדולים ממש מ1, אז $i^{k}$ היא פונקציה מונוטונית עולה בתחום המתאים, ונוכל להשתמש בכלל הראשון של חסמי האינטגרלים. בנוסף, נזכר ש $\int x^{k} d x = x^{k + 1} / (k + 1) + C$ (עבור $C$ כלשהו). הצבה פשוטה משלימה את ההוכחה.

טור כפול

שאלה

הפונקציה $T (n)$ נתונה על ידי הנוסחה. $T (n) = \sum_{i = 1}^{n} \sum_{j = i}^{n} [Θ (j - i + 1)]$ .

אנא הוכח $T (n) = Θ (n^{3})$ .

רמז

נסה להוכיח זאת באותו אופן בו הוכחנו $\sum_{i = 1}^{n} [\log (i)] = Θ (n \cdot \log (n))$ . כלומר:

הוכח בנפרד חסמי $O$ ו $Ω$ .
ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).

תשובה

שיטה א'

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

ראשית נראה כי $f (n) = O (n^{3})$ .

הוכחה: $f (n) = \sum_{i = 1}^{n} \sum_{j = i}^{n} [Θ (j - i + 1)] \leq \sum_{i = 1}^{n} \sum_{j = 1}^{n} [Θ (n)] = Θ (n^{3})$
.

כעת נראה כי $f (n) = Ω (n^{3})$ .

הוכחה: $f (n) = \sum_{i = 1}^{n} \sum_{j = i}^{n} [Θ (j - i + 1)] \geq \sum_{i = 1}^{n / 4} \sum_{j = i}^{n} [Θ (j - i + 1)] \geq \sum_{i = 1}^{n / 4} \sum_{j = 3 n / 4}^{n} [Θ (j - i + 1)]$ .
נשים לב שכאשר $i$ בתחום $1, \dots, n / 4$ ו $j$ בתחום $3 n / 4, \dots, n$ , אז $Θ (j - i + 1) = Ω (n / 2) = Ω (n)$ .

לכן נקבל

$f (n) \geq \sum_{i = 1}^{n / 4} \sum_{j = 3 n / 4}^{n} [Ω (n)] = Θ (n^{3})$ .

שיטה ב'

$f (n) = \sum_{i = 1}^{n} \sum_{j = i}^{n} [Θ (j - i + 1)]$ .

נשים לב שעבור ערך $i$ כלשהו, נוכל לבצע את החלפת המשתנים $j^{'} = j - i$ , ונקבל $\sum_{j = i}^{n} [Θ (j - i + 1)] = \sum_{j^{'} = 0}^{n - i} [Θ (j^{'} + 1)] = \sum_{j^{'} = 0}^{n - i} [Θ (j^{'})] = Θ ((n - i)^{2})$ .

נציב זאת חזרה בסכום הכפול: $f (n) = \sum_{i = 1}^{n} \sum_{j = i}^{n} [Θ (j - i + 1)] = \sum_{i = 1}^{n} [(n - i)^{2}]$ .

נבצע החלפת משתנים $i^{'} = n - i$ , ונקבל:

$f (n) = \sum_{i = 1}^{n} [(n - i)^{2}] = \sum_{i^{'} = 0}^{n - 1} [i'^{2}] = Θ (n^{3})$ .

חסם על טור לבניית ערימה בינרית ממערך

שאלה

אנא הוכח ש $\sum_{j = 1}^{h} [2^{- j} Θ (j)] = Θ (1)$ .

רמז

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

כדאי לדעת:

נצטרך חסם זה כשננתח את סיבוכיות בניית ערימה בינרית ממערך.

תשובה

מצד אחד, כל טור גדול לפחות כמו איברו הראשון. מכאן נקבל: $\sum_{j = 1}^{h} [2^{- j} Θ (j)] \geq [2^{- 1} Θ (1)] \geq Θ (1)$ ולכן הטור המקורי הוא $Ω (1)$ .

מצד שני, נקבל $\sum_{j = 1}^{h} [2^{- j} Θ (j)] \leq \sum_{j = 1}^{\infty} [2^{- j} Θ (j)] = Θ (\sum_{j = 1}^{\infty} [2^{- j} j])$ , ולכן נחסום מלמעלה את $\sum_{j = 1}^{\infty} [2^{- j} j]$ .

עבור ערכי $j$ מספיק גדולים, $2^{- j} j < 1. 5^{- j}$ (קל לראות זאת מל'וספיטל, לדוגמה). נגדיר את $k$ כאינדקס הראשון בו $2^{- k} k < 1. 5^{- k}$ . נקבל $\sum_{j = 1}^{\infty} [2^{- j} j] = \sum_{j = 1}^{k - 1} [2^{- j} j] + \sum_{j = k}^{\infty} [2^{- j} j] \leq O (1) + \sum_{j = k}^{\infty} [1. 5^{- j}] \leq O (1) + \sum_{j = 1}^{\infty} [1. 5^{- j}] = O (1) + O (1) = O (1)$

כדאי לדעת:

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