ببساطة ،، تحليل الخوارزميات

Posted: December 15, 2010 in Uncategorized

 

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

الكلام عن تحليل الخوارزميات – من وجهة نظري – أفضل طريقة له هي السؤال و الجواب يعني مثلا

يعني اية تحليل الخوارزم المعين ؟

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

المعيار الاساسي اللي بيفرق بين خوارزم و التاني هو سرعة الاداء بتاعهم فالخوارزم اللي بيأدي أسرع ممكن نضحي بجزء من سرعته لزيادة دقة الحل مثلا ( لو انا مثلا بادور على خوارزم في مجال التحليل العددي Numerical analysis هايهمني قوي إني أوصل لدقة أكبر )

هنا ممكن يكون الخوارزم اللي اخترته أسرع بس دقته أقل فاضطر اعدل الخوارزم بحيث يطلع دقة أكبر بس في المقابل هاضحي بجزء من سرعته ،، معنى كدا ان الخوارزم السريع بيمكنني من اني اضيف فيه أي مميزات و أدفع في المقابل من سرعته لذلك بيعرفوا السرعة على انها عملة الكمبيوتر ،، ممكن أضحي بالسرعة في مقابل مميزات تانية كمان ،، انما لو الخوارزم اصلا بطيء يبقى انا مش معايا العملة اللي هادفعها في مقابل المميزات اللي عاوزها في الخوارزم بتاعي

العامل الاساسي اللي بتتوقف عليه السرعة في الغالب هو كمية المدخلات اللي داخلة للخوارزم ،، بمعنى ان لو الدفعة اللي انا عاوز ارتبها مثلا كان عددها 100 طالب غير لما يكون عددها 8000 اكيد الوقت المطلوب عشان ارتب 8000 طالب هايكون أكبر ،، و السبب في كدا ان الوقت المطلوب لتنفيذ الخوارزم هو دالة في المدخلات و دة معناه ان

لو عندي خوارزم الوقت بتاعه  = ( المدخلات ) ^2 يبقى مطلوب 10000 وحدة زمن عشان يرتب الـ100 طالب حسب درجاتهم بينما لو الوقت بتاعه = ( المدخلات)^3 هانحتاج 1000000 وحدة زمن !!

بنستنتج من كل دة ان تحليل الخوارزم هو ايجاد الدالة اللي بتمثل العلاقة بين مدخلاته و الزمن اللي هايستغرقه

 

هل نوع المدخلات بيأثر في الزمن المطلوب ؟

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

Best case

Average case

Worst case

لذلك لما احلل خوارزم هاحلله على التلات حالات دول يعني هابقى محتاج أعرف لو الخوارزم دة جات له أفضل الحالات هاياخد وقت قد اية ،، طب لو جات له حالة متوسطة ( يعني المصفوفة نص مترتبة ) هاياخد وقت قد اية ،، طيب ماذا لو جت أسوأ حالة خالص إن المصفوفة تكون مترتبة بالعكس تماما بقا !!  طبيعي احنا لازم نتوقع الأسوأ عشان كدا أهم حالة عندنا هي الورست كايس ،، أهم ما في تحليل الخوارزم هو اجابة سؤال : الخوارزم دة هاياخد وقت قد اية لو كانت المدخلات معكوسة ؟

Asymptotic analysis

الدالة اللي بتمثل العلاقة بين عدد مدخلات خوارزم و الوقت اللي بيستغرقه مش لازم تكون حد واحد ممكن تكون دالة تربيعية

f(x) = ax^2 + bx +c

أو دالة تكعيبة او دالة خطية او غير كدا ، بس لما بنعمل تحليل لخوارزم بنهمل كل الحدود غير المؤثرة بشكل كبير يعني لو عندنا دالة لخوارزم معين هي f(x) = 3x^3 + 2x+17

لاحظ كدا الجدول دة

x 3x^3 2x 17
10 3000 20 17
100 3000000 200 17
1000 3000000000 2000 17
10000 3000000000000 20000 17

لاحظ بقا الحد الاولاني ( الاكس تكعيب ) و الفرق الرهيب بينه و بين الحد التاني و التالت خصوصا لو المدخلات ( الاكس ) زادت قوي ،، تخيل لو احنا عاوزين نرتب بقا دفعة تجارة ! او عاوزين نرتب سكان جمهورية مصر العربية حسب السن !!! في الحالة دي هانلاقي ان الحد التاني و التالتة لا يقارنوا بالحد الاولاني و الفرق بينهم رهيب ،، لو قسمتهم على بعض هابقى بتقسم مالا نهاية على رقم !

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

