Lassen Sie uns also die Idee praktizieren,
zum Beispiel zwei Polynome zu vergleichen und zu entscheiden, ob
sie zur gleichen Klasse gehören oder nicht.
Also definieren wir die Klasse selbst.
Um es zu tun, beginnen wir mit
der Idee der Big-O-Notation,
die manchmal bezeichnet wird
o in handgeschriebenem Text unterstrichen ist.
Das Verfahren hier ist wie folgt.
Grundsätzlich geht davon aus, dass wir zwei unserer Funktionen
als x quadriert und 5x quadriert minus 100x haben.
Wir sprechen irgendwie über
die obere Grenze
einer Funktion in Bezug auf eine andere.
Grundsätzlich bedeutet dies, dass eine Funktion nicht
mehr größer ist als in
einer bestimmten Anzahl von Malen als die andere.
Mit anderen Worten, wir müssen hier eine Ungleichheit aufschreiben.
Grundsätzlich nehmen wir an, dass wir eine Nachbarschaft
von einem bestimmten Punkt haben, ein, zum Beispiel.
Wir nennen eine Funktion
Big-o von einer anderen Funktion in dieser Nachbarschaft.
Wenn es eine konstante,
positive Konstante gibt, C wie die Beziehung,
absoluter Wert der Beziehung der
Funktionen f und g übersteigt
diesen Wert c. Also lassen Sie uns
zum Beispiel unseren Fall betrachten.
Wir haben x quadriert,
zum Beispiel, nennen wir es f ist x quadriert,
g ist 5x quadriert minus
100x und ich nehme an, dass x nähert sich unendlich.
Was wir also tun werden, werden wir sagen,
ist, dass eine Funktion größer ist als die
andere in irgendeiner Nachbarschaft der Unendlichkeit.
Wir müssen
so etwas aufschreiben wie der absolute Wert von f
ist kleiner oder gleich einer
Konstante multipliziert mit dem absoluten Wert von g, in Ordnung?
Mit anderen Worten, x Quadrat kleiner oder größer als eine
Konstante multipliziert mit Epsilon
[unhörbar] 5x quadriert minus 100x.
Es ist ziemlich einfach zu verstehen, welche
Konstante eigentlich gut für uns hier ist.
Beginnen wir zum Beispiel mit
der Konstante c, die gleich eins ist.
Nun, es ist offensichtlich, dass es so ist,
denn wenn wir einfach annehmen, dass c gleich eins ist.
So erhalten wir x quadriert auf der einen Seite und
5x Quadrate minus 100x auf der anderen Seite.
Wenn wir x quadriert
von beiden Seiten subtrahieren, so erhalten wir Funktionen,
die von irgendeinem Punkt deutlich positiv
sind, weil wir
eine parabolische Funktion mit positiver betrachten.
Mein Koeffizient, also gibt
es eine Wurzel und nach dieser Wurzel
haben wir nur positive Werte.
So hält diese Ungleichheit und eine.
F ist Big-o in Richtung G,
das war ein Beispiel.
Ein Code argumentiert leicht, dass, wenn wir
diese Funktion austauschen müssen, die immer noch gilt,
nur weil statt c gleich eins zu schreiben.
Lassen Sie uns versuchen, diese Interpretation hier zu tun.
Also, im Grunde müssen wir etwas beweisen, wie das hier.
Also, um jedes zu tun,
müssen wir ein anderes c nichts betrachten,
ein kleines, aber ein großartiges.
Also im Grunde beginnen wir mit wie c gleich fünf.
Dann bekommen wir hier ein schönes Ergebnis.
Aber es ist nicht immer der Fall, denn zum Beispiel
lassen Sie uns einen interessanteren Fall betrachten.
Zum Beispiel, was [unhörbar] Funktionen,
Sinus von x und x,
als x nähert sich Null? - Wir wissen was?
Sie sind im Grunde Äquivalente, wie man erwarten sollte,
dass Sinus x im Grunde ein Big-O von x ist.
Es ist ziemlich einfach, weil
der absolute Wert von Sinus x, wie wir gesagt
haben, während wir über unsere zweite wichtige Grenze gesprochen haben,
jetzt größer ist als Modell x,
weil der absolute Wert von x
ist eigentlich die Fläche des Sektors,
und Sinus von x ist die Fläche des Dreiecks beziehungsweise.
Damit zählen wir, dass wir
mit einer Konstante c gleich eins
das absolut richtig bekommen.
Aber was ist, wenn wir einen Punkt des Interesses von Null ersetzen,
um uns Unendlichkeit sagen zu lassen?
Zunächst einmal, die Ideen, dass Sinus von x
ist big-o in Richtung x,
immer noch an diesem Punkt, weil im Grunde,
Sinus von x ist nicht größer als eins und x ist der größte.
Wie Sie sich vorstellen können, nähert sich x der Unendlichkeit.
So gilt diese Ungleichheit
zum Beispiel immer noch für dieselbe Konstante gleich eins.
Aber wenn wir es ändern,
wenn wir zwei Funktionen ändern,
dann bekommen wir 380,
[unhörbar] hier, weil Sinus x
und x nicht in Zeiten verwandt sind.
Weil sine x immer noch ist, sorry,
ich habe Ihnen gesagt, dass wir
Funktionen tauschen müssen und es nicht getan haben.
Es ist also eine große Täuschung hier.
Das ist weniger betrügerisch.
Also x ist Big-o von Sinus von x.
Also im Grunde ist Sinus von x
durch eins und minus eins begrenzt und x ist unbegrenzt.
Also, wenn wir versuchten, mit der Idee zu kommen
, dass x kleiner als einige Konstante sein sollte,
multipliziert mit Sinus von x und wir sagen, dass diese
Konstante, zum Beispiel, 10.000.
Also, was ist der Fehler?
Dann können wir zum Beispiel
nehmen x größer als zwei, da n,
diese Gleichung, wir werden fast
definitiv einfach abfallen und
das ist extrem nicht der Fall.
Es ist nicht richtig. Wenn
wir also über Big-O-Notation sprechen,
müssen Sie hier immer die Reihenfolge berücksichtigen.
Welche Funktion, in Bezug auf welche Funktion? Ist es Big-o?