الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

الخوارزمية من درجة n log n ؟

بدأه الاخير زمانه في 13 فبراير 2012 · 11 رد · 1,694 مشاهدة · في الرياضيات والخوارزميات
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم

في كتاب Algorithms i a Nutshell

في الجزء الخاص بشرح n log n

لم افهم هذا الجزء

If we expand this out once more, we see that:
t(n)=2*[2*[2*t(n/8)+O(n/4)]+O(n/2)]+O(n)
This last equation reduces to t(n)=8*t(n/8)+O(3*n). In general, then, we can say
that t(n)=2k*t(n/2k)+O(k*n). This expansion ends when 2k=n, that is, when
k=log(n). In the final base case when the problem size is 1, the performance t(1) is
a constant c. Thus we can see that the closed-form formula for
t(n)=n*c+O(n*log(n)). Since n*log(n) is asymptotically greater than c*n for any
fixed constant c, t(n) can be simply written as O(n log n).

تحديدا اخر 4 اسطر - كيف وصل لى هذه المعادلة

t(n)=n*c+O(n*log(n))

ولماذا فرض هذا

Since n*log(n) is asymptotically greater than c*n for any
fixed constant c, t(n) can be simply written as O(n log n).

لدي مشاكل مع الرياضيات!!

ياريت اذا هناك شخص لديه معلومات - مع الشكر

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#2

أخي الخوارزميات من نمط فرق تسد "divide and conquer" لها تعقيد من رتبة الـ n log n ، لا أعلم إن كنت قرأت السطور السابقة في الكتاب و لكن دونها لا يمكن فهم ما تسأل عنه حضرتك أبداً حتى بعد تكرار القراءة n مرة :)

أولاً : يتم تقسيم المسألة المعطاة إلى مسألتين أصغر منها و يبنى الحل من دمج حل هاتين المسألتين أي أن لها العقيد :

t(n)=2*t(n/2)+O(n)

و لنسمها المعادلة رقم 1

الآن ماهو تعقيد :

t(n/2)

و كيف نوجده ؟؟؟؟

يحسب من المعادلة الأولى بتعويض n/2 مكان n :

t(n/2)=2*t(n/4)+O(n/2)

إذا عوضنا في المعادلة رقم 1 نجد التالي :

t(n)=2*[2*t(n/4)+O(n/2)]+O(n)

و عند التعويض تراجعياً مرة أخرى بنفس الطريقة نجد :

t(n)=2*[2*[2*t(n/8)+O(n/4)]+O(n/2)]+O(n)

بإصلاح المعادلة السابقة نجد : 

t(n)=8*t(n/8)+O(3*n)

نلاحظ في المعادلة الأخيرة أن هناك رقم 8 و رقم 3 و نعلم أن :

2 ^ 3 = 8

و لنفرض أن k = 3 فيمكن كتابة المعادلة السابقة بالشكل :

t(n)=(2^k)t(n/(2^k))+O(k*n)

- و هنا خطأك الفادح في الاقتباس فأنت كتبتها بشكل يوهم أن الـ 2 و الـk مضروبين ببعضهما -

المهم دعنا نكمل :)

إذا استمرينا في التعويض التراجعي سنصل إلى المرحلة الأساسية و فيها :

2 ^ k = n

أي أنّ 

k = log(n)

و إذا عوضنا في الحد الأول من الطرف الأيمن من المعادلة يصبح :

n * t(1)

و بما أن زمن تنفيذ خوارزمية تعقيدها من رتبة 1 هو ثابت ينتج :

n t(1) = n * c //حيث c هو ثابت

نكتب المعادلة بعد التعويض :

t(n)=n*c+O(n*log(n))

يمكن إهمال nc أمام الحد الثاني لأنه أصغر بكثير، ينتج :

t(n) = O(n log n).

تم تعديل هذه المشاركة بواسطة Mohammad Walid في 13 فبراير 2012 في 03:08

2
#3

اولا اشكرك اخي محمد على وقتك و محاولة جوابك بالتفصيل - جزاك الله خيرا.

انا قرأت في الكتاب - لكني فعلا اواجه مشكلة في فهم الكثير من الامور.

في ردك - الامور الاولى واضحة لكن الخطوات الاخيرة لم افهمها.

Mohammad Walid كتب:

إذا استمرينا في التعويض التراجعي سنصل إلى المرحلة الأساسية و فيها :

2 ^ k = n

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

أي أنّ 

k = log(n)

ممكن توضح الخطوات التالية الله يبارك فيك بالتفصيل؟

و إذا عوضنا في الحد الأول من الطرف الأيمن من المعادلة يصبح :

n * t(1)

و بما أن زمن تنفيذ خوارزمية تعقيدها من رتبة 1 هو ثابت ينتج :

n t(1) = n * c //حيث c هو ثابت

نكتب المعادلة بعد التعويض :

t(n)=n*c+O(n*log(n))

يمكن إهمال nc أمام الحد الثاني لأنه أصغر بكثير، ينتج :

t(n) = O(n log n).

و اعتذر عن جهلي في الموضوع - لكني قرأت في اكثر من كتاب - لكن لان خلفيتي الرياضية ضعيفة لم افهم

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#5

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

واذا في شي ما واضح راح ارجع لك

بارك الله فيك

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#6

اخي محمد

بعد قراءة المرفق

لدي فقط سؤال

في اول خطوة عندما عوضت بقيمة ال n تساوي 4

افترضت ان ال k =1 حتى تحصل على هذه المعادلة 

t(4) = 2 * t(2) + O(4)

صحيح؟

لكن في النهاية ذكرت

اقتباس

