(1) O בממוצע?

[אלוהים1980]

(1) O בממוצע?

שלום לכולם. בשיעורי הבית במבני נתונים קיבלנו משימה להציע מבנה נתונים כלשהו שפעולות מסויימות עליו יתבצעו בסיבוכיות של (1)O בממוצע. מה זה (1)O בממוצע??? אני יודע מה הרעיון של ממוצע - למשל כאשר יוצרים רשימת דילוגים (SKIP-LIST) אז הסיבוכיות למציאת איבר תהיה "או של לוג של מספר האיברים בממוצע" אבל למה הכוונה "או של 1 בממוצע" איזה מבנה נתונים ואלגוריתם יכול להכיל סיבוכיות כזאת?

 

[אלדד28]

זה אומר "זמן קבוע",

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

 

[עידו123456]

../images/Emo26.gif

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

 

[נועה לביא]

קבל כלל

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

 

[voguemaster]

אבל אז זה לא ממוצע...

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

(ד"א סוף סוף למדתי איך לכתוב דברים כמו שצריך שהסוגריים לא יתחרבשו

) אלגוריתם בידי דפוק....

 

[עידו123456]

עקרונית...

אבל סיבוכיות של Hashtable אם נדקדק היא (O(1+alpha - כאשר אלפא מוגדר להיות מספר האיברים חלקי מספר התאים - ולכן זה בממוצע (O(1.

 

[נועה לביא]

כשאומרים שאלגוריתם מסויים

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

 

[voguemaster]

סוגריים:

את כבר בטח יודעת שכדי לכתוב ++C לדוגמא צריך לשים את הפלוסים לפני ה-C, כן ? הרעיון עם סוגריים דומה. כשאת כותבת O(1) הסוגר האחרון מתחרבש בגלל שכיוון הכתיבה הוא מימין לשמאל ואת מנסה לכתוב באנגלית (סימנים כמו סוגריים נכתבים מימין לשמאל ממש כמו אותיות בעברית, אלא אם כן יש אחריהם מספרים או אותיות באנגלית). זו הסיבה שהסוגר מופיע במקום הלא נכון, הוא נחשב "עברית" (אין אחריו מספר או אות אנגלית). הפיתרון: לכתוב סוגר פותח ( ואז לעבור לאנגלית ולכתוב O(1 וזהו זה. הנה: (O(1

 

[נועה לביא]

../images/Emo51.gif אני אשתדל ../images/Emo13.gif

 

[אלוהים1980]

האם כוונתך היא

לטבלת עירבול שבה לא מוסיפים את האיברים לרשימות מקושרות, אלא ישר לטבלה? בכל מקרה, תודה לכולכם.

 

[zagzagzag]

אם אני זוכר נכון,

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