"Crashkurs" Landau-Notation ("groß-O")
Weitz / HAW Hamburg
https://www.youtube.com/watch?v=IxqZtYQqDCI

Transkript (automatisch erstellt)

0:00 so und jetzt kommen wir nachdem wir zwei Vereinfachungen haben die erste Vereinfachung war unser komisches RAM Computermodell die zweite Vereinfachung
0:07 ist dass wir uns nur den worstce angucken zur dritten Vereinfachung die geht auch gleich wieder mit einer Frage los wir haben ja
0:14 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
0:23 natürlich wird bei größeren komplizierteren Programm eine kompliziertere Formel rauskommen also es könnte z.B sein dass hier ein Algor mus
0:30 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
0:39 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
0:48 ich von Ihnen gerne wissen also besser im Sinne von schneller natürlich ja also es sind sich nicht alle einig
0:55 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
1:04 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
1:10 sie z.B n= 5 einsetzen dann bekommen sie beim ersten Algorithmus 6318 raus und hier bekommen Sie 45 raus
1:20 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
1:27 Malin Vergleichsfaktor a im Vergleich zu B da bekommen sie raus ungefähr 0,01 das heißt der Algorithmus B braucht
1:37 nur ungefähr 1% der Laufzeit von Algorithmus a sogar weniger glaube ich setzen sie mal 10 ein dann bekommen Sie hier
1:46 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
1:59 Sie 20 ein dann bekommen sie beim linken Algorithmus 1000 16600248 raus beim rechten Algorithmus bekommen sie raus
2:10 1 48619 immer noch besser der rechte Algorithmus aber die Verhältnisse sind
2:17 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
2:27 die Laufzeit des zweiten Algorithmus ist 66% der Zeit des ersten Algorithmus und jetzt setzen wir sie wissen ja schon was passiert setzen wir
2:34 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
2:48 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
3:00 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
3:09 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
3:16 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
3:25 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
3:32 das erst ab einem bestimmten end eventuell gilt also das ist für kleine dass sie vielleicht ein ziemlich genialen Algorithmus schreiben mit dem
3:39 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
3:46 Überlegenheit wenn er wenn er Grafen der Größe 50 oder mehr gefüttert bekommt und wie sie eben schon
3:54 angesprochen haben äh wenn man solche Laufzeiten untersucht äh möchte man sich das Leben noch deutlich einfacher machen erstmal möchte
4:03 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
4:11 Arbeit ist genau im Detail zu berechnen wie viel Schritte ein Algorithmus braucht was wir also eigentlich nachher wollen ist
4:19 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
4:27 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
4:34 das ist die sogenannte Landau Notation oder auch groß oh
4:50 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
4:59 Gr Idee ist die folgende
5:06 Laufzeit eines Algorithmus ist eine Funktion von der Größe des Inputs also sowas hier damit ist gemeint Funktion der Größe des
5:25 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
5:34 wie eben 10 x 1 ho 4 plus blablabla und was sie wollen ist statt F Vonn betrachten
5:49 wir die Ordnung dieser Funktion und das ist das was man in der groß o Notation dann als großo von F von N
6:07 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
6:16 z.B würde man sagen Beispiel wenn wie eben F von N sowas wäre wie 10 hoch n +
6:27 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
6:45 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
6:53 Details und die unwichtigen Details noch mal zur Erinnerung wir brauchen eigentlich nur drei Dinge
7:02 erstens konstante Faktoren spielen keine Rolle das bedeutet diese 10 hier das ist ein konstanter Faktor 10 x 4 ist von der
7:22 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
7:32 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
7:39 theoretische Untersuchung spielt das keine besondere Rolle weil tatsächlich auch ganz pragmatisch betrachtet wenn es solche Faktoren gibt die meistens
7:46 relativ klein sind und weil die wenn n groß genug ist sowieso immer wieder aufgefressen werden also spielt keine
7:58 Rolle Zite wichtige Regel beim Rechnen mit dieser landnotation wenn ich zwei Funktionen addiere dann muss ich im Prinzip nur das Maximum ausrechnen also
8:07 das größere von beiden also ich schreib das mal so als merkregel hin addition gleich
8:19 maximum das bedeutet ja immer höherwertiger als alle anderens die mit richtigen Zahl beschrieben sind
8:29 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
8:36 nennt man es Exponentialfunktion und die sind immer haben deutlich schlechteres Laufzeitverhalten solange die Basis unten größer als eins ist natürlich wenn
8:44 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
8:52 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
9:00 Analyse von Programmen wenn Sie zwei Programmteile hintereinander haben die unterschiedliche Laufzeiten haben die werden nacheinander ausgeführt dann ist
9:08 für die Laufzeit Ihres Programms eigentlich nur der langsamere Teil relevant den den schnelleren Teil können sie weglassen also typischerweise bei
9:16 komplizierten Problemen haben sie am Anfang sowas wie Aufbau der Datenstruktur und dann das eigentliche Programm der eigentliche Algorithmus und
9:22 normalerweise können Sie den Aufbau der Datenstruktur eigentlich weg einfach weglassen es sei denn der Aufbau der Datenstruktur ist komplizierter als der
9:29 sowas gibt auch aber grundsätzliche Regel wenn ich mehrere Sachen nacheinander ausführe ist für das Laufzeitverhalten nur wichtig welcher
9:36 von den Teilen braucht am längsten und die dritte Regel die wir noch brauchen die schreibe ich mal ganz flapsig so hin
9:47 Multiplikation ist Multiplikation da gibt's nicht so eine schöne Vereinfachung also die Ordnung
9:55 multiplizieren sich wenn ich ein wenn ich etwas habe und wann wann kommt überhaupt Multiplikation vor bei der Betrachtung von Algorithmen wenn ich
10:03 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
10:10 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
10:18 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
10:26 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
10:35 ich noch mal ein Klammern dahinter ADITION bedeutet eigentlich hintereinander ausführen hintereinander
10:45 ausführen und Schleifen bedeutet also Multiplikation bedeutet Schleifen also Wiederholung ja das sind die
10:55 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
11:03 äh die Ordnung von Polynom ist die des höchsten
11:21 monoms Beispiel wenn ich sowas habe wie 7 mal n hoch 3 + 8 n² - 42 wenn das
11:33 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
11:41 einzigen Potenz also hier ist einfach ganz simple Regel da braucht man überhaupt nicht zu rechnen oder nachzudenken Sie nehmen einfach den
11:48 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
11:57 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
12:05 spielen keine Rolle also die 7 spielt keine Rolle darum kommt hier n 3 raus also Ordnung von Polynomen ist die des höchsten
12:12 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
12:30 nicht von N ab das ist so ein Programm wie hello world was immer dasselbe macht egal was Sie eingeben das ist eine konstante
12:40 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
12:50 im Nachhinein auch keine große Einschränkung dass wir bei unserem RAM Modell gesagt haben alle Operationen dauern gleich lange denn
12:58 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
13:04 konstante Laufzeit hängt nicht von N ab ja und äh jetzt zu den Polynom und
13:27 Exponentialfunktionen n hoch K ist groß o von N hoch m wenn
13:37 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
13:46 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
14:03 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
14:12 Exponentialfunktion a hoch n ist groß o von B hoch n wenn erstmal die beiden Werte sowieso
14:23 größer als ein sind und wenn B mindestens so groß wie A ist aber auch hier gilt nicht
14:35 umgekehrt das bedeutet sowas wie 2 hoch n hat ein besseres Laufzeitverhalten als 3 hoch n aber nicht umgekehrt 3 hoch n ist
14:45 tatsächlich schlechter als 2 hoch n und die allerletzte Regel noch der Zusammenhang zwischen Polynom und Exponentialfunktion n hoch
14:53 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
15:11 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
15:23 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
15:32 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
15:38 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
15:45 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
15:55 unter anderem äh n hoch 1000 ist groß o von 1,01 hoch n das
16:07 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
16:15 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
16:23 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
16:31 zu bemäeln aber da kann man als wirklich sehr überzeugende Entschuldigung bringen sowas gibt's in der Realität nicht es
16:39 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
16:47 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
16:58 Fällen ist es tatsächlich so dass dummerweise die Exponentialfunktionen auch unter ganz pragmatischen Gesichtspunkten einfach schlechter sind
17:05 als die Polynome so jetzt noch eine kurze Übung dazu zum Auffrischen des Gedächtnisses und gleich mal ein bisschen schwieriger
17:15 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
17:23 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
17:32 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
17:39 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
17:48 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
17:58 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
18:08 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
18:20 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
18:29 ist der dominante Teil ist offensichtlich dieser term hier vorne und ich hatte ihn ja schon gesagt Multiplikation ist Multiplikation das
18:36 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
18:47 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
18:55 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
19:02 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
19:11 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
19:19 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
19:27 Exponentialfunktion aber es gibt sozusagen Exponentialfunktionen die ein bisschen höher sind und die das wieder auffressen also eigentlich ist
19:35 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
19:46 uns vorgenommen haben an Vereinfachung das war hier wir hatten gesagt wir möchten drei Dinge bei der Analyse von Algorithmen vereinfachen
19:55 erstens wir wollen technische Details ignorieren das heißt wir haben jetzt ein ein abstraktes Computermodell indem wir uns über Details überhaupt keine
20:02 Gedanken machen der Speicher ist umsonst jeder Schritt dauert eine Zeiteinheit wer wird im Pseudocode programmiert ganz simpel das ist unser RAM zweite
20:10 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
20:17 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
20:26 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