שאלה על מיזוג

[tanias1]

שאלה על מיזוג

יש לי שאלה ממבחן שאני לא ממש מצליחה לעלות על הפיתרון שלה: אם מישהו יוכל לעזור לי לגבש רעיון בבקשה.השאלה היא: נתונים n/k מערכים, שבכל אחד מהם k אברים. כל אחד מהמערכים ממויין כבר. מעוניינים למזג את המערכים למערך אחד ממויין באורך n. א)כיצד תעשה זאת בזמן (Θ(n²\k? ב)כיצד תעשה זאת בזמן ((Θ(nlg(n/k? המון המון תודה מראש לעוזרים.

 

[Okuryo]

../images/Emo119.gifנסיון

א) ב-(Θ(n² / k:

for i ← 1 to k ( Θ(k) ) do for j ← 1 to n / k ( Θ(n / k) ) do Insert A[ (j - 1)k + i ] into B[ (i - 1) ⋅ n / k + 1 .. i ⋅ n / k) ], keeping it sorted ( Θ(n / k) ) Θ(k) ⋅ Θ(n / k) ⋅ Θ(n / k) = Θ(n² / k)​

ב) ב-((Θ(n lg(n / k:

for i ← 1 to k ( Θ(k) ) do for j ← 1 to n / k ( Θ(n / k) ) do B[ (i - 1) ⋅ n / k + j ] ← A[ (j - 1)(n / k) + i ] ( Θ(1) ) sort B[ (i - 1) ⋅ n / k + 1 .. i ⋅ n / k) ] ( Θ( (n / k) lg(n / k) ) ) Θ(k) ⋅ ( Θ(n / k) + Θ( (n / k) lg(n / k) ) ) = Θ(k) ⋅ Θ( (n / k) lg(n / k) ) = Θ( n lg(n / k) )​

 

[tanias1]

נסיון

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

 

[Okuryo]

../images/Emo119.gifאין בעיה.

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

 

[גיל14]

לא הבנתי...

אילו תת-מערכים חדשים? אילו הם האברים החדשים? אתה יכול לפרט? כמו כן, נראה שאת ה-Sort אתה עושה בתוך הלולאה. זה לא נותן זמן ריצה של (n/k) כפול n/k log n/k?

 

[Okuryo]

../images/Emo119.gifתת-מערכים

במערך הישן (A) היו n/k תת-מערכים באורך k כל אחד, ובמערך החדש (B) יש k תת-מערכים באורך n/k כל אחד, שאת כולם ממיינים בנפרד. את האיברים אוספים ביחד: n/k האיברים הראשונים ב-B הם האיברים ה-1, ה-k+1, ה-2k+1 וכו' ב-A, האיברים שאחריהם הם האיברים ה-2, ה-k+2 וכו' ב-A, וכו'. את המיון אני עושה בתוך הלולאה שחוזרת k פעמים, אבל לא בתוך הלולאה שחוזרת n/k פעמים (בתוך הלולאה ש-i רץ בה, ולא בתוך הלולאה של j).

 

[גיל14]

עדיין לא הבנתי למה זה נכון,

אני אחשוב על זה מחר. מה דעתך על הרעיון להכליל את המיזוג שעושים ב-Merge Sort, ולמזג שני מערכים עוקבים בכל שלב, ברקורסיה עד שנגיע למערך אחד גדול?

 

[Okuryo]

../images/Emo119.gifזה בערך מה שעשיתי:

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

 

[גיל14]

זה נראה כאילו

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

 

[Okuryo]

../images/Emo119.gifהממ.

נראה לי שלא הבנתי נכון את השאלה כשכתבתי את זה. אתה צודק, זה לא יעבוד כמו שכתבתי. עדיף למזג אותם שניים-שניים.