1 00:00:00,000 --> 00:00:11,100 >> [Odtwarzanie muzyki] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: W porządku. 3 00:00:11,490 --> 00:00:12,170 Więc witamy z powrotem. 4 00:00:12,170 --> 00:00:15,180 Jest CS50, i jest Koniec tygodnia trzy. 5 00:00:15,180 --> 00:00:17,770 >> Więc przypomnieć w ciągu ostatnich kilku tygodni, byliśmy spędzać sporo 6 00:00:17,770 --> 00:00:20,820 Czas na C, na programowaniu, na składni. 7 00:00:20,820 --> 00:00:24,680 I to jest całkiem normalne, jeśli nadal zmaga się z zestawu Problem 2, być 8 00:00:24,680 --> 00:00:25,950 walić głową w ścianę. 9 00:00:25,950 --> 00:00:28,310 To tajemnicze komunikaty wyglądające i błędy, które 10 00:00:28,310 --> 00:00:29,220 może nie całkiem ścigać. 11 00:00:29,220 --> 00:00:32,310 Bo mieć pewność, że w tak razem kilka tygodni będziesz spojrzeć wstecz na 12 00:00:32,310 --> 00:00:35,930 rzeczy, jak Cezar, i [? V-genair,?] może nawet cracka, i 13 00:00:35,930 --> 00:00:40,050 sobie sprawę, jak daleko chcesz odejść w krótkim okresie czasu. 14 00:00:40,050 --> 00:00:43,670 Więc jeśli to jest jakieś pocieszenie, Trzymaj się teraz. 15 00:00:43,670 --> 00:00:46,610 >> Dzisiaj jednak zaczynamy przejście rzeczom wyższym poziomie. 16 00:00:46,610 --> 00:00:49,820 I zaczynamy brać za pewnik, że wiecie, jak program, lub w 17 00:00:49,820 --> 00:00:52,090 Najmniej początki że poziom komfortu. 18 00:00:52,090 --> 00:00:56,520 I zaczniemy zastanowić się, jak możemy go o projektowaniu programów więcej 19 00:00:56,520 --> 00:00:57,440 skutecznie. 20 00:00:57,440 --> 00:01:01,090 Jak możemy go o optymalizacji Efektywność naszych algorytmów i 21 00:01:01,090 --> 00:01:03,110 ogólnie rozwiązywania więcej ciekawe problemy. 22 00:01:03,110 --> 00:01:06,850 I zaczynają brać za pewnik, że jeśli chcemy, możemy zakodować się każdy 23 00:01:06,850 --> 00:01:08,350 przykłady mamy na myśli. 24 00:01:08,350 --> 00:01:11,430 Więc dzisiaj, nie dotykać klawiatury dla każdej postaci kodu. 25 00:01:11,430 --> 00:01:15,150 To będzie o wiele wyższy poziom, a ostatecznie, o rozwiązywaniu problemów. 26 00:01:15,150 --> 00:01:20,490 >> Tak więc, aby dostać się do tego punktu, chciałbym zaproponować że następujące siedem 27 00:01:20,490 --> 00:01:24,290 prostokąty reprezentują siedem drzwi, za które są całe grono 28 00:01:24,290 --> 00:01:26,340 numery, wśród których jest liczbą 50. 29 00:01:26,340 --> 00:01:30,470 Pozwól mi to na to rzutować Ekran również tutaj. 30 00:01:30,470 --> 00:01:36,770 I proponuje, że potrzebujemy ochotnika pomóc znaleźć mi numer z przodu 31 00:01:36,770 --> 00:01:38,140 internet, żeby zobaczyć. 32 00:01:38,140 --> 00:01:40,755 Chodź na górę, w kolorze różowym. 33 00:01:40,755 --> 00:01:43,050 Dobrze. 34 00:01:43,050 --> 00:01:43,930 Jak masz na imię? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [niesłyszalne] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Przepraszam? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Dobrze, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Miło Pana poznać. 41 00:01:47,630 --> 00:01:48,370 Chodź na górę. 42 00:01:48,370 --> 00:01:52,430 Więc to o siedem drzwi, a co Chciałbym, aby zrobić dla nas, 43 00:01:52,430 --> 00:01:56,560 wobec wszystkich swoich kolegów, jest nas znaleźć numer, 50. 44 00:01:56,560 --> 00:02:00,860 Aby znaleźć numer, można zajrzeć za Każda z tych drzwi stukając 45 00:02:00,860 --> 00:02:03,030 na jednym z drzwi, i to ujawni swój numer. 46 00:02:03,030 --> 00:02:06,080 I zobaczymy, jak szybko Można nas znaleźć numer, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Niezła robota. 54 00:02:17,350 --> 00:02:18,040 Dobrze. 55 00:02:18,040 --> 00:02:19,906 Brawa dla Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [APPLAUSE] 57 00:02:21,530 --> 00:02:22,320 >> Dobrze. 58 00:02:22,320 --> 00:02:25,254 Więc jaka była twoja strategia znalezieniem numeru 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, pomyślałem, że może, jeśli - 60 00:02:27,222 --> 00:02:27,714 [Niesłyszalne] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Daj jedną sekundę. 63 00:02:29,630 --> 00:02:32,420 Więc była twoja strategia znalezieniem numeru 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Więc po prostu zaczynają się zaczynają dostrzegać to, co pierwszy numer 65 00:02:34,760 --> 00:02:38,590 był, a potem pomyślałem, być może, jeśli są one klasyfikowane, po prostu zachować 66 00:02:38,590 --> 00:02:39,970 dotykając się wyżej? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 I wydaje się, że znaleziono że być przypadek. 69 00:02:42,910 --> 00:02:45,670 Chociaż, niech odwinąć warstwy tylko trochę, a ty chcesz iść 70 00:02:45,670 --> 00:02:47,640 dalej i ujawnić inne drzwi Mogłeś wybrać? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, kochanie. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Więc po prostu miał szczęście. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Więc masz szczęście. 76 00:02:55,270 --> 00:02:55,710 Dobrze. 77 00:02:55,710 --> 00:02:56,795 Więc nie jest źle. 78 00:02:56,795 --> 00:02:58,750 Ale to ciekawe insight, prawda? 79 00:02:58,750 --> 00:03:01,870 Jeśli założyć, i nie dostać, rzeczywiście, trochę szczęścia tam. 80 00:03:01,870 --> 00:03:05,350 Ale jeśli założyć, że numery były posortowane, można być bardziej precyzyjne 81 00:03:05,350 --> 00:03:08,750 , w jaki sposób, że pod wpływem Twoje zachowanie? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Więc jeśli były sortowane, I że być może od najmniejszych do największych. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: A jeśli ten zakończył się naprawdę duże, to największego do najmniejszego. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Więc największego do najmniejszego, lub od najmniejszych do największych. 87 00:03:18,170 --> 00:03:21,990 Ale pozwól mi zaproponować, załóżmy, że miał zdobyć pecha, i załóżmy, że 88 00:03:21,990 --> 00:03:26,840 nie były w rzeczywistości, sortowane, ile te drzwi można musieli peek 89 00:03:26,840 --> 00:03:28,590 tyle w tym najgorszym przypadku? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Wszystkie. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Wszystkie. 92 00:03:30,420 --> 00:03:31,740 Warto więc generalizować, że jak n. 93 00:03:31,740 --> 00:03:34,790 Nie dzieje się 7, ale niech więcej ogólnie mówi, że istnieje n drzwi na 94 00:03:34,790 --> 00:03:35,650 Ekran tutaj. 95 00:03:35,650 --> 00:03:40,110 Więc w najgorszym przypadku, to masz zajrzeć za 7 drzwi lub drzwi n. 96 00:03:40,110 --> 00:03:44,140 A więc to jest naprawdę, to trochę Powodzenia dzisiaj, ale to naprawdę liniowy 97 00:03:44,140 --> 00:03:46,440 Algorytm rodzaju, nawet jeśli niby omijając okolice. 98 00:03:46,440 --> 00:03:47,080 Czy to jest sprawiedliwe? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Tak. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Cóż, pozwól mi sprawdzić, czy zmiany strategii, jeśli przenieść nas do 101 00:03:50,000 --> 00:03:52,190 nasz drugi przykład tutaj z 7 różnych drzwi. 102 00:03:52,190 --> 00:03:55,240 Takie same numery, ale to razem są one klasyfikowane. 103 00:03:55,240 --> 00:03:58,350 Jaka jest twoja strategia tu będzie, próbuje zgasić umysłu, co 104 00:03:58,350 --> 00:03:59,310 inne numery były - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - wcześniej? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Zacznijmy z pierwszym. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: W porządku. 109 00:04:03,540 --> 00:04:05,190 Start z pierwszego. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Teraz gdy idziesz do pracy, i dlaczego? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 jest naprawdę mała. 113 00:04:10,040 --> 00:04:12,500 Więc jeśli są sort może najmniejsza do wielkości, powinna ona 114 00:04:12,500 --> 00:04:13,290 się dwukrotnie, i -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Zobaczmy, co myślisz? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Spróbuj ostatni. 118 00:04:19,050 --> 00:04:19,500 Miło. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Bardzo ładnie wykonane. 120 00:04:20,880 --> 00:04:21,860 Dobrze. 121 00:04:21,860 --> 00:04:23,010 >> [APPLAUSE] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Więc faktycznie to robi strasznie ponieważ jesteś 124 00:04:26,790 --> 00:04:27,700 robi to bardzo dobrze. 125 00:04:27,700 --> 00:04:31,150 Który pozostawia nas w stanie dokonać pewnych punktów. 126 00:04:31,150 --> 00:04:32,565 Więc spróbujmy przywrócić tutaj. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Bardzo dobrze zrobione, jednak. 129 00:04:35,980 --> 00:04:39,060 Tak więc rozpoczął się na początku, obejrzałeś że to 4, a następnie 130 00:04:39,060 --> 00:04:40,240 przeniósł się do końca. 131 00:04:40,240 --> 00:04:42,320 Załóżmy jednak, że nie miał szczęście tam, i załóżmy 50 132 00:04:42,320 --> 00:04:42,890 był gdzieś indziej. 133 00:04:42,890 --> 00:04:46,190 Co twój trzeci etap był? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Wróć do początku. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Wróć na początku. 136 00:04:48,320 --> 00:04:51,320 OK, więc to już dotknął te drzwi, które było 8. 137 00:04:51,320 --> 00:04:51,660 Dobrze. 138 00:04:51,660 --> 00:04:52,650 Więc to nie jest 50. 139 00:04:52,650 --> 00:04:55,380 Gdzie byś spojrzał dalej? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: jeśli nie wiedzą, że posortowane. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Correct. 142 00:04:57,005 --> 00:04:58,490 Cóż, jeśli nie wiesz zostały one posortowane - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Och, wiedziałam, tak. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - Ale nie wiedzieć, gdzie 50 to już? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Just keep going. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: W porządku. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Trzymaj się. 149 00:05:03,800 --> 00:05:05,270 OK, że mogę pracować. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Teraz, jeśli jesteś po prostu zamierza poddawać się, jak się 152 00:05:07,210 --> 00:05:09,680 Algorytm przekazanych kopii do. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: liniowy -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: To niby liniowy. 155 00:05:11,820 --> 00:05:13,480 Ale pozwól mi zaproponować, niech mnie umieścić na miejscu. 156 00:05:13,480 --> 00:05:14,900 Pozwól mi odświeżyć stronę. 157 00:05:14,900 --> 00:05:17,120 sam numer, sam układ, same drzwi. 158 00:05:17,120 --> 00:05:21,350 Ale wracam do tego pierwszego dnia w class, gdy wyrwał książkę telefoniczną w 159 00:05:21,350 --> 00:05:25,480 pół, rodzaj, i to, co było nasza strategia nie? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Start w środku. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Tak rozpoczyna się na środku. 163 00:05:27,610 --> 00:05:28,790 Więc śmiało i symulacji, które. 164 00:05:28,790 --> 00:05:30,720 Kliknij na środku przez ujawniając te drzwi. 165 00:05:30,720 --> 00:05:31,660 Tak więc liczba 16. 166 00:05:31,660 --> 00:05:35,290 Więc co będzie silny facet zrobić, który wyrwał książkę telefoniczną na pół, 167 00:05:35,290 --> 00:05:38,450 aby dostać się do następnego przypuszczenie? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Idź w tej połowie. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: A dlaczego w prawo? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Jeśli były jakby najmniejsza do wielkości, to 50 powinno być 171 00:05:43,900 --> 00:05:44,720 w tym celu. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Dobry. 173 00:05:44,920 --> 00:05:45,390 Całkowicie uzasadnione. 174 00:05:45,390 --> 00:05:48,380 Tak jak w książce telefonicznej, można przejść do prawo w przeciwieństwie do lewej, ale tutaj 175 00:05:48,380 --> 00:05:49,500 jest kluczem wynos. 176 00:05:49,500 --> 00:05:53,930 Teraz można wyrzucić, lub oderwać, połowa z tego problemu, nie pozostawiając cię 177 00:05:53,930 --> 00:05:55,970 z 7 drzwi, ale tak naprawdę tylko z 3. 178 00:05:55,970 --> 00:05:57,870 Jakie jest mniej więcej połowa Wielkość tego problemu. 179 00:05:57,870 --> 00:05:58,350 Dobrze. 180 00:05:58,350 --> 00:06:01,890 Więc teraz, co chcesz, zrobić po powrocie do porządku? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: So 16 jest wciąż bardzo mały, w stosunku do 50, więc może spróbuję, 182 00:06:05,870 --> 00:06:06,700 jak, to jedno. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: W porządku. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Dobra, co teraz jest twoim instynkt mówi ci? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: mogę wyrzucić to i po prostu - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Dobra, możesz wyrzucić lewa połowa nie. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - wybrać ten jeden. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: I dobrze. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Tak. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Więc choć trudno zobaczyć być może, gdy jest tylko 193 00:06:17,820 --> 00:06:21,320 7 drzwi, myśleć, teraz, Konsystencja 194 00:06:21,320 --> 00:06:22,620 algorytm po prostu stosować. 195 00:06:22,620 --> 00:06:24,510 W poprzednim przypadku, zrobiłeś miał szczęście, co było świetne. 196 00:06:24,510 --> 00:06:26,540 Ale nie używać metody heurystyczne, Chciałbym powiedzieć. 197 00:06:26,540 --> 00:06:29,150 Kiedyś rodzaju instynktów i wiedząc, że sortowane, jeśli jest to dość 198 00:06:29,150 --> 00:06:31,600 mały na początku, oczywiście, mamy iść bardziej w prawo. 199 00:06:31,600 --> 00:06:34,990 Ale w pewnym sensie, że masz szczęście, bo może to był numer 100, 200 00:06:34,990 --> 00:06:36,220 a może 50 był w środku. 201 00:06:36,220 --> 00:06:37,910 Być może 50 było nawet tutaj. 202 00:06:37,910 --> 00:06:40,960 >> Ale to, co zrobiłeś trochę inaczej tym razem było, to nie to samo 203 00:06:40,960 --> 00:06:42,150 znowu i znowu. 204 00:06:42,150 --> 00:06:45,310 I jestem zdania, że ​​to, co właśnie nie, chociaż zależy od telefonu 205 00:06:45,310 --> 00:06:48,100 Książka przykładem, jest czymś o wiele więcej algorytmiczne, i wiele 206 00:06:48,100 --> 00:06:49,930 mniej specjalny obudowane. 207 00:06:49,930 --> 00:06:51,620 Znacznie mniej instynktowne. 208 00:06:51,620 --> 00:06:57,160 Tak więc na koniec dnia, jak by opisać efektywność 209 00:06:57,160 --> 00:07:00,530 Pierwszy algorytm, gdzie poszedł od lewej do prawej, w porównaniu 210 00:07:00,530 --> 00:07:03,430 Drugi algorytm tutaj? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: To powinien, jak, być może połowę czasu, lub nawet więcej, tak. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, może nawet więcej. 213 00:07:07,320 --> 00:07:10,150 Miejmy wcisnąć trochę mocniej na tym. 214 00:07:10,150 --> 00:07:13,030 Co tak naprawdę, jeśli nadal tego Logika, na pewno o połowę 215 00:07:13,030 --> 00:07:15,830 czas pracy z tego drugiego algorytmu by wyrzucić połowę 216 00:07:15,830 --> 00:07:18,470 numery, ale co możemy zrobić na następny iteracji, kiedy Jennifer ujawnił 217 00:07:18,470 --> 00:07:20,615 Drugi numer? 218 00:07:20,615 --> 00:07:22,830 >> Mamy połowę liczby drzwi ponownie. 219 00:07:22,830 --> 00:07:25,270 I co wtedy robiliśmy po tym, gdy było więcej drzwi do zabawy? 220 00:07:25,270 --> 00:07:27,520 Chcemy zmniejszyć o połowę ich, i znowu, i znowu, i znowu. 221 00:07:27,520 --> 00:07:30,420 A było to tak, jak was wszystkich stojąc w pierwszym tygodniu 222 00:07:30,420 --> 00:07:33,000 class, połowa z was siedzi, pół z was siedzi, połowę Ciebie 223 00:07:33,000 --> 00:07:35,440 siedzi, aż jeden samotny dusza stała. 224 00:07:35,440 --> 00:07:39,050 A my powiedzieliśmy, że czas pracy , że pewne kroki zajęło to 225 00:07:39,050 --> 00:07:40,430 rzędu co? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [niesłyszalne] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Tak Podstawa log 2 n, czy tylko po prostu, zaloguj n. 228 00:07:43,970 --> 00:07:45,060 Więc coś logarytmiczna. 229 00:07:45,060 --> 00:07:48,380 A wykres nie był linią prostą że po prostu coraz gorzej, było 230 00:07:48,380 --> 00:07:52,490 to ciekawe, że nie łuk się tak źle w czasie. 231 00:07:52,490 --> 00:07:53,910 Warto więc trzymać się tej idei. 232 00:07:53,910 --> 00:07:54,690 Chcę podziękować Jennifer. 233 00:07:54,690 --> 00:07:56,150 Dziękuję bardzo za przybycie na górę. 234 00:07:56,150 --> 00:07:57,400 I jeden sec. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Brak lampki biurkowe dzisiaj, ale my mam CS50 stresu piłki. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Dobra, tutaj. 239 00:08:04,410 --> 00:08:06,545 Dziękujemy za ponoszenia stres tutaj. 240 00:08:06,545 --> 00:08:07,350 Dobrze. 241 00:08:07,350 --> 00:08:10,620 Zobaczmy więc, jeśli nie możemy teraz sformalizowania tego trochę więcej. 242 00:08:10,620 --> 00:08:14,820 Więc jeszcze raz, co właśnie zrobił, było w zasadzie to samo, co my 243 00:08:14,820 --> 00:08:16,660 W tym pierwszym tygodniu. 244 00:08:16,660 --> 00:08:23,780 Ale zamiast końcu z zaledwie liniowy Algorytm, które przedstawiono 245 00:08:23,780 --> 00:08:27,210 wcześniej w tej linii prostej zgodnie z którą, jeżeli stawiamy jeden drzwi 246 00:08:27,210 --> 00:08:29,610 ekran, a następnie Jennifer by musiało wyglądać, potencjalnie, 247 00:08:29,610 --> 00:08:30,600 za jedne drzwi. 248 00:08:30,600 --> 00:08:33,490 Jeśli stawiamy dwa kolejne drzwi, ona może mieć zajrzeć za dwa kolejne drzwi. 249 00:08:33,490 --> 00:08:35,990 >> I tak, nie było to liniowy zależność między wielkością 250 00:08:35,990 --> 00:08:39,059 Problem na, powiedzmy, osi x, a Czas potrzebny na 251 00:08:39,059 --> 00:08:40,440 rozwiązania na y. 252 00:08:40,440 --> 00:08:43,330 Ale obraz nawiązujący do mnie wcześniej była to zielona linia. 253 00:08:43,330 --> 00:08:45,970 Zielona celowo, ponieważ to po prostu czułem się lepiej. 254 00:08:45,970 --> 00:08:49,790 W teorii, algorytm, kiedy to zrobiliśmy z książki telefonicznej, kiedy to zrobiliśmy 255 00:08:49,790 --> 00:08:52,420 z wy licząc siebie, a w drugim przypadku, gdy Jennifer tylko 256 00:08:52,420 --> 00:08:55,250 zrobił to tutaj, to był rodzaj fundamentalnie lepiej. 257 00:08:55,250 --> 00:08:57,180 Bo to nie był tylko dwa razy szybciej. 258 00:08:57,180 --> 00:08:58,870 To nie było nawet cztery razy szybciej. 259 00:08:58,870 --> 00:09:03,290 To było całkowicie zależne od tego, co Wielkość wejściowym, jak na ile 260 00:09:03,290 --> 00:09:05,220 kroki ostatecznie wziął. 261 00:09:05,220 --> 00:09:08,040 >> A więc ten prosty pomysł, że wszyscy wzięliśmy za pewnik, z książki telefonicznej, 262 00:09:08,040 --> 00:09:10,200 Podobnie mogą być stosowane do czegoś takiego. 263 00:09:10,200 --> 00:09:12,380 I to może być bardziej niedbale znany jako,, jak może 264 00:09:12,380 --> 00:09:13,940 wyobrazić, dziel i rządź. 265 00:09:13,940 --> 00:09:16,390 Nie inaczej niż my, oczywiście, z książki telefonicznej. 266 00:09:16,390 --> 00:09:18,300 >> Ale pseudokod, przypomnijmy, to było. 267 00:09:18,300 --> 00:09:21,800 Tak więc nie będzie to zrobić jeszcze raz, ale pamiętam że pierwszy tydzień, każdy z nas stał się 268 00:09:21,800 --> 00:09:25,140 i połowa ciebie usiadł, połowa Ci usiadł, połowa Ciebie usiadł. 269 00:09:25,140 --> 00:09:29,280 To algorytm został wprowadzony w trochę sposób oszustwa, w tym, to 270 00:09:29,280 --> 00:09:32,870 był nie tylko jednym z mnie liczyć, Zasadniczo bardziej efektywnie. 271 00:09:32,870 --> 00:09:35,830 W tym przypadku, byłem wykorzystanie surowców wtórnych. 272 00:09:35,830 --> 00:09:39,470 Rodzaj, wielu procesorów, wiele mózgi, wielu inteligentnych ludzi w 273 00:09:39,470 --> 00:09:42,740 room pomagali mi dostać się z czegoś liniowy do czegoś 274 00:09:42,740 --> 00:09:45,190 logarytmiczna, z czegoś czerwony na coś zielonego. 275 00:09:45,190 --> 00:09:48,650 >> Ale w tym przypadku, Jennifer sam może fundamentalnie poprawić na 276 00:09:48,650 --> 00:09:52,370 Wykonanie jej pierwszego algorytmu przez, ponownie, po prostu myśleć trochę trudniej. 277 00:09:52,370 --> 00:09:56,650 A teraz, gdy przychodzi czas na wdrożenie te rzeczy, dowiedzieć się, 278 00:09:56,650 --> 00:10:00,670 co linie kodu można napisać takie że można je powtórzyć jeszcze raz, i 279 00:10:00,670 --> 00:10:03,350 znowu, i znowu, jakby w pętli mody. 280 00:10:03,350 --> 00:10:06,370 Ponieważ nie będziesz mieć luksus, jak Jennifer nie w pierwszym, do 281 00:10:06,370 --> 00:10:10,460 po prostu całą masę FI i powiedzieć, Hm, jeżeli pierwsza liczba jest 4, 282 00:10:10,460 --> 00:10:11,800 pozwól mi przejść całą drogę do końca. 283 00:10:11,800 --> 00:10:14,180 Ooh, jeżeli ta liczba jest zbyt duża, pozwól mi przejść arbitralnie powrotem 284 00:10:14,180 --> 00:10:15,220 do drugiego elementu. 285 00:10:15,220 --> 00:10:18,210 Przekonasz się, że to będzie dużo trudniej sformalizować to, co my, ludzie, 286 00:10:18,210 --> 00:10:21,270 za oczywiste, jak bardzo rozsądne heurystyka, ale komputer jest tylko 287 00:10:21,270 --> 00:10:23,260 zamiar zrobić to, co możesz powiedzieć to zrobić. 288 00:10:23,260 --> 00:10:25,280 >> Teraz to ma bardzo ciekawe implikacje. 289 00:10:25,280 --> 00:10:29,950 Ten wykres jest rodzajem myśli do rodzaju przytłaczają wizualnie, ale zauważ, gdzie 290 00:10:29,950 --> 00:10:32,230 jest prosta w tym wykresie? 291 00:10:32,230 --> 00:10:35,330 Gdzie jest wykres liniowy które nazywamy n? 292 00:10:35,330 --> 00:10:37,580 Cóż, jakby w kierunku dna z tego obrazu, prawda? 293 00:10:37,580 --> 00:10:40,500 Więc zrobiliśmy to mamy coś w rodzaju pomniejszeniu do osi x i 294 00:10:40,500 --> 00:10:44,780 oś y postarać się poczucie tego, co inne rodzaje krzywych wyglądać. 295 00:10:44,780 --> 00:10:47,760 >> A specyfika matematyczne wyrażenia dzisiaj tak nie będzie miało znaczenia 296 00:10:47,760 --> 00:10:52,440 dużo, ale zauważ, że jest wiele algorytmy, które są znacznie gorsze niż 297 00:10:52,440 --> 00:10:53,470 coś, co jest liniowa. 298 00:10:53,470 --> 00:10:55,410 Rzeczywiście, n do sześcianu wygląda bardzo źle. 299 00:10:55,410 --> 00:10:58,400 2 do n wygląda bardzo źle. n do kwadratu wygląda bardzo źle. 300 00:10:58,400 --> 00:11:01,630 I zobaczymy, co niektórzy z tych może być w rzeczywistości dziś. 301 00:11:01,630 --> 00:11:05,430 A log n nie czuje się tak źle, ale lepiej niż n jest log podstawa 2 n. 302 00:11:05,430 --> 00:11:08,080 Ale wiesz, to byłoby nawet bardziej zdumiewające, jeśli Jennifer, czy my, 303 00:11:08,080 --> 00:11:12,910 że pierwszy tydzień, wymyślił coś, co jest log log n. 304 00:11:12,910 --> 00:11:15,880 >> Tak więc, innymi słowy, nie ma tego cała Zakres możliwych rozwiązań 305 00:11:15,880 --> 00:11:18,570 problemy, ale nawet tutaj ogłoszenie to, co się wydarzy. 306 00:11:18,570 --> 00:11:22,910 Kiedy pomniejszyć, które z tych krzywych Okaże się absolutnym 307 00:11:22,910 --> 00:11:26,630 najgorsze te na ekranie teraz? 308 00:11:26,630 --> 00:11:28,680 Więc n kostkę wygląda całkiem źle w tej chwili. 309 00:11:28,680 --> 00:11:32,470 Jeśli jednak pomniejszyć i zobacz więcej x i y-axis, kto będzie 310 00:11:32,470 --> 00:11:34,550 dominują ostatecznie? 311 00:11:34,550 --> 00:11:37,120 Więc to rzeczywiście okazuje się, że 2 do n, i można to rozwiązać tylko poprzez 312 00:11:37,120 --> 00:11:39,990 podłączając niektóre coraz większa numery, a zobaczysz, że od 2 do 313 00:11:39,990 --> 00:11:42,070 n, rzeczywiście, ma większe znacznie szybciej. 314 00:11:42,070 --> 00:11:45,530 Jeśli naprawdę pomniejszyć, a 2 do Algorytm n absolutnie do bani. 315 00:11:45,530 --> 00:11:48,170 Mam na myśli to zajmie trochę czasu na 316 00:11:48,170 --> 00:11:49,460 komputer do rezygnacji przez. 317 00:11:49,460 --> 00:11:52,500 >> Ale zobaczymy z czasem, zwłaszcza z przyszłych zbiorów problem, a nawet 318 00:11:52,500 --> 00:11:55,600 Ostateczne projekty, to dane zestaw ma duży, dobrze? 319 00:11:55,600 --> 00:11:58,300 Nawet w pierwszej wersji Facebook, jak liczba przyjaciół, a 320 00:11:58,300 --> 00:12:01,840 Liczba zarejestrowanych użytkowników ma duże, można sortować z telefonem go i 321 00:12:01,840 --> 00:12:05,530 zaimplementować coś z liniowym wyszukiwania lub bardzo proste sortowanie 322 00:12:05,530 --> 00:12:07,030 algorytm, jak zobaczymy dzisiaj. 323 00:12:07,030 --> 00:12:09,280 Trzeba zacząć myśleć trudniejsze i trudniej o tych problemach. 324 00:12:09,280 --> 00:12:12,070 Oraz rodzaje problemów takich miejscach jak Facebook i Google i Microsoft, 325 00:12:12,070 --> 00:12:16,350 a inni pracują na to dokładnie te rodzaj wielkiego sortowanie danych pytań 326 00:12:16,350 --> 00:12:18,530 coraz te dni. 327 00:12:18,530 --> 00:12:18,900 >> Dobrze. 328 00:12:18,900 --> 00:12:23,800 Więc powodzenia Jennifer w tym drugim Algorytm, szczerze mówiąc, ona zadziwiająco 329 00:12:23,800 --> 00:12:26,110 dobrze za pierwszym razem, ale niech piszę to jak szczęście, tak abyśmy 330 00:12:26,110 --> 00:12:27,000 może ten punkt. 331 00:12:27,000 --> 00:12:30,970 W drugim przypadku, ona wykorzystała algorytm, który powtarza się ponownie i 332 00:12:30,970 --> 00:12:34,670 ponownie, ale brała za pewnik pewne założenie, że prawo 333 00:12:34,670 --> 00:12:39,370 ją, ale ona wykorzystać jakiś szczegół Drugi raz, że nie mają 334 00:12:39,370 --> 00:12:39,840 pierwszy raz. 335 00:12:39,840 --> 00:12:41,800 Co było, co? 336 00:12:41,800 --> 00:12:43,050 >> Że lista została posortowana. 337 00:12:43,050 --> 00:12:46,350 Tak więc, jak tylko lista została posortowane, że twierdzą, że Jennifer była w stanie zrobić 338 00:12:46,350 --> 00:12:47,480 zasadniczo lepiej. 339 00:12:47,480 --> 00:12:51,450 7 drzwi, tak, to nie jest ciekawe, Ale załóżmy, że to my jesteśmy 7000000 drzwi. 340 00:12:51,450 --> 00:12:54,080 Zaloguj n jest na pewno będzie wykonywać wiele, wiele 341 00:12:54,080 --> 00:12:55,610 szybciej w dłuższej perspektywie. 342 00:12:55,610 --> 00:12:58,880 Ale musiała mieć Drzwi posortowane dla niej. 343 00:12:58,880 --> 00:13:02,320 Teraz, ja pozwoliłem sobie robić z góry na ekranie komputera 344 00:13:02,320 --> 00:13:05,160 tutaj, ale przypuszczam, że Jennifer miał to zrobić sama? 345 00:13:05,160 --> 00:13:10,120 Załóżmy, że drzwi te przedstawione dane w bazie danych, lub 346 00:13:10,120 --> 00:13:14,260 przyjaciele zarejestrowani na Facebooku, lub żadnych stron internetowych w internecie, że 347 00:13:14,260 --> 00:13:16,880 różne strony internetowe mogą potrzebować do indeksu lub przeszukiwać. 348 00:13:16,880 --> 00:13:20,940 >> Załóżmy, że po prostu miał surowych danych ustawione i to pozostało do Ciebie, lub do 349 00:13:20,940 --> 00:13:23,010 Jennifer to zrobić sortowanie? 350 00:13:23,010 --> 00:13:26,950 To raczej wymaga od nas odpowiedzi pytanie, dobrze, ile czasu 351 00:13:26,950 --> 00:13:31,080 wziąłby Jennifer, a nawet mnie, posortować te liczby z góry tak 352 00:13:31,080 --> 00:13:32,680 że mogła skorzystać z tego? 353 00:13:32,680 --> 00:13:32,880 Prawda? 354 00:13:32,880 --> 00:13:36,620 Ponieważ implikacja, oczywiście, jeśli zajmuje mi sporo czasu, aby uporządkować 355 00:13:36,620 --> 00:13:40,800 numery, kto do cholery obchodzi, że cię Można znaleźć wiele jak 50 tak szybko, 356 00:13:40,800 --> 00:13:44,850 jak w przypadku Jennifer, jeśli więcej niż przytłoczony ilość całkowitego czasu 357 00:13:44,850 --> 00:13:46,920 zajęło sortując rzeczy z góry? 358 00:13:46,920 --> 00:13:49,320 >> Zobaczmy więc, jeśli nie możemy malować obraz tutaj. 359 00:13:49,320 --> 00:13:51,370 Mam całą masę więcej stresu kulki, czy to pomaga 360 00:13:51,370 --> 00:13:52,270 przełamać lody tutaj. 361 00:13:52,270 --> 00:13:55,690 A jeśli nie masz nic przeciwko, że potrzebują siedem wolontariusza - 362 00:13:55,690 --> 00:13:57,060 on, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Tak więc nie trzeba wydawać na lampy biurkowe, wydaje się. 365 00:13:59,250 --> 00:13:59,690 Dobrze. 366 00:13:59,690 --> 00:14:01,530 Tak jak o tobie dwa z przodu. 367 00:14:01,530 --> 00:14:04,160 Jak o tobie dwóch facetów w plecy. 368 00:14:04,160 --> 00:14:04,870 Więc to jest cztery. 369 00:14:04,870 --> 00:14:09,890 Jak Pan przed pięć, sześć i siedem. 370 00:14:09,890 --> 00:14:10,320 Właśnie tam. 371 00:14:10,320 --> 00:14:13,260 Twoja przyjaciółka, wskazując cię, tak dostaniesz nagrodę. 372 00:14:13,260 --> 00:14:13,700 >> Dobrze. 373 00:14:13,700 --> 00:14:14,410 Chodź na górę. 374 00:14:14,410 --> 00:14:17,120 A dlaczego nie mamy Cię chłopaki chodź tutaj. 375 00:14:17,120 --> 00:14:18,960 Mam zamiar dać każdą liczbę. 376 00:14:18,960 --> 00:14:22,150 I iść dalej i zorganizować siebie identyczny do tego, co 377 00:14:22,150 --> 00:14:25,180 przedstawione na ekranie. 378 00:14:25,180 --> 00:14:26,530 >> [Wstawienie GŁOSÓW] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Dobrze. 382 00:14:32,180 --> 00:14:32,750 Cóż, jedziemy. 383 00:14:32,750 --> 00:14:34,180 Numer pięć. 384 00:14:34,180 --> 00:14:35,136 Numer sześć. 385 00:14:35,136 --> 00:14:37,770 Jeden, dwa, trzy, cztery, pięć, sześć, siedem. 386 00:14:37,770 --> 00:14:39,410 Oh, to jest niewygodne. 387 00:14:39,410 --> 00:14:41,210 >> Głośnik 2: Ja po prostu -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Good deal. 389 00:14:41,900 --> 00:14:43,130 Dobrze. 390 00:14:43,130 --> 00:14:44,611 Dziękujemy za udział. 391 00:14:44,611 --> 00:14:47,200 >> [APPLAUSE] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Dobrze. 394 00:14:48,860 --> 00:14:51,970 Tak więc mamy cztery, dwa, sześć, jeden, trzy, siedem, pięć. 395 00:14:51,970 --> 00:14:56,010 Doskonalić więc mamy siedem wolontariuszy tu, którzy są równe szerokości do 396 00:14:56,010 --> 00:14:57,430 array, że gramy z wcześniej. 397 00:14:57,430 --> 00:14:59,470 I wybrałem siedem powodów które będą po prostu 398 00:14:59,470 --> 00:15:00,840 wygodne w trochę. 399 00:15:00,840 --> 00:15:04,400 I mam zamiar zaproponować pierwsze, że rozwiążemy tych siedmiu wolontariuszy. 400 00:15:04,400 --> 00:15:06,786 Jeśli chcesz, po pierwsze, przywitać chociaż. 401 00:15:06,786 --> 00:15:08,970 Od tego będzie niewygodne kilka minut. 402 00:15:08,970 --> 00:15:10,370 Przedstawcie się. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Cześć, jestem Grace. 404 00:15:10,980 --> 00:15:14,190 Jestem studentem drugiego roku w Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Hi. 406 00:15:14,620 --> 00:15:15,620 Jestem Branson. 407 00:15:15,620 --> 00:15:16,920 Jestem studentem pierwszego roku w Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hi. 410 00:15:20,230 --> 00:15:21,040 Jestem Gabe. 411 00:15:21,040 --> 00:15:22,300 Jestem młodszy w Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Jestem Neil. 414 00:15:25,980 --> 00:15:29,090 Jestem studentem pierwszego roku w Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Jestem Jason. 416 00:15:29,550 --> 00:15:32,816 Jestem studentem pierwszego roku w Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Jestem Mike. 418 00:15:33,700 --> 00:15:37,360 Jestem studentem pierwszego roku w Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Jestem Jess. 420 00:15:37,990 --> 00:15:40,313 Jestem studentem drugiego roku w Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excellent. 422 00:15:41,300 --> 00:15:41,850 Dobrze. 423 00:15:41,850 --> 00:15:44,190 Dziękuję wszystkim naszym wolontariuszy tutaj do tej pory. 424 00:15:44,190 --> 00:15:47,110 I wyzwanie pod ręką teraz dzieje się do rodzaju tych facetów, ale wtedy 425 00:15:47,110 --> 00:15:50,250 będziemy musieli trochę pomyśleć trudno o tym, jak skutecznie faktycznie 426 00:15:50,250 --> 00:15:51,110 sortowane ich. 427 00:15:51,110 --> 00:15:52,580 Warto więc najpierw spróbować. 428 00:15:52,580 --> 00:15:55,970 Chłopaki widać nawzajem numery po prostu przez umieszczenie wokół narożników. 429 00:15:55,970 --> 00:15:59,380 Śmiało i trwa kilka sekund, a sort sami z najmniejszych na 430 00:15:59,380 --> 00:16:01,240 od lewej do wielkości po prawej stronie. 431 00:16:01,240 --> 00:16:02,490 Idź. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Dobra. 435 00:16:08,030 --> 00:16:09,370 To było naprawdę cholernie szybko. 436 00:16:09,370 --> 00:16:14,040 Teraz ktoś tutaj, to, co było algorytm że ci faceci stosowane? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Najmniej do największych. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Najmniej do największych jest naprawdę coś w rodzaju obiektywne, ale nie jestem pewien, że to 440 00:16:18,070 --> 00:16:18,890 naprawdę algorytm. 441 00:16:18,890 --> 00:16:21,810 Najmniej do największych nie mówi mi krok po kroku, co robić. 442 00:16:21,810 --> 00:16:22,833 Tak? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [niesłyszalne] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Więc jeśli widzisz osobę mniejszy niż numer, a następnie przejść do 447 00:16:28,920 --> 00:16:29,680 prawo z nich. 448 00:16:29,680 --> 00:16:32,800 Więc to jest teraz coraz bardziej wyraziste, bardziej jak algorytmu, ponieważ 449 00:16:32,800 --> 00:16:35,410 można powiedzieć, czy to, to. 450 00:16:35,410 --> 00:16:37,050 Więc mamy jakieś Konstrukt warunkowe. 451 00:16:37,050 --> 00:16:39,700 I te chłopaki wydawało się zrobić kilka razy, ponieważ niektórzy z was trochę przeniesione 452 00:16:39,700 --> 00:16:40,420 w pewnej odległości. 453 00:16:40,420 --> 00:16:43,410 Więc nie było prawdopodobnie jakiś rodzaj zapętlenie dzieje się w ich umysłach. 454 00:16:43,410 --> 00:16:44,610 >> Spróbujmy jednak sformalizowanie tego. 455 00:16:44,610 --> 00:16:47,540 Jeśli wam się przywrócić z powrotem w tym układzie. 456 00:16:47,540 --> 00:16:50,650 Zobaczmy, czy nie możemy sformalizować ten bit, a następnie zadać sobie pytanie, po prostu 457 00:16:50,650 --> 00:16:51,580 jak skuteczne to jest? 458 00:16:51,580 --> 00:16:54,220 Oczywiście, gdy robimy to wolniej, to się czuje jako dobra 459 00:16:54,220 --> 00:16:57,210 algorytm, ale zobaczymy, czy możemy położyć rękę na konkretnych etapach. 460 00:16:57,210 --> 00:16:58,670 >> Więc wy dwaj faceci są cztery i dwa. 461 00:16:58,670 --> 00:17:01,020 Albo poprawne lub niepoprawne zamówienie? 462 00:17:01,020 --> 00:17:01,900 Oczywiście błędne. 463 00:17:01,900 --> 00:17:02,710 Więc zamienione. 464 00:17:02,710 --> 00:17:05,170 Teraz mam zamiar przejść na bok tutaj i powiedzieć, 05:56. 465 00:17:05,170 --> 00:17:06,240 Czy poprawne lub niepoprawne? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Correct. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Correct. 468 00:17:07,180 --> 00:17:08,300 Sześć i jeden? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Zamień. 471 00:17:09,630 --> 00:17:10,490 Więc to jest dwa swapy. 472 00:17:10,490 --> 00:17:11,710 Sześć i trzy? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Zamień. 475 00:17:13,000 --> 00:17:13,930 Sześć i siedem? 476 00:17:13,930 --> 00:17:14,630 Wygląda dobrze. 477 00:17:14,630 --> 00:17:15,396 Siedem i pięć? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [niesłyszalne] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, zamienić. 480 00:17:17,089 --> 00:17:19,770 I sortowane. 481 00:17:19,770 --> 00:17:19,980 Dobrze. 482 00:17:19,980 --> 00:17:21,440 Tak oczywiście nie jest, prawda? 483 00:17:21,440 --> 00:17:22,470 Więc nie było więcej się dzieje. 484 00:17:22,470 --> 00:17:24,920 Ale rzeczywiście, ci faceci, nawet po prostu instynktownie. 485 00:17:24,920 --> 00:17:25,450 przechowywane w ruchu. 486 00:17:25,450 --> 00:17:27,710 Oni nie tylko zatrzymać, gdy tylko skorygować jeden problem. 487 00:17:27,710 --> 00:17:27,839 Tak więc. 488 00:17:27,839 --> 00:17:29,390 Rzeczywiście, mam zamiar mieć zrobić to samo. 489 00:17:29,390 --> 00:17:32,720 Będę musiał sortować zwijanie z tyłu na początku tego problemu, 490 00:17:32,720 --> 00:17:35,630 lub na początku tej tablicy ludzie, zacznijmy nazywając je. 491 00:17:35,630 --> 00:17:38,366 >> A teraz to, co powinno mój algorytm na drugim podaniu być? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: To samo. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: To samo. 494 00:17:39,940 --> 00:17:41,460 A to, zaczynam się podoba, prawda? 495 00:17:41,460 --> 00:17:44,720 Jak tylko znajdziesz się robi to samo w kółko, to 496 00:17:44,720 --> 00:17:47,890 coraz bardziej jak algorytmu, i mniej ludzki instynkt. 497 00:17:47,890 --> 00:17:48,680 >> Więc teraz, znowu to samo. 498 00:17:48,680 --> 00:17:49,870 Dwa i cztery? 499 00:17:49,870 --> 00:17:50,220 Nie. 500 00:17:50,220 --> 00:17:51,050 Cztery i jeden? 501 00:17:51,050 --> 00:17:53,380 Ach, rzeczywiście niektóre działa jeszcze do zrobienia. 502 00:17:53,380 --> 00:17:53,620 Dla i trzy? 503 00:17:53,620 --> 00:17:54,572 Dobra. 504 00:17:54,572 --> 00:17:56,000 Cztery i sześć? 505 00:17:56,000 --> 00:17:58,380 Sześć i pięć? 506 00:17:58,380 --> 00:17:59,470 Sześć i siedem? 507 00:17:59,470 --> 00:18:00,970 OK, teraz zrobić. 508 00:18:00,970 --> 00:18:01,550 OK, nr. 509 00:18:01,550 --> 00:18:02,710 Muszę wrócić. 510 00:18:02,710 --> 00:18:05,130 >> Więc teraz znowu to robimy trochę bardziej świadomie. 511 00:18:05,130 --> 00:18:08,700 A teraz, jest tylko jeden mózg wykonywania tego algorytmu. 512 00:18:08,700 --> 00:18:10,290 Jeden CPU, jeśli będzie. 513 00:18:10,290 --> 00:18:13,090 I szczerze mówiąc, to jedyny zasób będziemy mieć dostęp. 514 00:18:13,090 --> 00:18:16,280 A gdy już wrócisz do klawiatury i mieć coś jak C w naszym 515 00:18:16,280 --> 00:18:19,600 zbycie, my tylko pisania programu że może zrobić jedną rzecz na raz. 516 00:18:19,600 --> 00:18:22,900 Zważywszy, że te chłopaki chwilę temu, dźwigni finansowej ich zbiorowej umysłowego 517 00:18:22,900 --> 00:18:24,180 jak zrobiliście w zera tygodni. 518 00:18:24,180 --> 00:18:24,980 Więc trzymajmy to robi. 519 00:18:24,980 --> 00:18:26,260 >> Dwa i jeden. 520 00:18:26,260 --> 00:18:26,945 Dwa i trzy. 521 00:18:26,945 --> 00:18:27,460 Trzy i cztery. 522 00:18:27,460 --> 00:18:28,310 Cztery i pięć. 523 00:18:28,310 --> 00:18:28,620 Pięć i sześć. 524 00:18:28,620 --> 00:18:30,510 Sześć i siedem. 525 00:18:30,510 --> 00:18:31,880 Gotowe? 526 00:18:31,880 --> 00:18:34,560 Więc jestem, ale pozwól mi grać Adwokat diabła. 527 00:18:34,560 --> 00:18:37,950 Czy, rodzaj komputera, który właśnie zanotował przejść przez ten szereg 528 00:18:37,950 --> 00:18:40,225 ludzi, wiem, że skończę? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Nie 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Więc dlaczego? 531 00:18:41,050 --> 00:18:46,900 Co muszę zrobić, aby stwierdzić stanowczo, że mam zrobić? 532 00:18:46,900 --> 00:18:48,230 Prawdopodobnie jeden karnet. 533 00:18:48,230 --> 00:18:48,430 Prawda? 534 00:18:48,430 --> 00:18:51,760 Bo wszystko, co wiem od tego poprzedniego karnet jest to, że skorygowany błąd. 535 00:18:51,760 --> 00:18:53,920 A to oznacza, może jest jeszcze inny błąd 536 00:18:53,920 --> 00:18:54,840 że muszę poprawić. 537 00:18:54,840 --> 00:18:58,680 Więc mogę tylko mieć pewność, przez przewijanie i następnie sprawdzenie, jedna do dwóch, i dwa 538 00:18:58,680 --> 00:19:00,940 trzy, trzy i cztery, cztery i pięć, pięć i sześć, sześć i siedem. 539 00:19:00,940 --> 00:19:02,510 OK, teraz już nie ma pracy. 540 00:19:02,510 --> 00:19:05,990 >> Mogę z pewnością pamięta, że ​​ja nie pracować z czymś w zmiennej, 541 00:19:05,990 --> 00:19:06,975 jak int. 542 00:19:06,975 --> 00:19:12,490 Nazwijmy to swapy, a jeśli swap jest 0 raz tu dostać, a zaczęło się od 0, a następnie 543 00:19:12,490 --> 00:19:15,520 Chciałbym po prostu być głupi, aby nie poddawać się iz powrotem, sprawdzając ponownie, a 544 00:19:15,520 --> 00:19:16,450 znowu, i znowu, tak? 545 00:19:16,450 --> 00:19:18,450 Bo utkniesz w niektórych rodzaj nieskończonej pętli. 546 00:19:18,450 --> 00:19:21,250 Więc jak tylko jest 0 swapy, możemy twierdzić, że ta 547 00:19:21,250 --> 00:19:23,810 Algorytm jest rzeczywiście pełne. 548 00:19:23,810 --> 00:19:25,400 >> Teraz postawmy nazwę na ten temat. 549 00:19:25,400 --> 00:19:28,930 Algorytm, który proponuję, który właśnie realizowany jest coś, co nazywa bańka 550 00:19:28,930 --> 00:19:32,800 sortowania, znane jako takie, w tym sensie, że numery, które są większe rodzaju 551 00:19:32,800 --> 00:19:37,990 bubble drogę do góry, lub w górę do końca tablicy numerów. 552 00:19:37,990 --> 00:19:40,270 Ale jak skuteczny był ten algorytm? 553 00:19:40,270 --> 00:19:44,600 Ile kroków ja fizycznie muszą się, na przykład, aby posortować je 554 00:19:44,600 --> 00:19:45,850 siedem ludzie? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Cztery do pięciu? 557 00:19:49,550 --> 00:19:51,420 OK, zbyt wiele jest ostatecznie będzie odpowiedź. 558 00:19:51,420 --> 00:19:54,960 Ale nawet wtedy, określony numer nie jest tak interesujące. 559 00:19:54,960 --> 00:19:56,670 Miejmy uogólnić go jako n. 560 00:19:56,670 --> 00:20:00,520 Więc gdybym n ludzi tutaj, a oni były, w pewnym sensie, w przypadkowej kolejności w 561 00:20:00,520 --> 00:20:02,180 początku, w tym oryginalnej kolejności. 562 00:20:02,180 --> 00:20:04,910 Cóż, ile kroków nie mam wziąć na pierwszym przejściu? 563 00:20:04,910 --> 00:20:09,810 Była to jedna, dwie, trzy, cztery, pięć, sześć, a oni siedem osób, więc 564 00:20:09,810 --> 00:20:13,670 to jest siedem, sześć - tak, że jest n minus jedna kroki po raz pierwszy. 565 00:20:13,670 --> 00:20:16,280 >> Teraz, ile kroków nie mam podjąć, gdy przewinął? 566 00:20:16,280 --> 00:20:19,310 Cóż, może faktycznie podwoić, że jeśli bardzo chcieliśmy, ale teraz jestem 567 00:20:19,310 --> 00:20:22,300 tylko powiedzieć, dobrze, kolejny n minus 1. 568 00:20:22,300 --> 00:20:25,240 Więc n minus 1 dostanie irytujące, aby śledzić, więc niech 569 00:20:25,240 --> 00:20:26,400 tylko zaokrąglić w górę nieznacznie. 570 00:20:26,400 --> 00:20:27,770 Więc 2n kroków. 571 00:20:27,770 --> 00:20:29,310 Więc 14 kroków, lub dać. 572 00:20:29,310 --> 00:20:31,930 >> Ile razy biorę krokiem następnym razem? 573 00:20:31,930 --> 00:20:33,740 Cóż, 3n. 574 00:20:33,740 --> 00:20:34,510 naprawdę. 575 00:20:34,510 --> 00:20:37,920 Teraz, w najgorszym przypadku, dla przykład, ile razy będę musiał 576 00:20:37,920 --> 00:20:41,730 poszedł w tę iz powrotem, tam iz powrotem, wykonywania tego algorytmu, zamiana 577 00:20:41,730 --> 00:20:44,620 ludzie na każdym przejściu, z grubsza? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 To rzeczywiście n do kwadratu, tak? 580 00:20:50,010 --> 00:20:53,000 >> Bo w najgorszym wypadku możesz rodzaj z myślą o tym intuicyjnie, 581 00:20:53,000 --> 00:20:54,800 choć może to zająć trochę nieco czasu tonąć w. 582 00:20:54,800 --> 00:20:57,590 W najgorszym przypadku, co by te siedem osób wyglądało, w 583 00:20:57,590 --> 00:21:00,230 warunki umowy ich liczby? 584 00:21:00,230 --> 00:21:01,460 Całkowicie do tyłu, prawda? 585 00:21:01,460 --> 00:21:02,815 I tylko do symulacji, które, co masz na imię? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, można po prostu dołączyć do mnie na tutaj tylko o sekundę? 589 00:21:08,100 --> 00:21:08,880 W rzeczywistości, nie ma. 590 00:21:08,880 --> 00:21:10,150 Niestety Mike, do tyłu niech. 591 00:21:10,150 --> 00:21:10,910 Jak masz na imię? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, pójdziesz ze mnie, jeśli nie masz nic przeciwko. 595 00:21:13,750 --> 00:21:17,150 Więc mam zamiar zaproponować, tylko dla Prostota, że ​​Neil jest teraz w jego 596 00:21:17,150 --> 00:21:18,510 najgorszy możliwy przypadek. 597 00:21:18,510 --> 00:21:20,720 Ale pamiętam, jak I wdrożone mój algorytm. 598 00:21:20,720 --> 00:21:24,530 Mam porównanie, porównanie, porównanie, porównanie, porównanie, oh. 599 00:21:24,530 --> 00:21:26,640 Teraz ci ludzie są z z rzędu, więc to naprawić. 600 00:21:26,640 --> 00:21:27,980 Więc chłopaki zamienić. 601 00:21:27,980 --> 00:21:31,630 Ale uważają się teraz, w jaki sposób o wiele dalej zgadza Neil mają iść? 602 00:21:31,630 --> 00:21:32,690 To mniej więcej n. 603 00:21:32,690 --> 00:21:33,570 Wiesz, to nie jest faktycznie n. 604 00:21:33,570 --> 00:21:36,040 To jak, n minus 1, ale jestem coraz zirytowany śledzenie mało 605 00:21:36,040 --> 00:21:37,550 liczba, więc po prostu nazwać to n. 606 00:21:37,550 --> 00:21:42,860 >> Więc jeśli Neil porusza każdy krok maksymalnie czas i przenieść Neil jeden krok, 607 00:21:42,860 --> 00:21:46,580 Muszę zrobić to bardzo żmudny przepustkę tam iz powrotem, to jest mniej więcej 608 00:21:46,580 --> 00:21:52,080 robi to, n krokach, w sumie n razy, bo to się do mnie 609 00:21:52,080 --> 00:21:55,820 że wiele kroków, aby Neil wszystkie sposób, gdzie należy. 610 00:21:55,820 --> 00:21:58,620 Nie mówiąc już wszyscy jeśli faceci były mis-zamówić również. 611 00:21:58,620 --> 00:22:01,100 >> Więc nazwijmy rodzaju bańki n do kwadratu. 612 00:22:01,100 --> 00:22:04,860 Czas działania tego algorytmu, wydajność tego algorytmu, 613 00:22:04,860 --> 00:22:07,120 wydajność tego algorytmu są po prostu opisać więcej 614 00:22:07,120 --> 00:22:08,800 ogólnie n do kwadratu. 615 00:22:08,800 --> 00:22:11,650 Co jest miłe, bo mogłem zrobić sam przykład z ośmiu osób, dziewięciu 616 00:22:11,650 --> 00:22:15,450 ludzie, miliony ludzi, i że Odpowiedź nie ulegnie zmianie. 617 00:22:15,450 --> 00:22:18,870 >> Jeśli więc wy, nie miałbym nic przeciwko, niech zresetować do miejsca startu. 618 00:22:18,870 --> 00:22:22,510 I spróbujmy podejść i dwie inne sprawdzić, czy nie możemy zrobić fundamentalnie 619 00:22:22,510 --> 00:22:23,820 lepszy niż ten. 620 00:22:23,820 --> 00:22:27,130 Więc tym razem, mam zamiar zaproponować rodzaj innego algorytmu. 621 00:22:27,130 --> 00:22:29,950 To było bardzo mądre z nas ostatni raz, a wy się prawo do 622 00:22:29,950 --> 00:22:32,470 prawo instynkty tylko rodzaju Zamiana parami. 623 00:22:32,470 --> 00:22:36,500 Ale jeśli naprawdę chciałem podejść do tego po prostu, a moim celem jest, aby przenieść 624 00:22:36,500 --> 00:22:39,800 wszystkie małe liczby w ten sposób, a wcisnąć wszystkich dużych liczb, które 625 00:22:39,800 --> 00:22:43,030 sposób, dlaczego nie po prostu zrobić, że w najbardziej naiwny sposób można i zobaczyć, czy ja 626 00:22:43,030 --> 00:22:45,730 można zrobić lepiej niż to, co było dość złożony algorytm? 627 00:22:45,730 --> 00:22:46,620 >> Zobaczmy więc. 628 00:22:46,620 --> 00:22:48,940 Cztery jest dość mała liczba, więc jestem zostawię cię tam chwilę. 629 00:22:48,940 --> 00:22:50,610 Ooh, numer dwa jest jeszcze lepiej. 630 00:22:50,610 --> 00:22:52,230 Więc może po prostu krok do przodu na chwilę? 631 00:22:52,230 --> 00:22:55,670 Obecnie jest to mój najmniejszy numerowane kandydat, i będę pamiętać 632 00:22:55,670 --> 00:22:57,000 że z, jak, zmiennej. 633 00:22:57,000 --> 00:22:57,930 Ale będę zaglądać. 634 00:22:57,930 --> 00:22:59,890 Czy jest ktoś, kogo liczba jest mniejsza? 635 00:22:59,890 --> 00:23:00,460 Six, nie. 636 00:23:00,460 --> 00:23:01,390 Och, jest Neil ponownie. 637 00:23:01,390 --> 00:23:04,050 >> Więc mam zamiar wcisnąć się z powrotem rodzaj koncepcyjnie. 638 00:23:04,050 --> 00:23:05,120 Neil wystąpi. 639 00:23:05,120 --> 00:23:08,440 A teraz, zmienną, że używam do śledzić, kto ma najmniejsze 640 00:23:08,440 --> 00:23:11,390 Numer jest aktualizowana zawierać Neila lokalizacja. 641 00:23:11,390 --> 00:23:12,110 Cóż, zobaczymy. 642 00:23:12,110 --> 00:23:13,960 Trzy, siedem, pięć. 643 00:23:13,960 --> 00:23:15,590 OK, wiem, że Neil był najmniejszy. 644 00:23:15,590 --> 00:23:18,110 Co jest najprostszą rzeczą dla mnie teraz zrobić? 645 00:23:18,110 --> 00:23:21,410 Nie mam zamiaru tracić czasu po prostu przepuszczając Neil jedno miejsce w lewo. 646 00:23:21,410 --> 00:23:25,350 Dlaczego nie mogę umieścić Neil gdzie należy, co jest oczywiście gdzie? 647 00:23:25,350 --> 00:23:26,160 >> Aż na początku. 648 00:23:26,160 --> 00:23:27,720 Więc Neil, chodź ze mną. 649 00:23:27,720 --> 00:23:28,910 I co masz na imię? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Więc Grace, niestety, jesteś rodzaju w drodze. 654 00:23:32,490 --> 00:23:34,290 Jak więc rozwiązać ten problem? 655 00:23:34,290 --> 00:23:34,490 Prawda? 656 00:23:34,490 --> 00:23:37,500 Jeśli jest to tablica, jest tylko siedem miejscowości. 657 00:23:37,500 --> 00:23:40,830 Przypomnijmy, że z Robem, rozmawialiśmy o deklarując wieku, a mieliśmy tylko 658 00:23:40,830 --> 00:23:41,740 skończona liczba grup wiekowych? 659 00:23:41,740 --> 00:23:42,535 Sama idea tutaj. 660 00:23:42,535 --> 00:23:44,300 Mamy tylko skończoną ilość liczb całkowitych. 661 00:23:44,300 --> 00:23:47,590 Grace jest trochę w naszym Tak więc w jaki sposób naprawić? 662 00:23:47,590 --> 00:23:49,555 >> Najprostszym sposobem jest jak, Grace, sorry. 663 00:23:49,555 --> 00:23:51,870 Będziesz musiał przejść istnieje więc możemy zrobić miejsce. 664 00:23:51,870 --> 00:23:55,290 Teraz, jeśli myślisz o tym, być może my po prostu się pogorszyć sytuację. 665 00:23:55,290 --> 00:23:58,510 A może i my, bo co, jeśli Grace była w odpowiednim miejscu? 666 00:23:58,510 --> 00:24:01,730 Ale wiemy, że nie jest, bo inaczej, to byłaby 667 00:24:01,730 --> 00:24:03,980 stojąc w przód zamiast Neil w tym czasie, prawda? 668 00:24:03,980 --> 00:24:05,550 Mamy już sprawdzone jej numer out. 669 00:24:05,550 --> 00:24:05,770 >> Dobrze. 670 00:24:05,770 --> 00:24:09,110 Więc teraz, Neil jest w odpowiednim miejscu, a Mogę zrobić niewielki optymalizacji. 671 00:24:09,110 --> 00:24:11,740 Na następnej minuty, będę ignorować Neil razem, w taki sposób, aby nie 672 00:24:11,740 --> 00:24:15,280 tracić czasu, lub przypadkowo zamienić go na niewłaściwym miejscu. 673 00:24:15,280 --> 00:24:17,805 Więc teraz, jak znaleźć następny Element, który jest najmniejszy? 674 00:24:17,805 --> 00:24:18,480 Two. 675 00:24:18,480 --> 00:24:20,225 To bardzo dobry numer, jeśli chcesz krok do przodu i 676 00:24:20,225 --> 00:24:21,100 Ja pamiętam. 677 00:24:21,100 --> 00:24:21,980 Six, nie jest dobre. 678 00:24:21,980 --> 00:24:24,820 Cztery, trzy, siedem, pięć, nie jest dobre. 679 00:24:24,820 --> 00:24:26,800 Więc pozwól mi przejść do Twój właściwe miejsce. 680 00:24:26,800 --> 00:24:28,470 A my po prostu mieliśmy szczęście tym razem. 681 00:24:28,470 --> 00:24:31,350 >> Teraz mam zamiar zignorować dwóch facetów, a teraz jeszcze jedno 682 00:24:31,350 --> 00:24:32,260 przejść przez to. 683 00:24:32,260 --> 00:24:33,490 Six, że dość mała liczba. 684 00:24:33,490 --> 00:24:34,300 Chodź do przodu. 685 00:24:34,300 --> 00:24:35,220 Oh, przepraszam. 686 00:24:35,220 --> 00:24:37,640 Liczba Grace jest lepszy, to krok na przód. 687 00:24:37,640 --> 00:24:38,260 Cztery. 688 00:24:38,260 --> 00:24:39,120 Niestety, Grace. 689 00:24:39,120 --> 00:24:39,950 Wróć ponownie. 690 00:24:39,950 --> 00:24:41,550 Numer trzy to lepiej. 691 00:24:41,550 --> 00:24:42,290 Seven. 692 00:24:42,290 --> 00:24:42,720 Five. 693 00:24:42,720 --> 00:24:43,550 A teraz to, co masz na imię? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Więc Jason jest teraz najmniejszy Element Wybrałam. 697 00:24:47,050 --> 00:24:49,160 Gdzie on pójdzie? 698 00:24:49,160 --> 00:24:50,380 Więc gdzie sześć jest. 699 00:24:50,380 --> 00:24:51,210 A nazwa jest znowu? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe jest w drodze. 703 00:24:53,220 --> 00:24:54,640 Co najłatwiej zrobić? 704 00:24:54,640 --> 00:24:58,390 Zamiana tych dwóch facetów i kontynuować. 705 00:24:58,390 --> 00:24:59,020 Więc teraz zobaczymy. 706 00:24:59,020 --> 00:25:00,170 Kto jest najmniejszy? 707 00:25:00,170 --> 00:25:01,030 Cztery. 708 00:25:01,030 --> 00:25:01,990 Pozwólcie mi tylko trochę oszukiwać. 709 00:25:01,990 --> 00:25:03,090 Five będzie najmniejsza. 710 00:25:03,090 --> 00:25:05,220 I znaleźć obok, jeśli chcesz do kroku do przodu, co mam zrobić z 711 00:25:05,220 --> 00:25:06,820 ci faceci, z Gabe? 712 00:25:06,820 --> 00:25:08,450 Zamień ponownie. 713 00:25:08,450 --> 00:25:10,740 Więc teraz, jeszcze lekko uszkodzony. 714 00:25:10,740 --> 00:25:14,140 Znalazłem Gabe się najmniejsza, więc I pop go, przenieść was over. 715 00:25:14,140 --> 00:25:15,190 I gotowe. 716 00:25:15,190 --> 00:25:17,200 >> Tak więc odpowiedź jest taka sama. 717 00:25:17,200 --> 00:25:18,600 Efekt końcowy jest taki sam. 718 00:25:18,600 --> 00:25:22,730 Która z tych dwóch algorytmów jest lepiej? 719 00:25:22,730 --> 00:25:23,500 Drugi, słyszałem. 720 00:25:23,500 --> 00:25:24,252 Dlaczego? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Jest n kroki [niesłyszalne]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: To n kroków w najbardziej. 723 00:25:27,600 --> 00:25:28,490 Ciekawe. 724 00:25:28,490 --> 00:25:30,610 Więc jest to jednak? 725 00:25:30,610 --> 00:25:33,630 Jak więc znaleźć najmniejszy element? 726 00:25:33,630 --> 00:25:37,060 Ile kroków nie muszę brać znaleźć najmniejszy element? 727 00:25:37,060 --> 00:25:39,220 I nie patrzeć na drodze na koniec, prawda? 728 00:25:39,220 --> 00:25:41,530 Ponieważ w przypadku najgorszego przypadku, co jeśli Neil był tutaj? 729 00:25:41,530 --> 00:25:45,700 Więc tylko znalezienie najmniejszy element bierze mnie n lub n kroki minus 1. 730 00:25:45,700 --> 00:25:46,100 Ale OK. 731 00:25:46,100 --> 00:25:46,980 Więc naprawić Neil. 732 00:25:46,980 --> 00:25:48,740 Pamiętaj, że około minuty temu. 733 00:25:48,740 --> 00:25:51,680 >> Ale jak znajdę następne najmniejszy element? 734 00:25:51,680 --> 00:25:54,830 To n minus 1, lub n minus 2 naprawdę, od liczby etapów. 735 00:25:54,830 --> 00:25:55,440 Więc OK. 736 00:25:55,440 --> 00:25:57,390 Więc zrobiłem n minus 2. 737 00:25:57,390 --> 00:25:57,600 Dobrze. 738 00:25:57,600 --> 00:25:59,130 Tak, że czuje się trochę lepiej. 739 00:25:59,130 --> 00:25:59,730 Dobrze. 740 00:25:59,730 --> 00:26:03,270 Ile kroków następnym razem znaleźć numer trzy? 741 00:26:03,270 --> 00:26:04,420 Więc n minus 4. 742 00:26:04,420 --> 00:26:07,670 Więc to spada, jeden mniej stawać na każdej iteracji. 743 00:26:07,670 --> 00:26:08,740 Więc to nie czuje się lepiej, prawda? 744 00:26:08,740 --> 00:26:13,450 Jeśli ostatni raz to było w przybliżeniu n razy n, tym razem jest to n minus 1, oraz n minus 745 00:26:13,450 --> 00:26:16,500 2, oraz n minus 3, oraz n minus 4, kropka, kropka, kropka. 746 00:26:16,500 --> 00:26:18,750 Ale czy pamiętacie z liceum podręczniki, trochę oszukiwać 747 00:26:18,750 --> 00:26:24,380 Arkusz z tyłu, który ma formuły, jeśli można dodać do tego szereg liczb, 748 00:26:24,380 --> 00:26:31,280 co liczby stopni będzie, że biorę tutaj? 749 00:26:31,280 --> 00:26:36,580 >> Jest to jedna z tych, jak, N minus 1 razy n, podzielić przez 2. 750 00:26:36,580 --> 00:26:39,040 Więc pozwól mi zobaczyć, czy mogę wyciągnąć to się na chwilę. 751 00:26:39,040 --> 00:26:42,230 I znowu jestem rodzaju zaokrągleń niektórych numery tylko zachować nasze życie proste, 752 00:26:42,230 --> 00:26:47,830 ale o ile pamiętam, to jest coś jak gdyby Ja n minus 1 rzeczy, a następnie n minus 753 00:26:47,830 --> 00:26:53,570 2, a następnie n minus 3, to z grubsza coś w tym ponad 2, a jeśli 754 00:26:53,570 --> 00:26:55,510 rozmnażajcie się na to, że jest faktycznie plac n. 755 00:26:55,510 --> 00:26:58,940 To nie czuje zbyt dobrze. n minus n nad 2. 756 00:26:58,940 --> 00:27:00,350 >> Ale tutaj jest rzeczą. 757 00:27:00,350 --> 00:27:03,720 W dziedzinie informatyki, gdy problemy zaczynają się interesujące jest, gdy n 758 00:27:03,720 --> 00:27:04,700 robi się naprawdę duża. 759 00:27:04,700 --> 00:27:08,110 A gdy n staje się naprawdę duża, co z wartości te będzie dominować wszystko 760 00:27:08,110 --> 00:27:09,750 z innymi? 761 00:27:09,750 --> 00:27:10,990 To rodzaj n kwadratu, tak? 762 00:27:10,990 --> 00:27:13,340 Tak, dzielenie przez 2 jest bardzo dobry. 763 00:27:13,340 --> 00:27:16,740 Ale jeśli mówimy o miliardach z części danych lub biliony 764 00:27:16,740 --> 00:27:18,700 fragmentów danych, OK, jesteś dwa razy szybciej. 765 00:27:18,700 --> 00:27:22,440 Ale kto tak naprawdę obchodzi, że dużej ilości, Jeśli czynnik ten jest co dostaje 766 00:27:22,440 --> 00:27:23,040 większe i większe. 767 00:27:23,040 --> 00:27:25,990 I z pewnością, to sprawia, że ​​więcej Różnica od tego faceta. 768 00:27:25,990 --> 00:27:29,120 Więc nawet jeśli macie rację, Drugi algorytm, nazwijmy go 769 00:27:29,120 --> 00:27:32,970 sort wybór, jest w świecie rzeczywistym, nieco szybciej potencjalnie, bo jestem 770 00:27:32,970 --> 00:27:35,360 biorąc coraz mniej kroki za każdym razem. 771 00:27:35,360 --> 00:27:37,340 >> To naprawdę nie jest zasadniczo szybciej. 772 00:27:37,340 --> 00:27:41,430 Bo jeśli rzeczywiście grać to dla dużych wartości n, na koniec 773 00:27:41,430 --> 00:27:44,750 dzień, na tyle duże, n, to jeszcze będzie czuć się dość powoli. 774 00:27:44,750 --> 00:27:46,770 Cóż, pozwól mi wziąć jeden ostatnio przechodzą na to. 775 00:27:46,770 --> 00:27:48,920 To, co nazwałbym sort wybór. 776 00:27:48,920 --> 00:27:51,040 Czy wy zresetować siebie po raz ostatni? 777 00:27:51,040 --> 00:27:53,550 I w tym ostatnim przypadku, zamierzam zaproponować coś 778 00:27:53,550 --> 00:27:54,970 nazywa rodzaj wstawiania. 779 00:27:54,970 --> 00:27:57,470 Sort Insertion jest, koncepcyjnie, nieco inaczej. 780 00:27:57,470 --> 00:28:00,980 >> Zamiast tam iz powrotem i wybierając najmniejszy element, jestem 781 00:28:00,980 --> 00:28:05,030 po prostu się do czynienia z każdym z nich Chłopaki, jak spotykałem je i włóż 782 00:28:05,030 --> 00:28:06,850 je w ich właściwym miejscu. 783 00:28:06,850 --> 00:28:10,160 Więc mam zamiar zacząć z Grace, i widzę, że jest numer cztery. 784 00:28:10,160 --> 00:28:11,720 Gdzie numer cztery należą? 785 00:28:11,720 --> 00:28:14,940 I nie rozpoczął sortowania niczego, więc Grace trafia na pobyt tam. 786 00:28:14,940 --> 00:28:18,355 A teraz mam zamiar ubiegać, jeśli można zrobić krok w prawo, to 787 00:28:18,355 --> 00:28:21,650 moja posortowane listy, to jest mój nieposortowane pozostała lista. 788 00:28:21,650 --> 00:28:23,260 Więc teraz mam zamiar przejść obok, a co masz na imię? 789 00:28:23,260 --> 00:28:23,700 >> Branson: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Więc Branson jest numerem dwa. 792 00:28:25,375 --> 00:28:27,490 Więc idę do podjęcia się na chwilę. 793 00:28:27,490 --> 00:28:30,940 A teraz, gdy należysz w tej tablicy? 794 00:28:30,940 --> 00:28:32,360 Tak więc na prawo Grace. 795 00:28:32,360 --> 00:28:35,670 Więc znowu, jesteśmy rodzajem dokonywania Grace zrobić dużo pracy tutaj. 796 00:28:35,670 --> 00:28:37,290 Gdzie możemy umieścić? 797 00:28:37,290 --> 00:28:40,120 Więc będziemy przesuwać się do w lewo i włóż Branson tam. 798 00:28:40,120 --> 00:28:41,680 Ale teraz twierdzą, że chłopaki są zrobione. 799 00:28:41,680 --> 00:28:43,240 Ale zauważ, nie używam dodatkowego miejsca. 800 00:28:43,240 --> 00:28:45,130 Jest jeszcze 2 elementy o, 5 tutaj. 801 00:28:45,130 --> 00:28:47,910 Całkowity rozmiar tablicy jest 7, więc jestem nie oszukuje, wszystko w porządku? 802 00:28:47,910 --> 00:28:51,950 >> Więc teraz mamy, z Gabe tutaj, numer sześć, gdzie należysz? 803 00:28:51,950 --> 00:28:52,650 Masz szczęście ponownie. 804 00:28:52,650 --> 00:28:53,820 Więc masz na pobyt tam. 805 00:28:53,820 --> 00:28:57,210 Wystarczy niewielki krok w prawo po prostu wyjaśnić, że jesteś sortowane. 806 00:28:57,210 --> 00:29:00,520 A teraz mamy Neil kolejny numer jeden, gdzie idziesz? 807 00:29:00,520 --> 00:29:03,540 A teraz jest, gdy zaczniemy widzieć, że Algorytm ten, choć na pierwszy 808 00:29:03,540 --> 00:29:05,950 spojrzenie, czuje się całkiem inteligentny, oglądać to, co się wydarzy. 809 00:29:05,950 --> 00:29:07,370 Jeśli można krok do przodu. 810 00:29:07,370 --> 00:29:09,260 >> W przypadku, gdy chcemy umieścić Neil? 811 00:29:09,260 --> 00:29:11,830 Tak oczywiście tutaj, tak jak dostaniemy Neil tam? 812 00:29:11,830 --> 00:29:12,970 Zróbmy to krok po kroku. 813 00:29:12,970 --> 00:29:15,620 Gabe, gdzie trzeba iść? 814 00:29:15,620 --> 00:29:19,590 Tak, więc wziąć jeden duży krok, lub dwie pół-kroki, aby 815 00:29:19,590 --> 00:29:20,820 jeden krok tam. 816 00:29:20,820 --> 00:29:21,750 Grace, gdzie jesteś? 817 00:29:21,750 --> 00:29:22,510 Dobra. 818 00:29:22,510 --> 00:29:23,500 Więc kolejny krok. 819 00:29:23,500 --> 00:29:24,960 I wreszcie, Branson? 820 00:29:24,960 --> 00:29:25,460 Kolejnym krokiem. 821 00:29:25,460 --> 00:29:27,190 A teraz możemy umieścić Neil na miejsce. 822 00:29:27,190 --> 00:29:28,440 >> Więc teraz, kontynuować tę logikę. 823 00:29:28,440 --> 00:29:32,420 Mimo, że nie przenoszą Neil nad, kółko, kółko, aby go 824 00:29:32,420 --> 00:29:36,420 gdzie przechodzi, w najgorszym przypadku, następny numer możemy spotkać może 825 00:29:36,420 --> 00:29:42,220 być numer, powiedzmy, nie było wiele zero, a następnie jedziemy do przesunięcia wszystkich 826 00:29:42,220 --> 00:29:42,730 ci faceci. 827 00:29:42,730 --> 00:29:44,950 Załóżmy, że istnieje liczba, negatywne jeden, to mamy do przesunięcia 828 00:29:44,950 --> 00:29:46,080 wszystkie z tych facetów. 829 00:29:46,080 --> 00:29:48,500 Więc jesteśmy naprawdę tylko trochę przerzucanie Problemem wokół, tak, że jesteśmy 830 00:29:48,500 --> 00:29:52,620 przeniesienie kosztów z Proces selekcji tak wstawiania 831 00:29:52,620 --> 00:29:56,930 Proces, tak, że wy po prostu miał przenieść około n minus coś 832 00:29:56,930 --> 00:29:57,940 liczba kroków. 833 00:29:57,940 --> 00:30:01,200 A że liczba kroków tylko będzie zwiększenie jak wybrać więcej numerów, 834 00:30:01,200 --> 00:30:04,730 czy muszę zachować wtykając chłopaki z powrotem, i z powrotem, i z powrotem. 835 00:30:04,730 --> 00:30:08,320 >> Tak smutne, to wszystkie te algorytmy są n do kwadratu. 836 00:30:08,320 --> 00:30:10,570 Idziemy do przodu i dzięki tym guys, i wizualizacji te trochę 837 00:30:10,570 --> 00:30:11,090 inaczej. 838 00:30:11,090 --> 00:30:12,312 Bardzo dobrze zrobione. 839 00:30:12,312 --> 00:30:14,120 >> [APPLAUSE] 840 00:30:14,120 --> 00:30:15,030 >> Dobrze. 841 00:30:15,030 --> 00:30:16,280 Proszę bardzo. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Dzięki za - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [niesłyszalne] zachować numery. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: No, możesz zachować numery, jak również. 846 00:30:21,990 --> 00:30:23,440 Dobrze. 847 00:30:23,440 --> 00:30:24,100 Niezła robota. 848 00:30:24,100 --> 00:30:25,300 Dobrze. 849 00:30:25,300 --> 00:30:30,510 Zobaczmy więc, jeśli nie możemy teraz podsumować szybciej i bardziej wizualnie, 850 00:30:30,510 --> 00:30:33,410 dokładnie to, co się stało tu w następujący sposób. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Mam zamiar iść do przodu i podciągnąć Firefox. 853 00:30:38,770 --> 00:30:41,310 Będziemy łączyć tę demonstrację w trakcie swojej stronie internetowej. 854 00:30:41,310 --> 00:30:43,870 Java jest trochę irytujące, aby dostać pracę w niektórych przeglądarkach te dni. 855 00:30:43,870 --> 00:30:46,760 Więc jeśli się bawić to w domu, sobie sprawę, być może trzeba użyć przeglądarki Firefox 856 00:30:46,760 --> 00:30:47,990 żeby działało. 857 00:30:47,990 --> 00:30:50,440 I co mam z tym zrobić Demonstracja jest następujący. 858 00:30:50,440 --> 00:30:54,875 >> Na dole, mam całą masę opcje menu, w tym rozpoczęcia i 859 00:30:54,875 --> 00:30:55,840 stop. 860 00:30:55,840 --> 00:30:59,450 Ponadto, jak na bok, nie wydaje się być bug w tych programach, w którym można 861 00:30:59,450 --> 00:31:03,720 nie można rzeczywiście zobaczyć początkowej lub końcowej przytrzymać przycisk, chyba że polecenie lub Alt 862 00:31:03,720 --> 00:31:06,560 plus i powiększyć, które z zaciekawieniem pokazuje więcej przycisków. 863 00:31:06,560 --> 00:31:09,090 Więc po prostu FYI jeśli grasz z tego w domu. 864 00:31:09,090 --> 00:31:12,870 Teraz mam zamiar kliknąć przycisk Start w tak chwilę, po określeniu opóźnienia, 865 00:31:12,870 --> 00:31:16,810 jak, 200 milisekund, po prostu dzięki czemu możemy zobaczyć, co się dzieje. 866 00:31:16,810 --> 00:31:20,180 >> Tak więc twierdzenie, że jest to wizualizacja z pierwszym algorytmem 867 00:31:20,180 --> 00:31:23,730 ci faceci nie, sortowanie bąbelkowe, przy czym Zamieniliśmy ludzi parami. 868 00:31:23,730 --> 00:31:27,490 Kluczem do tej wizualizacji pigułce jest to, że wysokość pasków 869 00:31:27,490 --> 00:31:30,510 oznacza wielkości liczby. 870 00:31:30,510 --> 00:31:32,210 Więc wyższy bar, większa liczba. 871 00:31:32,210 --> 00:31:33,680 Krótszy bar, mniejsza liczba. 872 00:31:33,680 --> 00:31:38,630 A jeśli zauważysz, jedziemy przez Pierwsza iteracja tego algorytmu, 873 00:31:38,630 --> 00:31:42,620 zamiana małych i dużych liczb, tak aby mała liczba jest na pierwszym i 874 00:31:42,620 --> 00:31:44,280 Duża liczba przesuwa się w prawo. 875 00:31:44,280 --> 00:31:48,770 >> I jak tylko dostać się do końca tablicy wiele więcej numerów niż siedem, jesteśmy 876 00:31:48,770 --> 00:31:49,900 zamiar wrócić do początku. 877 00:31:49,900 --> 00:31:51,140 I przewidywania tego. 878 00:31:51,140 --> 00:31:54,860 Na lewej stronie, że mały facet będzie zamienić na bok, a to 879 00:31:54,860 --> 00:31:56,010 proces powtarza się. 880 00:31:56,010 --> 00:31:59,450 Teraz ta wizualizacja szybko dostaje nudne, więc pozwól mi iść dalej i zatrzymać 881 00:31:59,450 --> 00:32:04,170 to zmień coś znacznie opóźnienia szybciej po to, żeby teraz, wyczucie 882 00:32:04,170 --> 00:32:05,060 ten algorytm. 883 00:32:05,060 --> 00:32:07,840 >> Więc nawet jakbym pędził go, to jest jak modernizacja mój procesor, kupując 884 00:32:07,840 --> 00:32:08,580 nowy komputer. 885 00:32:08,580 --> 00:32:12,980 I nie całkowicie zmieniły moje algorytm, ale można rzeczywiście zobaczyć więcej 886 00:32:12,980 --> 00:32:16,800 wyraźniej niż z ludźmi, że duża Liczby są przepuszczanie do szczytu, 887 00:32:16,800 --> 00:32:20,900 i małych pęcherzyków są liczby do dołu. 888 00:32:20,900 --> 00:32:22,390 A teraz to, co tutaj klasyfikowane. 889 00:32:22,390 --> 00:32:25,260 I jak na bok, na placach, jest tam jest wiele do księgowości 890 00:32:25,260 --> 00:32:28,010 pomóc policzyć ile porównań, lub ile ma swaps 891 00:32:28,010 --> 00:32:28,950 faktycznie zostało zrobione. 892 00:32:28,950 --> 00:32:30,750 >> Cóż, spróbować jednego z inni widzieliśmy. 893 00:32:30,750 --> 00:32:37,116 Pozwól mi kliknij rodzaju bańki tutaj, a pozwól mi wybrać, i cała ta strona 894 00:32:37,116 --> 00:32:38,936 jest trochę błędów. 895 00:32:38,936 --> 00:32:41,155 Miejmy zaakceptować ryzyko i uruchomić go ponownie. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Proszę bardzo. 898 00:32:45,030 --> 00:32:47,180 Więc zróbmy coś w rodzaju wyboru. 899 00:32:47,180 --> 00:32:49,140 Nie wiem, dlaczego menu pojawia się tam. 900 00:32:49,140 --> 00:32:54,070 Miejmy powiększać to naprawić bug, to zmienić do 50. 901 00:32:54,070 --> 00:32:56,020 Ach, niech faktycznie , które znacznie szybciej. 902 00:32:56,020 --> 00:32:59,160 Pięć milisekund lub tak, i Start. 903 00:32:59,160 --> 00:33:00,470 >> Jest to więc rodzaj selekcji. 904 00:33:00,470 --> 00:33:03,070 Więc jeszcze raz, pomyśl o tym, co A z ludzi tutaj. 905 00:33:03,070 --> 00:33:08,490 Przeszliśmy tablicy i wybrany najmniejszy element ponownie 906 00:33:08,490 --> 00:33:09,250 i znowu, i znowu. 907 00:33:09,250 --> 00:33:11,110 Teraz twierdzą, że była jeszcze bardzo złe. 908 00:33:11,110 --> 00:33:15,010 To wciąż n do kwadratu, lub dać, ale to było w rzeczywistości, nieco 909 00:33:15,010 --> 00:33:18,280 szybciej, bo rzeczywiście przy nieco mniej etapów każdym. 910 00:33:18,280 --> 00:33:19,800 Ale my tylko mówimy co? 911 00:33:19,800 --> 00:33:21,830 Być może 40 lub tak bary tutaj? 912 00:33:21,830 --> 00:33:23,200 Nie mówimy 40.000.000. 913 00:33:23,200 --> 00:33:27,430 Więc to nie jest dla mnie zupełnie jasne, że był rzeczywiście znaczący zysk. 914 00:33:27,430 --> 00:33:32,530 >> Chciałbym teraz wrócić i zmienić do naszych Trzeci algorytm, który wybrać 915 00:33:32,530 --> 00:33:33,180 sort wstawiania. 916 00:33:33,180 --> 00:33:36,380 A teraz to naprawdę buggy, ponieważ menu naprawdę nie powinno być tam. 917 00:33:36,380 --> 00:33:40,840 Więc teraz my przewijania tutaj i zacząć ten algorytm. 918 00:33:40,840 --> 00:33:43,270 Whoop, start i stop. 919 00:33:43,270 --> 00:33:47,160 Więc ten jeden rodzaj ma ładny wzór do tego, w którym jesteśmy znowu 920 00:33:47,160 --> 00:33:50,240 włożeniu ludzi, lub W tym przypadku, paski do 921 00:33:50,240 --> 00:33:52,620 ich właściwe miejsce. 922 00:33:52,620 --> 00:33:55,430 I to już zrobione wcześniej Odwróciłem się. 923 00:33:55,430 --> 00:33:58,940 Ale również to, w teorii, jest nadal n do kwadratu. 924 00:33:58,940 --> 00:34:01,430 >> Zobaczmy więc, jeśli nie możemy podsumować Są następujące. 925 00:34:01,430 --> 00:34:04,750 Mam zamiar iść do przodu i po prostu dać nam coś w rodzaju wspólnej drodze rozmowy 926 00:34:04,750 --> 00:34:08,489 o tych rzeczach, pozwól mi przedstawić tylko trochę notacji tutaj. 927 00:34:08,489 --> 00:34:12,480 Czy na pewno chcesz zobaczyć coś, co nazywa big O, ponieważ jest dosłownie duża 928 00:34:12,480 --> 00:34:16,320 O. I to jest sposób, że komputer naukowiec lub matematyk nawet używa 929 00:34:16,320 --> 00:34:19,230 opisać czas pracy pewnego algorytmu. 930 00:34:19,230 --> 00:34:21,400 Ile kroków to właściwie zabrać? 931 00:34:21,400 --> 00:34:25,080 >> Teraz będę musiał się wstydzić z mój charakter pisma tutaj za chwilę. 932 00:34:25,080 --> 00:34:29,020 Ale pozwól mi iść dalej i powiedzieć, że to będzie wielki O tutaj. 933 00:34:29,020 --> 00:34:33,610 I niech mi przedstawić jeszcze jeden symbol, omega kapitału. 934 00:34:33,610 --> 00:34:37,080 Omega ma być odwrotnie, zasadniczo, z dużym O. mając na uwadze duże O 935 00:34:37,080 --> 00:34:40,790 oznacza, w najgorszym przypadku, ile czasu może jakiś algorytm podejmuje, 936 00:34:40,790 --> 00:34:43,480 warunki n, omega będzie się, ile czasu może to 937 00:34:43,480 --> 00:34:45,409 się w najlepszym przypadku. 938 00:34:45,409 --> 00:34:48,090 I zobaczymy, co rozumiemy przez najlepszym wypadku za chwilę. 939 00:34:48,090 --> 00:34:49,940 >> Zacznijmy więc coś prostego. 940 00:34:49,940 --> 00:34:54,719 Zacznę liniowym wyszukiwania. 941 00:34:54,719 --> 00:34:55,679 Więc nie sortowania. 942 00:34:55,679 --> 00:34:58,000 Nazwijmy ten liniowy wyszukiwania. 943 00:34:58,000 --> 00:35:01,140 A teraz, zrobić trochę Stół z tego. 944 00:35:01,140 --> 00:35:06,600 Teraz, w przypadku liniowej wyszukiwania W najgorszym przypadku, ile kroków jest 945 00:35:06,600 --> 00:35:11,770 to zajmie mi znaleźć liczba arbitralnego wyboru? 946 00:35:11,770 --> 00:35:14,540 I jest n liczba drzwi lub n łączna liczba. 947 00:35:14,540 --> 00:35:15,940 Najgorszy przypadek. 948 00:35:15,940 --> 00:35:18,800 Ile kroków będę musiał podjąć, aby znaleźć numer 50 w tablicy 949 00:35:18,800 --> 00:35:20,830 drzwi n? 950 00:35:20,830 --> 00:35:21,410 A dlaczego? 951 00:35:21,410 --> 00:35:23,680 Ponieważ może to być wszystkie sposób na na końcu. 952 00:35:23,680 --> 00:35:27,120 Tak więc podobnie jak Jennifer spotkałem, numer 50 było sposobem na, więc w 953 00:35:27,120 --> 00:35:30,760 Szukaj w najgorszym przypadku liniowy jest duże O n, powiemy. 954 00:35:30,760 --> 00:35:33,430 >> Co najlepszym przypadku, jeśli się naprawdę szczęśliwy? 955 00:35:33,430 --> 00:35:36,200 To po prostu będzie jeden krok, lub stałą ilość kroków. 956 00:35:36,200 --> 00:35:37,830 Więc opiszemy, że jako 1. 957 00:35:37,830 --> 00:35:39,010 Więc to jest bardzo dobre. 958 00:35:39,010 --> 00:35:41,210 Teraz co, jeśli zrobił coś jak wyszukiwanie binarne? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Więc binary search, w najgorszym sprawę, jak wiele czasu zajęło? 961 00:35:47,846 --> 00:35:49,250 >> [Wstawienie GŁOSÓW] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Tak właściwie, to słyszałem to w kilku miejscach. 963 00:35:51,310 --> 00:35:56,390 Więc to faktycznie log n, lub dać, bo jak podzielić listę na pół 964 00:35:56,390 --> 00:36:00,730 znowu, i znowu, i znowu, że jesteśmy w stanie znaleźć ostatecznie wartość, 965 00:36:00,730 --> 00:36:04,750 jeśli jest tam, ale jest haczyk. 966 00:36:04,750 --> 00:36:08,590 Co jest założenie, że mamy do za oczywiste dla binarnego wyszukiwania? 967 00:36:08,590 --> 00:36:09,700 To musi być sortowane. 968 00:36:09,700 --> 00:36:12,770 To nie jest posortowane, można podzielić na rzecz w pół znowu i znowu, i 969 00:36:12,770 --> 00:36:15,490 mogą iść w lewo, i można iść w prawo, a można przejść w lewo i prawo, ale jesteś 970 00:36:15,490 --> 00:36:18,070 nie będzie znaleźć elementu, gdyby lista nie jest posortowana, ponieważ 971 00:36:18,070 --> 00:36:18,790 można go przegapić. 972 00:36:18,790 --> 00:36:22,120 Ponieważ twój heurystyki, aby jechać w lewo lub w prawo, będzie błędna, jeśli jest 973 00:36:22,120 --> 00:36:23,420 rzeczywiście nie sortowane. 974 00:36:23,420 --> 00:36:26,110 Więc jest coś w rodzaju ukrytych kosztów do korzystania z czegoś takiego. 975 00:36:26,110 --> 00:36:29,250 >> Teraz idziemy do naszego sortowaniu Algorytmy nie szukając - 976 00:36:29,250 --> 00:36:31,140 oh, naprawdę idziemy w ślepą. 977 00:36:31,140 --> 00:36:33,190 Binary search w najlepszym przypadku? 978 00:36:33,190 --> 00:36:36,290 To także 1, jeśli okazuje się być w samym środku tablicy, lub 979 00:36:36,290 --> 00:36:37,810 Środek książki telefonicznej. 980 00:36:37,810 --> 00:36:39,710 Teraz zróbmy coś w rodzaju bańki. 981 00:36:39,710 --> 00:36:42,570 Więc jeszcze raz, teraz wchodzimy rodzaju, a nie wyszukiwania. 982 00:36:42,570 --> 00:36:47,220 >> W najgorszym przypadku, ile kroków nie mamy Sortowanie bąbelkowe roszczenia zajmie? 983 00:36:47,220 --> 00:36:48,410 n do kwadratu. 984 00:36:48,410 --> 00:36:49,200 Więc mam zamiar wyciągnąć to. 985 00:36:49,200 --> 00:36:51,710 Och, moje pismo wygląda jeszcze gorzej , kiedy to przewiduje się, że duży. 986 00:36:51,710 --> 00:36:52,510 Dobrze. 987 00:36:52,510 --> 00:36:53,570 Więc to n do kwadratu. 988 00:36:53,570 --> 00:36:59,460 A w najlepszym przypadku rodzaju bańki, ile kroków to będzie trwało? 989 00:36:59,460 --> 00:37:00,980 1, słyszałem. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, słyszałem. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, słyszałem. 994 00:37:05,010 --> 00:37:06,670 Czy słyszę 3? 995 00:37:06,670 --> 00:37:07,080 Dobrze. 996 00:37:07,080 --> 00:37:11,390 Tak słyszałem 1, n, 2, ale niech odebrać Oprócz co najmniej pierwszy z tych 997 00:37:11,390 --> 00:37:12,330 sugestie, 1. 998 00:37:12,330 --> 00:37:15,370 To nie jest zły instynkt jest, bo to rodzaj następujący wzór tutaj. 999 00:37:15,370 --> 00:37:19,670 Ale jeśli to tylko 1 krok, jak w świat mógł I twierdzą, że lista 1000 00:37:19,670 --> 00:37:22,900 jest posortowana, bo jeśli mam tylko dozwolone wziąć 1 krok, ile elementów 1001 00:37:22,900 --> 00:37:25,230 faktycznie mogłem sprawdzić, aby mieć pewność? 1002 00:37:25,230 --> 00:37:28,270 Cóż, po prostu 1, co oznacza, że ​​jest n minus 1 elementy, które mogą być z 1003 00:37:28,270 --> 00:37:31,310 celu, a ja po prostu się na wierze, po patrząc na 1 element, który 1004 00:37:31,310 --> 00:37:31,850 rzeczą jest posortowana. 1005 00:37:31,850 --> 00:37:33,930 Więc 1 nie poprawić tutaj. 1006 00:37:33,930 --> 00:37:35,710 Tak minimalnie, jak wiele mam patrzeć? 1007 00:37:35,710 --> 00:37:36,680 >> [Wstawienie GŁOSÓW] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n minus 1, a tak naprawdę, n, bo trzeba spojrzeć na każdy 1009 00:37:40,160 --> 00:37:42,190 Element, aby upewnić się, że to nie jest w porządku. 1010 00:37:42,190 --> 00:37:44,750 Ale znowu, będziemy sortować fali naszej ręce w mniejszych liczbach i 1011 00:37:44,750 --> 00:37:47,100 Zakładamy, że w n dostaje duże, że są nieciekawe tak. 1012 00:37:47,100 --> 00:37:48,380 Więc to sortowanie bąbelkowe. 1013 00:37:48,380 --> 00:37:49,830 A teraz zróbmy tych dwóch ostatnich. 1014 00:37:49,830 --> 00:37:53,520 Sort Selection, a następnie my będziemy zrobić coś w rodzaju wstawiania. 1015 00:37:53,520 --> 00:37:57,160 A potem będziemy cios umysły o coś znacznie 1016 00:37:57,160 --> 00:37:58,926 lepiej wszystkie z nich. 1017 00:37:58,926 --> 00:38:00,410 Dobrze. 1018 00:38:00,410 --> 00:38:04,700 >> Jaki jest najgorszy przypadek działa Czas rodzaju selekcji? 1019 00:38:04,700 --> 00:38:05,680 >> GŁOŚNIK 4: n do kwadratu. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n plac, słyszę. 1021 00:38:06,710 --> 00:38:09,790 Ale dlaczego n do kwadratu, intuicyjnie? 1022 00:38:09,790 --> 00:38:11,170 >> GŁOŚNIK 4: Bo po prostu to zrobił. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Bo po prostu to zrobił. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Dobra odpowiedź. 1026 00:38:13,380 --> 00:38:16,660 Ale intuicyjnie, dlaczego wybór sort n do kwadratu? 1027 00:38:16,660 --> 00:38:18,980 Czego mamy do czynienia znowu i znowu? 1028 00:38:18,980 --> 00:38:22,570 Musieliśmy przeglądając, są Ci najmniejszy, jesteś 1029 00:38:22,570 --> 00:38:24,020 Najmniejszy, jesteś najmniejsze. 1030 00:38:24,020 --> 00:38:27,480 I przyznaje, że byliśmy w stanie podjąć n kroki, a następnie n minus 1, to n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Ale jeśli rodzaj dodać te wszystkie góry, lub zgłosić się na wierze, że dodałem 1032 00:38:30,700 --> 00:38:34,810 im się z góry, mamy mniej więcej n do kwadratu minus niektórych mniejszych ilościach. 1033 00:38:34,810 --> 00:38:36,730 Więc mam zamiar zadzwonić to n do kwadratu. 1034 00:38:36,730 --> 00:38:39,530 Ale z rodzaju wyboru w najlepsze Sprawa, ile kroków jest 1035 00:38:39,530 --> 00:38:40,632 zabierze mnie? 1036 00:38:40,632 --> 00:38:41,840 >> Głośnik 5: [niesłyszalne] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: To niestety nadal n do kwadratu, tak? 1038 00:38:44,350 --> 00:38:49,590 Bo jeśli mam wybór najmniejsza elementem, a mieliśmy siedem osób tutaj, 1039 00:38:49,590 --> 00:38:53,280 Wiem tylko, gdy dostanę się do bardzo end, które znalazłem najmniejszy 1040 00:38:53,280 --> 00:38:55,670 liczba, gdzie on lub ona może być. 1041 00:38:55,670 --> 00:38:58,820 Ale jak znajdę następne najmniejsza liczba? 1042 00:38:58,820 --> 00:39:00,160 Muszę zrobić kolejną przepustkę. 1043 00:39:00,160 --> 00:39:04,810 Tak więc, w najlepszym przypadku, co jest Wejście do rodzaju selekcji? 1044 00:39:04,810 --> 00:39:07,830 Jest już lista rodzaj, numer jeden, numer dwa, numer trzy, numer cztery. 1045 00:39:07,830 --> 00:39:08,600 Ale jestem komputer. 1046 00:39:08,600 --> 00:39:10,190 Mogę tylko patrzeć na jednego rzeczy naraz. 1047 00:39:10,190 --> 00:39:12,465 I nie można sortować z krok powrotem jak człowieka i powiedzieć, 1048 00:39:12,465 --> 00:39:14,030 ooh, to wygląda poprawnie. 1049 00:39:14,030 --> 00:39:17,580 >> Mogę jedynie orzekać poprawności w rodzaj selekcji, wybierając 1050 00:39:17,580 --> 00:39:18,370 najmniejsza liczba. 1051 00:39:18,370 --> 00:39:21,390 Ale nawet jeśli znajdę numer jeden pierwszy, jeśli nie wiem nic więcej na temat 1052 00:39:21,390 --> 00:39:24,460 inne numery, co nie, wszystko co wiem, że byłem przekazał tablicę 1053 00:39:24,460 --> 00:39:27,930 lub zestaw drzwi, za którymi są numery, jedynym sposobem wiem, że jeden 1054 00:39:27,930 --> 00:39:28,680 był najmniejszy? 1055 00:39:28,680 --> 00:39:32,440 Jeśli dostanę się aż tutaj, i uświadomić sobie, cholera, jeden był naprawdę najmniejszy. 1056 00:39:32,440 --> 00:39:34,870 >> Ale jak mam to określić, że dwa to następna najmniejsza? 1057 00:39:34,870 --> 00:39:38,350 Robiąc to samo nieskuteczność znowu i znowu. 1058 00:39:38,350 --> 00:39:42,210 Więc w końcu, z rodzaju wstawiania sposób, w najgorszym przypadku, 1059 00:39:42,210 --> 00:39:44,990 nie możemy powiedzieć, że to działa? 1060 00:39:44,990 --> 00:39:49,100 To też jest n do kwadratu. 1061 00:39:49,100 --> 00:39:53,020 A co w najlepszym wypadku? 1062 00:39:53,020 --> 00:39:56,282 Zostawimy to jako cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Będziemy wypełnić tego pustego czasu następnego, ale pozwól mi najpierw Proponuję 1064 00:40:00,090 --> 00:40:02,620 zasadniczo lepiej niż wszystkie z nich, prawda? 1065 00:40:02,620 --> 00:40:05,220 >> Więc zastanów się sam co wstawiania sort będzie. 1066 00:40:05,220 --> 00:40:06,910 Dobrze, że nie było bardzo dramatyczne, bo ja jestem tylko jedna 1067 00:40:06,910 --> 00:40:08,970 że widział zmiany. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Więc tutaj mamy nieco inna demonstracja. 1071 00:40:12,615 --> 00:40:16,580 Gdybym przybliżyć tutaj, zobaczysz, że na lewej mamy coś w rodzaju bańki, w 1072 00:40:16,580 --> 00:40:20,740 middle mamy rodzaj selekcji, a na prawej, mamy coś, czego 1073 00:40:20,740 --> 00:40:23,380 nie wyglądał na jeszcze nazywa połączyć rodzaju. 1074 00:40:23,380 --> 00:40:26,080 Ale za co byliśmy tu robisz tak daleko dziś. 1075 00:40:26,080 --> 00:40:29,200 Gdy Jennifer pierwszy wszedł na scenę, poszliśmy przez tablicę liczb 1076 00:40:29,200 --> 00:40:33,750 znowu, i znowu, z liniowym wyszukiwania i dostaliśmy czas pracy liniowej, big O 1077 00:40:33,750 --> 00:40:35,100 n, że tak powiem. 1078 00:40:35,100 --> 00:40:41,000 >> Kiedy teraz rozważyć pierwszy tydzień class, gdy mieliśmy dziel i rządź, 1079 00:40:41,000 --> 00:40:43,740 i my książka telefoniczna łzawienie, i Jennifer, a my wspólnie 1080 00:40:43,740 --> 00:40:47,500 wykorzystała ten klucz insight, który miał powtarzać się w kółko przez 1081 00:40:47,500 --> 00:40:50,930 jakoś wyrzucać, wyrzucać, wyrzucać, pół problemu, lub 1082 00:40:50,930 --> 00:40:55,320 Ogólnie, dzielenie problem w połowie, a następnie leczeniu mniejszy kawałek 1083 00:40:55,320 --> 00:40:59,630 Problem jak koncepcyjnie równoważny z drugiej strony, że w jakiś sposób nie 1084 00:40:59,630 --> 00:41:00,910 zasadniczo lepiej. 1085 00:41:00,910 --> 00:41:04,720 Ale z rodzaju bańki, z wyboru sort, z rodzaju wstawiania, mamy może 1086 00:41:04,720 --> 00:41:06,560 ma takie spostrzeżenia, że ​​Jennifer nie. 1087 00:41:06,560 --> 00:41:10,220 Mamy dość dużo właśnie wrócił i dalej cała masa czasu, a my 1088 00:41:10,220 --> 00:41:12,650 Podrasowane rzeczy trochę, zamiana W tym celu, może być 1089 00:41:12,650 --> 00:41:13,730 wstawiania lub wybierania. 1090 00:41:13,730 --> 00:41:16,950 A na koniec dnia, i tak dużo z niezręcznej chodzenia w tę iz powrotem. 1091 00:41:16,950 --> 00:41:21,160 My nie naprawdę coś wykorzystać mądry jak Jennifer lubił podzielenie 1092 00:41:21,160 --> 00:41:22,040 i podboju. 1093 00:41:22,040 --> 00:41:25,620 >> Tak połączyć rodzaju kontrastu, które nie zobaczy dopiero w przyszłym tygodniu, to będzie 1094 00:41:25,620 --> 00:41:29,540 wykorzystać ten klucz pomysł, dzieląc wejściowego, a następnie zmniejszenie o połowę, a następnie 1095 00:41:29,540 --> 00:41:30,580 zmniejszenie o połowę, a następnie połowę. 1096 00:41:30,580 --> 00:41:34,590 I na każdej iteracji tej pętli sortowania lewą połowę, a prawo 1097 00:41:34,590 --> 00:41:38,200 połowę, a następnie w lewej połowie lewej połowie, i prawa połowa w lewo, a następnie 1098 00:41:38,200 --> 00:41:40,990 Lewa połowa prawej połowie, a Prawa połowa prawej połowie. 1099 00:41:40,990 --> 00:41:42,840 I powtarzając raz po raz. 1100 00:41:42,840 --> 00:41:46,170 >> Więc widzisz to wizualnie, ale to jest to, co nas czeka w przyszłym tygodniu. 1101 00:41:46,170 --> 00:41:49,760 A w ogóle, kiedy myślimy trochę nieco trudniej na takiego problemu. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Mamy n kwadrat na lewo, n kwadrat w środku, a n 1104 00:41:57,970 --> 00:41:59,400 zaloguj n po prawej stronie. 1105 00:41:59,400 --> 00:42:00,590 Więc nie jest twoje prawdziwe cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Do zobaczenia w poniedziałek. 1107 00:42:02,040 --> 00:42:05,163 >> [APPLAUSE]