int sum , n, m ;
sum = 0 ;
while ( n > 1 ) {
m = n ;
while ( m > 1 ) {
sum = sum + 0 ;
m = m - 4 ;
}
n = n - 4 ;
}
}
1- Calculate The time complexity in the worst case, for this algorithm for number of (addition) operations?
2- Calculate the value of variable "sum"?
واو - ابرمج PHP و delphi و JavaScript من 9 سنوات ... وكاتب كودات الى حد الشبع ... ولحد الان لا افهم هذا الكلام الخاص بالكتب الجامعية.
تعقيد زمني و تربيع و تكعيب ... وجع راس !
درجة تعقيد الخوارزمية( أو كلفة الخوارزمية complexite ) تدرسها لأنها تجعلك تنشأ ألغوريتم بدقة يعني بدون تبذير للموارد المستعملة مثل المعالج و الذاكرة الحية الخخخ... فهذا التبذير يصبح عبأ عندما تكون الألغوريتمات كبيرة و معقدة جدا
مثال بسيط :
لدينا جدول لقيم غير مرتب و نريد معرفة اذا كان هذا الرقم موجود أو لا في الجدول
سيكون لدينا افتراضا حلين مرتبة من الأكثر تبذيرا الى الأقل :
1) أن نستخدم حلقة for و نمر على كامل الجدول الذي طوله n اذا كان العدد موجود نرجع صح و اذا كان لا يوجد نرجع خطأ و بالتالي نكون قمنا ب n عملية سواء وجدناه أم لا
2) ان نستخدم حلقة while فيها شرطين أن يكون المؤشر i<N و أن تكون قيمة الايجاد خاطئة .
نمر على الجدول الى أن نجد العدد و نخرج من الحلقة أو لا نجده و تصبح i=n
مقارنة بينهما :
في أسوء الحالة عندما يكون العدد غير وجود : كلاهما سيقومون ب n عملية
في أفضل حالة عندما يكون موجود في بداية الجدول ( الخانة الأولى ) : الأول سيقوم ب n عملية بالرغم من أنه وجده و الثاني سيقوم بعملية واحدة
int sum,n,m;
sum = 0 ;
while (n > 1 ){
m = n;
while (m > 1 ){
sum = sum + 0;
m = m - 4;
}
n = n - 4;
}
1 - حساب التعقيد الزمني في اسوء الاحوال لهذه الخوالرزمية, بالنسبة لعدد عمليات الجمع
2- حساب قيمة المتغير "sum"
1 - حساب التعقيد الزمني في اسوء الاحوال لهذه الخوالرزمية, بالنسبة لعدد عمليات الجمع
لم أفهم شيئًا!
2 - حساب قيمة المتغير "sum"
يساوي الصفر.
وأخيرًا لعرض النص كشفرة، أسبق الشفرة بأربع مسافات لتظهر هكذا:
movq $4,%rax
بدل أن تظهر هكذا:
movq $4,%rax
مع ان هذا يبدو كأنه واجب و يجب عليك ان تحله بنفسك و لكن سأعطيك الحل النهائي فقط، لكني تتأكد عندما تحله بنفسك بتتطابق الاجابة
الاجابة : BigO of N^2
شكراً للمساعدة :))
كل مافي الامر ان الامتحان غداً وانا اعرف الحل اذا كان يوجد تعليمة while واحدة في الخوارزمية
لكن الدكتور قال من الممكن ان تأتي while وفيها while اُخرى ولم نتعلم مثلها سابقاً
لذلك طلبت الحل "كاملاً"
شكراً مرة ثانية :))
انها N تربيع لأنها في حلقة N و بحلقة اخري M و بما أن N = M لذا تصبح N تربيع
و لكن لو كانت الزيادة بأستعمال * او / بدل من + او - ستصبح Log N تربيع بدل من N تربيع
و اذا كانت واحدة هكذا و الاخري بالشكل الاخر ستصبح N LogN
التعليقات