שלום בבקשה עזרה בתרגיל

[ron369]

מצטער על העצלנות, אבל אני מרגיש

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

 

[gil levi]

נדמה לי שכן יש טעות.

כי הפונקציה היא למעשה לא פונקציה. אם ניקח n=8, אז ניתן לכתוב את 8 כ 8/1 וגם כ 16/2. עבור 8/1 מקבלים 6 ועבור 16/2 מקבלים 0 ואז f(8) zzz הוא לא יחיד. צריך להגדיר אותה אחרת, אולי לקחת את הb הקטן ביותר שמתאים או משהו כזה.

 

[ron369]

הטעות שלך היא מינורית

אתה פשוט מניח שהנוסחה שהוא כתב נכונה, אבל הוא התבלבל בה מעט, ולכן הטעות שלו נגררה. אגב, טעויות כאלה הן כנראה *הכי אכזריות*, גם כי התשובות שיוצאות (כמו במקרה זה) שגויות לעיתים לחלוטין, וגם כי קשה מאד להבחין בהן, בהתחלה או בכלל. במקרים כאלה צריך פעמים רבות "מישהו מבחוץ". בכל אופן, שים לב שבנוסחה שלו מתקיים:

f(n/b)= n/b - (bn)/4​

אבל זה צריך להיות, בעצם:

f = n - n/4 f(m) = f((n/b))= (n/b) - (n/b)/4 = n/b - n/(4b) = n(1/b - 1/4b) = O(n/b)​

ועבור b קבוע

= O(f) = O​

אני חושב שהוכחתי את השקילות, לא? אלא אם כן התבלבלתי איפה-שהוא?

 

[gil levi]

תגובה.

לא הבנתי מדוע צריך להיות: f= n - n/4. תוכל להסביר?

 

[amirxbox]

צודק טעות שלי . ../images/Emo10.gif תודה תודה

תודה על ההפרכה חשבתי על זה יותר משעה .

 

[ron369]

מעולה. עכשיו תחפש דוגמא נגדית אחרת

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

(הכל זה, כמובן, הצעות לתרגילים שאולי ילבנו אצלך את הנושא, ויחפו על כך שגיליתי לך את התשובה

) בהצלחה

 

[amirxbox]

תודה אבל לא נראה לי חח

יש כל כך הרבה עומס ואני שמח שזה התרגיל שחתם את סיום העבודה במבני נתונים (ד"א את שאר התרגילים של ניתוח זמני ריצה אני מקווה ומאמין שעשיתי די טוב) לקחתי כדוגמא סותרת את 2ⁿ תודה לכל העוזרים!

 

[inferno3]

שאלה קטנה בקשר לדוגמא שנתת

אתה יכול להסביר לי איך בדיוק הדוגמא שנתת מפריכה את הטענה הזו?

 

[ron369]

כן, בטח (אבל זה ארוך! ../images/Emo3.gif ../images/Emo13.gif)

נניח בשלילה שקיימים c, n0, N, כך שלכל n>N מתקיים ש:

n_0 * e^x/2 + c > e^x​

אבל ברור שזה לא נכון, כי למשל אם נקח x=2(c+n0) (לא טרחתי להצמד), אז נקבל ש:

n_0 * e^x/2 + c > e^x <==> n_0 * e^2(c+n0)/2 + c > e^2(c+n0) <==> n_0 * e^(c+n0) + c > e^2(c+n0) <==> עבור n0,c גדולים מספיק n_0 * e^(c+n0) + c > e^((c+n0)+(c+n0)) <==> n_0 * e^(c+n0) + c > e^(c+n0)*e^(c+n0)) <==> n_0 * e^(c+n0) + c > c+e^(n0)*e^(c+n0)) <==> n_0 * e^(c+n0) + c > n0*e^(c+n0) +1 + c סתירה.​

סתירה.

במילים אחרות: lim e^x / e^(x/2) = n->oo lim e^x / (e^x)^1/2 = n->oo lim (e^x)^1/2 = oo n->oo​

מש"ל. (וכמובן שמכלילים את זה לכל חזקה כזו). בכל אופן, יותר מעניין לדעתי זה ש: נניח שנתונה פונקציה שמקיימת לכל x את f(x) = 5*f(x/2) + 5 אזי (נראה לי ש)זו פונקציה פולינומיאלית בהכרח! למה? אני חושב שמשפט האב מוכיח זאת.

 

[inferno3]

תודה רבה על ההסבר הממצה

שיחקת אותה. שבת שלום.

 

[vinney]

למה אתה סתם מסבך אנשים?

קח פונקציה 2 בחזקת N חישוב הוא כזה:

f=2^n f(n/2)=2^(n/2) lim (f/f(n/2))= lim ((2^n)/(2^(n/2))) = lim (2^(n/2)) = infinity מש"ל​

גבול באינסוף, כמובן.

 

[vinney]

(עם קצת ניפנופי ידיים, כמובן)

 

[ron369]

טרחת בכלל לקרוא את ההודעה שלי?

באמת, מצטער על התוקפנות.

 

[vinney]

היה נראה לי מסובך

יותר מדי eים וxים

כתבת אותו דבר, אם הבנתי נכון, רק הוכחת את זה קצת יותר טוב ממני

בעיקרון זה נכון לכל פונקציה מעריכית, אז למה בחרת e דווקא?

 

[ron369]

הטענה ש-e "מושלם" לא מספיקה? ../images/Emo13.gif

אגב, ל-e באמת יש כמה יתרונות, בפרט, יכולתי להעמיד פנים ש-e מציין מעריך כלשהו הגדול מ-1. למען האמת, אני נוטה לעבוד עם e במקרים כאלו, למקרה שיהיו מעורבות נגזרות כלשהן. (ולמה יותר טוב? היה נראה לי שעשינו בדיוק את אותה הדרך, חוץ מזה שהשתמשתי ב-e, וכתבתי קצת יותר ארוך

)