שאלה במיון

[guy81]

מצורפת שאלה לגב מיון של מספרים. רציתי לדעת אם יש דרך לפתור את השאלה באותו זמן ריצה אם לא היה מדובר ב"סתם מספרים"

אלא באובייקטים שיש להם מפתחות ומספר המפתחות השונים הוא n/logn

http://www.fastup.co.il/images/37686602.jpg

[QttP]

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

[שניצל]

השאלה היא האם לשני אובייקטים שונים יכול להיות אותו מפתח, ואם כן אז האם יש קשר בין הסדר של אובייקטים שונים עם אותו מפתח (כלומר, האם לכל שלושה אובייקטים x,y,z כאשר ל-x,y יש אותו מפתח, בהכרח יתקיים x<z אם ורק אם y<z).

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

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

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

[guy81]

בהכרח יש אובייקטים שונים עם אותו מפח כיוון שיש רק n/ lon ערכים שונים.

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

באובייקטים אין לי רעיון איך עושים אעת זה באותו זמן ריצה (אם אפשר בכלל..)

[שניצל]

בהכרח יש אובייקטים שונים עם אותו מפח כיוון שיש רק n/ lon ערכים שונים.

לא בהכרח, יכול להיות שיש n אובייקטים אבל עם חזרות (בדיוק כמו בשאלה המקורית).

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

[QttP]

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

[guy81]

נכון..נכון היה לי בלבול קטן..תודה לכם!!

[guy81]

אפשר לשאול שאלה על זמנים אסימפטוטים?

בהשאלה המצורפת ביקשו לדרג אות הפונקציות לפי סדר אסימפטורי..לא הצלחתי להבין למה A גדול מ-B

מספר בחקת logn גדול מ n בחזקת משהו..לא?

http://www.fastup.co.il/images/862981.jpg

[שניצל]

צריך קצת להתעסק עם מתמטיקה כאן. אני מניח שכשכתוב log הכוונה היא log בבסיס 2.

2 בחזקת logn זה בדיוק n. זה נובע מהחוקים של לוגים וחזקות. אז 2 בחזקת 2003logn זה כמו n בחזקת 2003.

2003 בחזקת loglogn זה logn (בחזקת log2003, לא משנה ממש)

ככה ש-B זה פשוט סדר גודל של n בחזקת 2003 כפול logn בחזקת log2003.

A לעומת זאת הוא n בחזקת מספר כלשהו (הסכום שבתוך החזקה הוא סכום של טור הנדסי, שזה סדר גודל קבוע - במקרה הזה הסכום הוא 1002*2). כלומר A הוא מסדר גודל n בחזקת 2004, שזה יותר מ-n בחזקת 2003 כפול logn בחזקת log2003.

[guy81]

תודה רבה!!

[guy81]

אשמח לעזרה בשאלה על מיון דליים.

מצורף קוד למיון דליים כאשר טווח המספרים הוא 0-1.

בקוד מחלקים את הקטע ל-n קטעים וממינים כל קטע בפני עצמו.

לא כ"כ מצליח להמיר את זה לשאלה המצורפת, לא הבנתי את הפתרון ומה עושים כאשר תחום המספרים הוא מ-1 עד n בריבוע ועדיין נרצה לחלק ל-n קטעים שיהיה בכל אחד מהם בממוצע o(1) .

תודה

http://www.fastup.co.il/images/91761172.jpg

[שניצל]

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

[Gil28]

כלומר אם N=5 אזי המספרים האפשריים הם 1,4,9,16,25 והדליים יהיו 1,2,3,4,5 בהתאמה.

[guy81]

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

נגיד שהתחום הוא n בחקת 100

אז בדלי הראשון יהיו מ-1 עד n בחזקת 99?

הבעיה העיקרית שלי היא הזמן ריצה, זה לא משנה משהו??

[שניצל]

כלומר אם N=5 אזי המספרים האפשריים הם 1,4,9,16,25 והדליים יהיו 1,2,3,4,5 בהתאמה.

ממש לא, אם N=5 אז המספרים האפשריים הם כל מספר בין 1 ל-25. הדליים יהיו 1-5,6-10,11-15,16-20,21-25.

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