التحليل المقارب / الأسمبيوتي

هو نوع من أنواع التحليل الرياضي لمعرفة مدى استمرارية الخوارزميات ووقتها لتقييم سلوكها .

وهي الطريقة الرئيسية لقياس كفاءة الخوارزميات , فمن غير المنطقي حساب خوارزميتين على جهازين مختلفين لأن هناك عوامل كثيرة قد تؤدي لنتائج مختلفة مثل :

ومن غير المنطقي كذلك قياس خوارزميتين مبنيتان على لغات برمجة مختلفة , فلذلك نستخدم التحليل الرياضي المقارب لقياس كفاءة الخوارزميات

يعتمد التحليل المقارب على حجم المدخلات في الخوارزمية أو البرنامج لقياس كفاءتها مقارنة ببقية الطرق السابقة.

المدخلات

بإفتراض أن المدخلات هي :

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)

مقارنة بين معدل أداء الخوارزميات

رسم بياني يوضح الفرق بين معدلات الأداء


أضغط هنا لتحميل شابتر إضافي عن التحليل المقارب

مصادر ومراجع