ניתוח זמן ריצה

מנהל: TA_Isana

ניתוח זמן ריצה

הודעהעל ידי bluemari » 19:05 14/06/2010

שלום,
רציתי לברר בניתוח זמן ריצה כאשר אני משתמש ב hash table האם ניתן להניח כי זמן הכנסה וחיפוש בתוך הטבלה הינו O(1) ?
תודה
מרינה
bluemari
 
הודעות: 6
הצטרף: 16:45 13/07/2009

Re: ניתוח זמן ריצה

הודעהעל ידי TA_Yakim » 07:43 15/06/2010

זה תלוי בפונקצית ההאש ובמקדם העומס
אבל הכי חשוב שזמן הריצה בו אנו משתמשים בניתוח טבלאות האש הוא זמן ריצה ממוצע !
זמן הריצה במקרה הגרוע יכול להיות רע מאד
אני מקווה שאתה לא שואל על זה בהקשר שך תרגיל 6, אם כן, שים לב שבכל השאלות מתבקש רק ניתוח זמן ריצה רגיל כלומר זמן ריצה במקרה הגרוע
(פרט לשאלה 1 סעיף ב שנדרש ניתוח לשיעורין אבל גם זה לא קשור ממש לזמן ריצה ממוצע)
TA_Yakim
 
הודעות: 53
הצטרף: 18:54 03/06/2010

Re: ניתוח זמן ריצה

הודעהעל ידי bluemari » 07:56 15/06/2010

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

תודה רבה
מרינה
bluemari
 
הודעות: 6
הצטרף: 16:45 13/07/2009

Re: ניתוח זמן ריצה

הודעהעל ידי TA_Yakim » 08:01 15/06/2010

קבעי לך את זה ככלל, גם במבחן
כשמבקשים ניתוח זמן ריצה בלי פירוט נוסף הכוונה לניתוח זמן ריצה במקרה הגרוע
אם מתבקש סוג ניתוח אחר זה מצויין במפורש (אלא אולי אם אנו בתחום בו מובן לכל שמצפים לניתוח אחר)
בד"כ (לא תמיד אבל כמעט) האש יכול לעזור רק בבעיות בהן מבקשים ניתוח בזמן ממוצע
TA_Yakim
 
הודעות: 53
הצטרף: 18:54 03/06/2010


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד