أسهل طريقة لتحديد تعقيد الوقت من أوقات التشغيل

Question

لنفترض أنني أحاول تحليل خوارزمية وكل ما يمكنني فعله هو تشغيله بمدخلات مختلفة. يمكنني بناء مجموعة من النقاط (x ، y) كـ (حجم العينة ، وقت التشغيل). أرغب في تصنيف الخوارزمية ديناميكيًا إلى فئة تعقيد (خطي ، تربيعي ، أسي ، لوغاريتمي ، إلخ.) من الناحية المثالية ، يمكنني إعطاء معادلة تقارب السلوك بشكل أو بآخر. لست متأكدًا من أفضل طريقة للقيام بذلك.

لأي درجة متعددة الحدود ، يمكنني إنشاء منحنيات الانحدار والتوصل إلى قدر من اللياقة البدنية ، لكن ليس لدي أدنى فكرة عن كيفية القيام بذلك لأي وظيفة غير proLynomial. إنه أمر أصعب لأنني لا أملك أي معرفة سابقة بالشكل الذي يجب أن أحاول أن أحاوله.

قد يكون هذا أكثر من سؤال الرياضيات أكثر من سؤال البرمجة ، لكنه مثير للاهتمام للغاية بالنسبة لي. أنا لست عالم رياضيات ، لذلك قد يكون هناك طريقة أبسط من الأبسط للحصول على وظيفة معقولة من مجموعة من النقاط التي لا أعرف عنها. هل لدى أي شخص أي أفكار لحل مشكلة مثل هذه؟ هل هناك مكتبة رقمية لـ C# يمكن أن تساعدني في تحطيم الأرقام؟

Answer 1

حسنًا ، لا توجد العديد من فصول التعقيد التي تهتم بها حقًا ، لذلك دعنا نقول: الخطية ، التربيعية ، متعدد الحدود (درجة> 2) ، الأسي ، ولوغاريتمي.

لكل من هذه ، يمكنك استخدام أكبر زوج (x ، y) لحلها للمتغير غير المعروف. دع y = f (x) تشير إلى وقت تشغيل الخوارزمية الخاص بك كدالة لحجم العينة. لنفترض أن f (1) = 0 ، وإذا لم يكن بإمكاننا دائمًا طرح هذه القيمة y (1) من كل من y ، فهذا يزيل الثوابت في F (x). دع y (نهاية) تشير إلى القيمة الأخيرة (وأكبر) من y في مجموعة البيانات (x ، y).

في هذه المرحلة ، يمكننا حل المجهول في كل شكل قانوني:

f(x) = c*x
f(x) = c*x^2
f(x) = x^c
f(x) = c^x
f(x) = log(x)/log(c)

نظرًا لعدم وجود مجهول واحد فقط في كل معادلة ، يمكننا أي نقطة لحلها. النظر في البيانات التالية التي تم إنشاؤها من متعدد الحدود من الدرجة العشوائية> 2:

x = [ 1 2 3 4 5 6 7 8 9 10 ];
y = [ 0 6 19 44 81 135 206 297 411 550 ];

إذا استخدمنا النقطة الأخيرة التي يجب حلها لـ C لكل احتمال (على افتراض أن هذا سيكون أقل تقدير للضوضاء)

550 = c*10    -> c = 55
550 = c*10^2  -> c = 5.5
550 = 10^c    -> c = log(550)/log(10) ~= 2.74
550 = c^10    -> c = 550^(1/10) ~= 1.88
550 = log(x)/log(c) -> c = 10^(1/550) ~= 1.0042

يمكننا الآن مقارنة مدى جودة كل من هذه الوظائف للبيانات المتبقية ، إليك مؤامرة:

أنا جديد ولا يمكنني نشر الصور ، لذا انظر إلى المؤامرة هنا: http://i.stack.imgur.com/uh6t8.png

يتم عرض البيانات الحقيقية في العلامة النجمية الحمراء ، الخطية مع الخط الأخضر ، التربيعي باللون الأزرق ، متعدد الحدود باللون الأسود ، الأسي باللون الوردي ، ومؤامرة السجل باللون الأخضر مع O's. يجب أن يكون واضحًا تمامًا من المتبقيات التي تناسب بياناتك أفضل.

Answer 2

كان المنحنى المناسب هو فن ، لكنه الآن منحش إلى حد ما :) (هذه مزحة للفيزيائيين حولها)

تم إحراز الكثير من التقدم ، مما يسمح للبشر البسيط بتخمين (بعض) التبعيات الوظيفية غير التافهة.

لن أدخل في وصف للطرق والقيود ، ولكن بدلاً من ذلك سأيلي eureqa, ، وهو جزء جميل جدًا من البرامج التي تم تطويرها في كورنيل.

Eureqa (وضوحا "Eureka") هي أداة برمجية للكشف عن المعادلات والعلاقات الرياضية المخفية في بياناتك. هدفها هو تحديد أبسط الصيغ الرياضية التي يمكن أن تصف الآليات الأساسية التي أنتجت البيانات. Eureqa مجاني في التنزيل والاستخدام. ابحث عن تنزيل البرنامج ، والفيديو التعليمي ، ومنتدى المستخدم ، والمواد الأخرى والمرجعية.

جربت Eureqa عدة مرات مع نتائج جيدة للغاية إذا لم تكن النماذج معقدة للغاية. أعتقد أنه جيد بما يكفي للتمييز بين الحدود الحدود والسجلات والأواني.

هول!

Post Scriptum:

للأسف ، لم يعد البرنامج مجانيًا بعد الآن :(