בהמשך להודעה הפרטית שלך, החישוב הוא חישוב ישיר - מציבים כל פעם בתנאי הרקורסיה עד שמגיעים לתנאי העצירה ומנסים לחסום משני הצדדים. כשרשמתי לך בשיחות חברים את התשובה, קצת התפרעתי עם החסמים, אז אני אעדן את זה כאן.קודם כל אתה רואה שתנאי הרקורסיה מקטין את הבעייה פי 2 בכל איטרציה, קרי לאחר log n איטרציות אתה מגיע ל-T(1) = 1. בכל איטרציה נוצר האיבר (עד כדי עיגול עליון/תחתון וכפל בקבועים) הבא:
5^k/2^ k * n^2 * [log (n/2^k)]^2 = n^2 * [ (5/2)^k * [log (n/2^k)]^2 ]
ומה שנותר לך לשאול את עצמך זה לאן הטור הזה מתכנס, או לפחות לאיזה סדר גודל. הרעיון למצוא 2 חסם מלרע וחסם מלעיל לטור שיחסית קרובים אחד לשני ובכל זאת מתכנסים לאותו סדר גודל - אתה יכול לעשות את זה בכל דרך שהיא, העיקר שיהיה נכון. אני בחרתי למשל לקחת כחסם מלעיל את האיבר הכי גדול של הלוג בסכום, כלומר log n ולכפול אותו בסכום, וכחסם מלרע לקחתי את האיבר האמצעי וכפלתי אותו בסכום החל מהאיבר האמצעי עד הסוף.
http://rotter.name/User_files/nor/4e3833753d26a6fe.jpg
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
