הגדרה 1 (זמן ריצה של אלגוריתם)

יהי אלגוריתם $A$ וקלט $x$ . נאמר כי זמן הריצה של $A$ על $x$ הוא מספר פקודות המכונה שהאלגוריתם מבצע על הקלט $x$ . נסמנו ב- $time_{\small A}(x)$ .

הערה

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

הגדרה (סימון)

האורך של הקלט $x$ יסומן כמובן ב- $|x|$ .

דוגמה

בתוכנית המסכמת איברי מערך $x$ , אורך הקלט הוא מספר איברי המערך.

הגדרה 2 (זמן הריצה במקרה הגרוע)

יהי אלגוריתם $A$ ויהי $n \in \mathbb{R}^+ \cup \left\{ 0 \right\}$ .
נאמר כי זמן הריצה הגרוע ביותר של $A$ עבור קלט שגודלו $n$ מוגדר ע"י:

t_{\tiny A}(n)=\max\left\{ time_{\tiny A}(x) \mid |x|=n\right\}

דוגמה

עבור קלט שהוא מערך $a$ בגודל $n$ נסכם את איברי המערך:

sum = 0;
for (i = 0; i < n; i++)
	sum = sum + a[i];

זמן הריצה הגרוע ביותר של אלגוריתם זה מקיים:

n+1\leq t_{\small A}(n)\leq c_{1}\cdot n +c_{2}

כאשר $c_{1}$ הוא מספר הפעולות בכל איטרציה של הלולאה ו- $c_{2}$ הוא מספר הפעולות מחוץ ללולאה.

דוגמה

נבדוק האם מספר מסויים $num$ הוא ראשוני ע"י חלוקה בכל האיברים עד אליו:

for (i = 2; i < num; i++)
	if (num % i == 0) return false;
return true;

למספר זוגי תתבצע איטרציה אחת בלבד ולכן $time(9998)=c_{1}+c_{2}$ .
עבור מספר ראשוני יהיו מלאאא איטרציות $time(9973)=9971\cdot c_{1}+c_{2}$ .
⟸ זמן הריצה הגרוע ביותר לקלט באורך $4$ ספרות יהיה $t(4)=9971\cdot c_{1}+c_{2}$ .
⟸ באופן כללי יותר לקלט באורך $n$ ספרות מתקיים $t(n)<10^nc_{1}+c_{2}$ .

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

הגדרה 3 (הקבוצה

O

)

יהיו $f,g:\mathbb{N}\to \mathbb{R}^+$ .
נאמר שהפונקציה $f(n)$ נמצאת בקבוצת הפונקציות $\textbf{O(g(n))}$ אם קיימים קבועים $c,n_{0}>0$ כך שלכל $n\geq n_{0}$ מתקיים: $f(n)\leq c\cdot g(n)$ .
כמו כן, נאמר ש- $g(n)$ מהווה חסם עליון אסימפטוטי לפונקציה $f(n)$ ונסמן זאת ע"י $f(n)=O(g(n))$ . (במקום הסימון הקבוצתי $f(n)\in O(g(n))$ )

דוגמה (מעבר בסיס בלוגריתמים)

לכל $a,b>1$ קבועים מתקיים: $f(n)=\log _an=O(\log_{b}n)$ משום ש:

\log_{a}n=\log_{a}b\cdot \log_{b}n

ומכיוון ש- $c=\log_{a}b$ הוא קבוע שאינו תלוי ב- $n$ נקבל ישירות כי $\log_{a}n\leq c\cdot \log_{b}n$ לכל $n \in \mathbb{N}$ .

טענה

לכל $k \in \mathbb{N}$ מתקיים:

f(n)=a_{0}a_{1}n+a_{2}n^2+\dots+a_{k}n^k=O(n^k)

הוכחה:
יהי $a_{\max}=\max\left\{ 1,a_{0},\dots,a_{k} \right\}$ אזי:

f(n)\leq a_{\max}(1+n+n^2+\dots+n^k)=\frac{a_{\max}\cdot(n^{k+1}-1)}{n-1}\underset{\begin{matrix} \downarrow \\ n\geq 2\R{\text{נכון לכל:}} \end{matrix}}{\leq} \frac{a_{\max}n^{k+1}}{\frac{n}{2}}=2a_{\max}n^k

לפיכך נבחר $n_{0}=2$ ו- $c=2a_{\max}$ ואז לפי הגדרה $f(n)=O(n^k)$ .
∎

