1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [MUZYKI] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. MALAN: Jest CS50. 5 00:00:12,550 --> 00:00:14,612 I to jest początek trzeciego tygodnia. 6 00:00:14,612 --> 00:00:16,820 Mamy więc dużo ekscytujące rzeczy na pokrycie dziś. 7 00:00:16,820 --> 00:00:20,160 Wiele możliwości Wolontariusze na scenie. 8 00:00:20,160 --> 00:00:22,780 I w końcu, dzisiaj jest nie chodzi o kod w ogóle. 9 00:00:22,780 --> 00:00:24,820 Ale tu chodzi o pomysły, a to o algorytmach, 10 00:00:24,820 --> 00:00:28,420 i faktycznie przywraca niektóre Wnioski wyciągnięte z tygodnia zerowej, 11 00:00:28,420 --> 00:00:31,910 gdzie przypomnieć, że wprowadził tę potworność. 12 00:00:31,910 --> 00:00:33,880 I pożyczki inspiracji z tym, aby rozpocząć 13 00:00:33,880 --> 00:00:36,879 rozwiązać coraz bardziej wyrafinowane Problemy algorytmicznie. 14 00:00:36,879 --> 00:00:38,420 Ale najpierw kilka ogłoszeń. 15 00:00:38,420 --> 00:00:42,020 Tak jeden, jeśli chcesz się przyłączyć Personel i koledzy CS50 jest w porze lunchu 16 00:00:42,020 --> 00:00:44,670 w ten piątek, zarówno tutaj, jak iw Cambridge oraz w New Haven, 17 00:00:44,670 --> 00:00:48,060 odwiedź kurs na stronę internetową, gdzie można znaleźć adresu URL. 18 00:00:48,060 --> 00:00:50,390 Wykład w środę będzie Nie będzie tu Sanders. 19 00:00:50,390 --> 00:00:53,610 To będzie tylko online, więc dostroić się na stronie internetowej CS50, w 20 00:00:53,610 --> 00:00:55,850 czy tu, w Cambridge lub New Haven, jak również. 21 00:00:55,850 --> 00:00:58,110 >> A potem problemu ustawić dwa jest już w Twoich rękach. 22 00:00:58,110 --> 00:01:03,067 Jeśli nie masz jeszcze zanurkował w, pozwala mi zaoferować silnie sformułowane sugestię 23 00:01:03,067 --> 00:01:05,150 , że zwłaszcza teraz, jak problem ustawia zaliczki, 24 00:01:05,150 --> 00:01:08,669 naprawdę chcesz rozpocząć już teraz, jeśli nie babrać się nieco na weekend lub przed 25 00:01:08,669 --> 00:01:10,710 kiedy po raz pierwszy wyjść na Piątki, bo będziesz 26 00:01:10,710 --> 00:01:14,380 okaże się, że nie są one koniecznie coraz dłuższe i bardziej wymagające na 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Myślę, że przekonasz się, że w Ogólnie rzecz biorąc, mają tendencję do podejmowania grubsza 29 00:01:17,575 --> 00:01:18,892 około samym czasie. 30 00:01:18,892 --> 00:01:20,850 Ale to oczywiście zależy na ucznia, a to 31 00:01:20,850 --> 00:01:22,880 zależy od sposobu myślenia z którym się do niego zbliżasz. 32 00:01:22,880 --> 00:01:24,910 Ale zawsze, będziesz uruchomić przeciwko jakiejś ścianie, 33 00:01:24,910 --> 00:01:26,350 i masz zamiar trafić jakiś błąd, a ty po prostu 34 00:01:26,350 --> 00:01:27,950 nie będzie mógł się nad nim w pewnym momencie. 35 00:01:27,950 --> 00:01:31,380 I to jest niezwykle cenne, aby móc odejść, wrócić następnego dnia, 36 00:01:31,380 --> 00:01:35,286 udać się do godzin pracy biura, post CS50 Dyskutuj lub tym podobne, aby rzeczywiście uzyskać odblokowane. 37 00:01:35,286 --> 00:01:36,160 Miejcie to na uwadze. 38 00:01:36,160 --> 00:01:40,830 Począwszy najwcześniej, jak to możliwe jest najlepszą rzeczą, jaką możesz zrobić. 39 00:01:40,830 --> 00:01:44,160 Tak tu, gdzie zaczęliśmy klasa, ponad w tygodniu zerowym. 40 00:01:44,160 --> 00:01:47,441 I możemy się wolontariuszem tutaj, aby pomóc mi znaleźć mikrofony? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Wstał już. 43 00:01:48,900 --> 00:01:50,080 Chodź na górę. 44 00:01:50,080 --> 00:01:53,707 Domyślam się, że to się uda. 45 00:01:53,707 --> 00:01:54,415 Jak masz na imię? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 David J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Chodź na górę. 49 00:01:57,910 --> 00:01:58,619 Miło cię poznać. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Miło cię poznać. 51 00:01:59,910 --> 00:02:02,772 David J. MALAN: I tu był z nami w tym tygodniu zerowym, oczywiście. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: byłem. 53 00:02:03,028 --> 00:02:03,160 Byłem. 54 00:02:03,160 --> 00:02:05,868 >> David J. MALAN: Więc można iść do przodu i znaleźć dla nas Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tak szybko, jak to możliwe? 56 00:02:08,639 --> 00:02:10,639 Tak szybko, jak to tylko możliwe. 57 00:02:10,639 --> 00:02:13,756 Dosłownie rozrywając problem w połowie, jak trzeba. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 David J. MALAN: Dosłownie łzawienie problem w połowie. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Och. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Bardzo dobrze. 64 00:02:23,300 --> 00:02:23,700 >> David J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Dobry. 66 00:02:24,200 --> 00:02:24,701 Dziękuję. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Bardzo dobry. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> David J. MALAN: A więc teraz, już stopniała w dół 70 00:02:27,610 --> 00:02:29,320 połowie wielkości tego problemu. 71 00:02:29,320 --> 00:02:31,267 Teraz jesteśmy w dół do kwartału. 72 00:02:31,267 --> 00:02:33,475 Czy zwracać uwagę na po której stronie jesteśmy utrzymanie? 73 00:02:33,475 --> 00:02:34,405 >> [LAUGHING] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Tak, ja think-- 75 00:02:35,970 --> 00:02:37,594 >> David J. MALAN: Co sekcja jesteśmy? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Tłumiki, tak. 77 00:02:39,150 --> 00:02:39,941 >> David J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Ale Mike Smith jedzie być po Tłumiki. 79 00:02:42,810 --> 00:02:44,130 Więc-- 80 00:02:44,130 --> 00:02:48,180 >> [LAUGHING] 81 00:02:48,180 --> 00:02:48,742 >> W porządku. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Gdzie szukamy? 83 00:02:50,200 --> 00:02:52,049 David J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 David J. MALAN: Teraz jesteśmy w chirurgiczna. 86 00:02:54,760 --> 00:02:57,840 Teraz lekarze. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- chodźmy z rzeczywistością. 89 00:02:59,856 --> 00:03:00,370 Realne. 90 00:03:00,370 --> 00:03:00,970 >> David J. MALAN: Biura. 91 00:03:00,970 --> 00:03:01,470 OK. 92 00:03:01,470 --> 00:03:03,700 Jeśli potrzebujesz rzeczywistym. 93 00:03:03,700 --> 00:03:05,250 Teraz, w jaki sposób jest Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: ten sposób. 95 00:03:06,250 --> 00:03:07,333 >> David J. MALAN: Którędy? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Czekaj. 97 00:03:08,240 --> 00:03:08,790 Prawo M jest--? 98 00:03:08,790 --> 00:03:09,110 Zaczęliśmy with-- 99 00:03:09,110 --> 00:03:10,090 >> David J. MALAN: Tak. 100 00:03:10,090 --> 00:03:10,650 Oni zostawili. 101 00:03:10,650 --> 00:03:11,430 Masz rację. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Tak. 103 00:03:11,710 --> 00:03:13,126 >> David J. MALAN: Więc Mike tutaj. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Co? 105 00:03:13,990 --> 00:03:14,665 >> [LAUGHING] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Zły przykład, chłopaki. 108 00:03:18,330 --> 00:03:18,830 Przepraszam. 109 00:03:18,830 --> 00:03:21,610 David J. MALAN: To nauczy można skakać z krzesła. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Och. 111 00:03:22,318 --> 00:03:22,890 Och. 112 00:03:22,890 --> 00:03:23,390 Mam cię. 113 00:03:23,390 --> 00:03:24,670 Mam cię. 114 00:03:24,670 --> 00:03:25,170 Och. 115 00:03:25,170 --> 00:03:25,669 Och. 116 00:03:25,669 --> 00:03:26,812 To jest-- OK, mam ciebie. 117 00:03:26,812 --> 00:03:27,520 Smith tutaj? 118 00:03:27,520 --> 00:03:28,894 >> David J. MALAN: Smith, dziękuję. 119 00:03:28,894 --> 00:03:30,535 Więc będę patrząc Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: O, tak. 121 00:03:30,790 --> 00:03:31,340 Nie nie nie. 122 00:03:31,340 --> 00:03:31,600 O nie. 123 00:03:31,600 --> 00:03:31,940 To jest moje. 124 00:03:31,940 --> 00:03:32,580 >> David J. MALAN: Och, masz Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Tak, ale Smith tutaj. 127 00:03:34,040 --> 00:03:34,700 Przepraszam chłopaki. 128 00:03:34,700 --> 00:03:35,860 Myślałem Michael-- mamy szukaliśmy Michała. 129 00:03:35,860 --> 00:03:36,550 Przepraszam. 130 00:03:36,550 --> 00:03:37,550 >> David J. MALAN: Jest OK. 131 00:03:37,550 --> 00:03:39,950 Dobra, teraz jesteśmy w Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini i synowie. 133 00:03:41,242 --> 00:03:43,158 David J. MALAN: Tylko ty i ja w to. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Znajdź nas Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> David J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Jesteśmy w R na śmieci. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Javascript. 141 00:03:48,644 --> 00:03:50,096 Och. 142 00:03:50,096 --> 00:03:52,480 To zajmie trochę czasu. 143 00:03:52,480 --> 00:03:54,340 >> [LAUGHING] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 David J. MALAN: Buty. 146 00:03:56,720 --> 00:03:58,080 Jesteśmy w butach. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Teraz jesteśmy gonna-- 148 00:04:00,210 --> 00:04:01,105 >> David J. MALAN: Nicea. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [LAUGHING] 151 00:04:03,620 --> 00:04:05,440 Och, to jest świetne. 152 00:04:05,440 --> 00:04:06,910 [LAUGHING] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> David J. MALAN: Jest OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Och, to jest dobre. 156 00:04:11,365 --> 00:04:14,425 Nie sądzę, że będę mają PSAT kumpli po tym. 157 00:04:14,425 --> 00:04:15,300 David J. MALAN: Dobra. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 David J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Warto więc oderwać to w połowie. 163 00:04:21,600 --> 00:04:22,270 Jest ok. 164 00:04:22,270 --> 00:04:25,606 To i tak kończy się źle, ponieważ Mike Smith nie będzie na żółtych stronach. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> David J. MALAN: Nie, to jest OK. 167 00:04:27,140 --> 00:04:28,930 Ale niech udawać, on jest na tej stronie. 168 00:04:28,930 --> 00:04:33,260 Więc teraz, już stopniała problem dół z jednej strony, a okazało się, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Doping] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Ok dziękuję. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 To było niezwykłe. 175 00:04:43,646 --> 00:04:45,954 Ale to było jeszcze szybciej niż wyszukiwania liniowego, 176 00:04:45,954 --> 00:04:47,870 w którym możemy rozpocząć się początku książki, 177 00:04:47,870 --> 00:04:51,210 i ruszamy naszą drogę od lewej do prawej, w końcu szuka Mike Smith. 178 00:04:51,210 --> 00:04:53,540 I tak, jeśli książka telefoniczna miał może z 1000 stron, 179 00:04:53,540 --> 00:04:56,300 Może zajęłoby nas 10 lub tak strona łzy. 180 00:04:56,300 --> 00:04:59,380 >> Ale może masz dźwignią dotknął założenie 181 00:04:59,380 --> 00:05:03,602 Podczas tego wszystkiego, to znaczy że książka telefoniczna z góry było, co? 182 00:05:03,602 --> 00:05:04,310 PUBLICZNOŚCI: Sortowanie. 183 00:05:04,310 --> 00:05:05,000 David J. MALAN: To jest klasyfikowane. 184 00:05:05,000 --> 00:05:05,160 Dobrze? 185 00:05:05,160 --> 00:05:07,909 To sortowane alfabetycznie, więc że wszystkie z tych nazw i numerów 186 00:05:07,909 --> 00:05:11,230 są klasyfikowane od A do danego Z, a alfabetycznie pomiędzy. 187 00:05:11,230 --> 00:05:13,100 Ale dzisiaj, teraz zapytać pytanie, dobrze, 188 00:05:13,100 --> 00:05:16,170 Jak Verizon lub telefon Firma dostać go w tym stanie? 189 00:05:16,170 --> 00:05:19,560 >> Bo to jest jedna rzecz, aby wykorzystać to założenie, a zatem, 190 00:05:19,560 --> 00:05:22,570 rozwiązać problem z Algorytm bardziej efektywnie. 191 00:05:22,570 --> 00:05:24,900 Ale nigdy tak naprawdę zapytał w tygodniu zerowym, dobrze, 192 00:05:24,900 --> 00:05:27,790 ile to kosztowało Verizon lub ktoś inny 193 00:05:27,790 --> 00:05:29,620 aby dostać tę książkę telefoniczną w uporządkowanej kolejności? 194 00:05:29,620 --> 00:05:29,780 >> Dobrze? 195 00:05:29,780 --> 00:05:31,529 To nie ma znaczenia, czy patrząc Mike Smith 196 00:05:31,529 --> 00:05:35,190 jest super szybki, jeśli to ma się do rok do sortowania stron początkowo. 197 00:05:35,190 --> 00:05:35,690 Dobrze? 198 00:05:35,690 --> 00:05:38,620 Równie dobrze można po prostu przesiać przez randomizowanym książce telefonicznej, 199 00:05:38,620 --> 00:05:40,690 jeśli to będzie bardzo drogie, aby je rozwiązać. 200 00:05:40,690 --> 00:05:42,350 Więc, jeśli możemy mieć inny wolontariusz. 201 00:05:42,350 --> 00:05:46,350 Przyjrzyjmy się patrzeć tutaj w jak might-- przychodzimy na up-- jak 202 00:05:46,350 --> 00:05:48,100 Może pójdziemy na temat sortowania tych. 203 00:05:48,100 --> 00:05:51,990 >> A jeśli Jordan mógł rzeczywiście dołącz do nas tu na scenie. 204 00:05:51,990 --> 00:05:55,100 Chodź na chwilę. 205 00:05:55,100 --> 00:05:56,359 Jak masz na imię? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 David J. MALAN: Caroline, chodź na górę. 208 00:05:58,691 --> 00:06:02,070 I będziesz dołączył przeze mnie i Jordanii tutaj. 209 00:06:02,070 --> 00:06:03,800 Caroline, dziękuję. 210 00:06:03,800 --> 00:06:04,300 W porządku. 211 00:06:04,300 --> 00:06:08,330 Tak więc to, co mamy tutaj Caroline jest 26 niebieskie książki 212 00:06:08,330 --> 00:06:10,747 że FAS używa do zarządzania niektóre egzaminy końcowe. 213 00:06:10,747 --> 00:06:13,330 Są one coraz trudne do znalezienia, ale to, co zrobiliśmy z góry 214 00:06:13,330 --> 00:06:15,800 jest to, że umieściliśmy czyjeś imię z przodu każdego z nich, 215 00:06:15,800 --> 00:06:18,133 ale trzymałem to proste przez potem gasił pełne nazwy. 216 00:06:18,133 --> 00:06:22,720 Więc chcemy umieścić osobę z nazwą L, D, J, B, całą drogę od A do Z, 217 00:06:22,720 --> 00:06:24,090 ale są w przypadkowej kolejności. 218 00:06:24,090 --> 00:06:26,890 I tak, jeśli będzie, mówi swojej drogę problemu jak ty 219 00:06:26,890 --> 00:06:31,620 zrób to można iść do przodu i posortować je dla nas, od A do Z. 220 00:06:31,620 --> 00:06:34,070 >> PUBLICZNOŚCI: OK, więc jest jak L, środkowy. 221 00:06:34,070 --> 00:06:35,050 C zaczyna. 222 00:06:35,050 --> 00:06:42,410 B. J przed L. B, P. 223 00:06:42,410 --> 00:06:45,140 >> David J. MALAN: Trzymaj, że że na jedną sekundę. 224 00:06:45,140 --> 00:06:48,910 W przeciwnym razie, to jest dopiero interesujące dla ciebie, mnie i Jordanii. 225 00:06:48,910 --> 00:06:49,724 No to jedziemy. 226 00:06:49,724 --> 00:06:50,640 PUBLICZNOŚCI: [niesłyszalne]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 David J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 Co ty robisz? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M przychodzi po O. 231 00:07:01,730 --> 00:07:02,564 >> David J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 David J. MALAN: O, dobrze. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> David J. MALAN: E, F. Tak. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> David J. MALAN: V, T, U, V, więc Wygląda na to, że jesteś making-- dalej. 238 00:07:10,689 --> 00:07:12,730 Wygląda na to, że robisz wielki stos tutaj, 239 00:07:12,730 --> 00:07:13,910 i niby wielki stos tam. 240 00:07:13,910 --> 00:07:16,230 Tak więc pierwsza połowa alfabetu, Druga połowa alfabetu. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Dobry. 243 00:07:16,960 --> 00:07:19,680 Rodzaj podziału problemu na dwa. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Tak. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 David J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Więc rodzaj wyboru je jeden po drugim, 248 00:07:25,070 --> 00:07:27,620 wprowadzenie go z lewej lub prawej, lub Z, dzieje się na podłodze. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z dzieje się na podłodze. 251 00:07:29,190 --> 00:07:29,360 >> David J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Tak dzieje się na podłodze. 253 00:07:30,920 --> 00:07:31,735 Teraz możemy umieścić X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 David J. MALAN: będzie lewo G. 256 00:07:33,700 --> 00:07:36,017 S będzie dobrze. 257 00:07:36,017 --> 00:07:37,642 Wszystko w porządku, A będzie całą drogę w lewo. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> David J. MALAN: Teraz dobrze. 260 00:07:39,873 --> 00:07:43,260 Mamy A, B, C. W dzieje tam na dole. 261 00:07:43,260 --> 00:07:45,566 Dobrze, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J 263 00:07:46,611 --> 00:07:47,860 David J. MALAN: H, I, J Dobra. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: W centrum, jestem gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Więc teraz, będziemy rodzaju od połączyć te różne stosy. 267 00:07:52,375 --> 00:08:00,730 Więc od A do C, to widzę, D, E i F i G i H oraz I. Nicea. 268 00:08:00,730 --> 00:08:05,540 J, K. A potem, to stos jest do góry nogami, ale to jest OK. 269 00:08:05,540 --> 00:08:06,040 Pewnie. 270 00:08:06,040 --> 00:08:07,240 Możemy wyciąć niektóre zakątki. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 A potem musimy W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Tak. 274 00:08:11,250 --> 00:08:11,880 >> David J. MALAN: Excellent. 275 00:08:11,880 --> 00:08:14,122 Więc wielkie dziękuję Caroline do sortowania tych. 276 00:08:14,122 --> 00:08:15,030 >> [Doping] 277 00:08:15,030 --> 00:08:17,287 >> Dziękuję. 278 00:08:17,287 --> 00:08:18,120 Dziękuję Ci bardzo. 279 00:08:18,120 --> 00:08:22,910 A teraz spójrzmy na chwilę jak Caroline chodził, czyniąc to, 280 00:08:22,910 --> 00:08:26,040 i co dokładnie mamy byli w stanie to-- jak 281 00:08:26,040 --> 00:08:28,409 udało się rozwiązać ten Problem, gdy byliśmy po prostu 282 00:08:28,409 --> 00:08:29,950 podana cała masa przypadkowych wejść. 283 00:08:29,950 --> 00:08:31,610 >> Cóż, wygląda na to, że był nieco systemu tam? 284 00:08:31,610 --> 00:08:32,110 Dobrze. 285 00:08:32,110 --> 00:08:34,495 Więc wcześniejszych listów w alfabecie, ona 286 00:08:34,495 --> 00:08:37,120 było wprowadzenie na lewo, a później litery alfabetu, 287 00:08:37,120 --> 00:08:38,270 ona wprowadzenie do prawa. 288 00:08:38,270 --> 00:08:40,500 I jak tylko znalazła niektóre bliższe litery, ones 289 00:08:40,500 --> 00:08:43,124 że go tuż obok siebie, ona umieścić te w porządku. 290 00:08:43,124 --> 00:08:46,750 A więc my niby miał to małe stosy segregowanych wejść występujących. 291 00:08:46,750 --> 00:08:50,540 >> A więc to jest zupełnie jak co większość z nas ludzi zrobi. 292 00:08:50,540 --> 00:08:53,530 Chcemy rodzaj przesiać przez niego, a my rodzaju posiadają mechanizm. 293 00:08:53,530 --> 00:08:56,930 Ale może to być trudne do napisania to w formule per se. 294 00:08:56,930 --> 00:08:59,010 Czułem się trochę bardziej ekologiczne niż. 295 00:08:59,010 --> 00:09:02,560 Zobaczmy więc, czy możemy teraz związany problem z mniejszą ilością wejść. 296 00:09:02,560 --> 00:09:05,170 >> Zamiast 26, niech zrobić coś o wiele mniej 297 00:09:05,170 --> 00:09:09,890 z tylko powiedzieć, siedem, za te drzwi, że tak powiem. 298 00:09:09,890 --> 00:09:11,300 Czy istnieje tylko siedem numery? 299 00:09:11,300 --> 00:09:15,240 A jeśli celem teraz w ręka jest znaleźć wartość, 300 00:09:15,240 --> 00:09:17,850 Zobaczmy, jak skutecznie możemy za to zabrać. 301 00:09:17,850 --> 00:09:22,460 I zobaczymy, czy możemy teraz zaczyna się stosować kilka liczb, 302 00:09:22,460 --> 00:09:26,310 lub niektóre formuły, z którym do opisania efektywność naszej książki telefonicznej 303 00:09:26,310 --> 00:09:31,060 Algorytm, nasz algorytm egzamin książka, i Bardziej ogólnie, wyszukiwania informacji. 304 00:09:31,060 --> 00:09:34,770 >> Więc na to, pozwól mi iść do przodu, a na ekranie dotykowym tutaj, 305 00:09:34,770 --> 00:09:41,100 umieścić na przeglądarkę internetową, która ma dokładnie te siedem drzwi. 306 00:09:41,100 --> 00:09:46,670 A jeśli możemy dostać jeszcze jeden dobrowolnie chodź tutaj, 307 00:09:46,670 --> 00:09:48,480 Mam umieścić te same drzwi tutaj. 308 00:09:48,480 --> 00:09:49,170 Szybkie wolontariuszy. 309 00:09:49,170 --> 00:09:51,130 >> Ten jedno- dema będą na szybsze i szybsze teraz. 310 00:09:51,130 --> 00:09:51,600 Zejdź na dół. 311 00:09:51,600 --> 00:09:52,308 Jak masz na imię? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> David J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Dobrze, Trevor, chodź na dół. 315 00:09:55,770 --> 00:09:59,212 Więc Trevor zgłosił się na ochotnika, żeby zrobić podobny problem, ale taki, który jest 316 00:09:59,212 --> 00:10:02,170 węższy zakres, i to się dzieje aby umożliwić nam spróbować sformalizować teraz 317 00:10:02,170 --> 00:10:03,970 proces sortowania tych numerów. 318 00:10:03,970 --> 00:10:05,500 >> Więc Trevor, miło cię poznać. 319 00:10:05,500 --> 00:10:08,720 Więc tutaj jest tablicą, więc do mówić, listę siedmiu drzwi. 320 00:10:08,720 --> 00:10:10,327 Śmiało i znaleźć nam numer 50. 321 00:10:10,327 --> 00:10:12,410 A następnie po fakcie, powiedz nam jak znalazł. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Powinno być: wszystko w porządku. 324 00:10:20,040 --> 00:10:21,945 Tak, to jest ten jeden tutaj? 325 00:10:21,945 --> 00:10:24,680 O o. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Kliknąłeś tego. 328 00:10:26,680 --> 00:10:28,690 Dobry. 329 00:10:28,690 --> 00:10:29,780 >> I dobrze. 330 00:10:29,780 --> 00:10:30,970 Teraz kliknięciu tego. 331 00:10:30,970 --> 00:10:34,060 I pozwól mi dać mikrofon, tak, że masz go za chwilę. 332 00:10:34,060 --> 00:10:37,000 Śmiało i kliknij obok, którzy zamierzają. 333 00:10:37,000 --> 00:10:39,812 Tak dobrze. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Czy mogę unclick drzwi? 335 00:10:41,020 --> 00:10:42,620 David J. MALAN: Nie, nie możesz usunąć zaznaczenie. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Ten. 338 00:10:43,974 --> 00:10:45,640 David J. MALAN: Gdzie chcesz iść? 339 00:10:45,640 --> 00:10:46,410 Który? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: To jedno. 341 00:10:47,230 --> 00:10:48,042 >> David J. MALAN: Nie 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Ten. 344 00:10:48,735 --> 00:10:49,020 >> David J. MALAN: Tak. 345 00:10:49,020 --> 00:10:49,700 To było dobre. 346 00:10:49,700 --> 00:10:50,380 W porządku. 347 00:10:50,380 --> 00:10:53,900 Więc jaki był twój algorytm lub Procedura robi to, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Właśnie przeszedł drzwi, aż znalazłem 50. 349 00:10:56,149 --> 00:10:56,940 David J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Doskonały algorytm. 351 00:10:58,150 --> 00:10:59,540 Tak to jest w porządku. 352 00:10:59,540 --> 00:11:03,120 Bo w rzeczywistości, jeśli ujawnię, co jest za tymi dwoma innymi drzwiami, co 353 00:11:03,120 --> 00:11:06,954 Znajdziemy tutaj jest to, że mamy tylko wejście losowe. 354 00:11:06,954 --> 00:11:08,870 Tak to było w rzeczywistości, jak dobre, jak można dostać. 355 00:11:08,870 --> 00:11:12,509 I faktycznie, masz lepiej niż wyczerpująco przeszukując cały szereg, 356 00:11:12,509 --> 00:11:15,300 bo byłoby naprawdę pecha jeśli trafił numer 357 00:11:15,300 --> 00:11:16,604 50 w ostatniej drzwi. 358 00:11:16,604 --> 00:11:18,520 Ale co, jeśli zamiast dał ci założenie. 359 00:11:18,520 --> 00:11:20,630 Przypuśćmy, że jakby wszystkie drzwi te wokół, 360 00:11:20,630 --> 00:11:23,500 tak, że masz numery klasyfikowane ten czas, 361 00:11:23,500 --> 00:11:29,730 ale tym razem to faktycznie different-- ten czas, 362 00:11:29,730 --> 00:11:32,640 to faktycznie posortowane dla Ciebie. 363 00:11:32,640 --> 00:11:35,380 A teraz celem pod ręką jest trafienie numer 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> David J. MALAN: Co Twój algorytm będzie? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Cóż, jeśli to klasyfikowane, to albo będzie 367 00:11:39,628 --> 00:11:42,710 aby być: jeśli największym na największym, malejąco, to będzie pierwszy, 368 00:11:42,710 --> 00:11:44,751 lub jeśli jest odwrotnie, to będzie ostatni. 369 00:11:44,751 --> 00:11:48,897 Więc ja po prostu wybierz te drzwi, a a potem po prostu dotknij ostatnie drzwi. 370 00:11:48,897 --> 00:11:49,980 David J. MALAN: Excellent. 371 00:11:49,980 --> 00:11:50,270 W porządku. 372 00:11:50,270 --> 00:11:51,150 Tak więc okazało się, że numer 50. 373 00:11:51,150 --> 00:11:52,970 Więc jak tylko wiedział, były sortowane, my 374 00:11:52,970 --> 00:11:55,040 były w stanie wykorzystać to założenie. 375 00:11:55,040 --> 00:11:57,040 Tak więc są one zbyt podobne przykład książka telefoniczna. 376 00:11:57,040 --> 00:11:59,540 Jak tylko masz, nawet z mały problem w ten sposób, 377 00:11:59,540 --> 00:12:02,380 Twoje wejścia wstępnie posortowane, możemy rzeczywiście znaleźć wartość zapewne 378 00:12:02,380 --> 00:12:03,130 bardziej efektywnie. 379 00:12:03,130 --> 00:12:05,800 >> I nie powiedzieć, czy to było klasyfikowane małych do dużych lub dużych do małych, 380 00:12:05,800 --> 00:12:08,080 i tak było bardzo rozsądne rozpocząć się na jednym końcu i drugi 381 00:12:08,080 --> 00:12:09,750 faktycznie okaże się, że wartość docelową. 382 00:12:09,750 --> 00:12:11,400 Więc dziękujemy Trevor również. 383 00:12:11,400 --> 00:12:13,260 A ja propose-- ładnie wykonane. 384 00:12:13,260 --> 00:12:16,960 Mamy trochę klip, w rzeczywistości, że jest jednym z naszych ulubionych momentów w CS50, 385 00:12:16,960 --> 00:12:19,700 przy czym czasami te dema Nie bardzo idzie zgodnie z planem. 386 00:12:19,700 --> 00:12:22,050 I rzeczywiście, w tej chwili, ja zatrzymał się w niewłaściwy interfejs 387 00:12:22,050 --> 00:12:23,508 z którym do korzystania z ekranu dotykowego. 388 00:12:23,508 --> 00:12:24,660 Więc to nie była moja wina. 389 00:12:24,660 --> 00:12:26,600 >> Więc to będzie dla przyszłoroczny klip jako 390 00:12:26,600 --> 00:12:28,570 dlaczego ja na moim ekranie było kliknięcie. 391 00:12:28,570 --> 00:12:31,390 Ale rzućmy okiem na to, co się stało w zeszłym roku 392 00:12:31,390 --> 00:12:34,770 z Jay, który przyszedł się, dużo jak Trevor tutaj, na ochotnika, 393 00:12:34,770 --> 00:12:39,380 iw tym krótkim klipie, zobaczysz jak to samo demo nie dość 394 00:12:39,380 --> 00:12:41,074 ujawnienia tych samych doświadczeń. 395 00:12:41,074 --> 00:12:41,740 [ODTWARZANIE] 396 00:12:41,740 --> 00:12:45,360 -Wszystkie Chcę, żebyś teraz zrobić, to znaleźć dla mnie, i dla nas, 397 00:12:45,360 --> 00:12:51,674 Naprawdę, numer 50 krok po kroku. 398 00:12:51,674 --> 00:12:52,450 >> -The Liczba 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Numer 50. 400 00:12:53,190 --> 00:12:55,356 I można ujawnić, co jest Za każdym z tych drzwi 401 00:12:55,356 --> 00:12:58,540 po prostu przez dotknięcie palcem. 402 00:12:58,540 --> 00:13:00,910 Cholera. 403 00:13:00,910 --> 00:13:02,870 >> [LAUGHING] 404 00:13:02,870 --> 00:13:03,806 >> [Zakończyć odtwarzanie] 405 00:13:03,806 --> 00:13:05,430 David J. MALAN: Tak, że poszło bardzo dobrze. 406 00:13:05,430 --> 00:13:06,796 To były nieposortowane drzwi. 407 00:13:06,796 --> 00:13:08,670 I Jay, oczywiście, znaleźć to wszystko zbyt szybko. 408 00:13:08,670 --> 00:13:12,910 Trevor zrobił o wiele lepiej w kategoriach teachable chwili 409 00:13:12,910 --> 00:13:15,850 że tak powiem, w tym roku w trwa dłużej, aby go znaleźć. 410 00:13:15,850 --> 00:13:17,950 Oczywiście, to daliśmy Jay drugą szansę, 411 00:13:17,950 --> 00:13:20,320 w którym możemy klasyfikowane drzwi, tak jak zrobiliśmy to dla Trevor, 412 00:13:20,320 --> 00:13:22,300 i Trevor zrobił bardzo dobrze ten czas. 413 00:13:22,300 --> 00:13:26,124 Ale Jay zrobił to w połowie tak szybko. 414 00:13:26,124 --> 00:13:26,790 [ODTWARZANIE] 415 00:13:26,790 --> 00:13:29,650 -The Celem jest teraz również znaleźć nam numer 50, 416 00:13:29,650 --> 00:13:33,030 ale zrobić algorytmicznie, i Powiedz nam, jaki masz zamiar o tym. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -A Jeśli go znaleźć, zachować ten film. 419 00:13:35,604 --> 00:13:37,228 Jeśli nie znajdziesz, możesz go oddać. 420 00:13:37,228 --> 00:13:38,044 >> -Człowiek. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Niesłyszalne] OK. 423 00:13:40,800 --> 00:13:46,236 Więc mam zamiar sprawdzić końce Pierwszy celu określenia, czy there's-- OH. 424 00:13:46,236 --> 00:13:48,646 >> [APPLAUSE] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [Zakończyć odtwarzanie] 427 00:13:55,729 --> 00:13:56,520 David J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Więc sortowania drzwi wyraźnie prowadzi do większej wydajności. 429 00:13:59,760 --> 00:14:01,680 I tak dwa razy szybciej to miałem na myśli nie. 430 00:14:01,680 --> 00:14:03,270 I tak miał szczęście Jay zarówno razy. 431 00:14:03,270 --> 00:14:06,685 I on też ma szczęście, że w ubiegłym roku, zamówiłem kilka płyt Blu-ray 432 00:14:06,685 --> 00:14:07,560 faktycznie dać się. 433 00:14:07,560 --> 00:14:09,768 Przykro mi tym roku, nie miało to samo, Trevor. 434 00:14:09,768 --> 00:14:11,540 Ale jeszcze lepiej było kilka lat temu. 435 00:14:11,540 --> 00:14:14,820 A niektórzy z was wiedzą o tym kolega, Sean, który gdy był w CS50, 436 00:14:14,820 --> 00:14:17,780 została zakwestionowana z dokładną sam problem, choć w SD, 437 00:14:17,780 --> 00:14:19,360 a szybko przekonasz się, z powrotem w dzień. 438 00:14:19,360 --> 00:14:22,622 A przekonasz się, że nie tylko on nieco dłużej niż Jay, 439 00:14:22,622 --> 00:14:25,580 trochę dłużej niż Trevor, był właściwie to wspaniała okazja 440 00:14:25,580 --> 00:14:29,820 angażować się niemal wszyscy w Tłum a la Price is Right, zachęcanie 441 00:14:29,820 --> 00:14:31,889 żeby znaleźć numer szukaliśmy. 442 00:14:31,889 --> 00:14:32,930 Miejmy. rzucić okiem. 443 00:14:32,930 --> 00:14:33,320 >> [ODTWARZANIE] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Tak więc twoim zadaniem tutaj, Sean jest następujący. 446 00:14:36,680 --> 00:14:40,860 Ukryłem się za nich Drzwi numer siedem. 447 00:14:40,860 --> 00:14:45,120 Ale schowany w niektórych z tych drzwi jak również są inne liczby ujemne. 448 00:14:45,120 --> 00:14:47,500 A twoim celem jest, że z tym górnym rzędzie cyfr 449 00:14:47,500 --> 00:14:50,390 jak tylko tablicę, lub po prostu Sekwencja kawałków papieru 450 00:14:50,390 --> 00:14:51,510 z numerami za nimi. 451 00:14:51,510 --> 00:14:55,540 I twoim celem jest, tylko przy użyciu górę Tablica tu znaleźć mi numer siedem. 452 00:14:55,540 --> 00:14:58,570 A my wtedy będziemy krytykować jak go o to robi. 453 00:14:58,570 --> 00:14:59,070 -W porządku. 454 00:14:59,070 --> 00:15:00,850 -Find Nam numer siedem, proszę. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nie. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Pięć, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [LAUGHING] 461 00:15:24,770 --> 00:15:25,910 >> To nie jest podchwytliwe pytanie. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Jeden. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [LAUGHING] 466 00:15:34,695 --> 00:15:37,861 W tym momencie, Twój wynik nie jest bardzo dobre, więc równie dobrze można iść dalej. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Trzy. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [LAUGHING] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Iść. 473 00:15:47,774 --> 00:15:50,690 Szczerze mówiąc, nie mogę pomóc, ale zastanawiam się, to, czego nawet nie myśląc o, SO- 474 00:15:50,690 --> 00:15:51,959 >> [LAUGHING] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Tylko górny rząd, więc masz trzy lewo. 477 00:15:55,020 --> 00:15:56,200 Więc znajdź mi siedem. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [LAUGHING] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Siedem. 484 00:16:26,946 --> 00:16:28,780 >> [APPLAUSE] 485 00:16:28,780 --> 00:16:29,426 >> W porządku. 486 00:16:29,426 --> 00:16:30,360 >> [Zakończyć odtwarzanie] 487 00:16:30,360 --> 00:16:31,840 >> David J. MALAN: Więc mogliśmy oglądać je przez cały dzień. 488 00:16:31,840 --> 00:16:34,090 Oczywiście, niektóre z tegoroczne pokazy być może 489 00:16:34,090 --> 00:16:36,330 będzie teraz kończy się w przyszłym Tegoroczny wideo, jak również. 490 00:16:36,330 --> 00:16:39,040 Więc teraz niech rzeczywiście skupić się na algorytmach 491 00:16:39,040 --> 00:16:42,140 tu, i zobacz, czy nie możemy teraz zaczynają sformalizować 492 00:16:42,140 --> 00:16:46,650 jak możemy go o uzyskanie nasze dane w takim stanie, że to jest klasyfikowane, 493 00:16:46,650 --> 00:16:50,054 sposób, że ostatecznie możemy rzeczywiście szukaj go bardziej efektywnie. 494 00:16:50,054 --> 00:16:52,470 I mimo, że mamy zamiar używać dość małych zbiorów danych, 495 00:16:52,470 --> 00:16:54,511 jak my osiem numerów mam tu na pokładzie, 496 00:16:54,511 --> 00:16:58,230 w rezultacie mogą stosować te same pomysły 1000 wejść, milion wejść, 497 00:16:58,230 --> 00:17:02,100 4 mld wejścia, ponieważ algorytmy będą zasadniczo takie same. 498 00:17:02,100 --> 00:17:05,359 >> I tak to jest nasz ostatni szansa dla wolontariuszy dzisiaj 499 00:17:05,359 --> 00:17:09,790 ale chyba najbardziej zaangażowany jeden, dla których musimy ośmiu wolontariuszy 500 00:17:09,790 --> 00:17:12,960 wymyślić i chodź z nami poprzez Proces sortowania, co wkrótce 501 00:17:12,960 --> 00:17:15,212 być na tych muzyki tutaj stoi. 502 00:17:15,212 --> 00:17:16,170 Zacznę tutaj. 503 00:17:16,170 --> 00:17:19,692 >> Więc jeden w turquoise-- zielony to jest? 504 00:17:19,692 --> 00:17:21,130 Czy popełnienie? 505 00:17:21,130 --> 00:17:21,630 Dwa. 506 00:17:21,630 --> 00:17:23,069 Zejdź na dół. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Trzy. 509 00:17:24,420 --> 00:17:25,400 Cztery. 510 00:17:25,400 --> 00:17:27,247 Niech me-- OK, pięć. 511 00:17:27,247 --> 00:17:28,830 Jesteś jest nominowany przez znajomego. 512 00:17:28,830 --> 00:17:31,340 Sześć, siedem, osiem. 513 00:17:31,340 --> 00:17:32,130 Chodź na górę. 514 00:17:32,130 --> 00:17:32,630 W porządku. 515 00:17:32,630 --> 00:17:33,190 Dziękuję bardzo. 516 00:17:33,190 --> 00:17:33,689 Chodź na górę. 517 00:17:33,689 --> 00:17:34,790 Chodź na górę. 518 00:17:34,790 --> 00:17:35,330 >> W porządku. 519 00:17:35,330 --> 00:17:38,890 Więc co mamy here-- i to jest jednym z bardziej kłopotliwych tych, 520 00:17:38,890 --> 00:17:42,390 od tego, że konieczna będzie humor mi na tylko trochę czasu. 521 00:17:42,390 --> 00:17:43,442 Powinien być numerem jeden. 522 00:17:43,442 --> 00:17:44,150 Jak masz na imię? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> David J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Jak masz na imię? 527 00:17:46,800 --> 00:17:47,140 >> Joseph Joseph. 528 00:17:47,140 --> 00:17:49,190 >> David J. MALAN: Józef, jesteś numer dwa. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, numer trzy. 530 00:17:52,260 --> 00:17:53,722 Stefan, numer cztery. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 David J. MALAN: Cynthia, numer pięć. 533 00:17:57,548 --> 00:17:58,452 [Niesłyszalne] 534 00:17:58,452 --> 00:17:59,618 David J. MALAN: [niesłyszalne]. 535 00:17:59,618 --> 00:18:00,391 David, numer sześć. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 David J. MALAN: Matta numer siedem. 538 00:18:02,160 --> 00:18:02,850 I? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> David J. MALAN: Waverly, numer osiem. 541 00:18:04,470 --> 00:18:04,970 W porządku. 542 00:18:04,970 --> 00:18:06,510 Jeśli could-- okrzyki. 543 00:18:06,510 --> 00:18:08,820 Jeśli was wszystkich, jak twój Pierwszym wyzwaniem, nie 544 00:18:08,820 --> 00:18:10,820 osiem stoiska muzyczne tutaj twarzą do publiczności. 545 00:18:10,820 --> 00:18:14,200 Jeśli można umieścić swoje numery te pulpity w taki sposób, 546 00:18:14,200 --> 00:18:16,560 oni się tej linii z same numery na płycie. 547 00:18:16,560 --> 00:18:19,560 Więc upewnij się wyglądać przez oddanie numery na tych muzyki 548 00:18:19,560 --> 00:18:21,960 stoi tutaj. 549 00:18:21,960 --> 00:18:25,980 Doskonały do ​​tej pory. 550 00:18:25,980 --> 00:18:26,600 >> Doskonałe. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Więc teraz mamy zamiar zapytać pytanie w kilka różnych sposobów. 553 00:18:29,556 --> 00:18:31,610 Jak możemy go o sortowaniu ci ludzie tutaj? 554 00:18:31,610 --> 00:18:34,500 Ponieważ mieliśmy kilka podejść wcześniej, w którym byliśmy 555 00:18:34,500 --> 00:18:36,360 rodzaju co dwa różne wiadra. 556 00:18:36,360 --> 00:18:38,842 A potem były na ogół składając rzeczy razem. 557 00:18:38,842 --> 00:18:41,050 Jak tylko zobaczyłem dwa numery że należeli razem, 558 00:18:41,050 --> 00:18:41,975 możemy je połączyć. 559 00:18:41,975 --> 00:18:43,350 Dwa listy, które należą razem. 560 00:18:43,350 --> 00:18:45,058 >> Ale zobaczymy, czy możemy Nie można sformalizować to, 561 00:18:45,058 --> 00:18:48,044 tak, że w końcu mają niektóre pseudo-kod będzie, 562 00:18:48,044 --> 00:18:49,710 z którym można rozwiązać te problemy. 563 00:18:49,710 --> 00:18:51,870 Więc teraz szukam się na te numery tutaj. 564 00:18:51,870 --> 00:18:55,030 I widzę całą masę błędów. 565 00:18:55,030 --> 00:18:57,750 Docelowo chcę jeden na w lewo i osiem po prawej stronie. 566 00:18:57,750 --> 00:19:00,650 >> I tak patrzę na te dwa, cztery i dwa. 567 00:19:00,650 --> 00:19:02,930 A w czym problem, oczywiście? 568 00:19:02,930 --> 00:19:04,261 Tak. 569 00:19:04,261 --> 00:19:04,760 Więc. 570 00:19:04,760 --> 00:19:07,160 Dwa oczywiście jest przed cztery, więc wiesz co? 571 00:19:07,160 --> 00:19:10,210 Pozwól mi wziąć chciwy podejście, jeśli będzie, podobnie jak problem, 572 00:19:10,210 --> 00:19:13,790 ustawić jedno-, czy pamiętacie z Standard Edition problemu Set One, 573 00:19:13,790 --> 00:19:16,820 gdzie tylko lokalnie rozwiązać problem to właśnie tu, w moich oczach 574 00:19:16,820 --> 00:19:17,690 i zobaczyć, dokąd prowadzi mnie. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Więc dwa i cztery, pozwól mi odejść dalej i po prostu zamienić ci dwa. 577 00:19:20,161 --> 00:19:22,400 Jeśli można fizycznie przenieść Sami i twój papier, 578 00:19:22,400 --> 00:19:25,040 Wydaje mi się zdobyć listy w lepszym stanie. 579 00:19:25,040 --> 00:19:26,330 >> Teraz są one dobre. 580 00:19:26,330 --> 00:19:28,480 Mam zamiar przejść, cztery i sześć, wygląda dobrze. 581 00:19:28,480 --> 00:19:29,110 To nie problem. 582 00:19:29,110 --> 00:19:30,440 Sześć i osiem, OK. 583 00:19:30,440 --> 00:19:31,860 Osiem i inny problem. 584 00:19:31,860 --> 00:19:34,750 Bo to, co prawda, o ósmej i jeden? 585 00:19:34,750 --> 00:19:36,990 Jedna jest przed ośmiu, i tak to, co powinniśmy zrobić? 586 00:19:36,990 --> 00:19:38,090 Miejmy zamienić te dwa. 587 00:19:38,090 --> 00:19:39,316 Jeden i osiem. 588 00:19:39,316 --> 00:19:40,690 A teraz, mam zamiar iść dalej. 589 00:19:40,690 --> 00:19:42,030 Zamierzam zachować patrząc w przyszłość. 590 00:19:42,030 --> 00:19:42,840 I zobaczmy, co się stanie. 591 00:19:42,840 --> 00:19:44,680 Osiem i trzy, z Oczywiście, nie w porządku. 592 00:19:44,680 --> 00:19:45,815 Miejmy swapa. 593 00:19:45,815 --> 00:19:46,940 Osiem i siedem, oczywiście. 594 00:19:46,940 --> 00:19:47,481 Nieczynny. 595 00:19:47,481 --> 00:19:48,280 Miejmy swapa. 596 00:19:48,280 --> 00:19:49,940 Osiem i pięć, oczywiście, niech wymiany. 597 00:19:49,940 --> 00:19:50,560 W porządku. 598 00:19:50,560 --> 00:19:51,880 Lista jest posortowana. 599 00:19:51,880 --> 00:19:53,060 tak? 600 00:19:53,060 --> 00:19:54,280 >> OK, oczywiście nie. 601 00:19:54,280 --> 00:19:55,860 Ale to jest trochę lepiej, prawda? 602 00:19:55,860 --> 00:19:57,270 Ponieważ informacja, co się stało. 603 00:19:57,270 --> 00:20:01,749 Za każdym razem przeprowadziliśmy swap mniejszy Numer rodzaj perkolacji w ten sposób, 604 00:20:01,749 --> 00:20:03,790 i większa liczba perkolacji w ten sposób, albo będziesz 605 00:20:03,790 --> 00:20:06,880 rozpocząć powiedzenie przepuszcza do lewo lub w postaci pęcherzyków w prawo. 606 00:20:06,880 --> 00:20:10,080 >> Teraz, to nie wystarczy, bo w najlepszym wiele może 607 00:20:10,080 --> 00:20:11,990 zostały przeniesione jedno miejsce do przodu, lub co gorsza, 608 00:20:11,990 --> 00:20:13,880 liczba może mieć przeniósł się jedno miejsce dalej. 609 00:20:13,880 --> 00:20:16,369 Więc wiesz co, tego rodzaju od pracował bardzo dobrze do tej pory. 610 00:20:16,369 --> 00:20:17,410 Pozwól mi po prostu spróbować ponownie. 611 00:20:17,410 --> 00:20:18,880 Dwa i cztery, są OK. 612 00:20:18,880 --> 00:20:20,180 Cztery i sześć, są OK. 613 00:20:20,180 --> 00:20:21,790 Sześć i jeden, w porządku. 614 00:20:21,790 --> 00:20:23,007 Warto więc zamienić cię dwa. 615 00:20:23,007 --> 00:20:25,840 A teraz, zauważysz problem na zaczyna znów się trochę lepiej. 616 00:20:25,840 --> 00:20:27,006 Sześć i trzy, w porządku. 617 00:20:27,006 --> 00:20:28,100 Miejmy zamienić cię dwa. 618 00:20:28,100 --> 00:20:29,730 Sześć i siedem, jesteś dobry. 619 00:20:29,730 --> 00:20:32,230 Siedem i pięć, oczywiście, nie w porządku. 620 00:20:32,230 --> 00:20:33,920 Siedem i osiem, w porządku. 621 00:20:33,920 --> 00:20:36,470 A teraz, może muszę zrobić jeszcze kilka razy. 622 00:20:36,470 --> 00:20:39,830 A w rzeczywistości, myśleć za siebie być może, ile razy maksymalnie 623 00:20:39,830 --> 00:20:41,330 Mogę chodzić tam iz powrotem? 624 00:20:41,330 --> 00:20:42,390 >> Wrócimy do tego. 625 00:20:42,390 --> 00:20:43,700 Więc dwa i cztery są nadal OK. 626 00:20:43,700 --> 00:20:44,940 Cztery i jeden, nope. 627 00:20:44,940 --> 00:20:45,747 Tak, niech swapa. 628 00:20:45,747 --> 00:20:47,830 I znowu zauważyć wizualnie z nich jest rodzaj bulgotanie 629 00:20:47,830 --> 00:20:49,163 po lewej stronie, gdzie powinien być. 630 00:20:49,163 --> 00:20:50,010 Cztery i trzy wymiany. 631 00:20:50,010 --> 00:20:51,330 Cztery i sześć. 632 00:20:51,330 --> 00:20:53,100 Sześć i pięć wymiany. 633 00:20:53,100 --> 00:20:53,959 Sześć i siedem. 634 00:20:53,959 --> 00:20:55,000 Siedem i osiem są dobre. 635 00:20:55,000 --> 00:20:55,500 >> Dobry. 636 00:20:55,500 --> 00:20:58,460 Dostajemy nawet lepiej. 637 00:20:58,460 --> 00:20:59,130 Więc zobaczymy. 638 00:20:59,130 --> 00:21:00,940 Teraz mamy dwa do jednego. 639 00:21:00,940 --> 00:21:02,520 Oczywiście, zamienić. 640 00:21:02,520 --> 00:21:07,520 Dwa i trzy, trzy i cztery, cztery i pięć, sześć i siedem, siedem i osiem. 641 00:21:07,520 --> 00:21:08,020 Dobry. 642 00:21:08,020 --> 00:21:08,730 I wiesz co? 643 00:21:08,730 --> 00:21:11,190 Bo ja się nie jedną zmianę, pozwól mi zrobić jedną testow. 644 00:21:11,190 --> 00:21:13,023 Pozwól mi przejść całą drogę powrót do początku. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Jeden, two-- yup, widzisz? 647 00:21:14,750 --> 00:21:15,870 Coś było nie tak. 648 00:21:15,870 --> 00:21:18,420 Trzy, cztery, pięć, sześć, siedem, osiem. 649 00:21:18,420 --> 00:21:21,920 I w tym ostatnim przejściu, są komfortowe z moim teraz 650 00:21:21,920 --> 00:21:23,830 twierdząc, że jest posortowana? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Wizualnie jest to absolutnie prawdziwe. 653 00:21:25,880 --> 00:21:28,410 Ale funkcjonalnie, co czy też po prostu się stało 654 00:21:28,410 --> 00:21:31,870 w tym ostatnim przejściu, która pozwala aby potwierdzić, że ta lista jest rzeczywiście 655 00:21:31,870 --> 00:21:32,660 klasyfikowane? 656 00:21:32,660 --> 00:21:34,477 >> Co mam zrobić, czy nie zrobić tego ostatniego przepustkę? 657 00:21:34,477 --> 00:21:35,810 PUBLICZNOŚCI: Nie było żadnych zmian. 658 00:21:35,810 --> 00:21:36,120 David J. MALAN: Słucham? 659 00:21:36,120 --> 00:21:37,070 PUBLICZNOŚCI: Nie było żadnych zmian. 660 00:21:37,070 --> 00:21:38,653 David J. MALAN: Nie było żadnych zmian. 661 00:21:38,653 --> 00:21:41,947 Więc byłoby głupie z mojej strony zrobić tego samego algorytmu ponownie 662 00:21:41,947 --> 00:21:43,780 gdybym nie dokonywała zmienia się po raz pierwszy. 663 00:21:43,780 --> 00:21:45,160 A państwo nie zmienił. 664 00:21:45,160 --> 00:21:47,576 Na pewno nie zamierzam zrobić Wszelkie zmiany po raz drugi. 665 00:21:47,576 --> 00:21:49,820 I tak, to teraz jest bezpieczny powiedzieć, lista jest sortowana. 666 00:21:49,820 --> 00:21:52,069 >> I rzeczywiście, to jest teraz coś, czego będziesz ogólnie 667 00:21:52,069 --> 00:21:56,900 rozmowa sortowanie bąbelkowe, przy czym parami, ponownie poprawić błędy, 668 00:21:56,900 --> 00:22:00,210 i znowu, i znowu, i ci utrzymać się tam iz powrotem, 669 00:22:00,210 --> 00:22:03,370 oraz w przód iw tył, aż do ciebie aby nie takie swapy, w którym momencie 670 00:22:03,370 --> 00:22:07,089 można mieć pewność, tak, zakończeniu mocowania wszystkich błędów. 671 00:22:07,089 --> 00:22:08,630 Miejmy zresetować i spróbować innego podejścia. 672 00:22:08,630 --> 00:22:11,590 Jeśli wam się wrócić do kolejność byłeś przed chwilą, 673 00:22:11,590 --> 00:22:13,780 który wyglądał jak ten. 674 00:22:13,780 --> 00:22:17,640 Teraz weźmy zbliżyć się trochę jak książki do egzaminu, 675 00:22:17,640 --> 00:22:21,122 w którym byliśmy stale wybierając literę alfabetu 676 00:22:21,122 --> 00:22:22,830 że niby chciał do czynienia z następnym. 677 00:22:22,830 --> 00:22:26,420 Może to była duża litera, jak A, lub niskim litery Z. 678 00:22:26,420 --> 00:22:28,170 >> Tak więc każdy z powrotem w tej kolejności. 679 00:22:28,170 --> 00:22:29,800 A teraz pozwól mi to zrobić. 680 00:22:29,800 --> 00:22:34,880 Zobaczmy, wiem, że mam tutaj osiem numerów. 681 00:22:34,880 --> 00:22:37,410 Mam zamiar iść do przodu i po prostu świadomie wybrać 682 00:22:37,410 --> 00:22:38,520 najmniejszych elementów. 683 00:22:38,520 --> 00:22:38,760 Dobrze? 684 00:22:38,760 --> 00:22:39,801 To wydaje się zbyt intuicyjne. 685 00:22:39,801 --> 00:22:42,560 Dlaczego nie mogę znaleźć najmniejszą Element, umieścić go tam, gdzie należy, 686 00:22:42,560 --> 00:22:45,280 następnie dostać następną najmniejszy element, umieścić że tam, gdzie należy, i po prostu powtórzyć. 687 00:22:45,280 --> 00:22:46,820 >> Ponieważ intuicyjnie, który powinien działać też. 688 00:22:46,820 --> 00:22:48,441 Tak więc cztery, to jest dość mała liczba. 689 00:22:48,441 --> 00:22:49,940 Idę sobie przypomnieć, gdzie to jest. 690 00:22:49,940 --> 00:22:50,523 Poczekaj minutkę. 691 00:22:50,523 --> 00:22:51,577 Nimi jest mniejszy. 692 00:22:51,577 --> 00:22:53,910 Chciałbym teraz przypomnieć, gdzie dwa jest, i zapomnieć o cztery. 693 00:22:53,910 --> 00:22:55,050 Zajmiemy się tym później. 694 00:22:55,050 --> 00:22:56,460 Sześć, nie jestem zainteresowany. 695 00:22:56,460 --> 00:22:57,810 Osiem, nie jestem zainteresowany. 696 00:22:57,810 --> 00:22:59,780 Jednym z nich jest moja nowa mała liczba. 697 00:22:59,780 --> 00:23:01,470 Więc będę pamiętał, gdzie się jest. 698 00:23:01,470 --> 00:23:02,534 Trzy, nie interesuje. 699 00:23:02,534 --> 00:23:03,450 Siedem, nie interesuje. 700 00:23:03,450 --> 00:23:04,530 Pięć, nie interesuje. 701 00:23:04,530 --> 00:23:07,390 >> Więc nie spadając scena w tym roku, 702 00:23:07,390 --> 00:23:09,890 Mam zamiar chwycić liczby jedno- a co jeszcze było na imię? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> David J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 I jeśli można dołączyć do mnie na początek listy 706 00:23:13,540 --> 00:23:14,870 postawmy cię tam, gdzie twoje miejsce. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- jak masz na imię? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> David J. MALAN: Stefan jest w drodze. 710 00:23:18,191 --> 00:23:23,490 Więc zanim Stefan rozwiązuje ten problem Problem, co powinniśmy zrobić? 711 00:23:23,490 --> 00:23:25,412 Co robimy ze Stefanem? 712 00:23:25,412 --> 00:23:27,269 >> PUBLICZNOŚCI: [niesłyszalne]. 713 00:23:27,269 --> 00:23:28,060 David J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Więc możemy to zrobić. 715 00:23:28,850 --> 00:23:31,730 Mogliśmy jakby się Stefan i jego cztery, i po prostu umieścić ją w zmiennej 716 00:23:31,730 --> 00:23:33,530 i przytrzymaj go przez jakiś czas, 717 00:23:33,530 --> 00:23:35,220 a tym samym pokoju na numer jeden. 718 00:23:35,220 --> 00:23:36,280 I to nie jest źle. 719 00:23:36,280 --> 00:23:39,270 Mogę zasugerować, dlaczego nie po prostu umieścić tutaj Stefan? 720 00:23:39,270 --> 00:23:41,610 Dlaczego może to naruszyć jeden pomysłów zaczęliśmy 721 00:23:41,610 --> 00:23:44,830 mówi o ostatnim czasie, w zeszłym tygodniu? 722 00:23:44,830 --> 00:23:45,330 Tak? 723 00:23:45,330 --> 00:23:45,740 >> PUBLICZNOŚCI: [niesłyszalne]. 724 00:23:45,740 --> 00:23:46,860 >> David J. MALAN: Nie ma indeksu dla niego. 725 00:23:46,860 --> 00:23:49,735 Jeśli myślisz o tym, rzeczywiście, jako Tablica ta jest jak negatywny, 726 00:23:49,735 --> 00:23:52,900 więc nie ma pamięci w rzeczywistości tu, czy to jest rzeczywiście tablicą, 727 00:23:52,900 --> 00:23:55,090 jak to oświadczył w ubiegłym tygodniu w wykładzie. 728 00:23:55,090 --> 00:23:56,250 Tak więc nie powinniśmy tego robić. 729 00:23:56,250 --> 00:23:57,340 Możemy go przechowywać w zmiennej. 730 00:23:57,340 --> 00:23:57,820 >> Albo wiesz co? 731 00:23:57,820 --> 00:23:59,153 Słyszałem ktoś inny go sugerują. 732 00:23:59,153 --> 00:24:01,020 Co jeszcze możemy zrobić ze Stefanem? 733 00:24:01,020 --> 00:24:03,770 Dlaczego nie możemy po prostu wyrzucić go i umieścić go na których numer jeden był. 734 00:24:03,770 --> 00:24:05,170 Więc jeśli chcesz iść tam. 735 00:24:05,170 --> 00:24:07,300 I rzeczywiście, że jest to całkiem dobre rozwiązanie. 736 00:24:07,300 --> 00:24:10,480 Teraz z jednej strony, mam rodzaj Made problem gorzej. 737 00:24:10,480 --> 00:24:13,650 Cztery jest teraz dalej z którego powinno być. 738 00:24:13,650 --> 00:24:14,900 Powinien on być w kierunku tej połowy. 739 00:24:14,900 --> 00:24:16,100 >> Ale wiesz co? 740 00:24:16,100 --> 00:24:17,630 To mogło być pecha. 741 00:24:17,630 --> 00:24:18,822 Może numer osiem było. 742 00:24:18,822 --> 00:24:20,530 I tak, być może będzie zdobyć szczęście, 743 00:24:20,530 --> 00:24:22,460 i pchnął osiem bliżej końca. 744 00:24:22,460 --> 00:24:24,710 Tak więc na koniec dnia to niby wszystkie średnie out. 745 00:24:24,710 --> 00:24:26,085 Nie musimy się martwić o cztery. 746 00:24:26,085 --> 00:24:29,400 Wszystko zależy mi teraz jest wybraniu najmniejszy element. 747 00:24:29,400 --> 00:24:32,030 >> A teraz, co mam zamiar zrobić, to zapomnieć o numer jeden 748 00:24:32,030 --> 00:24:35,160 na stałe, ponieważ wiem, że Lista za mną jest teraz posortowana. 749 00:24:35,160 --> 00:24:36,720 Więc moja lista była wcześniej rozmiar osiem. 750 00:24:36,720 --> 00:24:37,720 Teraz to od wielkości siedem. 751 00:24:37,720 --> 00:24:40,340 Więc mój problem jest coraz mniejsze, chociaż liniowo. 752 00:24:40,340 --> 00:24:43,022 Więc teraz, mam zamiar wybrać prąd najmniejszy element, dwa. 753 00:24:43,022 --> 00:24:46,520 Sześć, osiem, cztery, trzy, siedem, pięć. 754 00:24:46,520 --> 00:24:47,770 To był najmniejszy element. 755 00:24:47,770 --> 00:24:49,416 Więc co mam zamiar zrobić with-- co znowu masz na imię? 756 00:24:49,416 --> 00:24:49,760 >> Joseph Joseph. 757 00:24:49,760 --> 00:24:50,085 >> David J. MALAN: Józef? 758 00:24:50,085 --> 00:24:52,000 Mamy zamiar opuścić Józefa w miejscu. 759 00:24:52,000 --> 00:24:54,842 Teraz mam zamiar udawać że ci faceci are-- dobrze, 760 00:24:54,842 --> 00:24:56,550 Wiem, że te dwa są już klasyfikowane. 761 00:24:56,550 --> 00:24:58,424 Skupmy się teraz na Pozostała część listy. 762 00:24:58,424 --> 00:25:00,080 Sześć jest obecny najmniejsza. 763 00:25:00,080 --> 00:25:01,190 Osiem jest większy. 764 00:25:01,190 --> 00:25:02,970 Cztery jest teraz obecny najmniejsza. 765 00:25:02,970 --> 00:25:04,762 Trzy jest teraz obecny najmniejsza. 766 00:25:04,762 --> 00:25:07,720 A więc teraz, mam zamiar wybrać trzy, którzy jest-- jak masz na imię jeszcze raz? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 David J. MALAN: Serena, jeśli można chwycić liczby i zamianę with-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 David J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Wracaj, a my jesteśmy zamiar zamienić te dwa. 772 00:25:15,220 --> 00:25:17,360 A teraz postawmy to na autopilota. 773 00:25:17,360 --> 00:25:21,589 Mam zamiar iść i pozostawić do was Aby wybrać następny najmniejsze elementy. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Numer cztery, co należy zrobić? 776 00:25:24,560 --> 00:25:26,261 Doskonałe. 777 00:25:26,261 --> 00:25:27,760 Teraz mam zamiar dokonać innego przepustkę. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Widzę pięć jest następna najmniejsza. 780 00:25:31,465 --> 00:25:32,840 Teraz mam zamiar podjąć kolejną przepustkę. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Sześć jest najmniejsza. 783 00:25:34,880 --> 00:25:35,520 Dobry. 784 00:25:35,520 --> 00:25:36,585 Siedem jest najmniejsza. 785 00:25:36,585 --> 00:25:37,085 Bez zmiany. 786 00:25:37,085 --> 00:25:38,630 Osiem jest najmniejsza. 787 00:25:38,630 --> 00:25:39,170 Gotowe. 788 00:25:39,170 --> 00:25:43,900 >> Więc co my właśnie zrobić poprzez iteracyjne wybranie jednego elementu po drugim 789 00:25:43,900 --> 00:25:47,230 jest zaimplementować coś, że jesteśmy zamierza sformalizować jak wybór rodzaju. 790 00:25:47,230 --> 00:25:49,120 I to jest być może nawet łatwiejsze do wyjaśnienia, 791 00:25:49,120 --> 00:25:51,310 na tym, że dosłownie wszystko co chcesz zrobić, to utrzymać 792 00:25:51,310 --> 00:25:54,700 tam iz powrotem po liście wybranie, następny najmniejszy element, 793 00:25:54,700 --> 00:25:55,720 dopóki nie skończysz. 794 00:25:55,720 --> 00:25:58,650 >> Więc jest to jeszcze prostsze, być może intuicyjnie, niż w ubiegłym. 795 00:25:58,650 --> 00:26:00,020 Spróbujmy jeden ostatni. 796 00:26:00,020 --> 00:26:03,060 Jeśli moglibyście sobie zresetować w następujących pozycjach 797 00:26:03,060 --> 00:26:08,600 po raz ostatni, zobaczmy, czy nie możemy teraz sformalizować jedno inne podejście. 798 00:26:08,600 --> 00:26:12,857 W rzeczywistości, by ktoś tam Proponujemy 799 00:26:12,857 --> 00:26:14,440 jak inaczej moglibyśmy za to zabrać? 800 00:26:14,440 --> 00:26:17,439 Bez rzucając się słowa-wytrychy lub rodzaju odpowiedzi, które są już znane, 801 00:26:17,439 --> 00:26:19,689 tylko intuicyjnie, co możemy zrobić? 802 00:26:19,689 --> 00:26:21,635 >> PUBLICZNOŚCI: [niesłyszalne]. 803 00:26:21,635 --> 00:26:22,510 David J. MALAN: Tak. 804 00:26:22,510 --> 00:26:24,620 Więc jest jakaś wielka intuicja nie. 805 00:26:24,620 --> 00:26:28,020 Dobre rzeczy wydają się zdarzyć tak daleko w informatyce, gdy dzielimy 806 00:26:28,020 --> 00:26:30,832 i podbić problemu podzielenie go na pół i pół na pół. 807 00:26:30,832 --> 00:26:32,540 I tak sądzimy, może zacząć to robić. 808 00:26:32,540 --> 00:26:35,754 A w rzeczywistości, że będzie, będziemy zobacz, jeden z naszych najlepszych rozwiązań jeszcze. 809 00:26:35,754 --> 00:26:37,420 Ale wróćmy do tego niebawem. 810 00:26:37,420 --> 00:26:40,500 W rzeczywistości, mamy zamiar zrobić że nieco później w tym tygodniu. 811 00:26:40,500 --> 00:26:42,180 Co jeszcze możemy zrobić, aby rozwiązać ten problem? 812 00:26:42,180 --> 00:26:44,647 Więc wszyscy tu jest Kolejność pozornie przypadkowe. 813 00:26:44,647 --> 00:26:45,230 Wiesz co? 814 00:26:45,230 --> 00:26:48,320 Zamiast iść tam iz powrotem, tam iz powrotem, tam iz powrotem 815 00:26:48,320 --> 00:26:50,624 za każdym razem, to czuje się jak Robię dużo chodzenia. 816 00:26:50,624 --> 00:26:52,790 Dlaczego nie mogę po prostu zaczynają się początek listy 817 00:26:52,790 --> 00:26:54,960 i po prostu umieścić cztery, gdzie należy? 818 00:26:54,960 --> 00:26:59,680 Więc pozwól mi założyć, na chwilę, że moja lista jest tylko ten pierwszy element. 819 00:26:59,680 --> 00:27:04,937 Czy cztery klasyfikowane w tej chwili w czasie, jeśli wszystko zależy mi na to wszystko, co tutaj? 820 00:27:04,937 --> 00:27:06,520 Jest to rodzaj trywialnie prawdziwe, prawda? 821 00:27:06,520 --> 00:27:10,000 Podobnie jak listy zawierającej jeden numer i że numer cztery jest oczywiście klasyfikowane. 822 00:27:10,000 --> 00:27:13,070 >> Więc pozwól mi tylko zastrzec, że ta lista jest posortowana. 823 00:27:13,070 --> 00:27:15,090 Ale teraz mam resztę tej listy. 824 00:27:15,090 --> 00:27:17,240 Więc teraz, spotykam dwa. 825 00:27:17,240 --> 00:27:21,690 Gdzie dwóch oczywiście należą w odniesieniu do czterech? 826 00:27:21,690 --> 00:27:22,580 Przed czterech. 827 00:27:22,580 --> 00:27:23,862 Więc co można zrobić tutaj? 828 00:27:23,862 --> 00:27:24,820 Jeszcze raz, jak masz na imię? 829 00:27:24,820 --> 00:27:25,090 >> Joseph Joseph. 830 00:27:25,090 --> 00:27:26,030 >> David J. MALAN: Józef, jeśli można cofnąć 831 00:27:26,030 --> 00:27:27,790 na chwilę ze swoim numerem. 832 00:27:27,790 --> 00:27:31,130 A teraz to, co powinno Stefan zrobić tutaj? 833 00:27:31,130 --> 00:27:33,720 Miejmy przesunąć Stefan tutaj. 834 00:27:33,720 --> 00:27:35,520 A teraz, niech Józef tu przyjść. 835 00:27:35,520 --> 00:27:39,660 A teraz pozwól mi twierdzić, że wszystko tu jest posortowana. 836 00:27:39,660 --> 00:27:42,474 Tak więc, podobny wynik, lecz zasadniczo różne podejścia. 837 00:27:42,474 --> 00:27:44,140 I nawet nie spojrzał, co tam jest. 838 00:27:44,140 --> 00:27:46,310 Ja po prostu zachować przy elementy jak są one przekazane do mnie, 839 00:27:46,310 --> 00:27:47,240 i radzić sobie z nimi. 840 00:27:47,240 --> 00:27:48,330 >> Więc teraz, widzę numer sześć. 841 00:27:48,330 --> 00:27:51,110 Gdzie jest numer sześć należą? 842 00:27:51,110 --> 00:27:53,250 Mamy dwa, cztery, sześć. 843 00:27:53,250 --> 00:27:54,800 Dokładnie tam, gdzie ona jest teraz. 844 00:27:54,800 --> 00:27:57,750 Więc zostawmy to w spokoju, a teraz twierdzą, że części listy 845 00:27:57,750 --> 00:27:58,772 jest teraz posortowana. 846 00:27:58,772 --> 00:28:01,230 I tak, to czuje się całkowicie różni się tym, że jestem po prostu 847 00:28:01,230 --> 00:28:05,230 poruszanie się po liście tutaj liniowo, a ja nigdy nie podwaja się. 848 00:28:05,230 --> 00:28:05,730 Tak. 849 00:28:05,730 --> 00:28:06,230 W porządku. 850 00:28:06,230 --> 00:28:08,190 Więc osiem, gdzie należysz? 851 00:28:08,190 --> 00:28:08,730 Dokładnie tutaj. 852 00:28:08,730 --> 00:28:09,310 Doskonały. 853 00:28:09,310 --> 00:28:10,210 Więc teraz, jeden. 854 00:28:10,210 --> 00:28:10,900 O o. 855 00:28:10,900 --> 00:28:13,010 To czuje się jak to jest będzie drogie. 856 00:28:13,010 --> 00:28:15,690 Teraz w poprzednim algorytmu Po prostu zamieniłem ludzi. 857 00:28:15,690 --> 00:28:18,648 Więc mogę umieścić go przez całą drogę na początek, ale potem przeniósł Józefa. 858 00:28:18,648 --> 00:28:21,450 Ale jeśli przeniosę Józefa teraz co dzieje się źle? 859 00:28:21,450 --> 00:28:24,250 >> Teraz mam rodzaju undone-- mam podjęta jeden krok do przodu, a następnie 860 00:28:24,250 --> 00:28:26,300 jeden krok wstecz, bo teraz Joseph byłoby w porządku. 861 00:28:26,300 --> 00:28:26,830 Więc zróbmy to. 862 00:28:26,830 --> 00:28:29,150 Jeśli można wziąć numer jeden i cofnąć się na chwilę. 863 00:28:29,150 --> 00:28:30,490 Jak możemy put-- co znowu masz na imię? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> David J. MALAN: Annan w miejscu? 866 00:28:32,610 --> 00:28:36,091 Co musi się zdarzyć w odniesieniu do dwóch, czterech, sześciu, do ośmiu? 867 00:28:36,091 --> 00:28:37,570 Wszyscy oni muszą się zmieniać. 868 00:28:37,570 --> 00:28:42,590 Więc jeśli ośmiu chciałby przesunąć , potem sześć, potem cztery, potem dwa. 869 00:28:42,590 --> 00:28:45,380 A następnie Annan, gdybyś lubię tu przychodzić, dobra. 870 00:28:45,380 --> 00:28:47,760 Ale tutaj mamy tylko rodzaj zapłacił cenę 871 00:28:47,760 --> 00:28:49,510 w innym momencie w algorytmie. 872 00:28:49,510 --> 00:28:52,550 Podczas gdy ostatni raz z wyboru sortowanie, a nawet sortowanie bąbelkowe, 873 00:28:52,550 --> 00:28:54,700 Idę z powrotem i powrotem, tam iz powrotem, 874 00:28:54,700 --> 00:28:58,360 który jest na pewno dodanie czas-mądry, i dosłownie krok po kroku. 875 00:28:58,360 --> 00:29:00,660 >> Sortowanie przez wstawianie, na początku rzut oka, wygląda to 876 00:29:00,660 --> 00:29:05,150 bardzo inteligentne, w które jestem co powoli, przyrostowe postępy, 877 00:29:05,150 --> 00:29:07,120 ale ja nie zamierzam tego tam iz powrotem. 878 00:29:07,120 --> 00:29:09,410 Ale jeśli ktoś jest rzeczywiście z zamówienia, zawiadomienia 879 00:29:09,410 --> 00:29:10,840 wszystkie prace po prostu musiałem to zrobić. 880 00:29:10,840 --> 00:29:14,750 Musiałem przenieść połowę listy wystarczy, aby zrobić miejsce numer jeden. 881 00:29:14,750 --> 00:29:16,790 Więc to jest ta sama ilość pracy do tej pory go 882 00:29:16,790 --> 00:29:18,690 czuje, tylko inny rodzaj pracy. 883 00:29:18,690 --> 00:29:19,370 >> Kontynuujmy. 884 00:29:19,370 --> 00:29:22,657 Więc teraz wiemy, że każdy od jednego do ośmiu są klasyfikowane. 885 00:29:22,657 --> 00:29:23,740 Tutaj, mam numer trzy. 886 00:29:23,740 --> 00:29:25,864 Jeśli chcesz, aby podnieść numer trzy, krok wstecz jeden. 887 00:29:25,864 --> 00:29:28,260 I co wy trzeba zrobić? 888 00:29:28,260 --> 00:29:28,760 Tak. 889 00:29:28,760 --> 00:29:33,070 Tak, że jest jeszcze jeden, dwa, trzy kroki. 890 00:29:33,070 --> 00:29:36,010 Trzy jednostki czasu, że po prostu kosztować ja, tak, że trzy mogą zmieścić. 891 00:29:36,010 --> 00:29:37,460 Wreszcie, siedem. 892 00:29:37,460 --> 00:29:39,730 >> Idziemy do przodu i mieć Ci zrobić krok do tyłu. 893 00:29:39,730 --> 00:29:42,780 To będzie nas kosztować tylko jedna jednostka czasu, ale to jest OK. 894 00:29:42,780 --> 00:29:44,170 A teraz, pięć, dzieje się być trochę droższe. 895 00:29:44,170 --> 00:29:45,340 Jeśli chcesz, aby cofnąć. 896 00:29:45,340 --> 00:29:48,380 Musimy przenieść osiem, siedem i sześć. 897 00:29:48,380 --> 00:29:50,749 A potem wszyscy są teraz sortowane. 898 00:29:50,749 --> 00:29:52,290 Tak wielka ręka tutaj naszych wolontariuszy. 899 00:29:52,290 --> 00:29:53,554 Dziękuję bardzo. 900 00:29:53,554 --> 00:29:56,220 >> [APPLAUSE] 901 00:29:56,220 --> 00:29:56,860 >> Dziękuję Wam wszystkim. 902 00:29:56,860 --> 00:29:57,520 Dziękuję Wam wszystkim. 903 00:29:57,520 --> 00:30:02,940 Zobaczmy teraz, jak kosztowne wszystko to było. 904 00:30:02,940 --> 00:30:06,210 Rozważmy być może Najprostszy z nich, sortowanie bąbelkowe. 905 00:30:06,210 --> 00:30:09,950 I mówię najprostszy, tylko dlatego, można rozwiązać je łapczywie po prostu 906 00:30:09,950 --> 00:30:11,660 naprawić parami problem tutaj. 907 00:30:11,660 --> 00:30:13,720 Fix parami problemu tu znowu i znowu 908 00:30:13,720 --> 00:30:17,680 i znów, powtarzając aż razy, ile faktycznie potrzeba. 909 00:30:17,680 --> 00:30:21,050 >> Tak więc okazuje się, że z bańki rodzaju, dobrze, 910 00:30:21,050 --> 00:30:25,820 ile kroków muszę wziąć na pierwszy przebieg tego algorytmu? 911 00:30:25,820 --> 00:30:30,850 Mógłbym take-- niech see-- jeden, dwa, trzy, cztery, pięć, sześć, siedem. 912 00:30:30,850 --> 00:30:32,190 I nie ma osiem elementów tutaj. 913 00:30:32,190 --> 00:30:35,280 Tak to jest jak n minus 1 kroków się od początku listy 914 00:30:35,280 --> 00:30:36,380 na koniec listy. 915 00:30:36,380 --> 00:30:41,350 >> Ale z wyboru rodzaju, przypominam sobie, że jestem ciągle liczbę elementów 916 00:30:41,350 --> 00:30:44,590 i znowu to najmniejszy, Kładę go na miejscu, 917 00:30:44,590 --> 00:30:46,616 ale nie jestem patrząc za mnie. 918 00:30:46,616 --> 00:30:49,490 Więc myślę, że to trochę bardziej jasne to, że po raz pierwszy, to może 919 00:30:49,490 --> 00:30:52,680 wziąć wszystko n minus 1 kroki znaleźć najmniejszy element. 920 00:30:52,680 --> 00:30:55,920 Następnie umieścić je w miejscu, a ja eksmisji, kto był tu wcześniej. 921 00:30:55,920 --> 00:30:57,500 >> Ale wtedy nie trzeba zachować się w tym elemencie, 922 00:30:57,500 --> 00:30:59,040 bo wiem, że to Już najmniejsze. 923 00:30:59,040 --> 00:31:01,581 Więc teraz, mogę patrzeć na to siedem elementy, następnie sześć elementów, 924 00:31:01,581 --> 00:31:03,290 następnie pięć elementów, a następnie cztery elementy. 925 00:31:03,290 --> 00:31:06,900 I tak Matematycznie, jeżeli n jest liczba elementów lub liczb 926 00:31:06,900 --> 00:31:11,990 że zaczęliśmy, można sobie wyobrazić, który jest taki sam jak n minus 1, 927 00:31:11,990 --> 00:31:14,250 oraz n minus 2 stopnie, oraz n minus 3 stopnie, 928 00:31:14,250 --> 00:31:16,780 + N minus 4 stopnie, wszystko dół do jednego kroku. 929 00:31:16,780 --> 00:31:18,160 A ja jestem na mojej ostatniej osoby. 930 00:31:18,160 --> 00:31:20,650 >> A jeśli przypomnieć, że wiele z książek i Statystyki książek matematycznych 931 00:31:20,650 --> 00:31:24,730 mają te wzory na twarda tyłu lub z przodu z nich, 932 00:31:24,730 --> 00:31:27,690 Okazuje się, że tej serii można wyrazić prościej 933 00:31:27,690 --> 00:31:28,857 jak n razy n minus 1 na 2. 934 00:31:28,857 --> 00:31:31,273 I to jest w porządku, jeśli nie jest to na czele swojego umysłu. 935 00:31:31,273 --> 00:31:32,420 Ale to jest rzeczywiście prawda. 936 00:31:32,420 --> 00:31:34,449 To tylko prostszy sposób pisania. 937 00:31:34,449 --> 00:31:36,240 A jeśli myślisz z powrotem do szkoły podstawowej, 938 00:31:36,240 --> 00:31:38,698 po prostu zacząć pomnożenie rzeczy z, to oczywiście, 939 00:31:38,698 --> 00:31:41,820 jest po prostu n do kwadratu minus n dzieli się przez 2. 940 00:31:41,820 --> 00:31:44,772 Wszystko robiłem to poszerzyć tam wyrażenia. 941 00:31:44,772 --> 00:31:46,730 A więc niech to przepisać to trochę inaczej. 942 00:31:46,730 --> 00:31:49,780 To się n do kwadratu podzielić przez 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Więc jeszcze raz, jestem po prostu rodzaj stosowania niektóre zasady nie arytmetyczne. 944 00:31:53,270 --> 00:31:57,140 Ale zauważ, że teraz największym termin w tej wypowiedzi, że tak powiem, 945 00:31:57,140 --> 00:31:58,540 jest to, że n kwadratu. 946 00:31:58,540 --> 00:32:02,910 Więc tak, jest to n do kwadratu podzielić przez 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Generalnie jednak, jeśli n jest będzie duża wartość, 948 00:32:05,080 --> 00:32:08,740 Zamierzam twierdzą, że n do kwadratu będzie dominującym czynnikiem. 949 00:32:08,740 --> 00:32:10,490 To jest po prostu będzie większy współpracownikiem 950 00:32:10,490 --> 00:32:12,877 liczby etapów niż n / 2. 951 00:32:12,877 --> 00:32:13,960 Więc co mam przez to na myśli? 952 00:32:13,960 --> 00:32:16,795 Spróbujmy prosty przykład, nawet choć matematyka staje się trochę duży. 953 00:32:16,795 --> 00:32:20,210 >> Więc załóżmy, że mieliśmy 1 mln ludzi na scenie, lub 1 milion rzeczy 954 00:32:20,210 --> 00:32:21,320 że chcemy rozwiązać. 955 00:32:21,320 --> 00:32:23,730 Miejmy podłączyć milion w dokładnie tym wzorem 956 00:32:23,730 --> 00:32:27,230 aby zobaczyć, ile kroków potrzeba łącznie sortowanie milion elementów za pomocą powiedzmy, 957 00:32:27,230 --> 00:32:28,560 Wybór rodzaju. 958 00:32:28,560 --> 00:32:30,760 >> Więc my mamy ten sam wzór jak poprzednio. 959 00:32:30,760 --> 00:32:34,120 Chciałbym podłączyć miliona, tak aby uzyskać milion kwadratu podzielić przez 2, 960 00:32:34,120 --> 00:32:35,990 minus milion podzielić przez 2. 961 00:32:35,990 --> 00:32:40,180 Jeśli to zrobić matematyki z góry tutaj mamy 500 miliardów 962 00:32:40,180 --> 00:32:47,460 minus 500 tysięcy, które daje nam 499999500000, 963 00:32:47,460 --> 00:32:49,270 co jest cholernie duża. 964 00:32:49,270 --> 00:32:54,370 >> W rzeczywistości, jeśli porównać teraz 499 miliardów 999 milionów 965 00:32:54,370 --> 00:33:01,210 500000 przeciwko naszej pierwotnej wartości, 500 miliardów, to tak cholernie blisko. 966 00:33:01,210 --> 00:33:06,850 Dobrze? n do kwadratu podzielić przez 2 daje us-- czy raczej n do kwadratu podzielić przez 2 967 00:33:06,850 --> 00:33:08,370 dał nam 500 miliardów. 968 00:33:08,370 --> 00:33:13,510 To cholernie blisko do 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 to znaczy, odejmując 500.000 lub, bardziej ogólnie, odejmując 970 00:33:17,970 --> 00:33:20,010 n do kwadratu, nie naprawdę wielkiego. 971 00:33:20,010 --> 00:33:22,490 N do kwadratu sprawia, że ​​te numery rosną bardzo szybko. 972 00:33:22,490 --> 00:33:25,790 >> Obecnie, to jest tylko o tyle istotne, jak my, jako informatycy, 973 00:33:25,790 --> 00:33:29,350 nie są na ogół dzieje się tak przejmujesz o niuanse tych wzorach 974 00:33:29,350 --> 00:33:31,400 i co dokładnie precyzyjne odpowiedzi są. 975 00:33:31,400 --> 00:33:33,390 Dbamy tylko, że wiesz, co? 976 00:33:33,390 --> 00:33:37,810 Na koniec dnia, to wzór jest rzędu n kwadratu. 977 00:33:37,810 --> 00:33:39,350 >> Tak, jesteśmy podzielenie przez 2 tam. 978 00:33:39,350 --> 00:33:41,360 Tak, jesteśmy odjęcie od n minus 2. 979 00:33:41,360 --> 00:33:46,860 A na koniec dnia, termin które naprawdę nas boli i kosztuje nas 980 00:33:46,860 --> 00:33:48,995 dużo schodów jest to, że kwadrat termin. 981 00:33:48,995 --> 00:33:51,370 A więc to, co informatyk będzie na ogół nie 982 00:33:51,370 --> 00:33:54,160 jest ignorowanie wszystkich tych, mniejsze terminy zamówień, 983 00:33:54,160 --> 00:33:56,900 i po prostu patrzeć na tego, który przyczynia się najbardziej do kosztów. 984 00:33:56,900 --> 00:34:00,530 >> I to jest miłe, bo możemy teraz rozmawiać w znacznie większej ogólności 985 00:34:00,530 --> 00:34:02,470 o algorytmach i można je porównać. 986 00:34:02,470 --> 00:34:04,550 A fakt, że jestem Korzystając z tej O jest celowe. 987 00:34:04,550 --> 00:34:06,680 Kiedy mówię, że na zlecenie o, jestem specjalnie 988 00:34:06,680 --> 00:34:09,560 odnoszące się do czegoś zwane duże O. i Big O 989 00:34:09,560 --> 00:34:14,090 jest zapis, że komputer naukowiec używa do opisania 990 00:34:14,090 --> 00:34:16,710 górną granicę na coś. 991 00:34:16,710 --> 00:34:21,150 >> Jeśli więc powiedzieć, że algorytm jest w dużym O n do kwadratu, 992 00:34:21,150 --> 00:34:23,380 jak zaproponowałem tylko Chwilę temu, że środki 993 00:34:23,380 --> 00:34:27,710 że w zakresie jego biegania Czas i jego skuteczność, 994 00:34:27,710 --> 00:34:30,090 to ma na celu n do kwadratu kroki. 995 00:34:30,090 --> 00:34:31,420 Może więcej, może mniej. 996 00:34:31,420 --> 00:34:33,435 Ale to na kolejność n do kwadratu. 997 00:34:33,435 --> 00:34:34,560 I to jest górna granica. 998 00:34:34,560 --> 00:34:36,530 To nie będzie bardziej bolesne niż to. 999 00:34:36,530 --> 00:34:40,800 To nie będzie n pokrojone w kostkę, lub 2 do n, czy coś znacznie większego. 1000 00:34:40,800 --> 00:34:43,800 Jest to górna granica na cokolwiek to koszt jest. 1001 00:34:43,800 --> 00:34:46,150 Tak więc biorąc pod uwagę, że, powiedzmy, rozważyć tylko kilka przykładów. 1002 00:34:46,150 --> 00:34:49,820 I to jest właśnie lista skończona Czasy bardzo popularne uruchomione 1003 00:34:49,820 --> 00:34:52,870 dla algorytmów, które jest przeznaczone do ilustracją niektórych sprawach, przez które 1004 00:34:52,870 --> 00:34:53,600 widziałem już. 1005 00:34:53,600 --> 00:34:58,060 >> Tak na przykład, w przypadku Wybór rodzaju, co mi twierdząc tutaj 1006 00:34:58,060 --> 00:35:02,250 jest prowadzenie tego wyboru Sortuj w Czas jest rzędu n do kwadratu. 1007 00:35:02,250 --> 00:35:06,260 W najgorszym przypadku, będę mieć cała masa liczb losowych tutaj. 1008 00:35:06,260 --> 00:35:08,600 I jak widzieliśmy matematycznie, gdybym zachować spaceru 1009 00:35:08,600 --> 00:35:11,310 poprzez liście, poprzez lista, wybierając następna najmniejsza 1010 00:35:11,310 --> 00:35:14,410 Element ponownie i ponownie, jeśli I faktycznie spisać wszystkie kroki 1011 00:35:14,410 --> 00:35:18,750 Zabieram się zaproponowałem formulaically wcześniej, to na porządku n kwadratu 1012 00:35:18,750 --> 00:35:20,370 kroki, które biorę. 1013 00:35:20,370 --> 00:35:24,520 >> I okazuje się, że bańka sortowanie i Sortowanie przez wstawianie 1014 00:35:24,520 --> 00:35:27,370 są tak powolne, w najgorszym przypadku. 1015 00:35:27,370 --> 00:35:32,040 Zastanów się, na przykład, Sortowanie przez wstawianie, bardzo ostatnio algorytm którymi mieliśmy do czynienia, 1016 00:35:32,040 --> 00:35:35,500 który miał nam spojrzeć na elemencie, a następnie wstawić go tam, gdzie należy. 1017 00:35:35,500 --> 00:35:38,720 A potem spojrzał na następny element, i wstawia go tam, gdzie należy. 1018 00:35:38,720 --> 00:35:40,990 >> Więc rozważyć najlepszy możliwy scenariusz. 1019 00:35:40,990 --> 00:35:45,590 Załóżmy, że ochotnicy miałem linii dosłownie tak, jeden do osiem, 1020 00:35:45,590 --> 00:35:47,440 już klasyfikowane. 1021 00:35:47,440 --> 00:35:51,300 Ile kroków jest Sortowanie przez wstawianie zajmie się rozwiązać osiem osób, 1022 00:35:51,300 --> 00:35:55,640 jeżeli dotrą na scenie patrząc w ten sposób? 1023 00:35:55,640 --> 00:35:57,410 >> Osiem osób już klasyfikowane. 1024 00:35:57,410 --> 00:35:58,760 I używam Sortowanie przez wstawianie. 1025 00:35:58,760 --> 00:36:02,180 To ostatni z algorytmów. 1026 00:36:02,180 --> 00:36:03,640 No cóż, reaktywują naprawdę szybko. 1027 00:36:03,640 --> 00:36:05,504 Więc jeśli zacznę tutaj, widzę jeden. 1028 00:36:05,504 --> 00:36:06,420 Gdzie jeden należą? 1029 00:36:06,420 --> 00:36:07,730 Należy tutaj. 1030 00:36:07,730 --> 00:36:08,330 Widzę dwa. 1031 00:36:08,330 --> 00:36:09,660 Gdzie dwóch należą? 1032 00:36:09,660 --> 00:36:10,260 Dokładnie tutaj. 1033 00:36:10,260 --> 00:36:10,900 Widzę trzy. 1034 00:36:10,900 --> 00:36:11,920 Skąd trzy należą? 1035 00:36:11,920 --> 00:36:12,480 Dokładnie tutaj. 1036 00:36:12,480 --> 00:36:13,100 >> Widzę cztery. 1037 00:36:13,100 --> 00:36:13,600 Dokładnie tutaj. 1038 00:36:13,600 --> 00:36:15,660 Pięć, sześć, siedem, osiem. 1039 00:36:15,660 --> 00:36:17,320 Nie ma powodu, aby powtarzać. 1040 00:36:17,320 --> 00:36:21,260 I tak, to jak wiele kroków jest to, że chodzi o n? 1041 00:36:21,260 --> 00:36:23,870 To rzędu n Kroki, prawda? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Ale wziąłem numer liniowy kroków, a teraz mam zrobić. 1043 00:36:27,567 --> 00:36:28,900 Więc to najlepszy przypadek, choć. 1044 00:36:28,900 --> 00:36:29,983 A co w najgorszym przypadku? 1045 00:36:29,983 --> 00:36:32,730 Co osiem były tam, siedem były tam, 1046 00:36:32,730 --> 00:36:35,840 i jeden i dwa były tutaj, więc że lista była naprawdę odwrócić? 1047 00:36:35,840 --> 00:36:38,300 >> Cóż, co dzieje się w rzeczywistości Jeśli jest to liczba? 1048 00:36:38,300 --> 00:36:41,300 I zrobimy tylko kilka przykładów. 1049 00:36:41,300 --> 00:36:49,300 Co zrobić, jeśli rzeczywiście numer osiem jest tutaj, a number-- okrzyki. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Więc co, jeśli rzeczywiście liczba osiem jest aż tutaj, 1052 00:36:56,430 --> 00:36:57,790 i używam Sortowanie przez wstawianie? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Twierdzę, w tej chwili jest to na miejscu. 1055 00:37:00,280 --> 00:37:03,152 Ale teraz, seven-- skąd siedem przejść? 1056 00:37:03,152 --> 00:37:04,360 Oczywiście, idzie tutaj. 1057 00:37:04,360 --> 00:37:06,760 Więc muszę przenieść osiem nad jednym miejscu. 1058 00:37:06,760 --> 00:37:08,554 Teraz sześć, tam gdzie to idzie? 1059 00:37:08,554 --> 00:37:09,220 No, dobrze. 1060 00:37:09,220 --> 00:37:13,150 Teraz muszę przenieść osiem nad miejsce, a siedem na miejscu, 1061 00:37:13,150 --> 00:37:14,440 a potem rzuć się sześć. 1062 00:37:14,440 --> 00:37:16,870 >> Tak więc po raz pierwszy, to koszt mnie jeden krok, aby naprawić rzeczy, 1063 00:37:16,870 --> 00:37:18,570 to kosztowało mnie dwa kroki, aby naprawić rzeczy. 1064 00:37:18,570 --> 00:37:20,370 Ile kroków jest to zajmie naprawić 1065 00:37:20,370 --> 00:37:22,720 Atrakcje umieścić pięć we właściwym miejscu? 1066 00:37:22,720 --> 00:37:23,340 Trzy. 1067 00:37:23,340 --> 00:37:29,520 Bo teraz muszę przenieść jeden, dwa, trzy. 1068 00:37:29,520 --> 00:37:32,430 Ile kroków jest to zajmie umieścić cztery w odpowiednim miejscu? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5 plus 6, oraz 7. 1070 00:37:36,040 --> 00:37:40,260 >> A więc jest to matematycznie identyczne co opisano dla wyboru rodzaju. 1071 00:37:40,260 --> 00:37:42,130 Mamy tę serię że po prostu rośnie. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 oraz 4, lub odwrotnie, 7 oraz 6 1073 00:37:45,650 --> 00:37:52,610 oraz 5 oraz 4 dodaje się na dzisiejszym cele do rzędu n do kwadratu. 1074 00:37:52,610 --> 00:37:57,640 >> Więc pozwól mi przewidują też, że Sortowanie bąbelkowe jest również w n do kwadratu. 1075 00:37:57,640 --> 00:38:01,340 Ponieważ z bańki rodzaju, każdego razem przejść przez liście, 1076 00:38:01,340 --> 00:38:03,100 Biorę z grubsza, jak wiele kroków? 1077 00:38:03,100 --> 00:38:06,260 Za każdym razem, dosłownie spacerem od tam istnieje? 1078 00:38:06,260 --> 00:38:07,960 Około n kroków. 1079 00:38:07,960 --> 00:38:12,650 Ale ile razy mogę trzeba przejść przez liście? 1080 00:38:12,650 --> 00:38:13,920 >> No, mniej więcej n czas. 1081 00:38:13,920 --> 00:38:15,680 Może n minus 1, ale mniej więcej n razy. 1082 00:38:15,680 --> 00:38:16,430 Cóż, to dlaczego? 1083 00:38:16,430 --> 00:38:19,560 Cóż, z bańki rodzaju, jeśli zaczynamy sortowanie bąbelkowe, 1084 00:38:19,560 --> 00:38:23,570 z listy w najgorszy z możliwych Sytuacja, która ponownie jest zupełnie 1085 00:38:23,570 --> 00:38:25,550 do tyłu, co się wydarzy? 1086 00:38:25,550 --> 00:38:28,830 I przejść przez liście, a liczba jeden należy całą drogę tam. 1087 00:38:28,830 --> 00:38:33,280 >> Ale z bańki rodzaju, jak daleko ma jeden przenieść na mojej pierwszego przejścia przez liście? 1088 00:38:33,280 --> 00:38:36,620 Ile miejsc ma on się bliżej prawidłowej kolejności? 1089 00:38:36,620 --> 00:38:37,240 Tylko jeden. 1090 00:38:37,240 --> 00:38:40,281 Tak więc, jeśli rodzaj powód, przez to, za każdym razem przez ten algorytm, 1091 00:38:40,281 --> 00:38:41,880 Biorąc około n kroków Dawida. 1092 00:38:41,880 --> 00:38:44,940 Ale ilu przechodzi poprzez lista jest to 1093 00:38:44,940 --> 00:38:49,060 zamiar wziąć na jeden z bańki w lewo, gdzie należy? 1094 00:38:49,060 --> 00:38:51,840 >> Musi poruszać się jak, n spacji w ten sposób. 1095 00:38:51,840 --> 00:38:57,960 Więc po prostu zrobić sortowanie listy, Muszę chodzić tam iz powrotem n razy. 1096 00:38:57,960 --> 00:39:01,540 I za każdym razem, jestem patrząc na n elementów. 1097 00:39:01,540 --> 00:39:05,410 Więc co zrobić n n razy na kolejność n do kwadratu. 1098 00:39:05,410 --> 00:39:07,220 >> Teraz zobaczymy, w niektórych z szorty, które 1099 00:39:07,220 --> 00:39:10,440 są osadzone w kolejnym problemem CS50 jest ustawić, innego podejścia w nich, 1100 00:39:10,440 --> 00:39:13,490 ale teraz, po prostu rozważyć innym razem z systemem, 1101 00:39:13,490 --> 00:39:16,840 zwłaszcza jeśli ci się sortujących trochę czasu, by zatopić się w. 1102 00:39:16,840 --> 00:39:21,790 Co to jest algorytm już widzieliśmy że bierze na zlecenie n krokach? 1103 00:39:21,790 --> 00:39:27,560 >> Co należy wziąć numer liniowy kroków, które widzieliśmy do tej pory? 1104 00:39:27,560 --> 00:39:29,350 Co to? 1105 00:39:29,350 --> 00:39:30,480 Wyszukiwanie katalogu telefonów. 1106 00:39:30,480 --> 00:39:31,390 Pierwszy algorytm. 1107 00:39:31,390 --> 00:39:31,560 Dobrze? 1108 00:39:31,560 --> 00:39:33,650 Gdzie jesteśmy liniowo szukając Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 W rzeczy samej. 1110 00:39:34,150 --> 00:39:37,180 Od tygodnia zera, kiedy zacząłem obracając jedną stronę na raz, 1111 00:39:37,180 --> 00:39:40,095 i nawet powiedział, że to był rodzaj algorytmu liniowego uczucie, 1112 00:39:40,095 --> 00:39:42,720 i mieliśmy ten obraz na Płyta z prostej czerwonej linii 1113 00:39:42,720 --> 00:39:44,678 i prosto żółty linia, to były rzeczywiście 1114 00:39:44,678 --> 00:39:46,810 Algorytmy, które są w dużym O n. 1115 00:39:46,810 --> 00:39:50,680 >> Bo znaleźć Mike Smith w telefonie Księga n stron, w najgorszym przypadku, 1116 00:39:50,680 --> 00:39:52,422 może mi n kroki podjąć. 1117 00:39:52,422 --> 00:39:53,630 Co przy frekwencji? 1118 00:39:53,630 --> 00:39:55,790 Jeden dwa trzy cztery pięć sześć. 1119 00:39:55,790 --> 00:39:59,420 Jaki jest czas pracy tego Algorytm przy frekwencji? 1120 00:39:59,420 --> 00:40:03,070 Big O n, ponieważ w teorii I muszą wskazać wszystkich w pokoju. 1121 00:40:03,070 --> 00:40:05,861 >> Teraz tak na marginesie, co z inne optymalizacja z tygodnia zera? 1122 00:40:05,861 --> 00:40:08,117 Dwa, cztery, sześć, osiem, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Informatykiem będzie sobie sprawę, chwileczkę, 1124 00:40:10,200 --> 00:40:12,320 to jest na porządku n dzieli się przez dwa etapy. 1125 00:40:12,320 --> 00:40:12,820 Dobrze? 1126 00:40:12,820 --> 00:40:14,444 Ponieważ robię dwie osoby na raz. 1127 00:40:14,444 --> 00:40:17,015 Ale będziemy ignorować te niższe terminy zamówień, 1128 00:40:17,015 --> 00:40:19,140 a my po prostu się wyrzucić podzielić przez 2, 1129 00:40:19,140 --> 00:40:21,830 i po prostu powiedzieć, Big O n do tego algorytmu, jak również. 1130 00:40:21,830 --> 00:40:22,760 >> A co z tym? 1131 00:40:22,760 --> 00:40:26,170 Będziemy pominąć niektóre z nich, ale to, co był algorytm, który był log n? 1132 00:40:26,170 --> 00:40:29,900 To trwało około log n kroki? 1133 00:40:29,900 --> 00:40:30,870 Podział i przejęcie. 1134 00:40:30,870 --> 00:40:31,369 Dokładnie. 1135 00:40:31,369 --> 00:40:33,900 Podobnie jak w przykładzie z książki telefonicznej w tydzień zero i dzisiaj wcześniej, 1136 00:40:33,900 --> 00:40:36,191 gdzie dzieli problem znowu i znowu i znowu. 1137 00:40:36,191 --> 00:40:39,070 Mamy wyciągnął go na pokładzie w tym tygodniu zera jako zakrzywiony zielonej linii 1138 00:40:39,070 --> 00:40:41,460 i powiedział, że dnia było logarytmiczną algorytm. 1139 00:40:41,460 --> 00:40:44,970 >> I rzeczywiście, liczba kroków, przyjmuje do wykonania dziel i rządź, 1140 00:40:44,970 --> 00:40:48,610 lub przeszukiwanie binarne, jak zaczniemy nazywając ją, tak jak w książce telefonicznej, 1141 00:40:48,610 --> 00:40:50,680 jest na zlecenie dziennika i kroków. 1142 00:40:50,680 --> 00:40:52,470 I to jest trochę dziwne jeden. 1143 00:40:52,470 --> 00:40:54,910 >> Czym zajmuje jeden krok, lub bardziej szczegółowo 1144 00:40:54,910 --> 00:40:56,240 stała liczba kroków? 1145 00:40:56,240 --> 00:40:58,865 Może to dwa, może to trzy, ale informatyk tylko 1146 00:40:58,865 --> 00:41:01,423 Upraszcza to jako wielki O 1, niektóre stała liczba kroków. 1147 00:41:01,423 --> 00:41:04,256 Co znajduje się w coś, co można zrobić, że ma stałą liczbę kroków? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Jaki jest czas pracy klaskać? 1150 00:41:10,930 --> 00:41:11,920 Stała czasowa. 1151 00:41:11,920 --> 00:41:12,420 Dobrze? 1152 00:41:12,420 --> 00:41:15,490 Jak, co to jest czas pracy cokolwiek, które ma tylko jeden 1153 00:41:15,490 --> 00:41:18,570 Operacja, jak drukować F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Które mogą być uznane za stałą czasową, chyba mniej przypadku rogu z druku F, 1155 00:41:24,110 --> 00:41:28,260 Co może czas pracy druku F faktycznie? 1156 00:41:28,260 --> 00:41:28,790 I czemu? 1157 00:41:28,790 --> 00:41:30,550 Co to jest pomiarowy n w tym przypadku? 1158 00:41:30,550 --> 00:41:32,251 >> PUBLICZNOŚCI: [niesłyszalne]. 1159 00:41:32,251 --> 00:41:33,250 David J. MALAN: Dokładnie. 1160 00:41:33,250 --> 00:41:34,900 Liczba znaków chcemy wydrukować. 1161 00:41:34,900 --> 00:41:36,191 Więc to jest bardzo kontekstowa. 1162 00:41:36,191 --> 00:41:39,910 Dziś mamy skupia się wiele na Tutaj litery i cyfry na tablicy. 1163 00:41:39,910 --> 00:41:43,540 Ale może to być również znaki w rzeczywistej ciąg. 1164 00:41:43,540 --> 00:41:46,420 Tak więc okazuje się, że jest inny środek, który rozpocznie dbając o, 1165 00:41:46,420 --> 00:41:48,530 i to jest przeciwieństwem z Big O, tak powiem. 1166 00:41:48,530 --> 00:41:50,120 >> To zapis omega. 1167 00:41:50,120 --> 00:41:53,380 Podczas gdy duże O, co oznacza, The górne ograniczenie na czas pracy? 1168 00:41:53,380 --> 00:41:55,580 Maksymalnie, ile czasu może coś zabrać? 1169 00:41:55,580 --> 00:41:59,250 Omega-- przykro to ciągle pojawia up-- jest przeciwieństwem tego, 1170 00:41:59,250 --> 00:42:02,960 przy czym jest to dolna granica na ilość czasu coś może potrwać. 1171 00:42:02,960 --> 00:42:10,480 >> Więc. na przykład, co jest algorytm że ma zawsze n kwadratowe kroki? 1172 00:42:10,480 --> 00:42:15,600 Cóż, jeden z algorytmów widzieliśmy Obecnie, w rzeczywistości, może być tak, że również. 1173 00:42:15,600 --> 00:42:16,720 Sortuj wybór. 1174 00:42:16,720 --> 00:42:18,270 Wybór rodzaju całkiem głupi. 1175 00:42:18,270 --> 00:42:21,760 Nawet jeśli algorithm-- przykro, nawet jeśli tablica jest już posortowana, 1176 00:42:21,760 --> 00:42:24,150 Wybór rodzaju będzie zachować spaceru po liście 1177 00:42:24,150 --> 00:42:28,907 aby upewnić się, że ma najmniejszy Element znowu i znowu i znowu. 1178 00:42:28,907 --> 00:42:31,740 I nawet jeśli ludzie w Publiczność wie, że zaraz, 1179 00:42:31,740 --> 00:42:33,948 już przeszedł najmniejszy element, komputer 1180 00:42:33,948 --> 00:42:37,300 nie wie, że dopóki to wygląda przez całą drogę listy. 1181 00:42:37,300 --> 00:42:40,240 Podobnie, dolna granica, że może być również brane pod uwagę 1182 00:42:40,240 --> 00:42:42,000 Czas może być liniowa. 1183 00:42:42,000 --> 00:42:48,260 >> Ile czasu potrzeba, aby Elementy sortowania n w najlepszy 1184 00:42:48,260 --> 00:42:52,420 Sprawa bańki za pomocą czegoś takiego rodzaju? 1185 00:42:52,420 --> 00:42:54,280 Załóżmy, że lista jest już posortowana. 1186 00:42:54,280 --> 00:42:56,696 Powiedzieliśmy, sortowanie bąbelkowe nabiera kolejność n do kwadratu kroki. 1187 00:42:56,696 --> 00:42:59,640 Ale co, jeśli to już klasyfikowane? 1188 00:42:59,640 --> 00:43:02,310 Co zrobić, jeśli uświadomić sobie, po jedno przejście przez tablicę 1189 00:43:02,310 --> 00:43:03,540 że nie zrobiłeś swapy? 1190 00:43:03,540 --> 00:43:05,970 Czy trzeba zachować co więcej przechodzi? 1191 00:43:05,970 --> 00:43:06,470 >> Nie. 1192 00:43:06,470 --> 00:43:10,340 Więc dolną granicę sortowanie bąbelkowe Można powiedzieć, liniowy. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 I możemy spojrzeć na inni z nich, jak również. 1195 00:43:14,450 --> 00:43:17,990 Więc rzućmy okiem co tylko wizualizacji tutaj 1196 00:43:17,990 --> 00:43:20,790 aby zobaczyć, jak te wyróżniają się. 1197 00:43:20,790 --> 00:43:24,592 Mam zamiar iść na dół do tego Strona to jest dostępne na stronie internetowej C50, w 1198 00:43:24,592 --> 00:43:27,550 ale to będzie ból, aby dostać pracę, ponieważ wykorzystuje technologię o nazwie 1199 00:43:27,550 --> 00:43:30,560 Apletów Java, które jest w dużej mierze obsługiwane w tych dniach, 1200 00:43:30,560 --> 00:43:32,730 co najmniej przez Chrome i niektórych innych. 1201 00:43:32,730 --> 00:43:37,070 >> I pozwól mi iść do przodu i przyspieszyć ten się i wyjaśnić, co się dzieje. 1202 00:43:37,070 --> 00:43:40,840 Jest to demonstracja bańki rodzaju, pierwszy algorytm przyjrzeliśmy. 1203 00:43:40,840 --> 00:43:43,950 I to jest wizualizacja tym, że każdy z tych prętów stanowi liczbę. 1204 00:43:43,950 --> 00:43:45,710 Im większy jest bar, im większa liczba. 1205 00:43:45,710 --> 00:43:47,520 Im mniejszy jest bar, Im mniejsza liczba. 1206 00:43:47,520 --> 00:43:50,353 A co możesz zobaczyć wizualnie, nawet choć to będzie super szybki, 1207 00:43:50,353 --> 00:43:53,699 jest to, że czerwony pasek jest podobny do mnie, chodzenie tam iz powrotem rozwiązywania problemów. 1208 00:43:53,699 --> 00:43:56,740 Widać, że większe elementy rzeczywiście się pęcherzyków w prawo 1209 00:43:56,740 --> 00:43:59,650 i mniejsze elementy są pęcherzyków do lewej. 1210 00:43:59,650 --> 00:44:01,870 I tutaj, jeśli będziemy faktycznie przyjrzeć się bliżej, 1211 00:44:01,870 --> 00:44:04,330 faktycznie możemy liczyć liczba porównań i swapy 1212 00:44:04,330 --> 00:44:05,350 które były wykonane. 1213 00:44:05,350 --> 00:44:07,360 >> Ale zamiast tego, spójrzmy w drugim algorytmem 1214 00:44:07,360 --> 00:44:11,240 przyjrzeliśmy się wcześniej z naszym wolontariuszy, wybór rodzaju. 1215 00:44:11,240 --> 00:44:13,500 Wizualnie, posiada bardzo różny efekt. 1216 00:44:13,500 --> 00:44:16,820 Ale to znowu bardzo intuicyjny w że trzymamy wybierając następna najmniejsza 1217 00:44:16,820 --> 00:44:18,660 elementem, i mieliśmy trochę szczęścia. 1218 00:44:18,660 --> 00:44:20,110 Że czuł się zasadniczo szybciej. 1219 00:44:20,110 --> 00:44:22,840 Ale jeśli prowadził to znowu i znowu i znowu z wieloma wejściami, 1220 00:44:22,840 --> 00:44:26,680 to widzimy, że jest to w istocie nadal w dużym O n do kwadratu. 1221 00:44:26,680 --> 00:44:29,920 >> Zróbmy jeden ostatni tutaj, Sortowanie przez wstawianie, 1222 00:44:29,920 --> 00:44:33,180 która była trzecim algorytmem przyjrzeliśmy się i wycofywania 1223 00:44:33,180 --> 00:44:36,700 że ten zajmuje się elementy, jak napotka je, 1224 00:44:36,700 --> 00:44:39,290 Ale wtedy być może zmiany rzeczy, nad, aby zrobić miejsce, 1225 00:44:39,290 --> 00:44:41,660 wstawiania elementów do której należą. 1226 00:44:41,660 --> 00:44:45,330 >> I to też kończy się dając ostateczny wynik. Teraz wszystkie trzy z tych, 1227 00:44:45,330 --> 00:44:46,490 czułem się dość szybko. 1228 00:44:46,490 --> 00:44:48,740 I rzeczywiście, wpadłem je w całkiem dobrym klipu. 1229 00:44:48,740 --> 00:44:52,510 Ale zasadniczo, oni wszyscy dość straszne, szczerze mówiąc. 1230 00:44:52,510 --> 00:44:56,960 Wszystkie z tych algorytmów dotychczas że prowadzony w Big O n do kwadratu 1231 00:44:56,960 --> 00:44:59,270 zabrać sporo czas, aby uruchomić w końcu. 1232 00:44:59,270 --> 00:45:01,920 >> I rzeczywiście, możemy zobaczyć i czuć to wreszcie 1233 00:45:01,920 --> 00:45:04,090 jeśli podciągnąć ten trzeci i ostatni demo. 1234 00:45:04,090 --> 00:45:05,840 Jest to kolejny wizualizacji, które będzie 1235 00:45:05,840 --> 00:45:08,500 sortowanie bąbelkowe pokazać po lewej stronie, Wybór rodzaju w środku, 1236 00:45:08,500 --> 00:45:13,410 i coś, jako jeden z naszych ręka podnosi wcześniej zasugerował, 1237 00:45:13,410 --> 00:45:15,020 sortowanie przez scalanie po prawej stronie. 1238 00:45:15,020 --> 00:45:16,937 Podział i przejęcie Strategia na prawo. 1239 00:45:16,937 --> 00:45:19,520 I to jest w rzeczywistości, co mamy przyjrzymy się w środę. 1240 00:45:19,520 --> 00:45:21,990 , Ale niech czas te na prowadzenie równolegle. 1241 00:45:21,990 --> 00:45:26,765 To jest w przybliżeniu taka sama ilość Elementy wszystkim działa w tym samym czasie. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Sortowanie bąbelkowe vs wyboru Sortuj vs sortowanie przez scalanie. 1244 00:45:34,440 --> 00:45:36,760 >> Teraz oni wszyscy działa W teorii, w tym samym czasie. 1245 00:45:36,760 --> 00:45:39,830 Procesor pracuje z z tą samą prędkością, ale 1246 00:45:39,830 --> 00:45:44,014 może czuć się jak nudne to jest bardzo szybko stanie się, 1247 00:45:44,014 --> 00:45:45,930 i jak szybko, kiedy możemy wstrzyknąć trochę tygodnia 1248 00:45:45,930 --> 00:45:49,330 Algorytmy Zero może możemy przyspieszyć. 1249 00:45:49,330 --> 00:45:51,760 >> A teraz porównajmy tych w jednej ostatniej postaci. 1250 00:45:51,760 --> 00:45:55,710 Mam zamiar iść do przodu na stronie CS50, gdzie 1251 00:45:55,710 --> 00:45:59,020 mamy to ostatnie ogniwo na dziś, gdzie ktoś w internecie 1252 00:45:59,020 --> 00:46:03,960 prosimy umieścić razem film, który rejestruje to, co innego sortowania 1253 00:46:03,960 --> 00:46:07,510 Algorytmy brzmieć. 1254 00:46:07,510 --> 00:46:09,577 To Sortowanie przez wstawianie. 1255 00:46:09,577 --> 00:46:12,072 >> [DŹWIĘKOWY] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> W którym starasz się częstotliwość na podstawie wysokości Bar. 1258 00:46:16,850 --> 00:46:19,826 Jest to sortowanie bąbelkowe. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped DŹWIĘKOWY] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Jadąc obok jest-- nadchodzi w przyszłym jest-- wybór rodzaju, 1262 00:46:45,774 --> 00:46:48,820 gdzie znów mamy wyboru następny najmniejszy element, 1263 00:46:48,820 --> 00:46:51,820 i widzimy, że rośnie od lewej do prawej. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Sortowanie przez scalanie, nasz zwycięzca tej pory dzisiaj. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Zauważ, jak to podzielenie rzeczy do [niesłyszalne] połowie i kwartałów. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome rodzaju, które nie mamy mówił o, i tworzy wizualnie 1270 00:47:21,660 --> 00:47:24,450 i audally trochę inny kształt i dźwięk. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Tam iz powrotem, czyszczenia rzeczy. 1273 00:47:30,160 --> 00:47:32,230 Sprawdź również sortowanie przez kopcowanie na stronie internetowej tego faceta. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> I to wszystko. 1276 00:47:36,810 --> 00:47:38,210 Będziemy zobaczenia następnym razem. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [WHOOSHING I MUZYKA] 1279 00:47:48,334 --> 00:50:24,839