f(x) = x^2 + 4x^6 +678

باقول ان الخوارزم دة O(x^6)

و بتتنطق كدا ،، بيج او اوف اكس^6 و دة بينقلنا لجزئية تانية مهمة

Asymptotic notations

دالة البيج او دي بتوضح لينا الحد الاقصى من الوقت اللي عمر الخوارزم  ما هايعديه ،، يعني نقدر نقول ان

C*x^6 >= T(x) ,, where T(x) is the time of an algorithm which is Big-O of x^6

هل في دوال تانية بتوضح لي حدود الزمن اللي بياخده الخوارزم ؟

أيوة في دالة الثيتا و دالة البيح أوميجا بحيث ان لو كان الخوارزم من نوع θ(x^6)

دة معناه إن

C1*x^6<= T(x) <=C2*x^6

و لو كان الخوارزم من نوع Ω(x^6)

دة معناه إن

C*x^6 <= T(x)

 

نستنتج من كدا إن :-

Big-O Indicates the UPPER BOUND of the time an algorithm takes .

Big-Ω indicates the LOWER BOUND an algorithm takes .

θ indicates the area in which an algorithm falls .

طب اية هي الثوابت دي ؟

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

طيب اذا كانت عندي معادلة خورازم هي

f(x) = x+2

اية هي البج او بتاعته ؟ طبعا بيج او اوف اكس طيب هل تنفع انها تكون بيج او اوف اكس أس عشرة ؟ نظريا ينفع طبعا ما هو لو ضربت ثابت في اكس أس عشرة اكيد هايطلع أكبر من الوقت المطلوب في المعادلة دي لذلك اتطرحت فكرة تانية و هي ان الدوال اللي بتوضح لي الحدود نوعين :-

دوال Tight و دوال مش Tight!!

الدوال التايت دي يعني مش بعيدة بكتير عن الحل الصح زي ان البج أو للمعادلة الاخيرة دي بإكس إنما الحل اللي مش تاتيت معناه ان انا باوضع حد للزمن اه ،، انما الحد دة بعيد قوي عن الصح ،، زي مثلا لو انت رايح تشتري كتاب الام اي تي بتاع الخوارزميات : لو انت عارف ان الكتاب تمنه من خمسين لسبعين جنية و انت أخدت معاك سبعين جنية كدا تبقى انت واخد معاك البيج أو لسعر الكتاب دة و تبقى تاتيت أما لو أخدت معاك 10000 جنية هاتبقى واخد ليتل أو ( الحد الأقصى برضة بس ببيبقى بعيد ) اذن في مجموع دوال تانية للحدود و ماهياش تايت زي

Little-o

Little-ω

و هي بالظبط بتقوم بنفس وظيفة البج أو و البيج أوميجا بس مش تايت

إية بقا المشاكل اللي ممكن تقابلني لما احب احلل خوارزم؟

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

f(x) = 17x^3+55x^(1/2) +3000 is :-

O(x^3) & Ω(x^3) & θ(x^3)

يبقى انا لو وصلت للمعادلة هقدر أجيب الحدود بسهولة ،، المشكلة اللي ممكن تقابلني بقا لما احب احلل خوارزم هي اني ما اقدرش أوصل للمعادلة بتاعته ! طب ازاي ؟ ممكن مثلا تكون المعادلة بتاعته دي بتحتوي على دوال تانية انا ما اعرفهاش ( دوال معادلات تانية ) في الحالة دي هاضطر أعرفها الأول و ممكن تكون الدالة دي recursive

و دي بتمثل مشكلة كبيرة زي مثلا

f(x) = 2 where x = 1 & f(x) = 3x^2 + f(x/2) where x>1

هنا لازم احل المعادلة اللي الريكرسف دي الأول بمعنى إني استبدل استخدامها لنفسها بحدود عادية مثلا حاجة + حاجة عشان أعرف اجيب أكبر أس و بالتالي أجيب دوال الحدود التلاتة أو الخمسة لو محتاجهم

حاجات عاوز أوضحها

الشرح دة مبني بالأساس على

  • MIT : introduction to algorithms ( chapter 2,3 ) .
  • First lecture of MIT algorithms course ( available here) .
  • Lecture about asymptotic notations from IIT : design and analysis of algorithms course ( available here ) .

اي تعليقات ، تصحيحات او أسئلة تبقى مشكورة جدا و ان شاء الله المقال يكون مفيد

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s