הפיכת מיון ערימה/מיון מהיר למיון יציב

מנהל: TA_Isana

הפיכת מיון ערימה/מיון מהיר למיון יציב

הודעהעל ידי eliorar » 14:10 16/07/2010

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

אוקיי אז הפתרון הוא די פשוט, לשמור את האינדקסים של האיברים במערך המקורי, ובזמן השוואה להשוות בנוסף לערך של האיבר, גם את האינדקס שלו במערך המקורי.
חישוב זמן ריצה: במקרה הכי גרוע כל האיברים שווים, זמן הריצה לא ישתנה כיוון שהוספנו מספר קבוע של פעולות עבור כל השוואה.
הבעיה שאני נתקל בה היא בחישוב הזיכרון הנדרש: בפתרון כתוב,
עבור n איברים, האינדקסים שלהם הם 1...n. כל אחד יכול להיכתב ב log n ביטים לכן ביחד הם יקחו O(nlogn) זיכרון נוסף.
מישהו יכול להסביר לי את הטענה הזו? למה זה לא פשוט n - הוספנו שדה אחד עבור כל מספר...
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

Re: הפיכת מיון ערימה/מיון מהיר למיון יציב

הודעהעל ידי rubichi » 08:16 17/07/2010

אם אני לא טועה זה מתרגול ואם אני זוכר נכון שאלנו את זה בכיתה ולפי מה שהבנתי זו סתם התחכמות מיותרת שאין הרבה מאחוריה, כי בדרך כלל אנחנו מתייחסים לשלמים כזיכרון קבוע
rubichi
 
הודעות: 77
הצטרף: 18:50 22/10/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים