04-05-2009, 17:54
|
 |
|
|
חבר מתאריך: 21.12.04
הודעות: 30,021
|
|
לא ברור לי למה הכוונה ב ** שאתה משתמש. זה אמור להיות 'חזקה'?
כשאתה בודק שאיפה אסימפטוטית, אתה בודק מה קורה במקרה ה n-י.
אתה לא מתחיל לסכום את כל האפשרויות עד ל- n אלא מה קורה במקרה ה n-י כאשר n שואף לאינסוף.
אז כמו שאמרת, במקרה ה n-י שמים איבר אחד בתור (עלות של 1), מעבירית n-1 לאותו התור (מכאן בדיוק עלות של n) ואז בחזרה, מעבירים את הכל לתור הראשון.
עכשיו, כיוון שמדובר בשתי לולאות פשוטות (לא מקוננות), סוכמים את עלות שתי הלולאות יחד.
התוצאה היא, כמו שכתבתי למעלה - (O(2n שזה אסימפטוטית חסום ע"י (O(n.
בנוגע לדרישה הלניארית, אתה צודק... לא יודע איך פיספסתי את זה קודם, ודווקא עברתי על ההודעה כמה פעמים... חוסר תשומת לב 
|
ראשי
צ'אט
מצב כלאיים
