Nachweis der großen O-Notation

Question

Beweisen 5n^2 + 2n -1 = O (n^2). Dies ist, was ich bisher versucht:

5n^2 + 2n -1 <= 5n^2 + 2n^2 -n2 for n>1 
    5n^2+ 2n -1 <= 6n^2 for n>1 
    5n^2+ 2n -1 = O(n^2) [ c = 6n^2, n0 = 1 ] 

Ist dies der richtige Weg Big O-Notation zu beweisen?

Answer 1

es sieht gut aus, ich denke, wenn Sie es für Ihre Aufgabenarbeit oder andere formelle Arbeit tun, dann können Sie es auch auf formalere Weise tun, wie für die Auswahl des Werts von Konstante (c) wie durch f (n)/g (n). Ansonsten sieht es korrekt aus.

Answer 2

Um zu beweisen, dass Ihr Ausdruck ist O(n^2), müssen Sie zeigen, dass es durch M*n^2 begrenzt ist, für eine Konstante M und einige minimale n Wert. Durch die Inspektion, können wir zeigen, dass Ihr Ausdruck von 10*n^2 begrenzt ist, für n=10:

Für n = 10:

5n^2 + 2n -1 <= 10*n^2 
500 + 20 - 1 <= 1000 
519 <= 1000 

Wir zeigen auch, dass der Ausdruck von 10*n^2 für jeden Wert begrenzt ist ngrößer als 10:

Für n > 10:

5n^2 + 2n -1 <= 10*n^2 
5*(10+i)^2 + 2*(10+i) -1  <= 10*(10+i)^2 
5*(i^2 + 20i + 100) + 2i + 19 <= 10*(i^2 + 20i + 100) 
2i + 19 <= 5*(i^2 + 20i + 100) 
2i + 19 <= 5i^2 + 100i + 500 
5i^2 + 98i + 481 >= 0, which is true for `i > 0` 

Hier

ist ein Link zum Wikipedia-Artikel über Big-O-Notation:

https://en.m.wikipedia.org/wiki/Big_O_notation

Update:

Beachten Sie, dass in der Praxis, um Ihren Ausdruck zu beschriften O(n^2) wir ‚gewonnen auf solch einen hässlichen schriftlichen Beweis zurückgreifen. Stattdessen werden wir nur erkennen, dass der n^2 Begriff den Ausdruck für große n dominieren wird, und dass das Gesamtverhalten O(n^2) sein wird. Und dein Ausdruck ist auch O(n^3) (und O(n^4), etc.).

Answer 3

Wir haben f (n) = 5 * n^2 + 2 * n-1 und g (n) = n^2

Um f (n) = O (g (n) zu beweisen), müssen wir nur 2 Konstanten finden, nämlich c> 0 und n_0, st f (n) < = c.g (n) für alle n> = n0.

Lassen Sie uns einen Wert von c = 5,5 sagen. Lassen Sie uns f (n) und c * g (n) auswerten und darstellen. Wie wir aus dem Plot sehen können, können wir es auch theoretisch zeigen, da n^2/2 - 2 * n + 1 = (n^2-4 * n + 2)/2 = ((n-2)^2- 2)/2> = 0 für alle n> = 4 bedeutet dies, dass 5 * n^2 + 2 * n-1 < = 5.5 * n^2 für alle n> = n0 = 4. Daher gilt f (n) = O (g (n)). (Bewiesen)