ما هو تعقيد الوقت من هذه القطعة؟

Question

giveacodicetagpre.

أحاول معرفة الوقت في الوقت الذي أعمله في دراسة أسئلة الترميز وتعقيد وقتهم وتمكنت من حل مشكلة التقليب هذه باستخدام العودية كما هو مطلوب ولكني أتساءل كيف أناحدد بدقة The Big- SPAN CLASS="حاوية الرياضيات"> $ O $ تعقيد الوقت لهذا الغرض كما هو مزيج من العودية تليها حلقة تكرارية.سأقدر حقا بعض المدخلات المفيدة في هذا.

Answer 1

دع $ f (n) $ يكون الجواب للحصول على إدخال من حجم $ n $ . ثم لدينا المعادلة التالية:

$ f (n)= f (n - 1) + (n - 1)!* n= f (n - 1) + n! $

ذلك لأنك تسمون وظيفة إدخال إدخال الحجم $ n - 1 $ والتي تعطي $ f (n -1) $ ، ثم تكرر أكثر من جميع التباديل من الحجم $ n - 1 $ والتي توجد $ (n - 1)! $ مثل هذه التباديل، ثم تتكرر في موقف العنصر الجديد، والتي توجد $ n $ مثل هذه المواقف.هذا يعطينا:

$ f (n)= [\ sum_ {i= 1} ^ n i!] <(n + 1)! $

يمكنك إثبات هذا بسهولة عن طريق الحث. حتى $ f (n)= o ((n + 1)!) $ .