דף 1 מתוך 1

שאלה 7

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

Re: שאלה 7

נשלח: 21:15 03/04/2010
על ידי TA_Lena
למה שתרצה להימנע מלרוץ על כל הרשימה? זה לא מוסיף לך בזמן הריצה (מבחינה אסימפטוטית).

Re: שאלה 7

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

תודה

Re: שאלה 7

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

Re: שאלה 7

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

Re: שאלה 7

נשלח: 21:51 04/04/2010
על ידי Shahar
1. כן, אתה יכול להניח שאתה מקבל אותם באיזה מבנה שאתה רוצה, ושהם ממוינים לפי נק' ההתחלה שלהם על ציר הX.
2. כן, אבל אתה לא יכול להניח יותר מזה. ז"א אתה לא יכול להניח שהם ממוינים לפי גובה.
3. אני חושב שלא, אבל זה לא באמת חשוב.