1 - סיבוכיות (מההקלטה) — מבני נתונים 1

קצת על המבנה של הקורס:

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

ההגדרות הבסיסיות

הגדרה 1 (חסם עליון)

יהיו $f(n),g(n):\mathbb{N}\to \mathbb{R}^+$ .
נאמר כי $f(n)={\Large O(}g(n){\Large)}$ אם קיימים $c,n_{0} \in \mathbb{R}^+$ כך שלכל $n\geq n_{0}$ מתקיים: $f(n)\leq c\cdot g(n)$ .

הגדרה 2 (חסם תחתון)

יהיו $f(n),g(n):\mathbb{N}\to \mathbb{R}^+$ .
נאמר כי $f(n)={\Large\Omega(}g(n){\Large)}$ אם קיימים $c,n_{0}\in \mathbb{R}^+$ כך שלכל $n\geq n_{0}$ מתקיים $f(n)\geq c\cdot g(n)$ .

הגדרה 3 (חסם הדוק)

יהיו $f(n),g(n):\mathbb{N}\to \mathbb{R}^+$ .
נאמר כי $f(n)={\Large\Theta(}g(n){\Large)}$ אם $f(n)=\Omega(g(n))\land f(n)=O(g(n))$ .

דוגמה

יהי $p(n)\in \mathbb{N}_{k}[n]$ שמקדמיו חיוביים. כלומר:

p(n)=a_{0}+a_{1}n+\dots+a_{k}n^k=\sum_{i=0}^k a_{i}n^i \qquad \qquad a_{i}\geq 0, a_{k}>0

נרצה להראות כי $p(n)=O(n^k)$ . עבור כך נרצה למצוא קבועים $c,n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים $p(n)\leq c\cdot n^k$ .
נשים לב כי לכל $0\leq i\leq k$ ולכל $n\geq 1$ מתקיים $n^i\leq n^k$ ולכן נקבל כי:

p(n)=\sum_{i=0}^k a_{i}n^i\leq \sum_{i=0}^ka_{i}n^k=\left( \sum_{i=0}^ka_{i} \right)n^k

ולכן, עבור $n_{0}=1,c=\sum\limits_{i=0}^ka_{i}$ מתקיים כי $p(n)\leq c\cdot n^k$ ולכן $p(n)=O(n^k)$ .

כעת, נרצה להראות כי $p(n)=\Omega(n^k)$ . נשים לב כי לכל $n\geq 1$ מתקיים כי:

\sum_{i=0}^k a_{i}n^i=a_{0}+a_{1}n+\dots+a_{k}n^k\geq a_{k}n^k

ולכן, עבור $n_{0}=1,c=a_{k}$ נקבל כי $p(n)\geq c\cdot n^k$ ובכך $p(n)=\Omega(n^k)$ .

מסקנה

לפי הגדרה מתקיים כי $p(n)=\Theta(n^k)$ .

תרגיל

הראו כי לכל קבוע $k\geq 2$ מתקיים:

\sum_{i=0}^nk^i = 1+k+\dots+k^n=O(k^n)

נשתמש בסכום סדרה הנדסית:

\sum_{i=0}^n k^i=\frac{k^{n+1}-1}{k-1}\leq \frac{k^{n+1}}{k-1}

מכיוון ש- $k\geq 2$ מתקיים כי $k-1\geq \frac{1}{2}k$ ולכן:

\sum_{i=0}^n k^i\leq \frac{k^{n+1}}{\frac{1}{2}k}=2k^n

ולכן, לפי הגדרה $\sum_{i=0}^nk^i=O(k^n)$ .

תרגיל

הוכיחו כי $\log (n!)=\Theta(n\log n)$ .

הוכחה:
נראה כי $\log(n!)=O(n\log n)$ תחילה. לפי הגדרה נקבל:

