מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/החסם התחתון על מיון מבוסס-השוואות

כל שיטות המיון שראינו: מיון הכנסה, מיון מיזוג וQuicksort - כולן עבדו בסיבוכיות $\displaystyle \Omega (n\log(n))$ במקרה הטוב. האם אפשר לרדת נמוך מכך?

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

כדאי לדעת: בספר הקורס, הפרק "Sorting in Linear Time" עוסק בנושאים אלה. עם זאת, אנו נעסוק בנושא בגישה שונה מזו של הספר, גישה המבוססת על סיבוכיות קולמוגורוב.

מיון מבוסס השוואות

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

דוגמה: להלן הפסוודו-קוד של מיון הכנסה. שים לב ל4, שם כתובValues[j] > Values[j - 1].‏ הקוד משווה איברים, אך אינו בודק, לדוגמה, אם Values[j] הוא זוגי. למעשה, האלגוריתם אינו יודע האם Values בכלל מורכב ממספרים (שלמים). # Insertion sort. # Takes an array (Values). # Sorts the array in increasing order. Insertion-Sort(Values) 1 for i in [1, ..., Length(Values)] 2 v = Values[i] # Insert v into the correct position of Values[1, ..., i]. 3 j = i 4 while j > 1 and Values[j - 1] > v 5 Values[j] = Values[j - 1] 6 --j 7 Values[j] = v

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

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

מגבלת מיון מבוסס-השוואות

בשאר הדף נוכיח את המשפט הבא.

משפט: כל מיון מבוסס-השוואות פועל במקרה הגרוע בזמן $\displaystyle \Omega (n\cdot \log(n))$.‏

ההוכחה הנה קומבינטורית, ואינה קצרה במיוחד. שאר הדף עוסק בהוכחה.

בעיה קומבינטורית בקבצים

משפט: מספר הקבצים השונים, שאורך כל אחד מהם לכל היותר $\displaystyle n'$ ביטים, הוא $\displaystyle 2\cdot 2^{n'}-1$.‏

