שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2016 - רשימות מקושרות

עבור כל אחת מהפעולות שבטבלה, ציינו מהו סדר גודל זמן הריצה הדרוש כדי לבצע את הפעולה ברשימה מקושרת ממוינת בסדר עולה (מהקטן לגדול) וברשימה מקושרת שאינה ממוינת. כלומר, עליכם להתייחס לאלגוריתם יעיל ככל האפשר ולכתוב מה סדר גודל זמן הריצה שלו. כל זאת ללא שימוש ברשימות עזר, כלומר בסיבוכיות מקום קבועה $O(1)$, ובלי לשנות את אופי הרשימות (ממוינת/לא ממוינת). אורך הרשימה הוא $n$. זכרו שיש גישה אך ורק לראש הרשימה, והרשימה היא חד-סטרית. הפעולה: - הוצאת המינימום מהרשימה - בדיקה האם יש שני איברים שווים ברשימה - בדיקה מה ההפרש הקטן ביותר בין שני איברים כלשהם ברשימה - בדיקה אם איבר x נמצא ברשימה - צירוף שתי רשימות באורך n לרשימה אחת (ממוינת או לא ממוינת, כמו המקוריות) - מציאת האיבר השכיח ברשימה (האיבר שנמצא הכי הרבה פעמים ברשימה) (יש לציין זמן ברשימה ממוינת וזמן ברשימה לא ממוינת עבור כל פעולה). שימו לב, אינכם צריכים לכתוב את האלגוריתם אלא רק את הסיבוכיות של האלגוריתם היעיל ביותר.

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

