مساعدة - حساب تعقيد الخوارزمية

السلام عليكم ..

عند حساب التعقيد مع وجود حلقات .. إسأل نفسك .. ما هو العدد الأعظمي لكل حلقة ...

الحلقة الأولى تعمل n مرة ..

الحلقة الثانية . اعتقد انها تكافئ

for(int j = 1 ; j < ln(i^2); j++)

الحلقة الثالثة واضحة ..

اعتقد أن الخوارزمية من رتبة

O(n^3)

...و الله أعلم ...

اسف ( الى صاحب الموضوع ) كنت قد رأيت موضوعك قبل يومين ولكن انشغلت ونسيت ان ارد عليك ..

houssam11350_11350 كتب:

السلام عليكم ..

عند حساب التعقيد مع وجود حلقات .. إسأل نفسك .. ما هو العدد الأعظمي لكل حلقة ...

الحلقة الأولى تعمل n مرة ..

الحلقة الثانية . اعتقد انها تكافئ

for(int j = 1 ; j < ln(i^2); j++)

الحلقة الثالثة واضحة ..

اعتقد أن الخوارزمية من رتبة

O(n^3)

...و الله أعلم ...

@حسام ::

لا يمكنك ان تقول انها O(N^3) مالم تتأكد من شئ وهو ان الحلقات الثلاثة متداخلة .. أي ان تكون بهذا الشكل ::

for ( i ----------------)
{
    for(j= -----------------------------)
   {
              For(k= ---------------------)
                    {

عندها مباشرة الزمن الكلي للدالة يكون الزمن التكعيبي .. لكن هذا الزمن العام او ما يسمى بالاحتمال الاسوء .. اي ان اسوء احتمال في هذه الدوارات الثلاث نحصل عليه بعد n ^ 3 من الزمن ..

لكن هنا ايضا يجب ان ننتبه الى ( هل شرط التوقف او نهاية كل دوارة من الثلاث هي متساوية ؟ ) ؟

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

هنا لديك الحلقة تبدأ من 1 وتنتهي بـ n .. لذلك زمن هذه الجملة هو n+1 والسبب هو ان n عدد الدورات التي ستأخذها لتنتهي الدورات ، وسبب وجود +1 هو اخر شرط .. فانه سيختبر الشرط ولكن لن يدخل فيه لانه تناقض مع شرط التوقف ..

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

ان شاءلله نويت ان اكتب مقالة خاصة بهذا الموضوع ..

تحياتي العطرة ..

السلام عليكم ..

لو طبقنا الكود التالي بالجافا :

public class AlgoTest
{

	public static void main(String[] args)
	{
    	int n = 100;
    	int sum = 0;
    	for (int i = 1; i <= n; i++)
        	for (int j = 1; j <= i * i; j *= 2)
            	if (j % i == 0)
                	for (int k = 1; k <= j; k++)
                    	sum++;

    	System.out.println("sum="+sum);
    	System.out.println("n * Math.log(n)=" + n * Math.log(n));
    	System.out.println("n * Math.log(n) * n=" + n * Math.log(n) * n );
	}
}

لكانت النتيجة :

sum=10795
n * Math.log(n)=460.51701859880916
n * Math.log(n) * n=46051.701859880915

اذا ..n Log N لا يصلح .. (ماذا بشأن الحلقة الثالثة) و ربما الأقرب n * [Log N] * N أي [N^2] * [Log N]بدلا من N^3 والله أعلم ..

و بانتظار مقالتك ...

شكرا للجميع على المساعدة

سنان محمد صالح كتب:

ان شاءلله نويت ان اكتب مقالة خاصة بهذا الموضوع ..

ياريت يا سنان تكتب لنا مقالة عن الموضوع