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

פונקציה שקוראת לשלוש פונקציות אחרות

שאלה

נתבונן בפסוודו-קוד הבא:

Foo(n)
1	Bar-1(n)
2	Bar-2(n)
3	Bar-3(n)

נתון:

1. זמן הריצה של Bar-1(n) הוא $\displaystyle \Omega (n^{2}\log(n))$.
2. זמן הריצה של Bar-2(n) הוא $\displaystyle \Theta (n^{2})$.
3. זמן הריצה של Bar-3(n) הוא $\displaystyle O(n)$.

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

1. זמן הריצה של Foo(n) הוא $\displaystyle \Omega (n)$.
2. זמן הריצה של Foo(n) הוא $\displaystyle \Omega (n^{3})$.
3. זמן הריצה של Foo(n) הוא $\displaystyle O(n^{3})$.

תשובה

נקרא לזמן הריצה של Foo(n) $\displaystyle f(n)$.

1

הטענה נכונה.

ברור שזמן הריצה של Foo(n) לפחות גדול כמו זמן הריצה של Bar(n). לכן נקבל $\displaystyle f(n)\geq \Omega (n^{2}\log(n))\Rightarrow f(n)=\Omega (n^{2}\log(n))$. אבל $\displaystyle n^{2}\log(n))=\Omega (n)$, ולכן הטענה נובעת מטרנזיטיביות.

2

אי אפשר לקבוע אם הטענה נכונה או לא.

נניח שזמן הריצה של Bar-1(n) הוא $\displaystyle 10n^{4}$, זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2n^{2}$, וזמן הריצה של Bar-3(n) הוא $\displaystyle n$. (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, $\displaystyle f(n)=10n^{4}+1.2n^{2}+n=\Theta (n^{4})$. הטענה בבירור מתקיימת.

לחלופין, נניח שזמן הריצה של Bar-1(n) הוא $\displaystyle 10n^{2}\log(n)$, זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2n^{2}$, וזמן הריצה של Bar-3(n) הוא $\displaystyle n$. (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, $\displaystyle f(n)=10n^{2}\log(n)+1.2n^{2}+n=\Theta (n^{2}\log(n))$. קל להראות (באופן דומה לזה שראינו בתרגילים קודמים) שלא ייתכן שבמקרה זה $\displaystyle f(n)=\Omega (n^{3})$.

3

אי אפשר לקבוע האם הטענה נכונה או לא.

שני המקרים מהסעיף הקודם מראים זאת.

פונקציה המשתמשת במודולו

שאלה

להלן פסוודו-קוד לפונקציה Foo, המקבלת מספר שלם לא-שלילי ומחזירה מספר שלם:

Foo(n)
1	if n == 0
2		return 0

3	return n % 2 + Foo( ⌊n / 2⌋ )

אנא הסבר מה עושה הפונקציה (בלווי נימוק), ונתח את סיבוכיותה.

תשובה

פעולת הפונקציה

כדי להבין מה עושה הפונקציה כאשר היא מקבלת את הקלט $\displaystyle n$, נחשוב על הייצוג הבינרי של $\displaystyle n$, נניח $\displaystyle b_{h}b_{h-1}b_{2}b_{1}$ (כלומר נניח ש$\displaystyle n$ הנו מספר בעל $\displaystyle h$ ביטים, בעל הביט החשוב ביותר $\displaystyle b_{h}$, והביט החשוב פחות $\displaystyle b_{1}$).

כעת נראה מה הפונקציה עושה.

• בשורה 3, הביטוי $\displaystyle n\%2$ הוא בדיוק ערך הביט $\displaystyle b_{1}$.
• שוב בשורה 3, Foo( ⌊n / 2⌋ ) היא הקריאה לאותה פונקציה, אך עם הערך $\displaystyle b_{h}b_{h-1}b_{2}$.

מכאן ברור שהפונקציה פשוט סוכמת את הביטים של $\displaystyle n$. אפשר להראות זאת פורמלית באינדוקציה.

ניתוח סיבוכיות

מהתבוננות בשלוש שורות הפונקציה, ברור שלמעט הקריאה הרקורסיבית, כל הפעולות הן בזמן קבוע. מכאן נקבל את נוסחת הנסיגה $\displaystyle T(n)=T(\left\lfloor n/2\right\rfloor )+O(1)$. נזכר שוב שמותר לנו (בקורס זה) להתעלם משגיאות עיגול בנוסאות נסיגה של זמן ריצה, ולכן נוסחת הנסיגה היא $\displaystyle T(n)=T(n/2)+O(1)$. כבר ראינו (בדף על נוסחאות נסיגה) שפתרון נוסחה זו הוא $\displaystyle \Theta (\log(n))$.

קריאות רקרורסיביות בלולאת קפיצות שורש

שאלה

הפונקציה Alg מוגדרת כך:

Alg(A, i, j)
1	if j <= i + 1
2		return
	
3	q = Sqrt(j - i + 1) # q = ⌊(j - i + 1)^(1/2)⌋
4	for k in [0, ..., q - 1]
5		Alg(A, i + k * q, i + (k + 1) * (q - 1))

6	Proc(A, i, j)

היא משתמשת בשתי הפונקציות הבאות:

1. הפונקציה Sqrt(n) מחזירה את השורש הריבועי של $\displaystyle n$ מעוגל כלפי מטה. היא פועלת בזמן $\displaystyle O(1)$.
2. הפונקציה Proc היא פונקציה כלשהי המקיימת שזמן ריצת Proc(A, i, j) הוא $\displaystyle \Theta (j-i)$.

מהו זמן הריצה של Alg(A, 1, n)?

תשובה

נסמן את זמן הריצה של Alg(A, i, j) כ$\displaystyle T(i,j)$.

נצייר את עץ הפרישה של הפונקציה:

עץ הפרישה. ט"ו בשבט שמח.

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

נפתור $\displaystyle n^{\frac {1}{2^{h}}}=k$, ונקבל

$\displaystyle {\frac {\log(n)}{2^{h}}}=\log(k)\Rightarrow 2^{h}={\frac {\log(n)}{\log(k)}}\Rightarrow h=\Theta (\log \log(n))$.

הסיבוכיות, לכן, היא $\displaystyle \Theta (n\cdot \log \log(n))$.