זהירות ספוילר

מנהלים: TA_Isana, TA_Isana

שלח תגובה
oridov
הודעות: 11
הצטרף: 14:32 29/11/2008

זהירות ספוילר

שליחה על ידי oridov » 09:46 04/07/2009

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

לכל אלו שביקשו ולא היה לי לתת, הנה רעיון לפיתרון.


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

כדי לממש את זה, צריך לרשת ממבנה הנתונים ערימה בינארית ולשכתב את Heapify ו ReverseHeapify.

בניה:
בכדי למצוא את האיבר ה- k בגודלו, צריך לבנות מערך חד מימדי בגודל k של הערימות הללו.
למערך שאתם מקבלים כקלט, צריך להפעיל את פונקציית הסלקט שנלמדה בתרגול על כל אחד מה- k שעלול לצאת מהנוסחה הנתונה בתרגיל.
לאחר שהאיברים במקומות הרצויים מסודרים, צריך לבנות k ערימות כאשר האיבר המקסימלי בערימה הראשונה הוא האיבר שסודר ראשון, האיבר המקסימלי בשניה הוא השני שהסלקט סידרה וכן הלאה.

בכדי להחזיר את האיבר ה- k בגודלו, צריך להוציא את האיבר המקסימלי מהערימה המתאימה.

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


מסתבר שעל מבנה הנתונים הזה חשבו כבר באיזה כנס ב 1985, כתוצאה מרצון להיפטר מהמצביעים המסרבלים שבבניית שתי ערימות שונות, ויש לו אפילו שם:
למעטפת קוראים Min-Max Heap ולמבנה הספציפי שמוצא את האיבר ה- k בגודלו בזמן קבוע, קוראים
Order Statistics Tree. לקריאה נוספת:
http://cg.scs.carleton.ca/~morin/teachi ... minmax.pdf


ולסיום, הבונוס:
הרעיון הוא להפוך את הסלקשן ל O(n) במקרה הגרוע, וזה יכול להתבצע על ידי אלגוריתם ה"חציון של החציונים". לאלגוריתם המלא, תצטרכו לשפשף את האנגלית שלכם קצת:
The key to making the previous algorithm worst-case linear and the primary contribution of "Time bounds for selection" is the "median of medians algorithm", which consistently finds good pivots.

This algorithm divides the list into groups of five elements. Left over elements are ignored for now. Then, for each group of five, the median is calculated: an operation that can potentially be made very fast if the five values can be loaded into registers and compared. These medians are moved into one contiguous block in the list, select is called recursively on this sublist of n/5 elements to find new median values. Finally, the "median of medians" is the pivot.

The chosen pivot is both less than and greater than half of the elements in the list of medians, which is around n/10 elements for each half. Each of these elements is a median of 5, making it less than 2 other elements and greater than 2 other elements outside the block. Hence, the pivot is less than 2(n / 10) elements outside the block, and greater than another 2(n / 10) elements outside the block. Thus the chosen median splits the elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm.

The median-calculating recursive call does not exceed worst-case linear behavior because the list of medians is 20% of the size of the list, while the other recursive call recurs on at most 70% of the list, making the running time

T(n) ≤ T(n/5) + T(7n/10) + O(n)

The O(n) is for the partitioning work. An induction argument can then show that T(n) is indeed O(n).

benny
הודעות: 81
הצטרף: 22:27 29/11/2008

שליחה על ידי benny » 10:17 04/07/2009

הכוונה למקרה גרוע של (o(n היא לא לגבי הבנייה של הערימה בכלל שתתבצע בצורה אחרת או מימוש אחר?? כי שאר הפעולות שלי הן בסיבוכיות הדרושה ןרק הבנייה יכולה במקרה גרוע להיות o(nlogn)

שלח תגובה

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