דף 1 מתוך 1

שאלה 1 א' - שימוש במבנה נתונים נוסף

נשלח: 12:03 14/05/2009
על ידי Daemon
אהלן,

למיטב הבנתנו יש לעמוד ב-3n/2 השוואות, אך האם אנחנו מוגבלים מבחינת זכרון?

על מנת לעמוד בכמות השוואות אנחנו רוצים להשתמש במבנה נתונים נוסף, שעשוי לתפוס עד n/2 תאי זיכרון נוספים, מעבר לכמות זיכרון שהמערך תופס (n). בהנחה וסך ההשוואות (לא בהכרח סך הפעולות) עומד ב-3n/2, האם זה סביר?

נשלח: 12:45 14/05/2009
על ידי TA_Gila
בהחלט, אין הגבלה מדוייקת על גודל הזכרון הנדרש ואפשר להשתמש בתוספת של
O(n) זכרון ואפשר גם לבצע פעולות נוספות.

נשלח: 13:49 14/05/2009
על ידי Daemon
תודה ושאלה נוספת בנוגע לאותו סעיף - האם יש מניעה מלשנות את סדר האיברים במערך המקורי או שלצורך כך חייבים להשתמש במבנה נתונים נוסף?

ברמה העקרונית בשאלה לא כתוב שחייבים לשמור על סדר האיברים המקורי.

נשלח: 13:04 15/05/2009
על ידי TA_Gila
אפשר לשנות את המיקום, ואפשר להעתיק למקום אחר.