$ 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 {n} {e})= o (\ log (\ frac {n} {e}) ^ n) \ subeteq o (\ log n!) \ subetetq o (\ log n ^ n)= o (n \ log n) $ .

위의 모든 세트가 일치 함을 보여줍니다.

Answer 2

$ n ^ n $ 은 n보다 훨씬 큽니다. 첫 번째 곱셈 n x x n x n x ... x n (n 번), 후자는 1 x 2 x 3 x 4 x ... x n을 곱합니다. 따라서 $ o (\ log (n ^ n)) 이 아닌 명백한 입니다. 진실. $ o (\ log (n ^ n))> o (\ log (n!)) $ 은 분명하지만 사실이 아닙니다.

우리는 양쪽에있는 대수를 복용하기 때문입니다. Logarithms를 사용하면 제품이 제품과 지수를 제품 (매우 대략)으로 변경합니다. 우리가 제품을 N / 2를 위해 제품을 가져 가면 N / 2보다 큰 N / 2 요인이있는 것이 분명합니다! > $ (n / 2) ^ {n / 2} $ . 로그를 복용하고, 로그 N을 로그! > (n / 2) 로그 (n / 2). N> 4의 경우 N / 2> $ n ^ {1/2} $ n / span> (따라서 LOG N / 2> (log n) / 2, log n ...에! > (n / 2) 로그 (n / 2)> n / 4 log n= 1/4 로그 $ n ^ n $ .

그래서 로그 N!= $ \ theta (\ log n ^ n) $ .