שאלה לגבי מימוש בעבודה 5?

מנהל: TA_Isana

שלח תגובה
yinongo
הודעות: 35
הצטרף: 18:47 25/11/2008

שאלה לגבי מימוש בעבודה 5?

שליחה על ידי yinongo » 18:46 23/06/2009

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

אם כן, הצלחתי לממש את מבנה הנתונים בחלק הראשון של העבודה ללא שימוש בכלל בערימות, האם זה מקובל?

תודה.

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 19:31 23/06/2009

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

ury
הודעות: 57
הצטרף: 13:46 16/12/2008

מה זה וקטור?

שליחה על ידי ury » 22:32 23/06/2009

איך זה בנוי ואיך משתמשים בזה?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 00:55 24/06/2009

http://java.sun.com/j2se/1.4.2/docs/api ... ector.html
השיטות החשובות הן:
add(int index, Object element)
elementAt(int index)

yinongo
הודעות: 35
הצטרף: 18:47 25/11/2008

שליחה על ידי yinongo » 00:57 24/06/2009

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

וסה"כ בכל נק' זמן, שליפה של אלמנט תהיה O(1) זמן

אני מפספס משהו?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 15:02 24/06/2009

מה שתיארת זה מה שצריך לעשות.

litanil
הודעות: 46
הצטרף: 12:17 24/11/2008

שליחה על ידי litanil » 15:29 24/06/2009

המשך לשאלה:
רשום בתחילת העבודה שיהיה קובץ בגודל n (כמובן, n לא קבוע)
אבל אח"כ רשום שבהכנסה אני יכול להניח שסך ההכנסות יהיה עד n ולא תהיה חריגה...

אז לפי ההיגיון, אם בהתחלה הוכנסו 90 איברים (כלומר, n=90), אז לא ייכנסו איברים נוספים למבנה הנתונים, כי הוא כבר מכיל 90 איברים....
ואז זה בכלל לא הגיוני....

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 16:14 24/06/2009

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

שלח תגובה

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