כיצד מוצאים חסם עליון?

[tamir pop]

כיצד מוצאים חסם עליון?

נתבקשתי למצוא חסם עליון הכי טוב שאפשר לפונקציה הבאה:

f = שורש שביעי של n + [log]^11​

אשמח אם מישהו יוכל לכוון אותי להסברים כיצד ניגשים לפונקציה כזאת. מה הרעיון בלמצוא חסם וכו'.

 

[gil levi]

הפתרון אמור להיות במונחי O גדול?

 

[tamir pop]

כן, אני מניח

בינתים, עשיתי משהו כזה:

O(שורש שביעי של n) = O O(הביטוי עם הלוג) = O(logn) לכן: סה"כ אצלי: o(n+logn)​

בהנחה שהבנתי מה רצו ממני כאן. כל הרעיון הוא לשחק עם סדרי גודל?!

 

[gil levi]

פעם ראשונה שאני נתקל בשאלה כזו.

למה חסמת את O(שורש שביעי של n) ב O של n? זה לא הדוק. יכולת לסחום את זה בO(שורש ריבועי של n) באותה מידה. דבר שני, הערה קטנה וסתמית:

O(n+ logn) = O​

לדעתי מה שאתה אמור לעשות זה לבדוק איזה מהביטויים אסימטוטית גדול יותר- השורש שביעי או זה עם הלוג, ואז הפתרון יהיה O של הגדול מביניהם.

 

[tamir pop]

OK

אני יודע לפי סדרי גודל שהשורש n יותר גדול מהלוג של n . לכן, התשובה כנראה שורש של n . תאמין לי שגם אני לא מבין מה הקטע בשאלה הזו.

 

[טיורינג]

אני לא מכיר סוג כזה

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