\log(n!)=\log(1\cdot2\cdots n)=\log1+\log 2+\dots +\log n \underset{\begin{matrix} \downarrow \\ \R{\text{ היא פונקציה מונוטונית}} \log n \end{matrix}}{\leq}n\log n

לכן, עבור $c=1,n_{0}=1$ נקבל כי $\log n! = O(n\log n)$ .

כעת, נראה כי $\log(n!)=\Omega(n\log n)$ .

\begin{align*} \log (n!)&=\log1+\log2+\dots+\log \frac{n}{2}+\dots+\log n\geq \log \frac{n}{2}+\dots+\log n\geq \frac{n}{2}\log \frac{n}{2} \\ &=\frac{n}{2}(\log n-\log 2)=\frac{n}{2}\log n -\frac{n}{2} \end{align*}

הערה (טריק שיחזור בכמה מקומות)

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

\log(n!)\geq \frac{n}{2}\log n-\frac{n}{2}= \frac{n}{4}\log n+\frac{n}{4}(\log n-2)\geq \frac{n}{4}\log n

נשים לב כי השלב האחרון מתקיים רק עבור $n\geq4$ שכן $\log n-2\geq 0$ עבור $n\geq 4$ .

הערה

הלוג ה"רגיל" במדעי המחשב הוא $\log_{2}$ ולכן כל ה- $\log$ -ים פה היו $\log_{2}$ בסתר.

לכן מתקיים כי $\log(n!)=\Omega(n\log n)$ עם $c=\frac{1}{4},n_{0}=4$ בהגדרה.
לכן, לפי הגדרה $\log(n!)=\Theta(n\log n)$ .
∎

משפטים על החסמים

משפט

יהיו $f_{1},f_{2},g_{1},g_{2}:\mathbb{N}\to \mathbb{R}$ כך ש: $f_{1}(n)=O(g_{1}(n))$ ו- $f_{2}(n)=O(g_{2}(n))$ . אזי:

מתקיים $f_{1}(n)+f_{2}(n)=O(g_{1}(n)+g_{2}(n))$ .
מתקיים $f_{1}(n)+f_{2}(n)=O(\max\left\{ g_{1}(n),g_{2}(n) \right\})$
מתקיים $f_{1}(n)\cdot f_{2}(n)=O(g_{1}(n)\cdot g_{2}(n))$ .

הוכחה:
קיימים קבועים $c_{1},n_{01}>0$ כך שלכל $n\geq n_{01}$ מתקיים $f_{1}(n)\leq c_{1}g_{1}(n)$ וקיימים קבועים $c_{2},n_{02}>0$ כך שלכל $f_{2}(n)\leq c_{2}g_{2}(n)$ .
לכן:

f_{1}(n)+f_{2}(n)\leq c_{1}g_{1}(n)+c_{2}g_{2}(n)\leq(c_{1}+c_{2})g_{1}(n)+(c_{1}+c_{2})g_{2}(n)=(c_{1}+c_{2})(g_{1}(n)+g_{2}(n))

ולכן, עבור $c=c_{1}+c_{2},n_{0}=\max\left\{ n_{01},n_{02} \right\}$ מתקיים לפי הגדרה כי $f_{1}(n)+f_{2}(n)=O(g_{1}(n)+g_{2}(n))$ .
באותו האופן נקבל גם כי:

f_{1}(n)+f_{2}(n)\leq (c_{1}+c_{2})(g_{1}(n)+g_{2}(n))\leq(c_{1}+c_{2})\cdot 2\max\left\{ g_{1}(n),g_{2}(n) \right\}

ולכן, עבור $c=2(c_{1}+c_{2}),n_{0}=\max\left\{ n_{01},n_{02} \right\}$ מתקיים לפי הגדרה כי $f_{1}(n)+f_{2}(n)=O(\max\left\{ g_{1}(n),g_{2}(n) \right\})$ .
לבסוף, נקבל גם כי:

f_{1}(n)\cdot f_{2}(n)\leq c_{1}\cdot g_{1}(n)\cdot c_{2}\cdot g_{2}(n)= (c_{1}\cdot c_{2})(g_{1}(n)\cdot g_{2}(n))

ולכן, עבור $c=c_{1}c_{2},n_{0}=\max\left\{ n_{01},n_{02} \right\}$ מתקיים לפי הגדרה כי $f_{1}(n)\cdot f_{2}(n)=O(g_{1}(n)\cdot g_{2}(n))$ .
∎

תרגיל

האם מתקיים כי $f_{1}(n)^{f_{2}(n)}=O(g_{1}(n)^{g_{2}(n)})$ ?

התשובה היא לא

הערה

בשאלות מסוג אלו תמיד כדאי לנסות להפריך קודם.

נסתכל למשל על הפונקציות $f_{1}(n)=g_{1}(n)=n$ ו- $f_{2}(n)=2,g_{2}(n)=1$ .
הטענה $n^2=O(n)$ אינה נכונה ונראה זאת באמצעות הנחה בשלילה.
נניח בשלילה כי קיימים $c,n_{0}>0$ עבורם לכל $n\geq n_{0}$ מתקיים $n^2\leq c\cdot n$ נחלק ב- $n$ שכן $n\neq 0$ ונקבל כי:

n\leq c

מה שאינו נכון אם נקח $n=\max\left\{ n_{0},c+1 \right\}$ ולכן הגענו לסתירה ומתקיים כי $n^2\neq O(n)$ .

חישוב זמן ריצה של תוכנית

scanf("%d", &n);
int k = 2;

while (k < n)
{
	k += 1;
}

הפקודות מחוץ ללולאה הינן $O(1)$ ועלות איטרציה יחידה היא $O(1)$ .
מספר האינטרציות הוא $n-2$ ולכן סך זמן הריצה של התוכנית הוא $O(n)$ .

\begin{array}{c|c} \R{\text{ בסוף האיטרציה}}k & \R{\text{מספר האיטרציה}} \\ \hline 2 & 0 \\ 3 & 1 \\ 4 & 2 \\ \vdots & \vdots \\ i+2 & i \\ \vdots & \vdots \\ n & n-2 \\ \hline \end{array}

scanf("%d", &n);
int k = 2;

while (k < n)
{
	k = k * 2;
}

כעת, מכיוון שאנחנו משנים את $k$ בתוך הלולאה יהיה לנו זמן ריצה שונה מהדוגמה הקודמת. האיטרציה האחרונה תקרה כאשר:

2^i\cdot 2\geq n \implies i+1\geq \log_{2}n\implies i\geq \log_{2}n-1

לכן, סך זמן הריצה של התוכנית הוא $O(\log n)$ .

scanf("%d", &n);
int k = 2;

while (k < n)
{
	k = k * k * k;
}

בתוכנית זו אנחנו משנים את $k$ באופן דרסטי ובעצם עושים $k=k^3$ ולכן האיטרציה אחרונה תתרחש כאשר $2^{3^i}\geq n$ ולכן:

3^i\geq \log n \implies i\geq \log_{3}(\log_{2}n)

ולכן סך זמן הריצה הוא $O(\log \log n)$ .

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

הגדרה 4

נאמר כי $f(n)=o(g(n))$ אם לכל $c>0$ קיים $n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים $f(n)\leq c\cdot g(n)$ .

משפט (הגדרה שקולה)

נאמר ש- $f(n)=o(g(n))$ אם ורק אם $\lim_{ n \to \infty } \frac{f(n)}{g(n)}=0$ .

הגדרה 5

נאמר ש- $f(n)=\omega(g(n))$ אם לכל $c>0$ קיים $n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים $f(n)\geq c\cdot g(n)$ .

משפט (הגדרה שקולה)

\lim_{ n \to \infty } \frac{g(n)}{f(n)}=0 \iff f(n)=\omega(g(n))