הוכחה: יש בדיוק קובץ אחד בעל 0 ביטים: הקובץ הריק. יש בדיוק 2 קבצים באורך 1 ביט: הקובץ המורכב מ"0", והקובץ המורכב מ"1". יש בדיוק 4 קבצים באורך 2 ביטים: אלה המורכבים מ"00", "01", "10", ו"11". באופן כללי, יש $\displaystyle 2^{i}$ קבצים באורך $\displaystyle i$ ביטים. מספר הקבצים שאורך כל אחד מהם הוא לכל היותר $\displaystyle n'$ ביטים, הוא, לכן, $\displaystyle 1+2+4+\ldots +2^{n'}=2\cdot 2^{n'}-1$.

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

דוגמה: בתחנה מטאורולוגית מודדים מדי יום את הטמפרטורה, הנעה בין $\displaystyle -40$ ל$\displaystyle 60$ מעלות (כלומר, יש 101 אפשרויות). רוצים לשמור, מדי יום, קובץ המתאר את הטמפרטורה באותו היום. נוכיח שלא ייתכן שבכל יום משתמשים בקובץ שארכו לכל היותר 2 ביטים. הוכחה: ראשית נשים לב שלצורך ההוכחה, אין שום צורך שנדע מהי השיטה שלפיה ייקבעו את תוכן הקבצים. איננו צריכים לדעת האם יכתבו את המעלות באנגלית, אורדו, או ייצוג בינרי. כבר ראינו שיש $\displaystyle 7=2\cdot 2^{2}-1$ קבצים כאלה, ו$\displaystyle 7<101$.

דוגמה: מפעילים את תכנת הכיווץ bzip2 על כל הקבצים האפשריים באורך $\displaystyle n$; מוצאים שאורך קובץ הפלט הארוך ביותר הוא $\displaystyle n'$. נוכיח ש$\displaystyle n'=\Omega (n)$. הוכחה: ראשית, נשים לב שלצורך ההוכחה, אין שום צורך שנדע מהי בדיוק תכנת הקיבוץ הנ"ל, או נדע כיצד היא פועלת. מעט קומבינטוריקה תספיק. נשים לב שיש בדיוק $\displaystyle 2^{n}$ קבצי קלט שונים, ויש $\displaystyle 2\cdot 2^{n'}-1$ קבצי פלט שונים. נפתור $\displaystyle 2\cdot 2^{n'}-1\geq 2^{n}$, ונקבל את התוצאה המבוקשת (לאחר מעט פישוטים לא קשים).

בעיה קומבינטורית בפרמוטציות

הגדרה: נתונה קבוצה $\displaystyle A$. פרמוטציה של $\displaystyle A$ היא סידור כלשהו של איבריה.

דוגמה: נניח שהקבוצה היא $\displaystyle \{Koko,Menash,Nechama\}$. אז הסידור $\displaystyle <Koko,Menash,Nechama>$ (קוקו ראשון, מנש שני, נחמה אחרונה) הוא פרמוטציה של הקבוצה, וכן הסידור $\displaystyle <Menash,Koko,Nechama>$ (מנש ראשון, קוקו שני, נחמה אחרונה) הוא פרמוטציה של הקבוצה (יש גם פרמוטציות אחרות).

המשפט הבא טריביאלי.

דוגמה: אם $\displaystyle A$ היא קבוצה בגודל $\displaystyle n$, אז יש $\displaystyle n!$ פרמוטציות שונות ל$\displaystyle A$.

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

משפט: נתונה קבוצה $\displaystyle A$. מוצאים את כל הפרמוטציות שלה, ולכל פרמוטציה, רושמים בקובץ מידע שיאפשר לנו לשחזר את הפרמוטציה. אם אורך הקובץ הארוך ביותר הוא $\displaystyle n'$, אז $\displaystyle n'=\Omega (n\cdot \log(n))$.

הוכחה: ראשית נשים לב שבדיוק כמו מקודם (כשדברנו על תכנית הכווץ), אין צורך שנחשוב איזה מידע בדיוק נרשום כדי שנוכל לשחזר את הפרמוטציה. הטענה שוב קומבינטורית. נשים לב שיש בדיוק $\displaystyle n!$ פרמוטציות, ויש $\displaystyle 2\cdot 2^{n'}-1$ קבצי פלט שונים. נפתור $\displaystyle 2\cdot 2^{n'}-1\geq n!$, ונקבל

$\displaystyle 2\cdot 2^{n'}-1\geq n!$
$\displaystyle 2\cdot 2^{n'}\geq n!$
$\displaystyle \log(2\cdot 2^{n'})\geq \log(n!)$
$\displaystyle 1+\log((2^{n'})\geq \log(n!)$
$\displaystyle \log(2^{n'})\geq \log(n!)-1$
$\displaystyle n'\geq \log(n!)-1$
$\displaystyle n'=\Omega (n\cdot \log(n))$

(את המעבר האחרון ראינו כבר בטורים שימושיים בסדרי גדילה.)

מיון מבוסס-השוואות ופרמוטציות

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

דוגמה: נניח שהקבוצה היא $\displaystyle \{Koko,Menash,Nechama\}$, והפרמוטציה היא $\displaystyle <Menash,Koko,Nechama>$. רוצים לרשום בקובץ בדיוק מספיק מידע כדי לדעת שהאיבר הראשון בפרמוטציה הוא השני מבחינת הסדר המקורי (נניח, האלפבתי), האיבר השני בפרמוטציה הוא הראשון מבחינת הסדר המקורי, והאיבר השלישי בפרמוטציה הוא השלישי מבחינת הסדר המקורי.

כדוגמה למיון מבוסס-השוואות, נשתמש במיון הכנסה.

תהליך הכתיבה

תחילה מייצרים מערך בו כל איבר הוא זוג: הזוג ה$\displaystyle i$ מורכב מהאיבר ה$\displaystyle i$ בקבוצה, ומהמיקום $\displaystyle j$ של איבר מקורי זה בפרמוטציה.

דוגמה: נניח שהקבוצה היא $\displaystyle \{Koko,Menash,Nechama\}$, והפרמטציה היא $\displaystyle <Menash,Koko,Nechama>$. אז המערך הוא [(Koko, 2), (Menash, 1), (Nechama, 3)].

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

Compare-And-Print(x, y)
1	if x > y
2		Print 1
3		return True

4	Print 0
5	return False


Insertion-Sort-Zip(Values)
1	for i in [1, ..., Length(Values)]
2		v = Values[i]

		# Insert Values[j] into the correct position of Values[1, ..., j].
3		j = i
4		while j > 1 and Compare-And-Print(Values[j - 1], v)
5			Values[j] = Values[j - 1]
6			--j

7		Values[j] = v

דוגמה: נניח שהמערך הוא [(Koko, 2), (Menash, 1), (Nechama, 3)]. אם נקרא לInsertion-Sort-Zip, האלגוריתם ידפיס 10. בפעם הראשונה בודקים האם (Koko, 2) > (Menash, 1); התשובה היא True, ולכן מדפיסים 1. בפעם השניה בודקים האם (Koko, 2) > (Nechama, 3); התשובה היא False, ולכן מדפיסים 0.

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

תהליך הקריאה

כדי לקרוא (ולשחזר) את הפרמוטציה, לוקחים מערך של איברי הקבוצה בסדר המקורי, ואת רצף הביטים שבקובץ.

דוגמה: נניח שהקבוצה היא $\displaystyle \{Koko,Menash,Nechama\}$, ורצף הביטים הוא מה שקיבלנו לפני כן - 10.לוקחים את המערך [Koko, Menash, Nechama], ואת רצף הביטים 10.

כעת משנים את אותו אלגוריתם המיון (במקרה זה, Insertion-Sort) כך שכשהוא צריך להשוות בין שני איברים, הוא קורא ביט ומחליט מה לעשות. מריצים אלגורתים זה.

Read-And-Compare(x, y)
1	if Read() == 1
2		return True

3	return False



Insertion-Sort-Unzip(Values)
1	for i in [1, ..., Length(Values)]
2		v = Values[i]

		# Insert Values[j] into the correct position of Values[1, ..., j].
3		j = i
4		while j > 1 and Read-And-Compare(Values[j - 1], v)
5			Values[j] = Values[j - 1]
6			--j

7		Values[j] = v

מעצם הצורה שבה בנינו את שני האלגוריתמים, קל לראות את המשפט הבא:

משפט: תהליך הקריאה (והשחזור) אכן משחזר את הפרמוטציה המקורית.

דוגמה: מתחילים עם המערך [Koko, Menash, Nechama], ורצף הביטים 10.ההשוואה הראשונה ב4 בודקת האם Koko > Menash. היות שהביט הראשון הוא 1, התשובה היא True.‏ 5 תחליף בין האיברים. ההשוואה השניה ב4 בודקת האם Koko > Nechama. היות שהביט השני הוא 0, התשובה היא False.

הוכחת החסם התחתון

כעת נוכל להוכיח את החסם התחתון על זמן הריצה של מיון מבוסס-השוואות.

הוכחה: נזכר בנקודות הבאות שכבר ראינו:

1. כל אלגוריתם מיון מבוסס-השוואות יכול לשמש לכתיבת קובץ המתאר פרמוטציה של קבוצה שאיבריה ידועים, כך שנתן לקרוא ולשחזר את הפרמוטציה.
2. מספר הביטים שהפונקציה מדפיסה עבור פרמוטציה כלשהי, הוא בדיוק מספר הפעמים בהם היא משווה איברים עבור אותה פרמוטציה.
3. אם אורך הקבוצה הוא $\displaystyle n$, ואורך הקובץ הארוך ביותר הוא $\displaystyle n'$, אז $\displaystyle n'=\Omega (n\cdot \log(n))$.

משילוב המשפטים הקודמים קל לראות שלכל אלגוריתם מיון מבוסס-השוואות, קיימת פרמוטציה לה נדרשות $\displaystyle \Omega (n\cdot \log(n))$ פעולות השוואה כדי למיינה. היות שכל פעולת השוואה היא $\displaystyle \Omega (1)$, אז זמן הריצה הוא $\displaystyle \Omega (n\cdot \log(n))$.

הפרק הקודם: Quicksort

החסם התחתון על מיון מבוסס-השוואות

הפרק הבא: אלגוריתמים למיון בזמן לינארי