تراكيب البيانات: قياس فعالية الشيفرة

السلام عليكم

كل التحية للصامدين المثابرين المرابطين على زيارة مدونتي الغلبانة
بصراحة أن تتحملوا كل هذا الكم من الرخامة
(الرخامة كلمة فصيحة يقال رخم الصوت أي ثقيله ويوصف بالرخامة أي ثقل الظل يعني أنا)
لكن بما أنك تتحملني فلماذا لا أزيد رخامتي
أكتب هذا الموضوع بناءاً على طلب أحد الأخوة
صراحة تراكيب البيانات تعتمد بشكل أساسي عليه
لكني كنت أأخره قليلاً لكي لا أصعب الموضوع على المبتدئين
لكن بما أنا قد قطعنا شوطاً كبيراً في SinglyLinkedList
فقد حان موعده
بالطبع يتعين على الولد عبده أن يحضر لي كوباً من الشاي
لكن عبده اليوم متغيب
لذلك سأقوم أنا بذلك
اهدئ يا عبده إنما قصدت عبده البواب
(للقادمين الجدد أقول تحاشوا الشجار مع الأخ عبده فأنتم لن تحبوا النتيجة مطلقاً)
أطلت عليكم في المقدمة نبدأ درسنا الآن

في بدايات علم البرمجة حار العلماء في سلوك بعض الدوال
فتجد أن دالتين تقومان بنفس الوظيفة إحداهما تقوم بالأمر في دقائق معدودة والأخرى تستغرق ساعة كاملة
بل والأسوأ أن الدالة نفسها يختلف سلوكها على حسب عدد مدخلاتها
ومن هنا ظهرت الحاجة إلى إيجاد مقياس ثابت لتعقيد الخوارزميات
هنا ظهر الأخ Big O notation ليعذب الكثير من البشر
(منهم العبد لله)
عندما أقول التالي
د(س)=O(ل(س))
فأنا أعني أن الدالة ع*ل(س)
عند أي عدد س حيث س >ك ستكون دائماً أكبر من د(س)
ك ,س أعداد صحيحة
بمعنى آخر أن د(س) محدودة بـ ع*ل(س)
لا تزيد عنها عند أي س >ك
بالطبع ستجد الكثير من الدوال التي تعمل نفس العمل لكننا دائماً نبحث عن الأقرب
فمثلاً
س^2 + س =O(س^2)=O(س^3)=O(س^س)
لكننا نبحث عن أقل واحد فيهم O(س^2)
كل هذا الكلام لن يهمنا كثيراً
نحن نهتم أكثر بكيفية حساب التعقيد للشيفرة
الموضوع ببساطة يتركز في التكرار loop
سواءاً كان for while dowhile
لكي يتضح المفهوم بشكل أكبر
نأخذ مجموعة من الأمثلة
دالة الإضافة في البداية من فئة الحلقات المتسلسلة أحادية الاتجاه

public void addFirst(Object element){
 SNode newNode; 
 if(head==null){//set tail at first 

 	newNode=new SNode(element,null); 

 	head=tail=newNode; 

 } 

 else{ 

 	newNode=new SNode(element,head); 

 	head=newNode; 

 } 

}

