נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: מיונים

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
אבי
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 01 May 2005 בשעה 01:21 | IP רשוּם
ציטוט אבי
אני צריך רעיון לבעיה, יש לי מערך עם n אברים שבו כל האברים שונים זה מזה. נתון שכל איבר נמצא לכל היותר במרחק d ממקומו האמיתי (דוגמא: איבר ה i בגודלו ימצא המקונות i-d ו i+d .
צריך למצוא אלגוריתם הרץ בזמן( o(d*n הממין את המערך(סיבוכיות מקום( o(1 
יש למישהו איזה רעיון נחמד להתחיל איתו  
תודה רבה
חזרה לתחילת העמוד הצג את כרטיס החבר של אבי חפש הודעות אחרות של אבי בקר בדף הבית של אבי
 
ניר
מנהל האתר
מנהל האתר
סמל אישי

הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
נשלח בתאריך: 01 May 2005 בשעה 01:29 | IP רשוּם
ציטוט ניר
לא חשבתי לעומק, בזריקה הייתי חושב על משהו כזה:
ניקח את 2d האיברים הראשונים. נשתמש באלגוריתם הליניארי למציאת חציון.
בדומה ל-quick sort נאסוף את d האיברים הראשונים בצד שמאל.
ברור שכל האיברים האלו אכן ימצאו בסוף המיון באיזור זה.
ניתן עכשיו לקחת את האיברים החל מהאיבר במקום d ועד האיבר במקום 3d ולבצע אותו תהליך - מציאת חציון ואסיפת d איברים בצד שמאל. גם הם יהיו שם בסוף התהליך.

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

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

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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