פתרון: להלן ניתוח סיבוכיות זמן הריצה עבור כל פעולה, בהינתן רשימה מקושרת באורך $n$ וסיבוכיות מקום $O(1)$. **1. הוצאת המינימום מהרשימה** * **רשימה ממוינת:** ברשימה הממוינת בסדר עולה, האיבר המינימלי הוא תמיד האיבר הראשון (הראש). גישה לראש הרשימה היא פעולה שלוקחת זמן קבוע. **סיבוכיות זמן:** $O(1)$. * **רשימה לא ממוינת:** יש לעבור על כל איברי הרשימה כדי למצוא את המינימום. נאתחל משתנה שיחזיק את הערך המינימלי שמצאנו עד כה עם ערך האיבר הראשון, ולאחר מכן נעבור על שאר $n-1$ האיברים ונעדכן את המשתנה בכל פעם שנמצא איבר קטן יותר. **סיבוכיות זמן:** $O(n)$. **2. בדיקה האם יש שני איברים שווים ברשימה** * **רשימה ממוינת:** מכיוון שהרשימה ממוינת, אם קיימים איברים שווים, הם חייבים להיות סמוכים זה לזה. לכן, ניתן לעבור על הרשימה פעם אחת בלבד ולהשוות כל איבר עם האיבר הבא אחריו. אם נמצא זוג איברים סמוכים שווים, נדע שקיים איבר שמופיע יותר מפעם אחת. **סיבוכיות זמן:** $O(n)$. * **רשימה לא ממוינת:** בהיעדר זיכרון עזר, עלינו להשוות כל איבר עם כל איבר אחר ברשימה. ניתן לעשות זאת באמצעות שני מצביעים (המממשים לולאה מקוננת). המצביע החיצוני יתקדם איבר-איבר, ועבור כל איבר שהוא מצביע עליו, המצביע הפנימי יסרוק את כל האיברים שאחריו וישווה אותם לאיבר הנוכחי. מספר ההשוואות הוא מסדר גודל של $n^2$. **סיבוכיות זמן:** $O(n^2)$. **3. בדיקה מה ההפרש הקטן ביותר בין שני איברים כלשהם ברשימה** * **רשימה ממוינת:** ברשימה ממוינת, ההפרש הקטן ביותר יהיה תמיד בין שני איברים סמוכים. נוכיח זאת בשלילה: נניח שההפרש המינימלי הוא בין $a_i$ ל-$a_j$ כאשר $j > i+1$. היות שהרשימה ממוינת, מתקיים $a_i \le a_{i+1} \le a_j$. לכן, $a_{i+1} - a_i \le a_j - a_i$. מכאן שההפרש בין זוג סמוך ($a_i, a_{i+1}$) קטן או שווה להפרש בין הזוג המקורי. לפיכך, מספיק לעבור על הרשימה פעם אחת ולחשב את ההפרש בין כל זוג איברים סמוכים, ולשמור את המינימום. $\blacksquare$ **סיבוכיות זמן:** $O(n)$. * **רשימה לא ממוינת:** בדומה לבדיקת כפילויות, עלינו לחשב את ההפרש בין כל זוג אפשרי של איברים ברשימה. נשתמש בלולאה מקוננת כדי לעבור על כל הזוגות, נחשב את הערך המוחלט של ההפרש ביניהם, ונשמור את ההפרש המינימלי שמצאנו. **סיבוכיות זמן:** $O(n^2)$. **4. בדיקה אם איבר x נמצא ברשימה** * **רשימה ממוינת:** יש לבצע **חיפוש לינארי**. מתחילים מראש הרשימה ומתקדמים איבר אחר איבר. ניתן לעצור את החיפוש אם נתקלים באיבר שערכו גדול מ-$x$, מכיוון שכל האיברים הבאים יהיו גדולים ממנו גם כן. למרות אופטימיזציה זו, במקרה הגרוע (כאשר $x$ הוא האיבר האחרון, או גדול מכל איברי הרשימה), נצטרך לעבור על כל הרשימה. לא ניתן לבצע **חיפוש בינארי** ברשימה מקושרת רגילה כי אין גישה אקראית לאיברים. **סיבוכיות זמן:** $O(n)$. * **רשימה לא ממוינת:** האלגוריתם היחיד האפשרי הוא **חיפוש לינארי**. יש לסרוק את הרשימה מההתחלה ועד הסוף ולהשוות כל איבר ל-$x$. במקרה הגרוע, נסרוק את כל $n$ האיברים. **סיבוכיות זמן:** $O(n)$. **5. צירוף שתי רשימות באורך n לרשימה אחת** * **רשימה ממוינת:** כאשר שתי הרשימות המקוריות ממוינות, ההנחה היא שגם הרשימה המאוחדת צריכה להיות ממוינת. פעולה זו נקראת **מיזוג** (merge). ניתן למזג שתי רשימות מקושרות ממוינות בזמן לינארי ובסיבוכיות מקום קבועה על ידי שינוי המצביעים של האיברים הקיימים. עוברים על שתי הרשימות במקביל, ובכל שלב בוחרים את האיבר הקטן יותר מבין שני הראשים הנוכחיים ומוסיפים אותו לרשימה הממוזגת. **סיבוכיות זמן:** $O(n)$. * **רשימה לא ממוינת:** פעולה זו היא **שרשור** (concatenation) פשוט. כדי לשרשר את הרשימה השנייה לסוף הרשימה הראשונה, יש למצוא את האיבר האחרון ברשימה הראשונה. פעולה זו דורשת מעבר על כל הרשימה הראשונה. לאחר מכן, מכוונים את מצביע ה-`next` של האיבר האחרון להצביע על ראש הרשימה השנייה. **סיבוכיות זמן:** $O(n)$. **6. מציאת האיבר השכיח ברשימה** * **רשימה ממוינת:** ברשימה ממוינת, כל המופעים של איבר מסוים מופיעים ברצף. לכן, ניתן לעבור על הרשימה פעם אחת, לספור כמה פעמים כל איבר מופיע ברציפות, ולשמור במשתנים את האיבר השכיח ביותר עד כה ואת מספר מופעיו. **סיבוכיות זמן:** $O(n)$. * **רשימה לא ממוינת:** בהיעדר זיכרון עזר, נצטרך להשתמש בלולאה מקוננת. הלולאה החיצונית תעבור על כל איבר ברשימה. עבור כל איבר, הלולאה הפנימית תסרוק את כל הרשימה פעם נוספת כדי לספור את מספר המופעים הכולל של אותו איבר. נשמור את האיבר שהופיע הכי הרבה פעמים. **סיבוכיות זמן:** $O(n^2)$.