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

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

עריכה

שאלה

עריכה

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

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)  .

הטענה נכונה.

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

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

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

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


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

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

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

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

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

עריכה

שאלה

עריכה

להלן פסוודו-קוד לפונקציה 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) כ .

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

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

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

נפתור  , ונקבל

 .


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