Was ist die richtige Methode zu finden, um die Reihenfolge des Wachstums für diese Funktion zu gehen?

Question

2 ^ n + 6n ^ 2 + 3 n

Ich denke, es ist nur O (2 ^ n), die höchste Ordnung Begriff verwendet wird, aber was ist der formale Ansatz zu beweisen, dies zu realisieren?

Answer 1

Sie können diese 2^n + n^2 + n = O(2^n) beweisen, indem sie Grenzen im Unendlichen mit. Insbesondere f(n) ist O(g(n)) wenn lim (n->inf.) f(n)/g(n) endlich ist.

lim (n->inf.) ((2^n + n^2 + n) / 2^n)

Da Sie / inf inf haben, ein unbestimmte Form , können Sie L'Hopital der Regel und unterscheiden den Zähler und den Nenner, bis Sie etwas bekommen Sie können mit der Arbeit:

lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))

Die Grenze ist 1, so ist in der Tat 2^n + n^2 + n O(2^n).

Answer 2

Bitte beachten Sie:

Big O Notation HFG - Codefragment Algorithmus Analyse

Big O, wie Sie berechnen / nähern es?

Can bitte jemand den Unterschied zwischen Big-O und Little-O Notation?

erklären

Big-O für acht Jährige? (nicht gemeint sein Beleidigung)