פורסם 2009 באוקטובר 2416 שנים שלום חברים, קיבלתי בתרגיל בית שאלה די מסובכתשצריך לפתור את נוסחת הנסיגה (להעביר לנוסחה רגילה שתלויה בn)ואז למצוא לנוסחה הזאת חסם הדוק.הנוסחה היא:T(n) = T(0.13n) + T(0.87n) + 3nהבעיה היא שאותנו לימדו גם בהרצאה וגם בתרגיל לפתור שאלות בסגנון Tn = T(n/x) + Fnבלי משפט האב או משהו. פשוט אמרו לנו להמשיך לפתוח את הT הפנימי ואז "לנחש" פתרוןעם i ואז להוכיח באינד' שזה נכון ובסוף לפתור עם תנאי ההתחלה. לא משנה.העניין הוא שלא הראו לנו דבר כזה וכמעט אף אחד לא הצליח.תודה רבה מראש לעוזרים.
פורסם 2009 באוקטובר 2516 שנים אם משרטטים את יחס הנסיגה כעץ בינארי, מקבלים משהו שנראה ככה: טענת עזר: בהינתן צומת כלשהו בעץ עם ערך K ושני ילדים, אזי סכום הערכים של הילדים שווה לK (נובע ישירות מיחס הנסיגה). טענה: סכום הצמתים בכל רמה הוא (O(n הוכחה באינדוקציה: הטענה נכונה עבור השורש. נניח נכונות עבור הרמה הi. לכל צומת ברמה הi יש לכל היותר שני ילדים, ולכן סכום הצמתים ברמה הi+1 שווה לכל היותר לסכום הצמתים ברמה הi. טענה: עומק העץ הוא (O(logn הוכחה: העלה העמוק ביותר הוא העלה הימני ביותר. נסמן את עומקו ב-h 3n*(0.87)^h = 1 עבור n גדול מאוד h = logn משתי הטענות נובע שסכום הצמתים בכלל העץ הוא (O(nlogn, וזה (T(n עריכה: לגבי חסם תחתון נחכה לתשובה מעוד מישהו.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.