Ich konnte dies nicht beweisen:die folgende Implikation (Big O Notation)
f(n) = O(g(n)) impliziert f(n)^k = O(g(n)^k)
where k is element of the natural, positiv numbers
ich ähnliche Beispiele im Internet gefunden haben. Aber ich bin mir nicht sicher, ob es richtig ist, diese Lösungen für dieses Beispiel zu implementieren.
Gehen Sie zurück zu definition of big-o.
f(n) = O(g(n)) <=> \exists M \in R+,
\exists n_0 \in N,
such that:
\forall n > n_0
|f(n)| < M.|g(n)|
Es ist offensichtlich, dass, wenn k > 0 dann |f(n)|^k < (M.|g(n)|)^k.
Wenn k < 0, ist die Beziehung umgekehrt.
unter Berücksichtigung der Big-O-Notation, habe ich ein anderes interessantes Problem gefunden. http://stackoverflow.com/questions/23492509/big-o-notation-algebra/23493414#23493414 Ich muss nur wissen, ob der Beweis der zweiten Frage richtig ist? – Snelfie
, dass das ähnliche Beispiel, das ich http://stackoverflow.com/questions/12361448/i-need-help-proving-that-if-fn-ogn-implies-2fn-o2gn – Snelfie
Pleasantries entfernt werden gefunden habe, werden . Wenn ich meine Änderungen rückgängig mache, hat dies keine Auswirkungen, da andere meinen Platz einnehmen werden. –
1 = O (n) aber 1^{- 1} ist nicht O (n^{- 1}) –