O-Notation beweisen?

Hallo,

im Fach "Algorithmen und Datenstrukturen" muss ich die O-Notation beweisen.

Ich habe viel nachgelesen und verstehe trotzdem nicht wie ich das beweisen kann.

Ich habe absolut keine Ahnung wie ich vorgehen muss. :/

Die Aufgabe:

Bestimmen Sie, obf∈O(g) oderf∈Ω(g) oder beides (d.h.f∈Θ(g)). Beweisen Sie IhreAussagen unter Verwendung der Definitionen aus der Vorlesung.

f(n) g(n)

a) n^3/2 n^2/3

b) 10n^2+ log^2(n) n^2

c) 2^n 2^n+^4 + 3

d) 2^n 10n!

Ich würde mich sehr freuen, wenn mir jemand bei dieser Aufgabe helfen kann und

es mir für "dummies" erklären kann.

Danke schonmal im Vorraus!

1 Antwort

Rammstein53

28.04.2019, 16:41

Eine Funktion f(n) ist Element von O( g(n) ), wenn für n --> unendlich gilt :

f(n) <= const * g(n)

Das heisst, dass die Funktion f(n) für grosse n nicht so schnell wächst wie g(n).

Man schreibt auch oft f(n) = O( g(n) ), aber das ist nicht korrekt.

Beispiel :

f(n) = n + n^2

f(n) < n^2 + n^2

f(n) < 2 * n^2

Daher gilt f(n) € O ( n^2 ).

In der Praxis benutzt man für g(n) meistens die Funktionen

2^n
n^k
n * log(n)
n
n^(1/k)
log(n)

anders gesagt versucht man, eine Funktion f(n) auf eine der oben genannten Grenzen zu maximieren.

SRPower

Fragesteller

28.04.2019, 19:22

Danke:) könnten Sie mir das für a) zeigen?

Rammstein53

29.04.2019, 06:44

@SRPower

Wegen

f(n) <= c * g(n)

muss gelten

f(n)/g(n) <= c für grosse n

Hier am Beispiel

h1(n) = n^2/3

h2(n) = n^3/2

h1(n) / h2(n ) = 1 / n^(5/6)

Weil dieser Ausdruck für n-> unendlich gegen 0 strebt, kann man c einfach 1 setzen.

h1(n) / h2(n ) = 1 / n^(5/6) <= 1 für grosse n

Also gilt h1 € O( h2 )

Die Umkehrung:

h2(n) / h1(n ) = n^(5/6)

Dieser Ausdruck hat für n->unendlich keine Obergrenze, also ist h2 kein Element von O ( h1 ).

Aufgabe: O-Notation

Ist die folgende Aussage korrekt?

Wie beweise oder widerlege ich diese Aussage? Besten dank im voraus. :)

...zur Frage

Algorithmen und Datenstrukturen hilfe?

Es geht um die aufgabe 2, ich versteh die aufgabenstellung nicht und weiß halt nicht was man da machen soll. help pls

...zur Frage

Klassiker Aufgabe: "Die Seerose & der Teich"

Hallo Leute,

ich habe gestern eine Mathe Arbeit geschrieben, über Exponentielles Wachstum & Potenzen. Es gab eine Aufgabe, die man meiner Meinung nach nicht mathematisch lösen bzw. mit unserem Wissen nicht lösen konnte.

Die Aufgabe lautete:

Eine schnell wachsende Wasserpflanze bedeckt jeden Tag doppelt so viel von der Wasseroberfläche wie am Vortage. Nach 30 Tagen ist der halbe Teich zugewachsen. Nach wie vielen Tagen ist der Teich vollständig bedeckt ?

So diese Aufgabe wären rein logisch gesehen folgendermaßen zu lösen gewesen:

Pflanze verdoppelt ihre Größe pro Tag --> Nach 30 Tagen ist der halbe Teich bedeckt --> dementsprechend ist der Teich nach 31 Tagen vollständig bedeckt. Auf einen anderen Lösungsweg bin ich nicht gekommen. Wir sind in der 10 Klasse und haben uns noch nicht mit Algorithmen und Datenstrukturen beschäftigt & komme daher auf keinen anderen Lösungsweg.

Ich hoffe, jemand hat einen mathematischen Lösungsweg für die Aufgabe & kann mir helfen.

Danke im Vorraus, Acesoka

...zur Frage

Otto Forster Analysis 1 Buch unverhältnismaßig?

Hey. Ich übe gerade für Ana1 und bin in die Aufgaben gegangen (das nette Übungsbuch, was es zusätzlich gibt). Dort ist die Aufgabe 1C (also die 3. des gesamten Buches)

Man beweise für alle reellen Zahlen x,y und alle n aus N

(x+y über n) = Summe von k=0 bis n (x über n-k) (y über k)

Nach langem rumwerkeln mit einem Induktionsbeweis, schaute ich dann doch mal in die Lösung. Da schlug es mich glatt hin. Man führt für (mal eben) eine kleine Notation ein womit man die Aussage die es zu beweisen gilt, in eine äquivalente Aussage umformt. Man landet dann im Prinzip bei einem Beweis vom binomischen Lehrsatz (welcher dann rel. leicht ist).

