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

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

שאלה

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

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

1. האם $\displaystyle f(n)=O(g(n))$?
2. האם $\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_{2}n^{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)\neq O(f(n))$

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

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

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

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

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

שאלה

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

1. $\displaystyle 80=O(3\cdot n)$.
2. $\displaystyle 2^{n+1003}+30=O(2^{n})$.
3. $\displaystyle 2\cdot n+7=O(2\cdot n+3)$.
4. $\displaystyle 3\cdot n=O(1)$.
5. $\displaystyle \log _{2}(n)=O(\log _{10}(n))$.

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

תשובה

1

נכון.

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

2

נכון.

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

3

נכון.

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

4

לא נכון.

הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור $\displaystyle c>0$ ו$\displaystyle n_{0}>0$ כלשהם, $\displaystyle \forall _{n\geq n_{0}}3\cdot n\leq 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 \leq$
$\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\geq n_{0,f}$,‏ $\displaystyle f_{1}(n)\geq c_{f}\cdot f(n)$,‏ עבור $\displaystyle c_{f},n_{0,f}>0$ כלשהם.
• $\displaystyle g_{1}(n)=\Omega (g(n))$ משמעו שלכל$\displaystyle n\geq n_{0,g}$,‏ $\displaystyle g_{1}(n)\geq _{g}\cdot g(n)$,‏ עבור $\displaystyle c_{g},n_{0,g}>0$ כלשהם.

לכן:

• לכל $\displaystyle n\geq \max\{n_{0,f},n_{0,g}\}$,‏ $\displaystyle f_{1}(n)\geq \max\{c_{f},c_{g}\}\cdot f(n)$.
• לכל $\displaystyle n\geq \max\{n_{0,f},n_{0,g}\}$,‏ $\displaystyle g_{1}(n)\geq \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\geq n_{0,f}$,‏ $\displaystyle f(n)\geq c_{f}\cdot g(n)$,‏ עבור $\displaystyle n_{0,f},c_{f}>0$ כלשהם.
• $\displaystyle g(n)=\Omega (h(n))$ משמעו שלכל$\displaystyle n\geq n_{0,g}$,‏ $\displaystyle g(n)\geq c_{g}\cdot g(n)$,‏ עבור $\displaystyle n_{0,g},c_{g}>0$ כלשהם.

לכן:

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

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

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

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

שאלה

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

1. $\displaystyle f(n)=O(g(n))\Rightarrow g(n)=O(f(n))$
2. $\displaystyle f(n)+g(n)=\Theta (min\{f(n),g(n)\})$
3. $\displaystyle f(n)=O(g(n))\Rightarrow 2^{f(n)}=O(2^{g(n)})$
4. $\displaystyle f(n)+\Theta (f(n))=\Theta (f(n))$
5. $\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)$ הן פונקציות חיוביות ממש.)

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

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

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

שאלה

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

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

תשובה

1

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

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

2

ניקח $\displaystyle f(n)=n+1$, ו$\displaystyle g(n)=n$. קל לראות ש$\displaystyle f(n)-g(n)=1\neq \Theta (n)=\Theta (\max\{f(n),g(n)\})$:‏ הוכחנו בכיתה ש$\displaystyle n^{2}\neq O(n)$, ובאותו אופן בדיוק אפשר להראות ש $\displaystyle 1\neq \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)\neq \Theta (g(n))$.

תשובה

הטענה נכונה.

הוכחה: נניח בשלילה שהטענה מוטעית, ואכן $\displaystyle f(n)=\Theta (g(n))$. עפ"י ההגדרה, לכן, קיימים שני קבועים $\displaystyle c''>0$ ו$\displaystyle c'>0$ כך שלערכי $\displaystyle n$ גדולים מספיק, $\displaystyle c''\cdot g(n)\leq f(n)\leq c'\cdot g(n)$. נחלק ב$\displaystyle g(n)$ (שימו לב שאין צורך להפוך את סימני $\displaystyle \leq$), ונקבל $\displaystyle c''\leq f(n)/g(n)\leq 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)\neq \Omega (g(n))$. אם $\displaystyle c=\infty$ אז $\displaystyle f(n)\neq 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. ראשית נקבע צמדים של נקודות.
   1. נקבע $\displaystyle n_{0}=1$,‏ ו$\displaystyle n_{1}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{1})\geq 2\cdot f(n_{0})$ ‏(חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏‏.
   2. נקבע $\displaystyle n_{2}=n_{1}+1$,‏ ו$\displaystyle n_{3}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{3})\geq 2\cdot f(n_{2})$ (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏.
   3. נמשיך כך הלאה: נקבע $\displaystyle n_{4}=n_{3}+1$,‏ ו$\displaystyle n_{5}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{5})\geq 2\cdot f(n_{4}$) (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏, וכולי.
2. כעת נגדיר את $\displaystyle g(n)$ בעזרת הזוגות:
   1. עבור $\displaystyle n_{0}\leq n<n_{1}$,‏ $\displaystyle g(n)=f(n_{0})$;‏ $\displaystyle g(n_{1})=f(n_{1})/2$.
   2. עבור $\displaystyle n_{2}\leq n<n_{3}$,‏ $\displaystyle g(n)=f(n_{2})$;‏ $\displaystyle g(n_{3})=f(n_{3})/2$.
   3. עבור $\displaystyle n_{4}\leq 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^{k}dx=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)]\leq \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)]\geq \sum _{i=1}^{n/4}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \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)\geq \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)]\geq [2^{-1}\Theta (1)]\geq \Theta (1)$ ולכן הטור המקורי הוא $\displaystyle \Omega (1)$.

מצד שני, נקבל $\displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\leq \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]\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)$

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