שאלה ב Order of growth

[gil levi]

שאלה ב Order of growth

צריך לדרג את הפונ':

4^log n^2 * log​

לפי ה order of growth שלהן (הפונ' השניה זה n בריבוע כפול logzzz, לא n בחזקת 2log zzz ). נראה לי ש:

log*n^2 = O( 4^log )​

(O גדול) אבל אני לא מצליח להוכיח את זה. ניסיתי לקחת גבול של אחת חלקי השנייה אבל אני לא מצליח לחשב אותו (חוץ מלופיטל אני בקושי זוכר איך לגשת לגבולות). ניסיתי להשתמש בזה ש n^2 * log <= n^3 ואז לקחת גבול אבל גם זה לא מצליח. ניסיתי להגדיר את הפונ':

f:= 4^log - n^2 * log g:= 4^log - n^3​

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

 

[vinney]

חייב גבולות

ההגדרה של O מתבססת על הגבול, לכן אתה חייב ללכת על גבולות. אין מה לעשות, תפשפש בסיכומי אינפי הישנים

 

[נועה לביא]

אין שום צורך לגעת בגבולות

בעקרון, בשביל להוכיח ש f=O(g) zz מספיק להוכיח שקיימים n0,c כך שלכל n>n0 מתקיים f<=cg zzz ובפונקציות מסוג זה זה ממש לא סיפור, במיוחד כאשר ע"פ חוקי הלוגריתמים מה שיש לך שם זה n^2 ו n^2lgn

 

[vinney]

המם...

מה שאמרת בעצם הוא שגבול F/G כשN שואף לאינסוף הוא קבוע.

 

[נועה לביא]

וואלה?

אין צורך להתעסק עם חישובי גבולות...

 

[yuvalmadar]

תהפוך את שתיהן לפונקציות מעריכיות

עם אותו בסיס. (בסיס הלוג הזה, למשל)

 

[Witztum]

אני חושב שזה ההפך

כלומר, 4^log = O( log*n^2 ) 4^log = (2^2)^log = 2^(2*log) = 2^log(n^2) = n^2 = O( log*n^2 ) בהנחה שהלוג הוא על בסיס 2. אפשר גם להפעיל לוג על שתי הפוקנציות ואז מקבלים: f = log(4^log) = log*log4 g = log(log*n^2) = log(log) + log(n^2) = log(log) + 2log והחל מאן מסויים f<=g

 

[gil levi]

תודה לכולם.

הייתי צריך לדעת את התשובה בשביל לפתור נוסחת רקורסיה, שבסופו של דבר נפתרה בדרך הרבה יותר פשוטה מהדרך הראשונה שניסיתי. מחר כשאני אהיה קצת פחות עייף אני אעבור על הפתרון שהציעו כאן.