עבור לתוכן

פונקציות מבני נותנים

Featured Replies

פורסם

איך חוסמים

f[n]=f[n-1]+log[n

פורסם

בהנחה שתנאי העצירה הוא f[0]=0

tתה יכול ברקורסיה..

f[n]=f[n-1]+lgn[n]=f[n-2]+log[n-1]+log[n]=log[1] + . . . . . + log[n-1] + log[n]

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

עכשיו עלייך לחשב את log[n(n-1)(n-2)...]

אבל לא צריך לחשב את כל המכפלה מכיוון שמדובר בO(...), ולכן אתה יכול להוריד את ה- -1, -2, ...

ואז תקבל log[n^n]

שזה nlogn

פורסם
  • מחבר

מדהימ תודה ..אל תברח עוד שאלות ..

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים