מבני-נתונים ומבוא לאלגוריתמים - שאלה מבחינה

[thankful]

מבני-נתונים ומבוא לאלגוריתמים - שאלה מבחינה

להלן שאלה מבחינה ומחשבותיי (אינטואיציות בלבד) לגביה : נתונה קבוצה S של n מספרים ממשיים : ידוע שב - S קיימים (Theta(lgn ערכים שונים בלבד (עם כפילויות) . בנוסף , נתון מספר ממשי z . כתבו אלגוריתם למציאת זוג מספרים x,y ב - S , המקיימים : x+y = z . זמן הריצה הנדרש של האלגוריתם הוא (Theta(n lglgn . מחשבותיי לגבי השאלה : האם עלינו למיין את איברי הקבוצה תחילה ? השאלה מזכירה (לפי זמני הריצה) שצריך לבצע מיון ב - NLGN , כאשר במקום ה - N הימני יש לנו LGN (מהנתון שקיימים תטא LGN ערכים שונים בלבד ?) . ואולם , אם נמיין את איברי הקבוצה תחילה (במיון-מיזוג) , זמן הריצה אמור להיות NLGN (שהרי מיון-מיזוג רץ בכל מקרה בזמן NLGN) . אבל אז אכלנו אותה , כי אנו נדרשים בשאלה לזמן מיון כולל של NLGLGN *בלבד* . האם מיון-ערימה ישפר את זמן הריצה של NLGN ? חוששני שלא ... אז אולי לא צריך למיין ? ואם לא צריך למיין , איך נוכל למצוא זוג מספרים המקיים x+y = z בסיבוכיות הנדרשת ? בברכה , ליאור .

 

[vinney]

ניתוח עלות המיון שלך לא נכון.

זה nloglogn, לא nlogn. זאת אומרת, הניתוח שלך נכון, האלגוריתם לא

 

[thankful]

אינטואיציה נוספת , חשבתי אתמול : חיפוש בינרי

נניח כי איננו צריכים למיין : הרי נתונה לנו *קבוצה* S , ובקבוצה (מעצם הגדרתה כקבוצה) אפשר להסתכל על האיברים בכל סדר שהוא (נניח שמסתכלים עליהם בסדר הממויין) . (אמנם , בקבוצה מעצם הגדרתה כקבוצה , כל איבר נספר פעם אחת , ואילו כאן בשאלתנו יש כפילויות . נעזוב זאת בצד , ונסתכל על איברי הקבוצה , כפי שהם מופיעים , בסדר ממויין - ללא צורך להשתמש במיון .) אם כן , לאחר שאנו מסתכלים על איברי הקבוצה בסדר ממויין : לכל איבר s ב - S , נחפש ב - S את z-s באמצעות חיפוש בינרי (כלומר z פחות s , כדי שסכום האיברים המבוקש יהיה z) . 2 האיברים שסכומם הוא z יהיו שני האיברים המבוקשים . ידוע לנו , שכאשר יש במערך בגודל n n איברים שונים זה מזה , זמן הריצה של חיפוש בינרי (במקרה הגרוע) הוא (Theta(lgn . עכשיו האינטואיציה : אם כך , מכיוון שנתון כי יש לנו (Theta(lgn איברים שונים זה מזה , זמן הריצה של החיפוש הבינרי (במקרה הגרוע) יהיה (Theta(lglgn (אבל האם זה נכון ? ואם כן , מדוע ?) ומכיוון שיש לנו n איברים בקבוצה S , נקבל כי זמן הריצה של האלגוריתם הנ"ל הוא (Theta(n lglgn . בברכה , ליאור .

 

[vinney]

פה הניתוח שלך לא נכון

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

 

[thankful]

מאיפה ה - n הנוסף הגיע ?

איך הגענו ל - n^2 וכו' ? מאיפה "צץ" ה - n הנוסף הזה , בעקבות "לחפש את התואם במקרה הגרוע *לחצי* מהאיברים" ? במילים אחרות , איך הגעת כאן ל - n * nlglgn ? (זכור שלא ביצעתי כאן שום מיון מקדים .) ליאור .

 

[vinney]

אם לא ביצעת מיון מקדים

אז אין לך מה לעשות חיפוש בינארי. ברגע שאמרת "חיפוש בינארי", הנחת שהמערך ממוין.

 

[thankful]

ברור . לכן רשמתי שם שאנו מסתכלים על

איברי הקבוצה כממויינים כבר (שהרי בקבוצה , אין חשיבות לסדר האיברים) . מה דעתך ? יש לך רעיון לפתרון השאלה ? ליאור . (עוד שבועיים בחינה ...)

 

[thankful]

ועדיין לא הבנתי מאיפה ה - n הנוסף

שהרי רשמת שם n^2

 

[vinney]

מי אמר שאיברי הקבוצה ממוינים?

מה פתאום? אתה קיבלת מערך, אמרת "הוקוס פוקוס" וקיבלת תת מערך שמכיל את קבוצת האיברים כבר ממויין, סתם ככה? זה בדיוק הnloglogn שלך

הn הנוסף זה חיפוש התואמים (אפשר למעשה להגיד שזה logn, אבל זה עדיין עושה את זה יותר ממה שאתה צריך)?

 

[thankful]

רק המיון לוקח nlglgn ? ולא nlgn ?

אם נניח שבאלגוריתם שלנו , שלב המיון אכן לוקח רק nlglgn , אז השלב הבא באלגוריתם ישתמש בשיטת "הזזת המצביעים" (אם הסכום גדול מהאיבר z , נקטין את הסכום ע"י הזזת המצביע הימני שמאלה , ואם הסכום קטן מהאיבר z , נגדיל את הסכום ע"י הזזת המצביע השמאלי ימינה , כאשר המצביע השמאלי יצביע בהתחלה על האיבר השמאלי ביותר במערך והימני על האיבר הימני ביותר במערך (קבוצה)) . השלב הבא הזה ייקח (Theta(n במקרה הגרוע (אולי אף פחות , מכיוון שיש כפילויות במערך . אבל נניח שזה (Theta . ואז האלגוריתם כולו ירוץ בסיבוכיות המבוקשת . אין לי בשלב זה רעיונות נוספים ... ליאור .

 

[vinney]

לא צריך רעיונות נוספים, זה הפתרון

הנכון. כל מה שנשאר לך זה להבין למה המיון לוקח nlglgn . אני אומר לך שזה מה שהוא לוקח, תנסה לחשוב למה אני צודק

 

[thankful]

מה שאני חושב זה , לבצע את המיון המבוקש בעזרת

*מיון-ערימה* , ולא באמצעות מיון-מיזוג ! (כשאנו ממיינים , צריך לציין באיזה מיון אנו משתמשים .) שהרי , מיון-מיזוג לוקח בכל מקרה תטא NLGN (בכל מקרה - הטוב , הממוצע והגרוע) . אז חשבתי היום בכיוון של מיון-ערימה : כאשר כל האיברים במערך שווים , מיון-ערימה לוקח O של N . במקרה שלנו , לא כולם שווים : ואולם , יש לנו תטא (LGN) איברים שונים , מה שיכול לרמוז לכך שמיון-ערימה ייקח הפעם זמן שהוא *קטן יותר* (פחות) מ - O של NLGN . האם אתה מסכים עם המשפט האחרון הזה ? בברכה , ליאור .

 

[thankful]

מצד שני , שאלת "בשביל מה ערימה" ? קודם

ומצד שלישי , מיון-ערימה נותן לנו זמן ריצה של "O של" , ואילו זמן הריצה המבוקש הוא במונחי "תטא" . אם יש לנו דוגמת קלט (במקרה שלנו - תטא של LGN איברים שונים) , האם זה מרמז לנו על כך שזמן הריצה של מיון-ערימה יהיה במונחי תטא הפעם ? (*בגלל* שקיימת דוגמת קלט , עליה מיון-ערימה אמור לרוץ בזמן הריצה המבוקש אצלנו - NLGLGN ?) ליאור .

 

[vinney]

לפני שנכנסים לפתרונות לא טריויאליים ומסובכים

צריך להזכר בחסמים. למשל - מיון השוואתי בלי מגבלת נתונים לעולם יהיה nlogn לכל הפחות. זה הוכח. אבל מה שכן יכול לעזור לך זה לא למיין את כל n האיברים שקיבלת. לא משנה איזה מיון אתה בוחר, מה שמשנה זה מה אתה ממיין. תקרא שוב את נתוני השאלה

 

[thankful]

דיברתי עם מישהו,הוא דווקא הציע את חיפוש בינרי

שהצעתי בהתחלה . חשבתי על השאלה מחדש . הפתרון החדש הוא כזה : שלב 1 : נגדיר מערך חדש T . נעבור על איברי S , וכל פעם שנגלה איבר חדש (שלא הופיע קודם-לכן) , נעתיק אותו ל - T . מכיוון שב - S יש (Theta(lgn איברים שונים , הרי שב - T יש (Theta(lgn איברים (כולם שונים זה מזה) . אנו עוברים על כל האיברים ב - S : זה לוקח לנו (Theta(n (שכן ב - S יש n איברים) . כעת , נמיין את איברי T באמצעות מיון-מיזוג : מכיוון שיש לנו (Theta(lgn איברים ב - T , זמן הריצה של מיון-מיזוג על איברי T יהיה ((Theta(lgn lg(lgn . שלב 2 : לכל איבר s במערך S , נחפש את z-s (כלומר z פחות s) במערך הממויין T באמצעות חיפוש בינרי *על המערך T* . מכיוון שיש לנו (Theta(lgn איברים ב - T , זמן הריצה של חיפוש בינרי על המערך T ייקח ((Theta(lg(lgn . ואנו עושים את החיפוש הבינרי לכל אחד מ - n איברי S : לכן , זמן הריצה של שלב 2 יהיה ((Theta(n lg(lgn . (ה - x וה - y המבוקשים יהיו ה - s וה - z-s , שסכומם הוא האיבר z : מכיוון שכל איברי T שייכים גם ל - S , הרי ש - x,y שייכים ל - S .) ובסיכום , זמן הריצה המבוקש (של שלב 1 ושלב 2) יהיה : ((Theta + Theta(lgn lg(lgn)) + Theta(n lg(lgn)) = Theta(n lg(lgn . בברכה , ליאור .

 

[vinney]

שלב 1 בסדר

זה בדיוק המיון שלב 2 בסדר, אבל לדעתי עם זוג מצביעים תוכל לעשות את זה בlogn .

 

[thankful]

עם זוג מצביעים נוכל לעשות את שלב 2 ב - logn

על המערך בגודל T - מסכים (שכן המערך T הוא בגודל lgn , ושיטת הזזת המצביעים תעבוד על T ב - lgn) . אלא שכאן צצה בעייה : אם נניח ש - {S = {1,3,3,3,3,3,3,8 , אז {T = {1,3,8 . נניח ש - z = 6 . אז קיימים שני איברים ב - S (שני איברים שערכם 3) , שסכומם הוא 6 . (לא נאמר בשאלה ש - X שונה מ - Y .) לעומת זאת , ב - T לא קיימים שני איברים שסכומם הוא 6 ! ואנחנו בבעייה ... ליאור . (האם אכן ההעתקה מ - S ל - T לוקחת זמן של (Theta(N כפי שאמרתי ? כי יש הטוענים שזה לוקח *יותר* מ - (Theta(N - צריך גם לבדוק שאין איברים כפולים ב - T , כלומר שלא הכנסנו ל - T אותו איבר יותר מפעם אחת . ודבר נוסף : האם זמן הריצה עבור שלב 2 , כפי שתיארתי , הוא נכון ? כי יש גם החולקים על כך .)

 

[thankful]

*המערך בגודל T = המערך T*

 

[vinney]

לא הבנתי, מה זה S ומה זה T?

חשבתי לפי מה שתיארת קודם, שS זאת קבוצה, אז מלכתחילה אין שם איברים כפולים וכמובן שההעתקה תיקח תתה n, למה לא?

 

[thankful]

אני יודע שזה נשמע מוזר ,S הוגדרה בשאלה כקבוצה

אבל יש רק LGN איברים שונים (וכתוב בשאלה : עם כפילויות) . (זה היה אמור להיות מוגדר כמערך . הרי בקבוצה מעצם הגדרה המתימטית כקבוצה , אין בה איברים כפולים .) S ו - T - הגדרתי אותם בפתרון לפני-כן ... S - קבוצת המקור (יש כפולים) T - קבוצת היעד (אין כפולים)