זוהי אחת השאלות השכיחות ביותר בראיונות, לפחות כשאלת חימום. למרות שהיא לא שאלה קשה, היא נוטה לבלבל יחסית בקלות את הלא מנוסים שבאים לפתור אותה.
בפוסט זה נציג קודם את הפתרון הרקורסיבי ונבדוק דרך לשפר אותו לפתרון יעיל ומהיר יותר.
דרישות:
- יעילות זמן : n
- יעילות מקום: 1
למי שלא מכיר את סדרת פיבונאצ'י - זוהי סדרה מפורסמת של מספרים שכל אחד בה מהווה הסכום של שתי הספרות שלפניו. לכאורה, נשמע סדרה מטופשת שכתב מישהו ששיעמם לו, אבל יש לה יישומים מעניינים מאד. מומלץ לקרוא עליה למי שמעונין.
בשאלה, נתבקש להחזיר את המספר ה-n של פיבונאצ'י בסדרה. כדי לבצע זאת, נצטרך להגדיר את חוקיות הסדרה בפונקציה ולבצע חזרתיות עד שנגיע למספר המבוקש.
הפתרון הראשון שנציג יהיה פתרון רקורסיבי. במידה ואינכם מכירים רקורסיה, אני ממליץ לכם לקרוא פוסטים קודמים שכתבתי בנושא.
כללי העצירה הם פשוטים: כאשר n=0 אנחנו נחזיר 0 כיוון שלא קיים מספר באינדקס 0 ברשימה. עבור n=1 נחזיר 1 - כי זהו הערך של המספר הראשון בסדרה ומכאן והלאה, אנחנו יכולים להתחיל ולסכום את הספרה הקודמת ואת זו שלפניה -> אם n=2 אז שתי הספרות שלפניה יהיו 0 ו-1 כמו שהסברנו מקודם ולכן הסכום יהיה 1. האיבר הבא יהיה 2 וכן הלאה.
לכאורה, הרקורסיה פותרת את הבעיה בצורה אלגנטית ביותר - אבל היא בעייתית ככל שהמספר n גדל. אם תחשבו על זה תראו שלמעשה הפונקציה אינה פותרת דבר, אלא שולחת את הקוד לחפש את המספרים הקודמים שוב ושוב פעם עבור fib(n-1) ופעם עבור fib(n-2).
במילים אחרות, אין כאן שום "זיכרון" והעבודה שהתבצעה רק עכשיו, הולכת לפח בכל קריאה חדשה - זה גורם לאיטיות מרובה בזמן ריצה.
בעיה נוספת שתיתקלו בה היא שגיאה ברגע שיפתחו יותר מהמקסימום המותר של פונקציות רקורסיביות (נכון לעכשיו המספר הוא 1000).
אפשר לשפר זאת כמובן בקלות יחסית על ידי הוספת זיכרון לאלגוריתם שיוודא שהחישוב שהוא הולך לבצע - לא התבצע כבר בעבר.
זה שיפור משמעותי. אם תכניסו counter שיבדוק כמה פעמים הפונקציה נקראת תראו שיש ירידה של כ-90% בכמות הקריאות. אבל זו עדיין לא רמה ליניארית ואנחנו משתמשים בזיכרון לטובת ה-cache.
יש פתרון יעיל יותר וללא שימוש בזיכרון נוסף. המפתח לפתרון הוא ההבנה שאין באמת צורך לשמור את כל היסטורית המספרים שעברו אלא רק את השניים האחרונים ואת ההתקדמות ניתן לבצע באמצעות לולאה.
תובנה זו תסייע לכם בהמשך בפתרון של בעיות מורכבות יותר.
אין תגובות:
הוסף רשומת תגובה