littlerunaway פורסם יולי 17, 2014 דיווח שיתוף פורסם יולי 17, 2014 אני לא כל כך מבינה איך עושים את סעיף ב'. (את א' עשיתי עם מערך ועצי AVL).http://i.imgur.com/uoaEpsU.jpghttp://i.imgur.com/mNChVAx.jpg ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 17, 2014 דיווח שיתוף פורסם יולי 17, 2014 זה נראה לי דומה להוכחה ההיא של הunion בunion-findעבר קצת (הרבה...) זמן מאז סמסטר 3, אבל לפי מה שאני זוכר זה היה משהו כזה- כל פעם מוסיפים עץ קטן לעץ הגדול.החסם על כמות האיחודים הוא לוגריתמי, כי המקרה הכי "גרוע" הוא שכל פעם מאחדים 2 עצים באותו הגודל.כלומר, כל לקוח עובר בממוצע לוג פעמים לעץ אחר.כמו-כן, הפעולה של להעביר לקוח לוקחת logn במקרה הכי גרוע.סה"כ log^2(n) zz. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 זה נראה לי דומה להוכחה ההיא של הunion בunion-findעבר קצת (הרבה...) זמן מאז סמסטר 3, אבל לפי מה שאני זוכר זה היה משהו כזה- כל פעם מוסיפים עץ קטן לעץ הגדול.החסם על כמות האיחודים הוא לוגריתמי, כי המקרה הכי "גרוע" הוא שכל פעם מאחדים 2 עצים באותו הגודל.כלומר, כל לקוח עובר בממוצע לוג פעמים לעץ אחר.כמו-כן, הפעולה של להעביר לקוח לוקחת logn במקרה הכי גרוע.סה"כ log^2(n) zz.הבנתי את התשובה. אבל אני לא מבינה למה החסם על כמות האיחודים הוא לוגריתמי (אני יודעת שזה נכון, זה הוזכר פעם באיזו הרצאה/תירגול). הרי יכול להיות מצב שבו אני כל פעם מאחדת עם עץ של 1, ואז אני מקבלת n-1 איחודים, לא? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 אם כל העצים בגודל 1 אז כל צומת מחליף עץ רק פעם אחת. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 אם כל העצים בגודל 1 אז כל צומת מחליף עץ רק פעם אחת.אבל גם אם כל צומת מחליף עץ רק פעם אחת, עדיין מספר האיחודים הוא לא לוגריתמי. או שיש פה משהו שאני לא מבינה. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 נכון אבל תחשבי על הסיבוכיות המשוערכת במקרה שלך.כל צומת מחליף עץ רק פעם אחת. אבל הפעולה של האיחוד בין 2 עצים במקרה הזה היא ממש logn. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 נכון אבל תחשבי על הסיבוכיות המשוערכת במקרה שלך.כל צומת מחליף עץ רק פעם אחת. אבל הפעולה של האיחוד בין 2 עצים במקרה הזה היא ממש logn.איחוד בין 2 עצים זה logn אבל אני עושה n-1 איחודים כאלה (במידה ואני מאחדת את כולם לעץ אחד). אז אני לא מקבלת nlogn במקום 2^(logn)? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 אבל זה הסיבוכיות של n איחודים. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 אז על מה הם מדברים בסעיף ב'? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 את מסכימה שאם יש תור אחד גדול בגודל n-1 ויש תור נוסף בו יש לקוח אחד, הסיבוכיות היא log(n) zz?זה פשוט מקרה פחות "יקר".הסיבוכיות המשוערכת יוצאת עם ריבוע כי בהסתברות גבוהה יוצא שמאחדים 2 תורים בעלי גודל דומה, ואז צריך לבצע את פעולת ההכנסה מספר כלשהו של פעמים כתלות בגודל התור, וכאן נכנס המבט הזה של כמה פעמים כל אחד משנה את התור שלו. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 שאלה נוספת:http://i.imgur.com/ITBwDIB.jpgהצלחתי להוכיח ש T (n)=omega(2^n)zz. אבל אני לא מצליחה להוכיח את הצד השני של ה O(2^n)zz ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
602 פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 נדמה לי שמשפט המאסטר תופס כאן (עבור הפונ' שבמקרה של n>=10).יש בתרגול עליו דוגמה לפונקציה דומה. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 נדמה לי שמשפט המאסטר תופס כאן (עבור הפונ' שבמקרה של n>=10).יש בתרגול עליו דוגמה לפונקציה דומה.אבל מה אני עושה עם ה n-1 הזה? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 למה לא אינדוקציה? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 למה לא אינדוקציה?אינדוקציה על מה? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
3p1n פורסם יולי 18, 2014 דיווח שיתוף פורסם יולי 18, 2014 זה מבנה, לא לוגיקה. אין כאן אינדוקציה על שום דבר חוץ מ n...תעשי בסיס n=9 ואז n=10 ותראי שזה באמת מקיים את החסם.אח"כ תניחי נכונות עבור n כלשהו, שעבורו החסם באמת עובד: http://www.codecogs.com/gif.latex?T(n)%20אח"כ תיקחי את http://www.codecogs.com/gif.latex?T(n+1) ותראי שמתקיים http://www.codecogs.com/gif.latex?T(n+1)%20 עבור n>10. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
littlerunaway פורסם יולי 18, 2014 מחבר דיווח שיתוף פורסם יולי 18, 2014 אוקיי, קיבלתי דבר כזה:איך אני מסיימת את זה בסוף? http://i.imgur.com/lry7kjA.jpg ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
הודעות מומלצות
הצטרפות לשיח
באפשרותך לשלוח הודעה כעת ולהירשם מאוחר יותר. אם ברשותך חשבון, ניתן להתחבר עכשיו לשליחת הודעה דרך חשבונך.
הערה: הודעתך דרושה לאישור הנהלה לפני הצגתה.