تحليل التعقيد م! / ن! (M-N)!

Question

نظرا لوقت تشغيل خوارزمية ليكون M!أم أنها شيء آخر؟

يرجى توضيح.

شكرا

Answer 1

يمكن أن تكون النمو خطية أو ثابتة اعتمادا على العلاقة بين $ M $ و $ n $ لأنها تنمو كبيرة. على سبيل المثال، إذا $ n $ ينمو مع $ m $ كما في $ m= n + 1 $ ، ثم $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ .

الآن، إذا كنت مهتما بأقصى قدر من النمو، فإن المعاملات الحدية $ \ binom {m} $ هي الأكبر عند $ n $ هي نصف $ M $ . ضع $ M= 2N $ واستخدم تقريب ستيرلينغ للحصول على العاملين. تحصل

$$ \ binom {2n} {n}=frac {(2n)!} {(n!) ^ 2} \ sim \ frac {(2n) ^ ^ {(2N) ^ ^ { 2n} e ^ {- 2n} \ sqrt {4n \ pi} {n ^} {2n} e ^ {- 2n} 2n \ pi}=pi ^ {- 1/2} 2 ^ {2N} n ^ ^ ^ ^ { -1/2} $