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

Daemon · שליחה על ידי **Daemon** » 12:03 14/05/2009

אהלן,

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

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

TA_Gila · שליחה על ידי **TA_Gila** » 12:45 14/05/2009

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

Daemon · שליחה על ידי **Daemon** » 13:49 14/05/2009

תודה ושאלה נוספת בנוגע לאותו סעיף - האם יש מניעה מלשנות את סדר האיברים במערך המקורי או שלצורך כך חייבים להשתמש במבנה נתונים נוסף?

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

TA_Gila · שליחה על ידי **TA_Gila** » 13:04 15/05/2009

אפשר לשנות את המיקום, ואפשר להעתיק למקום אחר.