Time Complexity - تعريفه واهميته وكيفية حسابة

محروم.كوم · #1 09-27-2010, 09:01 PM

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

مقدمه :

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

كما ان تطور الاجهزة الماديه hardware يزداد صعوبه .. فكما تعلمون ان الشركات المصنعه للمعالجات توقفت عن التطور الطولي وبدات في التطور العرضي .. والمقصود به زيادة عدد ال Cores في المعالج و تقليل سرعة كل منها ( Mhz ) وهذا لان زييادة السرعه يحول هذه الموجات الي موجات Microwave ضاره بخلايا العقل البشري.

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

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

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

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

تعريف :

المقصود بحساب ال Time Complexity هو عملية يقوم بها المبرمج لمعرفة ما اذا كان برنامجه سيعمل بكفائه تحت اسوأ الظروف الممكنه.
واسوا الظروف الممكنه المقصود بها هو اكبر مدخلات يمكن ان يقوم بها المستخدم او من يطلب البرنامج

فمثلا لو كان المستخدم يطلب برنامج ادارة بقاله يختلف عن من يطلب برنامج ليعمل في سوبر ماركت .. هكذا

فيجب دائما مراعاة اختلاف المتطلبات حتى لا تقوم بمجهود لن تحتاجه .

في البدايه قم بالاطلاع على هذا الجدول ليكون عندك خلفية عامه عن انواع ال Complexity وسوف اشرح اهمها في السطور القادمه باذن الله

فوائده :

1 - يتيح لك معرفة ما اذا كان برنامج سيعمل بكفائه ام لا
2 - يتيح لغيرك ايضا الحكم على كفائه برنامجك
3 - يساعدك على تطوير برنامج الحالي الى ماهو اكثر كفائه
4 - يمثل مقياس ايضا لمدى كفائه البرنامج عند ربط اكثر من Algorithm ليعملو سويا
5 - يساعدك على تحديد ما اذا كنت تحتاج الى توفير الوقت ام الذاكرة ام الاثنين معا (ان كان ضروريا)

طريقة الحساب :

يعتمد حساب ال Time Complexity على حساب عدد التدورات التكراريه Loops التي يقوم بها برنامجك .. ويوجد عدة انواع من البرامج مقسمه كما يلي :

Constant time

ان كان برنامجك لا يحتوي على اي جمل تكراريه فحينها برنامجك يعمل في Constant Time ويعني ان برنامج لا يتاثر سرعته بمدخلات المستخدم.. وهو اسرع انوع البرامج وافضلها .. ولكن من المستحيل الاعتماد عليه كليا

مثلا مثل البرنامج التالي:

كود:
int x,y,z;
x = 100;
y = 200;
z = x + z;
.....
في هذه الحاله كما نرى لا يوجد اي جمل تكراريه .. حينها يطلق على هذه العمليه Constant Operation
ويرمز لها بالرمز
كود:
O(1)
ويفضل استخدام هذا النوع ان امكن ذلك لانه لا يتاثر مع حجم المدخلات يعني لو لاحظتم لو جعلنا ال x = 1000000 وال y = 100000 .. لن تستغرق العمليه وقتا اكثر مما هي عليه.

Linear time

وهو ايضا من البرامج الممتازه جدا ولكنه يتاثر سرعته مع المدخلات الكبيره جدا

مثلا لو نظرنا لهذا المثال :

كود:
for (int i = 0; i < n;i++){}
هذه جمله تكراريه تدور بمقدار n دورات

وحينها يرمز لها بالرمز

كود:
O(N)
اي ان هذا الكود يقوم بدورات تكراريه قدرها N

و N هنا هي المدخلات التي يدخلها المستخدم على سبيل المثال

Logarithmic time

واشهر تطبيق لهذا النوع هو ال Binary Search
وسوف اشرح ال Binary Search لكي تصل الصورة اليكم

يعمل البحث الثنائي فقط ان كانت المصفوفه مرتبه يعني مثلا لو المصفوفة تحتوي الارقام التاليه :

1,2,4,5,6,9,10

اذا اردنا البحث مثلا عن الرقم 2 سيقوم البحث بالخطوات التاليه :

1 - سيقوم بمقارنة الرقم 2 بالرقم الموجود في منتصف المصفوفه
2 - اذا كان هذا الرقم اكبر من 2 فهذا يعني قطعا ان الرقم 2 موجود في النصف الاول من المصفوفه
.. وان كانت الرقم اصغر من 2 فهذا يعني قطعا ايضا ان الرقم موجود في النصف الثاني من المصفوفه
(تذكر بان المصفوفه مرتبه)
3 - في اي حاله من الحالتين يتم اهمال النصف الاخر ثم القيام بنفس العمليه السابقه مع النصف المستخدم (في هذه الحاله سيتم استخدام النصف الاول لان الرقم 2 اقل من الرقم 5)
4 - يتم تكرار العمليه السابقه بعد اهمال النصف الثاني تماما كانه ليس موجود في المصفوفه وهكذا

كما نرى هنا هذا النوع من البحث افضل كثيرا من البحث الخطي اي المرور على جميع العناصر ومقارنتها

يعني مثلا لو عندنا عدد العنصار = 10 سيقوم البرنامج بعمل 10 دورات تكراريه قدرها 10 في اسوا الاحوال لمعرفة اذا كان العنصر موجودا ام لا
ولكن مع البحث الثنائي سيقوم ب 3 دورات فقط
لانه سيتم قسمة العناصر كما يلي

