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

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

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

קפיצה אל: ניווט, חיפוש

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

תוכן עניינים

1 תרגום ביטויים מפורשים לסדרי גדילה
- 1.1 שאלה
- 1.2 תשובה
2 שאלה בסיסית ביחסים
- 2.1 שאלה
- 2.2 תשובה
  - 2.2.1 1
  - 2.2.2 2
  - 2.2.3 3
  - 2.2.4 4
  - 2.2.5 5
3 הוכחת אדיטיביות
- 3.1 שאלה
- 3.2 תשובה
4 הוכחת טרנזיטיבות
- 4.1 שאלה
- 4.2 תשובה
5 עוד כללים בסדרי גדילה
- 5.1 שאלה
- 5.2 תשובה
6 כללים לגבי מקסימום
- 6.1 שאלה
- 6.2 תשובה
  - 6.2.1 1
  - 6.2.2 2
7 כלל שלילי בגבולות
- 7.1 שאלה
- 7.2 תשובה
8 יחסים בין פולינומים
- 8.1 שאלה
- 8.2 תשובה
9 הכוון השני לכללי הגבולות
- 9.1 שאלה
- 9.2 תשובה
10 טור פולינומים
- 10.1 שאלה
- 10.2 תשובה
11 טור כפול
- 11.1 שאלה
- 11.2 תשובה
  - 11.2.1 שיטה א'
  - 11.2.2 שיטה ב'
12 חסם על טור לבניית ערימה בינרית ממערך
- 12.1 שאלה
- 12.2 תשובה

[עריכה] תרגום ביטויים מפורשים לסדרי גדילה

[עריכה] שאלה

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

$\displaystyle f(n) = n + c_1 n \log^2(n)$
$\displaystyle g(n) =n + c_2 n^2$
כאשר $\displaystyle c_1 > c_2 > 0$ .

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

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

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

הוכחה: $\displaystyle \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} =$
$\displaystyle \lim_{n \rightarrow \infty} \frac{n + c_1 n \log^2(n)}{n + c_2n^2} =$
$\displaystyle \lim_{n \rightarrow \infty} \frac{\frac{1}{n} + c_1 \frac{1}{n} \log^2(n)}{\frac{1}{n} + c_2} =$
$\displaystyle 0$

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

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

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

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

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

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

[עריכה] שאלה בסיסית ביחסים

[עריכה] שאלה

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

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

שימו לב:

הכוונה בסעיף הראשון לפונקציה הקבועה $\displaystyle f(n) = 80$ ,‏ ולא לקבוע 80.

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

[עריכה] 1

נכון.

הוכחה: נבחר $\displaystyle c = 1$ ‏ ו $\displaystyle n_0 = 100$ ‏,‏ ונוודא $\displaystyle \forall_{n \ge 100}80 \le 1 \cdot 3 \cdot n$ .

[עריכה] 2

נכון.

הוכחה: נבחר $\displaystyle c = 2^{1008}$ ‏ ו $\displaystyle n_0 = 1$ ‏,‏ ונוודא $\displaystyle \forall_{n \ge 1}2^{n + 1003} + 30 = 2^{1003} \cdot 2^n + 30 \le 2^{1008} \cdot 2^n$ .

[עריכה] 3

נכון.

הוכחה: נבחר $\displaystyle c = 3$ ‏ ו $\displaystyle n_0 = 1$ ‏,‏ ונוודא $\displaystyle \forall_{n \ge 1}2 \cdot n + 7 \le 3 \cdot (2 \cdot n + 3) = 6 \cdot n + 9$ .

[עריכה] 4

לא נכון.

הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור $\displaystyle c > 0$ ו $\displaystyle n_0 > 0$ כלשהם, $\displaystyle \forall_{n \ge n_0}3 \cdot n \le c \cdot 1$ . אם נציב $\displaystyle n = n_0 + \left\lceil c\right\rceil,$ נקבל

$\displaystyle (3 \cdot n)|^{n_0 + \left\lceil c\right\rceil} = 3 \cdot n_0 + 3 \cdot \left\lceil c\right\rceil \le$
$\displaystyle (c \cdot 1)|^{n_0 + \left\lceil c\right\rceil} = c,$
שאינו הגיוני.

[עריכה] 5

נכון.

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

[עריכה] הוכחת אדיטיביות

[עריכה] שאלה

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

$\displaystyle \Omega(f(n)) + \Omega(g(n)) = \Omega(f(n) + g(n))$ .

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

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

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

$\displaystyle f_1(n) = \Omega(f(n))$ משמעו שלכל $\displaystyle n \ge n_{0,f}$ ,‏ $\displaystyle f_1(n) \ge c _f\cdot f(n)$ ,‏ עבור $\displaystyle c_f, n_{0, f} > 0$ כלשהם.
$\displaystyle g_1(n) = \Omega(g(n))$ משמעו שלכל $\displaystyle n \ge n_{0,g}$ ,‏ $\displaystyle g_1(n) \ge _g\cdot g(n)$ ,‏ עבור $\displaystyle c_g, n_{0, g} > 0$ כלשהם.

