סיבוכיות זמן ומקום

סיבוכיות זמן:

• מקרה מיטבי: O(n)
  • כאשר המערך כבר ממוין, Insertion Sort מבצע מעבר אחד בלבד כדי לוודא שהסדר ממוין.
• מקרה ממוצע ומקרה גרוע: O(n²)
  • במקרים הממוצע והגרוע, נדרש זמן ריבועי, משום שלכל איבר ייתכן שנצטרך להשוות איברים ולהזיז אותם לאורך כל החלק הממוין.

סיבוכיות מקום:

• O(1)
  • Insertion Sort הוא אלגוריתם "במקום", כלומר הוא אינו דורש זיכרון נוסף שגדל ביחס לגודל הקלט.
  • הזיכרון המשמש למיון נשאר קבוע, ללא תלות בגודל הקלט.

סיכום:

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