לדלג לתוכן

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

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

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

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

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

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

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


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

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