לכן:

לכל $\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}$ ,‏ $\displaystyle f_1(n) \ge \max\{c_f, c_g\}\cdot f(n)$ .
לכל $\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}$ ,‏ $\displaystyle g_1(n) \ge \max\{c_f, c_g\}\cdot g(n)$ .

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

[עריכה] הוכחת טרנזיטיבות

[עריכה] שאלה

אנא הוכח את טרנזיטיביות ל $\displaystyle \Omega$ :

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

‏ $\displaystyle f(n) = \Omega(g(n)) \wedge g(n) = \Omega(h(n)) \Rightarrow f(n) = \Omega(h(n))$ .

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

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

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

$\displaystyle f(n) = \Omega(g(n))$ משמעו שלכל $\displaystyle n \ge n_{0,f}$ ,‏ $\displaystyle f(n) \ge c_f \cdot g(n)$ ,‏ עבור $\displaystyle n_{0,f}, c_f > 0$ כלשהם.
$\displaystyle g(n) = \Omega(h(n))$ משמעו שלכל $\displaystyle n \ge n_{0,g}$ ,‏ $\displaystyle g(n) \ge c_g \cdot g(n)$ ,‏ עבור $\displaystyle n_{0,g}, c_g > 0$ כלשהם.

לכן:

לכל $\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}$ ,‏ $\displaystyle f (n) \ge c_f \cdot f(n)$ .
לכל $\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}$ ,‏ $\displaystyle g (n) \ge c_g \cdot g(n)$ .

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

לכל $\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}$ ,‏‏ $\displaystyle f(n) \ge c_f \cdot c_g \cdot h(n)$ .

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

[עריכה] שאלה

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

$\displaystyle f(n) = O(g(n)) \Rightarrow g(n) = O(f(n))$
$\displaystyle f(n) + g(n) = \Theta(min\{f(n), g(n)\})$
$\displaystyle f(n) = O(g(n)) \Rightarrow 2^{f(n)} = O(2^{g(n)})$
$\displaystyle f(n) +\Theta(f(n)) = \Theta(f(n))$
$\displaystyle f(n) = 2^{\log(n)}, g(n) = (\log(n))^{\log(n)} \Rightarrow f(n) = O(g(n))$

כדאי לדעת:

משמעות הביטוי בצד שמאל של סעיף 4 הוא הפונקציה $\displaystyle f(n)$ פלוס פונקציה כלשהי ששייכת ל $\displaystyle \Theta(f(n))$ .

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

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