10 > 5
5 > 2
2 > 1

في هذه الحاله يرمز لوقت التشغيل بالرمز :

كود:
O(LogN)
فمثلا لو كانت عناصر المصفوفه 1000
سيقوم البرنامج ب 10 دورات تكراريه بحد اقصى لان :

كود:
2 ^ 10 = 1024
لو كان عدد عناصر المصفوفه 1000000
سيقوم البرنامج ب 20 دوره تكراريه بحد اقصى لان :
كود:
2 ^ 20 = 1048576
ويمكنك من المثالين السابقين معرفة كيف يتم حساب ال Log

وبرامج ال Log سريعة جدا لانها تتاثر ببطئ شديد حتى مع الارتفاع الكبير في مدخلات المستخدم ولكن يصعب عملها لوحدها لان معظم البرامج لا تعتمد كليا على مجرد البحث

Polynomial time

نبدا في هذا النوع ببعض البرامج التي تتطلب حذرا ومعرفة جيده بمدخلات المستخدم لانها قد تتطلب وقتا كبيرا في حالة المدخلات الكبيره

يمكن تعريف هذا النوع ببساطه عن طريق ال Nested loops او الدورات المتفرعه
وهي عباره عن اي جملتين تكرارين او اكثر احدها متفرع من الاخرى

مثال :

كود:
for(int i = 0; i < n;i++)
for(int j = 0; i < n;j++)
لو نظرنا في هذا الكود سنجده يقوم بدورات قدرها N ^ 2 او N * N
ويتم التعبير عنها بالشكل :

كود:
O(N^2)
مثال 2

كود:
for(int i = 0; i < n;i++)
for(int j = 0; j < m;j++)
في هذا الكود كل جملة تكراريه تعتمد على متغير مختلف حينها يكون عدد الدورات N * M

ويعبر عنها بالشكل

كود:
O( N * M)

مثال 3:

كود:
for(int i = 0; i < n;i++)
for(int j = 0; j < n;j++)
for(int k = 0; k < m;j++)
في هذه الحاله سنجد ان هذه الحاله ستقوم بعدد دورات تكراريه قدرها N * N * M او N ^ 2 * M

ويمكن التعبير عنها بالشكل :

كود:
O((N^2) * M)
مثال 4:

ويمكن ايضا ان تعتمد دورة تكراريه على دورة تكراريه اخرى على سبيل المثال :

for(int i = 0; i < n;i++)

for(int j = i;j < n;j++)

في هذه الحاله كما ترون في الكود تعتمد الاولى على الثانيه .. فهي ليست ثابته بقيمه معينه
.. في مثل هذه الحالات نقوم بحساب متوسط الدوره الثانيه وهو N + 1/2 او N/2 على سبيل التقريب

ويكون سرعة الكود هي :

كود:
O(N * N/2)

مثال 5 :

ويمكن في بعض الحالات ان تحتوي الدورة التكراريه على اكثر من دورة تكراريه بداخلها ولكن منفصلتين كالتالي :

كود:
for(int i = 0; i < n;i++)
{
for(int j = 0;j < m;j++){}
for(int k = 0;k < z;k++){}
}
في هذه الحاله يتم جمع الدوارت الداخليه جميعها ثم ضربعا بالدوره الاساسيه المحتويه عليهم
فتكون السرعه كالتالي :

كود:
O(N * (M + Z)

مثال 6 :

وفي حالة اخرى يمكن ان تحتوي الدورة نفسها على بحث يتم في كل مره بداخلها

فتكون كالتالي :

كود:
for(int i = 0; i < n;i++)
Binary_Search();
حينها تكون السرعه :

كود:
O(N*LogN)
ومثال للحاله الاخيره ال Quick Sort حيث يتم المرور على جميع العناصر المراد ترتيبها ثم البحث عن المكان المناسب لكل عنصر عن طريق البحث الثنائي ووضعها في مكانها .. وهكذا

ويجب الحذر جدا من هذا النوع بشكل عام لانه يمثل استهلاكا كبيرا لامكانيات الحاسب ولكن احيانا لابد من استخدامه.

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

مقاييس :

معالج Intel Core 2 Due 2.4 GHz يقوم تقريبا بالاتي:

1000000 دورة تكراريه خلال 0.05 ثانيه
20000000 دورة تكراريه خلال 1 ثانيه
100000000 دورة تكراريه خلال 5 ثواني
1000000000 دورة تكراريه خلال 20 ثانيه
1000000000000 دورة تكراريه خلال 120 ثانيه

وفي النهاية

يجب الحذر مرارا وتكرارا والاهتمام بسرعة المعالجة بشتى الطريق .. والاهتمام الشديد بحساب ال Time Complexity قبل وبعد كتابة البرنامج حتتى تتاكد ان برنامجك سيعمل بالشكل المطلوب في ظل الظروف والاختبارات التي سيتعرض لها عن طريق المستخدم ...
ولمزيد من المعلومات قم بزيارة الرابط التالي :http://en.wikipedia.org/wiki/Time_complexity

وفي حالة وجود اي استفسارات برجاء اعلامي في الموضوع .. وشكرا

والسلام عليكم ورحمة الله وبركاته
__DEFINE_LIKE_SHARE__