Doch ich fragte mich: Wie verhältnismäßig ist es, eine solche Aufgabe als DRITTE Aufgabe in ein Analysis 1 Buch zu packen? Fühlte mich sehr demotiviert, weil ich die Aufgabe so vermutlich niemals hätte lösen können, weil sie meilenweit weg war.

...zur Frage

Bin ich der einzige, der mit Vorlesungen nichts anfangen kann?

Man kommt kaum mit den ausformulierten Definitionen mit, ehe einem die Lösungen monoton vorgekaut werden, und muss stets aus einer konzentrierten lage weggerissen werden und mit Notizen mitkommen.

Aber immerhin gibt es interessante Nebeninformationen, und man kann versuchen, nächste Beweisschritte abzufangen oder zu analysieren, in tandem mit starkem Konzentrationsaufwand.

Gibt es aber ein Skript, so kann ich das aber noch wesentlich verstärken:

Per Text kann man sich Sachen abdecken, überfliegen um mal einige Ansätze zu sehen und dann selbstständig versuchen zu beweisen ausgehend von Stichpunkten, mit höherem Tempo durchgehen (so war es laut einer neuen Studie so, dass 2x Anhören einer Vorlesung doppelt so effektiv fürs Lernen war, nun nehme ein Lehrbuch/Skript, ergo mehr Tempo) was das Verstehen fördert, sich ohne Ablenkung Notizen und weiterführende Gedanken (z.B. Verallgemeinerungen) aufbauen, und sich zunächst die Definitionen einprägen und auf Bedeutung tiefgründig zu analysieren (wichtiger Schritt, ohne den Übungen erschwert werden).

Der Nachteil ist jedoch dass man sich manchmal mehr mit Hintergrundforschung als Hausaufgaben und Missverständnissen beschäftigen muss, niemand Fragen beantwortet, und schon stark intrinsisch motiviert sein muss und ablenkungsresistent.

...zur Frage

Was geschieht wenn man Cl2 in Wasser einleitet?

Und gleichnochmal muss das "Gutefrage-Team Schiedsrichter spielen.

Ich bin der Meinung, dass wenn man Cl2 in Wasser einleitet, die Reaktionsgleichung lauten müsste

Cl2 + H2O <-> Cl- + ClO- + 2H+

Jetzt gibt's aber auch Kommilitonen, die raus haben

Cl2 + H2O <-> ClO- + O- + 1/2 H2

Ich bin ein wenig verwirrt ob der alternativen Lösung. Also wieso man statt 2 H+ Atomen, 1/2 H2-Atome hat.
In der Vorlesung hatten wir einmal diese Notation Cl + OCl- + 2H+

und diese: Clo + ClO- + 2H+

Ich hab jetzt also drei unterschiedliche Reaktionsgleichungen für die gleiche Reaktion vorliegen

Cl2 + 2 HO <-> Cl- + OCl- + 2H+
Cl2 + H2O <-> Cl- + ClO- + 2 H+
Cl2 + H2O <-> ClO- + O- + 1/2 H2

Da mir mein Dozent wahrscheinlich mit dem nackten Gesäß ins Gesicht springen würde, wenn ich ihm in der Klausur drei unterschiedliche Lösungen hinschreibe ("Bei mehreren Lösungen gilt die Aufgabe als nicht gelöst"). dachte ich, ich frag mal nach, was die richtige Antwort sein könnte.

Mit gräulichen Füßen,
JensErdkunde8.Klasse,1.Halbjahr

...zur Frage

Implikation -> erklärung für dummies

Ich bin gerade echt zu dumm um das was wir heute in der Algorithmen und Datenstrukturen Vorlesung gemacht haben richtig zu verstehen

Also, wieso kann man aus

x > 0

x > = 0

folgern

ich verstehe das nicht, wenn das x = 0 ist, dann wäre es doch oben falsch aber unten wahr, also würde man aus etwas falschem etwas wahres folgern, wie kann man sich das klar machen?

Das wäre so als würde ich sagen,

Es regnet nicht, also ist die Straße nass

das ergibt doch keinen sinn

wie lerne ich logisch zu denken ich bin zu blöd dafür

...zur Frage

O-Notation beispiele und Erklärung?

Hallo zusammen,

ich verstehe die O-Notation nicht genau, und wollte daher zu gegebenen Beispielen fragen, ob ich dies so richtig verstanden habe. Falls nicht, würde ich mich riesig über eine Erklärung freuen.

(Siehe Anhang)

Bei der ersten Aufgabe, ist es doch so, dass die Funktion höchstens so schnell wachsen darf, wie n hoch 7.

Wenn ich hier beispielsweise allerdings jegliche Zahl einsetze, so wächst es doch einwenig schneller als n hoch 7? So, dass dies nicht stimmen dürfte, oder?

