4 תשובות
כשאת רוצה למצוא את החציון של מערך גדול בצורה יעילה את משתמשת בזה.
את מחלקת את המערך לקבוצות של חמישה איברים ומוצאת את החציון של כל חמישה.
את החציונים האלו את מסדרת למערך חדש ומוצאת את החציון שלו שנקרא "חציון החציונים".
כתבתי חצי שעה אבל כבר הסבירו את זה אז בהצלחה לך, יש עוד המשך:)
את מחלקת את המערך לקבוצות של חמישה איברים ומוצאת את החציון של כל חמישה.
את החציונים האלו את מסדרת למערך חדש ומוצאת את החציון שלו שנקרא "חציון החציונים".
כתבתי חצי שעה אבל כבר הסבירו את זה אז בהצלחה לך, יש עוד המשך:)
שואל השאלה:
תודה
תודה
בעצם מחלקים את המערך לחמישיות ואז בכל חמישיה מוצאים את החציון,
ברגע שיש את זה מוצאים את החציון של החציונים (משתמשים באלגוריתם הזה רקורסיבית) ואז זורקים את האיברים הגדולים מהחציונים שגדולים מהחציון של החציונים ואותו דבר לקטנים, ככה מורידים כל פעם חלק משמעותי מהאיברים ומקבלים זמן לינארי
לא חומר של בגרות לא לפחד
ברגע שיש את זה מוצאים את החציון של החציונים (משתמשים באלגוריתם הזה רקורסיבית) ואז זורקים את האיברים הגדולים מהחציונים שגדולים מהחציון של החציונים ואותו דבר לקטנים, ככה מורידים כל פעם חלק משמעותי מהאיברים ומקבלים זמן לינארי
לא חומר של בגרות לא לפחד
אלגוריתם החמישיות, הידוע גם בשם **median of medians**, הוא שיטה למציאת החציון (או אלמנט אחר בסדר סטטיסטי) במערך בזמן לינארי \(o(n)\). זהו אלגוריתם חלוקת וכיבוש שתוכנן כדי להבטיח שמציאת האלמנט ה-k-י בגודלו (k-th order statistic) נעשית בזמן אופטימלי.
### איך זה עובד?
האלגוריתם פועל על ידי חלוקת המערך לתת-קבוצות קטנות יותר, מציאת מִיצּוּעים (ממוצעי תת-קבוצות) ובחירה של חציון מהן, אשר ישמש כאלמנט ה"ציר" (pivot) לחלוקה.
השלבים הבסיסיים של האלגוריתם:
1. **חלק את המערך לקבוצות של חמישה אלמנטים**: תחילה מחלקים את המערך המקורי לקבוצות של חמישה אלמנטים (או פחות אם נשארים פחות מאלמנטים).
2. **מצא את החציון של כל קבוצה**: לכל קבוצה מחמישה אלמנטים, מיין אותם ומצא את החציון (האלמנט האמצעי לאחר המיון). אם יש פחות מ-5, מצא חציון בדרך ישירה.
3. **צור מערך חדש מהחציון של כל קבוצה**: המערך החדש מכיל את החציונים שנמצאו עבור כל אחת מהקבוצות.
4. **מצא את חציון המערך החדש**: זהו שלב רקורסיבי, שבו משתמשים באותה שיטה כדי למצוא את החציון של המערך שנוצר מהחציון של כל הקבוצות. תוצאת החציון הזה תשמש כציר (pivot) לחלוקה הבאה.
5. **חלק את המערך לפי הציר**: בעזרת הציר שנבחר, חלק את המערך למספר חלקים אלה שקטנים מהציר, אלה ששווים לציר, ואלה שגדולים ממנו.
6. **חפש באחד החלקים**: תלוי במיקום החציון המבוקש ביחס לציר, האלגוריתם ממשיך לחפש באחד החלקים.
7. **חזרה רקורסיבית או סיום**: תהליך זה נמשך בצורה רקורסיבית עד שנמצא החציון או האלמנט ה-k-י המבוקש.
### למה זה עובד בזמן לינארי?
הטריק כאן הוא שהציר נבחר כך שהוא יוצר איזון טוב במערך המחולק. בכך שהאלמנט נבחר מתוך קבוצה של חציונים, מובטח שהחלקים לא יהיו קטנים מדי (תמיד לפחות 30% מהאלמנטים נמצאים באחד החלקים). זמן הריצה הכולל הוא \(o(n)\), מה שמבטיח יעילות גבוהה.
### איך זה עובד?
האלגוריתם פועל על ידי חלוקת המערך לתת-קבוצות קטנות יותר, מציאת מִיצּוּעים (ממוצעי תת-קבוצות) ובחירה של חציון מהן, אשר ישמש כאלמנט ה"ציר" (pivot) לחלוקה.
השלבים הבסיסיים של האלגוריתם:
1. **חלק את המערך לקבוצות של חמישה אלמנטים**: תחילה מחלקים את המערך המקורי לקבוצות של חמישה אלמנטים (או פחות אם נשארים פחות מאלמנטים).
2. **מצא את החציון של כל קבוצה**: לכל קבוצה מחמישה אלמנטים, מיין אותם ומצא את החציון (האלמנט האמצעי לאחר המיון). אם יש פחות מ-5, מצא חציון בדרך ישירה.
3. **צור מערך חדש מהחציון של כל קבוצה**: המערך החדש מכיל את החציונים שנמצאו עבור כל אחת מהקבוצות.
4. **מצא את חציון המערך החדש**: זהו שלב רקורסיבי, שבו משתמשים באותה שיטה כדי למצוא את החציון של המערך שנוצר מהחציון של כל הקבוצות. תוצאת החציון הזה תשמש כציר (pivot) לחלוקה הבאה.
5. **חלק את המערך לפי הציר**: בעזרת הציר שנבחר, חלק את המערך למספר חלקים אלה שקטנים מהציר, אלה ששווים לציר, ואלה שגדולים ממנו.
6. **חפש באחד החלקים**: תלוי במיקום החציון המבוקש ביחס לציר, האלגוריתם ממשיך לחפש באחד החלקים.
7. **חזרה רקורסיבית או סיום**: תהליך זה נמשך בצורה רקורסיבית עד שנמצא החציון או האלמנט ה-k-י המבוקש.
### למה זה עובד בזמן לינארי?
הטריק כאן הוא שהציר נבחר כך שהוא יוצר איזון טוב במערך המחולק. בכך שהאלמנט נבחר מתוך קבוצה של חציונים, מובטח שהחלקים לא יהיו קטנים מדי (תמיד לפחות 30% מהאלמנטים נמצאים באחד החלקים). זמן הריצה הכולל הוא \(o(n)\), מה שמבטיח יעילות גבוהה.