שאלה תאורטית על merge

[shaks]

השאלה ניתנה במסגרת קורס של מבני נתונים.

 

נתונים N מערכים בגודל N כל אחד.
מרחיבים את שגרת MERGE (זאת האחראית על מיזוג המערכים בmergesort), כך שבמקום למזג שני מערכים תמזג N מערכים למערך אחד.
תאר (לא פסודו קוד רק תיאור) כיצד ניתן לעשות זאת ומהו זמן הריצה הדרוש לכך (של merge בלבד!).

אני יודע שבמימוש נאיבי פשוט נוסיף עוד מצביעים כמס המערכים וכו'.
השאלה שלי היא מה יהיה זמן הריצה עבור האלגוריתם הזה?

תודה לכל העוזרים 

[TheReaper]

דבר ראשון אין באמת צורך שMERGE תמזג N מערכים בו זמנית. הרי לא משנה כמה מערכים/איברים תקבל, mergesort תפרק אותם ותחבר אותם מחדש רק שהפעם תקבל במקום N איברים בודדים N^2 איברים בודדים

 

בנוגע לשאלה עצמה, שמחייבת שMERGE יקבל N איברים בודדים ויחבר אותם, יש בעיה אחת גדולה:

התוצאה הסופית של החיבור היא מערך בגודל N, נגיד והכנסו את 2 האיברים הראשונים, איפה נשים אותם? אנחנו לא יודעים מה המיקום הסופי שלהם כי יש עוד N-2 איברים לסדר. פתרון נאיבי אומר שנצטרך להשתמש פה במיון נוסף כדי להכניס את כל האיברים למקום (משהו ביעילות  NLOGN מכיוון שאין מידע נוסף על האיברים) 

[shaks]

הבנת לא נכון את השאלה, השאלה היא לא על merge sort אלה על אלגוריתם merge.

רוצים לקחת את אלגוריתם merge ולשנות אותו כך שיידע להתמודד עם N מערכים ויידע למזג N מערכים בגודל N למערך אחד בגודל N^2.

 

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

תודה.

 

[TheReaper]

זה שכתבתי את המילה mergesort מפריע לך?

דיברתי על החלק של האיחוד במיון הזה

[shaks]

 

ציטוט של Diabetus

זה שכתבתי את המילה mergesort מפריע לך?

דיברתי על החלק של האיחוד במיון הזה

לא מפריע לי כלל אבל התשובה שנתת אינה בכיוון.

ראשית כל, merge זה אלגוריתם שמסתמך על כך שהמערכים שהוא מקבל ממוינים ככה שאין צורך למיין.

שנית, אני אכתוב את הפיתרון ואולי דרכו תבין את מה ששאלתי.

שוב, השאלה היא ברמת התאוריהה ולא ברמת הפרקטיקה:

יש להחזיק N מצביעים אחד לכל מערך, ליצור מערך גדול באורך N*N ליצור לולאת FOR שרצה על המערך הגדול, בכל ריצה של לולאת הFOR יש למצוא את האיבר המינימלי מבין מצביעי המערכים ולהציבו במערך הגדול במקום של האינדקס של לולאת הFOR ואז לקדם את המצביע של המערך שאיברו המינימלי נלקח.

סה"כ זמן הריצה הוא O of n^3 מכיוון שישנה לולאה שרצה N^2 פעמים ובכל איטרציה יש N השוואות.

 

[TheReaper]

זה הפתרון הנאיבי ביותר.

או שאתה לא צריך למיין ואז אין בכלל מה לדבר על יעילות

או שאתה צריך למיין ואז אני לא רואה מניעה למה לא להשתמש במיון מוכר יותר (למשל mergesort)

 

[Kurt]

אפשר לסגור את זה בזמן ריצה לוגריתמי אם מעניין אותך 

[TheReaper]

המצאת אלגוריתם מיון חדש בזמן שלא הסתכלתי?

[Kurt]

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

[שניצל]

בהנחה שכל אחד מהמערכים ממוין, אפשר לפתור את הבעיה ב-N²logN.

[TheReaper]

ציטוט של Kurt

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

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

 

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

 

בכל מקרה השאלה הזאת מנוסחת באופן נוראי- בתכלס אם מותר לי לעשות מה שאני רוצה נשתמש בערימת מינימום ונסגור את הסיפור בN^2LOGN בדיוק כמו ששניצל טען

אבל אז זה כבר לא האלגוריתם "הקלאסי" של merge ורצו שנרחיב את השגרה של merge

אם צריך "לשמור על הרוח של merge" אז  הפתרון כנראה יהיה O^3 כי זה פשוט יהיה השוואות בין N איברים במקום 2 באלגוריתם המקורי

 

השאלה הייתה אמורה להיות כתובה כ"רשום אלגוריתם למיון N מערכים ממויינים באורך N למערך אחד באורך N^2"

[שניצל]

לא צריך ערמת מינימום, אפשר N²logN בצורה פשוטה יחסית ובלי מבנים מתקדמים.

[TheReaper]

זה פשוט היעילות של מיון רגיל. אבל ערימה לא תיתן יעילות טובה יותר? או שזה רק הקבוע

 

עריכה- נגיד והיה K מערכים באורך N אז מיון רגיל היה יותר לי N^2logn ושימוש בערימה היה נותן לי N^2logk

אני מניח שהשיטה שלך תיתן את היעילות השנייה אבל חוץ משימוש בערימה אני לא מכיר דרכים

[שניצל]

אם יש K מערכים באורך N אז הסיבוכיות היא KNlogK.

 

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

בשלב הראשון יש לך K/2 זוגות של מערכים באורך N, ולכן צריך כ-2N * K/2 = KN פעולות.

בשלב השני יש לך K/4 זוגות של מערכים באורך 2N, ולכן שוב צריך 4N * K/4 = KN פעולות.

מספר השלבים הוא logK, ולכן הסיבוכיות הכוללת היא NKlogK.

אם K>N אז אכן עדיף להשתמש בערימה.

[shaks]

ציטוט של שניצל

אם יש K מערכים באורך N אז הסיבוכיות היא KNlogK.

 

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

בשלב הראשון יש לך K/2 זוגות של מערכים באורך N, ולכן צריך כ-2N * K/2 = KN פעולות.

בשלב השני יש לך K/4 זוגות של מערכים באורך 2N, ולכן שוב צריך 4N * K/4 = KN פעולות.

מספר השלבים הוא logK, ולכן הסיבוכיות הכוללת היא NKlogK.

אם K>N אז אכן עדיף להשתמש בערימה.

 

אתה צודק.

סעיף א' של השאלה הוא זה שכתבתי קודם ובו נדרשתי רק להרחיב את merge בצורה שאמרתי מקודם.

סעיף ב' של השאלה מבקש בדיוק את זה,למיין N מערכים בגודל logN  ואת השאלה פתרתי עם ערימת מינימום בצורה שהוזכרה כמו מקודם.

 

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