מבני נתונים ומבוא לאלגוריתמים

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

הבעיה: מציאת סטטיסטיקת סדר והגישות הנאיביות

בעיית מציאת סטטיסטיקת סדר (Order Statistics) היא בעיה יסודית במדעי המחשב. המטרה היא למצוא את האיבר ה-k הקטן ביותר במערך לא ממוין בגודל n. מקרה פרטי חשוב הוא מציאת החציון (האיבר ה- (n/2) הקטן ביותר).

סטטיסטיקת סדר (Order Statistic): האיבר ה-k הקטן ביותר במערך נתון. לדוגמה, עבור k=1 זוהי מציאת המינימום, ועבור k=n זוהי מציאת המקסימום.

גישות נאיביות:

מיון המערך: הדרך הפשוטה ביותר היא למיין את המערך כולו (לדוגמה, באמצעות Merge Sort או Heap Sort) בזמן של O(n log n), ולאחר מכן לגשת לאינדקס ה-k-1. גישה זו יעילה אם יש צורך ביותר מסטטיסטיקת סדר אחת, אך יקרה מדי אם אנו מחפשים רק איבר אחד.
שימוש בערימה: ניתן לבנות ערימת מינימום מכל האיברים בזמן O(n), ולאחר מכן לחלץ את האיבר הקטן ביותר k פעמים. זמן הריצה יהיה O(n + k log n). אם k קטן מאוד, זה יכול להיות יעיל יותר ממיון מלא.

אלגוריתם הבחירה הרנדומית (Randomized Select)

אלגוריתם ה-Randomized Select הוא אלגוריתם יעיל למציאת סטטיסטיקת סדר, המבוסס על רעיון החלוקה (Partition) מאלגוריתם Quicksort. הוא פועל בשיטת "הפרד ומשול" (Divide and Conquer).

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

פעולת האלגוריתם:

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

ניתוח זמן ריצה של Randomized Select: הבנת ניתוח המקרה הממוצע באמצעות עץ רקורסיה או שיטת ההצבה היא קריטית לבחינה. בממוצע, זמן הריצה הוא O(n). במקרה הגרוע (כאשר הציר נבחר תמיד להיות האיבר הקטן ביותר או הגדול ביותר), זמן הריצה הוא O(n^2). דגש מיוחד ניתן לפתרון יחסי נסיגה (recurrence relations) והבנת הסיבות למקרה הגרוע.

אלגוריתם הבחירה הדטרמיניסטי (Deterministic Select / Median-of-Medians)

בעוד ש-Randomized Select יעיל מאוד בממוצע, קיים אלגוריתם המבטיח זמן ריצה לינארי במקרה הגרוע: אלגוריתם ה-Deterministic Select, המכונה גם "Median-of-Medians". אלגוריתם זה מורכב יותר אך מבטיח בחירת ציר "טוב" מספיק בכל שלב.

חציון החציונים (Median-of-Medians): שיטה לבחירת ציר (pivot) באלגוריתם בחירה דטרמיניסטי, המבטיחה חלוקה מאוזנת מספיק כדי להשיג זמן ריצה לינארי במקרה הגרוע.

פעולת האלגוריתם (בגדול):

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

ניתוח זמן הריצה של אלגוריתם זה מורכב יותר, ויחס הנסיגה שלו הוא: T(n) = T(n/5) + T(7n/10) + O(n). פתרון יחס נסיגה זה מראה כי זמן הריצה הוא O(n) במקרה הגרוע. ההבטחה ל-O(n) נובעת מכך שחציון החציונים מבטיח שלפחות 3/10 מהאיברים יהיו קטנים מהציר ולפחות 3/10 יהיו גדולים ממנו, מה שמונע את המקרה הגרוע של חלוקה לא מאוזנת.

השוואת גישות ודגשים לבחינה

הבחינה בקורס זה דורשת לא רק הבנה של האלגוריתמים אלא גם יכולת ניתוח והשוואה ביניהם.

מיון מלא

זמן ריצה: O(n log n).
יתרונות: פשוט ליישום, נותן את כל סטטיסטיקות הסדר.
חסרונות: יקר מדי למציאת סטטיסטיקת סדר בודדת.

Randomized Select

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

Deterministic Select (Median-of-Medians)

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

דגשים לבחינה:

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

שאלות לדיון

מדוע אלגוריתם Randomized Select נחשב יעיל למרות זמן הריצה הפוטנציאלי של O(n^2) במקרה הגרוע?
כיצד בחירת קבוצות בגודל 5 (ולא 3 או 7) באלגוריתם חציון החציונים משפיעה על יחס הנסיגה ועל זמן הריצה במקרה הגרוע?
הסבירו את הקשר בין אלגוריתם Quicksort לאלגוריתם Randomized Select. מהם הדמיון והשוני ביניהם?
תארו מצב שבו הייתם מעדיפים להשתמש ב-Deterministic Select על פני Randomized Select, ומצב הפוך.

נקודות לתשובת מודל

הגדרת בעיית סטטיסטיקת הסדר והצורך באלגוריתמים יעילים.
תיאור הגישות הנאיביות (מיון, ערימה) וניתוח זמן הריצה שלהן.
הסבר מפורט של אלגוריתם Randomized Select, כולל פונקציית החלוקה, ניתוח זמן ריצה ממוצע (O(n)) ומקרה גרוע (O(n^2)), ויחס הנסיגה המתאים.
הסבר מפורט של אלגוריתם Deterministic Select (Median-of-Medians), כולל שלבי בחירת הציר, ניתוח זמן ריצה במקרה הגרוע (O(n)), ויחס הנסיגה המורכב שלו.
השוואה ביקורתית בין האלגוריתמים השונים, תוך התייחסות למורכבות, יעילות, ומתי כל אחד מתאים לשימוש.
הדגשת חשיבות ניתוח יחסי נסיגה והבנת המקרים השונים (ממוצע מול גרוע).

מצאתם טעות או שחסר משהו?