שאלה 7

מנהל: TA_Isana

שלח תגובה
yevlev
הודעות: 37
הצטרף: 20:56 12/11/2009

שאלה 7

שליחה על ידי yevlev » 13:04 03/04/2010

באם אני מניח שאני מקבל את אורכי הקטעים ברשימה דו-כיוונית, האם אני יכול להגידר מצביע שיצביע בהתחלה לזנב הרשימה (TAIL), מבלי לרוץ מ-HEAD בO_N כדי לקבוע אותו?
תודה.

TA_Lena
הודעות: 141
הצטרף: 14:46 22/04/2009

Re: שאלה 7

שליחה על ידי TA_Lena » 21:15 03/04/2010

למה שתרצה להימנע מלרוץ על כל הרשימה? זה לא מוסיף לך בזמן הריצה (מבחינה אסימפטוטית).

rangr
הודעות: 32
הצטרף: 18:59 28/10/2009

Re: שאלה 7

שליחה על ידי rangr » 11:36 04/04/2010

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

תודה

Shahar
הודעות: 160
הצטרף: 16:49 29/10/2009

Re: שאלה 7

שליחה על ידי Shahar » 14:38 04/04/2010

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

rvn
הודעות: 39
הצטרף: 23:05 14/11/2008
מיקום: מעונות ג'

Re: שאלה 7

שליחה על ידי rvn » 20:10 04/04/2010

וואו אפילו דברים יותר בסיסים יעזרו:
1. אני מניח שיש N קטעים ז"א מכל (i,0) בין 1 לN יוצא קטע? ושהם ממוינים ז"א שמורים בסדר I עולה?
2. יש לי חופש לקבוע את סוג מבנה הנתונים שבו הם מאוכסנים לפני כן?
3. אם יש אחד באותו הגובה משמאל הוא יראה אותו או מעבר לו?

Shahar
הודעות: 160
הצטרף: 16:49 29/10/2009

Re: שאלה 7

שליחה על ידי Shahar » 21:51 04/04/2010

1. כן, אתה יכול להניח שאתה מקבל אותם באיזה מבנה שאתה רוצה, ושהם ממוינים לפי נק' ההתחלה שלהם על ציר הX.
2. כן, אבל אתה לא יכול להניח יותר מזה. ז"א אתה לא יכול להניח שהם ממוינים לפי גובה.
3. אני חושב שלא, אבל זה לא באמת חשוב.

שלח תגובה

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