מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/החסם התחתון על מיון מבוסס-השוואות – ויקיספר
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/החסם התחתון על מיון מבוסס-השוואות
כל שיטות המיון שראינו: מיון הכנסה, מיון מיזוג וQuicksort - כולן עבדו בסיבוכיות Ω ( n log ⁡ ( n ) ) {\displaystyle \displaystyle \Omega (n\log(n))} במקרה הטוב. האם אפשר לרדת נמוך מכך?
באופן כללי, אי אפשר למיין בצורה יעילה יותר במקרה הטוב. דף זה עוסק בזאת.
בפרק הבא, אלגוריתמים למיון בזמן לינארי, נראה שאם הקלט מקיים הנחות נוקשות יחסית, אפשר למיין בצורה יעילה יותר גם במקרה הטוב.
בספר הקורס, הפרק "Sorting in Linear Time" עוסק בנושאים אלה. עם זאת, אנו נעסוק בנושא בגישה שונה מזו של הספר, גישה המבוססת על סיבוכיות קולמוגורוב.
1 מיון מבוסס השוואות
2 מגבלת מיון מבוסס-השוואות
3 בעיה קומבינטורית בקבצים
4 בעיה קומבינטורית בפרמוטציות
5 מיון מבוסס-השוואות ופרמוטציות
5.1 תהליך הכתיבה
5.2 תהליך הקריאה
6 הוכחת החסם התחתון
מיון מבוסס השוואות[עריכה]
מיון הוא מבוסס השוואות אם הוא מבסס את החלטותיו רק ע"י השוואת האיברים זה לזה, ולא על תכונות האיברים עצמם.
להלן הפסוודו-קוד של מיון הכנסה. שים לב ל4, שם כתובValues[j] > Values[j - 1].‏ הקוד משווה איברים, אך אינו בודק, לדוגמה, אם Values[j] הוא זוגי. למעשה, האלגוריתם אינו יודע האם 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 - הנו מיון מבוסס-השוואות.
באלגוריתמים למיון בזמן לינארי נראה מיונים שאינם מבוססי השוואות.
מיון מבוסס-השוואות הוא במידה מסויימת המיון הכללי ביותר שיכול להיות, מפני שהוא מניח מעט מאוד לגבי מה שהוא ממיין: הוא יכול למיין מספרים שלמים, מספרי נקודה צפה, מחרוזות, ובעצם כל טיפוס שאפשר להשוות שני איברים מסוגו.
מגבלת מיון מבוסס-השוואות[עריכה]
בשאר הדף נוכיח את המשפט הבא.
כל מיון מבוסס-השוואות פועל במקרה הגרוע בזמן Ω ( n ⋅ log ⁡ ( n ) ) {\displaystyle \displaystyle \Omega (n\cdot \log(n))} .‏
ההוכחה הנה קומבינטורית, ואינה קצרה במיוחד. שאר הדף עוסק בהוכחה.
בעיה קומבינטורית בקבצים[עריכה]
מספר הקבצים השונים, שאורך כל אחד מהם לכל היותר n ′ {\displaystyle \displaystyle n'} ביטים, הוא 2 ⋅ 2 n ′ − 1 {\displaystyle \displaystyle 2\cdot 2^{n'}-1} .‏
הוכחה: יש בדיוק קובץ אחד בעל 0 ביטים: הקובץ הריק. יש בדיוק 2 קבצים באורך 1 ביט: הקובץ המורכב מ"0", והקובץ המורכב מ"1". יש בדיוק 4 קבצים באורך 2 ביטים: אלה המורכבים מ"00", "01", "10", ו"11". באופן כללי, יש 2 i {\displaystyle \displaystyle 2^{i}} קבצים באורך i {\displaystyle \displaystyle i} ביטים. מספר הקבצים שאורך כל אחד מהם הוא לכל היותר n ′ {\displaystyle \displaystyle n'} ביטים, הוא, לכן, 1 + 2 + 4 + … + 2 n ′ = 2 ⋅ 2 n ′ − 1 {\displaystyle \displaystyle 1+2+4+\ldots +2^{n'}=2\cdot 2^{n'}-1} .
נוכל להשתמש בזאת כדי למצוא את מספר הביטים הנדרשים במקרה הגרוע לשמירת דברים שונים.
בתחנה מטאורולוגית מודדים מדי יום את הטמפרטורה, הנעה בין − 40 {\displaystyle \displaystyle -40} ל 60 {\displaystyle \displaystyle 60} מעלות (כלומר, יש 101 אפשרויות). רוצים לשמור, מדי יום, קובץ המתאר את הטמפרטורה באותו היום. נוכיח שלא ייתכן שבכל יום משתמשים בקובץ שארכו לכל היותר 2 ביטים.
הוכחה: ראשית נשים לב שלצורך ההוכחה, אין שום צורך שנדע מהי השיטה שלפיה ייקבעו את תוכן הקבצים. איננו צריכים לדעת האם יכתבו את המעלות באנגלית, אורדו, או ייצוג בינרי.
כבר ראינו שיש 7 = 2 ⋅ 2 2 − 1 {\displaystyle \displaystyle 7=2\cdot 2^{2}-1} קבצים כאלה, ו 7 < 101 {\displaystyle \displaystyle 7<101} .
מפעילים את תכנת הכיווץ bzip2 על כל הקבצים האפשריים באורך n {\displaystyle \displaystyle n} ; מוצאים שאורך קובץ הפלט הארוך ביותר הוא n ′ {\displaystyle \displaystyle n'} . נוכיח ש n ′ = Ω ( n ) {\displaystyle \displaystyle n'=\Omega (n)} .
הוכחה: ראשית, נשים לב שלצורך ההוכחה, אין שום צורך שנדע מהי בדיוק תכנת הקיבוץ הנ"ל, או נדע כיצד היא פועלת. מעט קומבינטוריקה תספיק. נשים לב שיש בדיוק 2 n {\displaystyle \displaystyle 2^{n}} קבצי קלט שונים, ויש 2 ⋅ 2 n ′ − 1 {\displaystyle \displaystyle 2\cdot 2^{n'}-1} קבצי פלט שונים. נפתור 2 ⋅ 2 n ′ − 1 ≥ 2 n {\displaystyle \displaystyle 2\cdot 2^{n'}-1\geq 2^{n}} , ונקבל את התוצאה המבוקשת (לאחר מעט פישוטים לא קשים).
בעיה קומבינטורית בפרמוטציות[עריכה]
נתונה קבוצה A {\displaystyle \displaystyle A} . פרמוטציה של A {\displaystyle \displaystyle A} היא סידור כלשהו של איבריה.
נניח שהקבוצה היא { K o k o , M e n a s h , N e c h a m a } {\displaystyle \displaystyle \{Koko,Menash,Nechama\}} . אז הסידור < K o k o , M e n a s h , N e c h a m a > {\displaystyle \displaystyle <Koko,Menash,Nechama>} (קוקו ראשון, מנש שני, נחמה אחרונה) הוא פרמוטציה של הקבוצה, וכן הסידור < M e n a s h , K o k o , N e c h a m a > {\displaystyle \displaystyle <Menash,Koko,Nechama>} (מנש ראשון, קוקו שני, נחמה אחרונה) הוא פרמוטציה של הקבוצה (יש גם פרמוטציות אחרות).
המשפט הבא טריביאלי.
אם A {\displaystyle \displaystyle A} היא קבוצה בגודל n {\displaystyle \displaystyle n} , אז יש n ! {\displaystyle \displaystyle n!} פרמוטציות שונות ל A {\displaystyle \displaystyle A} .
אם נחבר את שתי הבעיות הקומבינטריות עליהן עברנו עד כה, נקבל את המשפט הבא.
נתונה קבוצה A {\displaystyle \displaystyle A} . מוצאים את כל הפרמוטציות שלה, ולכל פרמוטציה, רושמים בקובץ מידע שיאפשר לנו לשחזר את הפרמוטציה. אם אורך הקובץ הארוך ביותר הוא n ′ {\displaystyle \displaystyle n'} , אז n ′ = Ω ( n ⋅ log ⁡ ( n ) ) {\displaystyle \displaystyle n'=\Omega (n\cdot \log(n))} .
הוכחה: ראשית נשים לב שבדיוק כמו מקודם (כשדברנו על תכנית הכווץ), אין צורך שנחשוב איזה מידע בדיוק נרשום כדי שנוכל לשחזר את הפרמוטציה. הטענה שוב קומבינטורית. נשים לב שיש בדיוק n ! {\displaystyle \displaystyle n!} פרמוטציות, ויש 2 ⋅ 2 n ′ − 1 {\displaystyle \displaystyle 2\cdot 2^{n'}-1} קבצי פלט שונים. נפתור 2 ⋅ 2 n ′ − 1 ≥ n ! {\displaystyle \displaystyle 2\cdot 2^{n'}-1\geq n!} , ונקבל
2 ⋅ 2 n ′ − 1 ≥ n ! {\displaystyle \displaystyle 2\cdot 2^{n'}-1\geq n!}
2 ⋅ 2 n ′ ≥ n ! {\displaystyle \displaystyle 2\cdot 2^{n'}\geq n!}
log ⁡ ( 2 ⋅ 2 n ′ ) ≥ log ⁡ ( n ! ) {\displaystyle \displaystyle \log(2\cdot 2^{n'})\geq \log(n!)}
1 + log ⁡ ( ( 2 n ′ ) ≥ log ⁡ ( n ! ) {\displaystyle \displaystyle 1+\log((2^{n'})\geq \log(n!)}
log ⁡ ( 2 n ′ ) ≥ log ⁡ ( n ! ) − 1 {\displaystyle \displaystyle \log(2^{n'})\geq \log(n!)-1}
n ′ ≥ log ⁡ ( n ! ) − 1 {\displaystyle \displaystyle n'\geq \log(n!)-1}
n ′ = Ω ( n ⋅ log ⁡ ( n ) ) {\displaystyle \displaystyle n'=\Omega (n\cdot \log(n))}
(את המעבר האחרון ראינו כבר בטורים שימושיים בסדרי גדילה.)
מיון מבוסס-השוואות ופרמוטציות[עריכה]
כעת נראה שכל אלגוריתם מיון מבוסס-השוואות יכול לשמש לכתיבת קובץ המתאר פרמוטציה של קבוצה שאיבריה ידועים, כך שנתן לקרוא ולשחזר את הפרמוטציה.
נניח שהקבוצה היא { K o k o , M e n a s h , N e c h a m a } {\displaystyle \displaystyle \{Koko,Menash,Nechama\}} , והפרמוטציה היא < M e n a s h , K o k o , N e c h a m a > {\displaystyle \displaystyle <Menash,Koko,Nechama>} . רוצים לרשום בקובץ בדיוק מספיק מידע כדי לדעת שהאיבר הראשון בפרמוטציה הוא השני מבחינת הסדר המקורי (נניח, האלפבתי), האיבר השני בפרמוטציה הוא הראשון מבחינת הסדר המקורי, והאיבר השלישי בפרמוטציה הוא השלישי מבחינת הסדר המקורי.
כדוגמה למיון מבוסס-השוואות, נשתמש במיון הכנסה.
תהליך הכתיבה[עריכה]
תחילה מייצרים מערך בו כל איבר הוא זוג: הזוג ה i {\displaystyle \displaystyle i} מורכב מהאיבר ה i {\displaystyle \displaystyle i} בקבוצה, ומהמיקום j {\displaystyle \displaystyle j} של איבר מקורי זה בפרמוטציה.
נניח שהקבוצה היא { K o k o , M e n a s h , N e c h a m a } {\displaystyle \displaystyle \{Koko,Menash,Nechama\}} , והפרמטציה היא < M e n a s h , K o k o , N e c h a m a > {\displaystyle \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)
# Insert Values[j] into the correct position of Values[1, ..., j].
4		while j > 1 and Compare-And-Print(Values[j - 1], v)
נניח שהמערך הוא [(Koko, 2), (Menash, 1), (Nechama, 3)]. אם נקרא לInsertion-Sort-Zip, האלגוריתם ידפיס 10. בפעם הראשונה בודקים האם (Koko, 2) > (Menash, 1); התשובה היא True, ולכן מדפיסים 1. בפעם השניה בודקים האם (Koko, 2) > (Nechama, 3); התשובה היא False, ולכן מדפיסים 0.
מספר הביטים שהפונקציה מדפיסה עבור פרמוטציה כלשהי, הוא בדיוק מספר הפעמים בהם היא משווה איברים עבור אותה
פרמוטציה.
תהליך הקריאה[עריכה]
כדי לקרוא (ולשחזר) את הפרמוטציה, לוקחים מערך של איברי הקבוצה בסדר המקורי, ואת רצף הביטים שבקובץ.
נניח שהקבוצה היא { K o k o , M e n a s h , N e c h a m a } {\displaystyle \displaystyle \{Koko,Menash,Nechama\}} , ורצף הביטים הוא מה שקיבלנו לפני כן - 10.לוקחים את המערך [Koko, Menash, Nechama], ואת רצף הביטים 10.
כעת משנים את אותו אלגוריתם המיון (במקרה זה, Insertion-Sort) כך שכשהוא צריך להשוות בין שני איברים, הוא קורא ביט ומחליט מה לעשות. מריצים אלגורתים זה.
Read-And-Compare(x, y)
1	if Read() == 1
3	return False
Insertion-Sort-Unzip(Values)
4		while j > 1 and Read-And-Compare(Values[j - 1], v)
מעצם הצורה שבה בנינו את שני האלגוריתמים, קל לראות את המשפט הבא:
תהליך הקריאה (והשחזור) אכן משחזר את הפרמוטציה המקורית.
מתחילים עם המערך [Koko, Menash, Nechama], ורצף הביטים 10.ההשוואה הראשונה ב4 בודקת האם Koko > Menash. היות שהביט הראשון הוא 1, התשובה היא True.‏ 5 תחליף בין האיברים. ההשוואה השניה ב4 בודקת האם Koko > Nechama. היות שהביט השני הוא 0, התשובה היא False.
הוכחת החסם התחתון[עריכה]
כעת נוכל להוכיח את החסם התחתון על זמן הריצה של מיון מבוסס-השוואות.
הוכחה: נזכר בנקודות הבאות שכבר ראינו:
כל אלגוריתם מיון מבוסס-השוואות יכול לשמש לכתיבת קובץ המתאר פרמוטציה של קבוצה שאיבריה ידועים, כך שנתן לקרוא ולשחזר את הפרמוטציה.
מספר הביטים שהפונקציה מדפיסה עבור פרמוטציה כלשהי, הוא בדיוק מספר הפעמים בהם היא משווה איברים עבור אותה פרמוטציה.
אם אורך הקבוצה הוא n {\displaystyle \displaystyle n} , ואורך הקובץ הארוך ביותר הוא n ′ {\displaystyle \displaystyle n'} , אז n ′ = Ω ( n ⋅ log ⁡ ( n ) ) {\displaystyle \displaystyle n'=\Omega (n\cdot \log(n))} .
משילוב המשפטים הקודמים קל לראות שלכל אלגוריתם מיון מבוסס-השוואות, קיימת פרמוטציה לה נדרשות Ω ( n ⋅ log ⁡ ( n ) ) {\displaystyle \displaystyle \Omega (n\cdot \log(n))} פעולות השוואה כדי למיינה. היות שכל פעולת השוואה היא Ω ( 1 ) {\displaystyle \displaystyle \Omega (1)} , אז זמן הריצה הוא Ω ( n ⋅ log ⁡ ( n ) ) {\displaystyle \displaystyle \Omega (n\cdot \log(n))} .
Quicksort החסם התחתון על מיון מבוסס-השוואות הפרק הבא:
אוחזר מתוך "https://he.wikibooks.org/w/index.php?title=מבני_נתונים_ואלגוריתמים_-_מחברת_קורס/אלגוריתמים/החסם_התחתון_על_מיון_מבוסס-השוואות&oldid=124447"