Jak udowodnić, że ?

To pytanie do pracy domowej z książki Udi Manbera. Każda wskazówka byłaby miła :)

Muszę pokazać, że:

$n(\log_3(n))^5 = O(n^{1.2})$

Próbowałem użyć Twierdzenia 3.1 książki:

$f(n)^c = O(a^{f(n)})$ (dla , ) $c > 0$ $a > 1$

Zastępowanie:

$(\log_3(n))^5 = O(3^{\log_3(n)}) = O(n)$

ale $n(\log_3(n))^5 = O(n\cdot n) = O(n^2) \ne O(n^{1.2})$

Dziękuję za wszelką pomoc.

asymptotics landau-notation mathematical-analysis Andre Resende
źródło

Jakich metod możesz użyć? spójrz na tę odpowiedź, która może dać ci kilka pomysłów. Również tutaj jest mnóstwo przydatnych informacji.

Ran G.

@RanG. czy należy to zamknąć w świetle powiązanego pytania

Suresh,

@Suresh Nie jestem pewien. Obawiam się, że jeśli nie, zostalibyśmy zalewani takimi pytaniami (które być może powinny lepiej pasować do matematyki ). Ale to ważne pytanie.

Ran G.

@RanG. Próbowałem nakładać limity, ale bezskutecznie.

Andre Resende

@RanG .: math.SE jest już zalany tymi pytaniami, w większości oznaczonymi „algorytmami”.

Louis

Odpowiedzi:

Zrób to, co zrobiłeś, ale pozwól ... to powinno to zrobić, prawda? $a = (3^{0.2})$

Powód, dla którego nie działałeś, jest następujący. Wielkie ograniczenie nie jest ścisłe; podczas gdy logarytm do piątej jest rzeczywiście duży - oh funkcji liniowych, jest także duży - oh piątej funkcji pierwiastkowej. Potrzebujesz tego silniejszego wyniku (który możesz również uzyskać z twierdzenia), aby zrobić to, co robisz.

Patrick87
źródło

W rzeczywistości dla każdego ,

ϵ > 0

$\epsilon >0$

n \log^{c} n = O (n^{1 + ϵ})

$n \log^c n = O(n^{1+\epsilon})$

Ran G.

@RanG. Tak, jest to bezpośrednia konsekwencja tego twierdzenia.

Patrick87

@AndreResende Jeśli moja odpowiedź pomogła ci rozwiązać problem i ma to sens, możesz „zaakceptować” za pomocą zielonego znacznika wyboru. Pomaga innym zobaczyć, co Ci pomogło, i może pomóc ci uzyskać więcej pomocy w przyszłości. Oczywiście, jeśli chcesz innych odpowiedzi, trzymaj się.

Patrick87

Innym sposobem myślenia o tym bardziej intuicyjnie jest przekonanie się, że główną rzeczą, którą musisz pokazać, jest to, że to lub równoważnie, że to . Kłody zawsze rosną wolniej niż jakakolwiek stała moc n, bez względu na to, jak małe. $(\log_3(n))^5$ $O(n^{0.2})$ $\log_3(n)$ $O(n^{0.04})$

Jeśli chcesz sformalizować ostatnie zdanie, możesz użyć twierdzenia 3 z wystarczająco małym jak wspomina @RanG w komentarzu do odpowiedzi @ Patrick87. $\alpha$

Artem Kaznatcheev
źródło