O-Notation (Landau-Symbolik)
NLogSpace
https://www.youtube.com/watch?v=LVP3jXQR_0M

Transkript (automatisch erstellt)

0:00 hallo und herzlich willkommen zu diesem video ich möchte diesem video erklären was die großen rotation ist oder auch landau
0:08 symbolik genannt und das ist eigentlich ein relativ allgemein das thema ist also diese rotation ist in der mathematik universell zu finden das bezieht sich
0:18 nicht nur auf theoretische informatik deswegen dachte ich mir füge ich dieses video nicht irgendwie in eine serie ein sondern macht das als ein
0:26 alleinstehendes video und jeder der sich irgendwie für die rotation interessiert kann dieses video völlig ohne vorwissen einfach ansehen
0:34 ok also was ist diese große rotation mit der großen rotation beschreibt man wie schnell eine funktion wächst ja machen ein kleines beispiel also es geht in
0:47 erster linie darum das wachstum einer funktion so ungefähr zu beschreiben in diesem fall wenn wir diese funktion hätten eher von einem gleich drei ein
0:54 quadrat + 5 + 17 dann würde man also man interessiert sich eigentlich gar nicht dafür je + 5 + 17 oder so denn das in sachen die tragen
1:05 nicht so viel zum wachstum dieser funktion bei und fragt sich was trägt eigentlich zum wachstum dieser funktion ausschlaggebend bei und das ist
1:13 eigentlich nur diese cent quadrat hier vorne ja und man sagt nicht mal dieser faktor 3 hier vorne interessiert ein man möchte eigentlich sagen diese
1:21 funktion her die wächst quadratisch die wächst ungefähr so schnell wie ein quadrat möchte man sagen das heißt wo man am ende hin möchte das
1:31 ist dass man sagt es ist eine funktion die wächst von quadrat hier möchte man also hin und formal wird es dann so sein opa nennen quadrat ist
1:42 einfach eine menge von funktionen und dann kann man sagen es ist in dieser menge denn in dieser menge von m ² da sollen alle funktionen seien die
1:53 höchstens ungefähr so schnell wachsen wie ein quadrat und wir sagen diese funktion hier gehört dazu uns interessiert nicht wenn irgendwelche
2:01 sachen sind die langsamer als in quadrath noch wachsen und uns interessieren auch keine konstanten faktoren ja das ist so die grundidee bei
2:09 der notation möchte jetzt gleich einmal die formale definition von der rotation durchgehen und erklären und dabei muss ich aber
2:18 noch auf eine sache eingehen und zwar dieses ofen quadrat was hier eigentlich drin stehen muss also wenn man schreibt ja von irgendetwas dann muss da drin
2:29 eigentlich eine funktion stehen und man sagt dann ruf von dieser funktion das ist die menge aller funktionen die höchstens so schnell wachsen wie diese
2:39 funktion die ich hier drin steht ja also eigentlich muss hier irgendeine funktion sagen wir mal drin stehen ja und das soll dann die menge aller funktionen
2:48 werden die höchsten zu schnell wachsen wie h hier stand aber jetzt ende quadrat da drin und ein quadrat ist streng genommen eigentlich nur so tanja es ist
2:58 keine funktion aber es ist so es hat sich so eingebürgert dass man sagt wenn man nur schreibt m ² dann meint man damit eigentlich die funktion die enev
3:09 in quadrath april also was soll man auch sonst mit mir hin ja aber das nur als klärung also eigentlich muss man immer schreiben von einer funktion und dann
3:19 wäre hier die funktion gemeint die jede zahl auf ihr quadrat abbildet ist halt so eine kurz schreibweise ok gucken wir uns jetzt mal wirklich die formale
3:29 definition von der rotation an und ich mache die aber schritt für schritt also ich schreibe nicht komplett hin sondern ich mache erstmal naiven ansatz und dann
3:37 werden wir sie noch stück für stück verbessern sage ich mal ja aber erstmal wir wollen ja oh von f definieren yahoo von f und da sagen wir
3:47 es erst mal irgendeine funktion sein okay also sagen wir es ist irgendeine funktionen machen wir einfach jetzt aber mal natürliche zahl nach natürlichen
3:56 zahlen weil wir wenn wir informatiker sind dann denken wir im hinterkopf immer an laufzeiten von algorithmen und die nehmen natürlich nur natürliche zahl
4:06 entgegen aber das könnte genauso gut von reellen zahlen reale zahl sein macht keinen unterschied ja okay also wenn er für und
4:15 so eine funktion ist wir wollen jetzt definieren was es von f und wir wollen so dass unsere unser ziel ist es dass die menge aller
4:23 nun wird die höchstens so schnell wie f wachsen da könnte man erstmal ganz naiv sagen okay das sind einfach alle funktionen
4:30 deren werte einfach immer kleiner sind als wer also ist die menge aller funktionen gehe die auch natürliche zahlen auf natürliche zahn abbilden
4:40 für die gilt gehe von n immer kleiner ist als er von den ja so geht von n kleiner gleich kann man sagen er von n für alle natürlichen zahlen nennen so
4:51 könnte man erstmal anfangen und man konnte auf jeden fall auch sagen ja alle solche funktionen die sollen ja auf jeden fall nur von f trends die die
4:59 wachsen ja offensichtlich höchstens so schnell wie f wenn der unwerte immer kleiner sind als fern gucken uns mal ein beispiel grafisch davon an
5:07 hier sehen wir mal zwei funktionen das eine ist 000 5x quadrat die blaue und das andere ist 0,016 quadrat +10 ja und wir sehen also ich meine wir sehen erst
5:21 mal offensichtlich die grüne ist immer größer als die blaue oder anders gesagt wenn das grün ist jetzt unser f und das blaue ist unser ghg von n ist immer
5:32 kleiner als er von m und das wenn man das nicht glaubt aus dem bild man kann es natürlich auch beweisen indem man hier diese ungleichen
5:41 zeigt er für jedes für jede zeit für iks einsetzt ist das grüne dass man beim grünen rauskommt immer größer als das was man beim blauen rausbekommt okay
5:53 aber das ist noch nicht alles was man will wir gucken uns mal ein bisschen anderes beispiel an das war habe ich die blaue
5:58 kurve jetzt mal hier verändert und zwar ich gesagt dass es 30 plus 0,03 iks quadrat und dann sieht die so aus vielleicht erstmal nur das bild wichtig
6:09 ja dann wenn wir uns das bild angucken und vor allem wenn wir ein bisschen raus zogen dann sehen will er die blaue dies immer kleiner als die grüne außer auf so
6:18 einem anfangs stück hier aber sind anfangs stück interessiert einen eigentlich nicht denn man will ja das wachstum der funktion insgesamt
6:27 betrachten eine funktion hat unendlich viel werte man interessiert sich vor allem wie verhält sich die funktion auf dauer ja ist sie auf dauer
6:35 ist das wachstum auf dauer höchstens so wie das von der grünen ja und das ist der fall denn es gibt irgendeinem punkt ab dem die funktion
6:45 immer kleiner gleich der grünen ist ja hier könnte man zum beispiel sagen ab 60 jahre oder sogar hier ab wir sogar angezeigt 53 oder so hab da ist die
6:56 blaue immer kleiner gleich der grünen und auch in dem fall wollen wir dann sagen die blaue ist in der grünen kurve ja obwohl sich hier größer ist sagen wir
7:06 trotzdem die s immo von der grünen kurve denn es gibt einen punkt ab dem die blaue immer kleiner ist versuchen wir das mal zu unserer definition noch
7:14 hinzuzufügen also wir sagen nicht dass das diese funktion gehe überall kleiner sein muss als erster kleiner gleich sondern es
7:25 reicht wenn sie aber irgendeinem punkt immer kleiner gleich sagen jetzt dass die menge aller funktionen so dass du eine zahl existiert großen es eben zum
7:36 beispiel unsere zahl 60 war und gehe von end kleiner gleich elf von n das fordern wir jetzt nicht mehr für alle natürlichen zahlen sondern nur für
7:45 alle die größer gleich dass menden sind ja wenn wir irgend so eine grenze wählen können dann ist geht auch in f in dem fall
7:55 können wir so eine grenze will zum beispiel die 60 deswegen ist die blaue in u von der grünen kurve okay das ist aber immer noch nicht alles ich hatte am
8:06 anfang auch davon gesprochen dass uns auch konstante faktoren nicht interessieren bei der notation das heißt es ist uns egal
8:14 zum beispiel diese weiß nicht was hatten wir da zweimal en quadrat da sagen wir auch das suv quadrat ja so ein konstanter faktor interessiert uns
8:24 also nicht gucken uns das mal bildlich an wir hatten hier eben gesagt die blaue ist von der grüne
8:31 ja aber es ist auch umgekehrt so die grüne ist auch von der blauen kurve denn wenn wir die blaue einfach mit einer bestimmten konstante multiplizieren
8:42 dann ist auf einmal die blaue immer größer als die grüne ja was für eine konstante können man hier nehmen das würde hier zum beispiel faktor 4
8:49 gegen das ist mal ein bisschen raus suchen damit für das sehen wenn wir die blaue kurve mit faktor vier multiplizieren und genau das habe ich
8:57 gemacht hier steht genau die blaue kurve mit einer konstanten produziert nämlich mehr 4 dann sehen wir diese lila kuh wie ist
9:07 das dann also die die lange ist jetzt die blaue mal 4 dann sehen wir die ist immer größer als die grüne und das könnte man jetzt auch
9:16 ausrechnen ja man kann ausrechnen wenn man hier irgendeine zahl iks einsetzt in die lieder dann trägt man immer was
9:22 größeres haus als bei der grünen und deswegen ist die grüne auch von der blauen denn man kann die blaue mit einer konstanten multiplizieren so dass die
9:32 grüne kleiner gleich der blauen ist das heißt aus notation sicht wie man eigentlich sagen die blaue und die grüne die sind sind gleich sozusagen ja den
9:41 die wachsen gleich schnell zum beispiel wo das nicht so gewesen wäre also wo die eine wirklich schneller wächst als die andere ist wenn wir jetzt hier sage ich
9:50 mal bei der blauen geschrieben hätte nix hoch drei die blau ist jetzt ein problem dritten grades die grünen polo zweiten grades
9:58 und da kann man sich überlegen man kann die grüne multiplizieren wie man will ja wenn man die mit irgendeiner konstanten zahlen multiplizieren wir schaffen es
10:09 niemals die blaue auf dauer zu überholen wenn ich zum beispiel hier die schwarze kurve die ist jetzt das zehnfache von der grünen ja denkt man vielleicht erst
10:19 mal wächst die schneller aber nein die blaue überholt die irgendwann ja und hätten wir das elffache gemacht dann passiert das halt
10:28 erst ein bisschen später oder das fünfzehnfache dann passiert es halt noch ein bisschen später aber die blaue gewinnt immer das kann man sich
10:35 überlegen denn die blaue ist ein problem dritten grades die grünen nur ein polyp zweiten grades und dementsprechend die schwarze auch
10:42 zweiten grades und dann wird das plenum dritten grades immer auf dauer gewinnen ja also in dem fall ist jetzt die grüne euro von der blauen denn die grüne
10:53 wächst höchstens so schnell wie die blaue aber nicht umgekehrt die blaue ist nicht so von der grün kurve so aber das müssen wir jetzt immer
11:00 noch in unsere definition ein arbeiten mit dieser konstanten wollen auch noch sagen muss gar nicht kleiner gleich f sein sondern es reicht wenn die kleiner
11:10 ist als f wenn man es mit irgendeiner konstanten multipliziert aber wir sagen auch noch soll eine zahl zu existieren so dass ge von ein kleiner gleich
11:19 zehnmal er von endes kommt also hier noch der faktor zählen und dann ist das wirklich die vollständige definition von o von fh ist die menge aller funktionen
11:31 gehen so das gilt es gibt irgend so eine zahl n das ist die grenze ab der die kleineren soll als f ja und es gibt eine zahl c
11:41 das ist die konstante mit der wf multiplizieren so dass dann die von den immer kleiner gleich zehnmal eva mendes für alle zahlen ein kleiner gleich
11:53 großen und dann hat man genau das erreicht was man am anfang wollte man hätte zb dass alle polen ohne zweiten grades
12:01 zum beispiel dieses hier sie benennt quadrat +13 im plus 9 das ist jetzt in ofen quadrat das nur als ein beispiel
12:10 ja wir haben also geschafft diese etwas komplizierter funktionen mit ihren komischen konstanten und was hier alles addiert wird und so viel einfacher
12:19 darzustellen ja dann meistens interessiert man sich eben nur dafür wie schnell wächst die ungefähr und das ausschlaggebende für das wachstum ist
12:27 eben dieses m ² her okay jetzt noch kurz ein bisschen was zur schreibweise ich habe hier geschrieben er von ende also diese funktion hier ist in offenen
12:37 quadrat das kann man so schreiben ja gemeint ist davon dass diese funktion tatsächlich ein element dieser menge ist den ufern fahrrad ist eine menge von
12:46 funktionen ich hätte auch schreiben können das element also wirklich so diese formal element parat
12:55 so hat man das schreiben können das ist eine formal korrekte aussage diese funktion hier ist jetzt aber eine sache die man oft sieht die ich sehr
13:04 unschön finde die sich aber leider durchgesetzt hat und zwar sieht man oft statt diesem element zeichen hier ein gleich zeichen also man sieht oft so was
13:14 wie f ist gleich offen was überhaupt keinen sinn macht ja hier gleich zeichen denn damit verliert das gleich zeichen seine eigentliche bedeutung ja
13:24 normalerweise benutzt man gleich zeichen nur wenn die beiden sachen die hier links und rechts stehend na ja gleich sind aber es ist natürlich keine menge
13:33 von funktionen es ist in dieser menge hier drin aber es selber ist keine menge von funktionen steht eine funktion hier steht eine
13:40 menge von ganz vielen funktionen und trotzdem sieht man das immer wieder ja oder man sieht zum beispiel auch so richtige gleichungen wo das oft von
13:50 irgendwas dann drin vorkommt er zum beispiel so was hier auf ist gleich zwei hoch von enplus m ² flussufern wurzeln ja so was würde man dann manchmal sehen
14:03 und was bedeutet das das bedeutet es gibt eine funktion auto von n die man hier in schreiben kann und es
14:12 gibt eine funktion ausufern wurzel andy man hier hin schreiben kann so dass es gleich diesem ausdruck hier wird ja also das so ein bisschen zur schreibweise
14:22 etwas ungewöhnlich etwas unglücklich würde ich sagen aber so ist es halt und abschließend machen wir nochmal eine kleine übersicht über verschiedene
14:30 typische funktionen die einem so übern weg laufen wenn man diese rotation sieht ja hier haben wir die kleine übersicht und ich würde sagen machen wir daraus
14:41 eine kleine aufgabe versucht doch mal diese oben und aktionen alle oder diese klassen von funktionen die wir stehen sind ja alles klassen von funktionen
14:51 oder menge von funktionen versucht die man in die richtige reihenfolge zu bringen bezüglich teilmenge also welche ist davon die kleinste und dann welche
15:00 ist oder wo von ist die eine teilmenge und wovon ist die wiederum eine teilmenge usw versuchte mal in die richtige reihenfolge zu bringen
15:09 ich gebe euch fünf sekunden zeit das video zu kursieren denn jetzt jeden moment werde ich die lösung zeigen und zwar jetzt so und hier
15:22 haben wir die lösung also wer mir zum beispiel von enya lineares wachstum wird man auch sagen kleiner ist das ist zum beispiel wovon
15:31 wurzeln also wächst klose steht die wurzel noch kleiner als wurzel des übrigens logarithmisch von enya verbot muss erstmal sehr langsam ja noch
15:40 langsamer als logo rhythmus ist eigentlich nur so etwas wie luca rhythmus von loga rhytmus und so ja was haben wir dann über n haben wir zum
15:49 beispiel mal loga rhythmus von enya bekommt muss von entwächst zwar sehr langsam aber ist halt ein faktor es ist mehr als ein konstanter faktor also wenn
16:00 sie so was wie ufer zweimal en haben das ist wieder das gleiche wie uwe hat mir gesagt konstante faktoren machen nichts aus aber wenn wir mit lok denn
16:12 sie beziehen dann ist das ein faktor er ganz langsam wächst schneller als die konstante ja der login überholt irgendwann jede konstante das heißt das
16:21 hier ist dann größer habe aber kommt natürlich nicht an den faktoren selbst ran also wenn wir einmal errechnet dann ist das wiederum größer als ein mal
16:30 locken ja und ja also das ist natürlich jetzt nur eine kleine auswahl hier es gibt ja natürlich noch viel mehr erfährt man zum
16:39 beispiel noch drei natürlich dennoch 4 ist das sind alles noch polygone die hier stehen weil es noch polen nominelles wachstum
16:46 hier ist ein exponentielles wachstum 2 hoch m2 hoch und wächst deutlich schneller als jedes politologen also auch zum beispiel als er noch 4
16:55 aber was wächst noch schneller als das zwei hoch nzb n fakultät ja das kann man sich überlegen hier multiplizieren will in verschiedene zahlen und zwar einmal
17:08 die 2 2 x 2 x 24 x auch in verschiedene zahlen aber das sind immer größere zahlen einmal zweimal dreimal viermal fünf die
17:20 faktoren sind größer als die dass heißt fakultät wächst schneller als das hier hier multiplizieren wir ebenfalls n zahlen aber das sind alles nc hier sind
17:30 es 1 2 3 4 5 und so weiter bis es hier sind ist alles endet also von den fakultäten hoch endes noch mal schneller und dann schließlich zweifache
17:41 exponentiell das wechseln richtig schnell zwei buch zwei hoch n ja versucht das mal zu zeigen dass ein hoch ein kleiner gleich zwei hoch zwei hoch
17:54 endes oder das anders versucht diese aussage die hier steht zu zeigen ja dass u von nsn enthalten ist in zwei wochen kleiner tipp logarithmen gesetze aber
18:06 ich würde sagen dass war es soweit was ich zur rotation sagen heute also dass für die einmal richtig verstanden haben was sie eigentlich ist ja die beschreibt
18:15 nämlich einfach nur das wachstum von funktionen ja und wir benutzen sie in der informatik immer zum beschreiben von der laufzeit eines algorithmus das kann
18:24 ich vielleicht auch noch kurz sagen ja wir hatten ja gesagt die laufzeit eines algorithmus das ist wahr wenn man eine eingabe der länge m bekommt dann möchte
18:33 man wissen wie viele schritte macht der höchstens und das ist ja auch eine funktion für jede eingabe habe ich dann am ende eine zahl also ein algorithmus
18:41 der macht auf eine eingabe der länge m immer höchstens ein quadrat viele schritte ja aber das sind meistens dann nicht
18:50 genau in quadrath sondern dann sind irgendwie fünf mal ein quadrat +17 endlos 3 oder so und so genau will man es halt nicht sagen und deswegen gibt es
18:59 diese ohne notation mit der wir dann sagen können ja also von quadrat ja genauer interessieren wir uns nicht dafür genau also ich hoffe es war das
19:08 verständlich und falls nicht dann schreibt ruhig ein kommentar und dann vielen dank fürs zuschauen und bis zum nächsten mal