|
عضو فعال
تاريخ التسجيل: 2004-04-21
مشاركات: 3106
الجامعة: حلب
الكلية: الهندسة المعلوماتية
المرحلة: ماجستير
الاختصاص: ذكاء صنعي
|
كتب Anos: من أجل حساب تعقيد خوارزمية : أول شي بدك تحددي العملية يلي عم تاكل وقت أكتر شي ..مثلا اذا كان عندك بلوك معين عملية ضرب و عملية جمع فالعملية يلي رح نهتم بحساب التعقيد من أجلها هي الضرب .. ثانيا : تحددي بعد المسألة n فمثلا من أجل البحث التسلسلي يكون البعد هو طول الشعاع ... بعد ذلك تحاولي ايجاد عدد مرات تنفيذ العملية الأعقد التي وجدناها في أولاً .. و ذلك بشكل تقريبي ... أقصد بدلالة n أو كما تعلمنا (n)O بأكدلك انو موضوع التعقيد سهل و بدو بس شوية تدريب فهو تطبيق لمجاميع شهيرة .... في اغلب الأحيان ... Rafee19_88 asked for some assistance to solve his exercise, not for some cock and bull story. It is often the case that it is hard to find the functions that give the progression and its sum, because it is neither arithmetic nor geometric for us to be able to deduce the functions from a simple application of a rule. Practically speaking, it is obvious that for 1 <= n <= 20, the inner loop of Rafee19_88's problem executes the following number of times: 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540 If we compare this to the square function on the same range:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400
And to the cube function:
1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, 4913, 5832, 6859, 8000
We find that it is much closer to the square function, and that saying that the algorithm is bound by O(n3) is really making an overstatement. On the other hand, it isn't directly obvious how to derive the function that represents the first progression for us to be able to make a big-theta analysis giving the exact complexity of the function. Does anyone know how to derive it? كتب Rafee19_88: طيب أنوس بتحسن تعطينا مثال مع الحل و ألك جزيل الشكر Consult a good algorithms book man. Check this one, for example. |
أرسل من قبل 
