הגדרה 1 (רקורסיה)

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

דוגמה (אלגוריתם ה-

Merge\;Sort

)

T(n)=\begin{cases} \Theta (1) & n=1 \\ 2\;T\!\!\;\!\left( \frac{n}{2} \right)+\Theta(n) & n>1 \end{cases}

שיטות לפתרון רקורסיות

השיטה האינדוקטיבית

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

דוגמה

נגדיר:

T(n)=\begin{cases} 1 & n=1 \\ 2T\left( \left\lfloor \frac{n}{2} \right\rfloor \right)+n & n>1 \end{cases}

ונוכיח $T(n)=O(n\log n)$ .
הוכחה:
בסיס:

עבור $n=2$ ו- $c\geq 2$ מתקיים: $4=T(2)\leq 2c\log_{2} 2$
עבור $n=3$ ו- $c\geq 2$ מתקיים: $5=T(3)\geq_{3}c\log{2}3$ .

צעד: נפעיל את הנחת האינדוקציה על ההגדרה הרקורסיבית:

T(n)=2T\left( \left\lfloor \frac{n}{2} \right\rfloor \right)+n\leq 2\left( c\left\lfloor \frac{n}{2} \right\rfloor \log_{2}\left\lfloor \frac{n}{2} \right\rfloor \right)+n\leq2\left( c \frac{n}{2}\log_{2} \frac{n}{2} \right)+n=cn(\log_{2}n-1)+n

=cn\log_{2}n-cn+n\leq cn\log_{2}n

אי השוויון האחרון נכון כאשר $c\geq 1$ .
∎

הערה (מדוע הצעד

\left\lfloor \frac{n}{2} \right\rfloor\implies n

מספיק?)

זה לא נכון נראה לי
מבני תרגול של החברה 2.png
זה הנימוק מהמצגת, לא אוהב אותו.

שיטת האיטרציות

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

דוגמה

T(n)=n+3T\left( \left\lfloor \frac{n}{4} \right\rfloor \right)

הוכחה:

T(n)=n+3T\left( \left\lfloor \frac{n}{4} \right\rfloor \right)=n+3\left( \left\lfloor \frac{n}{4} \right\rfloor +3T\left( \left\lfloor \frac{n}{16} \right\rfloor \right) \right)=n+3\left\lfloor \frac{n}{4} \right\rfloor +9\left\lfloor \frac{n}{16} \right\rfloor +27T\left( \left\lfloor \frac{n}{64} \right\rfloor \right)

הערה

מספר האיטרציות שנצטרך לבצע עד שנגיע לתנאי התחלה הוא $\left\lfloor \frac{n}{4^i} \right\rfloor=1\implies i=\log_{4}n$ .

T(n)\leq n+\frac{3}{4}n+\frac{9}{16}n+\dots+3^i T\left( \left\lfloor \frac{n}{4^i} \right\rfloor \right)\leq n\sum_{i=0}^\infty \left( \frac{3}{4} \right)^i +3^{\log_{4}n}\Theta(1)

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

\begin{align*} \mathrm{I}\; & \sum_{i=0}^\infty \left( \frac{3}{4} \right)^i=\frac{1}{1-\frac{3}{4}}=4 \\ \mathrm{II}\; & 3^{\log_{4}n}=3^{\frac{\log_{3}n}{\log_{3}4}}=(3^{\log_{3}n})^{\frac{1}{\log_{3}4}}=n^{\frac{1}{\frac{\log_{4}4}{\log_{4}3}}}=n^{\frac{1}{\frac{1}{\log_{4}3}}}=n^{\log_{4}3} \end{align*}

ולכן:

T(n)\leq 4n+n^{\log_{4}3}\Theta(1)=O(n)

∎

עצי רקורסיות - דרך אחרת להסתכל על שיטת האיטרציות

דוגמה

עבור:

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

מבני תרגול של החברה 3.png
סכום הצמתים של כל אחד מהעצים הנ"ל הוא $T(n)$ ולכן:

T(n)\leq n^2+2\left( \frac{n}{2} \right)^2+4\left( \frac{n}{4} \right)^2+\dots=n^2\left( 1+\frac{1}{2}+\frac{1}{4}+\cdots \right)=2n^2\implies T(n)=O(n^2)