خذ عندك القاعدة الأولى في حساب التعقيد
عندما لا تجد أي تكرار loop فالتعقيد يساوي (O(1
وذلك لسبب بسيط أن كل العمليات الموجودة في الدالة
تطبق مرة واحدة عند استدعاء الدالة
نأخذ مثالاً ثان
دالة الحذف من النهاية في فئة الحلقات المتسلسلة أحادية الاتجاه

public Object deleteLast(){
 SNode temp=head; 
 if(tail==head){ 

 	if(head==null) 

 		return null; 

 	head=tail=null; 

 	return temp.getElement(); 

 } 

 while(temp.getNext()!=tail)//1 

 	temp=temp.getNext();//2 

 Object objtemp=tail.getElement(); 

 tail=temp; 

 tail.setNext(null);//to help garbage collector 

 return objtemp; 

}

لاحظ معي الجملتين 1 و 2
هناك تكرار في الموضوع
كم عدد المرات التي ستنفذ فيها الجملتين؟
عدد الحلقات في السلسلة
إذن تعقيد الدالة يساوي (O(n حيث n هو عدد الحلقات في السلسلة
نأخذ مثالاً آخر

public void deleteAll(){
 while(head!=null)//1 
 	deleteLast(); 

}

جيد جداً لا صعوبة في الموضوع نفس المثال السابق
بالتأكيد هذا الكلام غير صحيح
يجب أن نركز قليلاً في مسائل النداء
بمعنى أني لا أستطيع أن أحكم على الدالة deleteAll
حتى أقوم بحساب تعقيد الدالة deleteLast
وقد قمنا بهذا قبل قليل وحصلنا على النتيجة (O(n
خذ عندك القاعدة الثانية في حساب التعقيد
في حالة تكرار التكرار نضرب تعقيد الداخل في تعقيد الخارج
في مثالنا السابق تعقيد الدالة deleteLast
يساوي (O(n و التكرار في الجملة رقم 1 يحصل n من المرات
إذن التعقيد الكلي للدالة deleteAll يساوي (O(n*n

لقد قمنا بعمل جيد حتى الآن
تعالوا نراجع ما تعلمناه اليوم
قواعد حساب التعقيد
1- عندما لا تجد أي تكرار loop فالتعقيد يساوي (O(1
2- في حالة تكرار التكرار نضرب تعقيد الداخل في تعقيد الخارج
3- ابدأ بحساب التعقيد للدوال المستدعاة داخل الدالة
ثم قم بحساب التعقيد للدالة الأصلية

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

Tags: , , , , , ,

10 Responses to “تراكيب البيانات: قياس فعالية الشيفرة”

  1. LuLu قال:

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

    المهم ..سؤالي…
    على حسب علمي ان استخدام ال Loops مفيد جدا
    حتى يسهل علينا اختصار الكثير من الاشياء

    ومافهمته انه عندما لايوجد loops فإن
    التعقيد يساوي (O(1

    هل هذا يعني انه كلما زاد التعقيد كانت الشيفرة افضل
    ام انني لم افهم شيئا ؟ :(

    صل اللهم على سيدنا محمد :)

  2. admin قال:

    أفضل دالة هي ذات التعقيد الأقل
    بالطبع التكرار مفيد جداً في البرمجة

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

    تحياتي

  3. LuLu قال:

    اها..فهمت
    بارك الله فيك
    صل على النبي

  4. admin قال:

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

    تحياتي

  5. حسن قال:

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

  6. admin قال:

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

    تحياتي

  7. أولا ,,,, أود أن أشكرك يا علاء على مدونتك و مقالاتك الرائعه…..
    ثانيا… عندي سؤال..
    إنت حدثتنا عن ال 1 و n و n^2 …. ماذا عن ال log n ….. متي نقول أن الدالة معقده من الدرجة log n ؟

  8. admin قال:

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

    دعني أحاول أن أسهل الموضوع
    حتى نقول أن تكرار ما تعقيده log n بدلاً من n فيجب أن يكون اللفة الواحدة في التكرار تقلص احتمالاتك إلى النصف
    مثال ذلك (وهو المثال الأشهر)
    خوارزمية البحث الثنائي
    خوارزمية البحث الثنائي تعتمد على تقسيم المجموعة المراد البحث فيها إلى مجموعتين
    وفحص العنصر المتوسط لهاتين المجموعتين
    إذا كان العنصر المتوسط أكبر من العنصر المراد البحث عنه نستثني مجموعة العناصر الأكبر من العنصر المتوسط والعكس بالعكس
    لاحظ أنك في كل مرة ستقوم باستثناء نصف العناصر والعمل على النصف الآخر
    لو كان عدد العناصر المراد البحث فيها يساوي 16
    ستصبح مع اللفة الأولى 8
    ومع اللفة الثانية 4
    ومع اللفة الثالثة 2
    ومع اللفة الرابعة 1
    16=2^4
    إذن log 16 للأساس 2=4

    تحياتي

  9. شكرا لك… ولكني أراها لا تكفي ….. ممنون جدا لك أخي علاء

  10. admin قال:

    وضح أكثر يا محمد
    لماذا لا تراها غير كافية؟ وما هي بالضبط؟

Leave a Reply