1) 1 nicht groß O (1/x)
Um zu zeigen, dass 1 nicht O (1/x), müssen wir, dass für jede konstante c, es zeigen, ist kein x_0 so dass 1 <= c*1/x für alle x >= x_0. Angenommen, 1 ist ein großes O von 1/x. Wir nehmen c = c_0 > 0, eine Konstante. Dann müssen wir 1 <= c_0*1/x für x >= x_0 haben. Unter der Annahme x > 0 können wir lösen und erhalten x <= c_0. Dies kann nicht für alle x >= x_0 (es funktioniert nicht für die erste Zahl, die größer als oder gleich max(x_0, c_0) ist), also unsere Annahme war falsch und die erste ist nicht groß O der Sekunde.
2) e^x ist nicht O (x^5) Big O
Um zu zeigen, dass e^x nicht O ist (x^5), wir, dass für jede Konstante c zeigen müssen, gibt es keine x_0 so dass für alle x >= x_0, e^x <= c*x^5. Angenommen e^x ist groß O von x^5. Wir nehmen c = c_0 > 0, eine Konstante. Dann müssen wir e^x <= c_0*x^5 für x >= x_0 haben. Wir können dies umstellen, um e^x/x^5 <= c_0 für alle x >= x_0 zu erhalten. Die Grenze von e^x/x^5 als x -> +inf tendiert jedoch zu +inf; wir können l'Hopital der Regel sehen diese durch Iteration:
e^x e^x e^x
lim --- = lim --- = ... = lim --- = +inf
x->+inf x^5 x->+inf 5x^4 x->+inf 120
Dies ist ein Widerspruch, da es keine Konstante c_0 größer oder gleich unendlich ist. Daher war unsere Annahme falsch und die erste ist nicht groß O der Sekunde.
Hinweis: Ich schreibe lim = +inf so etwas wie "der Wert des Ausdrucks wächst ohne Bindung".
Wenn Sie in einer diskreten Mathematik-Klasse sind, lehren sie Ihnen das. Machen Sie die Hausaufgaben, stellen Sie Fragen an den Professor, und Sie werden lernen, wie das funktioniert. Das Internet nach einer vorgefertigten Lösung zu fragen, entspricht im Allgemeinen nicht den akademischen Ethikstandards. Wie in Ihrem Lehrbuch erwähnt, besteht der Trick darin, zwei Funktionen zu bestimmen: Eine, die eine "untere Grenze" ist und eine, die eine "obere Grenze" ist. Wenn diese Begrenzungsfunktionen das gleiche Große O haben, dann funktioniert auch die Begrenzte Funktion. Es geht darum, die Konstanten zu ignorieren und sich darauf zu konzentrieren, wie die Funktion mit sehr großem x wächst. –
Das hört sich so an, als ob du um Hausaufgabenhilfe bittest ... –
@ChuckWalbourn Ich bin im Frühjahr in der Schule und die Klassen haben noch nicht angefangen. Ich habe etwas Vorwissen über diskrete Mathematik, aber ich weiß, dass großes O eines der Hauptkonzepte ist, also versuche ich, es vollständig zu verstehen.Ich mache Übungsfragen aus dem Lehrbuch und blättere durch das Internet, finde aber nichts, was mir hilft, die Schritte zu verstehen. Wenn Sie meine Frage nicht beantworten, sollten Sie den Beitrag nicht posten oder kommentieren. Diese Website wurde entwickelt, um einander zu helfen und darum bin ich hier. – Newbie