التحليل المقارب / الأسمبيوتي
هو نوع من أنواع التحليل الرياضي لمعرفة مدى استمرارية الخوارزميات ووقتها لتقييم سلوكها .
وهي الطريقة الرئيسية لقياس كفاءة الخوارزميات , فمن غير المنطقي حساب خوارزميتين على جهازين مختلفين لأن هناك عوامل كثيرة قد تؤدي لنتائج مختلفة مثل :
نظام التشغيل
عتاد الجهاز
المساحة الشاغرة في الجهاز
بيئة البرمجيات
وربما الشبكة حتى
ومن غير المنطقي كذلك قياس خوارزميتين مبنيتان على لغات برمجة مختلفة , فلذلك نستخدم التحليل الرياضي المقارب لقياس كفاءة الخوارزميات
يعتمد التحليل المقارب على حجم المدخلات في الخوارزمية أو البرنامج لقياس كفاءتها مقارنة ببقية الطرق السابقة.
المدخلات
بإفتراض أن المدخلات هي :
n
من الأرقام , إذا كان الرقم صغيراً فإن الحاسوب سيستغرق وقتاً أقل في العملية ويزيد الوقت بزيادة عدد المدخلات
وهناك ثلاث حالات رئيسية لقياس مدى كفاءة الدالة في التحليل المقارب :
- الحالة الاسوأ / Worst Case :
الحد الأعلى للدالة ويُمثل بهذا الشكل :
O(n)
حيث أن ال:
O = >
بما معناه أن الخوارزمية
>(n)
- الحالة الأفضل / Best Case :
وهي تمثل الحد الأدنى للدالة وتكون بهذا الشكل :
Ω(n)
والΩ تعرف بالأوميجا
وتكون الخوارزمية بهذا الشكل :
<(n)
- الحالة العادية / Average Case
وهي الحالة المتوسطة أو المتوقعة لأداء الخوارزمية وتكون بهذا الشكل :
Θ(n)
والعلامة هذه تدعى ثيتا , وهي نفسها علامة المساواة :
=(n)
وغالباً سنستخدم الحالة الأولى في قياس أغلب أداء الخوارزميات لمعرفة الحد الأعلى لأداء الخوارزمية , وسنتعرف على الفروقات بين عديد من الخوارزميات
أمثلة
#include <iostream>
using namespace std;
int main() {
int arr[1] = { 0 };
int arr[2] = { 0 };
int arr[3] = { 0 };
return 0;
}وخصوصاً هذه الجزئية :
int arr[1] = { 0 };
int arr[2] = { 0 };
int arr[3] = { 0 };بإعطاء كل نوع جديد من الأوامر قيمة محددة , نلاحظ هنا أن كل الأوامر الثلاثة إنشاء مصفوفات أي أنها تحمل نفس القيمة وهي :
c1 - cost 1
وهي قيمة متكررة سيفهمها الحاسوب دون الحاجة لإنشاء قيمة أخرى
وكأن حسبة الكود ستكون بهذا الشكل :
c1 + c1 + c1
أو بالأصح
c1 * N حيث أن ال :
N
عدد من تكرارات الأمر
وسنجد أن معدل الأداء الخاص بالخوارزمية سيكون :
O(n)
مثال آخر
#include <iostream>
using namespace std;
int main() {
for(i=0;i<n;i++) { // c1
int arr[1] = {0}; //c2
}
return 0;
}يُحسب الفور لوب كقيمة والدالة قيمة أخرى كونهما ليسا نفس الأمر والقاعدة ويتم حسابها بهذا الشكل :
c1 * (N+1) + c2 * N
القيمة هذه :
N+1 هي بسبب الفور لوب
وسيكون معدل الأداء :
O(n^2)
معدل الزيادة
معدل زيادة :
500n^3
هو :
O(n^3)
أمثلة أخرى :
3n is O(n)
n lg n is O(n lg n)
مقارنة بين معدل أداء الخوارزميات