דוגמה

עבור:

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

נשים לב כי מתקיים:
מבני תרגול של החברה 4.png
ולכן:

n\log_{3}n\leq T(n)\leq n\log_{\frac{3}{2}}n \implies T(n)=\Theta(n\log n)

שיטת המאסטר

משפט (המאסטר)

יהיו $a\geq1$ ו- $b>1$ קבוצים ותהי $f(n)$ פונקציה.
נגדיר: $T(n)=aT\left( \frac{n}{b} \right)+f(n)$ . אזי, ניתן לחסום את $T$ אסימפטוטית באופן הבא:

אם $f(n)=O(n^{\log_{b}a-\epsilon})$ כאשר $\epsilon>0$ קבוע כלשהו אזי $T(n)=\Theta(n^{\log_{b}a})$ .
אם $f(n)=\Theta(n^{\log_{b}a})$ אז $T(n)=\Theta(n^{\log_{b}a}\cdot \log n)$
אם $f(n)=\Omega(n^{\log_{b}a+\epsilon})$ כאשר $\epsilon>0$ קבוע כלשהו וגם $af\left( \frac{n}{b} \right)\leq cf(n)$ עבור קבוע $c<1$ והחל מ- $n$ מספיק גדול אזי $T(n)=\Theta(f(n))$ .

דוגמה

\begin{array}{|c|c|c|c|c|c|} \hline T(n)=aT\left( \frac{n}{b} \right)+f(n) & a & b & \log_{n}a & f(n) & \Theta \\ \hline T(n)=9T\left( \frac{n}{3} \right)+n & 9 & 3 & 2 & n & n^2 \\ \hline T(n)=T\left( \frac{2n}{3} \right)+1 & 1 & \frac{3}{2} & 0 & 1 & \log n \\ \hline T(n)=3T\left( \frac{n}{4} \right)+n\log n & 3 & 4 & \log_{4}3 & n\log n & n\log n \\ \hline T(n)=2T\left( \frac{n}{2} \right)+n\log n & 2 & 2 & 1 & n\log n & \R{\text{לא עומד בתנאי המשפט}} \\ \hline \end{array}

החלפת משתנים

תרגיל

מצאו חסם אסימפטוטי הדוק למשוואה הרקורסיבית הבאה:

T(n)=\begin{cases} 1 & n=1 \\ 2T(\sqrt{ n }) & +\log n-1 & n>1 \end{cases}

תחילה נסמן $m=\log_{2}n$ ואז:

T(2^m)=2T\left( 2^{\frac{m}{2}} \right)+m-1

נגדיר $S(m)=T(2^m)$ ונשים לב כי תחת הגדרה זו $S\left( \frac{m}{2} \right)=T\left( 2^{\frac{m}{2}} \right)$ ולכן:

S(m)=2S\left( \frac{m}{2} \right)+m-1

בתחילת התרגול ראינו כי $S(m)=\Theta(m\log m)$ ולכן:

T(n)=T(2^m)=S(m)=\Theta(m\log m)=\Theta(\log n\cdot \log(\log n))

תרגיל

מצאו חסם אסימפטוטי הדוק למשוואה הרקורסיבית הבאה:

T(n)=\begin{cases} 1 & n=1 \\ 2\sqrt{ n }T(\sqrt{ n })+n(\log n-1) \end{cases}

תחילה נחלק את המשוואה ב- $n$ :

\frac{T(n)}{n}=2 \frac{T(\sqrt{ n })}{\sqrt{ n }}+\log n-1

נציב $U(n)=\frac{T(n)}{n}$ ונשים לב כי תחת הגדרה זו $U(\sqrt{ n })=\frac{T(\sqrt{ n })}{\sqrt{ n }}$ .

U(n)=2U(\sqrt{ n })+\log n-1

נשים לב שזוהי המשוואה שהרגע ראינו ולכן:

T(n)=nU(n)=n\Theta(\log n\cdot \log(\log n))=\Theta(n\log n\cdot \log \log n)

הגדרה 1 (רקורסיה)

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

דוגמה (אלגוריתם ה-

Merge\;Sort

)