טענה

לכל קבוע $\epsilon>0$ מתקיים כי $\log n=o(n^\epsilon)$ .

הוכחה:
נוכיח את הטענה לפי ההגדרה השקולה של $o$ . כלומר, נראה כי $\lim_{ n \to \infty } \frac{\log n}{n^\epsilon}=0$ .
לפי כלל לופיטל נקבל כי:

\lim_{ n \to \infty } \frac{\log n}{n^\epsilon}=\lim_{ n \to \infty } \frac{\frac{1}{\ln2} \frac{1}{n}}{\epsilon\cdot n^{\epsilon-1}}=\lim_{ n \to \infty } \frac{1}{\epsilon \ln2} \frac{1}{n^\epsilon}=0

∎

תרגיל

נתונות פונקציות $f,g:\mathbb{N}\to \mathbb{R}^+$ .
נגדיר $f(n)=S(g(n))$ אם מתקיים $f(n)=O\left( \sum_{i=1}^n g(i)\right)$ .

הוכח/הפרך:
א. $n^2=S(n)$ .
ב. $n=S(\log n)$
ג. $f(n)=S(g(n))$ וגם $g(n)=S(h(n))$ אז $f(n)=S(h(n))$ .

פתרון א':
הטענה נכונה.

הערה (אינטואיציה)

אם אנחנו לוקחים את הסכום זה סכום של סדרה חשבונית וכבר ראינו שסכום של פונקציות זה $O(\R{\text{הפונקציה המקסימלית}})$

הוכחה:
נרצה להראות כי $n^2=O\left( \sum_{i=1}^n i \right)$ , כלומר, נרצה להראות כי קיימים קבועים $c,n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים:

n^2\leq c \sum_{i=1}^n i=c \frac{n(n+1)}{2}=\frac{1}{2}c (n^2+n)

אם נבחר $c=2$ נקבל $n^2\leq n^2+n$ וברור כי זה מתקיים לכל $n \in \mathbb{N}^+$ .
∎

פתרון ב':
הטענה גם כן נכונה.
הוכחה:
נרצה להראות כי $n=O\left( \sum_{i=1}^n \log i \right)$ . כלומר, שקיימים קבועים $c,n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים:

n\leq c\sum_{i=1}^n \log i=c\log(n!)

נזכר כי ראינו ממקודם כי $\log(n!)=\Theta(n\log n)$ ולכן, מתקיים $\log(n!)=\Omega(n\log n)$ . כלומר, קיימים קבועים $c',n_{0}'>0$ כך שלכל $n\geq n_{0}'$ מתקיים:

\log (n!)\geq c'\cdot n\log n\implies \frac{1}{c'}\log(n!)\geq n\log n

נשים לב כי לכל $n\geq 2$ מתקיים $n\log n\geq n$ ולכן לכל $n\geq n_{0}=\max\left\{ 2,n_{0}' \right\}$ מתקיים $n\leq c\cdot \log(n!)$ כאשר $c=\frac{1}{c'}$ .
∎

