ואיך לאתחל מערך בגדול n בסיבוכיות שלא תעלה על שורש n?

אתה יודע מה זה מערך דליל?

הכוונה מערך שיכול להכיל עד n תאים (כלומר, האופסט הגדול ביותר בו הוא n-1), אבל בפועל הוא מכיל הרבה פחות. המטרה העיקרית היא לחסוך בזיכרון (אם למשל דרוש לך אופסטים בטווח 990,000 - 995,000 ובטווח 1,000-10,000, ולא יותר מזה, זה יהיה בזבוז רציני לשמור קרוב ל-1,000,000 תאים בזיכרון שלרובם אין שימוש).

מבקשים ממך לממש את המבנה בצורה כזאת שתוכל לקיים את הדרישות שלהם.

בשאלה, הם אומרים לך שהמערך לא יכיל יותר משורש n איברים לא ריקים, ככה שבכל רגע נתון, כמות הזיכרון שהמערך ישתמש בה היא [O של שורש n]. מאותה סיבה, אתחול המערך הוא בסיבוכיות [O של שורש n], כי אתה לא מאתחל n תאים, אלא רק שורש n.

הכוונה היא למערך שהצגה חיצונית יכיל n מקומות אבל בכל רגע נתון יהיו בו במקסימום שורש n תאים אמיתיים תפוסים.

הרעיון שאסור לך להגדיר באמת מערך בגודל n אלא בגודל חסום על ידי שורש n כפול קבוע.

יש לי הרגשה שמדובר במימוש של האש.

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

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

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

אם מובטח לך שלא "דורסים" ערך במערך במקום i לפני שמבצעים מחיקה שלו עם הפונקציה המיועדת המימוש הוא פשוט.

רשימה מקושרת פותרת את הסיפור הזה. כל צומת תחזיק את השדות - ערך i, ודאטה.

כשאתה מכניס צומת אתה דוחף אותה בראש הרשימה.

חיפוש ומחיקה, רצות על הרשימה ומחפשות בשדה i את הערך שהמשתמש הכניס.

אם יש כזו צומת - מוחקים/מחזירים ערך

אם אין כזו צומת - מחזירים null

כמו שאמרתי, הבעיה שאם רוצים לשנות את הערך במקום ה-i, צריך להפעיל קודם פונקצית מחיקה

יש לי הרגשה שמדובר במימוש של האש.

ץודה על התגובות.

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

אם מובטח לך שלא "דורסים" ערך במערך במקום i לפני שמבצעים מחיקה שלו עם הפונקציה המיועדת המימוש הוא פשוט.

רשימה מקושרת פותרת את הסיפור הזה. כל צומת תחזיק את השדות - ערך i, ודאטה.

כשאתה מכניס צומת אתה דוחף אותה בראש הרשימה.

חיפוש ומחיקה, רצות על הרשימה ומחפשות בשדה i את הערך שהמשתמש הכניס.

אם יש כזו צומת - מוחקים/מחזירים ערך

אם אין כזו צומת - מחזירים null

כמו שאמרתי, הבעיה שאם רוצים לשנות את הערך במקום ה-i, צריך להפעיל קודם פונקצית מחיקה

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

ולפי איך שמכניסים צומת(לתחילת הרשימה) הרשימה לא תהיה ממוינת לפי האינדקסים נכון?

ככה הבנתי את מה שכתבת ואז לא ברור לי מה הבעיה כאשר מכניסים ערך חדש לפני שמוחקים את הקודם(פשוט המצביע ברשימה יעבור להצביע על האובייקט החדש עם הערך i והדאטה החדשים)

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

בדיוק, אם מצאת צומת עם ערך i שאתה מחפש, תחזיר אותה, ואם הגעת לסוף הרשימה הערך i כאילו לא מכיל ערך במערך (כי הוא לא קיים)

ולפי איך שמכניסים צומת(לתחילת הרשימה) הרשימה לא תהיה ממוינת לפי האינדקסים נכון?

נכון, הרשימה לא ממויינת. ולכן אין אפשרות לדעת אם הוכנס ערך בכתובת i מסויימת בלי לחפש על כל הרשימה.

ככה הבנתי את מה שכתבת ואז לא ברור לי מה הבעיה כאשר מכניסים ערך חדש לפני שמוחקים את הקודם(פשוט המצביע ברשימה יעבור להצביע על האובייקט החדש עם הערך i והדאטה החדשים)

נניח שיש לך ערך בכתובת x כלשהי במערך. במימוש של רשימה מקושרת תהיה צומת עם ערך i=x ודאטא כלשהי.

אם אתה רוצה לשנות את המידע במערך בתא x, אתה צריך לכתוב ערך חדש לכתובת x. במימוש הזה, אתה מוסיף צומת לרשימה בלי לבדוק אם התא מכיל ערך.

אתה יכול להגיע למצב שיש לך כמות גדולה של צמתים ברשימה המכילים את אותו i ולכן סיבוכיות המקום של המבנה לא תעמוד בדרישה.

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

הבנתי :) תודה לכולכם .אני אבדוק את העניין לגבי המחיקה שבת שלום