من الشكل العام في أول الحل نستنتج أن : 

2^k = 4 = n

لم افهم هذه النقطة.

و اشكرك جدا على الشرح التفصيلي و علو وقتك - بارك الله فيك

تم تعديل هذه المشاركة بواسطة الاخير زمانه في 14 فبراير 2012 في 02:15

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#7
اقتباس
و اشكرك جدا على الشرح التفصيلي و علو وقتك - بارك الله فيك

و فيك أخي العزيز

إذا طلبت منك إيجاد 

t(8)

كيف يمكن أن تبدأ بالحل ؟؟

بانتظار ردك أخي و أنصحك بأن تحاول جاهداً بالورقة و القلم ليس أن تكتفي فقط بالقراءة !

ردك له أهمية لأعرف كيف يمكنني إيصال الفكرة لك .

#8

اولا - شكرا لك اخي على تواصلك - وشكرا على السؤال - لأرى هل فهمي للموضوع صحيح

هل تقصد ان اجد القيمة مباشرة ام اعوض في المعادلة

يعني انا ممكن احسب ال 

t(8)

من هذه المعادلة

t(8) = 8 lg 8

صحيح؟

و ممكن ايضا اقول ان

t(8) = t(4) + t(2) + t(1)

ممكن اقول ان

t(8) = 3 * t(2) + O(8)

وبحساب ال

t(2)

و تعويضها

t(8) = 3 * [2*t(1) + O(2)] + O(8)
t(8) = 6 t(1) + 3 O(2) + O(8)

الان انا صراحة لست متأكد من التبسيط لهذه المعادلة

هل استطيع التلاعب بقيم ال O كما اشاء

بعد ادخال و اخراج حصلت على

O(24) ==> O( 3 * 8)

وبما ان

 
lg  8 = 3
n  =8

تصبح

O(n lg n)

مع اعتبار ان قيمة 

6 t(1)

هي ثابت

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#9
الاخير زمانه كتب:

اولا - شكرا لك اخي على تواصلك - وشكرا على السؤال - لأرى هل فهمي للموضوع صحيح

لا شكر على واجب

هل تقصد ان اجد القيمة مباشرة ام اعوض في المعادلة

أريد منك أن تستنتج التعقيد استنتاجاً حتى تعرف من اين أتت الـk !

يعني انا ممكن احسب ال 

t(8)

هذه هي النتيجة النهائية و التي نسعا للوصول إليها من خلال الاستنتاج

من هذه المعادلة

t(8) = 8 lg 8

صحيح؟

و ممكن ايضا اقول ان

من أين حصلت على هذه المعادلة ؟؟

لقد اقتربت من الحل لكن هنالك بعض الأخطاء

t(8) = t(4) + t(2) + t(1)

لا تنس شكل المعادلة العامّة و هو :

t(n) = 2 * t(n/2) + O(n)

ممكن اقول ان

لا يمكنك أن تقول :) هذا السطر خاطئ 

t(8) = 3 * t(2) + O(8)

بحساب t(8)من المعادلة العامة :

t(8) = 2 * t(4) + O(8)

أرني محاولتك في إكمال الحلّ ابتداءاً من السطر السابق ما هي خطوات الحلّ؟ يجب عليك أن توجد t(4) و t(2) من المعادلة العامة لتعود و تعوض كل منهم في مكانه .

t(2)

و تعويضها

t(8) = 3 * [2*t(1) + O(2)] + O(8)
t(8) = 6 t(1) + 3 O(2) + O(8)

الان انا صراحة لست متأكد من التبسيط لهذه المعادلة

هل استطيع التلاعب بقيم ال O كما اشاء

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

بعد ادخال و اخراج حصلت على

O(24) ==> O( 3 * 8)

وبما ان

 
lg  8 = 3
n  =8

تصبح

المهم الفكرة الأساسية وراء الـlog يبدو أنك ألفتها محاولة أخرى و سيكون الحل صحيحاً بإذن الله 

O(n lg n)

مع اعتبار ان قيمة 

6 t(1)

هي ثابت

#10

السلام عليكم

اولا - اسف على تأخري في الرد بسبب المحاضرات

بخصوص السؤال

اظنني فهمت نوعا ما ما تحاول الوصول اليه

t(n) = 2 * t(n/2) + O(n)

t(n/2) = (2 * t(n/4) + O(n/2)

t(n/4) = 2 * t(n/8) + O(n/4)

t(n/8) = 2 * t(n/16) + O(n/8)

و هكذا تستمر السلسلة

في حالة ال

t(8)

قيمة ال k هي 3 - صحيح؟

بالتعويض بالارقام

t(8) = 2 *[ 2 * [ 2 * t(1) + O(2) ] +O(4) ] + O(8)

= 8 * t(1) + 4 * O(2) + 2 * O(4) + O (8)

هنا ايضا لست متأكد من التبسيط

t (8) = O(8) + O(8) + O(8)

t(8) = 3 * O(8)
t(8) = O (3 * 8)

= n lg n

شاكرا تواصلك اخي محمد

تم تعديل هذه المشاركة بواسطة الاخير زمانه في 15 فبراير 2012 في 03:24

/index.php/topic/264448-%D8%A7%D9%84%D8%A8%D8%AF%D8%A7%D9%8A%D8%A9-%D9%85%D8%B9-%D8%A7%D9%84%D8%A7%D9%86%D8%AF%D8%B1%D9%88%D9%8A%D8%AF/

 

اني وان كنت الاخير زمانه ---- لأتِ بما لم تستطعه الاوائلُ

#11

تماماً أخي حلك صحيح 100% بارك الله بك

مواضيع مشابهة