T(n)=\begin{cases} \Theta (1) & n=1 \\ 2\;T\!\!\;\!\left( \frac{n}{2} \right)+\Theta(n) & n>1 \end{cases}

שיטות לפתרון רקורסיות

השיטה האינדוקטיבית

דוגמה

נגדיר:

T(n)=\begin{cases} 1 & n=1 \\ 2T\left( \left\lfloor \frac{n}{2} \right\rfloor \right)+n & n>1 \end{cases}

ונוכיח $T(n)=O(n\log n)$ .
הוכחה:
בסיס:

עבור $n=2$ ו- $c\geq 2$ מתקיים: $4=T(2)\leq 2c\log_{2} 2$
עבור $n=3$ ו- $c\geq 2$ מתקיים: $5=T(3)\geq_{3}c\log{2}3$ .

צעד: נפעיל את הנחת האינדוקציה על ההגדרה הרקורסיבית:

T(n)=2T\left( \left\lfloor \frac{n}{2} \right\rfloor \right)+n\leq 2\left( c\left\lfloor \frac{n}{2} \right\rfloor \log_{2}\left\lfloor \frac{n}{2} \right\rfloor \right)+n\leq2\left( c \frac{n}{2}\log_{2} \frac{n}{2} \right)+n=cn(\log_{2}n-1)+n

=cn\log_{2}n-cn+n\leq cn\log_{2}n

אי השוויון האחרון נכון כאשר $c\geq 1$ .
∎

הערה (מדוע הצעד

\left\lfloor \frac{n}{2} \right\rfloor\implies n

מספיק?)

זה לא נכון נראה לי
מבני תרגול של החברה 2.png
זה הנימוק מהמצגת, לא אוהב אותו.

שיטת האיטרציות

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

דוגמה

T(n)=n+3T\left( \left\lfloor \frac{n}{4} \right\rfloor \right)

הוכחה:

T(n)=n+3T\left( \left\lfloor \frac{n}{4} \right\rfloor \right)=n+3\left( \left\lfloor \frac{n}{4} \right\rfloor +3T\left( \left\lfloor \frac{n}{16} \right\rfloor \right) \right)=n+3\left\lfloor \frac{n}{4} \right\rfloor +9\left\lfloor \frac{n}{16} \right\rfloor +27T\left( \left\lfloor \frac{n}{64} \right\rfloor \right)

הערה

מספר האיטרציות שנצטרך לבצע עד שנגיע לתנאי התחלה הוא $\left\lfloor \frac{n}{4^i} \right\rfloor=1\implies i=\log_{4}n$ .

T(n)\leq n+\frac{3}{4}n+\frac{9}{16}n+\dots+3^i T\left( \left\lfloor \frac{n}{4^i} \right\rfloor \right)\leq n\sum_{i=0}^\infty \left( \frac{3}{4} \right)^i +3^{\log_{4}n}\Theta(1)

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

\begin{align*} \mathrm{I}\; & \sum_{i=0}^\infty \left( \frac{3}{4} \right)^i=\frac{1}{1-\frac{3}{4}}=4 \\ \mathrm{II}\; & 3^{\log_{4}n}=3^{\frac{\log_{3}n}{\log_{3}4}}=(3^{\log_{3}n})^{\frac{1}{\log_{3}4}}=n^{\frac{1}{\frac{\log_{4}4}{\log_{4}3}}}=n^{\frac{1}{\frac{1}{\log_{4}3}}}=n^{\log_{4}3} \end{align*}

ולכן:

T(n)\leq 4n+n^{\log_{4}3}\Theta(1)=O(n)

∎

עצי רקורסיות - דרך אחרת להסתכל על שיטת האיטרציות

דוגמה

עבור:

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

מבני תרגול של החברה 3.png
סכום הצמתים של כל אחד מהעצים הנ"ל הוא $T(n)$ ולכן:

T(n)\leq n^2+2\left( \frac{n}{2} \right)^2+4\left( \frac{n}{4} \right)^2+\dots=n^2\left( 1+\frac{1}{2}+\frac{1}{4}+\cdots \right)=2n^2\implies T(n)=O(n^2)

דוגמה

עבור:

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

נשים לב כי מתקיים:
מבני תרגול של החברה 4.png
ולכן:

