Timing und Big-O-Notation in der Informatik

1. Einführungsvideo: Hallo zusammen und willkommen zu diesem Kurs über Big O-Notation Dies ist ein großartiges Informatikthema, das Ihnen helfen wird, bei Ihrer Arbeit effizienter zu werden. Und es wird Ihnen auch helfen , Informatik ein bisschen besser zu verstehen. Das ist ideal für alle Arten von Berufen, auch für Programmierer, sowie für jeden, der in der Wirtschaft tätig ist. Es wird Ihnen helfen, Ihre Produktivität zu steigern, da Sie nur ein bisschen besser verstehen, womit Sie arbeiten, wodurch Sie mehr Einblick und Maßnahmen in Bezug auf die Schritte erhalten, die Sie möglicherweise ergreifen in Bezug auf die Schritte erhalten, die Sie möglicherweise müssen, um die Dinge effizienter zu gestalten Und genau das werden wir in diesem Kurs behandeln. Wir werden uns mit der Notation befassen, die der Analyse verschiedener Algorithmen und der Skalierbarkeit zugrunde liegt . Wir wollen verstehen, ob wir ein Programm oder einen Code oder auch nur eine Organisationseinheit erstellen. Kann es skalieren? Wenn wir Aufgaben und Verfahren entwickeln , die exponentieller Natur sind, dann werden sie niemals skalierbar sein Und genau das wollen wir analysieren können: Funktioniert es genauso, wenn wir zehn oder 100.000 Leute haben Denken Sie darüber nach, ob Sie jede einzelne Datei in einem Aktenschrank überprüfen möchten. Es gibt eine Methode, bei der Sie jede einzelne Datei herausziehen und einzeln betrachten können , oder Sie können ein Verfahren erstellen, bei dem sie organisiert und sortiert ist , sodass Sie wissen, wo Sie nach Dingen suchen müssen. Und das können Sie auch im Programmierbereich tun , aber auch mit den Dingen um uns herum. Ein anderes Beispiel wäre, wenn wir jemanden zu einer Organisation hinzufügen müssten, aber dafür müssten wir zuerst jedes andere Mitglied der Organisation kontaktieren . Das ist eine nicht skalierbare Lösung. Es ist ein nicht skalierbares Verfahren. Und wir wollen in der Lage sein, dieses Verfahren zu analysieren , zu überarbeiten und es zu einem skalierbareren Verfahren zu machen Wir werden uns dabei beide auf den Code konzentrieren, uns aber darüber im Klaren sein, dass diese Prinzipien auch im täglichen Leben gelten Sie gelten für alles, was uns umgibt. Lassen Sie uns also in dieses Informatik-Thema einsteigen und einen Blick auf einige wirklich interessante Mathematik werfen. 2. Big O-Einführung: Lassen Sie uns über unser erstes Hauptthema in der Analyse von Algorithmen sprechen , und das wird diese Idee der Notation sein. Wir werden das also tatsächlich zu einer sogenannten Big-O-Notation weiterentwickeln , die ungefähr so aussehen wird , wo Sie ein O haben und dann die In-Notation darin enthalten ist. Aber bevor wir das tun können, müssen wir herausfinden, was genau in der Notation steht. In der Notation gibt es also diese seltsame Art von Beziehung, wo ist eine Funktion von in. Also bleib bei mir. Das ist zunächst verwirrend. Also müssen wir das ein bisschen auspacken. Es ist so, dass Ausgabe eine Funktion der Eingabe und sie zufällig dasselbe waren. Lassen Sie uns also weitermachen und eine Art visuelles Modell davon erstellen . Wann immer wir einen Algorithmus oder ein Programm erstellen, wir erstellen wir diese Art von Blackbox. Was wir also haben, ist, dass wir auf der linken Seite Eingaben haben. Wir haben Dinge, die in die Kiste kommen. Wir haben vielleicht deine Facebook-Freunde, vielleicht ist es dein Google Drive, all die Daten, die du da sendest. Es ist das Internet. Wenn du etwas hochlädst, ist das die Eingabe Es wird an eine Art Logik gesendet, an eine Art Programm. Das ist also, weißt du, die Logik oder die Controller-Rate hier. Und dann hat es eine Art Ausgang. Etwas passiert, weil es genau hier zu dieser Logik übergegangen ist. Etwas ist passiert? Etwas hat sich bewegt, etwas wurde gerettet. Genau das macht die Logik. Nehmen wir zum Beispiel an, wir laden Bilder hoch. Die Eingabe sind die Bilder. Wir senden es an den Controller. Es nimmt die Bilder auf, vielleicht verkleinert es sie, um sie einfacher zu speichern. Dann nimmt es diese Bilder auf und speichert sie in einer Datenbank. Also legt es sie ab und schreibt sie in den physischen Speicher auf eine Festplatte. Und das ist die Ausgabe. Also die Eingabe, die Bilder, die Ausgabe ist jeder einzelne dieser Speichervorgänge auf einer Festplatte. Also, was wir versuchen herauszufinden , ist die Eingabe in. Das ist also die Eingabe von in. Was wird unser Output sein. In Bezug darauf. Ein Recht hier ist nur eine Variable. Das liegt nur daran, dass wir nicht wissen , wie viele Daten reinkommen. Wenn wir zum Beispiel ein Programm mit Facebook-Freunden hätten , hätte ich vielleicht, weißt du, vielleicht 182 Facebook-Freunde haben können. Nun, vielleicht hast du 1.373 und dein entfernter Cousin hat 10.157 Facebook-Freunde, weißt du, und so weiter und so weiter Und nehmen wir an, es gibt kein Limit. Ich denke, es gibt ein Limit. Aber nehmen wir an, es gibt kein Limit für Facebook-Freunde. Das heißt, Sie könnten bis ins Unendliche Null haben . Also wir wissen nicht, welche Nummer hier reinkommen wird. Anstatt also zu versuchen, einfach eine Zahl zu erfinden, sagen wir einfach, was nur der Platzhalterwert sein wird was nur der Platzhalterwert sein Also werden wir hier eine Eingabe von eingeben. Es kann jede dieser Zahlen von Null bis Unendlich sein. Also jede Zahl. Und dann wird es unsere Logik durchgehen. Und dann, am Ende, werden wir eine bestimmte Anzahl von Operationen haben. Zwischen dieser Punktrate werden wir also Logik und dann Operationen haben, und dann wird es ausgegeben. Und wir wollen wissen, was zu diesem Zeitpunkt passiert. Wie hängt das damit zusammen? Also das hier wird die Ausgabe oder unsere Funktion sein. Das wird die Notation sein. Und was wir normalerweise schreiben, ist , dass wir es auch als In schreiben. Aber wir schreiben es als Funktion von, was bedeutet, dass das nicht das Einzige ist, was wir hier angeben. Es gibt tatsächlich eine Menge verschiedener Dinge, die wir hier platzieren könnten. Was wir haben könnten, ist drin, und das bedeutet nur, dass wann immer wir, sagen wir, 1.000 Daten eingeben , es nur 1.000 Operationen dauert. zum Beispiel Wenn Sie zum Beispiel eine Menge Dateien auf Ihrer Festplatte finden und diese an einen anderen Ort verschieben möchten? Nun, es gibt nichts anderes , was wirklich passieren muss. Wir nehmen einen, wir verschieben ihn. Wir nehmen einen, wir verschieben ihn. Das ist drin. Für jedes Datenelement, das Sie hinzufügen, gibt es nur eine weitere Operation. Jetzt gibt es natürlich verschiedene Dinge. Also statt dessen könnte es Quadrat geben. Es gibt etwas namens Log of. Es gibt nur ein Protokoll von n. Es gibt ein Würfelwort. Da ist die Quadratwurzel von. Und so weiter und so weiter. Also alles was wir tun, ist, all diese Dinge zu nehmen und sie zu einer Funktion der Eingabe zu machen. Das wird immer so bleiben. Das wird immer drin sein. Es ist unser Beitrag. Es ist die Menge an Daten, die reinkommen. Auf der rechten Seite ist nur die Beziehung, und wir verwenden sie nur, weil sie uns zeigt, dass wir daraus eine Funktion machen. Ich meine, wir könnten X und das Quadrat X verwenden und dann X Logarithmus von X und so weiter und so weiter und so weiter und so weiter Aber das Problem ist, dass Sie vielleicht verwirrt werden, was genau X ist. Und dann müssen wir hier etwas aufstellen, das einfach sagt: Nun, x ist gleich n, x ist gleich oder Eingabe Und dann denken wir einfach, warum bleiben wir nicht einfach bei N, um diese ganze Sache zu machen Das wirklich verwirrendste an der Notation ist, dass N so aussieht, als ob es die Eingabe und die Ausgabe sein kann. Aber was wichtig ist, ist die Eingabe, und dann ist die Ausgabe nur eine Funktion von N. Es eine Darstellung dafür, wie lange oder wie viele Operationen N verwenden muss, um darüber hinwegzukommen. Zu den Ausgängen. Schauen wir uns nun ein kleines konkretes Beispiel an. Kehren wir zu den Facebook-Freunden zurück, denn das können wir uns alle sehr schnell vorstellen. Nehmen wir an, ich habe hier einen Algorithmus. Ich habe einen Algorithmus , der eine Anzahl von Facebook-Freunden und sie zum Zeitpunkt oder in der Beziehung von in eine Datenbank eingibt. Und nehmen wir an, ich habe hier einen anderen Algorithmus. Welches macht genau das Gleiche. Nur dass es stattdessen dasselbe von In aufnimmt, also nimmt es rein, aber es gibt quadratisch Hier ist die Effizienz etwas geringer . Jetzt können wir uns diese beiden ansehen und sie einfach ein bisschen vergleichen. Welcher dieser Algorithmen ist schneller? Wenn wir also weitermachen und nur ein bisschen schnell rechnen würden, nehmen wir an, dass wir das mit 100 Facebook-Frances testen werden. Also bei diesem ersten, naja, es werden einfach 100 sein, die in unsere kleine Blackbox gehen, und es kommen 100 verschiedene Operationen heraus zu tun, was auch immer es tut. Nun, im unteren Teil haben wir 100, die in unsere kleine Blackbox gehen. Denken Sie daran, es wird immer gleich bleiben, aber unsere Funktion ist n-Quadrat, was bedeutet, dass wir jetzt tatsächlich 100 nehmen und es quadrieren müssen , was sich herausstellt, dass 100 mal 100 ist, was bedeutet, dass unsere Summe Ups ist, wir müssen die Nullen genau hier hinbekommen Vier Nullen oder 10.000. Sie können also sehen , dass die erste nur 100 Operationen benötigte, während die zweite 10.000 Operationen benötigte Wir werden etwas später darauf eingehen. Ihre Wachstumsmuster sind jedoch wichtig. Innerhalb dessen, was wir haben, haben wir tatsächlich etwas, das wir linear nennen, und mit Quadrat haben wir etwas, das wir exponentiell nennen, was bedeutet, dass das Wachstum im Laufe der Zeit immer mehr zunimmt Aber wie gesagt, darauf kommen wir später zurück. Aber ich wollte dir nur zeigen , wie wir das sehen. Wir haben also einen Eingabewert und wir haben einen Ausgabewert. Wir haben einen anderen Eingabewert und einen anderen Ausgabewert und es gibt zwei verschiedene Algorithmen, Algorithmus A und Algorithmus B. Und wir können schnell sagen: Nun, A ist definitiv schneller als B. A ist man könnte sagen, es ist größer als B, oder man könnte sagen, dass es weniger Zeit benötigt als B oder wie auch immer Sie sie vergleichen möchten. Aber dieser ist schnell und dieser langsam, weil sie so viele Operationen benötigen. Also, was ist dann der Sinn von? Worauf wollen wir hier hinaus? Damit können wir sehen, wie ein Algorithmus mit der Eingabegröße skaliert. Wenn wir einen Algorithmus entwerfen, wollen wir wissen, ob er mit mehr Leuten und Input effizient ist. Wir wollen, dass unsere Programme erfolgreich sind. Deshalb wollen wir Lösungen entwickeln, die skalierbar sind. Und das werden Sie oft hören. Wir wollen skalierbare Lösungen entwickeln. Und eine skalierbare Lösung ist eine Lösung, die nicht nur für die genaue Anzahl von Menschen funktioniert , die sie gerade verwenden. Also, wie ich schon sagte, werden wir zum Beispiel auf Facebook weitermachen. Stellen Sie sich vor, Facebook würde dieses verwenden. Stellen Sie sich vor, es würde den quadratischen Algorithmus verwenden , weil es nicht glaubt, dass sie skalieren würden Nun, die Sache ist, wir sind Programmierer. Wir versuchen, unser Produkt zum besten Produkt zu machen , das es sein kann Und das bedeutet, dass wir wollen, dass das Produkt erfolgreich ist. Und wenn ein Produkt erfolgreich ist, nutzen es mehr Menschen, es werden mehr Daten eingegeben, und der Algorithmus muss diese neuen Teile verwenden Wenn wir kein Programm entwickeln, das skalierbar ist, stoßen wir auf das ganze exponentielle Problem, bei dem ja, das funktioniert für 100 und vielleicht funktioniert es für 1.000 und hey, vielleicht funktioniert es für Aber wenn Sie sich darüber im Klaren sind, dass das ein sehr kleiner Teil der Bevölkerung Nehmen wir an, vielleicht 1 Million Menschen. Willst du unser Programm nutzen. Nun, wir haben eine Lösung die für 1 Million Menschen nicht funktioniert. Wenn wir 1 Million mal 1 Million machen würden. Nun, wir hätten eine Zahl , die extrem groß ist. Eine Zahl, die unser Gehirn nicht einmal verstehen kann. Und das hier werden wir etwas später nachrechnen einer so großen Zahl dauert Ausführung einer so großen Zahl dauert Tage oder sogar Jahre. Ein Computer, der sich, wissen Sie, online anmelden und all diese schnellen Berechnungen durchführen kann, benötigt Tage oder Jahre, um online anmelden und all diese schnellen Berechnungen durchführen kann, benötigt eine einfache Aufgabe zu erledigen, und das liegt daran, dass das Programm nicht skalierbar ist. Das ist also die Grundlage der Notation. Es ist eine standardisierte Notationsform, die es uns ermöglicht, zwei Algorithmen in einer völlig sterilen Umgebung zu vergleichen , sodass wir sie nicht implementieren müssen. Wir können sie uns einfach ansehen. Es ermöglicht uns, sie zu vergleichen und herauszufinden, welche skalierbarer ist. Welches wird schneller sein, wenn wir mehr Personen oder mehr Daten oder mehr Operationen hinzufügen . Und das ist der Punkt der Notation. Und in der nächsten Vorlesung werden wir uns weiter damit befassen und wir werden immer wieder die Box mit der Notation auspacken , sodass wir diese solide Grundlage haben, um verschiedene Algorithmen vergleichen zu können 3. N-Notation: Lassen Sie uns etwas tiefer in die Endnotation eintauchen und uns einige der Ziele ansehen , die dahinter stehen, warum wir als Informatiker die Endnotation verwenden und was wir daraus herausholen wollen. Weil die Endnotation auf viele verschiedene Arten verwendet werden kann . Es gibt eine Menge verschiedener Kombinationen oder Informationen , die wir mithilfe dieser Notation daraus herausholen können . Aber ich möchte auf den Kern eingehen, wofür die meisten Informatiker es verwenden. Und was sind einige der Ziele? Warum benutzen wir es? Wenn wir also Notation verwenden, suchen wir nach großen Mustern, und wir suchen nach diesen Mustern in einer Art theoretischem Raum, was bedeutet, dass wir nicht wirklich ein Programm implementieren lassen werden oder so. Wir suchen nur nach diesen großen Mustern. Wir suchen zum Beispiel danach, ob ein Diagramm so aussieht und das andere so. uns egal, ob wir irgendwann dieses Diagramm unten haben, vielleicht geht es so und dann das obere Bild so oder so? uns an diesem Punkt egal, ja, da ist dieser Punkt , an dem ich quadriert habe, eigentlich nur ein bisschen effizienter ist Das ist für das Wesentliche, wenn Sie tatsächlich einen Algorithmus vor sich haben einen Algorithmus vor sich und versuchen Das ist es, was vielleicht ein Serveroptimierer machen könnte oder Datenbankmanagement, solche machen könnte oder Datenbankmanagement, Das ist uns nur wichtig, die Theorie insgesamt. Wir suchen, welche Gleichung im Laufe der Zeit schlechter skaliert. wir uns also der Unendlichkeit nähern, wenn wir uns der unbekannten Menge an Daten nähern , die in den Indoor-Algorithmus einfließen könnten, was wird dann mit unserer Gleichung passieren ? Werden wir zu dieser Gleichung kommen, die in diesem Jahrhundert nicht fertig gestellt werden kann in diesem Jahrhundert nicht fertig gestellt weil sie so viele Berechnungen erfordern wird, oder werden wir so etwas bekommen, bei dem es egal ist, wie viele Berechnungen wir ihr geben. Es wird einfach weiter tuckern. Und genau das wollen wir sehen Wir wollen, dass sich die Effizienz zwischen verschiedenen Algorithmen erheblich ändert . Das ist der Sinn der Notation und warum wir Notation verwenden. Aus diesem Grund gibt es ein paar Regeln, die wir normalerweise bei der Notation verwenden. Und das sind nur Abkürzungen, die wir benutzen, um uns nicht zu verwirren Und noch einmal, um zu diesem großen Ganzen zu kommen. Also verbringen wir nicht unsere ganze Zeit im Detail. Wir können uns einfach zwei Gleichungen ansehen und sagen, ja, diese skaliert ein bisschen besser Die erste ist, dass uns Vielfache egal sind. Und das bedeutet zum Beispiel, wenn wir n zum Quadrat und dann drei zum Quadrat haben. Diese sind in jeder Hinsicht gleich. Sie sind einander grundsätzlich gleichwertig. Es ist uns egal. Ich meine, drei, weißt du, vielleicht könntest du es dir selbst gegenüber rechtfertigen. Ja, drei sind in Ordnung, aber das könnten, weißt du, das könnten 3 Millionen sein, 3 Milliarden, 30 Milliarden, 30 Billionen. Es kann eine beliebige Zahl sein, die wir wollen, und es spielt keine Rolle. Wir nehmen das Vielfache und löschen es. Die Vielfachen sind uns egal. Und das kommt wieder auf die große, alles übergeordnete Sache an, es spielt keine Rolle, wie groß diese Zahl irgendwann zwischen Null Irgendwann wird das Quadrat n dazu führen, dass diese Zahl nicht einmal mehr effektiv ist dazu führen, dass diese Zahl nicht Stellen Sie sich vor, irgendwann wäre gleich, ich weiß es nicht. 300 Google, und Google hat am Ende 100 Nullen. Sie haben also 100 Nullen ganz am Ende. Denken Sie, dass die 3 Millionen , die multipliziert werden, zu diesem Zeitpunkt wirklich wichtig Ich meine, es wird ein sehr, sehr kleiner Unterschied im Endergebnis sein sehr kleiner Unterschied im Endergebnis Wir reden so, weißt du, es wird ein Unterschied sein zwischen einer Zahl, die so aussieht, oder zwischen einer Zahl , auf der das steht. Weißt du, ein bisschen mehr drauf. Es spielt überhaupt keine Rolle. Das ist der Grund, warum uns theoretisch immer dann, wenn wir von Null ins Unendliche gehen, Vielfache egal Für den Vergleich von zwei Algorithmen könnten es also 3 Millionen Quadrate sein, und wir vergleichen es mit quasi keinem Würfel , spielt keine Wir vergleichen immer noch n quadratisch mit n würfelförmig. Also entfernst du am Anfang immer die Vielfachen. Nun, wie bekommen wir diese Vielfachen? Nun, nehmen wir an, wir haben eine Gleichung, die das macht. Wir haben die Blackbox, also kommen die Eingänge hierher. Wir haben eine quadratische Operation. Als Nächstes bringen wir all diese Eingaben in eine weitere Blackbox, eine weitere quadratische Operation Okay. Und sagen wir ganz am Ende, wir haben noch einen, aber dieser ist nur ein Anmeldevorgang. Mit einem Algorithmus wie diesem erstellen wir hier also eine kleine Gleichung. Wir machen so etwas. Wir gehen quadratisch plus quadratisch rein und melden uns an. Und dann können wir diese tatsächlich zu einem Vielfachen kombinieren. Das sind also zwei N im Quadrat plus Einloggen. Und so kommen wir auf ein Vielfaches, und wissen Sie, was wir hier gesagt haben ist, dass uns das Vielfache nicht wirklich wichtig Ich kann das so oft machen, wie wir wollen. Wir schauen uns nur diesen großen Veränderungsfaktor an. Also das wird dann quadratisch plus Einloggen. Also dann kommt das zu unserer zweiten Regel. Wir nehmen die größte Gleichung. Wann immer wir also wieder eine Gleichung wie diese haben , wird sie nicht annähernd so schnell skalieren. Wenn wir zu diesen riesigen Zahlen mit 50 Nullen und 1 Milliarde Nullen am Ende kommen , ich meine, es ist zwei und fertig, also kann es irgendwann 1 Milliarde Nullen geben könnten 1 Milliarde Nullen Am Ende könnten 1 Milliarde Nullen stehen, nicht die Zahl Ich spreche von 1 Milliarde echten Nullen. Es wäre eine Zahl, die so lang wäre, weißt du, dass man sie nicht auf der ganzen Erde platzieren könnte. Es könnte eine solche Zahl geben. Ich meine, wir gehen hier bis in die Unendlichkeit. Irgendwann wird das einfach so gewaltig größer als diese Zahl werden , dass es uns egal Das ist nur eine kleine Hürde auf dem Weg zu dieser Zahl. Es wird sie irgendwann nur um vielleicht 0,000.00% beeinflussen irgendwann nur um vielleicht 0,000.00% Irgendwann wird es von fast nichts beeinflusst. Es wird eine so kleine Zahl sein. Es ist fast Null. Aus diesem entfernen wir es auch am Ende und lassen einfach eine Gleichung wie diese übrig, um zu sagen: Hey, dieser ganze Algorithmus hier drüben, dieser gesamte Algorithmus hier ist eigentlich nur quadratisch Also gibt es ein paar Skalierungsregeln. Nun, wenn Sie technisch werden wollen, wenn wir Serveroptimierung oder irgendwas anderes machen , wo wir tatsächlich eine Gleichung vor uns haben , ja, das ist wahrscheinlich etwas, das wir uns ansehen wollen denn wenn wir uns einen echten Server ansehen und wir haben eine Gleichung, die es mit n Quadrat plus Anmeldung ausführen kann , anstatt mit zwei Quadraten plus n Einloggen wir wollen diesen machen , weil er in der Praxis schneller sein wird . Aber auch das ist keine Praxis. Das ist Theorie. Wir versuchen, nur die Unterschiede von Großanwendungen herauszufinden . In diesem Sinne halten wir uns an diese beiden Regeln, wir unterteilen sie darauf, was genau die große Laufzeit dieser Regeln ist. Und wir haben tatsächlich kleine Modifikatoren von Big O und Little O und Beta Wir werden in Kürze auch über diese sprechen , um das Ganze etwas verständlicher zu machen Schauen wir uns hier einige Diagramme an. Schauen wir uns an, wissen Sie, was ich hier detailliert beschrieben habe , mit der ganzen Sache mit den Zahlen, sie werden ihre Partner übertreffen, und deshalb interessieren uns nur die großen Also, genau hier haben wir eine Art Darstellung eines Graphen Wir haben all die Dinge, über die wir gesprochen haben. Dies ist eine, die konstante Zeit ist. Das heißt, wir könnten 1.000, wir könnten 1 Milliarde investieren, wir könnten beliebig viele einsetzen, und es wird immer nur konstante Anzahl von Operationen erfordern. Also werden es nur vielleicht drei dauern. Vielleicht sind es 62 verschiedene Operationen. Egal, welche Zahl wir eingeben, es sind 62 Operationen erforderlich. Das ist also konstante Zeit. Und dann haben wir diese Anmeldezeit, und Sie können sehen, dass sie diese Art von Grafik hat , die so aussieht. Dann haben wir nur noch die Quadratwurzel von N, was dem Einloggen ähnelt, aber sie steigt mit der Zeit. Wir haben linear oder. Linar ist nur eine gerade Linie in einem Winkel. Beim Einloggen sieht es ein bisschen so aus, aber dann geht es irgendwie in eine lineare Linie über, vielleicht mit leichten Tendenzen Dann haben wir uns selbst ins Quadrat gebracht, was exponentiell ist. Dann haben wir zwei faktorielle n erhalten, was noch exponentieller ist und fast einfach in die Höhe geht Und dann haben wir faktoriell eingegeben, was genauso gut so aussehen könnte Es geht fast direkt in die Luft und erzeugt so große Zahlen , dass, wenn eines Ihrer Programme jemals faktoriell ausgeführt wird , es falsch ist Es muss besser gemacht werden. Schauen wir uns jedoch die Beispiele an was all diese Dinge bedeuten würden, wenn wir ihnen Zahlen hinzufügen würden, wie die Laufzeiten aussehen könnten. In dieser Situation sagen wir also, dass wir hier die Anzahl der Eingaben sehen können , und in Kapital genau hier ist die Anzahl der Operationen. Also hier drüben, das sind die kleinen Vorteile. Das ist es, was wir eingeben. Wir geben die 100.000 oder 10.000 oder 1110 oder eins ein. Und das ist die Ausgabe wie lange es dauern würde, bis es Und du merkst in der ersten Reihe, es wirklich interessant ist, dass mit nur einem Stück, egal was du hast, es im Grunde immer zur gleichen Zeit laufen wird. Natürlich kann es kleine Unterschiede geben, zum Beispiel vielleicht eine konstante Zeit. Vielleicht ist das eine Zeit, in der, wenn konstant mal 62, all diese Werte tatsächlich etwas schneller laufen würden. Aber auch das ist im Wesentlichen und das interessiert uns nicht wirklich Wir wollen uns diese Trends im Laufe der Zeit ansehen. Wenn wir also zu faktoriell übergehen, das E plus am Ende, bedeutet das, wie viele Nullen am Ende stehen Das heißt, das ist 9,3 oder Neun Drei mit 157 oder 156 Nullen, wenn Sie die Dezimalzahl verschieben Wie dem auch sei, am Ende dieser Eins stehen viele Nullen. Und diese eine ist, weißt du, es ist vier mit 2567350000, 456.000 Und Sie können feststellen, wie stark sich das im Laufe der Zeit ändert. Und dann haben wir zwei hier drin. Das sind zwei und dann zwei, etwas faktoriell. Also, weißt du, in dieser Situation ist es zwei Zehntel oder zwei zu 100 und so weiter und so weiter und so weiter Aber wie dem auch sei, Sie können feststellen , dass auch diese beiden. Diese beiden sind im Grunde direkt in der Luft. Es gibt einen so großen Unterschied. Es ist der Unterschied zwischen 400 und 56 Tausend Nullen und 300 oder 30.000 Und dann machen wir mehr und mehr weiter. Und was wir haben, ist, dass wir bis zum Quadrat heruntergefahren sind, worüber wir gesprochen haben, wir haben gezeigt , wie ineffizient das ist Und das sieht im Vergleich zu den Faktoren n und n im Vergleich zu zwei sehr winzig aus, wenn es mehr und mehr überwunden wird . Dann müssen wir uns mit N einloggen Wir kommen hier tatsächlich zu lesbaren Zahlen, nur 1.660.000, dann nur n, was natürlich der Anzahl entspricht, die wir eingegeben haben, weil N immer nur zu N geht. Genau eingegeben haben, weil N immer dafür steht es Und dann fangen wir an, uns mit diesen hier unten zu befassen , wo Sie feststellen, dass sie eigentlich ziemlich cool sind Das sind effiziente Algorithmen hier. Wir haben 100.000 eingesetzt und wir führen nur 316 Operationen durch. der Zeit gibt es immer kleinere Veränderungen Laufe der Zeit gibt es immer kleinere Veränderungen . Und das, Sie können sich vorstellen, wie wir irgendeine Art von Algorithmen dazu bringen konnten , tatsächlich ziemlich effizient zu werden. Ich meine, sieh dir das an. Also wir haben hier den Unterschied zwischen 90. Und in diesem Unterschied erhöhen wir uns um drei Operationen. Jetzt haben wir hier die Differenz von 900. Und um wie viel steigen wir? Nun, nur nach etwa drei Operationen. Dann haben wir den Unterschied von 9.000 neuen Daten. Um wie viel steigen wir? Nun, ungefähr drei Operationen. Und dann steigen wir um 90.000, das ist der nächste Schritt. Und wie viel haben wir? Nun, nur drei Operationen. Es ist das genaue Gegenteil. Je mehr wir hinzufügen, desto weniger steigt es. Es nimmt mit der Zeit immer weniger zu. Und es gibt tatsächlich Algorithmen, über die wir in diesem Kurs sprechen werden und die so ablaufen. Es verwendet so etwas wie Teile und herrsche, wo wir uns tatsächlich aufgeteilt haben. Solche Informationen und auf diese Weise können wir einfach sehr, sehr schnell darauf zugreifen, anstatt jedes einzelne Stück durchgehen zu müssen , um zu dem zu gelangen, was wir wollen. Aber wie dem auch sei, das ist nur ein weiterer Überblick über die Notation, wie sie skaliert, und dann einige der Begriffe, die wir in Bezug auf Notation und Skalierung verwenden In der nächsten Vorlesung werden wir ein Beispiel aus der realen Welt durchgehen, vielleicht ein bisschen mehr aus der Theorie herausholen und uns die Unterschiede zwischen diesen ansehen , wenn wir tatsächlich, Sie wissen schon, 0,01 Sekunden auf jede Operation anwenden Sie wissen schon, 0,01 Sekunden auf jede Operation Wir können sehen, wie groß diese Zahlen werden und welche Unterschiede zwischen ihnen bestehen. 4. Beispiel für die N-Notation: Lassen Sie uns einfach ein paar Zahlen zu worüber wir gesprochen haben, um es ein bisschen zu respektieren, damit jeder es verstehen kann. Lassen Sie uns dieses Problem hier besprechen und uns die Unterschiede ansehen , wie Sie sich anmelden und wie das Quadrat aussehen könnte In der letzten Vorlesung haben wir uns diese Art von grafischer Rate hier angeschaut von grafischer Rate hier Was wir uns also ansehen, ist diese Rate hier, beim Einloggen und Quadrat Und bei dieser kleinen grafischen Rate hier, ich meine, sie sehen wirklich nah beieinander aus, oder? Sie sehen aus, als gäbe es keinen großen Unterschied zwischen ihnen. Und das möchte ich zeigen, dass es selbst zwischen diesen hier oben große Unterschiede gibt , und die Änderung der Effizienz ist sehr wichtig. Schauen wir uns dann dieses Beispiel an. Es wird es einfach durchgehen und es sollte Ihnen hoffentlich die Unterschiede zeigen. Also haben wir oder wir sagen , dass jeder Zyklus eines Programms ungefähr 0,001 Sekunden dauert, was meiner Meinung nach eine Millisekunde ist Wir sagen also, wie viel schneller Anmeldung dauert als die quadratische Eingabe, wenn 1.000 Daten wenn 1.000 Daten eingegeben werden und dann weiter unten, wenn 25.000 Also, was wir damit machen werden, ist, dass wir das einfach einstecken werden Wir werden berechnen, wie viele Operationen es dauert, multiplizieren es mit einer Millisekunde und dann werden wir herausfinden, wie lange ein Programm , das so laufen würde, Also, unser erstes Beispiel, wir haben das beim Einloggen. Wir multiplizieren 1.000 mit dem Logarithmus von 1.000, und wir verwenden logarithmische Zwei, denken Sie daran. Das sind also alles logarithmische Zwei. Wir erhalten also 9.960 mal Millisekunden, und das alles ergibt Also, wenn wir das Quadrat nehmen, werden wir 1.000 Quadrat machen Das wird 1.000 mal 1.000 sein, was uns letztendlich die Zahl 1 Million Und mit 1 Million multiplizieren Sie die Millisekunden und wir erhalten 1.000 Sekunden oder Der Unterschied zwischen der Verwendung dieser beiden Algorithmen besteht also dass einer 9,96 Sekunden dauert Also, du weißt schon, 10 Sekunden. Es ist gar nicht so lang und die andere wird 16 Minuten dauern, bis sie fertig ist. Stellen Sie sich vor, Sie sind online und senden ein Formular und eines davon verwendet das n-Login während ein anderes Formular das n-Quadrat verwendet. Viele Leute könnten 10 Sekunden warten, Viele Leute könnten 10 Sekunden warten bis ein Formular gesendet Aber wenn wir 16 Minuten warten müssten, das nicht passieren Niemand wird das tun. Gehen wir also zu einem etwas höheren Beispiel über. Nehmen wir an, wir haben 25.000 Daten. Also machen wir die 25.000 Teile. Es ist 25 mal logarithmisch, basierend auf zwei von 25.000. Wir erhalten 365.000 mal Millisekunden. Das sind dann 6 Minuten und 5 Sekunden. Beachten Sie hier, dass dies auch bei 25.000 USD oder 24.000 zusätzlichen Daten wichtig ist. Das dauert immer noch 10 Minuten weniger, als wenn wir n squared für die vorherige Version verwendet Wie dem auch sei, jetzt schauen wir uns hier unten das n Squared an. Also machen wir 25.000 mal 25.000. Das bringt uns 625 Millionen mal pro Millisekunde, und wir Wir haben sieben Tage und fünf Stunden, um das zu erreichen. Es sind also nur 25.000 Daten, wir sind jetzt von 6 Minuten auf sieben Tage umgestiegen 6 Minuten auf sieben Tage Und wenn wir zum Beispiel 250.000 Daten verarbeiten würden, läge diese Rate hier irgendwo in den Jahren oder Tausenden von Es wäre etwas, bei dem es zu unseren Lebzeiten oder zu Lebzeiten unserer Enkelkinder nicht erreicht werden würde , bei dem es zu unseren Lebzeiten oder zu Lebzeiten unserer Enkelkinder nicht erreicht , die Sonne könnte ausbrennen, bevor wir zu der Leistung kommen, bevor das Programm tatsächlich Deshalb hoffe ich, dass dieses kleine Beispiel hier, nur für diese kleine Mathematik und Hinzufügen der Millisekunden hier, Sie den großen Unterschied erkennen können, auch wenn sie hier irgendwie gleich aussehen und vielleicht sogar ein bisschen hier Wenn wir auf immer mehr Zahlen skalieren, bekommen wir gigantische Inkonsistenzen bekommen wir gigantische Inkonsistenzen Und um diese riesigen Inkonsistenzen geht es beim Informatik-Theorem Darum geht es im Informatik-Lehrplan. Ich versuche nur herauszufinden, welche Art von Datenstruktur oder Techniken wir in jeder Situation verwenden sollten, damit wir die effizientesten Algorithmen entwickeln können, sodass wir Dinge am Ende schnell erledigen können, anstatt zusätzliche Zeit und Ressourcen aufzuwenden oder nicht einmal in der oder nicht einmal Lage zu sein, DS zu weil es zu lange dauern würde Und das ist nur ein kleines Beispiel dafür. Okay. 5. Big O: Jetzt haben wir also ein gutes Verständnis von N und wie genau es funktioniert, und es hängt mit unserer Analyse von Algorithmen zusammen, wir können anfangen, das irgendwie zu erweitern. Wir wissen also, dass das eine Methode ist , um zu klassifizieren, wie schnell ein Algorithmus läuft, wenn eine bestimmte Zahl gegeben ist, wie lange es in Bezug auf diese Zahl dauern wird Wird es also gerade noch rechtzeitig dauern? Also, wenn es 1.000 wären, wird es 1.000 entsprechen oder wird es etwa n Mal zum Quadrat brauchen, während, wenn es 1.000 sind, es 1 Million entspricht Und das ist eine wirklich wichtige Art der Klassifizierung. Programme sind jedoch nicht so einfach. Sie laufen nicht einfach ständig zu einer exakten Zeit. Oft haben sie eine Grenze. Also, wenn es geladen wird, wird es vielleicht ein n-Quadrat ausführen, aber es führt ein In und dann exportiert es in log-in Also müssen wir in der Lage sein, uns das anzusehen, und wir müssen uns das Programm ansehen und das Programm als Ganzes klassifizieren Also, dieses Programm, wir würden immer den schlimmsten Fall betrachten, der immer zum schlimmsten Fall führt, alles im Quadrat nehmen Bei bestimmten Schritten wird es jedoch schneller laufen Und aus diesem Grund haben wir hier tatsächlich diese Art von Systemrate, die die Grenzen auf unserer in der Notation klassifizieren wird Lassen Sie uns das einfach mal runtergehen und uns das ansehen Die hier oben heißen Omicron. Sie haben Theta in der Mitte und dann Omega, und das ist Omega in Kleinbuchstaben Sie können also sehen, dass es griechische Alphabete sind, aber wir verwenden in Mathe oft Griechisch, weil das Alphabet Also verwenden wir Griechisch, um Dinge symbolisch darzustellen. Und in diesem Fall steht jedes dieser griechischen Symbole symbolisch Was Sie hier haben, ist, dass wir hier zum Beispiel eine Grenze genau in der Mitte zeichnen zum Beispiel eine Grenze genau in der Mitte Und hier oben ist es schneller. Ich sage also, hier oben wird es schneller sein und hier unten wird es langsamer sein. Also, unsere erste Notation ist kleines O, und Sie können sehen, dass wir einfach nicht gerne Omicron sagen, wie eine große Omikron-Notation, die einfach Also sagen wir einfach kleines großes O. Und genau hier so Es bedeutet nur, dass es schneller sein wird, was bedeutet, dass das Programm immer schneller sein wird als diese Grenze. Also zum Beispiel, wenn unsere Grenze quadratisch wäre, genau hier, wenn wir ein kleines O von n im Quadrat hätten Genau hier würden wir sehen, dass das bedeutet, dass es niemals das N-Quadrat berühren wird Es wird eigentlich immer schneller sein als n zum Quadrat. Es wird also immer direkt über dieser Linie sein, aber schneller als das N-Quadrat Also was wir tun können, ist, dass wir das irgendwie nutzen können , um die Grenze herauszufinden Das nächste, was wir haben, ist ein großes O und ein großes O bedeutet, dass es schneller oder gleich sein wird. Das bedeutet also, dass es diese Linie berührt oder schneller sein wird. Also wird es im schlimmsten Fall sein, und das ist etwas , das hier sehr wichtig ist. Das heißt im schlimmsten Fall. Das wird quadratisch sein. Die nächste, die wir haben, ist Theta, was bedeutet, dass sie keinen dieser beiden berühren wird Es wird nicht tief fallen und es wird nicht hoch gehen Was es hinuntergehen wird, ist genau in dieser Linie. Also egal, was im Quadrat sein wird, es wird irgendwo in dieser Linie sein Und dann ist der nächste, den wir haben, langsamer oder gleich. Also, dieser ist Omega, und dieser ist langsamer oder gleich. Es berührt also diese Linie, und es ist immer langsamer. Also, weißt du, wir haben N zum dritten N zum vierten hier unten, hier oben, vielleicht haben wir das getan. Also ist es immer langsamer als das, oder gleich N im Quadrat Also bestenfalls. Also dieser ist bestenfalls. Es wird darauf laufen, wenn du das einlegst. Also, wenn wir zum Beispiel von n im Quadrat so schreiben. Lassen Sie uns genau da ein bisschen abschneiden, aber wenn n so quadriert ist, dann verstehen wir, dass dieses Programm immer am besten läuft, es wird im dann verstehen wir, dass dieses Programm immer am besten läuft, es wird im Quadrat n ausgeführt Das heißt, es kann noch schlimmer laufen. Und darunter haben wir langsamer als, was bedeutet, dass es immer schlechter als im Quadrat läuft Es wird sich nie im Quadrat bewegen, aber es läuft schlechter als Und warum ist das wichtig? Warum wollen wir uns auf diesen von all diesen konzentrieren? Und das liegt daran, dass Big O das schlimmste Szenario vorschreibt Und wir befassen uns mit dem Worst-Case-Szenario , denn angesichts der Wahrscheinlichkeit und der Statistiken könnte unser Programm irgendwann das Worst-Case-Szenario berühren , und wir wollen ohne Zweifel wissen, was das schlimmste Szenario ist? Deshalb verwenden wir das große O. Schlimmstenfalls ist es, was es sein wird. Und Sie können sehen, ich werde die Tabelle hier noch einmal aufrufen. Wenn wir diese Idee haben, wenn wir in der Lage sind, zu sagen, was unser Programm sein wird, können wir tatsächlich anfangen, das auszufüllen. Wenn wir also zum Beispiel ein großes O von N haben, großes O von N verstehen wir, dass es schlimmstenfalls drin sein wird. Es könnte also drin sein, aber es könnte auch etwas Größeres sein als in. Also können wir all unsere Zeitdiagramme und Skizzen und so weiter erstellen und davon ausgehen, dass es niemals auf dieser Seite der Linie passieren wird auf dieser Seite der Linie Es wird immer auf diese Seite gehen. Und das ist wirklich mächtig, weil wir jetzt anfangen können schlimmsten Fälle von Programmen zu vergleichen, und wir können feststellen, dass wir vielleicht, wenn ein Programm skaliert wird, wenn wir zum Beispiel ein Login-Programm mit einem In-Programm haben, sehen können, dass, wenn dieses skaliert, es schlimmer sein wird als dieses. Lassen Sie uns das einfach ein wenig aufschlüsseln, und wir können sehen, warum einige davon bedeutungslos sind Also, wir haben ein Programm, das bei Little O n Squared läuft, was bedeutet, dass es schneller ist als N Das heißt, es kann überall sein, von n zum Quadrat bis hin zu Im Grunde muss es einfach schneller sein als Es wird also nicht quadriert werden, aber es könnte alles sein, was schneller als Und das ist quasi wie das große O. Aber das Ding ist das Ding, das uns gegeben wird, also ist es ein kleines O von N. Wir können das eigentlich nicht anfassen Das macht es nur ein bisschen verwirrend. Es gibt uns eine Grenze, aber es macht es uns nicht leicht, es zu erkennen. Wir können uns das nicht sofort ansehen und sagen : Oh, das wird zur Laufzeit. Wir müssen uns das ansehen und sagen, oh, es wird schneller laufen als, aber wir wissen nicht wirklich wo. Und das gibt uns nicht wirklich viel Spielraum. Und dann haben wir unsere große O-Notation. Und das haben wir gerade besprochen, wir können uns das ansehen und sagen, oh, schlimmstenfalls läuft es beim Einloggen. Theta wäre toll, wenn wir Theta immer benutzen könnten. Das ist entweder gleich oder manchmal wird es als Durchschnitt verwendet, aber meistens bedeutet es gleich manchmal wird es als Durchschnitt verwendet, aber meistens bedeutet es gleich . Das wäre also großartig. Das Problem ist jedoch, dass Programme nicht immer genau entlang einer Linie laufen. Manchmal laufen sie vielleicht an einem Punkt, es läuft an einem, aber an einem Punkt läuft es und loggt sich ein, und es geht irgendwo dazwischen. Theta ist also einfach zu spezifisch , als dass wir es wirklich mögen könnten. Und dann sind diese ziemlich bedeutungslos, weil sie uns nicht viele Informationen geben Denk darüber nach. Dieser hier, der Omega ist. Also Omega zum Quadrat. Das heißt, es wird langsamer oder gleich dem Quadrat von Omega sein , was, wie Sie sagen, unser Programm wird entweder im Quadrat laufen oder es wird langsamer sein im Quadrat laufen oder es wird Wie sollen wir vor diesem Hintergrund planen? Weil langsamer ins Unendliche gehen könnte. Es könnte so langsam wie möglich sein, und darauf könnten wir uns nie vorbereiten , weil wir nie eine Grenze haben würden. Wir würden sagen, okay, es wird einfach laufen, wie schnell es im Quadrat dauern könnte, es könnte faktoriell sein, es könnte unendlich dauern Es hilft uns nicht, das Programm zu analysieren , weil es diese unendliche Seite Und genau die gleiche Idee mit dem kleinen Omega ist auch hier, dass es auf der schlechten Seite ins Unendliche geht, was uns nicht hilft. Diese helfen uns also, denn die schlechte Seite ist, lassen Sie mich hier ein paar Rennen machen und ein bisschen mehr Platz schaffen. Diese helfen uns also , weil sie die schlechte Seite haben. Also, nehmen wir an, hier drüben geht es ins Unendliche. Es gibt uns eine Grenze. Also was auch immer, es wird hier schlimmstenfalls sein , aber es könnte besser sein. Und es ist uns egal. Und wenn es zurückkommt und konstant läuft, ist das in Ordnung. Das ist völlig in Ordnung. Das bedeutet, dass unsere Programme hervorragend laufen. Sicher. Aber das können wir einplanen. Es bedeutet nur, dass unser Programm schneller als erwartet ausgeführt wird. Was wir dann tun können, ist einfach für den schlimmsten Fall zu planen. Wenn Sie jedoch auf die andere Seite dieser Linie gehen, können Sie nicht für die Unendlichkeit planen. Deshalb ist Big O so wichtig, weil es von all diesen Notationen die nützlichste Es gibt uns ein Worst-Case-Szenario. Lassen Sie uns also ein Beispiel dafür nehmen, wie wir dies auf ein bestimmtes Problem anwenden könnten . Normalerweise verwenden Sie also immer das Worst-Case-Szenario , das heißt, an welchem Punkt im Programm wird es am ineffizientesten sein wir hier zum Beispiel an, Nehmen wir hier zum Beispiel an, wir hätten ein großes O mit n im Quadrat Wir hatten ein großes O beim Einloggen. Großes O von N und dann großes O von konstanter Zeit. Also die hier unten sind großartig. Aber die Sache ist , egal was passiert, wir werden immer von diesem Typen hier einen Engpass von diesem Typen Und das liegt daran, dass unsere Ladezeit hier oben quadratisch ist, was bedeutet, dass dieses Programm rawnet in quadratisch plus einloggen wird , plus, plus, plus zum ersten, wodurch ich es hier irgendwie konstant halten kann Wir gehen plus eins. Und du denkst vielleicht, warum mache ich das? Und das liegt daran, dass Sie tatsächlich jeden Teil der Schritte zusammenfügen können. Also, weil du diesen Teil machst , machst du dann diesen Teil, dann machst du diesen Teil, dann machst du diesen Teil. Also kannst du sie tatsächlich alle zusammenfügen. Und ich erinnere mich, was wir vorher gemacht haben, als wir darüber gesprochen wie wir versuchen, ein Programm so zu betrachten, wie es ins Unendliche geht. Wenn wir uns also diese Zahl ansehen, welche davon wird die anderen übertreffen, wenn wir ins Unendliche gehen Nun, lassen Sie uns sie zum Beispiel auf 1 Million setzen. Wie bedeutsam ist 1 Million, was Vers 1 Million sein wird, Vers, vielleicht irgendwo um die 3 Millionen, Vers 1 Billiarde oder vielleicht 1 Billion, sechs Eins und 12 Dieser wird wesentlich größer sein. Dies wird ein immer kleinerer Teil der Zahl sein, je weiter sie ins Unendliche geht. Bis zu dem Punkt, an dem diese Werte als Signifikanz gegen Null gehen werden . Also wirst du anfangen, du weißt schon, eine Google-Nummer zu haben , die 100 Null ist, plus vielleicht 8 Millionen hier drüben oder so. Und das bedeutet, dass dieser Teil hier zu diesem Zeitpunkt völlig unbedeutend ist diesem Zeitpunkt völlig unbedeutend Was wir also tun, ist, die niedrigeren zu eliminieren und die Laufzeit dieses Programms ist quadratisch Und dann, lassen Sie uns das mit einem anderen Beispiel hier irgendwie zementieren Nehmen wir an, wir hätten Big Say, wir hätten ein großes O von N im Quadrat. Großes O von N im Quadrat. Großes O von muss hier das S zeichnen. große O von N ist wieder im Quadrat, und dann nehmen wir an, wir haben jetzt das große O von N als Drittel Und jetzt haben wir hier n zum Quadrat plus n zum Quadrat plus n zum Quadrat plus n Quadrat plus das dritte Und so können wir diese tatsächlich zu drei n zum Quadrat plus n zum dritten kombinieren Quadrat plus Und jetzt erinnere dich daran, worüber wir in der letzten Vorlesung über die Endnotation gesprochen haben der letzten Vorlesung über die Endnotation Diese spielen keine Rolle. Die konstante Rate spielt hier keine Rolle, denn je weiter wir in die Unendlichkeit gehen, desto weniger signifikant bis sie, sobald wir eine ausreichend hohe Zahl erreicht haben, im Grunde Null wird. Also können wir diese Zahl streichen. Also haben wir jetzt n Quadrat plus n Drittel. Und dann wird dieser natürlich viel höher abheben als der andere Also landet unser Programm am Ende einfach auf dem dritten Platz. Und da das alles große O-Notationen sind, wissen wir, dass unser Programm im schlimmsten Fall an dritter Stelle ausgeführt wird, was bedeutet, dass wir jetzt diese Grenze von Terz haben und die Unendlichkeit der Laufzeit auf diese Weise abläuft Und jetzt können wir planen, dass wir im schlimmsten Fall eine dritte haben, und wir können alles bis zur konstanten Zeit planen , weil wir jetzt nur noch genau diese Grenze haben. Wir verstehen, dass, wissen Sie, wenn wir 1 Million Daten eingeben, es vielleicht nicht funktioniert. Vielleicht können wir versuchen , das rüberzubringen, aber es gibt uns einen Anfang. Es gibt uns einen Ort, an dem wir es mit anderen vergleichen können. Das ist also eine große O-Notation. Sehr wichtig und im Laufe der Zeit werden Sie im Grunde damit beginnen, es zur zweiten Natur wird dass es zur zweiten Natur wird, sich das einfach ansehen zu können. Du wirst diese anderen nie wirklich oft sehen. Du wirst diesen manchmal sehen, wenn er sagt, dass ein bestimmter Punkt eines Programms dieser Laufzeit entspricht , dann wirst du diesen sehen. Aber abgesehen davon werden diese beiden wahrscheinlich nie und Sie werden den kleinen Mercon Two wahrscheinlich nie sehen Also diese Notizen hier, merken Sie sie sich irgendwie, verstehen Sie, was sie bedeuten, und Sie sollten startklar sein Sie werden anfangen, viel mehr Informatikdokumente zu verstehen Informatikdokumente zu 6. Die echte Welt: Jetzt haben wir eine Menge Theorie gelernt. Lassen Sie uns einen Schritt zurücktreten und einige Codeanalysen aus der realen Welt durchgehen. Nun, ich werde hier keinen komplexen oder irgendeinen Code verwenden , den Sie wissen müssen. Es ist alles Pseudocode, und ich werde es bei jedem Schritt erklären, als ob Sie noch nie zuvor Code angefasst hätten, denn so Sie noch nie zuvor Code angefasst möchte ich diese ganze Art von Kurs erklären, nämlich dass wir die Theorie hinter allem betrachten, nicht den Aber es auf etwas Reales anzuwenden, kann Ihnen helfen, einige der Konzepte herauszufinden, und deshalb machen wir es Schauen wir uns also einfach unseren ersten Code an. Ich werde weitermachen und das hier durchgehen. Was wir haben, ist , dass es heißt, ich habe es in einem Pseudo geschrieben, das sich einfach direkt aus der Zunge liest, etwas, das man sich ansehen und verstehen kann, was vor sich geht Es heißt also, für jeden Datensatz in der Datenliste. Also werden wir hier in einer Sekunde eine Datenliste erstellen und Daten auf den Bildschirm drucken. Okay, einfach genug. Nehmen wir an , wir geben hier eine Datenmenge ein, eine Liste, die vielleicht drei, zwei, zehn ist. Und dann gehen wir nach Buffalo. Also das sind drei ganze Zahlen und eine Zeichenfolge. So wäre es technisch klassifiziert, aber wir werden uns das nicht einmal ansehen Das sind vier Daten. Wir sagen also, dass wir für jede einzelne Information, also für jede einzelne Information in unserer Liste, diese Daten auf den Bildschirm drucken werden. Also, was ist in unserer Situation hier drin? Nun, in dieser Situation hier, Augenhöhe, eins, zwei, drei, vier, weil wir vier Daten haben In dieser Situation ist n also gleich vier. Lassen Sie uns nun sehen, wie lange das dauern würde. Also haben wir für jedes Datenelement, und dann haben wir es auf den Bildschirm gedruckt. Also, okay, lass uns die Liste hier durchgehen. Gehen wir mit unseren ersten Daten fort. Unser erstes Datenelement ist also drei. Wir holen uns hier drei aus unserem Dokumententarif. Also das ist Null in einer Reihe oder wenn Sie darüber nachdenken wollen , das ist eins, zwei, drei, vier, Computer gehen normalerweise mit Null, Eins , Zwei, Drei, so funktionieren sie einfach . Also holen wir uns hier unsere ersten Daten und drucken sie dann auf dem Bildschirm aus. Also schnappen wir uns unsere drei, wir drucken sie auf den Bildschirm. Also das ist eine Laufzeit. Unsere aktuelle Laufzeit ist also eins. Und jetzt werden wir uns die beiden schnappen , weil wir die Liste durchgehen. Also haben wir für jedes Datenelement dieses angefasst. Also gehen wir jetzt zu diesem über. Jetzt schnappen wir uns zwei und drucken auf den Bildschirm. Jetzt sieht unser Bildschirm so aus. Und das ist genau dort eine zusätzliche Laufzeit. Das ist eine Laufzeit. Und dann drucken wir jetzt unser nächstes Datenelement, nämlich zehn. Jetzt haben wir drei, zwei, zehn. Das ist zusätzliche Laufzeit genau dort. Und jetzt drucken wir Buffalo, das wären drei, zwei, zehn Büffel. So wie es ist. Und das ist eine zusätzliche Laufzeit. Weil wir uns nur die Daten schnappen und sie drucken Hier findet kein besonderer Denkprozess statt. Wir schnappen, drucken, schnappen, drucken , schnappen, drucken Und wenn wir das alles zusammenzählen, werden wir sehen, dass es eins plus eins plus eins plus eins ergibt , was Also ist unsere Laufzeit in dieser Situation vier, und Sie werden sehen, dass unsere Laufzeit der hier angegebenen Rate entspricht Und wenn wir nur eine Sekunde theoretisch darüber nachdenken könnten, wenn wir 1 Million Daten hier drin hätten, gäbe es zu keinem Zeitpunkt im Programm, an dem wir jemals mehr als 1 Million Daten berühren müssten zu keinem Zeitpunkt im Programm, an dem wir jemals mehr als 1 Million Daten berühren Egal, was wir hier tun, Laufzeit wird sein, was auch immer unser n ist, was bedeutet, dass wir hier eine Laufzeit von N haben . In dieser speziellen Situation könnten wir Theta tatsächlich als n verwenden, weil es tatsächlich n entspricht. Es gibt hier keinen Spielraum, aber wir werden weitermachen und einfach sagen, dass es im schlimmsten Fall sein wird, weil das die Notation ist im schlimmsten Fall sein wird , die wir gerne verwenden. Das ist also ein Beispiel für einen Eingang , der als Vierschleife bezeichnet wird. Vier Schleifen sind also typischerweise ein Beispiel für ein In in einer Situation. Gehen wir hier zu einem etwas komplexeren Problem über. Lassen Sie mich das auch aufschlüsseln. Was wir hier haben, ist, dass es für jeden Datensatz in einer Datenliste heißt . Das heißt also, anstatt es jetzt Daten zu nennen, wird jedes Datenelement in einer Liste enthalten sein. Prüfen Sie, ob die Daten in der Liste enthalten sind. Also suchen wir nach allen Daten in der Datenliste, wenn n gleich W ist, geben wir true aus Lassen Sie uns also weitermachen und das Ganze auch ein wenig aufschlüsseln Gehen wir mit demselben Beispiel von vorhin fort, das drei, zwei, zehn Buffalo war . So wie es ist. Und in dieser Situation ist unser Sin immer noch gleich vier. Und jetzt werden wir uns das erste Problem hier ansehen . Schauen wir uns das also nach rechts an. Nehmen wir an, wir holen uns jedes einzelne dieser Datenelemente, also holen wir uns die drei, und das ist jetzt drin. Und jetzt für jedes Datenelement in dieser Datenliste, und Sie können sehen, dass diese Namen exakt identisch sind. Das bedeutet also, dass dies die Datenliste ist. Wir suchen nach beiden. Wir haben also unsere drei. Wir haben uns unsere drei geschnappt. Und jetzt versuchen wir zu überprüfen, ob diese drei hier drüben irgendwas hier oben bedeuten. Und das können wir nur mit roher Gewalt tun. Also nehmen wir diese drei. Wir werden es mit dem ersten überprüfen. Wir werden es mit dem zweiten überprüfen. Wir werden es mit dem dritten überprüfen. Wir werden es mit dem vierten überprüfen. Das werden also eine, zwei, drei, vier Operationen sein. Also lass uns das hier, wirklich weit unten, aufschlüsseln . Wir haben unsere drei. Wir haben uns unsere drei geschnappt, und jetzt überprüfen wir, ob es gleichwertig ist Lassen Sie mich das etwas kleiner machen, weil es ein etwas größeres Diagramm sein wird Also sagen wir, ist drei gleich dem ersten Teil unserer Daten, was wieder die Drei sein wird weil wir nicht gesagt haben, dass es mit einer Zahl beginnen soll , die es nicht ist, oder irgendwelchen ausgefallenen Dingen. Wir überprüfen diese Liste gerade ein zweites Mal. Also haben wir unsere drei und wir prüfen, ob sie der ersten entspricht. Also entspricht es drei? Ja, tut es. Das wird also eine wahre Botschaft ausdrucken. Und das erforderte eine Operation. Nun, sind unsere Drei gleich Zwei, ist das nicht. Also drucken wir nichts. Das ist eine Operation. Entsprechen unsere drei zehn? Ist es nicht. Das ist also eine Operation. Entsprechen unsere drei Buffalo? Ist es nicht. Das ist also eine Operation. Und jetzt sind wir mit den dreien fertig. Also haben wir weitergemacht. Wir haben uns um die drei gekümmert. Also lass uns hier unten einen zweiten erstellen. Mal sehen, ob T eins derjenige sein wird , bei dem wir nachfragen. Sie sind genau gleich, aber ich möchte das für euch alle etwas visueller machen. Also sind wir mit den dreien fertig. Also lass uns jetzt zu den Zweien übergehen. Also ist zwei gleich drei? Ist es nicht. Das ist eine Operation. Ist zwei gleich zwei? Das tut es. Das ist eine Operation. Ist zwei gleich zehn? Ist es nicht. Das ist eine Operation. Entspricht zwei Buffalo? Ist es nicht. Das ist eine Operation. Und dann gehen wir die Liste noch einmal durch. Ist zehn gleich drei? Ist das nicht? Das ist eine Operation. Ist zehn gleich zwei, nicht wahr. Das ist eine Operation. Ist zehn gleich zehn. Das tut es. Das ist eine Operation. Ist zehn gleich Buffalo. Ist es nicht. Das ist eine Operation. Das tut Buffalo? Ich werde es hier einfach mit B abkürzen, damit ich Buffalo nicht weiter ausschreiben will Ist Buffalo gleich drei? Ist es nicht. Das ist also eine Operation. Ist Buffalo gleich zwei? Ist es nicht. Das ist also eine Operation. Ist Buffalo gleich zehn? Ist es nicht. Das ist also eine Operation. Ist Buffalo gleich Buffalo? Tut es. Das ist also eine Operation. Und jetzt, wenn wir all diese Erhöhungen hier zusammenzählen, werden wir sehen, dass das eins, zwei, drei, vier, fünf, sechs, sieben, acht, neun, zehn, 11, 12, 13, 14, 15, 16 sein wird. In dieser Situation war unser Input also vier, aber unsere Laufzeit war ungefähr 16. Und was stellt sich heraus? Nun, das stellt sich als quadratisch heraus. Nehmen wir an, wenn wir vier nehmen und die Quadratur machen würden, würde das 16 ergeben. Und darüber können wir theoretisch auch nachdenken. Wenn wir das auf fünf erweitern würden, hätten wir hier nicht nur weitere fünf, sondern wir müssten es multiplizieren, weil wir jetzt auch noch eine weitere überprüfen müssten auch noch eine weitere überprüfen müssten Also jede einzelne Instanz haben wir fünf und wir werden ganze andere fünf haben , was das Ganze quadriert. In dieser Situation ist unsere Laufzeit also quadratisch Und der Grund dafür ist obwohl wir zwei bis vier Schleifen haben, sogenannte Verschachtelung gibt Wir haben eine Viererschleife innerhalb einer weiteren Viererschleife verschachtelt. Also dieser Teil hier draußen. Lass uns das rot zeichnen. Dieser Teil hier draußen ist drin. Dieser Teil drinnen ist aber auch drin. Also nehmen wir das Innere von außen auf. Wir multiplizieren es mit dem Innen auf der Innenseite und wir erhalten das Quadrat Das wird also unsere letzte Laufzeit für diese Situation sein. Also, wie ich schon sagte, dieser Kurs ist nicht stark darauf Code zu schreiben oder zu verwerten, sondern er definiert trotzdem die Theorie, aber ich dachte, das könnte Ihnen helfen, Ihnen zu zeigen, worüber aber ich dachte, das könnte Ihnen helfen wir die ganze Zeit gesprochen haben, wie Code tatsächlich analysiert werden könnte damit wir diese verschiedenen Teile verstehen können Und Sie können sehen, dass wir, egal was passiert, gerade etwas sehr Wichtiges gelernt Vier Schleifen werden immer drin sein, aber verschachtelte vier Schleifen werden immer sein, egal wie viele Verschachtelungen es gibt Wenn diese hier also eine dritte verschachteln würde, wäre das eine n-Quadrat-Formel, und du fängst an, wirklich große Zahlen aufzustellen , um all diese Dinge zu überprüfen Ich hoffe also, dass Ihnen dieses praktische Beispiel geholfen hat, dieses Konzept ein bisschen besser zu verstehen 7. Datenstruktur-Beispiel: Lassen Sie uns nun ein konkreteres Beispiel besprechen. Und wir werden den Unterschied zwischen einem Array und einer Liste besprechen und wie das mit dem zusammenhängt, was wir gelernt haben? Und was wir gelernt haben, ist Skalierbarkeit, Speicherung von Informationen und wie das mit der Laufzeit reagiert , wenn wir zu immer mehr Informationen kommen. Bei diesen beiden Beispielen werden wir uns also ein Array ansehen, und wir werden uns eine Liste ansehen, und wir werden uns ihren Zugriff ansehen und die Backzeiten dieser Arrays erhöhen Wir werden uns also damit befassen, wie sich das im Laufe der Zeit mit diesen beiden unterschiedlichen Arten der Datenspeicherung skalieren lässt? mit diesen beiden unterschiedlichen Arten der Datenspeicherung Wie können wir anhand dieser Analyse herausfinden welche Lösung wir in Zukunft verwenden möchten? Lassen Sie uns einen kurzen Blick darauf werfen. Wir werden einen Überblick darüber geben was diese Datenstrukturen sind, ein sehr leichter Überblick. Sie müssen nicht viel Informatikkenntnisse um dieser Lektion zu folgen, aber es wird sehr wichtig sein, dem, was wir gelernt haben, ein konkretes Element hinzuzufügen . Die erste Datenstruktur , mit der wir uns hier befassen werden , ist also das Array. Bei einem Array holen wir uns also im Grunde ein Stück kontinuierlicher Daten aus unserem Speicher Nun, der Prozessor wird uns im Grunde sagen , wo wir uns das holen werden. Es könnte der RAM sein, es könnte der Cache sein. Es könnte die Festplatte sein. Es spielt keine Rolle. In diesem Fall ist es Erinnerung, und das ist alles, was wir wissen müssen. Beim Speicher teilen wir also im Grunde unseren gesamten Speicher in winzige kleine Datenblöcke auf. Wenn wir den Prozessor nach einem Array fragen, sucht er ein kleines Stück Speicher für uns. Das ist kontinuierlich und kann zu dem passen, was wir anfordern. In diesem Fall fordern wir hier vier Daten an. Es ist also eine Array-Größe von vier. Wenn wir das tun, erstellen wir es kontinuierlich, aber auf der anderen Seite haben wir keinen Zugriff darauf, was bedeutet, dass wir, wenn wir die Größe dieses Arrays erhöhen müssen , ein brandneues Array erstellen und Dinge darauf kopieren müssen. Und das wird der Nachteil sein. Lassen Sie uns also unsere beiden hier durchgehen, unseren Zugang und unsere Anzeige. Wann immer wir also auf Daten in einem Array zugreifen, ist das Tolle daran, dass es in konstanter Zeit erfolgt, denn wann immer wir danach fragen, ist es kontinuierlich. Daher können wir hier nach ganz bestimmten Daten fragen . Wenn wir also herausfinden müssen, ob wir etwas von der zweiten oder von dieser Position, der dritten Stelle in der Reihe, nehmen müssen von der zweiten oder von dieser Position, der dritten Stelle in der Reihe, , die mit zwei indexiert ist Das bedeutet einfach, dass alles in der Informatik einen Null-Index hat, also ist die erste Spalte Null, nicht Eins Wir können hier mit dieser kleinen Formelrate arbeiten, die im Grunde in jeder einzelnen Programmiersprache funktioniert . Es heißt nur, schnappen Sie sich das Element genau dort. Es wird es uns in konstanter Zeit zurückgeben. Es wird im Grunde genommen in konstanter Zeit ausspucken , was genau da Wir könnten Tonnen und Tonnen von Informationen haben. Das könnte 2000 lang sein. Das könnte 3.000 lang sein. Das könnten 20.000 bis 30.000$ sein und so weiter und so fort. Und wenn wir das einfach hier reinschreiben, bekommen wir es jedes Mal konstant zurück Und das ist es, was unserem Array ermöglicht , im schlimmsten Fall auf konstante Zeit zuzugreifen. Es wird immer konstant sein. Nun, hier ist das Problem. Denken Sie daran, dass ich gesagt habe, wenn wir am Ende hinzufügen, wenn wir unser Array-Limit erreicht haben, wir das Array aufgefüllt haben, müssen wir ein brandneues Array anfordern, was bedeutet, dass das Speichermodul einfach unser altes Array zerstört und dann ein größeres Array findet , in das wir Informationen einfügen können. Nun, um sicherzustellen, dass wir unsere alten Daten nicht verlieren, müssen wir jedes einzelne Stück kopieren. Mehr als eins nach dem anderen. Wenn wir also 300.000, 3 Millionen, 3 Milliarden Einträge haben, müssen sie alle kopiert werden, und jedes Datenelement hier muss angefasst werden Und das ist sehr, sehr wichtig, denn das bedeutet, dass mit der Größe unseres Arrays, der Anzahl der Eingaben, die wir haben, auch die Anzahl der Operationen, die wir verwenden müssen, zunimmt Und sie nimmt linear zu , was bedeutet, dass wir beim Hinzufügen zu einem Array ein Worst-Case-Szenario von O zu haben haben . Jetzt haben wir das Array also ziemlich gut abgedeckt. Schauen wir uns hier unten unsere andere Datenstruktur an. Die Liste. Die Liste ist interessant , denn was wir mit einer Liste machen , ist, dass wir hier im Wesentlichen zu unseren Daten gehen. Wir fordern sie an. Und anstatt uns kontinuierlich Daten zu geben, gibt es uns im Grunde ein Element nach dem anderen. Also können wir eins anfordern, es wird hier sein. Wir fordern einen anderen an. Es erzeugt einen Zeiger und geht dann zu diesem Teil. Wir wollen noch einen. Nun, es wird hier drüben gehen und so weiter und so fort. Und Sie können sehen, dass es keinen wirklich festgelegten Weg gibt, wie das geschehen soll. Ich bin mir sicher, dass die fortschrittlichen Speichermodule und all diese Dinge effizient funktionieren, aber sie werden nicht kontinuierlich funktionieren. Sie werden überall sein, und zwar auf die effizienteste Art und Weise, die es für richtig hält. Das heißt, wenn wir versuchen, auf unsere Informationen zuzugreifen und uns diese Information hier schnappen wollen, nun, schauen Sie sich das Chaos hier an. Wir müssen dem Punkt folgen. Also müssen wir hier anfangen und hier weitermachen. Dann hier, dann hier, dann hier. Und, Oh, da sind unsere Daten. Und das bedeutet, wenn wir auf unsere Daten zugreifen, wenn wir versuchen, etwas weiter unten in der Liste zu finden, etwas weiter weg, und, wissen Sie, es könnte so etwas wie eine Zahl, ein Buchstabe, ein Satz, ein Bild, irgendwas Lassen Sie uns hier einfach PE platzieren. Um zu P zu gelangen, müssen wir die gesamte verknüpfte Liste ausführen , um sie zu finden. Was ist also unsere Zugriffszeit? Also, das klingt nicht konstant. Das klingt so, als ob mit zunehmender Anzahl der Elemente auch unsere Zugriffszeit wächst, was so aussieht, als ob es Zugriff im schlimmsten Fall sein wird, also eine lineare Zeit bis zum Eingang. Nun hat die Liste den Vorteil des Arrays beim Hinzufügen, solange wir einen sogenannten Back-Pointer beibehalten, im Grunde nur ein Datenelement ist, das wir aktualisieren, sodass es sich um einen direkten Pfeil nach hinten handelt. Wenn wir also ein neues Stück hinzufügen, nehmen wir im Grunde einfach diesen Pfeil und verschieben es einfach zu dem neuen Teil. Wenn wir das auf dem neuesten Stand halten, was nur ein einziger konstanter Vorgang ist, nun ja, das Hinzufügen von Daten ist konstante Zeit. Es wird immer exakt dieselbe Operation sein. Wir zeigen auf die Rückseite und fügen die nächste hinzu. Eigentlich tun wir das in diesem Fall nicht. Ja, ja, das tun wir. Also haben wir hier den Backpointer. Wenn wir also etwas auf der Rückseite hinzufügen müssen, folgen wir dem Rückzeiger bis zum Ende der Linkliste, und dann fügen wir einfach ein neues Element hinzu und aktualisieren dann den Zeiger auf das neue Element. Es ist ein ständiger Vorgang. Es sind zwar ein paar Schritte drin, es wird immer dasselbe sein. Wenn es 1 Milliarde Teile oder ein Stück gibt, müssen genau die gleichen Dinge passieren. Wir folgen dem hinteren Zeiger, fügen einen neuen und fügen dann unsere Daten hinein. Das bedeutet also, dass unsere zusätzliche Zeit tatsächlich konstant sein wird . Jetzt können wir also sehen, dass wir mit diesen beiden Datenstrukturen hier zwei verschiedene Lösungsmöglichkeiten haben. Wenn wir eine schnelle Zugriffszeit benötigen, denken Sie an die Liste in Ihrem Telefon, Ihre Kontaktliste in Ihrem Telefon. Wir brauchen dafür eine schnelle Zugriffszeit. Sie möchten nicht jemanden in Ihrer Kontaktliste finden und warten müssen, bis er alle anderen Daten durchsucht. Das klingt überhaupt nicht so, als wäre es sehr effizient. Das wäre albern. Und wir fügen es nicht oft hinzu. Wissen Sie, wir fügen hier und da einen Kontakt hinzu, aber das ist nicht etwas, was wir ständig und immer wieder hinzufügen. Das Array könnte also die beste Lösung für dieses spezielle Problem sein. Nun, mit einer Liste, haben wir vielleicht eine Operation, die speichern muss Laufe der Zeit viele, viele Elemente speichern muss, aber kaum jemals auf sie zugreifen muss. Wir brauchen also konstante, Sie wissen schon, zusätzliche Zeit, aber wir brauchen nicht wirklich viel Zugriffszeit. Nun, dann würden wir uns eine Liste für diese Lösung ansehen. Die Dinge, die wir dabei lernen, können also genutzt werden , um bessere Lösungen für unsere Probleme zu finden. Und in diesem speziellen Fall handelt es sich um Speicherprobleme bei der Computerprogrammierung. Dies kann jedoch auch für andere Bereiche der Computerwelt und für das reale Leben gelten . Die Lösung, die Sie haben, ist skalierbar. Und damit können wir sehen , welche es sind und welche nicht. 8. Projektvideo: Jetzt, wo wir Notation, Fanatismus und all die Skalierung dazwischen durchgegangen und all die Skalierung dazwischen Das Projekt hier wird darin bestehen, alles, was Sie in Ihrem Leben gelernt haben, zu analysieren und in Ihrem Leben gelernt haben, zu analysieren uns zu sagen, wie es abläuft und was dann der Zeitpunkt ist. Das kann also mit Informatik zu tun haben. Du könntest einen Algorithmus, einen Suchalgorithmus verwenden oder darüber nachdenken, du weißt schon, wie eine Facebook-Freundschaftsanfrage funktionieren könnte oder so, aber es kann auch einfach nur beobachtend um dich herum sein kann so sein, wie ich es zu Beginn des Kurses gesagt habe, wie ein Aktenschrank oder wie jemand einem Mitglied Ihrer Organisation beitreten könnte, oder wie Sie entweder in einem großen Datensatz oder einer Gruppe von Personen oder etwas Ähnlichem suchen und etwas Ähnliches finden entweder in einem großen Datensatz oder einer Gruppe von Personen oder etwas Ähnlichem suchen und etwas Ähnliches Ich möchte, dass du kreativ bist und einfach die Welt um dich herum mit dem Wissen, das du gelernt hast, analysierst die Welt um dich herum mit dem Wissen, das du und es weitergibst Es ist eine ziemlich lustige Übung und es ist ziemlich nett zu sehen, dass wir im Grunde nur angewandte Mathematik machen wann immer wir programmieren oder mit dieser Art von Theorie der Mathematik selbst arbeiten . Wenn wir es anwenden, lernen wir, wie die Welt funktioniert und funktioniert, und dann beschäftigen wir uns damit. Und genau darum geht es bei diesem Projekt. Um ein kritisches Denken zu entwickeln und es dann zu analysieren und das Gelernte irgendwie zu bekräftigen. Ich bin wirklich gespannt, was sich alle einfallen lassen, und ich werde im Projektbereich darauf eingehen. Also, Meer, danke allen , dass sie an diesem Kurs teilgenommen haben.