לא נכון. נפריך ע"י $\displaystyle f(n) = n^2, g(n) = n^3$ .
לא נכון. נפריך ע"י $\displaystyle f(n) = n^2, g(n) = n^3$ .
לא נכון. נפריך ע"י $\displaystyle f(n) = 2 \cdot n, g(n) = n$ .
לכל פונקציה $\displaystyle g(n) = \Theta(f(n))$ מתקיים ש $\displaystyle c'' \cdot f(n) \le g(n)\le c'\cdot f(n)$ , עבור $\displaystyle c'',c' > 0$ כלשהם, החל מ $\displaystyle n_0>0$ כלשהו. לכן, החל מאותו $\displaystyle n_0$ ,‏‏ $\displaystyle (1 + c'')\cdot f(n)\le f(n) + g(n)\le(1 + c')\cdot f(n),$
‏ מה שמוכיח את הטענה.
$\displaystyle lim_{n \rightarrow \infty}[f(n)/g(n)]=0$ (לפי כללים פשוטים מחדו"א),

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

[עריכה] כללים לגבי מקסימום

[עריכה] שאלה

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

$\displaystyle f(n) + g(n) = \Theta(\max\{f(n), g(n)\})$
$\displaystyle f(n) - g(n) = \Theta(\max\{f(n), g(n)\})$

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

[עריכה] 1

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

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

[עריכה] 2

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

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

[עריכה] שאלה

$\displaystyle f(n)$ ו $\displaystyle g(n)$ הן פונקציות חיוביות ממש, והגבול $\displaystyle lim_{n \rightarrow \infty} [f(n)/g(n)]$ קיים ושווה ל $\displaystyle lim_{n \rightarrow \infty} [f(n)/g(n)] = c$ . אנא הוכח או הפרך את הטענה הבאה: אם $\displaystyle c = 0$ או $\displaystyle c = \infty$ ,‏ אז $\displaystyle f(n) \ne \Theta(g(n))$ .

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

הטענה נכונה.

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

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

משפט:

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

אם $\displaystyle c = 0$ אז $\displaystyle f(n) \ne \Omega(g(n))$ .
אם $\displaystyle c = \infty$ אז $\displaystyle f(n) \ne O(g(n))$ .

[עריכה] יחסים בין פולינומים

[עריכה] שאלה

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

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

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

$\displaystyle f < g \Rightarrow f(n) = O(g(n))$
$\displaystyle f = g \Rightarrow f(n) = \Theta(g(n))$
$\displaystyle f > g \Rightarrow f(n) = \Omega(g(n))$

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

[עריכה] הכוון השני לכללי הגבולות

[עריכה] שאלה

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

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

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

ראשית נקבע צמדים של נקודות.
1. נקבע $\displaystyle n_0 = 1$ ,‏ ו $\displaystyle n_1$ כנקודה הקטנה ביותר בה $\displaystyle f(n_1) \ge 2 \cdot f(n_0)$ ‏(חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏‏.
2. נקבע $\displaystyle n_2 = n_1 + 1$ ,‏ ו $\displaystyle n_3$ כנקודה הקטנה ביותר בה $\displaystyle f(n_3) \ge 2 \cdot f(n_2)$ (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏.
3. נמשיך כך הלאה: נקבע $\displaystyle n_4 = n_3 + 1$ ,‏ ו $\displaystyle n_5$ כנקודה הקטנה ביותר בה $\displaystyle f(n_5) \ge 2 \cdot f(n_4$ ) (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏, וכולי.
כעת נגדיר את בעזרת הזוגות:
1. עבור $\displaystyle n_0 \le n < n_1$ ,‏ $\displaystyle g(n) = f(n_0)$ ;‏ $\displaystyle g(n_1) = f(n_1) / 2$ .
2. עבור $\displaystyle n_2 \le n < n_3$ ,‏ $\displaystyle g(n) = f(n_2)$ ;‏ $\displaystyle g(n_3) = f(n_3) / 2$ .
3. עבור $\displaystyle n_4 \le n < n_5$ ,‏ $\displaystyle g(n) = f(n_4)$ ;‏ $\displaystyle g(n_5) = f(n_5) / 2$ . נמשיך כך הלאה והלאה.מהבניה קל לראות את הדברים הבאים:
4. $\displaystyle g(n)$ פונקציה מונוטונית עולה.
5. בכל נקודה ונקודה, $\displaystyle g(n)$ נמצאת בין $\displaystyle f(n)$ ל $\displaystyle f(n) / 2$ . לכן $\displaystyle g(n) = \Theta(f(n))$ בהכרח.
6. יש אינסוף נקודות בהן $\displaystyle f(n) = g(n)$ , אבל גם אינסוף נקודות בהן $\displaystyle g(n) = f(n) / 2$ , ולכן לא ייתכן שהגבול $\displaystyle f(n) / g(n)$ קיים.

כדאי לדעת:

לכאורה אפשר לבנות פונקציה $\displaystyle g_1(n)$ פשוטה הרבה יותר מהמוצגת כאן, לדוגמה:

$\displaystyle g_1(n) = f(n)$ אם $\displaystyle n$ זוגי.
$\displaystyle g_1(n) = f(n) / 2$ אם $\displaystyle n$ אי זוגי.

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

[עריכה] טור פולינומים

[עריכה] שאלה

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

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

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

[עריכה] טור כפול

[עריכה] שאלה

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

אנא הוכח $\displaystyle T(n) = \Theta(n^3)$ .

רמז

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

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

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

[עריכה] שיטה א'

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

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

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

כעת נראה כי $\displaystyle f(n) = \Omega(n^3)$ .

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

לכן נקבל

$\displaystyle f(n) \ge \sum_{i = 1}^{n/4}\sum_{j = 3n/4}^n[\Omega(n)] = \Theta(n^3)$ .

[עריכה] שיטה ב'

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

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

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

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

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

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

[עריכה] שאלה

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

רמז

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

כדאי לדעת:

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

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

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

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

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

כדאי לדעת:

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

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

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

תוכן עניינים

[עריכה] תרגום ביטויים מפורשים לסדרי גדילה

[עריכה] שאלה

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

[עריכה] שאלה בסיסית ביחסים

[עריכה] שאלה

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

[עריכה] 1

[עריכה] 2

[עריכה] 3

[עריכה] 4

[עריכה] 5

[עריכה] הוכחת אדיטיביות

[עריכה] שאלה

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

[עריכה] הוכחת טרנזיטיבות

[עריכה] שאלה

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

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

[עריכה] שאלה

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

[עריכה] כללים לגבי מקסימום

[עריכה] שאלה

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

[עריכה] 1

[עריכה] 2

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

[עריכה] שאלה

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

[עריכה] יחסים בין פולינומים

[עריכה] שאלה

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

[עריכה] הכוון השני לכללי הגבולות

[עריכה] שאלה

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

[עריכה] טור פולינומים

[עריכה] שאלה

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

[עריכה] טור כפול

[עריכה] שאלה

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

[עריכה] שיטה א'

[עריכה] שיטה ב'

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

[עריכה] שאלה

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

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא