المساعدة في التحليل المقارب

https://stackoverflow.com/questions/3815879

26-09-2019
|

سؤال

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

إليك مثال على ما أعنيه.

حان الوقت لـ "SortArray" لفرز صفيف مع 400 عنصر: 4
حان الوقت لـ "SortArray" لفرز صفيف مع 800 عنصر: 8
حان الوقت لـ "SortArray" لفرز صفيف مع 1600 عنصر: 16
حان الوقت لـ "SortArray" لفرز صفيف مع 3200 عنصر: 26
حان الوقت لـ "sortarray" لفرز مجموعة عشوائية مع 400 عنصر: 255
حان الوقت لـ "sortarray" لفرز مجموعة عشوائية مع 800 عنصر: 958
حان الوقت لـ "sortarray" لفرز مجموعة عشوائية مع 1600 عنصر: 4059
حان الوقت لـ "sortarray" لفرز مجموعة عشوائية مع 3200 عنصر: 16585

أي مساعدة حول كيفية القيام بحساب التدوين الكبير لشيء مثل هذا؟ شكرًا!

المحلول

بحكم التعريف ، فإن التعقيد المقارب للخوارزمية يمثل معدل النمو (في الوقت أو الفضاء أو بعض الموارد الأخرى) مع زيادة حجم (الإدخال). من الأفضل تحليل الخوارزمية نفسها لتحديد معدل النمو هذا. ومع ذلك ، إذا كان كل ما لديك هو خوارزمية فرز "صندوق أسود" ، وكنت تعرف فقط حجم الإدخال والوقت الناتج ، فإن أفضل ما يمكنك فعله هو التحقق مما إذا كان رسم بياني للمدخلات مقابل الوقت ينمو في نمط أن وظيفة معينة سوف.

لاختبار هذه الفكرة ، وظائف الرسم البياني مثل:

f (n) = n
f (n) = n ln n
f (n) = n^2

وما إلى ذلك ، ومعرفة أي شيء يشبه الرسم البياني الذي أنشأته في الوقت المناسب لتشغيل الخوارزمية. تذكر أن التحليل المقارب ينتهي بحذف كل من العوامل الثابتة على كل مصطلح وأي مصطلحات منخفضة الترتيب. لذلك ، إذا كانت الخوارزمية لا تزال تعمل في الوقت الخطي على الرغم من أن الرسم البياني يشبه f (n) = 2n ، فلا يزال لديك خوارزمية O (n).

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow