שאלה במבני נתונים

[gil levi]

שאלה במבני נתונים

רוצים מבנה נתונים שתומך בפעולות Insert, Delete ו-Find. מוצעים שני מבנים: הראשון תומך בכל הפעולות בזמן W.C. O zzz ובזמן Amortized לפעולה O(1)zzz. השני תומך בכל הפעולות בזמן W.C. O(log n) zzzובזמן Amortized לפעולה O(log N).zzz נזכיר ש-n מתאר את מספר האיברים במבנה, ו-N מתאר את מספר הפעולות שבוצעו על המבנה. המבנה דרוש לאלגוריתם שמבצע N פעולות על המבנה. המבנה מאותחל למצב ריק. בתחילת ריצת האלגוריתם מבוצעות עליו פעולות insert. איזה משני המבנים עדיף, על מנת להשיג זמן W.C. הנמוך ביותר לאלגוריתם? א. הראשון. ב. השני. ג. התשובה עבור שונה מהתשובה עבור . ד. אף אחת מהתשובות הנ"ל.

 

[gil levi]

והפתרון

א. הראשון. הפתרון מנומק בכך שמבנה הנתונים הראשון משיג סיבוכיות של O(N) zzz והשני O(NlogN) zzz. לפי הקלקולציות שלי הראשון בכלל משיג סיבוכיות של O(N^2) zzz: ראשית צריך להכניס N/10 איברים למבנה הנתונים. נתון שכאשר יש במבנה הנתונים n איברים הכנסה מתבצעת בסיבוכיות של O zzz. אז הכנסת N/10 איברים תיקח:

O(1)+O(2)+...+O(N/10) = O( (1+(n/10))*N/20 )= O(N^2)​

המעבר הלפני אחרון הוא בעזרת הנוסחא לסכום סידרה חשבונית. כבר בהכנסת N/10 האיברים הראשונים אני מקבל סיבוכיות ריבועית, אז כיצד ייתכן שהסיבוכיות היא בעצם לינארית? מה אני מפספס כאן? תודה מראש.

 

[vinney]

אתה מפספס את הניתוח לשיעורין

זה אומר שבהנתן N פעולות, האלגוריתם ירוץ בO של N (שים לב, לא כל פעולה, כל N הפעולות). זה אומר, שכל פעולה תרוץ בO של 1 (כי אם N פעולות רצות בO של N => כל פעולה בודדת זה O של 1). האלגוריתם השני מבטיח לך שכל פעולה רצה בO של LOG N, גם בפעולה בודדת, וגם בסט של N פעולות, ז"א סט של N פעולות ירוץ בO של NLOG N, שזה פחות טוב מN במקרה הראשון.

 

[gil levi]

תודה רבה, אבל ראית את התיקון שלי?

התשובה שלך עומדת בעינה?

 

[vinney]

לא, לא ראיתי../images/Emo13.gif

אמרתי לך כבר שאני שונא ניתוח לשיעורין?

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

 

[gil levi]

תודה.

 

[gil levi]

*תיקון:

המבנה דרוש לאלגוריתם שמבצע N פעולות על המבנה. המבנה מאותחל למצב ריק. בתחילת ריצת האלגוריתם מבוצעות עליו N/10 פעולות insert.