מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות/תרגילים/ניתוח אמורטייזד להכנסת איברים/תשובה

נניח שמספר האיברים בקלט הוא $\displaystyle n$.

א'

כל קריאה לInsert-Back של רשימה מקושרת היא $\displaystyle O(1)$, ולכן סיבוכיות הלולאה היא $\displaystyle \Theta (n)$.

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

ב'

נתבונן באיטרציה ה$\displaystyle i$ של הלולאה 3-12. בהכרח תופעל הלולאה הפנימית 9-10, וסיבוכיותה לינארית ב$\displaystyle i$. זמן הריצה הוא לכן $\displaystyle \sum _{i=1}^{n}[\Theta (i)]=\Theta (n^{2})$.

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

ג'

נתבונן באיטרציה ה$\displaystyle i$ של הלולאה 3-12. הלולאה הפנימית 9-10 תופעל אמ"ם $\displaystyle i$ חזקה של 2, וסיבוכיותה לינארית ב$\displaystyle i$. אם $\displaystyle h$ הוא מספר הפעמים שהופעלה הלולאה הפנימית, אז קל לראות שמתקיים $\displaystyle h=\log(n)\pm O(1)$.

זמן הריצה הוא לכן $\displaystyle \sum _{i=1}^{h}[\Theta (i)]=\sum _{j=1}^{\log(n)\pm O(1)}[\Theta (2^{j})]=\Theta (2^{\log(n)\pm O(1)})=\Theta (n)$.

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