Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
"Crashkurs" Landau-Notation ("groß-O")
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 130 Zeilen
- so und jetzt kommen wir nachdem wir zwei Vereinfachungen haben die erste Vereinfachung war unser komisches RAM Computermodell die zweite Vereinfachung
- ist dass wir uns nur den worstce angucken zur dritten Vereinfachung die geht auch gleich wieder mit einer Frage los wir haben ja
- eben schon gesehen bei unseren ganz simple Programm dass man da irgendwelche Formeln rausbekommt für die Laufzeit sowas wie 2n + C oder 3n oder sowas und
- natürlich wird bei größeren komplizierteren Programm eine kompliziertere Formel rauskommen also es könnte z.B sein dass hier ein Algor mus
- a haben bei dem die Formel für die Laufzeit 10 n hoch 4 + 12n + 8 Zeiteinheiten ist was immer das für zeiteinhalten sind und sie haben ein
- ander Algorithmus B bei dem die Formel für das Laufzeitverhalten 2 hoch n + 2n + 3 ist und welcher von den beiden hat denn das bessere Laufzeitverhalten würde
- ich von Ihnen gerne wissen also besser im Sinne von schneller natürlich ja also es sind sich nicht alle einig
- gewesen die richtige Antwort wäre die erste gewesen obwohl man darüber diskutieren kann ich sage Ihnen warum man darüber diskutieren kann also wenn
- wir A und B vergleichen habe ich hier schon mal ein paar Werte für n genommen stellen Sie sich vor das wären Sekunden Nanosekunden was immer Sie wollen wenn
- sie z.B n= 5 einsetzen dann bekommen sie beim ersten Algorithmus 6318 raus und hier bekommen Sie 45 raus
- also wenn sie angekreuzzt haben das habe ich ja auch das a besser ist dann könnte man sich an dieser Stelle jetzt fragen ist das wirklich besser ich habe hier
- Malin Vergleichsfaktor a im Vergleich zu B da bekommen sie raus ungefähr 0,01 das heißt der Algorithmus B braucht
- nur ungefähr 1% der Laufzeit von Algorithmus a sogar weniger glaube ich setzen sie mal 10 ein dann bekommen Sie hier
- 10028 raus und hier bekommen Sie 1047 raus Verhältnis immer noch ungefähr 0,01 Algorithmus B braucht nur ungefähr 1% der Laufzeit von Algorithmus a setzen
- Sie 20 ein dann bekommen sie beim linken Algorithmus 1000 16600248 raus beim rechten Algorithmus bekommen sie raus
- 1 48619 immer noch besser der rechte Algorithmus aber die Verhältnisse sind
- ein bisschen anders geworden wir haben jetzt nur noch einen deutlich geringeren Zeitgewinn wenn ich mir nicht verrechnet habe ist der Faktor jetzt 66% das heißt
- die Laufzeit des zweiten Algorithmus ist 66% der Zeit des ersten Algorithmus und jetzt setzen wir sie wissen ja schon was passiert setzen wir
- z.B mal 50 ein dann bekommen wir beim linken Algorithmus eine Laufzeit von ungefähr 8 Millionen und beim rechten Algorithmus bekommen wir sowas
- hier und diesmal ist der Faktor ungefähr 132,55 das heißt diesmal ist der Algorithmus rechts ungefähr 132 mal so langsam wie der Algorithmus Links
- das heißt äh wenn Sie kleine Inputs haben dann ist Algorithmus a gar nicht besser dann ist er schlechter wenn Sie große Inputs haben
- ist es so dass Algorithmus a deutlich besser ist einmal ist es nicht so völlig klar dass ein Algorithmus besser als der andere ist also eine Frage die ganz
- wesentlich ist ist für welche n interessiert mich das wir werden uns ganz grundsätzlich nur immer mit den großen n beschäftigen das
- heißt in diesem Fall wäre die Antwort für uns tatsächlich die gewesen das Algorithmus a besser ist aber Sie müssen natürlich dabei im Kopf behalten dass
- das erst ab einem bestimmten end eventuell gilt also das ist für kleine dass sie vielleicht ein ziemlich genialen Algorithmus schreiben mit dem
- sie sogar irgendwelche Preise gewinnen dass der aber für kleine Grafen z.B gar nicht so gut ist der ist erst dann richtig gut und zeigt seine
- Überlegenheit wenn er wenn er Grafen der Größe 50 oder mehr gefüttert bekommt und wie sie eben schon
- angesprochen haben äh wenn man solche Laufzeiten untersucht äh möchte man sich das Leben noch deutlich einfacher machen erstmal möchte
- man sich nicht mit solchen komplizierten Formeln hier befassen sie haben ja eben schon bei diesen ganz ganz simplen Dingen gesehen dass das viel zu viel
- Arbeit ist genau im Detail zu berechnen wie viel Schritte ein Algorithmus braucht was wir also eigentlich nachher wollen ist
- wir und das mal werden wir auch tun wir werden sagen dieses Ding hier hat im wesentlichen die Laufzeit n hoch 4 ja alles andere ist nicht so wichtig und
- bei diesem Algorithmus würden wir sagen der hat im wesentlichen die Laufzeit 2 hoch n und das ist das was wir im zweiten Semester in Matthe gemacht haben
- das ist die sogenannte Landau Notation oder auch groß oh
- Notation die ich jetzt eben in 5 Minuten noch mal wiederholen werde aber die werde ich natürlich jetzt nicht noch mal im Detail mit ihnen durchgehen also die
- Gr Idee ist die folgende
- Laufzeit eines Algorithmus ist eine Funktion von der Größe des Inputs also sowas hier damit ist gemeint Funktion der Größe des
- Inputs n ist irgendein Maß für die Größe des Inputs und FN ist die Funktion die Ihnen sagt im Detail wie lange der Algorithmus läuft das könnte sowas sein
- wie eben 10 x 1 ho 4 plus blablabla und was sie wollen ist statt F Vonn betrachten
- wir die Ordnung dieser Funktion und das ist das was man in der groß o Notation dann als großo von F von N
- bezeichnet und da sortiert man die in Kategorien ein S dass man auf der innerhalb dieser groß ooklammer möglich simple Ausdrücke bekommt also
- z.B würde man sagen Beispiel wenn wie eben F von N sowas wäre wie 10 hoch n +
- 4 3 qu + 7 was auch immer dann würden wir sagen F von N ist aus o von N hoch 4 und wir würden dann später sagen der Algorithmus ist von der Ordnung n hat
- ein Laufzeit von der Ordnung n hoch 4 das bedeutet der verhält sich im großen und ganzen so wie als wenn die Laufzeit N4 wäre alles andere sind unwichtige
- Details und die unwichtigen Details noch mal zur Erinnerung wir brauchen eigentlich nur drei Dinge
- erstens konstante Faktoren spielen keine Rolle das bedeutet diese 10 hier das ist ein konstanter Faktor 10 x 4 ist von der
- Ordnung her daselbe wie N 4 wenn wir wieder bei realistisch versus unrealistisch sind ist natürlich das wieder ein Punkt wo man drüber schreiten
- kann also in der Praxis spielt es natürlich eine Rolle wenn sie ihr Algorithmus Zeh mal so schnell machen können dann werden sie jubeln aber für
- theoretische Untersuchung spielt das keine besondere Rolle weil tatsächlich auch ganz pragmatisch betrachtet wenn es solche Faktoren gibt die meistens
- relativ klein sind und weil die wenn n groß genug ist sowieso immer wieder aufgefressen werden also spielt keine
- Rolle Zite wichtige Regel beim Rechnen mit dieser landnotation wenn ich zwei Funktionen addiere dann muss ich im Prinzip nur das Maximum ausrechnen also
- das größere von beiden also ich schreib das mal so als merkregel hin addition gleich
- maximum das bedeutet ja immer höherwertiger als alle anderens die mit richtigen Zahl beschrieben sind
- ja also der Unterschied ist ja dass N einmal unten ist ist die Basis einmal ist der Exponent wenn das n unten ist nennt man es Polynom wenn es oben ist
- nennt man es Exponentialfunktion und die sind immer haben deutlich schlechteres Laufzeitverhalten solange die Basis unten größer als eins ist natürlich wenn
- sie jetzt sowas haben wie 0,5 hoch n und so dann natürlich nicht aber das gibt's in der Realität nicht also addition ist gleich maximum
- bedeutet wenn ich zwei Funktionen zusammenzähle dann ist die Ordnung von den beiden einfach die größere der beiden Ordnungen das bedeutet für unsere
- Analyse von Programmen wenn Sie zwei Programmteile hintereinander haben die unterschiedliche Laufzeiten haben die werden nacheinander ausgeführt dann ist
- für die Laufzeit Ihres Programms eigentlich nur der langsamere Teil relevant den den schnelleren Teil können sie weglassen also typischerweise bei
- komplizierten Problemen haben sie am Anfang sowas wie Aufbau der Datenstruktur und dann das eigentliche Programm der eigentliche Algorithmus und
- normalerweise können Sie den Aufbau der Datenstruktur eigentlich weg einfach weglassen es sei denn der Aufbau der Datenstruktur ist komplizierter als der
- sowas gibt auch aber grundsätzliche Regel wenn ich mehrere Sachen nacheinander ausführe ist für das Laufzeitverhalten nur wichtig welcher
- von den Teilen braucht am längsten und die dritte Regel die wir noch brauchen die schreibe ich mal ganz flapsig so hin
- Multiplikation ist Multiplikation da gibt's nicht so eine schöne Vereinfachung also die Ordnung
- multiplizieren sich wenn ich ein wenn ich etwas habe und wann wann kommt überhaupt Multiplikation vor bei der Betrachtung von Algorithmen wenn ich
- Schleifen habe Multiplikation kommt nur dann vor wenn es irgendwelche Form von Wiederholung gibt ich habe einen Teil des Algorithmus von dem weiß ich wie
- lange er braucht zumindest von der Ordnung her und ich weiß wie oft er wiederholt wird auch zumindest von der Ordnung her und insgesamt habe ich dann
- die Anzahl der Wiederholung mal die Dauer eines einzelnen Schrittes also Ordnung mal Ordnung und da ist es leider so dass ich die Ordnung tatsächlich
- multiplizieren das wäre zu schön wenn das auch nur das Maximum wäre aber durch Schleifen werden Programme eigentlich gerade langsam also vielleicht schreibe
- ich noch mal ein Klammern dahinter ADITION bedeutet eigentlich hintereinander ausführen hintereinander
- ausführen und Schleifen bedeutet also Multiplikation bedeutet Schleifen also Wiederholung ja das sind die
- wesentlichen in Häkchen Rechenregeln die wir haben und jetzt für konkrete Fälle vielleicht noch ein paar Dinge sie haben das eben schon angesprochen
- äh die Ordnung von Polynom ist die des höchsten
- monoms Beispiel wenn ich sowas habe wie 7 mal n hoch 3 + 8 n² - 42 wenn das
- Maline Laufzeit ist dann ist das höchste monom was hier vorkommt n hoch 3 monomen sind ja immer solche Polynome ohne Koeffizienten davor mit nur einer
- einzigen Potenz also hier ist einfach ganz simple Regel da braucht man überhaupt nicht zu rechnen oder nachzudenken Sie nehmen einfach den
- höchsten term der hier vorkommt das ist die Ordnung von dem Ding weil das zählt nach unseren Regeln vorher erstmal haben Sie hier eine Addition von mehreren
- Termen bei addition zählt nur das max darum ist der höchste term 7 mal n 3 und die die erste Regel die da oben mit dem Fall steht ist konstante Faktoren
- spielen keine Rolle also die 7 spielt keine Rolle darum kommt hier n 3 raus also Ordnung von Polynomen ist die des höchsten
- monoms dann noch etwas was öfter vorkommt was bedeutet o von 1 ja konstante genau das heißt konstante mit anderen Worten die Laufzeit hängt
- nicht von N ab das ist so ein Programm wie hello world was immer dasselbe macht egal was Sie eingeben das ist eine konstante
- Laufzeit oder sowas wie in unseren Beispiel die wir eben hatten eine primitive Operation addition was auch immer zählen wir als on 1 darum ist es
- im Nachhinein auch keine große Einschränkung dass wir bei unserem RAM Modell gesagt haben alle Operationen dauern gleich lange denn
- wenn sie alle nicht gich lange dauern würden würden wir im Endeffekt sowieso sagen die sind alle o von 1 also spielt dann sowieso keine Rolle mehr also
- konstante Laufzeit hängt nicht von N ab ja und äh jetzt zu den Polynom und
- Exponentialfunktionen n hoch K ist groß o von N hoch m wenn
- K kleiner gleich m also wenn ich den Exponenten höher mache dann ist natürlich das eine sozusagen höchstens so schnell wie das
- andere das ist glaube ich klar ich muss aber dazu schreiben nicht umgekehrt also also z.B n hooch 2 ist groß o von N hoch 7 aber n 7 ist nicht
- groß o von N 2 das bedeutet n hooch 7 ist tatsächlich schlechter als N2 die sind nicht gleich das gleiche gilt für
- Exponentialfunktion a hoch n ist groß o von B hoch n wenn erstmal die beiden Werte sowieso
- größer als ein sind und wenn B mindestens so groß wie A ist aber auch hier gilt nicht
- umgekehrt das bedeutet sowas wie 2 hoch n hat ein besseres Laufzeitverhalten als 3 hoch n aber nicht umgekehrt 3 hoch n ist
- tatsächlich schlechter als 2 hoch n und die allerletzte Regel noch der Zusammenhang zwischen Polynom und Exponentialfunktion n hoch
- K ist groß o von A hoch n wenn A gröer 1 völlig unabhängig davon was K ist und was a ist also jedes Polynom ist
- langsamer äh ist äh von der Laufzeit her schneller als jede Exponentialfunktion und auch hier nicht umgekehrt also das bedeutet z.B n hoch 3
- ist groß o von 2 hoch n aber 2 hoch n ist nicht groß o von N hoch 3 ne auch hier kann man nicht umdrehen
- wenn Sie diese paar Regeln die ich i aufgeschrieben habe verinnerlichen für das Rechnen mit landymbolen haben Sie eigentlich alles was man braucht das
- einzige was vielleicht noch hinzu kommt später ist der Logarithmus über den reden wir dann noch mal aber das ist erstmal so das Wesentliche
- m hier könnte man jetzt auch wieder über realistisch oder nicht realistisch reden speziell was diese letzte Regel hier angeht diese letzte Regel besagt ja
- unter anderem äh n hoch 1000 ist groß o von 1,01 hoch n das
- bedeutet nach unserer Betrachtungsweise wäre es so dass wir von einem Algorithmus der das Laufzeitverhalten n 1000 hat sagen würden der ist besser als
- dieser Algorithmus hier wenn sie da jetzt aber wirklich mal Werte für n einsetzen werden Sie sehen bis sie tatsächlich mal so weit kommen dass
- dieser Algorithmus den anderen überholt in der Laufzeit müssen sie extrem große n einsetzen also natürlich ist auch hier wieder ein bisschen fehlender Realismus
- zu bemäeln aber da kann man als wirklich sehr überzeugende Entschuldigung bringen sowas gibt's in der Realität nicht es
- gibt keine n hoch 1000 Algorithmen hat noch nie jemand gesehen und genauso wenig gibt es irgendwelche 1,01 hoch n Algorithmen obwohl man das vielleicht
- gerne hätte in der Realität hat man es zu tun mit solchen Dingen wie n hoch 3 N hoch 7 oder sowas wie 2 hoch n oder 1,9 hoch n vielleicht noch mal und in diesen
- Fällen ist es tatsächlich so dass dummerweise die Exponentialfunktionen auch unter ganz pragmatischen Gesichtspunkten einfach schlechter sind
- als die Polynome so jetzt noch eine kurze Übung dazu zum Auffrischen des Gedächtnisses und gleich mal ein bisschen schwieriger
- also ich möchte von Ihnen wissen in welchen Fällen ist die Aussage wahr und bestmöglich also so dass ich da nicht noch eine bessere Abschätzung
- hinschreiben kann denn wir wollen natürlich wenn wir später Algorithmen beurteilen nicht nur sagen sowas wie natürlich ist n Quadrat aus Groß o von N
- hoch 7 aber das ist keine scharfe Abschätzung ne ich möchte irgendwas besseres haben möglichst die kleinste Schranke und darum möchte ich von Ihnen
- hier nicht nur die nicht die angekrotzt haben die Stimmen sondern ich möchte die angekotzt haben die Stimmen und auch scharf sind hier oben haben wir
- zwei Fälle zweimal dasselbe Polynom das stimmt natürlich beides das ist groß o von N Quadrat und groß von N hoch 3 aber natürlich ist groß von N 3 eine zu grobe
- Abschätzung weil die richtige Abschätzung groß von N quadr ist bei denen hier ist es so dass das hier oben das erste nicht stimmt 3 hoch n das ist
- ja der dominante Teil von dem Ding hier ist nicht groß von 2 hoch n ja aber hier das stimmt 3 hoch n der Rest fällt weg ist groß von 3 hoch n das danach stimmt
- auch aber das ist nicht die schärfst mögliche Abschätzung weil diese ja besser ist dieses hier ist schwierig wobei das nicht so schwierig
- ist der dominante Teil ist offensichtlich dieser term hier vorne und ich hatte ihn ja schon gesagt Multiplikation ist Multiplikation das
- heißt dieses Ding hier ist groß o von N hooch 4 x 2 hoch n und nicht groß o von 2 hoch n das ist tatsächlich mehr ja die Frage ist was hiermit ist und da
- müssten sie jetzt wirklich rechnen sie müssten mal also die hier hinten können sie weglassen aber sie müssten diesen Term hier vorne durch 2,1 hoch n
- dividieren und dann gucken was da für ein Term rauskommt und sie werden sehen dass da ein Term rauskommt der gegen Null geht das heißt das was hier steht
- stimmt überraschenderweise ist dieses hier tatsächlich groß von 2,1 hoch n aber das ist nicht die beste Abschätzung also die ist richtig aber nicht die
- beste also wenn sie um in solche gemischten Terme reinkommen ist es im allgemeinen ein bisschen schwieriger wir werden die einfach in der Form schreiben
- n hoch 4 x 2 hoch n das ist eigentlich auch das Beste was man sauber hinschreiben kann was uns einfach zeigt dass es noch schlechter als
- Exponentialfunktion aber es gibt sozusagen Exponentialfunktionen die ein bisschen höher sind und die das wieder auffressen also eigentlich ist
- sowas wie n 4 x 2 hoch n exponentielles Wachstum nur dass die Basis nicht stimmt so ich will nur noch mal zusammenfassen jetzt haben wir alles erreicht was wir
- uns vorgenommen haben an Vereinfachung das war hier wir hatten gesagt wir möchten drei Dinge bei der Analyse von Algorithmen vereinfachen
- erstens wir wollen technische Details ignorieren das heißt wir haben jetzt ein ein abstraktes Computermodell indem wir uns über Details überhaupt keine
- Gedanken machen der Speicher ist umsonst jeder Schritt dauert eine Zeiteinheit wer wird im Pseudocode programmiert ganz simpel das ist unser RAM zweite
- Vereinfachung wir werden die meisten möglichen Inputs ignorieren das heißt wir konzentrieren uns immer auf den worst case was ist das schlimmste was
- passieren kann und dritte Vereinfachung die Laufzeit wird nur grob geschätzt das heißt wir werden in Zukunft nur in Groß o denken wir werden nur noch sagen das
- ist groß o von N quadr oder so und werden nicht mehr äh im Detail sagen das ist NH4 plus blabla bla das interessiert uns dann alles nicht
Zum Nachlesen
Landau-SymboleLandau-Symbole (auch O-Notation, englisch big O notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von …
Laufzeit (Informatik)Der Begriff Laufzeit (englisch runtime) beschreibt in der Informatik einerseits die Zeitdauer, die ein Programm, ausgeführt durch einen Rechner, …
Effizienz (Informatik)Die Effizienz eines Algorithmus ist seine Sparsamkeit bezüglich Ressourcen, Rechenzeit und Speicherplatz, die jener zur Lösung eines festgelegten Problems …
ZeitkomplexitätUnter der Zeitkomplexität wird in der Informatik die Anzahl der ... Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet …