Na gut, so, Berechnungskomplexität. Nur ein bisschen eine Warnung Bevor wir uns in zu far-- Diese werden wahrscheinlich unter sein Die Mathematik-schwere Dinge wir über in CS50 sprechen. Hoffentlich wird es nicht zu überwältigend sein und wir werden versuchen, und führen Sie durch den Prozess, aber nur ein bisschen eine faire Warnung. Es ist ein bisschen Mathe hier beteiligt. Na gut, so, damit Verwendung unserer Rechenressourcen in der realen world-- es wirklich wichtig, um Algorithmen zu verstehen und wie sie Prozessdaten. Wenn wir eine wirklich effizienten Algorithmus, wir kann die Menge an Ressourcen zu minimieren wir zur Verfügung haben, damit umzugehen. Wenn wir einen Algorithmus, wird eine Menge Arbeit um wirklich zu verarbeiten ein große Menge von Daten, ist es gehen, um mehr erforderlich und mehr Ressourcen, die ist Geld, RAM, all solche Sachen. 

Also, in der Lage, eine Analyse Algorithmus mit diesem Werkzeug-Set, Grundsätzlich fordert die question-- wie funktioniert dieser Algorithmus Skala wie wir mehr und mehr Daten um sich werfen? In CS50, die Menge der Daten sind wir Arbeiten mit ist ziemlich klein. Im Allgemeinen werden unsere Programme gehen um in einer zweiten oder less-- laufen wahrscheinlich viel weniger besonders früh. 

Aber zu einer Firma, die Angebote zu denken Hunderte von Millionen von Kunden. Und sie brauchen, um zu verarbeiten dass Kundendaten. Als die Anzahl der Kunden, die sie haben wird größer und größer, es wird erforderlich mehr und mehr Ressourcen. Wie viele Ressourcen? Nun, das hängt davon ab, wie analysieren wir den Algorithmus, mit Hilfe der Tools in dieser Toolbox. Wenn wir von der Komplexität der zu sprechen ein algorithm-- was manchmal werden Sie hören es an der Zeit bezeichnet Komplexität und Speicherkomplexität aber wir sind gerade dabei zu rufen complexity-- wir sind in der Regel reden das Worst-Case-Szenario. Angesichts der absolute worst Haufen Daten, die wir auf sie zu werfen, wie wird dieser Algorithmus würde verarbeiten oder sich mit diesen Daten? Wir das Worst-Case-rufen in der Regel Laufzeit eines Algorithmus big-O. So könnte ein Algorithmus zu sagen laufen in O n oder O n quadriert. Und mehr über das, was diejenigen bedeuten, in einem zweiten. 

Manchmal aber geht uns über das Best-Case-Szenario. Wenn die Daten alles, was wir wollten es zu sein und es war absolut perfekt und wir senden diesen perfekten Set von Daten über unser Algorithmus. Wie wäre es in dieser Situation umgehen? Wir beziehen uns manchmal, dass als Big-Omega, so im Gegensatz zu Big-O, Wir haben big-Omega. Big-Omega für den besten Fall. Big-O für den Fall der Fälle. Im Allgemeinen, wenn wir sprechen Die Komplexität eines Algorithmus, wir über das reden Worst-Case-Szenario. So sollte man das im Hinterkopf. 

Und in dieser Klasse, wir sind in der Regel gehen um die strengen Analyse beiseite zu lassen. Es gibt Wissenschaften und Felder um diese Art von Sachen gewidmet. Wenn wir über die Gründe sprechen durch Algorithmen, was wir Stück für Stück für viele zu tun Algorithmen, wir sprechen in der Klasse. Wir sind wirklich nur darüber zu reden Argumentation durch sie mit gesundem Menschenverstand, nicht mit Formeln, oder Beweise, oder so etwas. Also keine Sorge, wir werden nicht sich in einen großen Math-Klasse. 

