In diesem Screencast demonstriert euch Prof. Dr. Oliver S. Lazar die Bedeutung der Zeitkomplexität für Algorithmen und die Einordnung in Komplexitätsklassen, welche mit der O-Notation angegeben werden können.
Hi, erstmal vielen Dank für deine Zeit! Super gut erklärt, doch stellt sich mir eine Frage auf. Ich schreibe demnächst eine Klausur in Algorithmen und Datenstrukturen, in der die Groß O Notation natürlich auch durchgenommen wird. Könntest du vielleicht genauer drauf eingehen (am besten mathematisch) wie du auf die Konstante C und den N wert gekommen bist? Ich muss es nämlich mathematisch zeigen. Zur Verdeutlichung eine Aufgabe:
C1* G(x) >= f(x)
3n^2 -5n + 7 // Professor setzt -5n = 0, da n<=0;
f(n)= 3n^2 + 7 für n>=0; // Wieso wird hier die Grenze auf 0 gelegt ?
f(n)= 3n^2 + 7n^2 für n>=1 // Da n^2 die höchste Komplexitätsklasse setzen wir die ganze Gleichung auf n^2, soweit verstanden. Aber woran erkenne ich, dass ich hier n>=1 setzen muss?
Daraus folgt 10n^2 => f(n)=o(n^2)
und c1 = 10 ;
Das gleiche wird natürlich auch für die untere Grenze im Anschluss gemacht.
Meine Frage ist nun, wie man auf so eine Rechnung kommt, da ich dies nicht 100% nachvollziehen kann..
Hoffe, dass du das beantworten kannst
meinkanalize
Hat mir sehr gut gefallen. Ich lerne gerade Datenstrukturen 1, und bevor ich das Skript durcharbeite, schau ich mir doch lieber erstmal so ein video an. Das lesen fällt dann gleich viel leichter.