Bei der zweiten Aufgabe darf die Funktion nur mindestens so schnell wachsen wie n hoch 7. Hier würde die Aussage doch zutreffen, da dies immer ein wenig höher ist, wenn man eine beliebe Zahl einsetzt, im Gegensatz zu n hoch 7, oder?

Bei der dritten Aufgabe darf die Funktion nur genau so schnell wachsen wie n quadrat.

Dies trifft allerdings nicht zu, oder?

Freue mich über jede Erklärung!

...zur Frage

Big O notation?

Wie löst man die obige Aufgabe. Habe mir jetzt ein paar Videos zum Thema angeschaut und kann ein paar Algorithmen analysieren. Bei obigem komme ich aber nicht weiter.

Beim ersten Algorithmus muss ich die Multiplikation ja jedes mal durchführen, während beim zweiten nur ein einziges mal am Ende multipliziert wird. Daher hätte ich gesagt:

Algorithmus O(n), da ich die Multiplikation jedes mal durchführen muss
Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Meine Fragen:

Ist die Analyse korrekt?
Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?
Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

...zur Frage

Wieso fällt dieser Test durch (Java)?

Hallo!

Im Rames des Moduls Algorithmen und Datenstrukturen, gibt es manchmal online so Programmieraufgaben. Da müssen wir dann einen Algorithmus mit einer vorgegebenen Laufzeit schreiben. Dieses sieht die Aufgabe so:

Hier mein Code dazu:

Mein Code dazu funktioniert auch. Nur fällt er bei einem Test durch und ich weiß nicht genau wie ich es deutet soll und was ich anpassen muss, damit er nicht durchfällt:

Mein Code sollte auch in O(n+m) laufen, denn die erste for-Schleife ist O(n) und die zweite O(m). In den Schleifen, passieren nur konstante Dinge. Der Test, welcher fehlschlägt erstellt zwei Random Arrays der Länge 9.500.000 und schaut sich an, ob es alles geklappt hat. Das ganze wird drei mal gemacht. Die Ausgabe Strings berechne ich auch richtig, was man an den drei ok's sehen kann. Aber trotzdem steht da dann irgendwas von Zeitbegrenzung überschritten...

Danke und LG

...zur Frage

Unterschied O(n) und T(n)?

Ich verstehe nicht, was der Unterschied zwischen der O-Notation und der asymptotischen Laufzeit ist. Beide beschreiben die Abhängigkeit der Laufzeit zur Problemgrösse und lassen uns die Algorithmen in verschieden Klassen einteilen, aber was ist der Unterschied?

...zur Frage

O-Notation Theta Beweis?

Hallo zusammen,

ich habe eine Verständnisfrage zur Aufgabe a und c (siehe Anhang).

Es ist ja so, dass bei a, im Grunde doch beides gleich schnell wächst, so dass wenn ich beispielsweise als konstante 999 wähle, dass 999 * n^7 / 2n^7 + 1000n^7 zu einer endlichen Zahl führt..

Laut der Definition, darf die Funktion nur höchstens so schnell wachsen wie n hoch 7, und da beide gleich schnell wachsen, trifft dies doch zu, oder?

Bei C habe ich nun aber das gleiche Ergebnis, hier ist es ja so, dass die Funktionnur gleich schnell wachsen darf, wie n quadrat, und auch hier trifft dies zu, da wenn ich beide dividiere, immer ein endliches Ergebnis dabei herauskommt, richtig?

Dementsprechend ist es doch so, dass beispielsweise die Aufgabe a, sowohl stimmen würde, wenn dort das O als auch das Theta (O mit einem Strich in der Mitte) stehen würde, oder?

Freue mich riesig über eine Erklärung!

Weiterhin muss ich solche Aufgaben wie im Anhang zu sehen, beweisen. Wie gehe ich da vor? Muss ich da einfach die Funktion durch g(n) teilen, und bestimmen, ob ein endlicher Wert rauskommt etc, oder es zu 0 führt, bei n gegen unendlich, und dementsprechend einordnen?

...zur Frage

Welche Definition von Konvergenz eignet sich für den Beweis?

Ich habe gerade einige Schwierigkeiten bei meinen Matheaufgaben. Ich soll beweisen, dass eine Folge konvergent ist. Für den konkreten Grenzwert interessiert man sich dabei nicht. Es reicht also theoretisch aus, zu zeigen, dass die Folge konvergent ist. Hingegen reicht es nicht aus, einen konkreten Grenzwert zu bestimmen. Hier müsste dann auch ein Beweis geführt werden, dass die Folge gegen diesen Grenzwert konvergiert.

Mir fehlt für diese Beweise momentan der grundlegende Ansatz. Ich versuche deshalb in der Formulierung "zu zeigen ist, dass die Folge konvergent ist" die Definition für Konvergenz einzusetzen, um so etwas "konkreter" werden zu können. Allerdings gibt es für Konvergenz ja mehrere Definitionen. Daneben haben wir in der Vorlesungen auch noch einige Aussagen gefunden, die äquivalent zu "die Folge ist konvergent" sind.

Mich würde deshalb interessieren, welche Definition ihr bei einer solchen Aufgabe benutzen würdet.

...zur Frage

Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen