עבור לתוכן

כיצד לחשב מיון מערך בסיבוכיות נמוכה ככל הניתן

Featured Replies

פורסם
  • מחבר

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

מה נראה לך יהיה יעיל לעשות ?

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

  • תגובות 45
  • צפיות 10.3k
  • נוצר
  • תגובה אחרונה
פורסם

כמו שאמרו 5n,4n,10n כולם O(n) בסופו של דבר.

וגם במקום לשחזר קוד של swap עדיף תעשה פונקציה נפרדת להחלפה.

פורסם

אם תעביר את האיברים למערך עזר זה כבר לא יהיה מיון במקום .

פורסם

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

פורסם
  • מחבר

אוקיי השאלה שלי היא איך הכי טוב להעביר למערך חדש ?

האם להגדיר מערך עזר אחד או שניים ? הסיבוכיות עדיין תהיה n ?

פורסם

ממליץ לך לעבור על האלגוריתם של bucket sort ולראות איך אתה משתמש בו.

פורסם

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

סיבוכיות מקום...

למה לעשות את זה אם לא חייבים ?

זה פתיר בסיבוכיות מקום של N ובזמן של N+K < 2N

פורסם

שימוש במערך נוסף (או שניים, שלושה) זה סיבוכיות מקום של (O(n

פורסם

אוקיי.

תספר לגוגל שפתרת להם את הבעיה של אינדוקס האינטרנט באו של.

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

פורסם

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

פורסם

אנחנו מנסים לגרום לו להיות מתכנת טוב יותר.

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

פורסם
  • מחבר

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

פורסם

למיין, זו בדר"כ בעיה קשה יותר ממה שיש לך פה.

כי יש סדר בין כל האיברים.

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

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

נניח שהייתי נותן לך מערך של כדורים שחורים ולבנים, והייתי רוצה שכל הלבנים יהיו בהתחלה והשחורים יהיו בסוף, איך היית עושה את זה ?

נניח שאסור לך להוציא את כל הכדורים ולהתחיל לסדר אותם, יש לך רק 2 ידיים.

משם הדרך ל3 צבעים קצרה.

פורסם
  • מחבר

לא הבנתי את השורה האחרונה (משם הדרך ל-3 צבעים קצרה) - האם אתה מתכוון למערך עזר ?

פורסם

לא. אמרנו שלצורך העניין אסור להוציא כדורים, ושיש לך רק 2 ידיים.

תן לי אלגוריתם ל2 צבעים, ובוא נחשוב איך אפשר להרחיב אותו, אם בכלל צריך..

ארכיון

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

דיונים חדשים