يعد التحليل المقارب في التحليل الرياضي ، طريقة لوصف سلوك النهايات. التحليل المقارب هو عملية حساب وقت تشغيل الخوارزمية في الوحدات الرياضية للعثور على قيود البرنامج ، أو “أداء وقت التشغيل”. الهدف هو تحديد أفضل حالة وأسوأها ومتوسط الوقت المطلوب لتنفيذ مهمة معينة. على الرغم من أن التحليل المقارب لا يعتبر طريقة من طرق التدريب العميق ، إلا أنه أداة تشخيصية مهمة للمبرمجين لتقييم كفاءة الخوارزميات ، بدلاً من دقتها فقط.
كتوضيح، افترض أننا مهتمون بخصائص الدالة f(n) بحيث n هو عدد كبير جدًا. إذا كانت f(n) = n^2 + 3n
إذاً كلما كَبُرت n ، 3n تصبح ضئيلة مقارنة بــ n^2. يُقال أن الدالة f(n) «مكافئة بشكل مقارب لـ n^2 ، عندما n → ∞ ». غالبًا ما يتم كتابة هذا على شكل f(n) ~ n^2 ، والذي يُقرأ « f(n) مقارب لـ n^2 ».
كمثال على نتيجة مقاربة مهمة نذكر مبرهنة الأعداد الأولية . لتكن π(x) هي الدالة المعدة للأعداد الأولية، أي أن π(x) هي عدد الأعداد الأولية التي تقل عن x أو تساويها. ثم تنص المبرهنة على الآتي :
كيف يعمل التحليل المقارب؟
هذا التحليل يحتاج إلى متغير إدخال للخوارزمية ، وإلا فمن المفترض أن يتطلب العمل مقدارًا ثابتًا من الوقت. تعتبر جميع العوامل بخلاف عملية الإدخال ثابتة.
على سبيل المثال ، بفرض أن وقت تشغيل طلب تنقيب بيانات data mining معين يرمز له ب f(n) ، ويتم حساب عملية البحث الناتجة عنه على أنها g(n2). لذا فإن وقت تشغيل العملية الأولى يزداد خطيًا مع زيادة n ، بينما يزداد وقت تشغيل العملية الثانية أضعافًا مضاعفة كلما تم تكبير قيمة n.
بينما يمكن حساب أداء وقت التشغيل بمساعدة العديد من الدوال المختلفة ، يتم التعبير عن سلوك الخوارزمية بيانياً باستخدام الاتي:
Ο(n): الحد الأعلى لوقت تشغيل الخوارزمية ويقيس السيناريو الأسوأ للوقت الذي يمكن أن تستغرقه الخوارزمية لإكمال عملية معينة.
Ω(n): الحد الأدنى لوقت تشغيل الخوارزمية ويقيس أفضل سيناريو للمدة التي يمكن أن تستغرقها الخوارزمية لإكمال عملية معينة.
Θ(n): يرسم كلاً من حدود وقت التشغيل العلوية والسفلية ، مع إعتبار سيناريو الحالة المتوسطة كمتوسط بين كل حد.
يمكن مشاهدة الفيديو التالي لتوضح الفكرة أكثر يمكن تفعيل الترجمة العربية للفيديو – الترجمة تلقائية –
