חידה מדהימה

[nautilus7791]

חידה מדהימה

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

 

[מספר6]

../images/Emo35.gif

אז רק חזקות של 2 יכולות להופיע?

 

[nautilus7791]

הכוונה לבסיס 2

 

[עריסטו]

logn זה לוגריתם לפי בסיס 2?

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

 

[nautilus7791]

פתרון

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

 

[carlos22]

זה

נראה כמו nlogn

 

[בסג]

?!

ההסבר שלך מאד לא ברור. אפשר שוב?