Also sagte ich: wir über die Komplexität Pflege weil sie die Frage, wie verlangt haben unsere Algorithmen umgehen größer und wobei größere Datenmengen auf sie geworfen. Nun, was ist ein Datensatz? Was habe ich meine, wenn ich das gesagt? Es bedeutet, was auch immer das macht Sinn im Kontext, um ehrlich zu sein. Wenn wir einen Algorithmus, der Prozesse Strings-- wir wahrscheinlich reden über die Größe der Zeichenfolge. Das ist die Daten-Satz-- Die Größe, die Anzahl von Zeichen, aus denen sich die Schnur. Wenn wir über ein Gespräch Algorithmus, der Dateien verarbeitet, könnten wir darüber, wie sprechen viele Kilobytes umfassen diese Datei. Und das ist der Datensatz. Wenn wir über einen Algorithmus im Gespräch daß Griffe Arrays allgemeiner wie Sortieralgorithmen oder Suchalgorithmen, Wir sind wahrscheinlich über die Anzahl Gespräche Elemente, die ein Array umfassen. 

Jetzt können wir ein zu messen algorithm-- insbesondere wenn ich sage, wir können messen einen Algorithmus, I bedeuten, können wir messen, wie viele Ressourcen nimmt es. Ob diese Ressourcen sind, wie viele Byte RAM-- oder Megabyte RAM es verwendet. Oder wie viel Zeit es braucht, um laufen. Und wir können diesen Aufruf zu messen, beliebig, f n. Wobei n die Anzahl von Elemente in der Datenmenge. Und f n ist, wie viele Jährigen. Wie viele Einheiten von Ressourcen funktioniert sie erfordern, um diese Daten zu verarbeiten. 

Nun, wir eigentlich egal über das, was f n ist genau. In der Tat, sehr selten will-- wir wird sicherlich nie in dieser class-- I tauchen Sie ein in jeder wirklich tief Analyse, was f von n ist. Wir sind gerade dabei, über das, was f sprechen n ungefähr oder was es dazu neigt. Und die Tendenz eines Algorithmus ist von seinem höchsten Reihenfolge tige diktiert. Und wir können sehen, was ich damit meine, indem sie einen Blick auf ein konkreteres Beispiel. 

Also lassen Sie uns sagen, dass wir drei verschiedene Algorithmen. Von denen die erste dauert n in Würfel geschnitten, einige Einheiten der Ressourcen um einen Datensatz der Größe n zu verarbeiten. Wir haben einen zweiten Algorithmus, der findet n hoch drei plus n quadriert Ressourcen um einen Datensatz der Größe n zu verarbeiten. Und wir haben ein Drittel Algorithmus, der in--, dass läuft nimmt n gewürfelt minus 8n Quadrat plus 20 n Einheiten von Ressourcen einen Algorithmus zu verarbeiten, mit Datensatz der Größe n. 

Jetzt wieder, wir wirklich nicht gehen, in diesem Detailgrad zu erhalten. Ich bin wirklich nur noch diese bis hier als Illustration eines Punktes daß ich werde sein was in einer zweiten, der ist, dass wir nur wirklich interessieren über die Tendenz der Dinge da die Datenmengen immer größer. Also, wenn die Datenmenge ist klein, es gibt eigentlich ein ziemlich großer Unterschied in dieser Algorithmen. Der dritte Algorithmus gibt dauert 13 mal länger, 13-fache der Menge an Ressourcen, zu laufen, bezogen auf die erste. 

Wenn Sie unsere Datensatz Größe 10, die ist größer, aber nicht unbedingt riesig, können wir sehen, dass es eigentlich ein bisschen von einem Unterschied. Der dritte Algorithmus wird effizienter. Es geht darum, tatsächlich 40% - oder 60% effizienter. Es dauert 40% der Menge an Zeit. Es kann run-- es dauern kann 400 Einheiten von Ressourcen um einen Datensatz der Größe 10 zu verarbeiten. Während die erste Algorithmus hingegen nimmt 1.000 Einheiten von Ressourcen um einen Datensatz der Größe 10 zu verarbeiten. Aber schauen Sie, was passiert, als unsere Zahlen noch größer. 

