צריכה עזרה בשתי שאלות...

[משיגנע מיידלע]

צריכה עזרה בשתי שאלות...../images/Emo205.gif

(עם דגש על השאלה השנייה) תודה רבה

מצורפות >> (במקום ? ב-ב' זה <)

 

[טום הוק]

עזרה קטנה לשאלה 2

אני לא משוכנע לחלוטין בפתרון הזה למרות שהוא נראה לי הגיוני אז ככה, לגבי סעיף א לאחר החלוקה יש לנו (n חלקי k) מערכים כל אחד באורך k. הסיבוכיות של InsertionSort היא (O של n בריבוע). מכאן שלמיין כל מערך בנפרד לוקח (O של k בריבוע). ישנם (n חלקי k) מערכים ולכן בסה"כ מיון המערכים לוקח (O של kn). לגבי סעיף ב כרגע כבר יש לנו (n חלקי k) מערכים ממוינים. נניח שהם ממוינים בצורה כזאת שבה בכל מערך האיברים הקטנים יותר נמצאים בתחילת המערך. כדי למזג אותם למערך אחד באורך n צריך למצוא כל פעם את האיבר המינימלי מבין כל המערכים. היות והאיברים המינימליים נמצאים בתחילת המערך אנחנו צריכים למצוא את המינימלי מבין (n חלקי k) איברים שזה לוקח (O של לוג(n חלקי k)) את התהליך אנחנו צריכים לבצע n פעמים. מכאן שהמיזוג לוקח בסה"כ (O של n כפול לוג(n חלקי k)). לגבי סעיף ג לדעתי ה- k המקסימלי הוא (לוג n) אבל אני לא מומחה גדול. ברור ש- (לוג n) הוא יכול להיות אבל לא נורא ברור שהוא בהכרח המקסימלי. לדעתי הוא המקסימלי כי אם k יהיה איזהשהו פולינום אזי רק ה- kn מסעיף א יהיה כבר יותר מ-(n כפול לוג n). אם איזה משהו לא ברור אז תשאל(י) שוב.

 

[משיגנע מיידלע]

אוקיי...אני אנסה.../images/Emo205.gif

תודה

 

[gil levi]

שאלה 1- סעיף א'.

(אני חולה, ויש לי זכרונות רעים ממבני נתונים, אז ברשותך אוותר לעצמי על סעיף ב'). זה לא נכון. תראי, נתון לך ש f חוסמת מלמעלה את g. מדוע שגם g תחסום מלמעלה את f? אם זה היה מתקיים אז f ו g היו טטא אחת של השניה וזה לא הכרחי. דוגמא נגדית: g=n, f=n^2 ובעצם כל שתי פונ' שהן לא טטא אחת של השניה יתאימו. השאלות האלו הן שאלות של תיכון או אנ' אגב?

 

[gil levi]

*אנ' = אונ'.

 

[משיגנע מיידלע]

תודה רבה ../images/Emo13.gif../images/Emo205.gif

אני דווקא לומדת את זה באלגוריתמים...