n\log_{3}n\leq T(n)\leq n\log_{\frac{3}{2}}n \implies T(n)=\Theta(n\log n)

שיטת המאסטר

משפט (המאסטר)

אם $f(n)=O(n^{\log_{b}a-\epsilon})$ כאשר $\epsilon>0$ קבוע כלשהו אזי $T(n)=\Theta(n^{\log_{b}a})$ .
אם $f(n)=\Theta(n^{\log_{b}a})$ אז $T(n)=\Theta(n^{\log_{b}a}\cdot \log n)$
אם $f(n)=\Omega(n^{\log_{b}a+\epsilon})$ כאשר $\epsilon>0$ קבוע כלשהו וגם $af\left( \frac{n}{b} \right)\leq cf(n)$ עבור קבוע $c<1$ והחל מ- $n$ מספיק גדול אזי $T(n)=\Theta(f(n))$ .

דוגמה

\begin{array}{|c|c|c|c|c|c|} \hline T(n)=aT\left( \frac{n}{b} \right)+f(n) & a & b & \log_{n}a & f(n) & \Theta \\ \hline T(n)=9T\left( \frac{n}{3} \right)+n & 9 & 3 & 2 & n & n^2 \\ \hline T(n)=T\left( \frac{2n}{3} \right)+1 & 1 & \frac{3}{2} & 0 & 1 & \log n \\ \hline T(n)=3T\left( \frac{n}{4} \right)+n\log n & 3 & 4 & \log_{4}3 & n\log n & n\log n \\ \hline T(n)=2T\left( \frac{n}{2} \right)+n\log n & 2 & 2 & 1 & n\log n & \R{\text{לא עומד בתנאי המשפט}} \\ \hline \end{array}

החלפת משתנים

תרגיל

מצאו חסם אסימפטוטי הדוק למשוואה הרקורסיבית הבאה:

T(n)=\begin{cases} 1 & n=1 \\ 2T(\sqrt{ n }) & +\log n-1 & n>1 \end{cases}

תחילה נסמן $m=\log_{2}n$ ואז:

T(2^m)=2T\left( 2^{\frac{m}{2}} \right)+m-1

נגדיר $S(m)=T(2^m)$ ונשים לב כי תחת הגדרה זו $S\left( \frac{m}{2} \right)=T\left( 2^{\frac{m}{2}} \right)$ ולכן:

S(m)=2S\left( \frac{m}{2} \right)+m-1

בתחילת התרגול ראינו כי $S(m)=\Theta(m\log m)$ ולכן:

T(n)=T(2^m)=S(m)=\Theta(m\log m)=\Theta(\log n\cdot \log(\log n))

תרגיל

מצאו חסם אסימפטוטי הדוק למשוואה הרקורסיבית הבאה:

T(n)=\begin{cases} 1 & n=1 \\ 2\sqrt{ n }T(\sqrt{ n })+n(\log n-1) \end{cases}

תחילה נחלק את המשוואה ב- $n$ :

\frac{T(n)}{n}=2 \frac{T(\sqrt{ n })}{\sqrt{ n }}+\log n-1

נציב $U(n)=\frac{T(n)}{n}$ ונשים לב כי תחת הגדרה זו $U(\sqrt{ n })=\frac{T(\sqrt{ n })}{\sqrt{ n }}$ .

U(n)=2U(\sqrt{ n })+\log n-1

נשים לב שזוהי המשוואה שהרגע ראינו ולכן:

T(n)=nU(n)=n\Theta(\log n\cdot \log(\log n))=\Theta(n\log n\cdot \log \log n)

2 - פונקציות רקורסיביות

מבני נתונים 1

פונקציות רקורסיביות

2 - פונקציות רקורסיביות

מבני נתונים 1

פונקציות רקורסיביות

שיטות לפתרון רקורסיות

השיטה האינדוקטיבית

שיטת האיטרציות

עצי רקורסיות - דרך אחרת להסתכל על שיטת האיטרציות

שיטת המאסטר

החלפת משתנים

שיטות לפתרון רקורסיות

השיטה האינדוקטיבית

שיטת האיטרציות

עצי רקורסיות - דרך אחרת להסתכל על שיטת האיטרציות

שיטת המאסטר

החלפת משתנים