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

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

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

שאלה[עריכה]

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

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

נתון:

  1. זמן הריצה של Bar-1(n) הוא .
  2. זמן הריצה של Bar-2(n) הוא .
  3. זמן הריצה של Bar-3(n) הוא .

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

  1. זמן הריצה של Foo(n) הוא .
  2. זמן הריצה של Foo(n) הוא .
  3. זמן הריצה של Foo(n) הוא .

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

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

1[עריכה]

הטענה נכונה.

ברור שזמן הריצה של Foo(n) לפחות גדול כמו זמן הריצה של Bar(n). לכן נקבל . אבל , ולכן הטענה נובעת מטרנזיטיביות.

2[עריכה]

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

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

אז במקרה זה, . הטענה בבירור מתקיימת.


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

אז במקרה זה, . קל להראות (באופן דומה לזה שראינו בתרגילים קודמים) שלא ייתכן שבמקרה זה .

3[עריכה]

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

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

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

שאלה[עריכה]

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

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

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

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

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

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

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

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

  • בשורה 3, הביטוי הוא בדיוק ערך הביט .
  • שוב בשורה 3, Foo( ⌊n / 2⌋ ) היא הקריאה לאותה פונקציה, אך עם הערך .

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


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

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

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

שאלה[עריכה]

הפונקציה 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) מחזירה את השורש הריבועי של מעוגל כלפי מטה. היא פועלת בזמן .
  2. הפונקציה Proc היא פונקציה כלשהי המקיימת שזמן ריצת Proc(A, i, j) הוא .

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

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

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

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

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

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

נפתור , ונקבל

.


הסיבוכיות, לכן, היא .