1 00:00:00,000 --> 00:00:05,760 2 00:00:05,760 --> 00:00:08,900 >> DOUG LLOYD: Also in CS50 wir gelernt, eine Vielzahl von Sortieren und Suchen 3 00:00:08,900 --> 00:00:09,442 Algorithmen. 4 00:00:09,442 --> 00:00:11,400 Und manchmal ist es sein kann, ein wenig schwierig zu halten 5 00:00:11,400 --> 00:00:14,161 verfolgen, was Algorithmus tut, was. 6 00:00:14,161 --> 00:00:15,910 Wir haben eigentlich nur Mager die Oberfläche zu, 7 00:00:15,910 --> 00:00:18,740 es gibt viele andere Such und Sortieralgorithmen. 8 00:00:18,740 --> 00:00:21,780 Also in diesem Video lassen nur ein paar Minuten in Anspruch nehmen 9 00:00:21,780 --> 00:00:24,980 um zu versuchen und zu destillieren jeder Algorithmus bis auf die Kernelemente 10 00:00:24,980 --> 00:00:27,810 so dass Sie die meisten erinnern kann wichtige Informationen über sie 11 00:00:27,810 --> 00:00:31,970 und in der Lage, das zu artikulieren Unterschiede, falls erforderlich. 12 00:00:31,970 --> 00:00:34,220 >> Die erste ist die Auswahl sortieren. 13 00:00:34,220 --> 00:00:38,210 Die Grundidee hinter Auswahl sort ist der kleinste unsortierte Element zu finden 14 00:00:38,210 --> 00:00:42,890 in einem Array und tauschen Sie sie mit der zunächst unsortierte Element des Arrays. 15 00:00:42,890 --> 00:00:46,620 Wir haben gesagt, dass die Worst-Case- Laufzeit der das war n quadriert. 16 00:00:46,620 --> 00:00:50,060 Und wenn Sie sich daran erinnern, warum möchten, nehmen Sie einen Blick auf die Auswahl sort Video. 17 00:00:50,060 --> 00:00:54,560 Die Best-Case-Laufzeit wird auch n quadriert. 18 00:00:54,560 --> 00:00:58,910 >> Bubble-Sort, die Idee dahinter, dass eine ist es, benachbarte Paare tauschen. 19 00:00:58,910 --> 00:01:01,730 Also das ist der Schlüssel, das Ihnen hilft erinnere mich an den Unterschied. 20 00:01:01,730 --> 00:01:04,920 Auswahl Sortierung, so weit, finden Sie das smallest-- Blase 21 00:01:04,920 --> 00:01:06,790 Sortierung Swap benachbarte Paare. 22 00:01:06,790 --> 00:01:08,710 Wir tauschen benachbarte Paare von Elementen, wenn sie 23 00:01:08,710 --> 00:01:12,530 sind nicht in Ordnung, die effektiv Blasen größeren Elementen auf der rechten Seite, 24 00:01:12,530 --> 00:01:17,060 und zur gleichen Zeit beginnt auch kleinere Elemente links zu bewegen. 25 00:01:17,060 --> 00:01:20,180 Das Worst-Case-Fall der Laufzeit der Bubble-Sort ist n quadriert. 26 00:01:20,180 --> 00:01:23,476 Die Best-Case-Laufzeit der Bubble-Sort ist n. 27 00:01:23,476 --> 00:01:25,350 Da in dieser Situation wir wissen nicht actually-- 28 00:01:25,350 --> 00:01:27,141 wir nicht brauchen, um nehmen Sie die Swaps überhaupt. 29 00:01:27,141 --> 00:01:31,026 Wir haben nur eine zu machen Pass für alle n-Elemente. 30 00:01:31,026 --> 00:01:34,600 >> In Insertion Sort, dem Grundidee dabei verlagert. 31 00:01:34,600 --> 00:01:36,630 Das ist das Stichwort für die Insertion sort. 32 00:01:36,630 --> 00:01:39,630 Wir werden einmal durch Schritt die Anordnung von links nach rechts. 33 00:01:39,630 --> 00:01:41,670 Und wie wir es tun, wir sind gehen, um Elemente zu verschieben 34 00:01:41,670 --> 00:01:46,260 Wir haben bereits gesehen, um Platz für kleinere, die irgendwo passen müssen 35 00:01:46,260 --> 00:01:48,080 zurück in die sortiert Teil. 36 00:01:48,080 --> 00:01:51,600 So bauen wir die sortierten Array ein Element nach dem anderen, von links nach rechts, 37 00:01:51,600 --> 00:01:54,740 und wir verschieben die Dinge um Platz zu schaffen. 38 00:01:54,740 --> 00:01:58,650 Das Worst-Case-Laufzeit Insertion Sort ist n quadriert. 39 00:01:58,650 --> 00:02:02,380 Die Best-Case-Laufzeit ist n. 40 00:02:02,380 --> 00:02:05,380 >> Merge sort-- dem Schlüsselwort Hier wird geteilt und zusammenzuführen. 41 00:02:05,380 --> 00:02:08,949 Wir teilen Sie die ganze Palette, ob es sechs Elemente, acht Elemente, 42 00:02:08,949 --> 00:02:13,790 10.000 elements-- wir sie aufteilen um die Hälfte, die Hälfte, die Hälfte, 43 00:02:13,790 --> 00:02:17,720 bis wir unter Array n ein Element-Arrays. 44 00:02:17,720 --> 00:02:19,470 Ein Satz von n ein Element-Arrays. 45 00:02:19,470 --> 00:02:22,640 Also mit einem begannen wir 1000-Elementanordnung, 46 00:02:22,640 --> 00:02:26,550 und wir an den Punkt gelangen, wo wir haben 1.000 Ein-Element-Arrays. 47 00:02:26,550 --> 00:02:30,990 Dann beginnen wir, diese Unterfelder zusammenführen wieder zusammen in der richtigen Reihenfolge. 48 00:02:30,990 --> 00:02:34,860 Also nehmen wir zwei Ein-Element-Arrays und erstellen Sie ein Array mit zwei Elementen. 49 00:02:34,860 --> 00:02:38,180 Wir nehmen zwei Zwei-Element-Arrays und erstellen Sie ein Vier-Element-Array 50 00:02:38,180 --> 00:02:43,900 und so weiter und so weiter, bis wir wieder aufgebaut einer n Elementanordnung. 51 00:02:43,900 --> 00:02:48,410 >> Das Worst-Case-Laufzeit Mergesort n mal log n. 52 00:02:48,410 --> 00:02:52,390 Wir haben n Elemente, aber Diese Rekombination Prozess 53 00:02:52,390 --> 00:02:56,960 nimmt log n Schritten zur Bewertung erhalten zurück auf eine vollständige Palette. 54 00:02:56,960 --> 00:03:01,160 Im besten Fall die Laufzeit ist auch n log n, da dieser Prozess nicht wirklich 55 00:03:01,160 --> 00:03:04,090 egal, ob die Anordnung war sortiert oder nicht, mit zu beginnen. 56 00:03:04,090 --> 00:03:07,590 Das Verfahren ist das gleiche, es ist keine Möglichkeit, Kurzschluss Dinge. 57 00:03:07,590 --> 00:03:11,610 SO n log n im schlimmsten Fall, n log n im besten Fall. 58 00:03:11,610 --> 00:03:13,960 >> Wir sprachen über zwei Suchalgorithmen. 59 00:03:13,960 --> 00:03:16,230 So lineare Suche ist etwa Iteration. 60 00:03:16,230 --> 00:03:19,500 Wir gehen über das Array einmal, von links nach rechts, 61 00:03:19,500 --> 00:03:21,950 versuchen, die Zahl zu finden dass wir suchen. 62 00:03:21,950 --> 00:03:24,550 Das Worst-Case-Laufzeit ist ein großes O n. 63 00:03:24,550 --> 00:03:27,610 Es könnte uns zu nehmen Iteration für jedes einzelne Element 64 00:03:27,610 --> 00:03:30,660 um das Element wir zu finden für die entweder in der letzten Position, 65 00:03:30,660 --> 00:03:31,630 oder gar nicht. 66 00:03:31,630 --> 00:03:34,720 Aber wir können nicht bestätigen, dass bis wir haben alles angesehen. 67 00:03:34,720 --> 00:03:36,730 m das Best-Case, so finden wir sofort. 68 00:03:36,730 --> 00:03:41,060 Die Best-Case-Laufzeit lineare Suche ist Omega von 1. 69 00:03:41,060 --> 00:03:43,689 >> Schließlich gab es binäre Suche, was erfordert, sortierten Array. 70 00:03:43,689 --> 00:03:45,605 Denken Sie daran, das ist eine sehr wichtige Überlegung 71 00:03:45,605 --> 00:03:47,155 bei der Arbeit mit binären Suche. 72 00:03:47,155 --> 00:03:50,180 Es ist eine Voraussetzung, um mit es-- das Array, das Sie durch suchen 73 00:03:50,180 --> 00:03:52,160 muss sortiert werden. 74 00:03:52,160 --> 00:03:54,500 Andernfalls wird das Keyword- ist teile und herrsche. 75 00:03:54,500 --> 00:03:58,310 Teilen Sie das Array in der Mitte und beseitigen Hälfte der Elemente 76 00:03:58,310 --> 00:04:00,780 jedes Mal, wenn Sie durch gehen. 77 00:04:00,780 --> 00:04:04,330 Aufgrund dieser Teile und Herrsche und Spaltung Dinge im Halb Ansatz, 78 00:04:04,330 --> 00:04:07,450 das Worst-Case-Laufzeit der binären Suche ist 79 00:04:07,450 --> 00:04:11,730 log n, das im wesentlichen besser als lineare Suche von n. 80 00:04:11,730 --> 00:04:13,570 Die Best-Case-Laufzeit ist immer noch einer. 81 00:04:13,570 --> 00:04:17,010 >> Wir könnten sie sofort das finden Erstmals machen wir eine Sparte, aber, 82 00:04:17,010 --> 00:04:19,339 wieder daran erinnern, dass obwohl binäre Suche ist 83 00:04:19,339 --> 00:04:24,030 wesentlich besser als lineare Suche aufgrund des Seins log n gegen n, 84 00:04:24,030 --> 00:04:27,110 Sie haben könnten, um durch die Arbeit zu gehen Sortier Ihr Array erste, was 85 00:04:27,110 --> 00:04:32,010 könnte es weniger wirksam, je von der Größe der Iteration sortiert. 86 00:04:32,010 --> 00:04:35,250 >> Ich bin Doug Lloyd, ist dies CS50. 87 00:04:35,250 --> 00:04:36,757