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

[amirxbox]

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

2. f=(f(n/2)) .​

צריך להוכיח או להפריך.

 

[amirxbox]

הסימן שחסר זה טטה.

 

[vinney]

תלך לפי ההגדרה

עם תחשיב גבולות. תנסה, תגיד אם תסתבך.

 

[amirxbox]

תודה בדיוק ככה ניסתי ולא הלך

 

[vinney]

אז תרשום פה מה עשית

שנראה מה לא הולך לך

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

 

[amirxbox]

פשוט כתבתי את ההגדרה

צ"ל

c*f(n/2)<= f f<=f(n/2)​

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

 

[vinney]

כדי שיהיה טטה

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

 

[vinney]

בעצם, לא צריך שום כלל

2 בחזקת N, יצטמצם לך יפה.

 

[amirxbox]

לא למדנו בדרך של גבולות

אלא רק ע"י חסימת C ו N0 . יכול להיות שלא הבנתי אותך או אתה אותי. הפונקציה כאן היא לא נתונה , כמובן להפריך ע"י שתי פונקציות בסדר גודל של N זה אפשרי אבל להוכיח בד"כ הוכיחו בהרצאות ע"י הגדרה ולא בחירת פונקציות. (בעצם אף פעם לא למדנו הוכחה ע"י בחירת פונקציות).

 

[amirxbox]

רעיון שעלה לי עכשיו

הפרכה: f(n/b)= n- (bn)/4 f(n/1)= n-0.25 = O f(n/2)= n/2-n/2=0 =! O כ ש O כאן זה טטה. האם הפתרון נכון או שלא הבנתי נכון את התרגיל?

 

[ron369]

זה לא נכון (גם הטענה, וגם הדוגמא)

דוגמא נגדית: f(x) = 5^5x הפרכה. סיבה ששלך לא טוב: מה זה ה-b הזה? ומה היו החישובים שלך? איך הגעת ל-0? :-|

 

[gil levi]

הייתה לו טעות חישוב קטנה

"הפרכה: f(n/b)= n/b - (bn)/4 f(n/1)= n-0.25 = O f(n/2)= n/2-n/2=0 =! O כ ש O כאן זה טטה. האם הפתרון נכון או שלא הבנתי נכון את התרגיל?" עכשיו זה נכון?

 

[ron369]

אני חושב שלא

שים לב שה-bn צריך להיות n/b, אם הבנתי נכון את התרגיל. לא?

 

[gil levi]

לא נראה לי.

מה הבעיה עם הbn בדיוק?

 

[ron369]

שזה צריך להיות n/b!

 

[ron369]

תראה, אם יש לך פונקציה כלשהי,

ואתה רוצה לחלק את n ב-2, אז למה שתכפיל אותו לעזאזל ב-2? מה אני לא רואה פה?

 

[gil levi]

שויסה שויסה.

תסביר לי לאט לאט.

f(n/b)= n/b - (bn)/4 f(n/1)= n-(n/4) = Θ f(n/2)= n/2-(2n/4)= n/2 - n/2= 0 =! Θ​

מה לא בסדר?

 

[ron369]

הנוסחה ההתחלתית.

 

[gil levi]

סתם ולא פירש?

מדוע היא לא נכונה? כי ממילא f מוגדרת מהמספרים הטבעיים ולכן b=1 תמיד?

 

[ron369]

לא, לא...