التعقيدات العملية (Practical Complexities)

تعقيدات الوقت لبرنامج تكون عموما دالة في خصائص المثال. هذه الدالة مفيدة جدا لتحديد كيف تتغير متطلبات الوقت بتغير خصائص المثال. تستخدم دالة التعقيدات ايضا لمقارنة برنامجين ينجزان نفس المهمة.

مثال/ افترض ان البرنامج P له تعقيدات وقت ?(n) والبرنامج Q له تعقيدات وقت ?(n2), اي البرنامجين افضل؟

الجواب:-
زمن تنفيذ البرنامج P حده الاعلى cn لقيمة معينة c ولجميع قيم n?n1 .
زمن تنفيذ البرنامج Q حده الادنى dn2 لقيمة معينة d ولجميع قيم n?n2 .
وحيث ان cn ?dn2عندما n ? c/d ، فان البرنامج P يكون اسرع من Q عندما n ? max(c/d, n1, n2) .

وعلى سبيل المثال اذا كان البرنامج P ينفذ فعليا في (106n)ms بينما البرنامج Q ينفذ في (n2)ms وعندما تكون قيمة n ? 106 فان البرنامج Q هو الذي سيتم اختياره.

قياس الانجازية (Performance measurement)

الهدف هو الحصول على المتطلبات الحقيقية خزنا ووقتا للبرنامج( هذه تعتمد على الحاسب وعلى المؤلف والخيارات المستخدمة). سنركز فقط على وقت تشغيل البرنامج، وللحصول على هذا الوقت نحتاج الى اجراء تجربة حيث يتم التخطيط لها باعتبار الجوانب التالية:-

1) ما هي دقة الساعة وماهي دقة النتائج المرغوبة. بمعلومية دقة النتائج المرغوبة يمكن تحديد طول اقصر حدث يقاس
وقته. فمثلا اذا كانت دقة الساعة 0.01 من الثانية فيمكن قياس دقة حدث لا يقل عن ثانية واحدة للحصول على
دقة0.01 .
2) يتم تكرار وقت الحدث ليصبح مساويا على الاقل لاقل وقت يمكن قياسه بالدقة المرغوبة.
مبدأ/ لقياس وقت حدث قصير يكون ضروريا تكراره عددا من المرات ثم قسمة الوقت الكلي على عدد مرات
تكراره.
3) هل سنقيس انجازية اسوأ حالة ام الحالة المتوسطة. بيانات الاختبار تولد تبعا للحالة ولا توجد استراتيجية ثابتة حيث
تعتمد على الخوارزمية, غالبا نوجد تقريبا اعتمادا على اعداد عشوائية.
4) ما غرض التجربة هل هي لمقارنة خوارزميات ام التنبؤ بوقت الخوارزمية. لعملية التنبؤ نحتاج الى طرح وقت
توليد البيانات ودوارة التكرار الخاصة باطالة فترة الحدث(تكرار التجربة). اما لحالة المقارنة فلا نحتاج الى طرح
اي شيء طالما كانت ثابتة في جميع الحالات.
5) في حالة التنبؤ نحتاج الى معرفة التعقيدات التقاربية للبرنامج فاذا كانت خطية نفصل خطا مستقيما ذي اقل مربعات
انحراف.


واذا كانت تربيعية نفصل قطع مكافىء


واذا كانت التعقيدات ?(n log n) نفصل منحني ذات صيغة



جزء البرنامج التالي يمثل الخطوات الاساسية لقياس الوقت في لغة JAVA:
long startTime=System.currentTimeMillis( );
// gives time in milliseconds since 1/1/1970 GMT.
long counter;
Do{
Counter++;
doSomething ( ); // code to be timed comes here.
} while (System.currentTimeMillis( ) - startTime < Shortest_Event_Length)
long elapsedTime=System.currentTimeMillis( ) - startTime;
float timeForMethod=((float)elapsedTime)/counter;

ملاحظة/ هذا يعطينا وقت الحدث doSomething( ) مضافا له وقت دوارة التكرارات وللتخلص من وقتها علينا ان
نعيد نفس التجربة مع حذف العبارة doSomething( )ونسجل الزمن التي تاخذه كل دورة ثم نطرحه من
قيم الزمن في التجربة السابقة.