تحليل التعقيد م! / ن! (M-N)!
-
29-09-2020 - |
سؤال
نظرا لوقت تشغيل خوارزمية ليكون M!أم أنها شيء آخر؟
يرجى توضيح.
شكرا
المحلول
يمكن أن تكون النمو خطية أو ثابتة اعتمادا على العلاقة بين $ 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} $
لا تنتمي إلى cs.stackexchange