מס שאלות

מנהל: TA_Isana

שלח תגובה
stavsap
הודעות: 37
הצטרף: 12:41 28/12/2009

מס שאלות

שליחה על ידי stavsap » 23:17 20/05/2010

אני יודע שחפרו על זה אבל עדין לא מובן...מה הכוונה במקרה הממוצע? מהו המקרה האידיאלי ומהו המקרה הגרוע בפונקציה הראשונה של int(a,k) f
אם יש לי k ערימות ואני צריך להכניס n איברים האם המקרה הממוצע עומד בזמן של ההכנסה O(n*logk) f? האם יש הבדל בין שימוש של ערימות לבין שימוש בעצי אי בי אל עם מצביעים למקסימום ולמינימום בכל עץ? הרי זמני איתחול לערימה ריקה ולעץ ריק הוא זהה(תקנו אותי אם אני טועה)? איזה מימוש יתקבל? אשמח לתשובות :)
ומה הבעיה בלהשתמש בcounting sort? אשמח לפירוט כי הרי זה מיון ליניארי ככה נקבל O(n) f

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: מס שאלות

שליחה על ידי TA_Ariel » 23:35 20/05/2010

להכניס n איברים לערימות זה o(n( במקרה הגרוע
בעצם k*o(n/k).

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

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: מס שאלות

שליחה על ידי TA_Ariel » 23:39 20/05/2010

לחלק השני של השאלה- יש הבדל גדול בשימוש בעצים כי האתחול הוא לא של עץ ריק או ערימה ריקה אלא של מבנה עם n איברים,
תזכור שbuild-heap זה o(n) ואתחול עץ הוא מnlogn.
לגבי counting-sort אי אפשר להשתמש בו אלא אם כן יש לך הנחות על גודל המפתחות מה שאין לך במקרה הזה.

stavsap
הודעות: 37
הצטרף: 12:41 28/12/2009

Re: מס שאלות

שליחה על ידי stavsap » 02:16 21/05/2010

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

shaivak
הודעות: 23
הצטרף: 19:54 27/12/2009

Re: מס שאלות

שליחה על ידי shaivak » 17:08 21/05/2010

ב counting sort אי אפשר להשתמש מפאת חוסר ההנחות הנ"ל אבל radix sort מניח רק שהמספרים טבעיים,כמו בעבודה, בו אפשר להשתמש?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: מס שאלות

שליחה על ידי TA_Ariel » 18:49 21/05/2010

אי אפשר להתשמש בשום מיון בזמן לינארי כי,כמו שראיתם בהרצאה, לא ניתן למיין בזמן לינארי במקרה הכללי. אין שום הנחות על הקלט ולכן לא ניתן להתשמש במיון כזה.
זמן הריצה של radix-sort תלוי במספר הספרות.

shaivak
הודעות: 23
הצטרף: 19:54 27/12/2009

Re: מס שאלות

שליחה על ידי shaivak » 20:38 21/05/2010

אבל מצד שני ביקשתם זמן ריצה במקרה הממוצע, במקרה הממוצע buscket sort ממיין בזמן ליניארי ללא הנחות, כי במקרה הממוצע המספרים מפוזרים באופן די אחיד, לא?
חוץ מזה בקשר ל רדיקס סורט, אין חשיבות לכך שגודל המספרים מוגבל במחשב ולכן גם מספר הספרות מוגבל לקבוע?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: מס שאלות

שליחה על ידי TA_Ariel » 22:00 21/05/2010

קודם כל בקשר לחלק שני, מהטיעון הזה נובע שאין טעם לכל מה שלמדת עד עכשיו, הכל קבוע.
הניתוח הוא לא בשביל מחשב ספיציפי.

לחלק הראשון- פה התשובה יותר עדינה, הבעיה הראשונה היא שכשאומרים בממוצע לא מתכוונים להתפלגות אחידה אלא לרב ההתפלגויות.
למשל באלג למציאת חציון הממוצע הוא על פני הבחירות האקראיות של הpivot ולא על הנתונים. אז זו סיבה ראשונה.
סיבה שניה היא שבbucket-sort צריך למצוא דרך להכניס את המפתחות לדליים. הבעיה היא שגם אם הם מתפזרים בצורה אחידה, צריך לדעת את טווח המפתחות בשביל לעשות את זה.

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

shaivak
הודעות: 23
הצטרף: 19:54 27/12/2009

Re: מס שאלות

שליחה על ידי shaivak » 17:00 23/05/2010

כן אבל אני יכול לרוץ על המערך בזמן ליניארי ולמצוא את המינימום והמקסימום ולהשתמש בהם כטווח, מה הבעיה עם זה?
אתה יכול בבקשה להסביר מה הכוונה ב"רב ההתפלגויות"?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: מס שאלות

שליחה על ידי TA_Ariel » 19:06 23/05/2010

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

שלח תגובה

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