פתרון ג':
הטענה אינה נכונה.
נראה דוגמה נגדית באמצעות הפונקציות $f(n)=n^2,g(n)=n,h(n)=\log n$ .
בסעיפים א' ו-ב' ראינו כי $n^2=S(n)$ וכי $n=S(\log n)$ אולם הטענה $n^2=S(\log n)$ אינה נכונה.
נניח בשלילה כי $n^22=S(\log n)$ , כלומר, קיימים קבועים $c,n_{0}>0$ כך ש- $n^2\leq c\sum_{i=1}^n\log i=c\log(n!)$ .
ראינו בתחילת התרגול כי $\log(n!)=\Theta(n\log n)$ ולכן בפרט $\log (n!)=O(n\log n)$ . כלומר, קיימים קבועים $c',n_{0}'>0$ כך שלכל $n\geq n_{0}'$ מתקיים $\log(n!)\leq c'\cdot n\log n$ .
לכן, לכל $n\geq \max\left\{ n_{0},n_{0}' \right\}$ מתקיים:

n^2\leq c\cdot c'\cdot n\log n\implies n\leq c\cdot c'\cdot \log n

בסתירה לכך ש- $\log n=o(n)$ .

קצת על המבנה של הקורס:

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

ההגדרות הבסיסיות

הגדרה 1 (חסם עליון)

הגדרה 2 (חסם תחתון)

הגדרה 3 (חסם הדוק)

יהיו $f(n),g(n):\mathbb{N}\to \mathbb{R}^+$ .
נאמר כי $f(n)={\Large\Theta(}g(n){\Large)}$ אם $f(n)=\Omega(g(n))\land f(n)=O(g(n))$ .

דוגמה

יהי $p(n)\in \mathbb{N}_{k}[n]$ שמקדמיו חיוביים. כלומר:

p(n)=a_{0}+a_{1}n+\dots+a_{k}n^k=\sum_{i=0}^k a_{i}n^i \qquad \qquad a_{i}\geq 0, a_{k}>0

p(n)=\sum_{i=0}^k a_{i}n^i\leq \sum_{i=0}^ka_{i}n^k=\left( \sum_{i=0}^ka_{i} \right)n^k

ולכן, עבור $n_{0}=1,c=\sum\limits_{i=0}^ka_{i}$ מתקיים כי $p(n)\leq c\cdot n^k$ ולכן $p(n)=O(n^k)$ .

כעת, נרצה להראות כי $p(n)=\Omega(n^k)$ . נשים לב כי לכל $n\geq 1$ מתקיים כי:

\sum_{i=0}^k a_{i}n^i=a_{0}+a_{1}n+\dots+a_{k}n^k\geq a_{k}n^k

ולכן, עבור $n_{0}=1,c=a_{k}$ נקבל כי $p(n)\geq c\cdot n^k$ ובכך $p(n)=\Omega(n^k)$ .

מסקנה

לפי הגדרה מתקיים כי $p(n)=\Theta(n^k)$ .

תרגיל

הראו כי לכל קבוע $k\geq 2$ מתקיים:

\sum_{i=0}^nk^i = 1+k+\dots+k^n=O(k^n)

נשתמש בסכום סדרה הנדסית:

\sum_{i=0}^n k^i=\frac{k^{n+1}-1}{k-1}\leq \frac{k^{n+1}}{k-1}

מכיוון ש- $k\geq 2$ מתקיים כי $k-1\geq \frac{1}{2}k$ ולכן:

\sum_{i=0}^n k^i\leq \frac{k^{n+1}}{\frac{1}{2}k}=2k^n

ולכן, לפי הגדרה $\sum_{i=0}^nk^i=O(k^n)$ .

תרגיל

הוכיחו כי $\log (n!)=\Theta(n\log n)$ .

הוכחה:
נראה כי $\log(n!)=O(n\log n)$ תחילה. לפי הגדרה נקבל:

\log(n!)=\log(1\cdot2\cdots n)=\log1+\log 2+\dots +\log n \underset{\begin{matrix} \downarrow \\ \R{\text{ היא פונקציה מונוטונית}} \log n \end{matrix}}{\leq}n\log n

לכן, עבור $c=1,n_{0}=1$ נקבל כי $\log n! = O(n\log n)$ .

כעת, נראה כי $\log(n!)=\Omega(n\log n)$ .

\begin{align*} \log (n!)&=\log1+\log2+\dots+\log \frac{n}{2}+\dots+\log n\geq \log \frac{n}{2}+\dots+\log n\geq \frac{n}{2}\log \frac{n}{2} \\ &=\frac{n}{2}(\log n-\log 2)=\frac{n}{2}\log n -\frac{n}{2} \end{align*}

הערה (טריק שיחזור בכמה מקומות)

\log(n!)\geq \frac{n}{2}\log n-\frac{n}{2}= \frac{n}{4}\log n+\frac{n}{4}(\log n-2)\geq \frac{n}{4}\log n

נשים לב כי השלב האחרון מתקיים רק עבור $n\geq4$ שכן $\log n-2\geq 0$ עבור $n\geq 4$ .

הערה

הלוג ה"רגיל" במדעי המחשב הוא $\log_{2}$ ולכן כל ה- $\log$ -ים פה היו $\log_{2}$ בסתר.

לכן מתקיים כי $\log(n!)=\Omega(n\log n)$ עם $c=\frac{1}{4},n_{0}=4$ בהגדרה.
לכן, לפי הגדרה $\log(n!)=\Theta(n\log n)$ .
∎

משפטים על החסמים

משפט

יהיו $f_{1},f_{2},g_{1},g_{2}:\mathbb{N}\to \mathbb{R}$ כך ש: $f_{1}(n)=O(g_{1}(n))$ ו- $f_{2}(n)=O(g_{2}(n))$ . אזי:

מתקיים $f_{1}(n)+f_{2}(n)=O(g_{1}(n)+g_{2}(n))$ .
מתקיים $f_{1}(n)+f_{2}(n)=O(\max\left\{ g_{1}(n),g_{2}(n) \right\})$
מתקיים $f_{1}(n)\cdot f_{2}(n)=O(g_{1}(n)\cdot g_{2}(n))$ .

f_{1}(n)+f_{2}(n)\leq c_{1}g_{1}(n)+c_{2}g_{2}(n)\leq(c_{1}+c_{2})g_{1}(n)+(c_{1}+c_{2})g_{2}(n)=(c_{1}+c_{2})(g_{1}(n)+g_{2}(n))

ולכן, עבור $c=c_{1}+c_{2},n_{0}=\max\left\{ n_{01},n_{02} \right\}$ מתקיים לפי הגדרה כי $f_{1}(n)+f_{2}(n)=O(g_{1}(n)+g_{2}(n))$ .
באותו האופן נקבל גם כי:

f_{1}(n)+f_{2}(n)\leq (c_{1}+c_{2})(g_{1}(n)+g_{2}(n))\leq(c_{1}+c_{2})\cdot 2\max\left\{ g_{1}(n),g_{2}(n) \right\}

f_{1}(n)\cdot f_{2}(n)\leq c_{1}\cdot g_{1}(n)\cdot c_{2}\cdot g_{2}(n)= (c_{1}\cdot c_{2})(g_{1}(n)\cdot g_{2}(n))

ולכן, עבור $c=c_{1}c_{2},n_{0}=\max\left\{ n_{01},n_{02} \right\}$ מתקיים לפי הגדרה כי $f_{1}(n)\cdot f_{2}(n)=O(g_{1}(n)\cdot g_{2}(n))$ .
∎

תרגיל

האם מתקיים כי $f_{1}(n)^{f_{2}(n)}=O(g_{1}(n)^{g_{2}(n)})$ ?

התשובה היא לא

הערה

בשאלות מסוג אלו תמיד כדאי לנסות להפריך קודם.

n\leq c

מה שאינו נכון אם נקח $n=\max\left\{ n_{0},c+1 \right\}$ ולכן הגענו לסתירה ומתקיים כי $n^2\neq O(n)$ .

חישוב זמן ריצה של תוכנית

scanf("%d", &n);
int k = 2;

while (k < n)
{
	k += 1;
}

\begin{array}{c|c} \R{\text{ בסוף האיטרציה}}k & \R{\text{מספר האיטרציה}} \\ \hline 2 & 0 \\ 3 & 1 \\ 4 & 2 \\ \vdots & \vdots \\ i+2 & i \\ \vdots & \vdots \\ n & n-2 \\ \hline \end{array}

scanf("%d", &n);
int k = 2;

while (k < n)
{
	k = k * 2;
}

כעת, מכיוון שאנחנו משנים את $k$ בתוך הלולאה יהיה לנו זמן ריצה שונה מהדוגמה הקודמת. האיטרציה האחרונה תקרה כאשר:

2^i\cdot 2\geq n \implies i+1\geq \log_{2}n\implies i\geq \log_{2}n-1

לכן, סך זמן הריצה של התוכנית הוא $O(\log n)$ .

scanf("%d", &n);
int k = 2;

while (k < n)
{
	k = k * k * k;
}

בתוכנית זו אנחנו משנים את $k$ באופן דרסטי ובעצם עושים $k=k^3$ ולכן האיטרציה אחרונה תתרחש כאשר $2^{3^i}\geq n$ ולכן:

3^i\geq \log n \implies i\geq \log_{3}(\log_{2}n)

ולכן סך זמן הריצה הוא $O(\log \log n)$ .

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

הגדרה 4

נאמר כי $f(n)=o(g(n))$ אם לכל $c>0$ קיים $n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים $f(n)\leq c\cdot g(n)$ .

משפט (הגדרה שקולה)

נאמר ש- $f(n)=o(g(n))$ אם ורק אם $\lim_{ n \to \infty } \frac{f(n)}{g(n)}=0$ .

הגדרה 5

נאמר ש- $f(n)=\omega(g(n))$ אם לכל $c>0$ קיים $n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים $f(n)\geq c\cdot g(n)$ .

משפט (הגדרה שקולה)

\lim_{ n \to \infty } \frac{g(n)}{f(n)}=0 \iff f(n)=\omega(g(n))

טענה

לכל קבוע $\epsilon>0$ מתקיים כי $\log n=o(n^\epsilon)$ .

\lim_{ n \to \infty } \frac{\log n}{n^\epsilon}=\lim_{ n \to \infty } \frac{\frac{1}{\ln2} \frac{1}{n}}{\epsilon\cdot n^{\epsilon-1}}=\lim_{ n \to \infty } \frac{1}{\epsilon \ln2} \frac{1}{n^\epsilon}=0

∎

תרגיל

נתונות פונקציות $f,g:\mathbb{N}\to \mathbb{R}^+$ .
נגדיר $f(n)=S(g(n))$ אם מתקיים $f(n)=O\left( \sum_{i=1}^n g(i)\right)$ .

הוכח/הפרך:
א. $n^2=S(n)$ .
ב. $n=S(\log n)$
ג. $f(n)=S(g(n))$ וגם $g(n)=S(h(n))$ אז $f(n)=S(h(n))$ .

פתרון א':
הטענה נכונה.

הערה (אינטואיציה)

אם אנחנו לוקחים את הסכום זה סכום של סדרה חשבונית וכבר ראינו שסכום של פונקציות זה $O(\R{\text{הפונקציה המקסימלית}})$

n^2\leq c \sum_{i=1}^n i=c \frac{n(n+1)}{2}=\frac{1}{2}c (n^2+n)

אם נבחר $c=2$ נקבל $n^2\leq n^2+n$ וברור כי זה מתקיים לכל $n \in \mathbb{N}^+$ .
∎

n\leq c\sum_{i=1}^n \log i=c\log(n!)

\log (n!)\geq c'\cdot n\log n\implies \frac{1}{c'}\log(n!)\geq n\log n

נשים לב כי לכל $n\geq 2$ מתקיים $n\log n\geq n$ ולכן לכל $n\geq n_{0}=\max\left\{ 2,n_{0}' \right\}$ מתקיים $n\leq c\cdot \log(n!)$ כאשר $c=\frac{1}{c'}$ .
∎

n^2\leq c\cdot c'\cdot n\log n\implies n\leq c\cdot c'\cdot \log n

בסתירה לכך ש- $\log n=o(n)$ .