אשמח לעזרה בשאלה ממבחן - האם הפתרון שעליו חשבתי הוא נכון ואופטימלי (מבחינת יעילות).

נתון מערך באורך 2n - כאשר n תאים מכילים '0' ו-n תאים מכילים '1'. צריך לכתוב שיטה שתחזיר את מספר ההחלפות המינימלי שיביא מערך מסוג זה למערך מתחלף (010101...). לדוגמא: במידה והמערך הנתון הוא 00011011 אז מינימום ההחלפות שנדרש הוא 2 (במודגש - התאים המוחלפים):

• 00011011
  
• 00011011
  

כמובן שיכולות להיות אפשרויות נוספות לעשות זאת ב-2 צעדי החלפות, אבל זה לא משנה, מה שחשוב הוא המס' המינימלי.

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

האם הפתרון שלי הוא נכון ויעיל (היעילות של ההצעה שלי היא O(n) )?

תודה!

למה אתה קורא החלפה? החלפת תא מ-0 ל-1 למשל או החלפת 2 תאים צמודים?

החלפת המקומות (swap).

למשל בדוגמא שנתתי בצעד השני, אם נסמן את תאי המערך מ-0 עד ל-7 (משמאל לימין כמובן): אני לוקח את הערך שבתא 6, שם אותו בתא 1, ואת הערך בתא 1 שם בתא 6.

שים לב שאת ההחלפה אני לא צריך לבצע.

אם כך הפיתרון שלך נכון, רק מספיק לבדוק את המקומות האי-זוגיים בלבד ולקחת את הקטן מבין x ו-(n-x)

תודה, אבל האם עצם זה שאני סופר פעמיים, את המקומות הזוגיים והאי זוגיים, פוגעת ביעילות האלגוריתם?

מן הסתם. אמנם לא אסימפטוטית אבל הקבוע גדל פי 2.