תרגול אלגוריתמים לגאמא: סיבוכיות ומבני נתונים

מאת ארז ברזאני · תרגול מקורי של GammaCyber

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

דוגמה: לא כל לולאה כפולה היא אותה עבודה

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

בחירת מבנה נתונים

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

תרגול עצמאי עם הסברים

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

שאלה 1: מה סיבוכיות סריקה אחת על n איברים?

  1. O(n)
  2. O(log n)
  3. O(n²)
תשובה והסבר

O(n): כל איבר נבדק פעם אחת בגוף בעל עלות קבועה.

שאלה 2: מה נדרש לחיפוש בינארי רגיל במערך?

  1. סדר מתאים
  2. שהמערך ריק
  3. מיון אקראי
תשובה והסבר

סדר מתאים: הסדר מאפשר לשלול חצי מהטווח בכל השוואה.

שאלה 3: מה מחסנית מוציאה ראשונה?

  1. את האחרון שהוכנס
  2. את הראשון שהוכנס
  3. אקראי
תשובה והסבר

את האחרון שהוכנס: מחסנית מקיימת LIFO.

שאלה 4: שתי לולאות מלאות זו בתוך זו, כל אחת n צעדים: כמה פעולות גוף?

  1. n
  2. n²
  3. log n
תשובה והסבר

n²: לכל אחד מ־n הצעדים החיצוניים מבוצעים n צעדים פנימיים.

שאלה 5: מה הבעיה בקביעת O(1) תמיד ל־hash lookup?

  1. מקרי התנגשויות והנחות המימוש
  2. אין בעיה
  3. hash דורש מיון תמיד
תשובה והסבר

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

שאלה 6: מהי טענת נכונות של אלגוריתם?

  1. שהוא מחזיר תוצאה לפי החוזה לכל קלט בתחום
  2. שהוא קצר
  3. שהוא משתמש בלולאה אחת
תשובה והסבר

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

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

הצעד הבא בלמידה

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

לשיעור הקשור בקורסלמפת הקורס וחלוקת התוכן

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

להמשך תרגול

מקורות טכניים וגבולות התרגול

המקורות מסבירים טכנולוגיה. הם אינם אסמכתה למבנה מיון צבאי. התוכן כאן עצמאי; הנחיות הזימון האישי הן הקובעות. מצאתם שגיאה? כתבו לנו.