Wie kann man beweisen, dass

Dies ist eine Hausaufgabenfrage aus Udi Manbers Buch. Jeder Hinweis wäre schön :)

Ich muss das zeigen:

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

Ich habe versucht, Satz 3.1 des Buches zu verwenden:

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

Ersetzen:

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

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

Vielen Dank für jede Hilfe.

asymptotics landau-notation mathematical-analysis Andre Resende
quelle

Welche Methoden können Sie anwenden? Schauen Sie sich diese Antwort an, sie könnte Ihnen einige Ideen geben. Auch hier gibt es viele nützliche Informationen.

Ran G.

@RanG. sollte dies im Lichte der verknüpften Frage geschlossen werden

Suresh

@ Suresh Ich bin nicht sicher. Ich fürchte, wenn wir das nicht tun, werden wir mit solchen Fragen überflutet (die vielleicht besser zur Mathematik passen sollten ). Aber es ist eine berechtigte Frage.

Ran G.

@RanG. Ich habe versucht, Grenzen einzuhalten, aber keinen Erfolg.

Andre Resende

@RanG.: Math.SE ist bereits mit diesen Fragen überflutet, meistens mit "Algorithmen".

Louis

Antworten:

Mach was du getan hast, aber lass ... das sollte es tun, richtig? $a = (3^{0.2})$

Der Grund, warum das, was Sie getan haben, nicht funktioniert hat, ist folgender. Die Big-Oh-Grenze ist nicht fest; Während der Logarithmus zum fünften tatsächlich ein großes Oh der linearen Funktionen ist, ist er auch ein großes Oh der fünften Wurzelfunktion. Sie benötigen dieses stärkere Ergebnis (das Sie auch aus dem Satz erhalten können), um das zu tun, was Sie tun.

Patrick87
quelle

In der Tat, für jede

ϵ > 0

$\epsilon >0$

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

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

Ran G.

@RanG. Ja, das ist eine direkte Folge des Satzes.

Patrick87

@AndreResende Wenn meine Antwort Ihnen bei der Lösung Ihres Problems geholfen hat und es sinnvoll ist, können Sie mit dem grünen Häkchen "akzeptieren". Es hilft anderen zu sehen, was für Sie funktioniert hat, und kann Ihnen helfen, in Zukunft mehr Hilfe zu erhalten. Wenn Sie andere Antworten wünschen, halten Sie natürlich durch.

Patrick87

Ein anderer Weg , um darüber mehr intuitiv zu denken, ist zu sehen , dass die Hauptsache , Ihnen zu zeigen ist , dass ist , oder äquivalent , dass ist . Protokolle wachsen immer langsamer als jede konstante Potenz von n, egal wie klein sie sind. $(\log_3(n))^5$ $O(n^{0.2})$ $\log_3(n)$ $O(n^{0.04})$

Wenn Sie den letzten Satz formalisieren möchten, können Sie Satz 3 mit einem ausreichend kleinen wie @RanG im Kommentar zur Antwort von @ Patrick87 erwähnt. $\alpha$

Artem Kaznatcheev
quelle