-1
Ich kann das beweisen, aber ich verstehe nicht, warum 3^n in O (10^n) ist. Liege ich falsch?Groß-Oh: Ist f (n) = 3^n in O (g (n)) = 10^n?
A
Antwort
0
Je konzeptioneller, je größer die Basis des Exponenten, desto schneller das Wachstum der Funktion.
Big-O gibt uns eine obere Grenze; das heißt, gegeben zwei Funktionen f(n) und g(n), wenn für alle Werte von n über einem bestimmten Schwellenwert (abgesehen von einigen kleinen Details wie die Konstante mehrere), g(n) dominiert f(n), dann können wir das sagen f(n) = O(g(n)).
Jetzt, für jede n >= 0, sollte es klar sein, dass 10^n ist mindestens so groß (aber die meiste Zeit viel größer) als 3^n.
Beachten Sie, dass es nicht besonders nützlich ist, das zu sagen 3^n = O(10^n). Dies ist keineswegs eine enge Bindung; Die Wachstumsraten dieser beiden Funktionen sind drastisch unterschiedlich. Eine effektivere Grenze für 3^n ist selbst — das heißt, 3^n = O(3^n).
+0
Ja, genau das habe ich mir gedacht, denn die Grenze ist nicht "eng", ich wurde verwirrt, wenn es überhaupt als o (g (n)) betrachtet wurde! Ich wollte nur bestätigen, dass es immer noch korrekt ist, auch wenn es nicht sinnvoll ist. – TimelordViktorious
+0
Ja, es ist zwar richtig, aber nicht sinnvoll. Wir könnten auch sagen: 1 = O (10^n). Während das wahr ist, ist es * wirklich * nicht nützlich; Eine Funktion mit der Funktion "1" hat eine konstante Laufzeit, während die Funktion mit der Funktion "10^n" eine exponentiell schlechtere Laufzeit hat. – Purag
+1
@ MH1993 Beachten Sie, dass Sie beim Schreiben mit "o" (wenig-oh) gegen "O" (groß-oh) vorsichtig sein sollten. Sie bedeuten zwei verschiedene Dinge, "o" bedeutet, dass die Grenze definitiv nicht eng ist, "O" bedeutet, dass es sein kann oder nicht. 'o' steht für' <'was' O' für '<=' ist. – Paulpro
'3^n' ist in' O (10^n) ', weil es nicht asymptotisch schneller wächst als' 10^n'. Das ist natürlich keine enge Grenze. '3^n 'ist auch in' O (3^n) ', was eine enge Bindung ist. – Paulpro
'h (n) = 1' und' i (n) = n' sind auch beide in 'O (10^n)' – Paulpro