bienstock פורסם יולי 2, 2013 דיווח שיתוף פורסם יולי 2, 2013 היי לכולם, אז ביקשו מאיתנו ב"מבוא למדמ"ח" בתרגיל האחרון שפורסם, למיין n מספרים כך ש:1. המופע הראשון של האיבר המקסימלי נשאר במקומו. (בה"כ המקום ה-k).2. k האיברים הקטנים ביותר מסודרים לפניו בסדר עולה.3. שאר האיברים מסודרים אחריו בסדר יורד. כל הסיפור צריך להתבצע בסיבוכיות זמן http://www.codecogs.com/gif.latex?$O%5Cleft(%20n%5Ccdot%20%5Clog%20%5Cleft(%20n%20%5Cright)%20%5Cright)$ וסיבוכיות מקום http://www.codecogs.com/gif.latex?$O%5Cleft(%20n%20%5Cright)$,מה שהביא אותי למסקנה, שצריך להשתמש ב-Merge Sort שאלו הגדרות הסיבוכיות שלו, אפילו עבור המקרה הכי גרוע. חשבתי בהתחלה להשתמש איכשהו בהגדרה האיטרטיבית של Merge Sort, אבל היא מוגדרת רק עבור גדלי מערך שהם חזקה של 2 ולא הצלחתי לראות איך אני מרחיב אותה לטיפול במערך מגודל כלשהו. ניסיתי גם עם הגירסה הרקורסיבית אבל זה נראה לי מסובך מדי ומתכון לאסון להיכנס שם לתוך הרקורסיה ולקבוע פתאום איבר כלשהו במערך הזמני במקומו. תודה מראש לכל העוזרים. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
samael פורסם יולי 2, 2013 דיווח שיתוף פורסם יולי 2, 2013 מותר לך ליצור מערך עזר?לעניין מרג' סורט - במקום לחלק מערך בדיוק ל-2 אתה יכול לחלק אותו כמעט ל-2 , מערך בגודל 5 יתחלק למערך בגודל 3 ו-2 ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
bienstock פורסם יולי 2, 2013 מחבר דיווח שיתוף פורסם יולי 2, 2013 מותר לך ליצור מערך עזר? לא נראה לי, כי הדרישה עבור הזיכרון היא http://www.codecogs.com/gif.latex?$O%5Cleft(%20n%20%5Cright)$ ו-merge sort כבר משתמש במערך עזר בגודל הקלט ולכן מותר רק אם זהו מערך בגודל קבוע ללא קשר לקלט. לעניין מרג' סורט - במקום לחלק מערך בדיוק ל-2 אתה יכול לחלק אותו כמעט ל-2 , מערך בגודל 5 יתחלק למערך בגודל 3 ו-2 אני יודע! אבל איך עושים את זה?! הרי הסיבוכיות הנמוכה של מרג' סורט האיטרטיבי נובעת מהחלוקה למערכים בגדלים של חזקות של 2 ואם משנים את זה, זה לא יפגע בסיבוכיות? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
samael פורסם יולי 2, 2013 דיווח שיתוף פורסם יולי 2, 2013 1. שני מערכים בגודל n הם עדיין בסיבוכיות של On2. לא. למעשה, מדי פעם אוהבים לתת שאלה במבחן שבה מספרים על פרופסור שהחליט לשפר את סיבוכיות זמן הריצה של מרגסורט באמצעות חלוקת המערכים ל-3 ולשאול למה (או האם) הוא טועה. איפה אמרו לכם שזה חייב להיות חזקות של 2? תביא לינק. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
bienstock פורסם יולי 2, 2013 מחבר דיווח שיתוף פורסם יולי 2, 2013 http://webcourse.cs.technion.ac.il/234114/Spring2013/ho/WCFiles/234114-09.pdf בעמוד 27 כותרת: מיון באמצעות מיזוגים:Merge-sort. מההסבר שהיה באותו פידיאף בע"מ 29-30 נראה שהסיבוכיות כן נובעת מהחלוקה למערכים בגודל חזקה של 2. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
samael פורסם יולי 2, 2013 דיווח שיתוף פורסם יולי 2, 2013 תעבור על ההסבר של סיבוכיות זמן ריצה ותראה מה קורה כשבמקום סדרות באורך http://www.codecogs.com/gif.latex?2%5Ek אתה לוקח סדרות באורך http://www.codecogs.com/gif.latex?3%5Ekבויקיפדיה המאמר על מרג' סורט כולל איור למה קורה כשממיינים מערך בן 7 איברים. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
bienstock פורסם יולי 2, 2013 מחבר דיווח שיתוף פורסם יולי 2, 2013 אוקיי. תודה רבה על העזרה. יום טוב. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
הודעות מומלצות
הצטרפות לשיח
באפשרותך לשלוח הודעה כעת ולהירשם מאוחר יותר. אם ברשותך חשבון, ניתן להתחבר עכשיו לשליחת הודעה דרך חשבונך.
הערה: הודעתך דרושה לאישור הנהלה לפני הצגתה.