1 00:00:00,000 --> 00:00:11,904 >> [Musikwiedergabe] 2 00:00:11,904 --> 00:00:12,910 >> PROFESSOR: Alles klar. 3 00:00:12,910 --> 00:00:16,730 Dies CS50 und dies das Ende der dritten Woche. 4 00:00:16,730 --> 00:00:20,230 So sind wir heute hier, nicht in Sanders Theater, statt in Weidner Library. 5 00:00:20,230 --> 00:00:23,170 In dessen Inneren sich ein Studio wie Hauser Studio bekannt, 6 00:00:23,170 --> 00:00:28,310 oder sagen wir Studio H, oder soll wir sagen--, wenn Sie diesen Witz genossen, 7 00:00:28,310 --> 00:00:30,540 es ist eigentlich aus Klassenkamerad, Mark, online, 8 00:00:30,540 --> 00:00:32,420 die so viel über Twitter vorgeschlagen. 9 00:00:32,420 --> 00:00:34,270 Nun, was ist cool zu wobei hier in einem Studio 10 00:00:34,270 --> 00:00:38,410 ist, dass ich durch diese Grünen Wände, einen grünen Bildschirm oder Chroma, 11 00:00:38,410 --> 00:00:43,290 so zu sprechen, was, dass das bedeutet, CS50 Produktions-Team, ohne mein Wissen 12 00:00:43,290 --> 00:00:47,380 gerade jetzt, könnte setzen mich am meisten auf der ganzen Welt, 13 00:00:47,380 --> 00:00:48,660 zum Guten oder zum Schlechten. 14 00:00:48,660 --> 00:00:51,800 >> Nun, was vor uns liegt, Problem eingestellt zwei liegt in Ihren Händen für diese Woche, 15 00:00:51,800 --> 00:00:53,830 aber mit Problem eingestellt drei in der kommenden Woche, 16 00:00:53,830 --> 00:00:56,600 Sie werden mit in Frage gestellt werden die so genannte Spiel von 15, 17 00:00:56,600 --> 00:00:58,960 eine alte partybevorzugung, dass Sie erinnern sich vielleicht an Empfangs 18 00:00:58,960 --> 00:01:02,030 wie ein Kind, das eine ganze Reihe hat von Zahlen, die gleiten kann nach oben, unten, 19 00:01:02,030 --> 00:01:05,790 links und rechts, und es gibt eine Lücke im Puzzle, in dem Sie 20 00:01:05,790 --> 00:01:07,840 kann tatsächlich schieben Sie diese Puzzleteile. 21 00:01:07,840 --> 00:01:11,150 Letztlich Sie dies erhalten Puzzle in einigen halb zufälliger Reihenfolge, 22 00:01:11,150 --> 00:01:12,940 und das Ziel ist, sortieren sie, von oben nach unten, 23 00:01:12,940 --> 00:01:16,310 von links nach rechts, von einem den ganzen Weg bis über 15. 24 00:01:16,310 --> 00:01:19,360 >> Leider ist die Umsetzung Sie werden bei der Hand haben 25 00:01:19,360 --> 00:01:21,590 wird sich Software sein basiert, nicht physisch. 26 00:01:21,590 --> 00:01:25,280 Sie tatsächlich zu haben, um zu schreiben Code, mit dem ein Student oder Benutzer Dose 27 00:01:25,280 --> 00:01:26,760 spielen das Spiel von 15. 28 00:01:26,760 --> 00:01:29,030 Und in der Tat, in den Hacker Ausgabe-Spiel von 15, 29 00:01:29,030 --> 00:01:32,155 Sie werden eine Herausforderung, zu implementieren, nicht nur das Abspielen von dieser alten Schule 30 00:01:32,155 --> 00:01:35,010 Spiel, sondern die Lösung der es, die Umsetzung Gott-Modus, 31 00:01:35,010 --> 00:01:38,280 so zu sprechen, die tatsächlich löst das Rätsel der menschlichen, 32 00:01:38,280 --> 00:01:41,080 indem sie sie mit Hinweis, nach dem Hinweis, nach dem Hinweis. 33 00:01:41,080 --> 00:01:42,280 Also mehr dazu nächste Woche. 34 00:01:42,280 --> 00:01:43,720 Aber das ist, was vor uns liegt. 35 00:01:43,720 --> 00:01:47,610 >> Für den Moment erinnern, dass Anfang der Woche wir hatten diese Cliffhanger, wenn man so will, 36 00:01:47,610 --> 00:01:52,560 wobei das Beste, was wir taten, Sortier weise war eine obere Schranke von Big O n 37 00:01:52,560 --> 00:01:53,210 zum Quadrat. 38 00:01:53,210 --> 00:01:56,520 Mit anderen Worten, Bubble-Sort, Selection Sort, Insertion Sort, 39 00:01:56,520 --> 00:01:59,120 alle von ihnen, während verschiedene bei der Umsetzung, 40 00:01:59,120 --> 00:02:03,480 in ein n übertragen quadriert Lauf Zeit im schlimmsten Fall. 41 00:02:03,480 --> 00:02:06,010 Und wir gehen davon aus, dass in der Regel die sehr schlechtesten Fall für die Sortierung 42 00:02:06,010 --> 00:02:08,814 ist eine, die Ihre Eingaben vollständig nach hinten. 43 00:02:08,814 --> 00:02:11,980 Und in der Tat, es hat durchaus ein paar Schritte auf jeden dieser Algorithmen zu implementieren. 44 00:02:11,980 --> 00:02:15,110 >> Jetzt am Ende der Klasse Rückruf verglichen wir Bubble-Sort 45 00:02:15,110 --> 00:02:19,390 gegen Auswahl sort gegen einen anderen dass wir aufgerufen merge sort zu der Zeit, 46 00:02:19,390 --> 00:02:22,120 und ich schlage vor, dass es unter Vorteil einer Lektion von Woche 47 00:02:22,120 --> 00:02:24,060 Null, teile und herrsche. 48 00:02:24,060 --> 00:02:28,810 Und irgendwie zu erreichen eine Art von logarithmischer Laufzeit letztendlich, 49 00:02:28,810 --> 00:02:31,024 anstatt etwas das ist rein quadratisch. 50 00:02:31,024 --> 00:02:33,440 Und es ist nicht ganz logarithmisch, es ist ein bisschen mehr als das. 51 00:02:33,440 --> 00:02:36,520 Aber wenn man von der Klasse erinnern, es war viel, viel schneller. 52 00:02:36,520 --> 00:02:38,210 Werfen wir einen Blick auf, wo wir aufgehört haben. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble-Sort gegen Auswahl Art gegen merge sort. 55 00:02:45,370 --> 00:02:47,700 Jetzt sind sie alle laufen, in Theoretisch gleichzeitig. 56 00:02:47,700 --> 00:02:50,510 Die CPU mit der gleichen Geschwindigkeit läuft. 57 00:02:50,510 --> 00:02:54,990 Aber man kann fühlen, wie langweilig diese wird sehr schnell gehen, um zu werden, 58 00:02:54,990 --> 00:02:58,790 und wie schnell, wenn wir zu injizieren ein bisschen Woche Null-Algorithmen, 59 00:02:58,790 --> 00:03:00,080 können wir Dinge zu beschleunigen. 60 00:03:00,080 --> 00:03:01,630 >> So Marke Art sieht toll aus. 61 00:03:01,630 --> 00:03:05,220 Wie können wir es nutzen, um Zahlen schneller zu sortieren. 62 00:03:05,220 --> 00:03:07,140 Nun lassen Sie uns denken Sie zurück um eine Zutat, die wir 63 00:03:07,140 --> 00:03:10,380 musste zurück in Woche null, dass der Suche nach jemandem in einem Telefonbuch, 64 00:03:10,380 --> 00:03:12,380 und daran erinnern, dass die Pseudocode, die wir vorgeschlagen, 65 00:03:12,380 --> 00:03:14,560 , über die wir finden können jemanden wie Mike Smith, 66 00:03:14,560 --> 00:03:16,310 sah ein wenig so etwas wie dieses. 67 00:03:16,310 --> 00:03:20,820 >> Nun werfen Sie einen Blick in bestimmten in Zeile 7 und 8 sowie 10 und 11, 68 00:03:20,820 --> 00:03:25,240 wonach Schleife induzieren, wobei wir gehalten gehen wieder und wieder zurück zu Zeile 3, 69 00:03:25,240 --> 00:03:26,520 und wieder. 70 00:03:26,520 --> 00:03:31,790 Aber es stellt sich heraus, dass wir sehen können Dieser Algorithmus, hier in Pseudocode, 71 00:03:31,790 --> 00:03:33,620 ein wenig mehr ganzheitlich. 72 00:03:33,620 --> 00:03:35,960 In der Tat, was ich suche bei hier auf dem Bildschirm, 73 00:03:35,960 --> 00:03:41,180 ist ein Algorithmus zum Suchen Mike Smith bei einigen Reihe von Seiten. 74 00:03:41,180 --> 00:03:45,520 Und in der Tat, könnten wir dies zu vereinfachen Algorithmus in den Zeilen 7 und 8, 75 00:03:45,520 --> 00:03:49,860 und 10 und 11, nur sagen, dass dies, , die ich hier in gelb dargestellt. 76 00:03:49,860 --> 00:03:52,210 In anderen Worten, wenn Mike Smith ist zuvor in dem Buch, 77 00:03:52,210 --> 00:03:55,004 wir nicht brauchen, um Schritt angeben Schritt jetzt, wie man sucht ihn. 78 00:03:55,004 --> 00:03:56,920 Wir müssen nicht angeben, zurück zu Zeile 3 zu gehen, 79 00:03:56,920 --> 00:03:58,960 Warum gehen wir nicht nur statt, sagen, allgemeiner, 80 00:03:58,960 --> 00:04:01,500 Suche nach Mike in der linke Hälfte des Buches. 81 00:04:01,500 --> 00:04:03,960 >> Umgekehrt, wenn Mike tatsächlich später im Buch, 82 00:04:03,960 --> 00:04:07,540 warum machen wir nicht nur zitieren unquote Suche Mike in der rechten Hälfte des Buches. 83 00:04:07,540 --> 00:04:11,030 Mit anderen Worten, warum wir nicht einfach Art von Punt, um uns zu sagen, 84 00:04:11,030 --> 00:04:13,130 Suche nach Mike in diesem Untergruppe des Buches, 85 00:04:13,130 --> 00:04:16,279 und lassen Sie es zu unserem bestehenden Algorithmus, um uns zu sagen, 86 00:04:16,279 --> 00:04:18,750 wie man für Mike in suchen dass linke Hälfte des Buches. 87 00:04:18,750 --> 00:04:20,750 Mit anderen Worten, unsere Algorithmus arbeitet, ob es 88 00:04:20,750 --> 00:04:24,670 ein Telefonbuch von dieser Dicke davon Dicke oder eine beliebige Dicke auch immer. 89 00:04:24,670 --> 00:04:27,826 So können wir rekursiv definieren diesen Algorithmus. 90 00:04:27,826 --> 00:04:29,950 Mit anderen Worten, auf der Bildschirm hier, ist ein Algorithmus, 91 00:04:29,950 --> 00:04:33,130 für die Suche nach Mike Smith zwischen den Seiten eines Telefonbuch. 92 00:04:33,130 --> 00:04:37,410 So in Zeile 7 und 10, lassen Sie uns nur sagen, genau das zu. 93 00:04:37,410 --> 00:04:40,250 Und ich verwende diesen Begriff ein Moment vor, und in der Tat, Rekursion 94 00:04:40,250 --> 00:04:42,450 ist das Schlagwort für jetzt, und es ist dieser Prozess 95 00:04:42,450 --> 00:04:47,210 von etwas zyklischen tun, indem irgendwie Verwendung von Code, die Sie bereits haben, 96 00:04:47,210 --> 00:04:49,722 und wieder aufrufen, wieder und wieder. 97 00:04:49,722 --> 00:04:51,930 Jetzt wird es wichtig sein, dass wir irgendwie unten 98 00:04:51,930 --> 00:04:53,821 out und nicht unendlich lang tun. 99 00:04:53,821 --> 00:04:56,070 Sonst werden wir zu gehen haben in der Tat eine Endlosschleife. 100 00:04:56,070 --> 00:04:59,810 Aber lassen Sie uns sehen, ob wir diese Idee zu leihen einer Rekursion, wieder etwas zu tun 101 00:04:59,810 --> 00:05:03,600 und immer wieder zu lösen das Sortierproblem über merge 102 00:05:03,600 --> 00:05:05,900 Sortieren, umso effizienter. 103 00:05:05,900 --> 00:05:06,970 >> Also gebe ich dir Art zusammenzuführen. 104 00:05:06,970 --> 00:05:07,920 Lass uns einen Blick darauf werfen. 105 00:05:07,920 --> 00:05:10,850 So, hier ist Pseudocode, mit was wir umsetzen Sortierung, 106 00:05:10,850 --> 00:05:12,640 Verwendung dieses Algorithmus namens merge sort. 107 00:05:12,640 --> 00:05:13,880 Und es ist ganz einfach dieses. 108 00:05:13,880 --> 00:05:15,940 Am Eingang von n Elementen, mit anderen Worten, wenn Sie 109 00:05:15,940 --> 00:05:18,830 bei n Elementen und Zahlen und Briefe oder was auch immer der Eingang, 110 00:05:18,830 --> 00:05:22,430 wenn Sie n-Elemente, wenn gegeben, n kleiner als 2 ist, nur zurückkehren. 111 00:05:22,430 --> 00:05:22,930 Recht? 112 00:05:22,930 --> 00:05:26,430 Weil, wenn n kleiner als 2, das heißt bedeutet, dass meine Liste von Elementen 113 00:05:26,430 --> 00:05:30,446 entweder der Größe 0 oder 1 und in diesen beiden Fällen trivial, 114 00:05:30,446 --> 00:05:31,570 die Liste bereits sortiert. 115 00:05:31,570 --> 00:05:32,810 Wenn es keine Liste, es sortiert. 116 00:05:32,810 --> 00:05:35,185 Und wenn es eine Liste der Länge 1, es ist offensichtlich sortiert. 117 00:05:35,185 --> 00:05:38,280 So der Algorithmus muss nur wirklich etwas Interessantes, 118 00:05:38,280 --> 00:05:40,870 wenn wir zwei oder mehr haben, Elemente, die uns gegeben. 119 00:05:40,870 --> 00:05:42,440 Also schauen wir uns an die Magie dann. 120 00:05:42,440 --> 00:05:47,500 Else sortieren Sie die linke Hälfte der Elemente, Dann sortieren Sie die rechte Hälfte der Elemente, 121 00:05:47,500 --> 00:05:49,640 dann verschmelzen die sortierten Hälften. 122 00:05:49,640 --> 00:05:52,440 Und was ist eine Art Geist Biegen hier, ist, dass ich nicht wirklich 123 00:05:52,440 --> 00:05:56,190 scheinen Sie gesagt haben, alles nur noch, nicht wahr? 124 00:05:56,190 --> 00:05:59,560 Alles, was ich gesagt habe, ist, da eine Liste der n Elementen, sortieren Sie die linke Hälfte, 125 00:05:59,560 --> 00:06:01,800 dann die rechte Hälfte, dann verschmelzen die sortierten Hälften, 126 00:06:01,800 --> 00:06:03,840 aber wo ist der tatsächliche Geheimrezept? 127 00:06:03,840 --> 00:06:05,260 Wo ist der Algorithmus? 128 00:06:05,260 --> 00:06:09,150 Nun stellt sich heraus, dass diese beiden Linien ersten, sortieren linke Hälfte der Elemente, 129 00:06:09,150 --> 00:06:13,970 und Sortier rechten Hälfte der Elemente, sind rekursive Aufrufe, so zu sprechen. 130 00:06:13,970 --> 00:06:16,120 >> Denn an diesem Zeitpunkt muss ich 131 00:06:16,120 --> 00:06:18,950 ein Algorithmus, mit dem sortieren eine ganze Reihe von Elementen? 132 00:06:18,950 --> 00:06:19,450 Ja. 133 00:06:19,450 --> 00:06:20,620 Es ist hier richtig. 134 00:06:20,620 --> 00:06:25,180 Es ist hier auf dem Bildschirm, und also kann ich die gleiche Satz von Schritten verwenden 135 00:06:25,180 --> 00:06:28,500 auf die linke Hälfte zu sortieren, wie ich kann die rechte Hälfte. 136 00:06:28,500 --> 00:06:30,420 Und in der Tat, wieder und wieder. 137 00:06:30,420 --> 00:06:34,210 So irgendwie, und wir werden in Kürze dies zu sehen, die Magie des Mergesort 138 00:06:34,210 --> 00:06:37,967 wird in diesem sehr endgültige eingebettete Linie, die Zusammenführung der sortierten Hälften. 139 00:06:37,967 --> 00:06:39,300 Und das scheint recht intuitiv. 140 00:06:39,300 --> 00:06:41,050 Sie nehmen zwei Hälften, und du, irgendwie, verschmelzen sie zusammen, 141 00:06:41,050 --> 00:06:43,260 und wir werden das sehen konkret in einem Augenblick. 142 00:06:43,260 --> 00:06:45,080 >> Aber dies ist eine vollständige Algorithmus. 143 00:06:45,080 --> 00:06:46,640 Und lassen Sie uns genau, warum sehen. 144 00:06:46,640 --> 00:06:50,912 Nun nehme an, dass wir diese gleichen gegebenen acht Elemente hier auf dem Bildschirm, ein 145 00:06:50,912 --> 00:06:53,120 durch acht, aber sie sind in scheinbar zufälliger Reihenfolge. 146 00:06:53,120 --> 00:06:55,320 Und das Ziel bei der Hand ist um diese Elemente zu sortieren. 147 00:06:55,320 --> 00:06:58,280 Nun, wie kann ich gehen, tun es mit wieder 148 00:06:58,280 --> 00:07:00,407 Mergesort, nach dieser Pseudocode? 149 00:07:00,407 --> 00:07:02,740 Und wieder, Raufaser dies in Ihren Geist, nur für einen Augenblick. 150 00:07:02,740 --> 00:07:05,270 Der erste Fall ist ziemlich trivial, wenn es weniger als 2, 151 00:07:05,270 --> 00:07:07,060 nur zurückkehren, gibt es keine Arbeit zu tun. 152 00:07:07,060 --> 00:07:09,290 Also eigentlich gibt es nur drei Schritte, um wirklich im Auge zu behalten. 153 00:07:09,290 --> 00:07:11,081 Wieder und wieder, ich bin gehen zu wollen, haben 154 00:07:11,081 --> 00:07:13,980 auf die linke Hälfte zu sortieren, sortieren Sie die rechte Hälfte, 155 00:07:13,980 --> 00:07:15,890 und dann, wenn ihre beiden Hälften werden sortiert, 156 00:07:15,890 --> 00:07:18,710 Ich möchte sie miteinander verschmelzen in eine sortierte Liste. 157 00:07:18,710 --> 00:07:19,940 So sollte man das im Hinterkopf. 158 00:07:19,940 --> 00:07:21,310 >> Also hier ist die ursprüngliche Liste. 159 00:07:21,310 --> 00:07:23,510 Lassen Sie behandeln Sie dies als ein Array, als wir begannen, 160 00:07:23,510 --> 00:07:25,800 in der zweiten Woche, die eine ist zusammenhängenden Speicherblock. 161 00:07:25,800 --> 00:07:28,480 In diesem Fall mit acht Zahlen, Zurück, um zurück zurück. 162 00:07:28,480 --> 00:07:30,700 Und lassen Sie uns jetzt merge sort anzuwenden. 163 00:07:30,700 --> 00:07:33,300 Deshalb möchte ich zunächst zu sortieren die linke Hälfte dieser Liste, 164 00:07:33,300 --> 00:07:37,370 und lassen Sie uns daher konzentrieren sich auf die 4, 8, 6 und 2. 165 00:07:37,370 --> 00:07:41,000 >> Nun, wie soll ich mich gehen Sortieren einer Liste von Größe 4? 166 00:07:41,000 --> 00:07:45,990 Nun, ich muss jetzt prüfen, Sortieren der links von der linken Hälfte. 167 00:07:45,990 --> 00:07:47,720 Auch hier lassen Sie uns Rücklauf nur für einen Augenblick. 168 00:07:47,720 --> 00:07:51,010 Wenn die Pseudocode ist dies, und ich bin angesichts acht Elementen, 169 00:07:51,010 --> 00:07:53,230 8 ist offensichtlich grßer als oder gleich 2 ist. 170 00:07:53,230 --> 00:07:54,980 Also mit dem ersten Fall keine Anwendung findet. 171 00:07:54,980 --> 00:07:58,120 So zu acht Elemente, die ich zuerst zu sortieren, sortieren Sie die linke Hälfte der Elemente, 172 00:07:58,120 --> 00:08:01,930 dann habe ich die rechte Hälfte zu sortieren, dann verschmelzen I die beiden sortierten Hälften, die jeweils der Größe 4. 173 00:08:01,930 --> 00:08:02,470 OK. 174 00:08:02,470 --> 00:08:07,480 >> Aber wenn Sie gerade mir gesagt, sortieren die linke Hälfte, die jetzt von der Größe 4, 175 00:08:07,480 --> 00:08:09,350 wie kann ich die linke Hälfte sortieren? 176 00:08:09,350 --> 00:08:11,430 Nun, wenn ich eine Eingabe von vier Elementen, 177 00:08:11,430 --> 00:08:14,590 Ich zum ersten Mal mit der linken sortieren zwei, dann die zwei rechten, 178 00:08:14,590 --> 00:08:16,210 und dann habe ich sie zusammen verschmelzen. 179 00:08:16,210 --> 00:08:18,700 Also noch einmal, wird es ein wenig ein Geist Biegen Sie hier, Spiel, 180 00:08:18,700 --> 00:08:21,450 weil Sie, Art, müssen erinnern, wo Sie in der Geschichte sind, 181 00:08:21,450 --> 00:08:23,620 aber am Ende des Tages, gegeben beliebige Anzahl von Elementen, 182 00:08:23,620 --> 00:08:25,620 möchten Sie zuerst die Sortier linke Hälfte, dann die rechte Hälfte, 183 00:08:25,620 --> 00:08:26,661 dann verschmelzen sie zusammen. 184 00:08:26,661 --> 00:08:28,630 Lassen Sie uns beginnen, um genau das zu tun. 185 00:08:28,630 --> 00:08:30,170 Hier ist die Eingabe von acht Elementen. 186 00:08:30,170 --> 00:08:31,910 Jetzt sind wir auf der linken Hälfte der Suche hier. 187 00:08:31,910 --> 00:08:33,720 Wie kann ich vier Elemente sortieren? 188 00:08:33,720 --> 00:08:35,610 Nun, ich zuerst sortieren Sie die linke Hälfte. 189 00:08:35,610 --> 00:08:37,720 Nun, wie ich die linke Hälfte sortieren? 190 00:08:37,720 --> 00:08:39,419 Nun, ich habe zwei Elemente gegeben. 191 00:08:39,419 --> 00:08:41,240 Lassen Sie uns also zu sortieren diese beiden Elemente. 192 00:08:41,240 --> 00:08:44,540 2 grßer oder gleich 2, versteht sich. 193 00:08:44,540 --> 00:08:46,170 So dass erste Fall keine Anwendung findet. 194 00:08:46,170 --> 00:08:49,010 >> So habe ich nun auf die linke sortieren die Hälfte dieser beiden Elemente. 195 00:08:49,010 --> 00:08:50,870 Die linke Hälfte, natürlich, ist nur 4. 196 00:08:50,870 --> 00:08:54,020 So, wie ich eine Liste mit einem Element zu sortieren? 197 00:08:54,020 --> 00:08:57,960 Nun, dass spezielle Basisfall bis oben, so zu sprechen, gilt. 198 00:08:57,960 --> 00:09:01,470 1 kleiner als 2 ist, und meine Liste ist in der Tat der Größe 1. 199 00:09:01,470 --> 00:09:02,747 Also habe ich einfach zurück. 200 00:09:02,747 --> 00:09:03,580 Ich weiß gar nichts zu tun. 201 00:09:03,580 --> 00:09:06,770 Und in der Tat, bei dem, was ich sehen getan, 4 bereits sortiert. 202 00:09:06,770 --> 00:09:09,220 Wie ich schon teilweise erfolgreich hier. 203 00:09:09,220 --> 00:09:11,750 >> Jetzt, scheint ziemlich blöd Anspruch, aber es ist wahr. 204 00:09:11,750 --> 00:09:13,700 4 ist eine Liste der Größe 1. 205 00:09:13,700 --> 00:09:15,090 Es ist bereits sortiert. 206 00:09:15,090 --> 00:09:16,270 Das ist die linke Hälfte. 207 00:09:16,270 --> 00:09:18,010 Jetzt habe ich die rechte Hälfte zu sortieren. 208 00:09:18,010 --> 00:09:22,310 Ihr Eingang ist ein Element, 8 In ähnlicher Weise bereits sortiert. 209 00:09:22,310 --> 00:09:25,170 Dumm auch, aber wieder, Dieses Grundprinzip 210 00:09:25,170 --> 00:09:28,310 wird, damit wir jetzt aufbauen Am Anfang dieser erfolgreich. 211 00:09:28,310 --> 00:09:32,260 4 sortiert, 8 wird sortiert, jetzt was war das letzte Schritt? 212 00:09:32,260 --> 00:09:35,330 Dabei wird die dritte und letzte Schritt, jedes Zeit, die Sie sortieren bist eine Liste, Rückruf, 213 00:09:35,330 --> 00:09:38,310 war, um die beiden Hälften zusammenzuführen, die linke und die rechte. 214 00:09:38,310 --> 00:09:39,900 Lassen Sie uns also genau das tun. 215 00:09:39,900 --> 00:09:41,940 Meine linke Hälfte ist natürlich, 4. 216 00:09:41,940 --> 00:09:43,310 Meine rechte Hälfte ist 8. 217 00:09:43,310 --> 00:09:44,100 >> Also lassen Sie uns dies tun. 218 00:09:44,100 --> 00:09:46,410 Zuerst werde ich zu vergeben einige zusätzlichen Speicher, 219 00:09:46,410 --> 00:09:48,680 dass ich hier zu vertreten, als nur eine sekundäre Array, 220 00:09:48,680 --> 00:09:49,660 das ist groß genug, um dies zu passen. 221 00:09:49,660 --> 00:09:52,243 Aber können Sie sich vorstellen, die sich dieses Rechteck die gesamte Länge, 222 00:09:52,243 --> 00:09:53,290 wenn wir brauchen mehr später. 223 00:09:53,290 --> 00:09:58,440 Wie kann ich 4 nehmen und 8, und Zusammenführen diese beiden Listen der Größe 1 zusammen? 224 00:09:58,440 --> 00:10:00,270 Auch hier ist ziemlich einfach. 225 00:10:00,270 --> 00:10:03,300 4 kommt zuerst, dann kommt 8. 226 00:10:03,300 --> 00:10:07,130 Weil, wenn ich will, um die Sortier linke Hälfte, dann die rechte Hälfte, 227 00:10:07,130 --> 00:10:09,900 und dann mischen Sie die beiden Hälften zusammen, in sortierter Reihenfolge, 228 00:10:09,900 --> 00:10:11,940 4 kommt zuerst, dann kommt 8. 229 00:10:11,940 --> 00:10:15,810 >> So scheinen wir werden Fortschritte machen, auch aber ich habe keine tatsächliche Arbeit geleistet. 230 00:10:15,810 --> 00:10:17,800 Aber denken Sie daran, wo wir in der Geschichte sind. 231 00:10:17,800 --> 00:10:19,360 Wir hatten ursprünglich dauerte acht Elementen. 232 00:10:19,360 --> 00:10:21,480 Wir sortiert die linke Hälfte, die 4 ist. 233 00:10:21,480 --> 00:10:24,450 Dann sortiert man die linke Hälfte der linken Hälfte, die 2 war. 234 00:10:24,450 --> 00:10:25,270 Und es geht los. 235 00:10:25,270 --> 00:10:26,920 Wir sind mit diesem Schritt getan. 236 00:10:26,920 --> 00:10:29,930 >> Wenn wir also nach habe die linke Hälfte von 2, jetzt sind wir 237 00:10:29,930 --> 00:10:32,130 müssen die rechte Hälfte von 2 sortieren. 238 00:10:32,130 --> 00:10:35,710 Also die rechte Hälfte von 2 ist Diese beiden Werte sind hier, 6 und 2. 239 00:10:35,710 --> 00:10:40,620 Also lassen Sie uns nun eine Eingabe von Größe 2, und sortieren Sie die linke Hälfte, und dann 240 00:10:40,620 --> 00:10:42,610 die rechte Hälfte, und dann verschmelzen sie zusammen. 241 00:10:42,610 --> 00:10:45,722 Nun, wie kann ich eine Liste der Größe zu sortieren 1, die nur die Nummer 6? 242 00:10:45,722 --> 00:10:46,430 Ich bin bereits getan. 243 00:10:46,430 --> 00:10:48,680 Diese Liste der Größe 1 ist sortiert. 244 00:10:48,680 --> 00:10:52,140 >> Wie kann ich eine andere Liste zu sortieren Größe 1, die sogenannte rechte Hälfte. 245 00:10:52,140 --> 00:10:54,690 Nun, es ist auch bereits sortiert. 246 00:10:54,690 --> 00:10:56,190 Die Nummer 2 ist allein. 247 00:10:56,190 --> 00:11:00,160 So, jetzt habe ich zwei Hälften, links und Recht, ich brauche, um sie miteinander zu verschmelzen. 248 00:11:00,160 --> 00:11:01,800 Lassen Sie mich etwas mehr Platz gebe mich. 249 00:11:01,800 --> 00:11:05,580 Und legte 2 in es, dann 6 in es, wodurch 250 00:11:05,580 --> 00:11:10,740 Sortieren Sie diese Liste, links und rechts, und miteinander verschmelzenden es letztlich. 251 00:11:10,740 --> 00:11:12,160 So bin ich in etwas besserer Verfassung. 252 00:11:12,160 --> 00:11:16,250 Ich bin noch nicht fertig, weil klar 4, 8, 2, 6 nicht die letzte Bestellung, die ich will. 253 00:11:16,250 --> 00:11:20,640 Aber ich habe jetzt zwei Listen von Größe 2, dass haben beide jeweils sortiert. 254 00:11:20,640 --> 00:11:24,580 So, jetzt, wenn Sie in Ihrem Kopf zu zurückspulen Auge, wo haben, dass uns das? 255 00:11:24,580 --> 00:11:28,520 Ich begann mit acht Elementen, dann habe ich schnitzte es auf der linken Hälfte der 4, 256 00:11:28,520 --> 00:11:31,386 dann die linke Hälfte von 2, und dann die rechte Hälfte von 2 ist, 257 00:11:31,386 --> 00:11:34,510 Ich beendete damit die Sortierung der linken Hälfte 2 und die rechte Hälfte von 2, 258 00:11:34,510 --> 00:11:37,800 so was ist der dritte und letzte Schritt hier? 259 00:11:37,800 --> 00:11:41,290 Ich muss miteinander verschmelzen zwei Listen der Größe 2. 260 00:11:41,290 --> 00:11:42,040 Also lassen Sie uns weitermachen. 261 00:11:42,040 --> 00:11:43,940 Und auf dem Bildschirm hier, geben mir etwas zusätzlicher Speicher, 262 00:11:43,940 --> 00:11:47,170 obwohl technisch, bemerken, dass ich erhielt eine ganze Reihe von Leerzeichen bis oben 263 00:11:47,170 --> 00:11:47,670 Dort. 264 00:11:47,670 --> 00:11:50,044 Wenn ich will vor allem sein effiziente Raum weise, 265 00:11:50,044 --> 00:11:52,960 Ich konnte einfach in Bewegung der Elemente hin und her, oben und unten. 266 00:11:52,960 --> 00:11:55,460 Aber nur für visuelle Klarheit, Ich werde es unten legte, 267 00:11:55,460 --> 00:11:56,800 die Dinge schön und sauber zu halten. 268 00:11:56,800 --> 00:11:58,150 >> Also habe ich zwei Listen der Größe 2 erhielt. 269 00:11:58,150 --> 00:11:59,770 Die erste Liste hat 4 und 8. 270 00:11:59,770 --> 00:12:01,500 Die zweite Liste besteht aus 2 und 6. 271 00:12:01,500 --> 00:12:03,950 Lassen Sie uns zusammenführen diejenigen, zusammen in sortierter Reihenfolge. 272 00:12:03,950 --> 00:12:09,910 2 natürlich zuerst kommt, dann 4, dann 6, dann 8. 273 00:12:09,910 --> 00:12:12,560 Und jetzt scheinen wir bekommen irgendwo interessant. 274 00:12:12,560 --> 00:12:15,720 Jetzt habe ich nach der Hälfte der Liste, und zufälligerweise ist es 275 00:12:15,720 --> 00:12:18,650 alle geraden Zahlen, sondern dass ist in der Tat nur ein Zufall. 276 00:12:18,650 --> 00:12:22,220 Und ich habe jetzt die linke sortiert halb, so dass es 2, 4, 6 und 8. 277 00:12:22,220 --> 00:12:23,430 Nichts ist in Ordnung. 278 00:12:23,430 --> 00:12:24,620 Das fühlt sich an wie Fortschritte. 279 00:12:24,620 --> 00:12:26,650 >> Jetzt fühlt es sich wie ich habe für immer jetzt sprechen, 280 00:12:26,650 --> 00:12:29,850 so was noch zu, wenn dies zu sehen Algorithmus ist tatsächlich effizienter. 281 00:12:29,850 --> 00:12:31,766 Aber wir durchmachen es super methodisch. 282 00:12:31,766 --> 00:12:34,060 Ein Computer natürlich wäre es, das zu tun. 283 00:12:34,060 --> 00:12:34,840 Also, wo sind wir? 284 00:12:34,840 --> 00:12:36,180 Wir begannen mit acht Elementen. 285 00:12:36,180 --> 00:12:37,840 Ich sortierte die linke Hälfte des 4. 286 00:12:37,840 --> 00:12:39,290 Ich scheine damit fertig werden. 287 00:12:39,290 --> 00:12:42,535 So, jetzt ist der nächste Schritt, um sortieren Sie die rechte Hälfte des 4. 288 00:12:42,535 --> 00:12:44,410 Und dieser Teil wir gehen können durch ein wenig mehr 289 00:12:44,410 --> 00:12:47,140 schnell, wenn auch du bist Willkommen zu zurückspulen oder Pause, nur 290 00:12:47,140 --> 00:12:49,910 denken, durch sie an Ihrem eigenen Tempo, aber was 291 00:12:49,910 --> 00:12:53,290 Wir haben jetzt eine Gelegenheit, tun genau das gleiche Algorithmus auf vier 292 00:12:53,290 --> 00:12:54,380 unterschiedliche Nummern. 293 00:12:54,380 --> 00:12:57,740 >> Also lassen Sie uns gehen Sie vor, und konzentrieren sich auf die rechte Hälfte, die wir hier sind. 294 00:12:57,740 --> 00:13:01,260 Die linke Hälfte, dass rechte Hälfte, und jetzt die 295 00:13:01,260 --> 00:13:04,560 linke Hälfte des linken die Hälfte dieser rechte Hälfte, 296 00:13:04,560 --> 00:13:08,030 und wie kann ich eine Liste der Größe zu sortieren 1 enthält nur die Nummer 1? 297 00:13:08,030 --> 00:13:09,030 Ist schon erledigt. 298 00:13:09,030 --> 00:13:11,830 Wie kann ich das gleiche für eine Liste zu tun der Größe 1, nur 7 enthalten? 299 00:13:11,830 --> 00:13:12,840 Ist schon erledigt. 300 00:13:12,840 --> 00:13:16,790 Schritt drei für dieses Halb dann ist, diese beiden Elemente verschmelzen 301 00:13:16,790 --> 00:13:20,889 in eine neue Liste von Größe 2, 1 und 7. 302 00:13:20,889 --> 00:13:23,180 Scheinen Sie nicht, alles getan haben, dass viel interessante Arbeit. 303 00:13:23,180 --> 00:13:24,346 Mal sehen, was als nächstes passiert. 304 00:13:24,346 --> 00:13:29,210 Ich habe nach der linken Hälfte des rechte Hälfte meines ursprünglichen Eingang. 305 00:13:29,210 --> 00:13:32,360 Lassen Sie uns nun zu sortieren das Recht Hälfte, die 5 und 3 enthält. 306 00:13:32,360 --> 00:13:35,740 Versuche es noch auf der linken Seite sehen Hälfte, sortiert, rechte Hälfte, sortiert, 307 00:13:35,740 --> 00:13:39,120 und verschmelzen diese beiden zusammen, in etwas zusätzlichen Platz, 308 00:13:39,120 --> 00:13:41,670 3 kommt zuerst, dann kommt 5. 309 00:13:41,670 --> 00:13:46,190 Und jetzt haben wir sortiert haben die linke Hälfte der rechten Hälfte 310 00:13:46,190 --> 00:13:49,420 des ursprünglichen Problems und die rechte Hälfte der rechten Hälfte 311 00:13:49,420 --> 00:13:50,800 des ursprünglichen Problems. 312 00:13:50,800 --> 00:13:52,480 Was ist die dritte und letzte Stufe? 313 00:13:52,480 --> 00:13:54,854 Nun, diese beiden Hälften miteinander verschmelzen. 314 00:13:54,854 --> 00:13:57,020 So möchte ich mich etwas zu bekommen mehr Platz, aber, wieder, ich 315 00:13:57,020 --> 00:13:58,699 könnte mit diesem Ersatzraum bis oben. 316 00:13:58,699 --> 00:14:00,490 Aber wir halten es einfach visuell. 317 00:14:00,490 --> 00:14:07,070 Lassen Sie mich jetzt in 1 zusammenzuführen, und dann 3 und dann 5, dann mit 7. 318 00:14:07,070 --> 00:14:10,740 Dabei ließ mich jetzt mit dem rechte Hälfte des ursprünglichen Problems 319 00:14:10,740 --> 00:14:12,840 das ist perfekt sortiert. 320 00:14:12,840 --> 00:14:13,662 >> Also, was bleibt? 321 00:14:13,662 --> 00:14:16,120 Ich fühle mich wie ich immer wieder sagen, die elben Dinge wieder und wieder, 322 00:14:16,120 --> 00:14:18,700 aber das ist repräsentativ für die Tatsache, dass wir mit Rekursion. 323 00:14:18,700 --> 00:14:21,050 Das Verfahren der Verwendung eines Algorithmus wieder und wieder, 324 00:14:21,050 --> 00:14:23,940 auf kleinere Teilmengen das ursprüngliche Problem. 325 00:14:23,940 --> 00:14:27,580 So dass ich jetzt eine linke sortiert die Hälfte des ursprünglichen Problems. 326 00:14:27,580 --> 00:14:30,847 Ich habe ein Recht sortierten Halb des ursprünglichen Problems. 327 00:14:30,847 --> 00:14:32,180 Was ist der dritte und letzte Schritt? 328 00:14:32,180 --> 00:14:33,590 Oh, es ist Zusammenführen. 329 00:14:33,590 --> 00:14:34,480 Also lassen Sie uns tun. 330 00:14:34,480 --> 00:14:36,420 Lassen Sie uns einige zusätzliche zuzuweisen Speicher, aber mein Gott, wir 331 00:14:36,420 --> 00:14:37,503 könnte es jetzt überall setzen. 332 00:14:37,503 --> 00:14:40,356 Wir haben so viel Platz zur Verfügung zu uns, aber wir werden es einfach halten. 333 00:14:40,356 --> 00:14:42,730 Anstatt sich zurück und her mit unserem ursprünglichen Speicher, 334 00:14:42,730 --> 00:14:44,480 lassen Sie uns einfach tun optisch nach unten hier unten, 335 00:14:44,480 --> 00:14:47,240 zu Ende zu bringen Zusammenlegung der linke Hälfte und die rechte Hälfte. 336 00:14:47,240 --> 00:14:49,279 >> So durch die Zusammenführung, was muss ich tun? 337 00:14:49,279 --> 00:14:50,820 Ich möchte die Elemente, um zu nehmen. 338 00:14:50,820 --> 00:14:53,230 So suchen Sie in der linken Hälfte, Ich sehe die erste Zahl 2. 339 00:14:53,230 --> 00:14:55,230 Ich schaue auf die rechte Hälfte, Ich sehe die erste Zahl 340 00:14:55,230 --> 00:14:58,290 1 ist, so offensichtlich die Zahl will ich auszureißen, 341 00:14:58,290 --> 00:15:00,430 und an erster Stelle in meinem letzten Liste? 342 00:15:00,430 --> 00:15:01,449 Natürlich 1. 343 00:15:01,449 --> 00:15:02,990 Jetzt möchte ich die gleiche Frage stellen. 344 00:15:02,990 --> 00:15:05,040 Auf der linken Hälfte, habe ich immer noch die Nummer 2. 345 00:15:05,040 --> 00:15:07,490 Auf der rechten Hälfte, Ich habe die Nummer 3 bekam. 346 00:15:07,490 --> 00:15:08,930 Welcher will ich wählen? 347 00:15:08,930 --> 00:15:11,760 Natürlich Nummer 2 und Jetzt bemerken Sie die Kandidaten 348 00:15:11,760 --> 00:15:13,620 4 sind auf der linken Seite, 3 auf der rechten Seite. 349 00:15:13,620 --> 00:15:15,020 Lassen Sie uns, natürlich, wählen Sie 3. 350 00:15:15,020 --> 00:15:18,020 Jetzt sind die Kandidaten sind 4 auf der linke, 5 auf der rechten Seite. 351 00:15:18,020 --> 00:15:19,460 Wir natürlich wählen 4. 352 00:15:19,460 --> 00:15:21,240 6 links, 5 auf der rechten Seite. 353 00:15:21,240 --> 00:15:22,730 Wir natürlich wählen 5. 354 00:15:22,730 --> 00:15:25,020 6 links, 7 auf der rechten Seite. 355 00:15:25,020 --> 00:15:29,320 Wir wählen 6, und dann werden wir Wählen Sie 7, und dann wählen wir 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> So eine große Anzahl von Wörtern später, haben wir haben diese Liste der acht Elemente sortiert 358 00:15:34,370 --> 00:15:38,450 in eine Liste von eins bis acht, dass die zunehmende bei jedem Schritt, 359 00:15:38,450 --> 00:15:40,850 aber wie viel Zeit haben es dauern uns, das zu tun. 360 00:15:40,850 --> 00:15:43,190 Nun, ich habe absichtlich laid Dinge bildlich 361 00:15:43,190 --> 00:15:46,330 Hier, so dass wir Art sehen oder schätzen die Teilung 362 00:15:46,330 --> 00:15:49,060 erobern das ist geschehen. 363 00:15:49,060 --> 00:15:52,830 >> In der Tat, wenn man sich im Zuge zurückblicken, Ich habe alle diese gestrichelten Linien links 364 00:15:52,830 --> 00:15:55,660 in Platzhaltern, können Sie, Art finden, in umgekehrter Reihenfolge, 365 00:15:55,660 --> 00:15:58,800 wenn Sie Art von Blick zurück in Geschichte nun, meine ursprünglichen Liste 366 00:15:58,800 --> 00:16:00,250 ist natürlich der Größe 8. 367 00:16:00,250 --> 00:16:03,480 Und dann zuvor, war ich Umgang mit zwei Listen von Größe 4, 368 00:16:03,480 --> 00:16:08,400 und dann vier Listen von Größe 2, und dann acht Listen der Größe 1. 369 00:16:08,400 --> 00:16:10,151 >> Was bedeutet dies, Art, erinnern Sie an? 370 00:16:10,151 --> 00:16:11,858 Nun, in der Tat, jeder die Algorithmen wir haben 371 00:16:11,858 --> 00:16:14,430 sah bisher, wo wir Kluft, und dividieren, und dividieren, 372 00:16:14,430 --> 00:16:19,500 halten wieder mit Dingen, und wieder, führt zu diesem allgemeinen Gedanken. 373 00:16:19,500 --> 00:16:23,100 Und so gibt es etwas logarithmische hier los ist. 374 00:16:23,100 --> 00:16:26,790 Und es ist nicht ganz log n, aber es gibt eine logarithmische Komponente 375 00:16:26,790 --> 00:16:28,280 zu dem, was wir gerade getan haben. 376 00:16:28,280 --> 00:16:31,570 >> Betrachten wir nun, wie das eigentlich ist. 377 00:16:31,570 --> 00:16:34,481 So melden Sie sich von n, war wieder eine tolle Laufzeit, 378 00:16:34,481 --> 00:16:36,980 als wir so etwas wie binäre Suche, wie wir jetzt nennen es, 379 00:16:36,980 --> 00:16:40,090 die Teile und Herrsche-Strategie , über die wir gefunden Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Nun technisch. 381 00:16:41,020 --> 00:16:43,640 Das ist log Basis 2 n, auch wenn auch in den meisten Mathematikunterricht, 382 00:16:43,640 --> 00:16:45,770 10 ist in der Regel die Basis, die Sie übernehmen. 383 00:16:45,770 --> 00:16:48,940 Aber Informatiker fast immer zu denken und zu sprechen im Hinblick auf die Basis 2, 384 00:16:48,940 --> 00:16:52,569 so dass wir in der Regel nur Protokoll sagen n anstelle von log Basis 2 von N, 385 00:16:52,569 --> 00:16:55,110 aber sie sind genau ein und die elben in der Welt der Computer 386 00:16:55,110 --> 00:16:57,234 Wissenschaft und Nebenbei es gibt einen konstanten Faktor 387 00:16:57,234 --> 00:17:01,070 Unterschied zwischen den beiden, so dass es Moot trotzdem, für mehr formalen Gründen. 388 00:17:01,070 --> 00:17:04,520 >> Aber für jetzt, was wir kümmern etwa ist dieses Beispiel. 389 00:17:04,520 --> 00:17:08,520 Lassen Sie uns also nicht mit gutem Beispiel zu beweisen, aber bei wenigstens einem Beispiel der Nummern 390 00:17:08,520 --> 00:17:10,730 bei der Hand als eine Plausibilitätsprüfung, wenn man so will. 391 00:17:10,730 --> 00:17:14,510 So zuvor war die Formel log Basis 2 N, aber was n in diesem Fall. 392 00:17:14,510 --> 00:17:18,526 Ich hatte n Original-Nummern oder 8 der ursprünglichen Zahl spezifisch. 393 00:17:18,526 --> 00:17:20,359 Nun es ist schon ein wenig während, aber ich bin ziemlich 394 00:17:20,359 --> 00:17:25,300 Sie sicher, dass Log-Basis 2 des Wertes 8 3, 395 00:17:25,300 --> 00:17:29,630 und in der Tat, was ist schön daran ist, daß 3 ist genau die Anzahl von Malen 396 00:17:29,630 --> 00:17:33,320 dass Sie eine Liste zu teilen der Länge 8 wieder und wieder, 397 00:17:33,320 --> 00:17:36,160 und immer wieder, bis Sie sind links mit Listen von nur Größe 1. 398 00:17:36,160 --> 00:17:36,660 Recht? 399 00:17:36,660 --> 00:17:40,790 8 geht bis 4, geht in 2, auf 1 geht, und das ist 400 00:17:40,790 --> 00:17:43,470 reflektiert genau das Bild hatten wir eben noch. 401 00:17:43,470 --> 00:17:47,160 So ein wenig geistige Gesundheit zu überprüfen, wo der Logarithmus tatsächlich beteiligt. 402 00:17:47,160 --> 00:17:50,180 >> So, jetzt ist das, was andere hier beteiligt? n. 403 00:17:50,180 --> 00:17:53,440 So bemerken, dass jeder Zeit, die ich teilen die Liste, 404 00:17:53,440 --> 00:17:58,260 wenn auch in umgekehrter Reihenfolge in der Geschichte hier war ich noch zu tun n Dinge. 405 00:17:58,260 --> 00:18:02,320 Das Vereinigungsschritt erforderlich, dass Ich berühre jede eine der Zahlen, 406 00:18:02,320 --> 00:18:05,060 um es in schieben seinen geeigneten Platz. 407 00:18:05,060 --> 00:18:10,760 Also auch wenn die Höhe dieses Diagramm der Größe log n von n oder 3, 408 00:18:10,760 --> 00:18:13,860 Insbesondere wird in anderen Worten Ich habe drei Divisionen hier. 409 00:18:13,860 --> 00:18:18,800 Wie viel Arbeit habe ich horizontal zu tun entlang dieser Tabelle jedes Mal? 410 00:18:18,800 --> 00:18:21,110 >> Nun, ich habe n Schritte arbeiten, weil, wenn ich 411 00:18:21,110 --> 00:18:24,080 bekam vier Elemente und die vier Elemente, und ich brauche, um sie miteinander zu verschmelzen. 412 00:18:24,080 --> 00:18:26,040 Ich brauche, um durch zu gehen diese vier, und diese vier, 413 00:18:26,040 --> 00:18:28,123 schließlich, sie zu verschmelzen zurück in acht Elementen. 414 00:18:28,123 --> 00:18:32,182 Wenn umgekehrt habe ich acht Finger bekam hier, die ich nicht tun, und acht 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- wenn ich bekam vier Finger hier, 416 00:18:34,390 --> 00:18:37,380 was ich tue, vier Finger hier, was ich tue, 417 00:18:37,380 --> 00:18:40,590 dann ist das die gleiche Beispiel wie zuvor, wenn ich es tue 418 00:18:40,590 --> 00:18:44,010 haben acht Finger zwar in Gesamt, was ich kann, Art, zu tun. 419 00:18:44,010 --> 00:18:47,950 Ich kann hier genau das zu tun, dann kann ich mit Sicherheit 420 00:18:47,950 --> 00:18:50,370 Zusammenführen all dieser Listen der Größe 1 zusammen. 421 00:18:50,370 --> 00:18:54,050 Aber ich sicherlich zu schauen an jedem Element genau einmal. 422 00:18:54,050 --> 00:18:59,640 So dass die Höhe dieses Verfahrens ist log n, die Breite dieses Prozesses sozusagen 423 00:18:59,640 --> 00:19:02,490 n ist, so dass das, was wir scheinen zu haben, ist es letztendlich, 424 00:19:02,490 --> 00:19:06,470 Laufzeit der Größe n mal log n. 425 00:19:06,470 --> 00:19:08,977 >> Mit anderen Worten, teilten wir die Liste, log n-mal, 426 00:19:08,977 --> 00:19:11,810 aber jedes Mal, wenn wir das täten, wir hatten jede eines der Elemente zu berühren 427 00:19:11,810 --> 00:19:13,560 um sie zu verschmelzen alle zusammen, die 428 00:19:13,560 --> 00:19:18,120 wurde Schritt n, also müssen wir das n-fache log n, oder als ein Computerwissenschaftler würden sagen, 429 00:19:18,120 --> 00:19:20,380 asymptotisch, die würde das große Wort 430 00:19:20,380 --> 00:19:22,810 beschreiben die Ober auf einer Laufzeit gebunden, 431 00:19:22,810 --> 00:19:28,010 wir in einem großen o laufen log n Mal so zu sprechen. 432 00:19:28,010 --> 00:19:31,510 >> Nun ist dies von Bedeutung, da daran erinnern, was die Laufzeiten waren 433 00:19:31,510 --> 00:19:34,120 mit Bubble-Sort, und Auswahl sortieren und Insertion Sort, 434 00:19:34,120 --> 00:19:38,200 und sogar ein paar andere, die vorhanden sind, n quadriert war, wo wir waren. 435 00:19:38,200 --> 00:19:39,990 Und Sie können, Art, finden Sie diese hier. 436 00:19:39,990 --> 00:19:45,720 Wenn n quadriert ist offensichtlich n-mal n, aber hier haben wir n mal log n, 437 00:19:45,720 --> 00:19:48,770 und wir von Woche wissen bereits, Null ist, das log n die logarithmische, 438 00:19:48,770 --> 00:19:50,550 ist etwas besser als linear. 439 00:19:50,550 --> 00:19:52,930 Schließlich erinnern, das Bild mit der roten und der gelben 440 00:19:52,930 --> 00:19:56,500 und die grünen Linien, die wir zogen, die grüne logarithmischen Linie war viel geringer. 441 00:19:56,500 --> 00:20:00,920 Und daher viel besser und schneller als die geraden gelben und roten Linien, 442 00:20:00,920 --> 00:20:05,900 n mal log n ist in der Tat besser als n mal n oder n quadriert. 443 00:20:05,900 --> 00:20:09,110 >> So scheinen wir haben identifiziert einen Algorithmus merge 444 00:20:09,110 --> 00:20:11,870 Art, die in viel läuft Kürzere Zeit, und in der Tat, 445 00:20:11,870 --> 00:20:16,560 das ist, warum, zu Beginn dieser Woche, wenn Wir sahen, dass Wettbewerb zwischen Luftblase 446 00:20:16,560 --> 00:20:20,750 Sortieren, Auswahl sortieren und zusammenführen Sortieren, Mergesort wirklich, wirklich gewonnen. 447 00:20:20,750 --> 00:20:23,660 Und in der Tat, wir haben nicht einmal warten, für Bubble-Sort und Auswahl sort 448 00:20:23,660 --> 00:20:24,790 beenden. 449 00:20:24,790 --> 00:20:27,410 >> Werfen wir nun einen weiteren Pass in diesem, von einem etwas mehr 450 00:20:27,410 --> 00:20:31,030 formalen Perspektive, nur in Fall schwingt das besser 451 00:20:31,030 --> 00:20:33,380 als dieser höheren Ebene diskutiert. 452 00:20:33,380 --> 00:20:34,880 Also hier ist der Algorithmus noch einmal. 453 00:20:34,880 --> 00:20:36,770 Fragen wir uns, Was die Laufzeit 454 00:20:36,770 --> 00:20:39,287 ist dieser Algorithmen verschiedene Schritte? 455 00:20:39,287 --> 00:20:41,620 Lassen Sie uns teilen sie in der ersten Gehäuse und das zweite Gehäuse. 456 00:20:41,620 --> 00:20:46,280 Der IF und der andere in der ZF-Fall Falls n kleiner als 2 ist, nur zurückkehren. 457 00:20:46,280 --> 00:20:47,580 Fühlt konstante Zeit. 458 00:20:47,580 --> 00:20:50,970 Es ist, Art von, wie zwei Schritte, Falls n kleiner als 2 ist, dann zurückzukehren. 459 00:20:50,970 --> 00:20:54,580 Aber wie wir am Montag sagte, konstante Zeit oder große o von 1, 460 00:20:54,580 --> 00:20:57,130 können zwei Schritte, drei sein Schritte, auch 1000 Schritte. 461 00:20:57,130 --> 00:20:59,870 Was zählt, ist, dass es eine konstante Anzahl von Schritten. 462 00:20:59,870 --> 00:21:03,240 Also die gelb markierten Pseudo Hier läuft, wir nennen es, 463 00:21:03,240 --> 00:21:04,490 konstante Zeit. 464 00:21:04,490 --> 00:21:06,780 Also mehr formal, und wir zu-- gehende 465 00:21:06,780 --> 00:21:09,910 wird das Ausmaß sein, die wir Formalisierung dieses Recht now-- T n, 466 00:21:09,910 --> 00:21:15,030 die Laufzeit eines Problems das dauert n Somethings als Eingang, 467 00:21:15,030 --> 00:21:19,150 gleich große o von einem, Falls n kleiner als 2 ist. 468 00:21:19,150 --> 00:21:20,640 Es ist also davon abhängig, dass. 469 00:21:20,640 --> 00:21:24,150 So klar zu sein, falls n kleiner ist 2, haben wir eine sehr kurze Liste, dann 470 00:21:24,150 --> 00:21:29,151 die Laufzeit T n, wobei n 1 oder 0 sind, in diesem speziellen Fall, 471 00:21:29,151 --> 00:21:30,650 ist es nur geht, um konstante Zeit. 472 00:21:30,650 --> 00:21:32,691 Das wird man nehmen Schritt, zwei Schritte, was auch immer. 473 00:21:32,691 --> 00:21:33,950 Es ist eine feste Anzahl von Schritten. 474 00:21:33,950 --> 00:21:38,840 >> Also die saftigen Teil sicherlich in sein der andere Fall, in dem Pseudocode. 475 00:21:38,840 --> 00:21:40,220 Die ELSE Fall. 476 00:21:40,220 --> 00:21:44,870 Sortieren linken Hälfte der Elemente, sortieren rechts die Hälfte der Elemente, zusammenführen sortierten Hälften. 477 00:21:44,870 --> 00:21:46,800 Wie lange dauert jeder dieser Schritte zu unternehmen? 478 00:21:46,800 --> 00:21:49,780 Nun, wenn die Lauf Zeit, um n Elemente zu sortieren 479 00:21:49,780 --> 00:21:53,010 ist, nennen wir es sehr generisch, T N, 480 00:21:53,010 --> 00:21:55,500 dann die Sortierung der linken Hälfte der Elemente 481 00:21:55,500 --> 00:21:59,720 ist, Art von, wie zu sagen, T n durch 2 geteilt, 482 00:21:59,720 --> 00:22:03,000 und in ähnlicher Weise die Sortierung der rechten Hälfte von Elementen ist, Art von, wie zu sagen, 483 00:22:03,000 --> 00:22:06,974 T n 2 geteilt und dann Zusammenführen der sortierten Hälften. 484 00:22:06,974 --> 00:22:08,890 Nun, wenn ich habe einige Anzahl der Elemente hier 485 00:22:08,890 --> 00:22:11,230 wie vier, und eine bestimmte Anzahl von Elementen Sie hier, wie vier, 486 00:22:11,230 --> 00:22:14,650 und ich habe zu jedem dieser vier zusammenführen in, und jede dieser vier, eins 487 00:22:14,650 --> 00:22:17,160 nach dem anderen, so dass schließlich habe ich acht Elementen. 488 00:22:17,160 --> 00:22:20,230 Es fühlt sich an wie das ist große o n Schritte? 489 00:22:20,230 --> 00:22:23,500 Wenn ich n Fingern und jeder bekam sie muss in Ort zusammengeführt werden, 490 00:22:23,500 --> 00:22:25,270 das ist wie ein anderes n Schritte. 491 00:22:25,270 --> 00:22:27,360 >> Also ja formelhaft, wir können dies zum Ausdruck bringen, 492 00:22:27,360 --> 00:22:29,960 wenn auch ein wenig beängstigend auf den ersten Blick, aber es ist etwas 493 00:22:29,960 --> 00:22:31,600 dass fängt genau diese Logik. 494 00:22:31,600 --> 00:22:35,710 Die Laufzeit T n, falls n größer als oder gleich 2 ist. 495 00:22:35,710 --> 00:22:42,500 In diesem Fall wird der ELSE Fall ist T n geteilt durch 2 plus T von n geteilt durch 2, 496 00:22:42,500 --> 00:22:45,320 plus große o n, einige lineare Reihe von Schritten, 497 00:22:45,320 --> 00:22:51,630 vielleicht genau n, vielleicht 2 mal n, aber es ist etwa, um von n. 498 00:22:51,630 --> 00:22:54,060 So dass auch das ist, wie wir können, Ausdruck dieses formelhaft. 499 00:22:54,060 --> 00:22:56,809 Jetzt würden Sie nicht, es sei denn Sie es in Ihrem Kopf aufgenommen haben, 500 00:22:56,809 --> 00:22:58,710 oder schauen Sie in die Rücken eines Lehrbuch, dass 501 00:22:58,710 --> 00:23:00,501 könnte ein wenig haben Spickzettel am Ende, 502 00:23:00,501 --> 00:23:03,940 aber dies ist in der Tat werde geben uns eine große o n log n, 503 00:23:03,940 --> 00:23:06,620 weil die Rezidiv DASS Sie hier zu sehen auf dem Bildschirm, 504 00:23:06,620 --> 00:23:09,550 wenn Sie tatsächlich tat es aus, mit eine unendliche Anzahl von Beispielen 505 00:23:09,550 --> 00:23:13,000 oder Sie können es formelhaft taten, würden Sie sehen, dass dies, weil dieser Formel 506 00:23:13,000 --> 00:23:17,100 selbst ist rekursiv, mit t n mehr als etwas auf der rechten Seite, 507 00:23:17,100 --> 00:23:21,680 und t n über auf der linken, so kann tatsächlich ausgedrückt werden letztendlich 508 00:23:21,680 --> 00:23:24,339 so groß los n log n. 509 00:23:24,339 --> 00:23:26,130 Wenn nicht überzeugt, das ist, Geldstrafe für jetzt, 510 00:23:26,130 --> 00:23:28,960 nehmen auf den Glauben, dass das ist, ja, was das Wiederauftreten zu, 511 00:23:28,960 --> 00:23:31,780 aber das ist nur ein bisschen mehr von einem mathematischen Ansatz zu suchen 512 00:23:31,780 --> 00:23:36,520 an der Laufzeit merge sort auf der Grundlage ihrer Pseudo allein. 513 00:23:36,520 --> 00:23:39,030 >> Lassen Sie uns jetzt ein bisschen ein Verschnaufpause von all dem, 514 00:23:39,030 --> 00:23:41,710 und schauen Sie sich ein bestimmter ehemaliger Senator, der 515 00:23:41,710 --> 00:23:44,260 könnte ein wenig bekannt vor, , die sich mit Googles Eric saß 516 00:23:44,260 --> 00:23:48,410 Schmidt, vor einiger Zeit für ein Interview auf der Bühne, vor einem ganzen Bündel 517 00:23:48,410 --> 00:23:53,710 Menschen letztlich sprechen ein Thema, das ist ziemlich jetzt vertraut. 518 00:23:53,710 --> 00:23:54,575 Lass uns einen Blick darauf werfen. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Jetzt Senator, du bist hier bei Google, 521 00:24:03,890 --> 00:24:09,490 und Ich mag an die denken, Präsidentschaft, wie ein Vorstellungsgespräch. 522 00:24:09,490 --> 00:24:11,712 Jetzt ist es schwer, einen Job als Präsident zu bekommen. 523 00:24:11,712 --> 00:24:12,670 PRÄSIDENT OBAMA: Richtig. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: Und du bist jetzt tun [unverständlich]. 525 00:24:13,940 --> 00:24:15,523 Es ist auch schwer, einen Job bei Google zu bekommen. 526 00:24:15,523 --> 00:24:17,700 PRÄSIDENT OBAMA: Richtig. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Wir haben Fragen, und wir bitten unsere Kandidaten Fragen, 528 00:24:21,330 --> 00:24:24,310 und dieses ist von Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> PRÄSIDENT OBAMA: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Was? 531 00:24:27,005 --> 00:24:28,130 Ihr Jungs denken, ich bin verrückt? 532 00:24:28,130 --> 00:24:30,590 Es ist hier richtig. 533 00:24:30,590 --> 00:24:33,490 Was ist die effizienteste Art, sortieren eine Million 32-Bit-Ganzzahlen? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> PRÄSIDENT OBAMA: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Manchmal vielleicht tut mir leid, maybe-- 537 00:24:41,020 --> 00:24:42,750 PRÄSIDENT OBAMA: Nein, nein, nein, nein, nein, ich think-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: Das ist nicht es-- 539 00:24:43,240 --> 00:24:45,430 PRÄSIDENT OBAMA: I denke, denke ich, die Blase 540 00:24:45,430 --> 00:24:46,875 Art wäre der falsche Weg zu gehen. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Komm schon. 543 00:24:50,535 --> 00:24:52,200 Die ihm das gesagt? 544 00:24:52,200 --> 00:24:54,020 OK. 545 00:24:54,020 --> 00:24:55,590 Ich hatte nicht den Computerwissenschaften an-- 546 00:24:55,590 --> 00:24:58,986 >> PRÄSIDENT OBAMA: Wir haben haben unsere Spione dort. 547 00:24:58,986 --> 00:24:59,860 PROFESSOR: Alles klar. 548 00:24:59,860 --> 00:25:03,370 Lassen Sie uns hinter uns lassen jetzt die theoretische Welt der Algorithmen 549 00:25:03,370 --> 00:25:06,520 in der asymptotischen Analysis , sowie auf einige Themen zurück 550 00:25:06,520 --> 00:25:09,940 von Woche Null und Eins und Start einige Stützräder zu entfernen, 551 00:25:09,940 --> 00:25:10,450 wenn du möchtest. 552 00:25:10,450 --> 00:25:13,241 So dass Sie wirklich verstehen, schließlich von Grund auf, was ist 553 00:25:13,241 --> 00:25:16,805 geht unter der Haube, wenn Sie Schreiben, Kompilieren und Ausführen von Programmen. 554 00:25:16,805 --> 00:25:19,680 Daran erinnern, insbesondere, dass dies die erste C-Programm sahen wir uns an, 555 00:25:19,680 --> 00:25:22,840 eine kanonische, einfaches Programm von Art, relativ gesehen, 556 00:25:22,840 --> 00:25:24,620 wobei, er druckt, Hallo Welt. 557 00:25:24,620 --> 00:25:27,610 Und daran erinnern, dass ich gesagt habe, das Verfahren dass Quellcode durchläuft 558 00:25:27,610 --> 00:25:28,430 Genau diese. 559 00:25:28,430 --> 00:25:31,180 Sie übernehmen Ihr Quellcode, übergeben sie durch einen Compiler, wie Clang, 560 00:25:31,180 --> 00:25:34,650 und heraus kommt Objekt-Code, dass könnte wie folgt, Nullen und Einsen zu suchen 561 00:25:34,650 --> 00:25:37,880 dass die CPU des Computers, Zentral Verarbeitungseinheit oder des Gehirns, 562 00:25:37,880 --> 00:25:39,760 letztendlich versteht. 563 00:25:39,760 --> 00:25:42,460 >> Es stellt sich heraus, daß das ein wenig eine zu starke Vereinfachung, 564 00:25:42,460 --> 00:25:44,480 dass wir jetzt in eine Stellung auseinander zu necken 565 00:25:44,480 --> 00:25:46,720 um zu verstehen, was wirklich war geht unter der Haube 566 00:25:46,720 --> 00:25:48,600 jedes Mal wenn Sie laufen Klappern oder allgemeiner, 567 00:25:48,600 --> 00:25:53,040 jedes Mal, wenn Sie ein Programm zu machen, mit Make und CF-50 IDE. 568 00:25:53,040 --> 00:25:56,760 Insbesondere solche Sachen wird diese zunächst erzeugt wird, 569 00:25:56,760 --> 00:25:58,684 wenn Sie zuerst Ihr Programm kompilieren. 570 00:25:58,684 --> 00:26:00,600 Mit anderen Worten, wenn man nehmen Sie Ihre Source-Code 571 00:26:00,600 --> 00:26:04,390 und kompilieren Sie es, was ist zuerst von Clang ausgegeben 572 00:26:04,390 --> 00:26:06,370 ist etwas, als Assembler-Code bekannt. 573 00:26:06,370 --> 00:26:08,990 Und in der Tat sieht es genau so. 574 00:26:08,990 --> 00:26:11,170 >> Ich lief ein Befehl an die Befehlszeile früher. 575 00:26:11,170 --> 00:26:16,260 Clang dash Kapital s hello.c, und dies erzeugt eine Datei 576 00:26:16,260 --> 00:26:19,490 für mich genannt hello.s, innerhalb dessen waren genau 577 00:26:19,490 --> 00:26:22,290 diese Inhalte, und ein wenig mehr oberhalb und etwas unterhalb, 578 00:26:22,290 --> 00:26:25,080 aber ich habe die saftigsten setzen Informationen hier auf dem Bildschirm. 579 00:26:25,080 --> 00:26:29,190 Und wenn Sie genau hinsehen, werden Sie sehen, zumindest ein paar vertraute Keywords. 580 00:26:29,190 --> 00:26:31,330 Wir haben Haupt oben. 581 00:26:31,330 --> 00:26:35,140 Wir haben in der Mitte printf. 582 00:26:35,140 --> 00:26:38,670 Und wir haben auch hallo Welt Backslash n in Anführungszeichen unten. 583 00:26:38,670 --> 00:26:42,450 >> Und alles andere hier ist sehr gering Anleitungen Level 584 00:26:42,450 --> 00:26:45,500 daß die CPU des Computers versteht. 585 00:26:45,500 --> 00:26:50,090 CPU-Anweisungen, die Speicher zu verschieben um, dass Last Strings aus dem Speicher, 586 00:26:50,090 --> 00:26:52,750 und schließlich, drucken Dinge auf dem Bildschirm. 587 00:26:52,750 --> 00:26:56,780 Nun, was passiert, wenn nach Dieses Assemblercode generiert? 588 00:26:56,780 --> 00:26:59,964 Letztlich, die Sie tun, in der Tat, noch generieren Objektcode. 589 00:26:59,964 --> 00:27:02,630 Aber die Schritte, die wirklich nun schon unter der Haube 590 00:27:02,630 --> 00:27:04,180 schauen ein wenig mehr davon. 591 00:27:04,180 --> 00:27:08,390 Quellcode wird Assembler-Code, die dann zur Objektcode, 592 00:27:08,390 --> 00:27:11,930 und hier die operative Worte sind, dass, wenn Sie Ihren Quellcode zu kompilieren, 593 00:27:11,930 --> 00:27:16,300 heraus kommt Assembler-Code, und dann wenn Sie Ihren Assembler-Code zusammenzubauen, 594 00:27:16,300 --> 00:27:17,800 heraus kommt Objektcode. 595 00:27:17,800 --> 00:27:20,360 >> Jetzt Clang ist super anspruchsvoll, wie eine Menge von Compilern, 596 00:27:20,360 --> 00:27:23,151 und alle diese Schritte tut, zusammen, und es ist nicht notwendigerweise 597 00:27:23,151 --> 00:27:25,360 Ausgangs jede Zwischen Dateien, die Sie auch sehen können. 598 00:27:25,360 --> 00:27:28,400 Es kompiliert nur Dinge, Das ist der allgemeine Begriff, 599 00:27:28,400 --> 00:27:30,000 beschreibt diesen gesamten Prozess. 600 00:27:30,000 --> 00:27:32,000 Aber wenn Sie wirklich wollen, Insbesondere ist, da ist 601 00:27:32,000 --> 00:27:34,330 viel mehr los dort. 602 00:27:34,330 --> 00:27:38,860 >> Aber lassen Sie uns auch überlegen nun, dass auch dass Super einfaches Programm, hello.c, 603 00:27:38,860 --> 00:27:40,540 heißt Funktion. 604 00:27:40,540 --> 00:27:41,870 Es fordert printf. 605 00:27:41,870 --> 00:27:46,900 Aber ich wollte nicht schreiben, printf, ja, das kommt mit c, so zu sprechen. 606 00:27:46,900 --> 00:27:51,139 Es ist eine Funktion, die Rückrufaktion ist in Standard io.h erklärte die 607 00:27:51,139 --> 00:27:53,180 eine Header-Datei, die ist ein Thema werden wir tatsächlich 608 00:27:53,180 --> 00:27:55,780 tauchen Sie ein in mehr Tiefe, bevor lang. 609 00:27:55,780 --> 00:27:58,000 Aber eine Header-Datei ist in der Regel begleitet 610 00:27:58,000 --> 00:28:02,920 durch einen Code-Datei Quellcode-Datei, so dass ähnlich wie es existiert Standard io.h 611 00:28:02,920 --> 00:28:05,930 >> Vor einiger Zeit, jemanden, oder someones, schrieb auch 612 00:28:05,930 --> 00:28:11,040 eine Datei namens Standard io.c, in die den eigentlichen Definitionen, 613 00:28:11,040 --> 00:28:15,220 oder Implementierungen von printf, und Trauben von anderen Funktionen, 614 00:28:15,220 --> 00:28:16,870 tatsächlich geschrieben. 615 00:28:16,870 --> 00:28:22,140 So daß bei, wenn man bedenkt, mit hier auf der linken Seite, hallo.c, dass, wenn 616 00:28:22,140 --> 00:28:26,250 kompiliert, gibt uns hello.s, auch wenn Clang nicht Einsparung an einem Ort, die Mühe 617 00:28:26,250 --> 00:28:31,360 wir können es sehen, und das Assembler-Code erhält in hello.o, montiert die 618 00:28:31,360 --> 00:28:34,630 ist in der Tat der Standardname gegeben, wenn Sie Quellcode zu kompilieren 619 00:28:34,630 --> 00:28:39,350 Code in Objektcode, sind aber nicht ganz bereit, es noch nicht ausführen, 620 00:28:39,350 --> 00:28:41,460 weil weiteren Schritt zu geschehen hat, und hat 621 00:28:41,460 --> 00:28:44,440 wurde für die letzten paar geschieht Wochen, vielleicht unbemerkt von Ihnen. 622 00:28:44,440 --> 00:28:47,290 >> Insbesondere irgendwo in CS50 IDE, und dies 623 00:28:47,290 --> 00:28:49,870 Auch wird ein bisschen eine sein Vereinfachung für einen Moment, 624 00:28:49,870 --> 00:28:54,670 gibt es, oder war eine Zeit, eine Datei namens Standard io.c, 625 00:28:54,670 --> 00:28:58,440 dass jemand in kompilierte Standard io.s oder den Gegenwert, 626 00:28:58,440 --> 00:29:02,010 dass jemand dann zusammengebaut in Standard-io.o, 627 00:29:02,010 --> 00:29:04,600 oder es stellt sich heraus in einen etwas andere Datei 628 00:29:04,600 --> 00:29:07,220 Format, das eine andere haben kann, Dateierweiterung zusammen, 629 00:29:07,220 --> 00:29:11,720 aber in der Theorie und konzeptionell genau jene Schritte in irgendeiner Form geschehen. 630 00:29:11,720 --> 00:29:14,060 Was bedeutet, dass nun wenn ich ein Programm schreiben, 631 00:29:14,060 --> 00:29:17,870 hello.c, dass, nur sagt: Hallo Welt, und ich bin mit Code jemand anderes 632 00:29:17,870 --> 00:29:22,480 wie printf, die einst eine war Zeit, in einer Datei namens Standard io.c, 633 00:29:22,480 --> 00:29:26,390 dann irgendwie muss ich meine zu nehmen Objektcode, mein Nullen und Einsen, 634 00:29:26,390 --> 00:29:29,260 und diese Person die Aufgabe Code oder Nullen und Einsen, 635 00:29:29,260 --> 00:29:34,970 und irgendwie miteinander zu verknüpfen eine letzte Datei namens hallo, daß 636 00:29:34,970 --> 00:29:38,070 hat alle Nullen und diejenigen aus meinem Hauptfunktion, 637 00:29:38,070 --> 00:29:40,830 und alle Nullen und diejenigen für printf. 638 00:29:40,830 --> 00:29:44,900 >> Und in der Tat ist, dass letzte Prozess genannt, die Verknüpfung Ihrer Objektcode. 639 00:29:44,900 --> 00:29:47,490 Dessen Ausgangs ist eine ausführbare Datei. 640 00:29:47,490 --> 00:29:49,780 So in Fairness, bei der am Ende des Tages, nichts 641 00:29:49,780 --> 00:29:52,660 seit einer Woche verändert, als wir anfing Kompilieren von Programmen. 642 00:29:52,660 --> 00:29:55,200 Zwar all dies wurde geschieht unter der Haube, 643 00:29:55,200 --> 00:29:57,241 aber jetzt sind wir in der Lage sind wo wir können tatsächlich 644 00:29:57,241 --> 00:29:58,794 necken auseinander diese verschiedenen Schritte. 645 00:29:58,794 --> 00:30:00,710 Und in der Tat am Ende des Tages, sind wir immer noch 646 00:30:00,710 --> 00:30:04,480 links mit Nullen und Einsen, die ist eigentlich ein großer segue jetzt 647 00:30:04,480 --> 00:30:08,620 zu einer anderen Funktion von C, das wir haben nicht sehr wahrscheinlich nutzen musste 648 00:30:08,620 --> 00:30:11,250 auf dem neuesten Stand, wie Bit-Operatoren bekannt. 649 00:30:11,250 --> 00:30:15,220 Mit anderen Worten, die bisher, zu jeder Zeit wir haben mit Daten, die in C oder Variablen C behandelt, 650 00:30:15,220 --> 00:30:17,660 wir haben Dinge wie gehabt Zeichen und schwimmt ins 651 00:30:17,660 --> 00:30:21,990 und sehnt sich und Doppelzimmer und dergleichen, aber all das sind mindestens acht Bits. 652 00:30:21,990 --> 00:30:25,550 Wir haben noch nie in der Lage sein Manipulation einzelner Bits, 653 00:30:25,550 --> 00:30:28,970 obwohl eines einzelnen Bits, die wir wissen, kann eine 0 und 1 repräsentieren. 654 00:30:28,970 --> 00:30:32,640 Jetzt stellt sich heraus, dass in C, die Sie kann der Zugriff auf einzelne Bits zu erhalten, 655 00:30:32,640 --> 00:30:35,530 wenn Sie wissen, die Syntax, , mit denen, um an sie heranzukommen. 656 00:30:35,530 --> 00:30:38,010 >> Werfen wir also einen Blick bei Bit-Operatoren. 657 00:30:38,010 --> 00:30:41,700 Also hier abgebildet sind ein paar Symbole, wir haben, Art, Art, gesehen. 658 00:30:41,700 --> 00:30:45,580 Ich sehe ein Und-Zeichen, eine vertikale bar, und einige andere als gut, 659 00:30:45,580 --> 00:30:49,430 und daran erinnern, dass die Kaufmanns-Und-Zeichen ist etwas, was wir gesehen haben. 660 00:30:49,430 --> 00:30:54,060 Die logische UND-Operator, wo Sie zwei von ihnen zusammen, oder die logische ODER 661 00:30:54,060 --> 00:30:56,300 Betreiber, in dem Sie habe zwei vertikale Balken. 662 00:30:56,300 --> 00:31:00,550 Bit-Operatoren, auf die wir siehe arbeiten auf Bits einzeln, 663 00:31:00,550 --> 00:31:03,810 nur ein einzelnes und-Zeichen zu verwenden, ein Einzel vertikalen Balken, der Caret-Zeichen 664 00:31:03,810 --> 00:31:06,620 als Nächstes kommt, den kleinen Tilde, und dann nach links 665 00:31:06,620 --> 00:31:08,990 Halter links Halter oder rechte Klammer rechte Klammer. 666 00:31:08,990 --> 00:31:10,770 Jedes von diesen unterschiedliche Bedeutungen haben. 667 00:31:10,770 --> 00:31:11,950 >> In der Tat, lassen Sie uns einen Blick. 668 00:31:11,950 --> 00:31:16,560 Lassen Sie uns gehen alte Schule heute und Verwendung ein Touch-Screen aus vergangenen Zeiten, 669 00:31:16,560 --> 00:31:18,002 wie eine weiße Tafel bekannt. 670 00:31:18,002 --> 00:31:19,710 Und das weiße Tafel wird uns erlauben, 671 00:31:19,710 --> 00:31:27,360 einige ziemlich einfache Symbole zum Ausdruck bringen, oder vielmehr einige recht einfache Formeln, 672 00:31:27,360 --> 00:31:29,560 dass wir dann letztendlich Hebelwirkung, um 673 00:31:29,560 --> 00:31:33,230 für den Zugriff auf einzelne Bits innerhalb eines C-Programms. 674 00:31:33,230 --> 00:31:34,480 Mit anderen Worten, lassen Sie uns dies tun. 675 00:31:34,480 --> 00:31:37,080 Sprechen wir zuerst für ein Moment über Und-Zeichen, 676 00:31:37,080 --> 00:31:39,560 das ist die bitweise UND-Operator. 677 00:31:39,560 --> 00:31:42,130 In anderen Worten, dies ist ein Operator, der erlaubt 678 00:31:42,130 --> 00:31:45,930 mir, eine linke Variable haben Typischerweise und eine rechte Variable 679 00:31:45,930 --> 00:31:50,640 oder ein einzelner Wert, dass, wenn wir UND sie zusammen, gibt mir ein Endergebnis. 680 00:31:50,640 --> 00:31:51,560 Also, was ich meine? 681 00:31:51,560 --> 00:31:54,840 Wenn in einem Programm, eine Variable müssen Sie daß speichert einen dieser Werte, 682 00:31:54,840 --> 00:31:58,000 oder lassen Sie es einfach halten und nur schreiben, Nullen und Einsen einzeln, 683 00:31:58,000 --> 00:32:00,940 hier ist, wie das kaufmännische Bediener arbeitet. 684 00:32:00,940 --> 00:32:06,400 0 0 Ampersand wird zu 0 gleich. 685 00:32:06,400 --> 00:32:07,210 Nun, warum ist das so? 686 00:32:07,210 --> 00:32:09,291 >> Es ist sehr ähnlich, Boolesche Ausdrücke, 687 00:32:09,291 --> 00:32:10,540 dass wir bisher diskutiert. 688 00:32:10,540 --> 00:32:15,800 Wenn Sie nach dem alle denken, das 0 ist false 0 false false false 689 00:32:15,800 --> 00:32:18,720 ist, wie wir besprochen haben logischerweise auch falsch. 690 00:32:18,720 --> 00:32:20,270 So bekommen wir hier 0 als auch. 691 00:32:20,270 --> 00:32:24,390 Wenn Sie eine 0 Und-Zeichen 1, und das auch, 692 00:32:24,390 --> 00:32:29,890 wird auf 0 gesetzt, weil hierfür linke Ausdruck wahr oder 1 ist, 693 00:32:29,890 --> 00:32:32,360 es müsste wahre und wahr zu sein. 694 00:32:32,360 --> 00:32:36,320 Aber hier haben wir falsch und wahr oder 0 und 1. 695 00:32:36,320 --> 00:32:42,000 Jetzt wieder, wenn wir 1 Und-Zeichen 0, das auch, wird zu 0, 696 00:32:42,000 --> 00:32:47,240 und wenn wir ein kaufmännisches Und-Zeichen 1, schließlich haben wir ein 1-Bit. 697 00:32:47,240 --> 00:32:50,340 Also mit anderen Worten, wir nicht tun, etwas Interessantes mit diesem Operator 698 00:32:50,340 --> 00:32:51,850 nur noch, diese kaufmännisches Und-Operator. 699 00:32:51,850 --> 00:32:53,780 Es ist die bitweise UND-Operator. 700 00:32:53,780 --> 00:32:57,290 Aber das sind die Zutaten , über die wir tun können, 701 00:32:57,290 --> 00:32:59,240 interessante Dinge, wie wir bald sehen werden. 702 00:32:59,240 --> 00:33:02,790 >> Jetzt schauen wir uns nur den Einzel Senkrechte Striche hier auf der rechten Seite. 703 00:33:02,790 --> 00:33:06,710 Wenn ich eine 0-Bit und ich Oder er mit, die bitweise 704 00:33:06,710 --> 00:33:11,030 OR-Operator, ein weiterer 0-Bit, das wird mir 0 zu geben. 705 00:33:11,030 --> 00:33:17,540 Wenn ich ein 0-Bit und OR mit zu nehmen ein 1-Bit, dann werde ich auf 1 zu bekommen. 706 00:33:17,540 --> 00:33:19,830 Und in der Tat, nur für Klarheit, lass mich gehen zurück, 707 00:33:19,830 --> 00:33:23,380 so dass meine vertikalen Balken sind nicht für 1 irrt. 708 00:33:23,380 --> 00:33:26,560 Lassen Sie mich alles neu schreiben mein 1 ist ein wenig mehr 709 00:33:26,560 --> 00:33:32,700 klar, so dass wir weiter sehen, wenn ich haben eine 1 oder 0, das wird eine 1, 710 00:33:32,700 --> 00:33:39,060 und wenn ich eine 1 oder 1, die, Auch wird eine 1 sein. 711 00:33:39,060 --> 00:33:42,900 So können Sie logisch, dass die OR sehen Operator verhält sich ganz anders. 712 00:33:42,900 --> 00:33:48,070 Das gibt mir 0 oder 0 gibt mir 0, aber jede andere Kombination gibt mir 1. 713 00:33:48,070 --> 00:33:52,480 Solange ich eine 1 in das haben Formel, wird das Ergebnis würde 1 sein. 714 00:33:52,480 --> 00:33:55,580 >> Im Gegensatz zu dem UND Betreiber, das Und-Zeichen, 715 00:33:55,580 --> 00:34:00,940 nur wenn ich zwei 1 in der Gleichung, ich tatsächlich eine 1 aus. 716 00:34:00,940 --> 00:34:02,850 Jetzt gibt es ein paar andere Betreiber als auch. 717 00:34:02,850 --> 00:34:04,810 Einer von ihnen ist ein wenig komplizierter. 718 00:34:04,810 --> 00:34:07,980 Also lassen Sie mich gehen Sie vor und löschen dies etwas Platz. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Und lassen Sie uns einen Blick auf die Caret-Zeichen, nur für einen Augenblick. 721 00:34:16,460 --> 00:34:18,210 Dies ist typischerweise ein Zeichen, das Sie eingeben können 722 00:34:18,210 --> 00:34:21,420 auf Ihrer Tastatur die Umschalttaste gedrückt halten und dann eine der Zahlen oben auf Ihrer US 723 00:34:21,420 --> 00:34:22,250 Tastatur. 724 00:34:22,250 --> 00:34:26,190 >> Das ist also die ausschließliche OR-Operator, Exklusiv-ODER. 725 00:34:26,190 --> 00:34:27,790 So sahen wir nur den OR-Operator. 726 00:34:27,790 --> 00:34:29,348 Dies ist der Exklusiv-Oder-Operator. 727 00:34:29,348 --> 00:34:30,639 Was ist eigentlich der Unterschied? 728 00:34:30,639 --> 00:34:34,570 Nun lassen Sie uns einfach an der Formel zu suchen, und dies als Zutaten letztendlich. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Ich werde sagen, ist immer 0. 731 00:34:39,650 --> 00:34:41,400 Das ist die Definition von XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 wird zu 1 sein. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 wird zu 1 sein, und 1 XOR 1 sein wird? 734 00:34:58,810 --> 00:34:59,890 Wrong? 735 00:34:59,890 --> 00:35:00,520 Oder rechts? 736 00:35:00,520 --> 00:35:01,860 Ich weiß es nicht. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Nun, was ist denn hier los? 739 00:35:04,700 --> 00:35:06,630 Nun denken Sie an die Name des Bedieners. 740 00:35:06,630 --> 00:35:09,980 Exklusiv-ODER, um die Name, Art der schlägt, 741 00:35:09,980 --> 00:35:13,940 die Antwort ist nur zu sein, a 1, wenn die Eingänge sind exklusiv, 742 00:35:13,940 --> 00:35:15,560 exklusiv anders. 743 00:35:15,560 --> 00:35:18,170 Also hier die Eingänge sind die gleich, so ist der Ausgang 0. 744 00:35:18,170 --> 00:35:20,700 Hier sind die Eingänge der gleich, so ist der Ausgang 0. 745 00:35:20,700 --> 00:35:25,640 Hier sind die Ausgänge sind anders, sie sind exklusiv, und so ist der Ausgang 1. 746 00:35:25,640 --> 00:35:28,190 So ist es sehr ähnlich Und, es ist sehr ähnlich, 747 00:35:28,190 --> 00:35:32,760 oder besser gesagt, es ist sehr ähnlich, OR, aber nur in einem exklusiven Art und Weise. 748 00:35:32,760 --> 00:35:36,210 Dieses ist nicht mehr a 1, weil wir zwei 1 ist, 749 00:35:36,210 --> 00:35:38,621 und nicht ausschließlich, nur einer von ihnen. 750 00:35:38,621 --> 00:35:39,120 Gut. 751 00:35:39,120 --> 00:35:40,080 Was ist mit den anderen? 752 00:35:40,080 --> 00:35:44,220 Nun die Tilde, mittlerweile ist wirklich schön und einfach, Gott sei Dank. 753 00:35:44,220 --> 00:35:46,410 Und das ist ein unärer Betreiber, was bedeutet, 754 00:35:46,410 --> 00:35:50,400 es ist nur einen Eingang angelegt wird, einen Operanden, so zu sprechen. 755 00:35:50,400 --> 00:35:51,800 Nicht an einer linken und einer rechten Seite. 756 00:35:51,800 --> 00:35:56,050 Mit anderen Worten, wenn Sie Tilde nehmen 0, wird die Antwort das Gegenteil sein. 757 00:35:56,050 --> 00:35:59,710 Und wenn Sie Tilde von 1 zu nehmen, die Antwort wird es umgekehrt sein. 758 00:35:59,710 --> 00:36:02,570 So ist die Tilde-Betreiber ein Weg der Negation ein bisschen, 759 00:36:02,570 --> 00:36:06,000 oder Spiegeln ein wenig von 0-1 oder 1-0. 760 00:36:06,000 --> 00:36:09,820 >> Und das lässt uns endlich mit nur zwei Abschlussbetreiber, 761 00:36:09,820 --> 00:36:13,840 die sogenannte Linksverschiebung und sogenannte rechte Shift-Operator. 762 00:36:13,840 --> 00:36:16,620 Werfen wir einen Blick auf, wie diese Arbeit. 763 00:36:16,620 --> 00:36:20,780 Die linke Shift-Operator, geschrieben mit zwei spitzen Klammern so, 764 00:36:20,780 --> 00:36:22,110 arbeitet wie folgt. 765 00:36:22,110 --> 00:36:27,390 Wenn meine Eingangs oder mein Operanden nach links Verschiebungs-Operator ist ganz einfach ein 1. 766 00:36:27,390 --> 00:36:33,750 Und ich sage dann den Computer an Verschiebung nach links, dass 1, sagen sieben Plätze, 767 00:36:33,750 --> 00:36:37,150 das Ergebnis ist, als ob ich nehmen, dass 1, und verschieben Sie sie 768 00:36:37,150 --> 00:36:40,160 sieben Stellen über den die links, und standardmäßig, 769 00:36:40,160 --> 00:36:42,270 werden wir davon ausgehen, dass der Raum auf der rechten 770 00:36:42,270 --> 00:36:44,080 wird sich mit Nullen aufgefüllt werden. 771 00:36:44,080 --> 00:36:50,316 Mit anderen Worten, ein Linksverschiebung 7 wird mir zu geben, dass 1, gefolgt von 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 Nullen. 773 00:36:54,060 --> 00:36:57,380 Dies in einer Weise, ermöglicht es Ihnen, nehmen Sie eine kleine Zahl wie 1, 774 00:36:57,380 --> 00:37:00,740 und deutlich machen es viel wesentlich, so viel größer, 775 00:37:00,740 --> 00:37:06,460 aber wir sind eigentlich vor sich geht, um zu sehen gescheiter Ansätze für die es 776 00:37:06,460 --> 00:37:08,080 statt, als auch, 777 00:37:08,080 --> 00:37:08,720 >> Gut. 778 00:37:08,720 --> 00:37:10,060 Das war es für drei Wochen. 779 00:37:10,060 --> 00:37:11,400 Wir werden Sie sehen, das nächste Mal. 780 00:37:11,400 --> 00:37:12,770 Dies war CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Musikwiedergabe] 783 00:37:22,243 --> 00:37:25,766 >> Sprecher 1: Er war in der Snack- Bar Essen ein Eisbecher. 784 00:37:25,766 --> 00:37:28,090 Er hatte alles über sein Gesicht. 785 00:37:28,090 --> 00:37:30,506 Er trägt, dass Schokolade wie ein Bart 786 00:37:30,506 --> 00:37:31,756 Sprecher 2: Was machst du? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Was? 789 00:37:33,500 --> 00:37:36,800 >> Sprecher 2: Haben Sie gerade Double Dip? 790 00:37:36,800 --> 00:37:38,585 Sie tauchte den doppelten Chip. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Entschuldigung. 792 00:37:39,460 --> 00:37:44,440 Sprecher 2: Sie tauchten den Chips, die Sie nahm einen Bissen, und du wieder getaucht. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 Sprecher 2: Also das ist, wie wenn man Ihren ganzen Mund direkt im dip. 795 00:37:48,440 --> 00:37:52,400 Sie das nächste Mal einen Chip zu nehmen, nur tauchen sie einmal, und beenden Sie ihn. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Weißt du was, Dan? 797 00:37:53,890 --> 00:37:58,006 Sie tauchen die Art und Weise, die Sie eintauchen möchten. 798 00:37:58,006 --> 00:38:01,900 Ich werde die Art und Weise, die ich will, um dip dip. 799 00:38:01,900 --> 00:38:03,194