דוגמה

נאמר כי לכל $\epsilon>0$ חיובי מתקיים: $f(n)=\log_{a}n=O(n^\epsilon)$ וזאת כך:

\log_{a}n \underset{\begin{matrix} \downarrow \\ \R{\text{חוקי לוגריתמים}} \end{matrix}}{=}\frac{1}{\epsilon \log_{2}a}\log_{2}(n^\epsilon)\underset{\begin{matrix} \downarrow \\ \log_{2}n<n \end{matrix}}{\leq} c\cdot n^\epsilon

הערה

כל פונקציה לוגריתמית גדלה לאט יותר מכל חזקה חיובית של $n$ . (אפילו $n^{0.00000000001}$ )

דוגמה

f(n)=n^k+a^n=O(a^n) \qquad \qquad \qquad \qquad \quad f(n)=a^n=O(b^n), \quad a<b

n^k+a^n=a^{k\log_{a}n}+a^n<c\cdot a^n \qquad \qquad \qquad \quad \forall n \in \mathbb{N}, a\leq b:\; a^n\leq b^n

דוגמה

נראה כעת למה $3^n\neq O(2^n)$ :
נניח בשלילה שקיימים קבועים $n_{0},c>0$ כך שלכל $n\geq n_{0}$ מתקיים: $3^n\leq c\cdot 2^n$ .
נחלק ב- $2^n$ ונקבל: $\left( \frac{3}{2} \right)^n\leq c$ ונוציא לוגריתם בבסיס $\frac{3}{2}$ משני האגפים: $n\leq \log_{\frac{3}{2}}c$ .
סתירה לכך שלכל $n> \log_{\frac{3}{2}}c$ אי השוויון לא נכון. לכן, $3^n\neq O(2^n)$ .

דוגמה

האם $f(n)=e^n=O(n^k)$ עבור $k$ קבוע? לא, בכלל לא.
על מנת להוכיח זאת נחשב את הגבול:

\lim_{ x \to \infty } \frac{x^k}{e^x}=\lim_{ x \to \infty } \frac{kx^{k-1}}{e^x}=\dots=\lim_{ x \to \infty } \frac{k!}{e^x}=0

נקבל אם כן את השלבים הבאים:

\forall \epsilon \in \mathbb{R}^+, \exists x_{0}, \forall x>x_{0}:\; \left| \frac{x^k}{e^x} \right|<\epsilon \implies \forall \epsilon \in \mathbb{R}^+,\exists x_{0},\forall x>x_{0}:\;x^k<\epsilon\cdot e^x

נעבור לשלילה ונחליף את $\epsilon$ ב- $c$ ואת $x$ ב- $n$ ואז נקבל כי:

\not \exists c,n_{0}, \forall n>n_{0}:\; e^n<c\cdot n^k

מסקנה

התשובה שלילית. $e^n$ אינו חסום ע"י שום פולינום $n^k$ . כלומר $e^n\neq O(n^k)$ .

מסקנה (היררכית קצב הגידול של משפחות הפונקציות)

1 \quad \log(\log n) \qquad \log n \qquad \dots \qquad n \qquad n\log n \qquad n^2 \qquad \dots \qquad 2^n

סיבוכיות זמן

דוגמה (כפל מטריצות בגודל

m\times m

)

גודל הקלט שלנו הוא: $n=2m^2$ .
מחשבים $m^2$ איברים במטריצת התוצאה, כאשר כל איבר מחושב לפי ההגדרה:

C_{i,j}=\sum_{k=1}^m A_{i,k}B_{k,j}

סיבוכיות הזמן כפונקציה של $m$ היא $T(m)=O\left( m^3 \right)$ (ביצוע של $m$ פעולות כפל וחיבור עבור כל אחת מה- $m^2$ איברים)

m=\sqrt{ \frac{n}{2} }\implies T(n)=O(m^3)=O\left( \frac{n^{\frac{3}{2}}}{2^{\frac{3}{2}}} \right)=O(n^{\frac{3}{2}})

דוגמה (חיפוש בינארי)

חיפוש בינארי המוכר יהיה בעל סיבוכיות זמן $T$ המוגדרת בעזרת נוסחת הנסיגה הבאה:

T(n)=c+T\left( \frac{n}{2} \right)

כאשר $T(1)=c$ . נאמר אם כן כי:

T(n)=c+c+T\left( \frac{n}{4} \right)=\overbrace{c+\dots+c}^i+T\left( \frac{n}{2^i} \right)=c\log_{2}n+T(1)=O(\log n)

דוגמה

עבור פיסת הקוד:

S = 0;
for (i = 1; i < n; i++)
	for (j = 0; j < n; j += i)
		S++;

באנליזה גסה היינו אומרים כי $T(n)\leq O(n^2)$ .
באנליזה עדינה יותר היינו מגלים כי:

עבור $i=1$ מתבצעות $n$ פעולות.
עבור $i=2$ מתבצעות $\frac{n}{2}$ פעולות.
עבור $i=k$ מתבצעות $\frac{n}{k}$ פעולות.
עד $i=n$ עבורו מתבצעות $\frac{n}{n}$ פעולות.

סה"כ פעולות:

T(n)\leq n+\frac{n}{2}+\frac{n}{3}+\dots+\frac{n}{n}=n\left( 1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n} \right)=nH_{n}

כאשר $H_{n}$ נקרא המספר ההרמוני ה- $n$ .

טענה (חסם אינטגרלי לסכום ההרמוני)

\ln(n+1)=\int_{1}^{n+1} \frac{1}{x}dx\leq 1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}\leq 1+\int_{1}^n \frac{1}{x}dx=1+\ln(n)

מהטענה הנ"ל נקבל כי $T(n)\leq nH_{n}\leq n(1+\ln n)\leq n\cdot 2\ln n=2n\ln n=O(n\log n)$ .

הערה (חשובה מאוד)

ניתוח אסימפטוטי מתאר התנהגות עבור קלטים גדולים מאוד ( $n\to \infty$ )
עבור גדלי קטל קטנים ומעשיים, הקבועים הכפליים עשויים להכריע!

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

הגדרה 3 (הקבוצה

O

)

דוגמה (מעבר בסיס בלוגריתמים)

לכל $a,b>1$ קבועים מתקיים: $f(n)=\log _an=O(\log_{b}n)$ משום ש:

\log_{a}n=\log_{a}b\cdot \log_{b}n

ומכיוון ש- $c=\log_{a}b$ הוא קבוע שאינו תלוי ב- $n$ נקבל ישירות כי $\log_{a}n\leq c\cdot \log_{b}n$ לכל $n \in \mathbb{N}$ .

טענה

לכל $k \in \mathbb{N}$ מתקיים:

f(n)=a_{0}a_{1}n+a_{2}n^2+\dots+a_{k}n^k=O(n^k)

הוכחה:
יהי

a_{\max}=\max\left\{ 1,a_{0},\dots,a_{k} \right\}

אזי:

f(n)\leq a_{\max}(1+n+n^2+\dots+n^k)=\frac{a_{\max}\cdot(n^{k+1}-1)}{n-1}\underset{\begin{matrix} \downarrow \\ n\geq 2\R{\text{נכון לכל:}} \end{matrix}}{\leq} \frac{a_{\max}n^{k+1}}{\frac{n}{2}}=2a_{\max}n^k

לפיכך נבחר

n_{0}=2

ו-

c=2a_{\max}

ואז לפי הגדרה

f(n)=O(n^k)

.
∎

דוגמה

נאמר כי לכל $\epsilon>0$ חיובי מתקיים: $f(n)=\log_{a}n=O(n^\epsilon)$ וזאת כך:

\log_{a}n \underset{\begin{matrix} \downarrow \\ \R{\text{חוקי לוגריתמים}} \end{matrix}}{=}\frac{1}{\epsilon \log_{2}a}\log_{2}(n^\epsilon)\underset{\begin{matrix} \downarrow \\ \log_{2}n<n \end{matrix}}{\leq} c\cdot n^\epsilon

הערה

כל פונקציה לוגריתמית גדלה לאט יותר מכל חזקה חיובית של $n$ . (אפילו $n^{0.00000000001}$ )

דוגמה

f(n)=n^k+a^n=O(a^n) \qquad \qquad \qquad \qquad \quad f(n)=a^n=O(b^n), \quad a<b

n^k+a^n=a^{k\log_{a}n}+a^n<c\cdot a^n \qquad \qquad \qquad \quad \forall n \in \mathbb{N}, a\leq b:\; a^n\leq b^n

דוגמה

