מדעי המחשב קיץ תשפ"ד 899271 2024 פתרון מלא שאלה אחת בשפת Java שאלון בגרות שאלה מספר 3 Java שאלה שלוש מעקב רקורסיה שפת C#

3.א.2.

הפעולה what מסירה את כל החוליות שערכן x ומחזירה את הרשימה החדשה.

3.א.3.

הסיבוכיות של הפעולה what היא O(n) כאשר n הוא אורך שרשרת החוליות.

3.ב.2.

הפעולה guess מסירה את כל האיברים הכפולים, כלומר משאירה עותק ראשון (זה שהכי קרוב לראש הרשימה lst) ואת שאר העותקים היא מסירה.

3.ב.3:

הפעולה guess עצמה סורקת את כל n חוליות (כאשר n הוא אורך הרשימה). בכל סריקה של חוליה היא מבצעת את הפעולה what שהיא בעצמה בעלת סיבוכיות O(n) לכן סך כל הסיבוכיות הוא O(n^2)