מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מציאת סיבוכיות פסוודו-קוד/תרגילים
פונקציה שקוראת לשלוש פונקציות אחרות
עריכהשאלה
עריכהנתבונן בפסוודו-קוד הבא:
Foo(n)
1 Bar-1(n)
2 Bar-2(n)
3 Bar-3(n)
נתון:
- זמן הריצה של
Bar-1(n)
הוא . - זמן הריצה של
Bar-2(n)
הוא . - זמן הריצה של
Bar-3(n)
הוא .
עבור כל אחד מהחסמים הבאים, אנא ציין האם הוא בהכרח מתקיים, בהכרח לא מתקיים, או שאי אפשר לקבוע בוודאות האם הוא בהכרח מתקיים או לא:
- זמן הריצה של
Foo(n)
הוא . - זמן הריצה של
Foo(n)
הוא . - זמן הריצה של
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)
היא משתמשת בשתי הפונקציות הבאות:
- הפונקציה
Sqrt(n)
מחזירה את השורש הריבועי של מעוגל כלפי מטה. היא פועלת בזמן . - הפונקציה
Proc
היא פונקציה כלשהי המקיימת שזמן ריצתProc(A, i, j)
הוא .
מהו זמן הריצה של Alg(A, 1, n)
?
תשובה
עריכהנסמן את זמן הריצה של Alg(A, i, j)
כ .
נצייר את עץ הפרישה של הפונקציה:
מהפרישה אפשר לראות (ולהוכיח פורמלית באינדוקציה), שכל רמה תורמת , והארגומנטים קטנים מרמה לרמה לפי שורש. אם גובה העץ הוא , אז סכום הרמות הוא . נותר למצוא את .
נפתור , ונקבל
.
הסיבוכיות, לכן, היא
.