معايير تحديد زمن التنفيذ  

*المعايير المستخدمة في تحديد زمن التنفيذ**

& خطوات العد Steps Counting

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

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

& ويمكن وصف هذه الخطوات بدالة حجم الإدخال. وبالطبع يختلف تعريف الخطوة من نموذج تقني إلى اخر .

وبشكل بديهي فإن عمليات المقارنة والإضافة ومبادلة رقمين هي عمليات اساسية مقبولة عموما في معظم النماذج، كل من هذه العمليات يتطلب عدد ثابت من وحدات أو دورات الزمن في نموذج الحواسيب SISD (الذي يحوي معالج وحيد).

يمكن الحصول على زمن تتفيذ خوارزمية التوازي بعد نوعين من الخطوات:

خطوات الحساب وخطوات الاضطراب أو الدوران steps Routing.

خطوة الحساب هي عملية رياضية أو منطقية تنفذ على عنصر بيانات في المعالج.

من ناحية أخرى فإنه في خطوة الاضطراب ينتقل عنصر البيانات من أحد المعالجات إلى آخر عن طريق الذاكرة المقسمة أو عن طريق شبكة الاتصالات.

من أجل مسألة بحجم n فإن زمن تتفيذ اسوا حالة توازي في خوارزمية هو دالة في n سنرمز لها بـ t

(n)

كما أن زمن لتتفيذ هو ايضا دالة لعدد المعالجات.

عموما الخطوت الحسابية والخطوات الاضطرابية لا تتطلب بالضرورة نفس عدد وحدات الزمن حيث ان خطوة الاضطراب عادة تعتمد على المسافة بين المعالجات ونموذجيا تأخذ زمن نتتفيذ أقل طولا من الحسابية. &

& 2- الحدود الدنيا والعلبا BOUNDS UPPER AND LOWER

من الشائع بين مصممي الخوارزميات في مسألة حسابية مصممة فقط من أجل خوارزمية تسلسلية جديدة تطبيق السؤالين التاليين:

1- هل هذه هي الخوارزمية المحتملة الأسرع للمسألة ؟

2- إذا لم تكن كذلك كيف يمكن مقارنتها مع الخوارزميات الأخرى الموجودة لنفس المسألة ؟

تحصل الإجابة عن السؤال الأول عادة عن طريق مقارنة عدد الخطوات المنفذة من الخوارزمية لمعرفة الحد الأننى لرقم الخطوات المطلوبة لحل المسألة في أسوأ حالة.

مثال :

لنقل أننا نرغب بحساب حاصل ضرب مصفوفتين (nXn) . بما أن المصفوفة تتطلب n2 إدخال علـى الأقل فإن هذه الخطوات العديدة مطلوبة من أي خوارزمية ضرب