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

מנהל: TA_Isana

שלח תגובה
eliorar
הודעות: 35
הצטרף: 19:43 11/11/2009

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

שליחה על ידי eliorar » 15:10 16/07/2010

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

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

rubichi
הודעות: 77
הצטרף: 18:50 22/10/2009

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

שליחה על ידי rubichi » 09:16 17/07/2010

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

שלח תגובה

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