تعقيد $ O (\ Log (n ^ n)) $ vs $ o (\ log (n!)) $

Question

هو $ o (\ log (n ^ n)) ؟هل هناك أي خوارزمية جيدة / عملية مع هذا النوع من التعقيد؟

وأيضا، للتحقق من فهمي لتعقيد الخوارزميات، هل هذين $> O (n \ log (n)) $ ؟

أنا بدأت للتو في هذا الموضوع وليس متأكدا حقا ما إذا كنت أحصل عليه بشكل صحيح.

شكرا وابق في آمنة.

Answer 1

$ o (\ log n ^ n) $ و $ o (\ log n!) $ كلاهما يصف نفس مجموعة الوظائف.

لاحظ أن $ (\ frac {n} {e}) ^ n \ le n!\ Le n ^ n $ ، ومن هنا:

$ o (n \ log n)= o (n \ log \ frac {e} {e} {e})= o (\ log (\ frac {n} {e}) ^ n) \ subseteq o (\ log n!) \ subseteq o (\ log n ^ n)= o (n \ log n) $ .

يظهر هذا أن جميع المجموعات المذكورة أعلاه تتزامن.

Answer 2

$ n ^ n $ أكبر بكثير من n!. أول تضاعف N X X N X N X ... X N (N مرات)، تضاعف الأخير 1 × 2 × 3 × 4 ... x n. لذلك هو واضح هذا $ O (\ Log (n ^ n)) ليس كذلك حقيقية. $ o (\ log (n ^ n))> o (\ n!)) $ أقل وضوحا، ولكن أيضا غير صحيح.

ذلك لأننا نأخذ اللوغاريتم على كلا الجانبين. يؤدي أخذ اللوغاريتمي إلى تغيير المنتجات إلى المبالغ والعروض للمنتجات (تقريبا تقريبا). وإذا أخذنا المنتج ل N!، فمن الواضح أن لدينا عوامل N / 2 أكبر من N / 2، لذلك N! > $ (n / 2) ^ {n / 2} $ . أخذ اللوغاريتم، سجل ن! > (N / 2) سجل (N / 2). ل n> 4 لدينا N / 2> $ n ^ {1/2} $ ، وبالتالي تسجيل n / 2> (سجل n) / 2، لذلك سجل n ! > (n / 2) سجل (n / 2)> n / 4 سجل n= 1/4 سجل $ n ^ n $ .

حتى سجل ن!= $ \ theta (\ log n ^ n) $ .