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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

קפיצה אל: ניווט, חיפוש

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

תוכן עניינים

1 פונקציה שקוראת לשלוש פונקציות אחרות
- 1.1 שאלה
- 1.2 תשובה
  - 1.2.1 1
  - 1.2.2 2
  - 1.2.3 3
2 פונקציה המשתמשת במודולו
- 2.1 שאלה
- 2.2 תשובה
  - 2.2.1 פעולת הפונקציה
  - 2.2.2 ניתוח סיבוכיות
3 קריאות רקרורסיביות בלולאת קפיצות שורש
- 3.1 שאלה
- 3.2 תשובה

[עריכה] פונקציה שקוראת לשלוש פונקציות אחרות

[עריכה] שאלה

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

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

נתון:

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

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

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

[עריכה] תשובה

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

[עריכה] 1

הטענה נכונה.

ברור שזמן הריצה של Foo(n) לפחות גדול כמו זמן הריצה של Bar(n). לכן נקבל $\displaystyle f(n) \ge \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 10 n^4$ , זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2 n^2$ , וזמן הריצה של Bar-3(n) הוא $\displaystyle n$ . (קל לראות שנתוני השאלה מסופקים.)

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

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

אז במקרה זה, $\displaystyle f(n) = 10 n^2 \log(n) + 1.2 n^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)

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

הפונקציה Sqrt(n) מחזירה את השורש הריבועי של $\displaystyle n$ מעוגל כלפי מטה. היא פועלת בזמן $\displaystyle O(1)$ .
הפונקציה 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))$ .

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] פונקציה שקוראת לשלוש פונקציות אחרות

[עריכה] שאלה

[עריכה] תשובה

[עריכה] 1

[עריכה] 2

[עריכה] 3

[עריכה] פונקציה המשתמשת במודולו

[עריכה] שאלה

[עריכה] תשובה

[עריכה] פעולת הפונקציה

[עריכה] ניתוח סיבוכיות

[עריכה] קריאות רקרורסיביות בלולאת קפיצות שורש

[עריכה] שאלה

[עריכה] תשובה

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא