contents
- what is asymptotic analysis
- how does asymptotic analysis help us choose the best algorithm
ما هو التحليل المقارب
في هذا النوع من التحليل، نقوم بتقييم أداء الخوارزمية بناءً على حجم المدخلات. لا نقيس الزمن الفعلي للتشغيل، بل نحسب كيف يزداد الوقت أو استهلاك الذاكرة مع زيادة حجم البيانات المدخلة. مثال للتوضيح لنفترض أن لدينا مصفوفة مرتبة تصاعديًا ونريد البحث عن عنصر معين بداخلها. لدينا طريقتان للبحث إما باستخدام البحث الخطي الذي تعقيده O(n) أو البحث الثنائي الذي تعقيده O(log n)، فنحن هنا نستخدم التحليل المتقارب لاختيار الخوارزمية الأفضل لعملية البحث.
كيف يساعدنا التحليل المقارب في اختيار الخوارزمية الأفضل
لنفترض السيناريو التالي قمنا بتشغيل البحث الخطي على جهاز سريع جدًا. وقمنا بتشغيل البحث الثنائي على جهاز أبطأ. ماذا سيحدث؟بالنسبة لحجم صغير من البيانات، قد يكون الجهاز الأسرع قادرًا على تنفيذ البحث الخطي في وقت أقل، لكن عند زيادة حجم البيانات (مثلاً 2000 أو 10,000 عنصر)، سيبدأ البحث الثنائي في العمل بشكل أسرع من البحث الخطي، حتى لو كان يعمل على جهاز أبطأ. وذلك حصل لأن معدل نمو البحث الثنائي هو لوغاريتمي، مما يعني أنه يزيد ببطء مع زيادة حجم المدخلات. بينما معدل نمو البحث الخطي هو خطي، مما يعني أنه يصبح أبطأ بكثير عند التعامل مع بيانات كبيرة.