האם $f(n)=e^n=O(n^k)$ עבור $k$ קבוע? לא, בכלל לא.
על מנת להוכיח זאת נחשב את הגבול:

\lim_{ x \to \infty } \frac{x^k}{e^x}=\lim_{ x \to \infty } \frac{kx^{k-1}}{e^x}=\dots=\lim_{ x \to \infty } \frac{k!}{e^x}=0

נקבל אם כן את השלבים הבאים:

\forall \epsilon \in \mathbb{R}^+, \exists x_{0}, \forall x>x_{0}:\; \left| \frac{x^k}{e^x} \right|<\epsilon \implies \forall \epsilon \in \mathbb{R}^+,\exists x_{0},\forall x>x_{0}:\;x^k<\epsilon\cdot e^x

נעבור לשלילה ונחליף את $\epsilon$ ב- $c$ ואת $x$ ב- $n$ ואז נקבל כי:

\not \exists c,n_{0}, \forall n>n_{0}:\; e^n<c\cdot n^k

מסקנה

התשובה שלילית. $e^n$ אינו חסום ע"י שום פולינום $n^k$ . כלומר $e^n\neq O(n^k)$ .

מסקנה (היררכית קצב הגידול של משפחות הפונקציות)

1 \quad \log(\log n) \qquad \log n \qquad \dots \qquad n \qquad n\log n \qquad n^2 \qquad \dots \qquad 2^n

סיבוכיות זמן

דוגמה (כפל מטריצות בגודל

m\times m

)

גודל הקלט שלנו הוא: $n=2m^2$ .
מחשבים $m^2$ איברים במטריצת התוצאה, כאשר כל איבר מחושב לפי ההגדרה:

C_{i,j}=\sum_{k=1}^m A_{i,k}B_{k,j}

סיבוכיות הזמן כפונקציה של $m$ היא $T(m)=O\left( m^3 \right)$ (ביצוע של $m$ פעולות כפל וחיבור עבור כל אחת מה- $m^2$ איברים)

m=\sqrt{ \frac{n}{2} }\implies T(n)=O(m^3)=O\left( \frac{n^{\frac{3}{2}}}{2^{\frac{3}{2}}} \right)=O(n^{\frac{3}{2}})

דוגמה (חיפוש בינארי)

חיפוש בינארי המוכר יהיה בעל סיבוכיות זמן $T$ המוגדרת בעזרת נוסחת הנסיגה הבאה:

T(n)=c+T\left( \frac{n}{2} \right)

כאשר $T(1)=c$ . נאמר אם כן כי:

T(n)=c+c+T\left( \frac{n}{4} \right)=\overbrace{c+\dots+c}^i+T\left( \frac{n}{2^i} \right)=c\log_{2}n+T(1)=O(\log n)

דוגמה

עבור פיסת הקוד:

S = 0;
for (i = 1; i < n; i++)
	for (j = 0; j < n; j += i)
		S++;

באנליזה גסה היינו אומרים כי $T(n)\leq O(n^2)$ .
באנליזה עדינה יותר היינו מגלים כי:

עבור $i=1$ מתבצעות $n$ פעולות.
עבור $i=2$ מתבצעות $\frac{n}{2}$ פעולות.
עבור $i=k$ מתבצעות $\frac{n}{k}$ פעולות.
עד $i=n$ עבורו מתבצעות $\frac{n}{n}$ פעולות.

סה"כ פעולות:

T(n)\leq n+\frac{n}{2}+\frac{n}{3}+\dots+\frac{n}{n}=n\left( 1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n} \right)=nH_{n}

כאשר $H_{n}$ נקרא המספר ההרמוני ה- $n$ .

טענה (חסם אינטגרלי לסכום ההרמוני)

\ln(n+1)=\int_{1}^{n+1} \frac{1}{x}dx\leq 1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}\leq 1+\int_{1}^n \frac{1}{x}dx=1+\ln(n)

מהטענה הנ"ל נקבל כי $T(n)\leq nH_{n}\leq n(1+\ln n)\leq n\cdot 2\ln n=2n\ln n=O(n\log n)$ .

הערה (חשובה מאוד)

1 - סיבוכיות של חישובים

מבני נתונים 1

סיבוכיות של חישובים

1 - סיבוכיות של חישובים

מבני נתונים 1

סיבוכיות של חישובים

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

סיבוכיות זמן

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

סיבוכיות זמן