Wenn die Laufzeit eines Algorithmus als Funktion F(x)=√n+(logn)^2 ausgedrückt werden kann, dann ist eine der folgenden Bedingungen nicht korrekt die Laufzeit?Wenn die Laufzeit eines Algorithmus als Funktion ausgedrückt werden kann F (x) = √n + (logn)^2,
1. O(n)
2. O(√n)
3. O(log(n)^2)
4. Omega(1)
Wenn die Zeitkomplexität eines Algorithmus von mehreren Begriffen besteht (hier √n und (log n)^2), können Sie alle Begriff mit Ausnahme der ignorieren, die größte für große n bekommt.
In diesem Fall kann gezeigt werden, dass √n >>(log n)^2 für ausreichend große n. Daher ist die Komplexität O(√n). Dies sollte genügend Informationen zur Verfügung stellen, damit Sie die Frage beantworten können.
Dies ist jedoch ein bisschen ein Sonderfall, weil n wirklich zu bekommen braucht sehr groß, bis der zweite Begriff wirklich ignoriert werden kann. Man sollte also bedenken, dass Big-O-Komplexität eine theoretische Aussage macht und nicht immer praktisch signifikant ist.
Haben Sie etwas über Komplexität gelesen? Es wäre sehr nützlich für deine Hausaufgaben. – MBo
Hallo, du fragst nicht am richtigen Ort. Ich rate Ihnen, gehen Sie dort fragen: http://math.stackexchange.com/ oder –
@ J.Chomel: Ich stimme nicht zu: Zeit Komplexität gehört zur Informatik, nicht in erster Linie auf Mathematik. Habe die Tags jedoch bearbeitet. –