מס שאלות

[stavsap]

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

[TA_Ariel]

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

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

[TA_Ariel]

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

[stavsap]

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

[shaivak]

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

[TA_Ariel]

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

[shaivak]

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

[TA_Ariel]

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

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

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

[shaivak]

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

[TA_Ariel]

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