قائمة مصطلحات التعلم الآلي (15): التحليل المقارب Asymptotic Analysis

يعد التحليل المقارب في التحليل الرياضي ، طريقة لوصف سلوك النهايات. التحليل المقارب هو عملية حساب وقت تشغيل الخوارزمية في الوحدات الرياضية للعثور على قيود البرنامج ، أو “أداء وقت التشغيل”. الهدف هو تحديد أفضل حالة وأسوأها ومتوسط ​​الوقت المطلوب لتنفيذ مهمة معينة. على الرغم من أن التحليل المقارب لا يعتبر طريقة من طرق التدريب العميق ، إلا أنه أداة تشخيصية مهمة للمبرمجين لتقييم كفاءة الخوارزميات ، بدلاً من دقتها فقط.

كتوضيح، افترض أننا مهتمون بخصائص الدالة 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): يرسم كلاً من حدود وقت التشغيل العلوية والسفلية ، مع إعتبار سيناريو الحالة المتوسطة كمتوسط ​​بين كل حد.

 

يمكن مشاهدة الفيديو التالي لتوضح الفكرة أكثر يمكن تفعيل الترجمة العربية للفيديو – الترجمة تلقائية –

 

Share on facebook
فاسبوك
Share on twitter
تويتر
Share on linkedin
لينكد إن
Share on whatsapp
واتساب

اترك تعليقاً

المشاركات الاخيرة

أحدث التعليقات

أفحص بحثك بالمجان

رفع الملف