student (guest) 14 Sep 2016 11:24
זו השאלה שבה נתנו לנו רשימת קשתות ממויינת ע"פ משקל, כאשר משקל כל קשת הוא w(ei) = floor(i/5, ונתבקשנו למצוא את כל הקשתות המוכלות בעפ"מ.
האם ניתן לעשות זאת ב-O(1) ע"י האלגוריתם הבא:
אנו יודעים שמלבד 3 הקשתות הראשונות לכל קשת משקל שונה. לכן אנו יכולים לקחת את n+2 הקשתות הקלות ביותר, ועבור 3 הראשונות לבדוק האם הן מוכלות בעפ"מ כלשהו ובפרט בכל עפ"מ ע"ב האלגוריתמים שנלמדו במסגרת שיעורי הבית שבודקים את הדברים האלה (זריקת כל הקשתות הכבדות מהקשת הנבדקת, הרצת DFS ממנה ובדיקה האם היא נמצאת במעגל, ואם כן האם היא הקשת הכבדה ביותר במעגל).
האלגוריתם לבדיקה הוא ליניארי, ומכיוון שידוע שיש רק 3 קשתות הוא ייתבצע בזמן קבוע.
כעת: אם גילינו שיש 2 קשתות מתוך השלוש שחייבות להופיע בכל עפ"מ - נזרוק את הקשת הn+2 מהרשימה.
אם גילינו ששלושתן חייבות להיות בכל עפ"מ - נזרוק גם את הקשת ה-n+1.
אחרת - נחזיר את כל הרשימה {1,…..n+2}.
לסיכום: זריקת כל הקשתות הלא רלוונטיות - זמן קבוע כי הרשימה ממויינת.
הבדיקות על הקשתות הקלות ביותר שצויינו - גם זמן קבוע.
סכ"ה אלגוריתם רץ בזמן קבוע.
האם זה נכון?
