Wie kann man herausfinden, ob eine gegebene Funktion O (n) ist?

Question

Ich wurde die folgende Frage in meinem Test gegeben:

Welche der folgenden sind in O (n)?

a) n + lgn b) n + 2n c) n + n^2 d) 1000n + 4500lgn + 54n

ich, dass die Zeit Komplexität von O kennen (n) hängt von der Anzahl der Elemente auf, um die Anzahl der Elemente, die Zeit erhöht es eine Operation steigt bis zum Ende nimmt. Stimmt es nach dieser Logik richtig zu sagen, dass a und c Zeitkomplexität von O (n) benötigen?

Answer 1

Betrachten wir die Definition von O (n), die es sein, dass für eine Funktion f (n) müssen zwei positive Konstanten sind, und ck, so dass c > 0, k > 0, n >= k und 0 <= f(n) <= cn. Wenn wir zeigen können, dass die Konstanten c und k existieren, dann ist die Funktion O (n) (und wenn diese Konstanten nicht existieren, dann ist die Funktion tatsächlich größer als O (n)).

Schauen wir uns F(n) = n + lg(n). Ist das O (n)? Wenn ja, dann sollten wir keine Probleme haben, Werte für c und k zu finden.

0 <= f(n) <= cn 
0 <= n + lg(n) <= cn 

Lets k 2 und betrachten den Basisfall festgelegt, wobei n 2 ist (weil n> = k).

0 <= 2 + lg(2) <= c * 2 
0 <= 2 + 1 <= 2c 
0 <= 3 <= 2c 
0 <= 3/2 <= c 

Lässt sehen, wie sich die Funktion verhält, wenn n zunimmt (lassen Sie n = 4 setzen und sehen, was passiert).

0 <= 4 + lg(4) <= c * 4 
0 <= 4 + 2 <= 4c 
0 <= 6 <= 4c 
0 <= 6/4 <= c 
0 <= 3/2 <= c .. take a look at that, it doesn't matter how large n becomes, c is 3/2 

So haben wir unsere Konstanten (c = 3/2 und k = 2) und so ist diese Funktion O (n) durch die formale Definition gefunden.

Schauen wir uns F(n) = n + n^2. Ist das O (n)? Es sollte ziemlich offensichtlich sein, dass es nicht ist, es ist tatsächlich O (n^2), aber lasst uns sehen, ob wir irgendwie Werte c und k finden können.

0 <= f(n) <= cn 
0 <= n + n^2 <= cn 

Lets k 2 erneut prüfen, und die Basis Fall, in dem n = k gesetzt.

0 <= 2 + 2^2 <= c*2 
0 <= 2 + 4 <= 2c 
0 <= 6 <= 2c 
0 <= 3 <= c .. so IF this is O(n), c is at least 3 

Mal sehen, was als n zunimmt passiert (jetzt n = 4)

0 <= 4 + 4^2 <= 4c 
0 <= 4 + 16 <= 4c 
0 <= 20 <= 4c 
0 <= 20/4 <= c 
0 <= 5 <= c  .. last time c was 3, now its 5 ... as n increases, c is not constant! 

Diese Funktion ist nicht O (n) - wir konstante Werte nicht finden können c und k, weil sie einfach don Ich existiere nicht.

Betrachte f (n) = 5n ... das ist O (n) (in diesem Fall ist es offensichtlich, dass c 5 ist). Betrachte f (n) = n * n .. das ist nicht O (n) (c wäre gleich n, was nicht konstant ist). Was wir wirklich sagen, ist, dass unsere Funktion f (n) durch eine andere Funktion g (n) begrenzt ist, die mit einer Konstanten multipliziert wird. Wenn wir fragen, ob eine Funktion O (n) ist, lassen wir g(n) = n, aber n^2, lgn, nlgn sind alle interessanten Grenzen (die wahrscheinlich auf einem Test sein werden).

Ist n + n^2 O (n^2)? Sie sollten keine Probleme haben, die Werte c > 0 und k > 0, n >= k zu finden, so dass 0 <= n + n^2 <= cn^2.

Werfen Sie einen Blick auf https://xlinux.nist.gov/dads//HTML/bigOnotation.html für weitere Informationen.