Time and Space Complexity

تعقيد الوقت:

• أفضل حالة: O(n)
  • عندما تكون المصفوفة مرتبة بالفعل، يقوم الفرز بالإدراج (Insertion Sort) بتمريرة واحدة فقط لتأكيد الترتيب.
• الحالة المتوسطة والأسوأ: O(n²)
  • في الحالات المتوسطة والأسوأ، يستغرق الأمر وقتاً تربيعياً لأنه، لكل عنصر، قد نحتاج إلى المقارنة والإزاحة عبر الجزء المرتب بالكامل.

تعقيد المساحة:

• O(1)
  • الفرز بالإدراج (Insertion Sort) هو خوارزمية "في المكان" (in-place)، مما يعني أنها لا تتطلب ذاكرة إضافية تتناسب مع حجم المدخلات.
  • تظل المساحة المستخدمة للفرز ثابتة، بغض النظر عن حجم المدخلات.

ملخص:

• الفرز بالإدراج (Insertion Sort) فعال لمجموعات البيانات الصغيرة أو المصفوفات المرتبة تقريباً.
• إنه أقل ملاءمة لمجموعات البيانات الكبيرة بسبب تعقيد الوقت التربيعي.
• تعقيد المساحة ثابت، مما يجعله فعالاً من حيث استخدام الذاكرة لأي حجم مدخلات.