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

פעולת הפונקציה

כדי להבין מה עושה הפונקציה כאשר היא מקבלת את הקלט $\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))$.