Nun wird die Differenz zwischen diesen Algorithmen beginnen, etwas weniger deutlich. Und die Tatsache, dass es niedrigerer Ordnung terms-- oder besser gesagt, Begriffe mit niedrigeren exponents-- starten irrelevant zu werden. Wenn ein Datensatz ist von der Größe 1000 und der erste Algorithmus läuft in eine Milliarde Schritte. Und der zweite Algorithmus läuft in eine Milliarde und eine Million Schritte. Und der dritte Algorithmus läuft in knapp einer Milliarde Schritte. Es ist so ziemlich eine Milliarde Schritte. Diese Terme niedrigerer Ordnung zu starten um wirklich irrelevant werden. Und nur um wirklich hammer haupt die point-- Wenn der Dateneingang der Größe A million-- alle drei von ihnen ziemlich viel nehmen Sie eine quintillion-- wenn meine Mathe ist correct-- Schritte mit einem Dateneingang zu verarbeiten der Größe einer Million. Das ist eine Menge von Schritten. Und die Tatsache, dass einer von ihnen könnte nehmen Sie ein paar 100.000 oder ein paar 100 Millionen noch weniger, wenn wir über eine Reihe sprechen dass big-- es irgendwie irrelevant ist. Sie alle sind in der Regel übernehmen ca. n in Würfel geschnitten, und so haben wir eigentlich beziehen würde Für alle diese Algorithmen als in der Größenordnung von n gewürfelt oder Big-O von n gewürfelt. 

Hier ist eine Liste von einigen der mehr gemeinsame Komplexitätsklassen dass wir stoßen in Algorithmen, in der Regel. Und auch speziell in CS50. Diese werden aus bestellt in der Regel am schnellsten an der Spitze, allgemein langsamsten an der Unterseite. So konstante Zeit-Algorithmen sind in der Regel die am schnellsten zu sein, unabhängig davon, von der Größe des Dateneingabe Sie übergeben in. Sie einem Arbeitsgang erfolgen immer oder eine Einheit von Ressourcen, zu beschäftigen. Es kann 2 sein, könnte es 3 sein, könnte es vier sein. Aber es ist eine konstante Zahl. Sie ändert sich nicht. 

Logarithmischen Zeitalgorithmen sind etwas besser. Und ein wirklich gutes Beispiel dafür, einen logarithmischen Algorithmus Sie haben sicherlich inzwischen gesehen, ist die Auseinanderreißen des Telefonbuchs Mike Smith im Telefonbuch zu finden. Wir schneiden das Problem in zwei Hälften. Und so, n größer wird und größer und larger-- in der Tat, jedes Mal wenn Sie verdoppeln n, dauert es nur noch ein Schritt. Also das ist viel besser als, sagen wir, die lineare Zeit. Das ist, wenn Sie n verdoppeln, es nimmt die doppelte Anzahl von Schritten. Wenn Sie n verdreifachen, dauert es Verdreifachung der Anzahl der Schritte. Einen Schritt pro Einheit. 

Dann wird es ein wenig more-- etwas weniger von dort super. Sie haben lineare rhythmische Zeit, manchmal genannt log lineare Zeit oder einfach nur n log n. Und wir werden ein Beispiel eines Algorithmus, läuft in n log n, die noch besser ist, als quadratische Zeit-- n quadriert. Oder polynomialer Zeit, n zwei beliebige Zahl größer als zwei ist. Oder exponentieller Zeit, die Noch C bis worse-- der n. So angehoben einige konstante Anzahl die Leistung der Größe der Eingabe. Also, wenn es 1,000-- wenn die Dateneingabe der Größe 1000, sie zur Preis 1000. Macht zu übernehmen C. Es ist viel schlimmer als Polynomialzeit. 

Factorial Es ist noch schlimmer. Und in der Tat, es gibt wirklich tun existieren unendliche Zeit-Algorithmen, wie beispielsweise so genannte dumme sort-- deren Aufgabe ist es, nach dem Zufallsprinzip Shuffle ein Array und dann überprüfen Sie, ob es sortiert. Und wenn es nicht, nach dem Zufallsprinzip mische das Array wieder und überprüfen Sie, ob es sortiert. Und wie Sie wahrscheinlich imagine-- können Sie können eine Situation vorstellen, wobei im schlimmsten Fall, dass Wille nie wirklich mit dem Array zu starten. Das Algorithmus würde ewig laufen. Und damit wäre ein unendliche Zeit-Algorithmus. Hoffentlich werden Sie nicht zu schreiben jede Fakultät oder unendliche Zeit Algorithmen in CS50. 

Also, lassen Sie uns ein wenig mehr Beton Blick auf einige einfachere Komplexitätsklassen. So haben wir eine example-- oder zwei Beispiele hier-- der konstante Zeitalgorithmen, die immer nehmen eine einzige Operation in der Worst-Case. So die erste example-- wir eine Funktion haben genannt 4 für Sie, die nimmt ein Array der Größe 1.000. Aber dann offenbar nicht wirklich aussehen bei es-- nicht wirklich, was ist innen von ihm, dieses Arrays. Immer nur liefert vier. So, dass Algorithmus trotz der Tatsache, daß es nimmt 1000 Elemente nicht nichts mit ihnen. Nur gibt vier. Es ist immer ein Schritt. 

