סיבוכיות ברקורסיה

[pdib]

סיבוכיות ברקורסיה ../images/Emo26.gif

איך אני מעריך מהי הסיבוכיות בפונקציה רקורסיבית? הרי לא תמיד יש שם לולאה או משהו, אז אם אין לולאה הסיבוכיות של הפונ' היא o(1) ?

 

[gil levi]

לא, למה?

למשל:

f if (n==1) return 1 return 1 + f(n-1)​

הפונ' הזו מחברת 1+1+1+...+1 כאשר ה1 מופיע n פעמים. הסיבוכיות היא O zzz. לפונ' רקורסיביות אפשר לבנות נוסחת נסיגה: יהי T zzz זמן הריצה של פונ' g (סתם פונ') על קלט בגודל n. נניח שכשg מקבלת קלט בגודל n היא מבצעת פעולות שעולות O zzz ומריצה את עצמה ברקורסיה על קלט בגודל n/2, אז נוסחת הנסיגה היא T=T(n/2) + n zzz. הפתרון לנוסחת הנסיגה הוא זמן הריצה של הפונ'. כמובן שלא חייבים לפעול בשיטה הזו, זה פשוט הדבר היחיד שעלה לי לראש.

 

[ron369]

אני חושב שזו לא הייתה הגדרת המשורר

(או הכוונה שלו) אבל אשמח לשמוע מה הוא רצה

 

[pdib]

כן, אבל ../images/Emo26.gif

אם יש לי אלגוריתם רקורסיבי, אז לא תמיד אני יכול לבנות לו נוסחת נסיגה, ולפתור אותה, אתה מבין? במיוחד באמצע בחינה. אני פשוט צריך להסתכל על הפקודות ולהעריך את הסיבוכיות של אותה פונ' רקורסיבית. איך עושים זאת? על פי אילו כללים? לדוג' כשהפונ' אינה רקורסיבית, אז לולאה = on , ולולאה בתוך לולאה = on². וכו', אבל כשיש לי פונ' רקורסיבית איך אני מעריך את הסיבוכיות, כי כמו בדוג' שנתת אין לולאה או משהו בסגנון.

 

[ron369]

כללי אצבע, כמובן

1) כל תרגיל שייתנו לך במבחן, לדעתי, כמעט בלי ספק, יהיה פתיר באמצעות נוסחת נסיגה פשוטה ושיטת האב. 2) אם לא, פשוט תחשוב. במקרים רבים יכול מאד להיות שניתן יהיה ליצור מעין "רדוקציה" לשיטת האב, ע"י כל מיני שינויים קטנים (זכור שקבועים לא משנים יותר מדי, וכו'). 3) עכשיו, אם הכל לא עובד, אתה כנראה פשוט צריך לשחק איתה "הרבה". כלומר, נניח שנתון לך ש: T = T(n/2) + T(n/4) + 1 אז מה אתה יכול לעשות? כמובן, לשחק עם זה. למשל, להציב במקום T(n/2) את T(n/4) + T(n/8) + 1, וכך להמשיך, עד שתזהה את החוקיות. בנוסף, אתה יכול גם ממש לשנות את נוסחת הנסיגה לחלוטין, כדי לקבל מעין "קירוב" עבורה. למשל, להפוך את e^n ל- ZZZ 2^n כדי שיצטמצם עם זה ועם זה, וכולי'. אין לי עוד הרבה רעיונות.

 

[ron369]

ואל תתן לאנשים להפחיד אותך,

עם כל מיני "תרגילים שאי אפשר לפתור".

 

[the new L]

יש כאלה

למשל, נסה לנתח את הסיבוכיות של האלגוריתם הרקורסיבי הבא:

T: if (n==1) return ; if ((n % 2) == 1) return T(3n+1); return T(n/2);​

 

[ron369]

לאו דווקא

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

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

 

[ron369]

למיטב ידיעתי, ולפי ההגדרה ההגיונית

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

 

[נועה לביא]

עם נוסחאת נסיגה

 

[shirbi]

באמצעות שיטת האב

http://he.wikipedia.org/wiki/%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%90%D7%91

 

[נועה לביא]

לא תמיד אפשר.

 

[the new L]

לא ניתן לדעת

באופן כללי זאת בעיה בלי פתירה. קל לראות שקילות לבעיית העצירה.

 

[gil levi]

אבל אבל אבל

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

 

[נועה לביא]

לירן התכוון להתחכם ולומר

שאין אלגוריתם כזה...

 

[gil levi]

תיקון: אפשר להרחיב את ההגדרה

לפונ' שלא תמיד עוצרות.