שאלה במבני נתונים (order of growth)

[gil levi]

שאלה במבני נתונים (order of growth)

השאלה בתמונה. f היא פונ' מונוטונית עולה. אני לא בטוח בפתרון שלי ולמעשה הוא נראה לי קצת חשוד, לכן אני שואל כאן: אני חושב שהטענה נכונה וההוכחה היא כזו: כיוון ראשון: 'O מוכל (שווה) בO: תהי g ב'O, אזי קיים C וN כך שלכל n>N מתקיים: g<C*f zzz ולכן גם: g<=C*f zzz . כיוון שני: O מוכל ב'O: תהי h ב 'O, אזי קיים D וM כך שלכל n>M מתקיים: h<=D*f zzz אבל D*f < 2D*f zzz לכן, אם נבחר C=2D ו N=M נקבל שלכל n>N מתקיים: h<D*f zzz לכן h שייכת גם לO. הכלה דו כיוונית ==> O ו'O שקולות. האם הפתרון נכון? תודה מראש.

 

[gil levi]

וכמובן ששכחתי את התמונה

 

[vinney]

נראה לי בסדר

הפונקציות מקבלות מN לN, אני מניח?

 

[gil levi]

תודה. הפונ' מקבלות ערכים בN,

לא הכרחי שהם מחזירות ערכים בN.

 

[gil levi]

*לא הכרחי = לא בהכרח

 

[vinney]

אז יכולה להיות לך בעיה

כי אם C גדול מ0, אבל ערכי פונקציה שליליים - אתה בברוך.

 

[gil levi]

תודה.

אז עכשיו אני בבעיה. יש לך רעיון? אפשר רמז? תודה מראש.

 

[vinney]

נתתי לך רמז

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

 

[gil levi]

סעיף b של התרגיל

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

 

[gil levi]

הסתדרתי.