פורום קהילת הסטודנטים בטכניון

טכניוני => עזרה בפיתרון תרגילים => נושא נשלח על ידי: ohad על נובמבר 16, 2012, 15:53:03 PM

כותרת: חסמים אסימפטוטיים של פונקציות
תגובה על ידי: ohad על נובמבר 16, 2012, 15:53:03 PM

נתנו לנו 14 (!) פונקציות שונות ומשונות ובקשו לסדר אותם מהקטנה לגדולה (אסימפטוטית) ולהוכיח שאחת היא O של השנייה וכו'.
נשארתי עם הארבע פונקציות הללו:

f_1=3^n,f_2=3^{2^n},f_3=(loglogn)^{logn},f_4=\Pi_{i=2}^n log(i)

ברור לי ש

f_1=O(f_2)

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

(תוספת: אני יודע ש

f_4=O((logn)^n)

אבל איך לחסום אותה מלמטה לא ברור לי)

כותרת: בעניין: חסמים אסימפטוטיים של פונקציות
תגובה על ידי: radagast על נובמבר 16, 2012, 16:37:16 PM

אני לא כל כך מבין בזה, אבל אני דווקא חושב ש-f3 לא שייך לשם, הוא log של log (לוג של לוג של 1 ו-19 אפסים זה פחות מ-4, למשל), זו פונקציה שמתקדמת לאט מאד, והיא בחזקת logn, לא בחזקת n.

בנוגע ל-f4, החל מ-n כלשהו תקבל שהלוג כבר גדול ממספר כלשהו, למשל, עבור n=21 הוא כבר גדול מ-3, ואפשר לחסום אותו מלמטה ע"י [tex]3^n[/tex].

כותרת: בעניין: חסמים אסימפטוטיים של פונקציות
תגובה על ידי: ohad על נובמבר 17, 2012, 19:00:50 PM

תודה, זה בערך מה שעשיתי בסוף,
f3 באמת קטנה יותר וחסמתי ככה ממטה את f4.  :thumbsup:

נגמר התרגיל  :dance: