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

מנהל: TA_Isana

שלח תגובה
bluemari
הודעות: 6
הצטרף: 17:45 13/07/2009

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

שליחה על ידי bluemari » 20:05 14/06/2010

שלום,
רציתי לברר בניתוח זמן ריצה כאשר אני משתמש ב hash table האם ניתן להניח כי זמן הכנסה וחיפוש בתוך הטבלה הינו O(1) ?
תודה
מרינה

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

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

שליחה על ידי TA_Yakim » 08:43 15/06/2010

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

bluemari
הודעות: 6
הצטרף: 17:45 13/07/2009

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

שליחה על ידי bluemari » 08:56 15/06/2010

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

תודה רבה
מרינה

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

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

שליחה על ידי TA_Yakim » 09:01 15/06/2010

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

שלח תגובה

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