לאחרונה הכרתי את אלגוריתם המיון מרג' סורט,

והבנתי שאין אלגוריתם מיון בזמן ריצה לינארי,

ואף שמעתי שיש הוכחה שאי אפשר לעשות אחד כזה..

אבל אני חושב שהצלחתי,

בהתחלה היה מספר הגבלות, הצלחתי רק בטווח 1-10

אח"כ הצלחתי בטווח כל P

ועכשיו הטווח הוא כל Z

המגבלות שנותרו כעת הם מספרים ממשיים, (לא ממיין מספרים ממשיים)

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

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

השאלה שלי-

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

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

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

תודה וסוף שבוע מצוין.

יש הוכחה לכך שמיון מבוסס השוואות הוא מינימום nlogn (כלומר אומגה של). ההוכחה משתמשת בעץ ההשוואות.

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

אבל זה רק אם יש לך הנחות מסויימות על הקלט (למשל מספרים מ-0 עד 100 בלבד או מספרים בני 10 ספרות בלבד).

תבדוק את האלגוריתמים radix sort או bucket sort.

מה הקשר לג'אווה? הועבר לפורום תכנות כללי. מומלץ גם שתערוך את הכותרת כך שתכיל את תמצית השאלה.

שים לב, אגב, שיכול להיות שחישוב הסיבוכיות שלך שגוי (לדוגמה, אם האלגוריתם שלך תלוי באיזשהו גודל חיצוני שאינו קשור לגודל הקלט, יכול להיות שאתה לא מתייחס אליו בחישוב).

אין אצלי השוואות ..

ראיתי עכשיו גם את קאונטינג סורט, שלי מעט (ממש מעט) דומה לו ,

והחישוב לא שגוי, זמן הריצה פחות או יותר

4n ועוד קבוע מסויים

אז אתה מוזמן להעלות לכאן את האלגוריתם שלך ונאמר לך מה דעתנו

יכול להיות שגם הקבוע הזה הוא החלק הבעייתי בסיבוכיות.

אוקי אני יסדר אותו קצת למה הוא בערך 4 מתודות,

ישב עליו קצת הלילה ינסה לפתור את בעיית הדופליקט ויעלה,

בכל אופן במקרה וזה נכון ואצליח,

יש מה לעשות עם האלגוריתם?

להעביר לאן שהוא?

בוא נתקדם שלב שלב

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