تحليل الخوارزميات Analysis of Algorithms مع مجموعة من الامثلة

سنناقش فى هذه الدورة تحليل الخوارزميات وكيفية عمل بعض الخوارزميات الشهيرة لكن دعونا نتعرف اولًا على معنى الخوارزمية فى سياق البرمجة وسنستخدم امثلة فى الاغلب من لغة برمجة Python.

ماهى الخوارزميات Algorithms

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

يمكن التفكير فيها كوصفة الطعام حيث المكونات وطريقة تحضير اكلة معينة.

لماذا الحاجة إلى تحليل الخوارزميات

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

كيفية تحليل الخوارزميات

لنفترض اننا لدينا خواررزمياتان ونريد معرفة الافضل منهم.

قد تقول حسنًا لتحليل الخوارزمية قد نقوم بتنفيذ البرنامجين على جهازين مختلفين ونرى ايهم اسرع – يستغرق وقت اقل – .

المشكلة هنا ان مدخلات معينة تجعل الخوارزمية الاولى تعمل افضل , بينما عند مدخلات اخرى فالخوارزمية الثانية تعمل افضل.

وايضًا قد تعمل الخوارزمية الاولى على جهاز بشكل افضل والثانية بشكل افضل على جهاز مختلف.

مثال بالكود لاستخدام هذه الطريقة


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

يمكننا استخدام مكتبة time فى لغة python لحساب الزمن اللازم لتنفيذ البرنامج الاول كتالى

ويكون الخرج للكود السابق كالتالى :

Sum is 50005000 required 0.0018950 seconds

تحليل الخوارزميات عن طريق Big-O

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

كمثال توضيحى


البرنامج فى المثال السابق يقوم بجمع الاعداد من 0 إلى 100.

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

  1. جملة 100 = n
  2. جملة 0 = sum
  3. حلقة التكرار for سنقوم بتنفيذ 100 مرة

بالتالى مجموع هذه الخطوات هى 102 خطوة.

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

لانه فى الحقيقة كلما زادت قيمة n تقل قيمة 2 بالنسبة لها.

فتخيل ان عدد n = 10000 بالتالى عدد الخطوات الكلى = عدد خطوات for وهى 10000 + 2  = 10002.

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

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

مثال

اذا كانت قيمة الوقت اللازمة لتنفيذ خوارزمية معينة هو كالتالى :

فان هذه الخوارزمية تعتبر

مع تجاهل الحدود الاخرى.

مثال


عدد العمليات فى المثال السابق يمكن حسابه كالتالى :

عدد ثابت = 3 فى البداية وبعد ذلك for-loop بداخلها for-loop اخرى داخلها ثلاثة خطوات اخرى اي 

بعد ذلك for-loop داخلها خطوتان اي 

وبعد ذلك عملية واحدة فى اخر البرنامج.

بالتالى يمكن التعبير عن الزمن كليًا باستخدام الصيغة التالية.

وباستخدام صيغة Big-O

فى النهاية إليك بعض الصيغ الشهيرة التى تعبر عن اداء الخوارزميات 

الدالة الاسم
1 ثابت constant
Log n لوغريتمية Logarithmic
n خطية Linear
n log n لوغرتمية خطية Log Linear
n2 تربيعية Quadratic
n3 تكعبية Cubic
2n اُسية Exponential

وسلوك هذه الدوال فى القيمة الصغيرة ل n يكون متقارب لهم جميعًا ومن الصعب التمييز بينهم , بينما فى القيم الكبيرة تظهر الفروق واضحة كالتالى :

تحليل الخوارزميات
 تحليل الخوارزميات

مرجع مفيد فى هذا الصدد

http://interactivepython.org/runestone/static/pythonds/index.html