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

מנהל: TA_Isana

שלח תגובה
Daemon
הודעות: 12
הצטרף: 13:23 12/12/2008

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

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

אהלן,

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

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

TA_Gila
הודעות: 66
הצטרף: 14:56 24/04/2009
יצירת קשר:

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

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

Daemon
הודעות: 12
הצטרף: 13:23 12/12/2008

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

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

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

TA_Gila
הודעות: 66
הצטרף: 14:56 24/04/2009
יצירת קשר:

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

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

שלח תגובה

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