تقاطع سطح الطائرة

Question

أحاول معرفة متى تكون خوارزمية الاختيار التربيعية أسرع من خوارزمية اختيار خطية. تشغيل بعض التجارب التي قمت بإنشاء قطعتين ثلاثية الأبعاد تظهر أوقات تشغيل الخوارزمية كدالة لحجم صفيف الإدخال وإحصاء الترتيب المرغوب فيه. باستخدام gnuplot لرسم المؤامرة أكدت أن هناك حالات عندما تكون الخوارزمية التربيعية أسرع. ثم استخدمت خوارزميات Gnuplot المناسب للعثور على وظيفتين يتمتعان بأوقات الدراجات التي أجريتها (A، B، C، D، E، F) ثوواط ثابتة وجدت بالفعل ولكن المغادرة):

lin_alg_runtime (x، y) =X + B.Y + C.

quad_alg_runtime (x، y) = (d * x * e * y) + f

حيث x هو حجم صفيف الإدخال و y هو إحصاء النظام.

الآن أنا أضيع نوعا من كيفية استخدام هذه النماذج لحساب وقت التبديل بين التنفيذ التربيعي والتنفيذ الخطي. أظن أنني يجب أن أجد حيث تتقاطع هاتين الوظيفتين لكنني لست متأكدا تماما عن كيفية القيام بذلك. كيف يجد المرء مكان وجود هاتين الوظيفتين؟

Answer 1

أساسا تريد استخدام الخوارزمية التي لديها أدنى تقدير وقت التشغيل.

يمكنك فقط حساب قيمة كل من الدورات الدراسية المقدرة، واستخدم الخوارزمية بأقل قيمة. يمكنك تبسيط هذا قليلا جدا.

تريد استخدام الخوارزمية رباعية عندما:

qual_alg_runtime(x,y) < lin_alg_runtime(x,y)
ax + by + c < dxey + f
ax + by -dexy + c-f < 0

لذلك يمكنك حساب ax + by -dexy + c-f وإذا كان أقل من الصفر، استخدم الخوارزمية التربيعية.