Hilfe mit großer O-Notation

Question

Ich hatte einige Probleme, als ich versuchte, das Konzept der großen O-Notation zu verstehen. Also, per Definition ist großes O wie folgt, T(n) ∈ O(G(n)) if T(n) <= G(n) * C.

Da die Konstante "C" eine ganze Zahl> 0 sein kann, wäre das folgende Beispiel auch nicht wahr?

Beispiel:

n log n ∈ O(log n) 
n log n <= log n * c 

Wo C auf den Wert von n gleich ist.

Ich weiß, dass die Antwort ist, dass n log n ∉ O(log n) aber ich verstehe nicht, wie C kann jede Konstante sein.

Vielen Dank im Voraus für Ihre Hilfe: D

Answer 1

c ist nur, dass ein Konstante. Das bedeutet, dass Sie nicht sagen können: "Sei c der Wert von n", denn Sie müssen zuerst ein c auswählen und dann zulassen, dass der Vergleich für alle n gilt. In anderen Worten, damit einige T (n) O (G (n)) sein können, muss keine Konstante c existieren, so dass G (n) * c größer als T (n) für ist alle n.

Somit ist n log n nicht O (log n), weil n> c unabhängig davon, welche Konstante Sie wählen, bewirkt, dass n log n größer als c log n ist.

Answer 2

Lassen Sie mich Ihre Worte wiederholen.

c kann beliebig sein konstant.

Dies bedeutet, dass c nicht von n abhängen kann.

Answer 3

Die Idee ist, dass die Ungleichung gilt für alle n und festen c. Während Sie vielleicht ein bestimmtes c finden, so dass Sie log n, können Sie leicht andere n finden, für die es nicht gilt (nämlich n '> c).

Answer 4

In der Definition sollten Sie C nur durch die T und G selbst bestimmen. Das ist was ein konstantes C bedeutet. Also sollte C nicht von deren Eingabe abhängig sein. So können Sie nicht betrachten C = n

Answer 5

im Ausdruck n log n, können Sie die Außenn bis C nicht vergleichen, wie Sie tun. Das wäre so, als würde man den algebraischen Ausdruck x (x + 1) nehmen und eines der x durch eine Konstante ersetzen.

In n log n ist n eine Variable. In der großen O-Ausdruck ist C eine Konstante.

Answer 6

Der Wert von n hängt von der eingegebenen Menge ab, der Wert von C ist fest.

Also ja, wenn n = 16 und C = 256, es sieht aus wie n^2 * lg (n) für einen kleinen Eingang. Erhöhen Sie jetzt den Eingabewert auf 100.000.000; der Wert von C bleibt bei 256, Sie haben jetzt 256 * lg (100.000.000)

Answer 7

Vor allem, wenn n = C dann ist C keine Konstante. Und in den meisten realen Algorithmen ist C klein, sodass der große O-Teil für typische Werte von n normalerweise dominiert.

Aber die Groß-O-Komplexität beschäftigt sich mit der Effizienz eines Algorithmus für große n, insbesondere wenn n gegen unendlich geht. Mit anderen Worten sagt es Ihnen die Skalierbarkeit eines Algorithmus: wie gut ein gegebener Algorithmus eine sehr große oder doppelte Arbeitslast bewältigt.

Wenn Sie wissen, dass n immer klein ist, dann ist die Big-O-Komplexität nicht so wichtig, stattdessen sollten Sie sich auf die vom Algorithmus benötigte Wanduhrzeit konzentrieren. Auch wenn Sie zwischen zwei Algorithmen wählen, die die gleiche große O-Komplexität aufweisen (z. B. O (n log n)), ist oft eines besser als das andere (z. B. Zufalls-Pivot-Quicksort übertrifft im Allgemeinen eine binäre Heap-Sortierung).

Answer 8

Immer wenn ich auf dem großen oh feststecke, finde ich es nützlich, es als eine Konkurrenz zu betrachten: Ich wähle eine große-oh-Funktion (also in deinem Fall logn) und eine Konstante (c). Wichtig ist, dass ich einen echten Wert wählen muss. Normalerweise wähle ich tausend, nur weil. Dann muss ich meinen Erzfeind wählen lassen jeder n er wählt. Normalerweise wählt er eine Milliarde.

Dann mache ich den Vergleich.

Um das Beispiel zu beenden, wird jetzt 10^9 * (log (10^9)) deutlich deutlich größer als 1000log (10^9) gemacht. So weiß ich, dass das große oh nicht funktionieren wird.

Answer 9

Ich denke, dieser Link kann Dinge für Sie klären.

http://mohalgorithmsorbit.blogspot.com/2013/12/complexity-theory-approaching.html