Komplexitätstheorie: Wie vorgehen bei diesem Beispiel? |
17.11.2018, 18:07 | MatheNoob32 | Auf diesen Beitrag antworten » |
Komplexitätstheorie: Wie vorgehen bei diesem Beispiel? Die Frage ist jetzt, ob diese stimmt oder nicht, und warum. Lösungsideen Mein größtes Ziel wäre es, den Term links so umzuformen, dass man auf ein Vielfaches von kommt. Leider ist die Wurzel hier sehr unhandlich; leider ist ja , weshalb ich das nicht in die erste Potenz kriege. Alternativ habe ich auch versucht, ein bisschen abzuschätzen, was denn nun größer sein könnte. Ich habe jetzt einfach mal abgeschätzt, dass die Wurzelfunktion . Man könnte also sagen, nach 4 Schritten verzehnfacht sich der Funktionswert links. Währenddessen versechzehnfacht er sich rechts, was die Aussage gültig machen dürfte. Aber ob das ein ausreichender Beweis ist? |
||
23.11.2018, 08:03 | HAL 9000 | Auf diesen Beitrag antworten » |
Nachzuweisen ist die Beschränktheit von für . Das sieht man sofort durch Logarithmieren, z.B. mit dem dekadischen Logarithmus: für , daraus folgt , also sogar . |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|