In der Tat, fügen Sie 2 nums-- die wir zuvor als well-- gesehen haben gerade verarbeitet zwei ganzen Zahlen. Es ist nicht ein Schritt. Es ist eigentlich ein paar Schritte. Sie erhalten ein, erhalten Sie b, Sie sie hinzufügen zusammen, und du Ausgabe der Ergebnisse. So ist es 84 Stufen. Aber es ist immer konstant, unabhängig von a oder b. Du musst ein, bekommen b, fügen sie zusammen, das Ergebnis auszugeben. Also das ist eine konstante Zeit-Algorithmus. 

Hier ist ein Beispiel für ein linearen Zeit algorithm-- ein Algorithmus, der gets-- das braucht einen zusätzlichen Schritt, gegebenenfalls, wie Ihr Eingangs wächst um 1. Also, sagen wir, wir suchen die Nummer 5 innerhalb eines Arrays. Vielleicht haben Sie eine Situation, wo haben Sie ziemlich früh zu finden. Aber Sie haben auch könnte eine Situation, wo es könnte das letzte Element des Arrays. In einer Anordnung von der Größe 5, wenn wir sind für die Zahl 5 suchen. Es würde 5 Stufen. Und in der Tat, sich vorstellen, dass es 5 nicht überall in diesem Array. Wir haben immer noch tatsächlich haben, zu betrachten Jedes einzelne Element des Arrays um zu bestimmen, ob oder ob nicht 5 ist da. 

Also im ungünstigsten Fall, der das ist das Element in dem Array letzten oder überhaupt nicht existieren. Wir haben immer noch zu sehen alle der n Elemente. Und so dieser Algorithmus läuft in linearer Zeit. Sie können das bestätigen Extrapolation ein wenig mit den Worten: wenn wir eine 6-Element-Array und wurden wir für die Zahl 5 suchen, sie treffen könnte, 6 Stufen. Wenn wir eine 7-Elementanordnung und wir sind für die Zahl 5 suchen. Es könnte dauern 7 Schritten. Da wir ein weiteres Element hinzuzufügen, um unsere Array, dauert es noch ein Schritt. Das ist ein linearer Algorithmus im ungünstigsten Fall. 

Paar kurze Fragen für Sie. Was ist der runtime-- was ist das Worst-Case-Laufzeit dieses bestimmten Code-Snippet? So habe ich eine 4-Schleife, die hier läuft von j gleich 0 ist, den ganzen Weg bis zum m. Und was ich hier sehen, ist, dass die Rumpf der Schleife läuft in konstanter Zeit. So mit der Terminologie, wir haben bereits about-- was gesprochen würde im schlimmsten Fall sein, Laufzeit dieses Algorithmus? Nehmen Sie eine Sekunde. Der innere Teil der Schleife läuft in konstanter Zeit. Und der äußere Teil der Schleife wird sich m-mal ausgeführt. Also, was ist das Worst-Case-Laufzeit hier? Haben Sie Big-O von m erraten? Sie würden Recht haben. 

Wie wäre es mit einem anderen? Dieses Mal haben wir ein Schleife innerhalb einer Schleife. Wir haben eine äußere Schleife das läuft von null auf p. Und wir haben eine innere Schleife, die läuft von Null auf P, und im Inneren davon, Ich behaupte, dass der Körper die Schleife läuft in konstanter Zeit. Also, was ist das Worst-Case-Laufzeit dieses bestimmten Code-Snippet? Nun, wieder haben wir ein äußere Schleife, die p-mal ausgeführt wird. Und jeder Iteration Zeit-- dieser Schleife statt. Wir haben eine innere Schleife dass auch läuft p Zeiten. Und dann im Inneren der, dass, gibt es das Konstante Zeit-- kleine Ausschnitt gibt. 

Wenn wir also eine äußere Schleife, läuft p-mal innerhalb von denen ist eine innere Schleife, läuft p times-- was das Worst-Case-Laufzeit dieser Code-Snippet? Haben Sie big-O p denke Quadrat? 

Ich bin Doug Lloyd. Dies ist CS50.