חידה מדהימה

[nautilus7791]

חידה מדהימה

נתון מערך A עם n מספרים ממשיים.ידוע כי לכל מספר ב A יש תכונה הבאה: אם המספר שייך ל A אז המספר הזה מופיע ב A logn פעמים בדיוק.יש למיין את כל המספרים ב A ללא חזרות בזמן O(n

 

[עתודאי23]

פתרון

go over A and create a new array which holds A without reps (takes O) this Array, say B, will have the size of n/logn as A has size n but each of his elements repeats exactly logn times. now take B and sort it using any method of "nlogn" sorting (quicksort with pivot selection or heap sort), this will take O(n/logn*(logn - loglogn)) = O(n - n/logn*loglogn) = O. now the sorted array A is B with copying each element exactly logn times, or if you want A without reps you just take the sorted array B. got you correctly?

 

[amni]

בהנחה ש- B הוא מערך המייצגים, לא ברור כלל

שבניית B לוקחת זמן לינארי (כלומר פרופורציוני ל- n ) כל השאר נראה לי כבעל קושי מישני .

 

[nautilus7791]

מדוע רשמת באנגלית?

 

[HaifaMan]

איך אתה בונה את B?

גם לי זה לא נראה טריוויאלי לממש את זה בזמן לינארי.

 

[KarNaF המקורי]

פתרון לא טוב

העברת כל המספרים שיש להם מופע אחד ממערך A למערך B אינו בזמן לינארי כיוון שאין לך דרך לדעת אילו מספרים כבר העברת, ובנוסף המספרים הם ממשיים... החלק הראשון פשוט לא טוב... יש לזה פתרון?? בינתיים כל מה שניסיתי הגעתי ל o(nlogn)

 

[nautilus7791]

פתרון

סך הכל יש logn עיברים כך שאם נצליח להוציא אותם אזי למיין אותם בטח אפשר בפחות מ O(n.איך להוציא אותם?נא לשים לב שעיבר שמופיע n/2 פעמים אמור להיות במקום n/2 אחרי שמערך ממוין.אזי נפעיל select(n/2 ונוציא אותו.אחרי זה נמחוק אותו ממערך ושוב נבצע אותה פעולה. זמן ריצה: T=T(n/2)+O(n שזה שווה ל O(n

 

[amni]

לא ברור שום דבר.

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

 

[inbal76]

יש n/logn איברים. לא logn.

(וגם ההמשך לא ברור: למה שאיבר יופיע n/2 פעמים, והמערך לא ממויין אז איך תוציא אותו...)

 

[nautilus7791]

מישהו לא יודע מה עושה פונקציית ה select?

 

[inbal76]

אני יודעת מה עושה סלקט

אבל לא רואה איך זה עוזר. איזה איבר מופיע n/2 פעמים? כל איבר מופיע logn פעמים, כלומר האיבר הראשון יופיע במערך ממוין במקומות 0 עד logn-1. וכן הלאה.

 

[inbal76]

אנא הסבר את הפתרון שלך.