Fachrat Informatik - Forum

Schwierig dir zu helfen ohne gleich die Lösung zu offenbaren.

Quoted from "nethwa"

Hallo alle zusammen,
2n [nicht element von] O(n)
O(n) = {0,... ,n}

Das kannst du so auf keinen Fall machen. 2n ist in dem Beispiel eine Funktion und O(n) ist eine Laufzeitklasse.
In der Vorlesung/Übung müsste es Rechenregeln zum Umgang mit Laufzeitklassen gegeben haben, wenn ich mich recht erinnere ist die einfache Anwendung einer davon auch schon der Beweis für wahr/falsch.

Wie Sebastian schreibt: Das was du da schreibst, stimmt so nicht und der Beweis leitet sich sehr direkt aus der Definition bzw. den einfachen Rechenregeln für Laufzeitklassen ab
(deren Richtigkeit zumindest vom Verständnis auch gut nachvollziehbar ist).

Die Definition für O(n) ist wie folgt:


c ist dabei ein beliebiger konstanter Faktor.

Umgangssprachlich bedeutet "ist Element von O(g(n))" also "wächst höchstens so stark, wie g(n) - abgesehen von einem konstanten Faktor"

(Hinweise zur Notation: "genau dann, wenn" wird oft mit "gdw." abgekürzt oder auch als Äquivalenz geschrieben, also <=>.
Das umgedrehte E bedeutet "es existiert" und das umgedrehte A bedeutet "für alle")

Hoffe, dass das schon ein bisschen geholfen hat.

Mit freundlichen Grüßen,
Anselm

Das ist zwar ein wenig durcheinander/unkorrekt aufgeschrieben, aber du bist definitiv auf dem richtigen Weg!
Schau dir noch mal genau die 2 ersten Regeln (sehen richtig aus) von deinem Link genau an und dann führ jeden Schritt einzeln aus.

Denke schon, dass das die richtigen sind Und letztlich lässt sich der Beweis für deine Beispielaufgabe ja auch schon direkt aus der Definition ableiten.
Eine weitere recht grundlegende Rechenregel ist übrigens O(f(n)+g(n)) = O(max{f(n), g(n)})
Sollte klar sein: Wenn das Maximum über die stärke des Wachstums definiert ist lässt sich die schwächer wachsende natürlich durch die stärker wachsende ausdrücken,
somit "reicht" die stärker wachsende in der O-Notation aus.
Also ich würde hier den Beweis wohl einfach so führen, dass ich meine Beispielfunktion 2n und die Funktion n, zu deren Laufzeitklasse sie gehören soll, in der Schreibweise der Definition schreibe,
um so zu zeigen, dass 2n Element von O(n) gemäß Definition.

Im übrigen ist n hier KEINE funktion, sondern die Variable, von der die Funktionen abhängen können (üblicherweise in den Anwendungsfällen dann die größe des Arguments, also z.B. Anzahl der Elemente einer Liste oder derartiges).
Du schreibst entsprechend nicht n(x), sondern wenn dann f(n) und g(n) und setzt da entsprechend deine Funktionen ein.

Mit freundlichen Grüßen,
Anselm

PS: Hoffe ich nehme nicht schon zuviel vorweg, aber irgendwie muss ein Grundverständnis ja aufgebaut werden

Die Definition von lautet . Natürlichsprachlich kann man vielleicht sagen, das ab einem festen multipliziert mit einer Konstanten eine obere Schranke für ist.

Um zu beweisen ob gilt oder nicht, musst du entweder die entsprechenden Konstanten finden, sodass die obige Definition erfüllt wird, oder aber zeigen, dass es keine gibt, die obige Definition erfüllen.

Dazu kannst du dir erstmal hinschreiben ggf. umformen und überlegen, was hier zutrifft.

Gleich die erste Umformung solltest du anders angehen.
Wenn du die Regel

auf

anwenden willst, dann steht das f(n) für 2n (mit 2!). Und vergiss nicht das O mit aufzuschreiben.

Noch ein bisschen anders
Du hast ja schon eine Vorgabe, zu welcher Laufzeitklasse deine Funktion gehören soll, also wirst du in etwa so rangehen:




Zudem wirst du nie links eine Laufzeitklasse stehen haben: Eine Laufzeitklasse kann nicht Element einer anderen Laufzeitklasse sein, wenn überhaupt nur Teilmenge (da beide Mengen von Funktionen sind, nicht einzelne Funktionen). Dann ist entsprechend nur zu zeigen, dass gilt:

Ist jetzt irgendwie schon sehr viel geholfen, aber ist eben eine sehr grundlegende Aufgabe. Ich denke es macht wenig Sinn bei etwas, was fast nur die Schreibweise betrifft zu hoffen, dass du selber drauf kommst Muss man denke ich eher einfach mal gesehen haben.

Also mit Aussagenlogik hat das eigentlich nichts zu tun. Warte einfach die Übung ab, dort wird alles weiter erläutert. Außerdem werden aller Voraussicht nach nicht alle Aufgaben gelöst, sodass Du die Möglichkeit bekommst anschließend noch solche Aufgaben selber zu lösen.

du machst es dir viel schwerer als es ist.

Der Post von Anselm (19:02) sagt bereits alles, was du beweisen sollst.






Also nochmal auf deutsch: 'es gibt ein n0 in den ganzen Zahlen und ein c in den reellen Zahlen, sodass für alle n größer/gleich als n0 gilt, dass c*2*n kleiner oder gleich n ist'

Jetzt fängst du an zu testen: (später siehst du's sofort bzw. wenn du in der Schule dauernd Ungleichungen rechnen musstest, auch). Such dir ein c aus den reellen Zahlen aus. Nehmen wir zB. c = dreißig Millionen, passt es schon mal nicht, egal welches n0 ich nehme. Geht das überhaupt? Kriegst du schon raus

Übrigens: GTI und Aussagenlogik brauchst du in KvA nicht wirklich, aber es hilft ein bißchen (vllt zu 5%). Was du tun musst, ist das Skript verstehen (VERSTEHEN, nicht nur lesen) und sonst den Kopf anstrengen. Und die Übungen helfen vor allem auch

Naja, gerade bei so einfachen Sachen ist es teilweise schwer zu sehen, was man dann denn überhaupt noch hinschreiben soll, aber auch insgesamt ist es gewöhnungssache, einen Anfang zu finden. Aber mit der Zeit hat man das dann raus. In der Schule hatte ich wenig bis gar nichts in Richtung Beweise, aber in eigentlich allen theoretischen Vorlesungen (sei es nun Mathe oder GTI) bekommt man das Vorgehen recht schnell mit und bekommt dann ein Gefühl dafür. Mach dir also keine Sorgen, falls du noch Probleme hast.
Und wie pythong schreibt: Es fehlt bei dem, was ich geschrieben habe, nurnoch etwa eine Zeile. Und nicht zu kompliziert denken