Komplexität O-Notation

[DerSaugstutzen]

Hey Leute, ich sitze hier an der Vorbereitung für eine Klausur und tu mich mit der O-Notation noch etwas schwer. Im Anhang ist eine Aufgabe, bei der ich mir etwas unsicher bin, was meine Lösungsvorschläge angeht. Diese sind folgende:
a) O(n^2)
b) O(n^3)
c) O(n^3)
Wenn da mal jemand drüberschauen und gegebenenfalls verbessern könnte, wäre ich sehr dankbar. Danke schonmal

 

[Xyz1]

13.10?
Dieser Link könnte dir nützlich sein: https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
Ich habe ehrlich keine Lust, vorzurechnen, bei 0 Eigeninitiative

 

[JCODA]

Ich hätte beim letzen O(n^4) gesagt, da du "n mal n^3" aufsummierst.

 

[DerSaugstutzen]

Am 13.10.2016 war die letzte Klausur, die ich gerade durcharbeite. Was spielt das Datum denn für eine Rolle? 0 Eigeninitiative find ich auch stark zu behaupten, wenn ich bei einer Ankreuzaufgabe meine angekreuzten Antworten liefer. Danke für den Wikipedia-Link...da wär ich nie drauf gekommen. Wenn man keine Lust hat zu helfen, kann man es auch einfach lassen.
@JCODA danke für deine Antwort. Könntest du das ein bisschen genauer erläutern? Sehe auf den ersten Blick nicht, wo ich "n mal n^3" rechne. Ich summiere doch praktisch nur n^3 auf oder nicht?!

 

[DerSaugstutzen]

Edit: Doch macht Sinn mit n^4. Dankeschön

 

[Tobse]

@DerSaugstutzen Mach dir um den Kollegen keinen Kopf, dessen Gedankengängen kann man manchmal nicht folgen.

Ist damit deine Frage geklärt? Oder brauchst du bei den anderen Aufgaben noch Hilfe?

Ich verstehe selbst nicht ganz, wie man bei 2. auf n³ kommt. n * sqrt(9n²) +n lässt sich doch in linearer Zeit bestimmen. Bleibt die Summe in Abhängigkeit von n, ergo O(n).

 

[Xyz1]

0 Eigeninitiative find ich auch stark zu behaupten,

Nagut, eigentlich wollte ich nicht darauf antworten, aber jetzt bin ich ja gezwungen dazu......
Sogar ein dressierter Schimpanse könnte zufällig drei Antwortmöglichkeiten hin klatschen und sagen: Macht mal, fundiert begründet das mal schön, ich mach mir keinen Finger krumm.
Von daher kann ich dir leider nicht helfen. Werf doch ne Münze?

 

[DerSaugstutzen]

@Tobse naja die Wurzel aus 9n^2 ist 3*n und das mit n multipliziert ergibt 3n^2, also quasi n^2. Durch das Summenzeichen kommt man dann auf n^3. Also dachte ich mir zumindest

 

[DerSaugstutzen]

@DerWissende du rufst sicher auch bei Leuten an, die ihre Katze vermissen und sagst, dass du sie nicht gesehen hast oder? Wenn man nichts Positives zu sagen hat, ist es manchmal nicht schlecht, einfach gar nichts zu sagen...

 

[Tobse]

@Tobse naja die Wurzel aus 9n^2 ist 3*n und das mit n multipliziert ergibt 3n^2, also quasi n^2. Durch das Summenzeichen kommt man dann auf n^3. Also dachte ich mir zumindest

Ich verstehe die Aufgabe glaub nicht 100%. Die Terme, die man da bewerten soll, haben ja nichts mit der O-Notation zu tun, oder? So wie ich das verstehe sind das einfach nur Terme deren Komplexität bei der Auswertung man bestimmen soll.
Unter dieser Annahme:

n*sqrt(9n²)+n lässt sich in Konstanter zeit Bestimmen, weil:

x * y ist O(1)
x + y ist O(1)
x^y ist O(y), bei y = const also O(1)
sqrt(x) ist O(1)

Damit ist der Gesamte Term n*sqrt(9n²)+n O(1). Jetzt wird das ganze ja noch Aufsummiert, und zwar für alle n von 0 bis n (n ist hier ja irgendwie doppelt verwendet...). Und die Summe hat eine Komplexität von O(n).

Und O(n) * O(1) bleibt O(n).

 

[stg]

Ich verstehe die Aufgabe glaub nicht 100%.

Richtig.

Die Terme, die man da bewerten soll, haben ja nichts mit der O-Notation zu tun, oder?

Hier war der Aufgabensteller ein wenig schlampig bei der Formulierung, vielleicht kommt daher auch dein Missverständnis der Aufgabe. Die Terme, die dort stehen, sind als "rechte Seite" einer Abbildungsvorschift zu verstehen. Die Frage ist nun: Wenn n wächst, wir stark wächst dann diese "rechte Seite".

 

[DerSaugstutzen]

Rechne dir mal die Ergebnisse für n=2 und n=4 aus. Wenn es O(n) wäre, müssten sich die Ergebnisse ja auch mindestens verdoppeln und das kommt bei weitem nicht hin. Das Ergebnis für n=4 ist auch mehr als das 4 fache, somit kann es auch nicht O(n^2) sein. Für n^3, also das 8 fache kommt es hin.

 

[stg]

Rechne dir mal die Ergebnisse für n=2 und n=4 aus. Wenn es O(n) wäre, müssten sich die Ergebnisse ja auch mindestens verdoppeln und das kommt bei weitem nicht hin. Das Ergebnis für n=4 ist auch mehr als das 4 fache, somit kann es auch nicht O(n^2) sein. Für n^3, also das 8 fache kommt es hin.

Die Argumentation ist aber grundfalsch. Das, was du machst, liefert allenfalls eine grobe Vorab-Vermutung. Du widersprichst dir in deinen Argumenten sogar selbst, aber das nur am Rande. Die Landau-Symbole sind ganz klar definiert und an diese Definition und nichts anderes sollte man sich halten.

 

[Xyz1]

O(n) wäre, müssten sich die Ergebnisse ja auch mindestens verdoppeln und das kommt bei weitem nicht hin.

goldig, natürlich können O(n) und O(n) unterschiedlich schnell wachsen (ganz erheblich sogar), das besagt die O-Notation *nicht*.
Das Fach heißt Algorithmen, also ist ein Algorithmus gemeint, der beschriebene Laufzeit hat.
Sorry, aber ich habe dir doch bereits einen nützlichen Link an die hand gegeben. Damit solltest du es schaffen können. Zum Bereitstellen einer Musterlösung bin ich nicht willens.