בוחן 2007

מנהל: TA_Isana

שלח תגובה
lironsam
הודעות: 25
הצטרף: 23:12 04/12/2009

בוחן 2007

שליחה על ידי lironsam » 20:19 20/04/2010

בבוחן 2007 שאלה 1
T(n)= 1 n< = 3
T(n) =T(n-1)+(n-2)+ (n-3) n>= 3

הגעתי לחסמים O(n^3) ו
Ω(3^n/3)

עכשיו תשובות 1,3,5 באמת מתאימות לחסמים האלה ( אני לא מדברת כרגע על f(n) - תשובות 6 ו7)

אבל למה תשובה 4 (O(3^(n/4)*n^0.5
לא מתאימה?

naknik
הודעות: 11
הצטרף: 11:32 02/04/2010

Re: בוחן 2007

שליחה על ידי naknik » 20:44 20/04/2010

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

lironsam
הודעות: 25
הצטרף: 23:12 04/12/2009

Re: בוחן 2007

שליחה על ידי lironsam » 20:53 20/04/2010

תודה :)

palpal
הודעות: 7
הצטרף: 21:39 02/11/2009

Re: בוחן 2007

שליחה על ידי palpal » 11:21 21/04/2010

כן אבל אתם יכולים להגיד למה התשובות 3 ו5 נכונות?

lironsam
הודעות: 25
הצטרף: 23:12 04/12/2009

Re: בוחן 2007

שליחה על ידי lironsam » 23:51 21/04/2010

תנסה לחסום את הביטוי משני הצדדים...
אם תחסום את f(n|) מלמטה ( שים לב שכשn קטן מ3 T(n)=2 אז כשאתה משווה את המשוואה שאתה מקבל אחרי i איטרציות ... תשווה אותה ל2
אתה תקבל את תשובה 5
לגבי תשובה 3 - פשוט תשווה את כל התשובות עם החסמים שקיבלת ותראה שהחסם העליון של T(n) קטן מתשובה 3 ז"א שאם החסם העליון שקיבלנו הוא O של T(n) אז תשובה 3 היא בטוח O של T(n) (טרנזיטיביות..)


אם זה לא מובן... אני אעלה סריקה....

שלח תגובה

חזור אל “- מבני נתונים 2010”