1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Głośnik: Dobrze, to jest CS50. 3 00:00:14,910 --> 00:00:19,020 Jest to koniec trzy tygodnie, a gdy nie skorzystało już, 4 00:00:19,020 --> 00:00:21,790 wiem, że nie będzie obiad jak zwykle w piątek, gdzie 5 00:00:21,790 --> 00:00:25,430 można cieszyć się dobrą rozmowę i jedzenie w Fire and Ice 6 00:00:25,430 --> 00:00:27,980 niektóre z CS50 jest Pracownicy i koledzy. 7 00:00:27,980 --> 00:00:30,170 Udaj się do tego adresu URL tutaj. 8 00:00:30,170 --> 00:00:33,420 >> Teraz możesz sobie przypomnieć, czy jesteś może szybko zapoznać się z, 9 00:00:33,420 --> 00:00:35,970 te rzeczy, które tutaj podane są na końcu 10 00:00:35,970 --> 00:00:37,850 semestru dla wielu klas. 11 00:00:37,850 --> 00:00:40,870 Tak zwany egzamin niebieski książek, w których napisać swoje odpowiedzi do egzaminów. 12 00:00:40,870 --> 00:00:44,240 Teraz mam tutaj 26 takich niebieskie książki, na każdą z nich 13 00:00:44,240 --> 00:00:47,580 jest napisane imię, A do Z. I rzeczywiście nazwy są takie proste, 14 00:00:47,580 --> 00:00:50,490 przez Z. I jeden z cele w ręku dzisiaj 15 00:00:50,490 --> 00:00:53,910 będzie kontynuować co zaczęliśmy w poniedziałek, który nie jest 16 00:00:53,910 --> 00:00:57,830 tak patrząc na kod, ale naprawdę patrząc na pomysły i rozwiązywania problemów. 17 00:00:57,830 --> 00:01:00,170 Jednym z celów i Obietnice tego kursu 18 00:01:00,170 --> 00:01:02,985 jest, aby nauczyć się myśleć starannie, bardziej metodycznie, 19 00:01:02,985 --> 00:01:05,400 i sprawne rozwiązanie problemów. 20 00:01:05,400 --> 00:01:09,526 I rzeczywiście, można to zrobić bardzo bez dotykania linii kodu. 21 00:01:09,526 --> 00:01:12,150 Mam więc kilka słoni się tu dzisiaj, pomarańczowy i niebieski, 22 00:01:12,150 --> 00:01:15,780 czy możemy dostać jednego wolontariusza, być może z powrotem dalej niż zwykle. 23 00:01:15,780 --> 00:01:18,070 Jak się tam, chodź na dół. 24 00:01:18,070 --> 00:01:24,180 Celem, który ma być do pomóc Plus podawać ten egzamin tutaj. 25 00:01:24,180 --> 00:01:24,935 Jak masz na imię? 26 00:01:24,935 --> 00:01:25,768 >> PUBLICZNOŚCI: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Głośnik: Mary Beth, dalej w górę. 28 00:01:27,560 --> 00:01:29,560 Pozwól mi mikrofon tu dla Ciebie. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Miło cię poznać. 31 00:01:32,880 --> 00:01:34,005 >> PUBLICZNOŚCI: Miło cię poznać. 32 00:01:34,005 --> 00:01:36,790 Głośnik: Dobrze, więc mam o niebieskie książki od A do Z, 33 00:01:36,790 --> 00:01:41,680 i będę udawać, że Mam jeden z uczniów, 34 00:01:41,680 --> 00:01:45,770 i jedziesz w nieco losowo na koniec trzy godziny egzaminu bloku 35 00:01:45,770 --> 00:01:49,400 więc oni kończący się w niektórych semi-losowa kolejność tak. 36 00:01:49,400 --> 00:01:54,510 Teraz Twoja praca za chwilę będzie aby być: to jest rzeczywiście jak się dostać 37 00:01:54,510 --> 00:01:56,820 Okazało się przy końcu Klasa, najprawdopodobniej. 38 00:01:56,820 --> 00:02:01,120 Twoim zadaniem jest teraz będzie, całkiem po prostu, aby sortować te niebieskie książek dla nas 39 00:02:01,120 --> 00:02:05,220 od A do Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLICZNOŚCI: Och, to jest będzie trwać wiecznie. 41 00:02:08,400 --> 00:02:13,747 >> Głośnik: I będziemy oglądać jak to zrobić, nie ma ciśnienia. 42 00:02:13,747 --> 00:02:15,330 PUBLICZNOŚCI: Nie, nie ma ciśnienia, ani nic. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> Głośnik: A dla zabawy, postawmy się zegar. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLICZNOŚCI: Tyle radości, tyle zabawy. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Głośnik: mogę trzymać mikrofon dla Ciebie. 49 00:02:38,574 --> 00:02:40,240 Wszystko w porządku, właśnie podwoił naszą prędkość. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Więc w międzyczasie, niech stanowią co będzie pytanie do Mary Beth 52 00:02:49,060 --> 00:02:51,540 jest to, co ona robi, jak jest ona idzie o rozwiązanie tego? 53 00:02:51,540 --> 00:02:54,040 I rzeczywiście, nie może mieć kiedykolwiek myślałeś o czymś 54 00:02:54,040 --> 00:02:57,440 tak proste, jak przy odbiorze aż 26 książek takich jak ta, 55 00:02:57,440 --> 00:02:59,350 które mają naturalne Zamawiając do nich. 56 00:02:59,350 --> 00:03:01,335 Co to jest proces że faktycznie korzysta? 57 00:03:01,335 --> 00:03:03,770 Jest to dość losowo tylko zbieranie się pierwszy widoczny 58 00:03:03,770 --> 00:03:05,250 i wprowadzenie go w jego miejsce? 59 00:03:05,250 --> 00:03:09,680 Czy najpierw przenieść swoje ręce wokół Szukam następnie szuka B? 60 00:03:09,680 --> 00:03:11,722 Czy warto zapoznać się Para strony je stronie 61 00:03:11,722 --> 00:03:14,680 i po prostu powiedzieć: chwileczkę, to nie jest w porządku, a następnie zamienić kolejność? 62 00:03:14,680 --> 00:03:16,960 Widzieliśmy już w poniedziałek że istnieje wiele sposobów, 63 00:03:16,960 --> 00:03:22,140 w którym możemy to zrobić, i Rzeczywiście, kiedy w pobliżu końca tutaj 64 00:03:22,140 --> 00:03:26,360 Chciałbym zwrócić uwagę może czego Mary Beth robi. 65 00:03:26,360 --> 00:03:30,040 Mamy kilka pali się wydaje, większy, trzy mniejsze. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBLICZNOŚCI: Jestem ich zamawianiu kiedy znajdę dwie litery 68 00:03:36,415 --> 00:03:39,540 Wiem, że są ze sobą w sekwencji, I umieścić je razem tak, że ja nie 69 00:03:39,540 --> 00:03:42,915 muszą się martwić o utrzymanie utwór z całego szeregu książek. 70 00:03:42,915 --> 00:03:45,706 To jest po prostu, no, to po pierwsze, Mam ten stos tutaj. 71 00:03:45,706 --> 00:03:47,580 Głośnik: Tak, prawie jak a kawałki układanki, które 72 00:03:47,580 --> 00:03:49,860 mają odpowiedni kształt zgadza się ze sobą. 73 00:03:49,860 --> 00:03:51,026 PUBLICZNOŚCI: Dość dużo, tak. 74 00:03:51,026 --> 00:03:55,320 Głośnik: OK, doskonałe. 75 00:03:55,320 --> 00:03:59,850 Teraz każdy z nich pale jest prawdopodobnie sortowane? 76 00:03:59,850 --> 00:04:00,990 >> PUBLICZNOŚCI: Tak. 77 00:04:00,990 --> 00:04:09,900 >> Głośnik: Dobra, przez Z. Wszystkie Dobrze, gratulacje, udało ci się. 78 00:04:09,900 --> 00:04:11,461 Masz wybór. 79 00:04:11,461 --> 00:04:11,960 Niebieski? 80 00:04:11,960 --> 00:04:13,530 Wszystko w porządku, dziękuję za to. 81 00:04:13,530 --> 00:04:16,679 Więc nie zaproponować Mary Beth co jej podejście było, 82 00:04:16,679 --> 00:04:19,720 ale to, co jest inne podejście, w jaki sposób Sortowanie może iść o te rzeczy? 83 00:04:19,720 --> 00:04:21,130 Co byś zrobił? 84 00:04:21,130 --> 00:04:24,060 Rekord do pobicia byłby jednej minuty, 50 sekund lub tak, 85 00:04:24,060 --> 00:04:26,039 Plus te zapomniałem liczyć. 86 00:04:26,039 --> 00:04:27,080 Co byś zrobił? 87 00:04:27,080 --> 00:04:27,579 Tak? 88 00:04:27,579 --> 00:04:28,735 PUBLICZNOŚCI: Weź stos. 89 00:04:28,735 --> 00:04:29,776 Zacznij od początku. 90 00:04:29,776 --> 00:04:32,284 Sprawdź swoje papiery. 91 00:04:32,284 --> 00:04:36,586 I jeśli jedna górna jest większa niż, być może, że są, 92 00:04:36,586 --> 00:04:38,980 dolny jest wyższy, a następnie przełączyć je. 93 00:04:38,980 --> 00:04:41,300 >> Głośnik: OK, więc zaczynając Na górze i na dole 94 00:04:41,300 --> 00:04:43,716 a następnie na swój sposób pracy do wewnątrz tak, zamieniając je? 95 00:04:43,716 --> 00:04:46,580 OK, więc trochę podobna w duchu do bańki rodzaju, 96 00:04:46,580 --> 00:04:49,160 ale wybór skrajności nie sąsiadujące pary. 97 00:04:49,160 --> 00:04:52,080 Ale krótkie jest to, że nie ma na pewno kilka różnych sposobów 98 00:04:52,080 --> 00:04:54,210 możemy to zrobić, i Szczerze mówiąc, myślę, że rodzaj 99 00:04:54,210 --> 00:04:55,700 przyjęła kilka podejść, prawda? 100 00:04:55,700 --> 00:05:00,567 Zrobiłeś coś w rodzaju czterech segregowanych pali, i następnie skutecznie połączył je razem. 101 00:05:00,567 --> 00:05:02,650 A to, śmiem twierdzić, inny całkowicie techniką. 102 00:05:02,650 --> 00:05:06,950 Nie traktują go jako jeden wielki stos, można podzielić na cztery problem quadów, 103 00:05:06,950 --> 00:05:09,820 jeśli chcesz, a następnie w jakiś sposób połączono je na końcu. 104 00:05:09,820 --> 00:05:13,410 >> Warto więc rozważyć, ostatecznie, jak inaczej moglibyśmy to zrobić. 105 00:05:13,410 --> 00:05:15,860 Mamy sformalizowane pojęcie bubble sort ostatnim czasie, 106 00:05:15,860 --> 00:05:18,780 i wycofanie bubble sort był Algorytm że wizualizowane 107 00:05:18,780 --> 00:05:22,640 z ośmioma kolegami się tutaj, pozornie przypadkowo sortowane w pierwszej kolejności. 108 00:05:22,640 --> 00:05:26,110 I wtedy zdecydowaliśmy parami, jeśli dwa elementy są w porządku, 109 00:05:26,110 --> 00:05:26,950 po prostu zamienić je. 110 00:05:26,950 --> 00:05:28,930 Tak więc cztery i dwa są oczywiście w porządku, 111 00:05:28,930 --> 00:05:31,080 więc te dwa koledzy pozycji włączony. 112 00:05:31,080 --> 00:05:35,390 A potem powtórzyć z czterech do sześciu, następnie sześć i osiem na każdej iteracji, 113 00:05:35,390 --> 00:05:36,980 przemieszcza się na prawo. 114 00:05:36,980 --> 00:05:42,590 >> Tak więc biorąc pod uwagę osiem osób, ile parami porównania zrobiłem podczas spaceru z 115 00:05:42,590 --> 00:05:45,220 od lewej do prawej w jednej iteracji tego? 116 00:05:45,220 --> 00:05:48,410 Ile porównań? 117 00:05:48,410 --> 00:05:49,197 Siedem, prawda? 118 00:05:49,197 --> 00:05:51,405 Bo jeśli jest osiem osób, ale trzeba parę 119 00:05:51,405 --> 00:05:53,880 im i ruszać po jednym z prawej 120 00:05:53,880 --> 00:05:56,060 nie będziemy mieć osiem porównania, ponieważ nie można porównać 121 00:05:56,060 --> 00:05:59,226 Element na sobie, albo byłoby po prostu bez sensu, więc trzeba siedem. 122 00:05:59,226 --> 00:06:01,290 Lub, bardziej ogólnie, gdy mamy n ludzi, my 123 00:06:01,290 --> 00:06:04,300 do porównań n minus 1 z bańki rodzaju. 124 00:06:04,300 --> 00:06:08,150 >> Rozważmy więc teraz, jak dobre lub złe sortowanie bąbelkowe faktycznie było, i spróbuj 125 00:06:08,150 --> 00:06:13,570 dać sobie słownictwo z które do algorytmów krytyki jak to, 126 00:06:13,570 --> 00:06:14,430 i wkrótce nasz własny. 127 00:06:14,430 --> 00:06:16,970 Więc pierwszego przejścia przez sortowanie bąbelkowe, pierwszy raz 128 00:06:16,970 --> 00:06:20,909 Chodziłem od lewej do prawej etap, wziął mnie n minus 1 porównań. 129 00:06:20,909 --> 00:06:22,950 I to będzie mój jednostka miary, prawda? 130 00:06:22,950 --> 00:06:26,170 Miałam rozmowy i spacery, dość szybko, trochę powolny 131 00:06:26,170 --> 00:06:29,300 więc licząc mojego liczbę sekund nie jest szczególnie mówiąc, 132 00:06:29,300 --> 00:06:32,260 a zliczanie liczby Operacje, które zrobiłem w poniedziałek, 133 00:06:32,260 --> 00:06:35,900 Porównując dwie osoby, które uważa jak miły jednostki miary. 134 00:06:35,900 --> 00:06:40,980 >> Więc n minus 1 kroki po raz pierwszy, ale to, co się stało potem? 135 00:06:40,980 --> 00:06:46,610 Co jeden plus z jednym przejściu poprzez listy inaczej niesegregowanych? 136 00:06:46,610 --> 00:06:49,840 Co możesz mi powiedzieć o elemencie który był aż tam? 137 00:06:49,840 --> 00:06:51,300 Tak? 138 00:06:51,300 --> 00:06:52,870 To był największy elementem, prawda? 139 00:06:52,870 --> 00:06:55,710 Numer osiem, mimo że rozpoczął tutaj, za każdym razem kiedy 140 00:06:55,710 --> 00:06:57,860 porównano ją do sąsiad, trzymała 141 00:06:57,860 --> 00:07:00,480 pęcherzyków do prawej strony listy. 142 00:07:00,480 --> 00:07:02,710 I rzeczywiście, to gdzie Algorytm dostaje swoją nazwę. 143 00:07:02,710 --> 00:07:07,630 >> Teraz o tym logiki, ile porównania muszę zrobić na raz drugi 144 00:07:07,630 --> 00:07:09,800 Robię to podanie z lewej do prawej? 145 00:07:09,800 --> 00:07:10,730 n minus 2, prawda? 146 00:07:10,730 --> 00:07:14,297 To byłoby marnować mój czas, gdybym zachować porównanie ośmiu przeciwko komuś 147 00:07:14,297 --> 00:07:16,630 indziej, bo już wiemy, była w odpowiednim miejscu. 148 00:07:16,630 --> 00:07:19,760 Więc to jest trochę optymalizacja, więc następnego przejścia 149 00:07:19,760 --> 00:07:23,899 będzie Plus n minus dwa stopnie, gdzie n oznacza liczbę osób. 150 00:07:23,899 --> 00:07:26,940 Teraz możesz rodzaju ekstrapolacji, nawet jeśli nie jesteś informatykiem, 151 00:07:26,940 --> 00:07:27,680 jak to się kończy. 152 00:07:27,680 --> 00:07:31,259 Pod koniec tego algorytmu przypuszczalnie masz tylko jedno porównanie lewo. 153 00:07:31,259 --> 00:07:33,800 Musisz trochę naprawić początku listy w przypadku dwóch 154 00:07:33,800 --> 00:07:36,540 i jeden jest w porządku i powinna być jeden i dwa 155 00:07:36,540 --> 00:07:40,330 tak więc długość, przy Plus 1 ostateczne porównanie. 156 00:07:40,330 --> 00:07:44,500 >> Teraz kropka, kropka, kropka rodzaj fal jest ręce na niektóre z bardziej soczyste szczegóły, 157 00:07:44,500 --> 00:07:46,452 ale niech po prostu iść do przodu i uproszczenia. 158 00:07:46,452 --> 00:07:48,660 Jeśli pamiętacie z wysokiej Szkoła, szczerze mówiąc, wiele z was 159 00:07:48,660 --> 00:07:50,340 miały książki matematyczne, które miały trochę ściągawki 160 00:07:50,340 --> 00:07:52,550 na okładce lub tylna pokrywa, że ​​pokazałem 161 00:07:52,550 --> 00:07:56,400 sumowania, co seria, jak to ostatecznie dodana do. 162 00:07:56,400 --> 00:07:59,600 W ogólnym przypadku, jeśli masz Zmienna jak n, a nawet ten, 163 00:07:59,600 --> 00:08:01,634 jeśli spojrzał na swoje stara szkoła książka matematyka, 164 00:08:01,634 --> 00:08:04,050 to zobaczysz, że to naprawdę dodaje do tej sumy tutaj, 165 00:08:04,050 --> 00:08:07,970 n razy n minus 1 wszystko podzielić przez 2. 166 00:08:07,970 --> 00:08:11,172 Więc teraz niech mi tylko zastrzec, to prawda, więc na skok wiary, 167 00:08:11,172 --> 00:08:12,880 to właśnie ta podsumowuje do, i mogliśmy 168 00:08:12,880 --> 00:08:14,341 dowodzą, że w bardziej ogólnym przypadku. 169 00:08:14,341 --> 00:08:15,590 Ale teraz niech poszerzyć to. 170 00:08:15,590 --> 00:08:19,920 Warto więc pomnożyć to, więc to n do kwadratu minus n, wszystko podzielić przez 2. 171 00:08:19,920 --> 00:08:23,200 To naprawdę n do kwadratu, podzielić przez 2, minus n nad 2, 172 00:08:23,200 --> 00:08:25,010 tak, to wszystko ładne i ciekawe. 173 00:08:25,010 --> 00:08:27,060 Ale co się stanie, jeśli teraz plug-in o wartości? 174 00:08:27,060 --> 00:08:29,724 Załóżmy, że nie miałem osiem osób, ale powiedzieć milion. 175 00:08:29,724 --> 00:08:31,890 I tylko dlatego, że miliony jest to dość duża liczba, 176 00:08:31,890 --> 00:08:34,039 niech wtyczkę i zobaczyć, co się dzieje. 177 00:08:34,039 --> 00:08:39,039 Więc jeśli podłączyć mln w tym wzorze Mam zamiar dostać milion do kwadratu, 178 00:08:39,039 --> 00:08:42,868 podzielić przez 2, minus mln, podzielić przez 2. 179 00:08:42,868 --> 00:08:44,159 Teraz co to będzie równe? 180 00:08:44,159 --> 00:08:47,354 Więc 500 miliardów, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 I jeśli faktycznie że matematyka się, że środki 182 00:08:49,270 --> 00:08:53,920 że sortowanie milion osoby o sortowanie bąbelkowe 183 00:08:53,920 --> 00:09:01,800 może zająć mi 499999500000 kroków lub porównania w celu 184 00:09:01,800 --> 00:09:02,900 jesteśmy po prostu ekstrapolację. 185 00:09:02,900 --> 00:09:06,860 >> Że czuje się dość wolno, ale szczerze wejście do pomiaru jednego konkretnego 186 00:09:06,860 --> 00:09:09,160 tak, to nie wszystko, że wiadomo. 187 00:09:09,160 --> 00:09:14,050 Ale w rzeczywistości to nie sugeruje, że jak n dostaje coraz większy, to algorytm 188 00:09:14,050 --> 00:09:16,280 rodzaj czuje się gorzej i gorzej, lub że naprawdę 189 00:09:16,280 --> 00:09:20,450 zacznie odczuwać ból, że potęgowanie, że n do kwadratu, 190 00:09:20,450 --> 00:09:21,770 który dodaje się dość szybko. 191 00:09:21,770 --> 00:09:25,340 I to nie jest detal stracił na ludzi, w rzeczywistości 192 00:09:25,340 --> 00:09:29,640 kilka lat temu pewien senator, który był kampanii, usiadł na rozmowę 193 00:09:29,640 --> 00:09:32,180 z Google'a Eric Schmidt, CEO w czasie, 194 00:09:32,180 --> 00:09:36,380 i został zakwestionowany w pytaniu podobnie jak badamy dzisiaj. 195 00:09:36,380 --> 00:09:38,468 Rzućmy okiem. 196 00:09:38,468 --> 00:09:45,280 >> [ODTWARZANIE] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Że tu jesteś w Google, i lubię 198 00:09:48,560 --> 00:09:53,382 myśleć o prezydenturę jak rozmowy kwalifikacyjnej. 199 00:09:53,382 --> 00:09:56,434 Teraz, to jest trudne do uzyskania praca jako prezydent, 200 00:09:56,434 --> 00:09:58,100 i przechodzisz rygorów teraz. 201 00:09:58,100 --> 00:10:01,860 Trudno też, aby dostać pracę w Google. 202 00:10:01,860 --> 00:10:05,490 Mamy pytania, a my zapytaj naszych kandydatów na pytania, 203 00:10:05,490 --> 00:10:09,770 i ten jest z Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Co-- myślicie, że jestem żartuję, że to właśnie tutaj. 205 00:10:14,760 --> 00:10:17,930 Jaki jest najbardziej efektywny sposób sortować milion 32-bitowe liczby całkowite? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Przepraszam, Maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nie, nie, nie. 210 00:10:27,400 --> 00:10:30,700 Myślę, że coś w rodzaju bańki byłoby tak droga. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Daj spokój, który powiedział mu to? 213 00:10:38,180 --> 00:10:40,590 Nie widziałem komputer Nauka w tle. 214 00:10:40,590 --> 00:10:42,130 >> -Mamy Naszych szpiegów tam. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Zapytajmy inaczej Wywiad pytanie. 217 00:10:48,444 --> 00:10:49,300 >> [KONIEC ODTWARZANIE] 218 00:10:49,300 --> 00:10:52,290 >> Głośnik: Tak mówi o choć, konkretne numery 219 00:10:52,290 --> 00:10:53,890 nie będzie wszystko, co użyteczne. 220 00:10:53,890 --> 00:10:56,810 To nie jest życie, że bańka lekcja sortowania, ponieważ milion wejść, 221 00:10:56,810 --> 00:10:58,590 może zająć aż 500 miliardów kroków. 222 00:10:58,590 --> 00:11:01,120 Naprawdę nie można generalizować z tego zbyt skutecznie 223 00:11:01,120 --> 00:11:03,560 i podejmować dobre decyzje projektowe podczas pisania programów. 224 00:11:03,560 --> 00:11:07,070 Więc skupmy się jednak, w jaki sposób możemy uprościć ten wynik. 225 00:11:07,070 --> 00:11:11,780 >> Więc ja tu zaznaczony na żółto Wynik n kwadratu podzielony przez 2, 226 00:11:11,780 --> 00:11:14,330 tak mln kwadratu dzielona przez 2, a potem 227 00:11:14,330 --> 00:11:16,710 Podświetlony, co mam Najlepsza odpowiedź była 228 00:11:16,710 --> 00:11:20,180 raz możemy odjąć od n dzieli się przez 2. 229 00:11:20,180 --> 00:11:24,850 I roszczenia Zamierzam zrobić to, kto do cholery obchodzi, jeśli odjąć od 230 00:11:24,850 --> 00:11:30,060 trochę stary n nad 2, gdy pierwszy część tej formuły jest więc znacznie większy? 231 00:11:30,060 --> 00:11:33,910 Dominuje inne Termin, n do kwadratu podzielić przez 2 232 00:11:33,910 --> 00:11:37,510 jest więc znacznie większy, wyraźnie, jak n pobiera duże jak milion, 233 00:11:37,510 --> 00:11:41,450 że tam jest naprawdę duża różnica w Koniec dni pomiędzy 500000000000 234 00:11:41,450 --> 00:11:45,730 i 499999500000? 235 00:11:45,730 --> 00:11:46,349 Nie bardzo. 236 00:11:46,349 --> 00:11:48,640 A więc to, co mamy zamiar zrobić, jak to informatycy 237 00:11:48,640 --> 00:11:53,270 zignorować te warunki zamówienia i niższe wziąć coś takiego i naprawdę 238 00:11:53,270 --> 00:11:56,050 tylko do uproszczenia Określenie, że będzie to znaczenia. 239 00:11:56,050 --> 00:12:00,315 Większe nasze zbiory danych, tym większe nasze bazy danych, tym więcej stron internetowych 240 00:12:00,315 --> 00:12:02,690 musimy szukać, więcej przyjaciele masz na Facebooku. 241 00:12:02,690 --> 00:12:07,340 >> Jak n staje się większy, że jesteśmy naprawdę zamiar dbać o największym 242 00:12:07,340 --> 00:12:11,560 Termin w takiej analizie nasza wydajność algorytmów. 243 00:12:11,560 --> 00:12:16,230 I mam zamiar powiedzieć, że wiesz, co, Sortowanie bąbelkowe jest na porządku Big O, 244 00:12:16,230 --> 00:12:18,060 rzędu n do kwadratu. 245 00:12:18,060 --> 00:12:20,090 To nie jest dokładnie n kwadratu, jak widzieliśmy, 246 00:12:20,090 --> 00:12:22,060 ale kogo to obchodzi chodzi o tych mniejszych, 247 00:12:22,060 --> 00:12:24,390 i szczerze mówiąc, kto naprawdę obchodzi, dzielimy przez 2? 248 00:12:24,390 --> 00:12:25,870 To tylko czynnikiem stałym. 249 00:12:25,870 --> 00:12:29,480 I jest w porównaniu do 250 500 miliardów mld naprawdę to nic wielkiego? 250 00:12:29,480 --> 00:12:32,190 Mogę tylko czekać na jeden rok, niech mój laptop dosłownie 251 00:12:32,190 --> 00:12:34,810 się dwa razy szybciej w sprzęcie, i tego rodzaju różnicy 252 00:12:34,810 --> 00:12:36,650 po prostu zniknie w sposób naturalny w czasie. 253 00:12:36,650 --> 00:12:39,300 >> Co dbamy o to Wyrażenie część 254 00:12:39,300 --> 00:12:42,489 wyrażenia, które będzie się zmieniać jako nasz wkład robi się coraz większy i większy. 255 00:12:42,489 --> 00:12:45,280 I rzeczywiście, w prawdziwym świecie, że to, co dzieje się w coraz większym stopniu 256 00:12:45,280 --> 00:12:48,330 ma wejść do naszych problemów i Algorytmy są coraz większe. 257 00:12:48,330 --> 00:12:53,470 Tak duże O będzie zapis, asymptotycznej zapis, że po prostu 258 00:12:53,470 --> 00:12:57,160 używać jako informatycy, aby opisać wydajność, lub czas pracy, 259 00:12:57,160 --> 00:12:58,130 algorytmu. 260 00:12:58,130 --> 00:13:00,800 Tak, że możemy porównać algorytmy pisanych na różnych komputerach 261 00:13:00,800 --> 00:13:04,170 przez różne osoby, stosując niektóre zasadniczo podobny metryczne 262 00:13:04,170 --> 00:13:07,557 jak liczby porównań jesteś co, a może liczby swapów 263 00:13:07,557 --> 00:13:08,140 robisz. 264 00:13:08,140 --> 00:13:11,910 >> Co my nie zamierzamy Ilość jest czas 265 00:13:11,910 --> 00:13:13,981 który przechodzi na zegarze na typowo ścianie. 266 00:13:13,981 --> 00:13:16,230 Co nie będziemy się martwić o to, ile pamięci 267 00:13:16,230 --> 00:13:17,820 używasz dzisiaj na najmniej, choć to 268 00:13:17,820 --> 00:13:19,370 inny zasób możemy zmierzyć. 269 00:13:19,370 --> 00:13:23,610 Mamy zamiar spróbować oprzeć nasze analizy na zaledwie podstawowych operacji, te, 270 00:13:23,610 --> 00:13:25,930 szczerze, że można zobaczyć najbardziej wizualnie. 271 00:13:25,930 --> 00:13:30,700 Więc coś jak Big O n do kwadratu, to twierdzą, że O n do kwadratu 272 00:13:30,700 --> 00:13:35,820 jest górne ograniczenie tzw czas bubble rodzaju systemem. 273 00:13:35,820 --> 00:13:38,820 Innymi słowy, jeśli chciał twierdzić, że nie ma 274 00:13:38,820 --> 00:13:41,370 ta górna granica liczby kroków algorytmu może podjąć, 275 00:13:41,370 --> 00:13:46,240 to będzie w wielkim O n obrobione w tym przypadku górna granica. 276 00:13:46,240 --> 00:13:49,710 >> Co zrobić, jeśli zamiast zmienić historia się nie o sortowanie bąbelkowe, 277 00:13:49,710 --> 00:13:50,910 ale o to górna granica. 278 00:13:50,910 --> 00:13:54,030 Można myśleć o algorytmie że poznaliśmy już wcześniej 279 00:13:54,030 --> 00:13:59,530 którego górna granica, maksymalna pomiaru czasu lub działań, 280 00:13:59,530 --> 00:14:04,300 to być uznane za ograniczone przez n, funkcja liniowa, 281 00:14:04,300 --> 00:14:07,260 nie jeden, który znajduje się kwadratowa zakrzywiona? 282 00:14:07,260 --> 00:14:10,780 Co to jest algorytm, który zawsze trwa dłużej 283 00:14:10,780 --> 00:14:12,860 nie jak krokach n, lub 2n kroków, lub kroki 3n? 284 00:14:12,860 --> 00:14:13,360 Tak? 285 00:14:13,360 --> 00:14:15,030 >> PUBLICZNOŚCI: Znalezienie Najwięcej na liście? 286 00:14:15,030 --> 00:14:16,930 >> GŁOŚNIK: Perfect, znalezienie Najwięcej na liście. 287 00:14:16,930 --> 00:14:18,940 Jeśli mam podano listę osób, na przykład, 288 00:14:18,940 --> 00:14:21,440 każdy kto trzyma numer, co jest maksymalną liczbę 289 00:14:21,440 --> 00:14:23,770 kroków powinien wziąć mnie, rozsądnie inteligentny człowiek, 290 00:14:23,770 --> 00:14:27,530 znaleźć największą osoby na tej liście? 291 00:14:27,530 --> 00:14:28,100 n, w porządku? 292 00:14:28,100 --> 00:14:31,320 Ponieważ w najgorszym przypadku, w którym Największą wartość może być? 293 00:14:31,320 --> 00:14:32,700 Prawo, aż w końcu. 294 00:14:32,700 --> 00:14:34,575 Tak więc w najgorszym przypadku górna granica, mogę 295 00:14:34,575 --> 00:14:36,450 musiał przejść całą drogę tu i być jak, 296 00:14:36,450 --> 00:14:39,170 O, tu jest numer osiem, lub cokolwiek to jest wartość nie jest. 297 00:14:39,170 --> 00:14:41,330 Teraz byłoby to po prostu głupie jeśli ja ruszyłem, prawda? 298 00:14:41,330 --> 00:14:43,840 Szukasz więcej i więcej elementów jeśli ostatni z nich jest tam? 299 00:14:43,840 --> 00:14:45,340 Więc na pewno, n jest górna granica. 300 00:14:45,340 --> 00:14:47,420 Nie trzeba podejmować więcej kroków niż to. 301 00:14:47,420 --> 00:14:51,580 >> Więc co, jeśli zamiast tego proponuje się, istnieją algorytmy, które w tym świecie 302 00:14:51,580 --> 00:14:57,750 mają czas, który jest systemem ograniczona przez duże O. dziennika n, log n? 303 00:14:57,750 --> 00:15:00,390 Gdzie widzieliśmy tego wcześniej? 304 00:15:00,390 --> 00:15:00,890 Tak? 305 00:15:00,890 --> 00:15:03,309 >> PUBLICZNOŚCI: W książce telefonicznej problemu? 306 00:15:03,309 --> 00:15:04,850 Głośnik: Jak problemu książki telefonicznej. 307 00:15:04,850 --> 00:15:07,754 Co było miarą wiele czasu i ile łez IT 308 00:15:07,754 --> 00:15:10,170 zajęło mi znaleźć kogoś takiego jak Mike Smith w książce telefonicznej? 309 00:15:10,170 --> 00:15:13,212 Twierdziliśmy, że to log n, a nawet jeśli nie zna albo jest 310 00:15:13,212 --> 00:15:15,170 trochę zamglone, co logarytm lub wykładnik był, 311 00:15:15,170 --> 00:15:17,650 Wystarczy pamiętać, że log n ogólnie odnosi się do procesu 312 00:15:17,650 --> 00:15:20,790 W tym przypadku dzielenia coś w połowie znowu, i znowu, 313 00:15:20,790 --> 00:15:25,790 i i znów, tak, że staje się coraz bardziej mały, jak to zrobić. 314 00:15:25,790 --> 00:15:28,470 >> Więc zalogować n odnosi, na pewno, na przykład w książce telefonicznej, 315 00:15:28,470 --> 00:15:32,662 do wyszukiwania binarnego w teorii, kiedy miał drzwi wirtualnych na pokładzie, 316 00:15:32,662 --> 00:15:34,370 lub gdy Sean szukając czegoś. 317 00:15:34,370 --> 00:15:37,374 Gdyby stosować wyszukiwanie binarne, log n byłaby górną granicę ile 318 00:15:37,374 --> 00:15:38,040 czas, który zajmuje. 319 00:15:38,040 --> 00:15:44,027 Ale te algorytmy, które biegły w log n zakłada Jaki klucz szczegół? 320 00:15:44,027 --> 00:15:45,360 Że lista została posortowana, tak? 321 00:15:45,360 --> 00:15:47,789 Twój algorytm jest nie tak, jeśli Twój wkład nie jest klasyfikowane, 322 00:15:47,789 --> 00:15:49,830 i jeszcze używasz coś jak wyszukiwanie binarne 323 00:15:49,830 --> 00:15:51,704 ponieważ można skakać tuż nad elementem 324 00:15:51,704 --> 00:15:53,600 nie zdając sobie sprawy, że to rzeczywiście nie. 325 00:15:53,600 --> 00:15:55,600 >> Teraz co to może oznaczać, Big O jednego? 326 00:15:55,600 --> 00:15:59,117 To nie znaczy, że twój algorytm trwa jeden i tylko jeden krok, 327 00:15:59,117 --> 00:16:01,200 to po prostu oznacza, że ​​trwa stałej liczby kroków. 328 00:16:01,200 --> 00:16:04,060 Może to 1, może to 10, może to 1000, 329 00:16:04,060 --> 00:16:07,750 ale to jest niezależne od Wielkość tego problemu. 330 00:16:07,750 --> 00:16:10,850 Bez względu na to, jak duże n, Stała czasowa algorytmu 331 00:16:10,850 --> 00:16:12,747 ma zawsze tę samą liczbę stopni. 332 00:16:12,747 --> 00:16:15,080 Więc co może być algorytm Rozmawialiśmy o lub po prostu 333 00:16:15,080 --> 00:16:20,418 intuicyjnie, że przychodzi do ciebie, że przebiega zawsze w tak zwanym stałym czasie? 334 00:16:20,418 --> 00:16:20,918 Tak? 335 00:16:20,918 --> 00:16:22,001 >> PUBLICZNOŚCI: Dodaj dwie liczby. 336 00:16:22,001 --> 00:16:25,320 Głośnik: Dodaj dwie liczby, 2 plus 2 równa się 4, zrobione. 337 00:16:25,320 --> 00:16:27,227 Tak, że może działać, co jeszcze? 338 00:16:27,227 --> 00:16:28,560 Jak o bardziej realnym świecie, tak? 339 00:16:28,560 --> 00:16:30,686 >> PUBLICZNOŚCI: Znalezienie Pierwszą rzeczą, na liście. 340 00:16:30,686 --> 00:16:32,810 Głośnik: Znalezienie pierwszy elementu na liście, na pewno. 341 00:16:32,810 --> 00:16:34,540 Mamy faktycznie rozmawia o już tablic, 342 00:16:34,540 --> 00:16:36,540 jak masz na Pierwszy element tablicy 343 00:16:36,540 --> 00:16:40,465 niezależnie od tego, jak długo Tablica jest w kod C? 344 00:16:40,465 --> 00:16:43,090 Po prostu użyć jak wspornika Zapis zero, bam, że tam jesteś. 345 00:16:43,090 --> 00:16:46,120 I rzeczywiście, jak tablice, na bok, Wsparcie coś ogólnie znane 346 00:16:46,120 --> 00:16:49,240 jako losowy dostęp losowy dostęp pamięci, ponieważ można dosłownie 347 00:16:49,240 --> 00:16:50,284 przejście do jednego miejsca. 348 00:16:50,284 --> 00:16:52,700 Możemy to zrobić jeszcze prościej możemy przewinąć do tygodnia zerowego 349 00:16:52,700 --> 00:16:53,900 kiedy zrobiliśmy Scratch. 350 00:16:53,900 --> 00:16:59,707 Ile czasu zajęło Say w Scratch do wykonania? 351 00:16:59,707 --> 00:17:00,790 Tylko stały czas, prawda? 352 00:17:00,790 --> 00:17:03,960 Powiedz coś, powiedzieć coś, to nie ma znaczenia 353 00:17:03,960 --> 00:17:07,359 Jak duży Rysy świat jest, to zawsze będzie mieć taką samą ilość czasu 354 00:17:07,359 --> 00:17:08,490 po prostu coś powiedzieć. 355 00:17:08,490 --> 00:17:11,089 >> Więc to jest stała czasowa, ale co druga strona? 356 00:17:11,089 --> 00:17:13,030 Jeśli to była górna granice, co, jeśli chcemy 357 00:17:13,030 --> 00:17:17,089 opisać dolną granicę naszych algorytmów działa czas? 358 00:17:17,089 --> 00:17:19,852 Prawie najlepszym przypadku potencjalnie, jeśli chcesz, 359 00:17:19,852 --> 00:17:23,060 choć terminy te mogą mieć zastosowanie do najlepiej skrzynki, najgorszych przypadkach średnie przypadki więcej 360 00:17:23,060 --> 00:17:26,359 ogólnie, ale niech po prostu skupić się na dolnych granicach ogólnie. 361 00:17:26,359 --> 00:17:31,920 Co to jest algorytm, który ma dolna granica n krokach, 362 00:17:31,920 --> 00:17:33,350 lub 2n kroków, lub kroki 3n? 363 00:17:33,350 --> 00:17:36,241 Niektóre czynnik n krokach, to jej dolnej granicy. 364 00:17:36,241 --> 00:17:36,740 Tak? 365 00:17:36,740 --> 00:17:37,910 >> PUBLICZNOŚCI: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> Głośnik: Bubble sort bierze Ci minimalnie n kroków, dlaczego? 367 00:17:41,610 --> 00:17:42,279 Dlaczego tak jest? 368 00:17:42,279 --> 00:17:45,320 Dlaczego warto, że początek przyjść do Ciebie intuicyjnie, nawet jeśli to nie wystarczy 369 00:17:45,320 --> 00:17:46,530 jeszcze? 370 00:17:46,530 --> 00:17:47,030 Tak? 371 00:17:47,030 --> 00:17:47,990 >> PUBLICZNOŚCI: [niesłyszalne]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Głośnik: Dokładnie. 374 00:17:52,360 --> 00:17:55,810 W najlepszy możliwy scenariusz Sortowanie bąbelkowe i wiele algorytmów, 375 00:17:55,810 --> 00:17:58,769 jeśli oddam ci osiem osób którzy są już posortowane, 376 00:17:58,769 --> 00:18:00,560 byłoby głupotą dla Ciebie, algorytm, 377 00:18:00,560 --> 00:18:02,202 do tam iz powrotem więcej niż raz, prawda? 378 00:18:02,202 --> 00:18:04,285 Bo jak tylko Ciebie przejść przez listy raz, 379 00:18:04,285 --> 00:18:08,090 należy zdać sobie sprawę, och, nie zrobiłem swapy, ta lista jest posortowana, zjazd. 380 00:18:08,090 --> 00:18:09,700 Ale to zajmie ci n kroków. 381 00:18:09,700 --> 00:18:12,033 >> I odwrotnie, co jest kolejnym sposób myślenia o nim? 382 00:18:12,033 --> 00:18:15,240 Sortowanie bąbelkowe jest omega, że tak powiem, n, 383 00:18:15,240 --> 00:18:19,050 bo jeśli spojrzeć na mniej niż n elementów, co 384 00:18:19,050 --> 00:18:23,009 Zasadniczą kwestią jest tam? 385 00:18:23,009 --> 00:18:24,550 Nie wiem, czy to jest klasyfikowane, prawda. 386 00:18:24,550 --> 00:18:26,800 My, ludzie, może spojrzenie na ośmiu osób i być jak, och, to sortowane, 387 00:18:26,800 --> 00:18:28,430 że nie wziął mnie n kroków, ale to zrobiłem. 388 00:18:28,430 --> 00:18:30,810 Twoje oczy, nawet jeśli rodzaj z ma duże pole widzenia, 389 00:18:30,810 --> 00:18:33,184 spojrzał na ośmiu elementów, spojrzał na osiem osób, 390 00:18:33,184 --> 00:18:34,610 to osiem stopni skutecznie. 391 00:18:34,610 --> 00:18:38,612 I tylko wtedy, gdy idę przez cały lista nie rozumiem, tak, sortowane. 392 00:18:38,612 --> 00:18:41,320 Gdybym przerwanie myśli, wszystko Dobrze, że to całkiem klasyfikowane do tej pory, 393 00:18:41,320 --> 00:18:42,520 jakie są szanse, że nie sortowane? 394 00:18:42,520 --> 00:18:44,186 Że nie będzie algorytmy prawidłowe. 395 00:18:44,186 --> 00:18:46,250 Może być szybsze, ale błędne. 396 00:18:46,250 --> 00:18:48,500 >> Więc teraz mamy drogę Opisywanie niższe granice, 397 00:18:48,500 --> 00:18:49,710 i co o stałym czasie? 398 00:18:49,710 --> 00:18:54,565 Co jest algorytmem, który ma niższe związany od jego czasu pracy w jednym? 399 00:18:54,565 --> 00:18:58,350 1 krok, 2 stopnie, 10 stopni, ale stała, niezależnie od n, 400 00:18:58,350 --> 00:18:59,310 Powierzchnia wejścia? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Tak, w plecy. 403 00:19:04,600 --> 00:19:05,309 >> PUBLICZNOŚCI: printf? 404 00:19:05,309 --> 00:19:06,183 Głośnik: Co to jest? 405 00:19:06,183 --> 00:19:07,184 PUBLICZNOŚCI: printf? 406 00:19:07,184 --> 00:19:07,850 GŁOŚNIK: printf. 407 00:19:07,850 --> 00:19:08,400 OK, na pewno. 408 00:19:08,400 --> 00:19:10,720 Więc to ma stałą liczbę kroków. 409 00:19:10,720 --> 00:19:13,170 I mam teraz-- teraz mówimy o kod C 410 00:19:13,170 --> 00:19:16,040 i nie podstaw, coś jak powiedzmy, z printf, 411 00:19:16,040 --> 00:19:17,710 powinniśmy zacząć się uważać. 412 00:19:17,710 --> 00:19:21,090 Ponieważ printf bierze wejście, to ciąg, 413 00:19:21,090 --> 00:19:23,220 i łańcuchy nie mają długość technicznie. 414 00:19:23,220 --> 00:19:25,530 Jeśli więc teraz chcą odebrać na ciebie, jeśli nie masz nic przeciwko, 415 00:19:25,530 --> 00:19:29,430 technicznie możemy twierdzić, że printf bierze wejście zmiennej długości, 416 00:19:29,430 --> 00:19:32,270 i na pewno może zająć więcej Czas wydrukowania ciąg tak długo, 417 00:19:32,270 --> 00:19:33,560 od tej długości. 418 00:19:33,560 --> 00:19:36,570 >> Więc co, jeśli weźmiemy pod uwagę tylko sortowanie i wyszukiwanie przykładów? 419 00:19:36,570 --> 00:19:40,450 Co Mike Smith w telefonie książka, lub bardziej ogólnie binarne wyszukiwania? 420 00:19:40,450 --> 00:19:42,220 W najlepszym przypadku, co może się zdarzyć? 421 00:19:42,220 --> 00:19:45,577 Otworzyć książkę telefoniczną i, bam, jest liczba Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Mogę zadzwonić do niego od razu. 423 00:19:46,660 --> 00:19:49,390 >> Zrobił krok, może dwa kroki, a stałą ilość kroków 424 00:19:49,390 --> 00:19:50,230 jeśli mam szczęście. 425 00:19:50,230 --> 00:19:52,570 I szczerze mówiąc, widzieliśmy na Poniedziałek twój kolega 426 00:19:52,570 --> 00:19:54,710 się dość szczęśliwy dwa razy z rzędu. 427 00:19:54,710 --> 00:19:57,050 I to było rzeczywiście stała czas w niższych granicach 428 00:19:57,050 --> 00:20:01,280 algorytmu określonego do znalezienia Numer 50 za te zamknięte 429 00:20:01,280 --> 00:20:01,830 drzwi. 430 00:20:01,830 --> 00:20:06,400 >> Teraz, jak na bok, jeśli odkryjesz że zarówno duże O, górne, 431 00:20:06,400 --> 00:20:09,310 i omega, dolna granica, są jedna identyczne, 432 00:20:09,310 --> 00:20:11,830 Jest w ten sam wzór nawiasy, można również 433 00:20:11,830 --> 00:20:15,170 powiedzieć, po prostu być wyszukane, że coś jest w teta 434 00:20:15,170 --> 00:20:18,270 n lub teta innej wartości. 435 00:20:18,270 --> 00:20:20,661 To oznacza, że ​​gdy duże O i omega są takie same. 436 00:20:20,661 --> 00:20:21,910 Teraz to, co o wybór rodzaju? 437 00:20:21,910 --> 00:20:23,400 Użyjmy tego nowego słownictwa. 438 00:20:23,400 --> 00:20:27,407 W selekcji rodzaju, co byliśmy robi znowu, i znowu, i znowu? 439 00:20:27,407 --> 00:20:29,990 Byłem tam iz powrotem przez listę, szukając kogo? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Najmniejsza liczba. 442 00:20:34,730 --> 00:20:37,560 >> Tak jak wiele kroków, jak I zrobił wiele porównań 443 00:20:37,560 --> 00:20:43,250 trzeba zrobić, aby dowiedzieć się, kto najmniejszy element listy jest? 444 00:20:43,250 --> 00:20:44,437 n minus 1, prawda? 445 00:20:44,437 --> 00:20:47,770 Bo jeśli po prostu zacząć z jednego jestem podane i zaczynam porównanie mu, 446 00:20:47,770 --> 00:20:49,519 następnie go lub ją, nim albo ona, on czy ona, że 447 00:20:49,519 --> 00:20:52,010 można powiązać tylko elementy razem n minus 1 razy. 448 00:20:52,010 --> 00:20:55,630 Więc wybór sortowania podobnie trwa n minus 1 kroki po raz pierwszy. 449 00:20:55,630 --> 00:20:59,540 >> Ile kroków zajmuje mi znajdź drugi najmniejszy element? 450 00:20:59,540 --> 00:21:02,920 n minus 2, bo jest głupi jestem jeśli Ciągle patrząc na tych samych ludzi, 451 00:21:02,920 --> 00:21:06,280 ponownie, jeśli go już wybrany lub jej i umieścić je w ich miejsce. 452 00:21:06,280 --> 00:21:09,270 Oraz trzeci krok, n minus 3, to n minus 4. 453 00:21:09,270 --> 00:21:11,020 Widzieliśmy ten wzór Przed i rzeczywiście 454 00:21:11,020 --> 00:21:13,460 Wybór sortowania podobnie ma górnej granicy 455 00:21:13,460 --> 00:21:16,210 n do kwadratu, jeśli robimy się, że sumowanie. 456 00:21:16,210 --> 00:21:19,790 Co jest jej dolnej granicy, wybór sortowania? 457 00:21:19,790 --> 00:21:25,350 Minimalnie, ile czasu musi wybór Sortuj wziąć, jak określono to w poniedziałek? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Proponuję dwie opcje. 460 00:21:30,490 --> 00:21:32,360 Może to n, jak poprzednio. 461 00:21:32,360 --> 00:21:35,040 Może to n do kwadratu, jak to jest teraz w górnej granicy. 462 00:21:35,040 --> 00:21:35,874 >> PUBLICZNOŚCI: n do kwadratu. 463 00:21:35,874 --> 00:21:36,664 Głośnik: n do kwadratu. 464 00:21:36,664 --> 00:21:37,368 Dlaczego? 465 00:21:37,368 --> 00:21:40,060 >> PUBLICZNOŚCI: Bo masz zdefiniować [niesłyszalne]. 466 00:21:40,060 --> 00:21:41,510 >> Głośnik: Dokładnie. 467 00:21:41,510 --> 00:21:45,077 Przynajmniej jak zdefiniowano wyboru rodzaju to dość naiwne, nie poddawać się, 468 00:21:45,077 --> 00:21:46,160 Najkorzystniejsze najmniejszy element. 469 00:21:46,160 --> 00:21:47,770 Idź jeszcze raz, znaleźć najmniejszy element. 470 00:21:47,770 --> 00:21:49,490 Idź jeszcze raz, znaleźć najmniejszy element. 471 00:21:49,490 --> 00:21:51,700 Nie ma rodzaj tam, że optymalizacja 472 00:21:51,700 --> 00:21:54,350 może dać mi przerwać po tylko brak lub tak kroki. 473 00:21:54,350 --> 00:21:57,080 Tak więc w rzeczywistości, wybór sortowania, omega n do kwadratu. 474 00:21:57,080 --> 00:22:00,667 >> Co wstawiania rodzaju, gdzie odbył który dostałem, a potem koleś go 475 00:22:00,667 --> 00:22:01,750 lub jej we właściwym miejscu? 476 00:22:01,750 --> 00:22:04,958 Potem udał się do drugiej osoby, koleś go lub ją w odpowiednim miejscu. 477 00:22:04,958 --> 00:22:07,910 Potem następna osoba, koleś go lub ją w odpowiednim miejscu. 478 00:22:07,910 --> 00:22:10,537 Zauważ, że jest to bardzo liniowa, że ​​tak powiem. 479 00:22:10,537 --> 00:22:12,620 Jestem prosta, jestem nie tam iz powrotem, 480 00:22:12,620 --> 00:22:16,080 Nigdy nie oglądając się naprawdę, ale co się dzieje po włożeniu go 481 00:22:16,080 --> 00:22:20,302 lub jej na początku lista jak my w poniedziałek? 482 00:22:20,302 --> 00:22:21,010 Co się dzieje? 483 00:22:21,010 --> 00:22:21,510 Tak? 484 00:22:21,510 --> 00:22:23,122 PUBLICZNOŚCI: [niesłyszalne]. 485 00:22:23,122 --> 00:22:24,830 Głośnik: Tak, był haczyk, prawda? 486 00:22:24,830 --> 00:22:26,746 Może pamiętacie z Twoi koledzy z klasy, jeśli 487 00:22:26,746 --> 00:22:29,670 robili żadnego ruchu z ich stopy, to było działanie. 488 00:22:29,670 --> 00:22:33,610 Więc gdyby nie było tu trzy osoby Nowa osoba należała droga tam, 489 00:22:33,610 --> 00:22:37,360 na długim etapie, jak to, na pewno, że lub może po prostu udać się do samego końca. 490 00:22:37,360 --> 00:22:40,074 Ale jeśli myślimy o komputer i tablica pamięci, 491 00:22:40,074 --> 00:22:41,990 osoby te będą mieć na shuffle 492 00:22:41,990 --> 00:22:43,260 aby zrobić miejsce dla tej osoby. 493 00:22:43,260 --> 00:22:46,930 I tak, że n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings tylko rodzaj dzieje za mną, nie przede mną 495 00:22:50,660 --> 00:22:52,710 , jak powyżej, w pewnym sensie. 499 00:22:52,557 --> 00:22:54,640 Teraz, jak na bok, a jak mogłeś online 500 00:22:54,640 --> 00:22:57,699 jeśli zaczniesz grzebać o rodzaju, nie ma tak wiele różnych te 501 00:22:57,699 --> 00:22:59,490 tam, niektóre z nich lepiej niż inne. 502 00:22:59,490 --> 00:23:02,200 Rzeczywiście, jest bogosort to rodzaj zabawy, aby sprawdzić. 503 00:23:02,200 --> 00:23:06,650 Bogosort wykonuje szereg numery lub powiedzieć talię kart, 504 00:23:06,650 --> 00:23:09,870 losowo tasuje je i sprawdza, czy są one klasyfikowane. 505 00:23:09,870 --> 00:23:12,130 A jeśli nie, to czy go ponownie. 506 00:23:12,130 --> 00:23:14,140 A jeśli nie, to czy go ponownie. 507 00:23:14,140 --> 00:23:15,440 Jeśli nie, to robi to ponownie. 508 00:23:15,440 --> 00:23:17,060 Niewiarygodnie głupi. 509 00:23:17,060 --> 00:23:19,520 >> I rzeczywiście, jeśli czytasz jak Wikipedia, 510 00:23:19,520 --> 00:23:21,200 jego nick to głupi rodzaj. 511 00:23:21,200 --> 00:23:25,180 Doprowadzi pracy, miejmy nadzieję, że wystarczająco dużo czasu, 512 00:23:25,180 --> 00:23:28,240 ale, że czas może zająć trochę czasu. 513 00:23:28,240 --> 00:23:31,650 Więc jeśli mogę, niech przyspieszyć się od przykładu Mary Beth wcześniej, 514 00:23:31,650 --> 00:23:35,150 mając jeszcze kilka elementów, ale jeszcze dwa procesory. 515 00:23:35,150 --> 00:23:37,100 Dwie osoby, jeśli Ciebie nie przeszkadza łączenie mnie. 516 00:23:37,100 --> 00:23:40,972 Jak o 1 tutaj, i niech go-- nikogo tam? 517 00:23:40,972 --> 00:23:41,722 Nikt tam? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Ci z czarnym koszula, tak, chodź na dół. 520 00:23:44,190 --> 00:23:45,000 Dobra, jak masz na imię? 521 00:23:45,000 --> 00:23:45,720 >> PUBLICZNOŚCI: Peter. 522 00:23:45,720 --> 00:23:46,100 >> Głośnik: Co to jest? 523 00:23:46,100 --> 00:23:46,766 >> PUBLICZNOŚCI: Peter. 524 00:23:46,766 --> 00:23:49,450 Głośnik: Peter David, miło cię poznać. 525 00:23:49,450 --> 00:23:53,670 Dobra, mamy tu Peter, jeśli Ciebie chce przyjść na stół tutaj. 526 00:23:53,670 --> 00:23:54,550 A jak masz na imię? 527 00:23:54,550 --> 00:23:55,216 >> PUBLICZNOŚCI: Elena. 528 00:23:55,216 --> 00:23:55,970 Głośnik: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, miło cię poznać. 530 00:23:57,030 --> 00:23:58,060 Elena spotykają Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 I musimy Andrew się również tutaj, proszę. 533 00:24:02,290 --> 00:24:06,107 A twój wyzwaniem będzie się uporządkować talię kart. 534 00:24:06,107 --> 00:24:08,190 A jeśli nie znają, talia kart powinna ostatecznie 535 00:24:08,190 --> 00:24:11,064 być klasyfikowane trochę coś jak tego, gdzie zrobimy kluby, a następnie 536 00:24:11,064 --> 00:24:13,660 te piki, kiery i wtedy diamenty, od asa jako jeden, 537 00:24:13,660 --> 00:24:15,570 wszystko aż do króla. 538 00:24:15,570 --> 00:24:20,890 >> Karty Zamierzam dać będą 52 w ilości. 539 00:24:20,890 --> 00:24:23,160 Jedziemy do podobnie Czas cię za chwilę. 540 00:24:23,160 --> 00:24:26,410 Mamy zamiar rzucić Andrew na ekranie tutaj 541 00:24:26,410 --> 00:24:28,170 tak, aby przyglądać się, jak to zrobić. 542 00:24:28,170 --> 00:24:31,070 I tak że wszystko Jest to szczególnie widoczne 543 00:24:31,070 --> 00:24:33,490 są to karty dostałem na Amazon. 544 00:24:33,490 --> 00:24:42,861 Więc są już losowo sortowane i będziemy razem, gdy. 545 00:24:42,861 --> 00:24:44,610 I będziemy keep it real tym razem, 546 00:24:44,610 --> 00:24:47,820 więc mamy zamiar spróbować na Ciebie naciskać bo inaczej to będzie nudne 547 00:24:47,820 --> 00:24:48,460 szybko. 548 00:24:48,460 --> 00:24:53,860 Jeśli można przystąpić do sortowania 52 elementy ze sobą za pośrednictwem niektórych środków, teraz. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> I znowu, jak oglądać te robicie to, co w końcu 551 00:25:07,180 --> 00:25:10,200 będzie produkować oczywiste Wynik, myśleć o naprawdę 552 00:25:10,200 --> 00:25:12,962 jak oni sobie robią, jak można to opisać. 553 00:25:12,962 --> 00:25:15,045 Ponieważ znów są Wszystkie procesy, algorytmy 554 00:25:15,045 --> 00:25:17,090 które bierzemy za pewnik, jako człowiek. 555 00:25:17,090 --> 00:25:22,349 Ale to prawdopodobnie dawna intuicja, jeszcze na długo przed tobą 556 00:25:22,349 --> 00:25:24,390 myślał o podjęciu ci klasy informatyka 557 00:25:24,390 --> 00:25:27,223 Może miał intuicję z który do rozwiązywania problemów, takich jak ten. 558 00:25:27,223 --> 00:25:29,560 Ale kiedy uznają wzorce i rozpocząć 559 00:25:29,560 --> 00:25:32,407 sformalizowanie czynności, z którymi jesteś rozwiązywania tych problemów, 560 00:25:32,407 --> 00:25:35,490 przekonasz się, że można rozwiązać wiele ciekawsza i dużo bardziej skomplikowana 561 00:25:35,490 --> 00:25:39,190 problemy szybko. 562 00:25:39,190 --> 00:25:42,351 Więc ktoś z publiczności, co jest co najmniej jeden element algorytmu 563 00:25:42,351 --> 00:25:43,350 że używamy tutaj? 564 00:25:43,350 --> 00:25:44,275 >> PUBLICZNOŚCI: [niesłyszalne] 565 00:25:44,275 --> 00:25:45,150 Głośnik: Co to jest? 566 00:25:45,150 --> 00:25:47,062 PUBLICZNOŚCI: Przez kolorze. 567 00:25:47,062 --> 00:25:47,770 Głośnik: Przez kolorze. 568 00:25:47,770 --> 00:25:50,630 Więc najpierw ich grupowanie wszystkich diamentów razem 569 00:25:50,630 --> 00:25:52,560 Wydaje się, że wszyscy serca razem jak się wydaje, 570 00:25:52,560 --> 00:25:56,520 i tak dalej, bez odniesieniu dla numerów na kartach. 571 00:25:56,520 --> 00:26:00,900 Teraz pojawiają się, na przykład, do sortowania ich liczby. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Bardzo dobre. 574 00:26:08,910 --> 00:26:12,370 >> Dobra, więc co się końcowy etap to tutaj? 575 00:26:12,370 --> 00:26:16,950 Raz mamy cztery posortowane garnitury, co musimy zrobić do czterech palach 576 00:26:16,950 --> 00:26:20,059 W celu osiągnięcia jednego sortowane pokład, po prostu? 577 00:26:20,059 --> 00:26:21,350 Więc musimy połączyć je ponownie. 578 00:26:21,350 --> 00:26:25,160 >> Więc jest to ciekawy pomysł, który ponownie, śmiem twierdzić, jest bardzo intuicyjne, nawet 579 00:26:25,160 --> 00:26:28,140 jeśli nigdy nie mogło uderzył że rodzaj etykiety na nim. 580 00:26:28,140 --> 00:26:31,900 To fundamentalne pojęcie podzielenie Problem nie w połowie tego czasu 581 00:26:31,900 --> 00:26:33,410 lecz co najmniej na cztery kawałki. 582 00:26:33,410 --> 00:26:36,810 Rozwiązywanie prawie zasadniczo identyczne problemy 583 00:26:36,810 --> 00:26:40,480 oddzielnie od siebie, a następnie łączenie wyniki. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 I, doskonała, zrobione. 586 00:26:50,140 --> 00:26:52,140 Wszystko w porządku, duży okrągły oklasków, jeśli można. 587 00:26:52,140 --> 00:26:56,480 >> [Aplauz] 588 00:26:56,480 --> 00:26:59,740 >> Głośnik: nie mam pojęcia, co będzie z tym zrobić, ale tutaj jesteś. 589 00:26:59,740 --> 00:27:01,690 Dziękuję bardzo. 590 00:27:01,690 --> 00:27:04,660 Zobaczmy więc, dwie minuty i osiem sekund 591 00:27:04,660 --> 00:27:07,490 jeśli chcesz, aby zmierzyć się z przyjaciółmi. 592 00:27:07,490 --> 00:27:12,160 Co to będzie będzie zabrać z tego 593 00:27:12,160 --> 00:27:13,830 że możemy wykorzystać bardziej ogólnie? 594 00:27:13,830 --> 00:27:16,080 Dobrze, że powrót do Ta tablica z numerami, 595 00:27:16,080 --> 00:27:19,060 i wracam teraz do niektórych pseudokod pisaliśmy w przeszłości, 596 00:27:19,060 --> 00:27:22,080 i był to pseudokod dla rozwiązania problemu z książki telefonicznej. 597 00:27:22,080 --> 00:27:25,150 Przy czym w pseudokod I wyliczone bardziej metodyczny, 598 00:27:25,150 --> 00:27:28,400 opisać, jak ja bardzo intuicyjny Algorytm podziału ludzki telefon 599 00:27:28,400 --> 00:27:31,650 książka w połowie, powtarzać, powtarzać, powtarzać, dopóki nie znajdę kogoś takiego jak Mike Smith, 600 00:27:31,650 --> 00:27:33,790 jeśli jest on rzeczywiście w książce telefonicznej. 601 00:27:33,790 --> 00:27:37,610 >> Ale rodzaj stosowany co zadzwonię bardzo iteracyjne podejście tutaj, 602 00:27:37,610 --> 00:27:42,160 w szczególności zawiadomienia linia linia 8 i 11. 603 00:27:42,160 --> 00:27:46,750 To są dowody iteracyjny podejście, podejście pętli, 604 00:27:46,750 --> 00:27:49,040 bo to jest dokładnie zachowanie ich wywoływać. 605 00:27:49,040 --> 00:27:52,910 Linie te mówią idź do obu Linia trzy, i można trochę 606 00:27:52,910 --> 00:27:55,140 myśleć, że w Oko umysłu jako pętla. 607 00:27:55,140 --> 00:27:59,080 To mówi ci, aby wrócić do kroku trzy i powtarzam jeszcze raz, i jeszcze raz, 608 00:27:59,080 --> 00:28:00,010 i znowu. 609 00:28:00,010 --> 00:28:04,410 >> Ale co, jeśli wykorzystać kluczową ideę tutaj, że nie po raz ostatni, 610 00:28:04,410 --> 00:28:10,280 i uproszczenie linii 8 i Linia 11 i ich sąsiedzi 611 00:28:10,280 --> 00:28:12,840 jak tylko ten, w kolorze żółtym. 612 00:28:12,840 --> 00:28:16,480 To nie jest zasadniczo skraca pseudokod bardzo, 613 00:28:16,480 --> 00:28:20,530 ale to zasadniczo zmienia charakter mojego algorytmu. 614 00:28:20,530 --> 00:28:24,220 Co mam teraz powiedzieć W etapie 7, w kroku 10, 615 00:28:24,220 --> 00:28:29,140 jest, aby szukać Mike w ten sam sposób, 616 00:28:29,140 --> 00:28:31,580 lecz tylko w lewej połowa lub prawa połowa. 617 00:28:31,580 --> 00:28:33,420 >> Tak więc, innymi słowy, jeśli Zacznę od pierwszego kroku, 618 00:28:33,420 --> 00:28:36,150 odebrać książkę telefoniczną, otwarty na środku z książki telefonicznej, spojrzeć na nazwiska, 619 00:28:36,150 --> 00:28:39,010 jeśli Smith jest jednym na imię, zadzwoń Mike, jeszcze 620 00:28:39,010 --> 00:28:44,340 jeśli Smith jest wcześniej w książce Krok siódmy szukaj Mike lewej połowie książki. 621 00:28:44,340 --> 00:28:47,130 Ale że niby czuje się jak pozostawiając mnie to wisi, prawda? 622 00:28:47,130 --> 00:28:49,240 W kolorze żółtym, jest instrukcji, ale w jaki sposób 623 00:28:49,240 --> 00:28:51,870 szukaj Mike w lewo połowa z książki telefonicznej? 624 00:28:51,870 --> 00:28:54,210 Gdzie mam Algorytm z którą 625 00:28:54,210 --> 00:28:57,100 może szukać kogoś takiego jak Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Cóż, to gapi nam w twarz. 627 00:28:58,980 --> 00:29:03,090 Mogę dosłownie użyć dokładnie to samo Program skutecznie idzie do góry 628 00:29:03,090 --> 00:29:06,490 ponownie i ponownie uruchomiony te same linie kodu. 629 00:29:06,490 --> 00:29:10,610 >> Tak więc mimo, że powinien to poczuć jak trochę definicji cyklicznej 630 00:29:10,610 --> 00:29:13,480 dokąd się wybierasz, odpowiadając na czyjeś Pytanie tylko o rodzaj prośbą 631 00:29:13,480 --> 00:29:15,990 samo pytanie jeszcze raz, jak, dlaczego, dlaczego, dlaczego? 632 00:29:15,990 --> 00:29:21,580 W rzeczywistości jest to trudne, ponieważ mamy zakodowane Kilka specjalnych linii, etap 4, 633 00:29:21,580 --> 00:29:25,320 który, jeśli a etap 12, która jest faktycznie inny oddział, 634 00:29:25,320 --> 00:29:30,120 ponieważ mamy te środki prowizorka, algorytm ten wygasa, jeżeli 635 00:29:30,120 --> 00:29:32,050 znaleźć Mike, lub jeśli nie mamy. 636 00:29:32,050 --> 00:29:36,810 Ale w kroku 7 i 10 Teraz mamy to, co my nazywamy algorytmu rekurencyjnego. 637 00:29:36,810 --> 00:29:40,420 A rekurencja jest rzeczywiście potężna idea to trochę umysł gięcia w pierwszym, 638 00:29:40,420 --> 00:29:42,500 , które można obecnie stosować w sposób następujący. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort będzie ostatni sort, że przyjrzymy się, co najmniej w klasie formalnie. 640 00:29:46,600 --> 00:29:50,040 I jest to zasadniczo różne z tych trzech ostatnich, a na pewno 641 00:29:50,040 --> 00:29:52,140 Ostatnie cztery jeśli to bogosort. 642 00:29:52,140 --> 00:29:54,810 Oto pseudokod do seryjnej rodzaju. 643 00:29:54,810 --> 00:30:00,170 Gdy na wejściu n elementów, więc biorąc pod uwagę Tablica wielkości n, gdy n jest mniejsze niż 2, 644 00:30:00,170 --> 00:30:01,040 powrót. 645 00:30:01,040 --> 00:30:03,610 Więc dlaczego mam, że rozsądek sprawdzić w pierwszej kolejności? 646 00:30:03,610 --> 00:30:09,477 Co jest implikacja jeśli oddam ci Tablica o długości n jest mniejsze niż 2? 647 00:30:09,477 --> 00:30:11,060 To już posortowane, oczywiście, prawda? 648 00:30:11,060 --> 00:30:13,640 Ponieważ lista albo ma jeden element, który jest trywialny 649 00:30:13,640 --> 00:30:15,180 sortowane, bo to Jedyne, co tam. 650 00:30:15,180 --> 00:30:18,138 Albo, że to z wielkości zerowej, co oznacza, nie ma nic do sortowania, więc z natury 651 00:30:18,138 --> 00:30:18,720 jest klasyfikowane. 652 00:30:18,720 --> 00:30:20,410 Nie tylko nic złego nie. 653 00:30:20,410 --> 00:30:22,310 Więc to jest nasza tzw wariant podstawowy. 654 00:30:22,310 --> 00:30:24,440 >> Który jest podobny w duchu do tego, co zrobiliśmy z Mike. 655 00:30:24,440 --> 00:30:26,023 Jeśli Mike w książce telefonicznej, zadzwonić do niego. 656 00:30:26,023 --> 00:30:27,740 Jeśli go tam nie ma, zrezygnować. 657 00:30:27,740 --> 00:30:31,240 To tak zwane bazowym, aby upewnić algorytm na koniec dnia 658 00:30:31,240 --> 00:30:33,540 zatrzyma się w pewnych okolicznościach. 659 00:30:33,540 --> 00:30:37,890 >> Ale tutaj jest skok wiary teraz, jeszcze, sortować lewą połowę elementów, 660 00:30:37,890 --> 00:30:39,740 następnie posortować prawo połowa elementów 661 00:30:39,740 --> 00:30:41,189 a następnie połączyć posortowane połówki. 662 00:30:41,189 --> 00:30:43,230 I tu czuje jakbyśmy copping się. 663 00:30:43,230 --> 00:30:46,900 Poprosiłem cię do sortowania n elementów, a ja jestem 664 00:30:46,900 --> 00:30:50,712 mówiąc: OK, czy to przez sortowanie w lewo i prawo do sortowania. 665 00:30:50,712 --> 00:30:52,420 Ale mówię jeden Inna rzecz, i to 666 00:30:52,420 --> 00:30:55,530 jest kluczowym tematem wydaje się w intuicji dotąd 667 00:30:55,530 --> 00:30:57,380 jest to trzeci etap łączenia. 668 00:30:57,380 --> 00:31:00,430 Które, mimo to wydaje się tak głupie w duchu, 669 00:31:00,430 --> 00:31:02,320 jak tylko połączyć rzeczy łącznie, wydaje 670 00:31:02,320 --> 00:31:05,380 być kluczowym krokiem w kierunku ponowny montaż dwóch problemów, które 671 00:31:05,380 --> 00:31:07,330 podzielono ostatecznie na pół. 672 00:31:07,330 --> 00:31:12,090 >> Więc scalanie sortowanie, zróbmy to, jeśli będziesz humor mi, z jednej większej demonstracji, 673 00:31:12,090 --> 00:31:14,730 po prostu tak, że mamy jakiś numery pracować. 674 00:31:14,730 --> 00:31:19,470 Czy mogę wymienić osiem stres Piłki dla ośmiu osób? 675 00:31:19,470 --> 00:31:29,320 Dobrze, jak o tobie trzy, to cztery w niniejszej sekcji, pięć, sześć, a niech 676 00:31:29,320 --> 00:31:30,720 nie 7, 8, dalej w górę. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, tak OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, tam idziemy plus 1. 680 00:31:38,640 --> 00:31:39,150 Doskonałe. 681 00:31:39,150 --> 00:31:42,000 Dobra chodź, niech szybko daje numery. 682 00:31:42,000 --> 00:31:50,800 Numer dwa, numer trzy, numer cztery, numer pięć, sześć, siedem, osiem. 683 00:31:50,800 --> 00:31:52,140 Zrobiłem osiem poprawnie tym razem. 684 00:31:52,140 --> 00:31:56,390 >> OK, więc śmiało, jeśli można, i niech sortować w oryginalnej kolejności 685 00:31:56,390 --> 00:31:59,810 że mieliśmy wczoraj który wyglądał tak, jeśli nie masz nic przeciwko. 686 00:31:59,810 --> 00:32:03,620 I zróbmy to przed tabelą. 687 00:32:03,620 --> 00:32:06,510 W porządku, więc scalić rodzaju. 688 00:32:06,510 --> 00:32:08,820 To jest, gdzie to się dzieje aby uzyskać rodzaju ciekawych, 689 00:32:08,820 --> 00:32:12,800 bo wydaje się dawać sobie więc dziś znacznie mniej informacji. 690 00:32:12,800 --> 00:32:15,149 >> Więc łączyć przede wszystkim sortowania na wejściu n elementów, 691 00:32:15,149 --> 00:32:18,440 i oczywiście nie mniej niż dwa, to osiem, więc mam jeszcze trochę do zrobienia. 692 00:32:18,440 --> 00:32:21,140 Więc teraz my jako psychicznie klasy są obecnie w branży innego, 693 00:32:21,140 --> 00:32:22,540 co oznacza, że ​​trzy kroki. 694 00:32:22,540 --> 00:32:25,017 Po pierwsze, muszę uporządkować Lewa połowa elementów. 695 00:32:25,017 --> 00:32:26,350 Więc jak mam to zabrać? 696 00:32:26,350 --> 00:32:28,950 Cóż, mam zamiar trochę psychicznie podzielić listę tutaj, 697 00:32:28,950 --> 00:32:30,700 nie masz do fizycznie przenieść, a ja jestem 698 00:32:30,700 --> 00:32:33,180 zamiar skupić się tylko na lewa połowa tu elementów. 699 00:32:33,180 --> 00:32:36,770 Więc jak mam go o sortowaniu lista teraz wielkości czterech? 700 00:32:36,770 --> 00:32:38,730 Jaki jest mój algorytm? 701 00:32:38,730 --> 00:32:42,580 Najpierw sprawdź to n mniej niż dwa, nie, więc przejść do bloku innego. 702 00:32:42,580 --> 00:32:43,900 Sortuj opuścił połowę elementów. 703 00:32:43,900 --> 00:32:45,608 >> Teraz znowu, psychicznie, i tam 704 00:32:45,608 --> 00:32:49,550 należy zdobyć wiele Historia psychicznego, jeśli będzie. 705 00:32:49,550 --> 00:32:51,940 Teraz jestem w lewo sortowania połowa lewej połowy. 706 00:32:51,940 --> 00:32:57,000 Dobrze, więc teraz ja nazywam moją samą seryjnej algorytm sortowania, to N mniej niż dwa? 707 00:32:57,000 --> 00:33:00,590 Nie, to jest dwa, więc mam do sortowania Lewa połowa i prawa połowa. 708 00:33:00,590 --> 00:33:02,042 Więc zaczynamy, uporządkować lewą połowę. 709 00:33:02,042 --> 00:33:03,750 Dlaczego nie można po prostu jeden krok do przodu. 710 00:33:03,750 --> 00:33:04,415 Jak masz na imię? 711 00:33:04,415 --> 00:33:04,860 >> PUBLICZNOŚCI: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Głośnik: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan podszedł. 714 00:33:06,040 --> 00:33:06,748 >> PUBLICZNOŚCI: Darren. 715 00:33:06,748 --> 00:33:09,000 Głośnik: Darren, zrobione. 716 00:33:09,000 --> 00:33:10,090 Powiedziałeś Darren lub Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBLICZNOŚCI: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Głośnik: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren zwiększyła do przodu, a on jest teraz posortowana. 720 00:33:14,422 --> 00:33:16,130 I to jest prawie idiotyczny zarzut, prawda? 721 00:33:16,130 --> 00:33:18,862 I naprawdę nie wydaje się być osiągnięcie cokolwiek, ale przejdźmy. 722 00:33:18,862 --> 00:33:20,820 Teraz pozwól mi uporządkować prawo połowa elementów. 723 00:33:20,820 --> 00:33:21,200 Jak masz na imię? 724 00:33:21,200 --> 00:33:21,690 >> PUBLICZNOŚCI: Luke. 725 00:33:21,690 --> 00:33:22,273 >> Prelegent: Łukasz. 726 00:33:22,273 --> 00:33:23,400 Chodź, krok do przodu. 727 00:33:23,400 --> 00:33:25,640 Sporządzono, mam posortowane Luke. 728 00:33:25,640 --> 00:33:28,570 Lewa połowa jest obecnie klasyfikowane i prawa połowa jest teraz posortowana, 729 00:33:28,570 --> 00:33:30,770 ale znowu, jest kluczowym krokiem tutaj. 730 00:33:30,770 --> 00:33:32,940 Czego potrzebujesz, aby zrobić następny? 731 00:33:32,940 --> 00:33:33,941 Scalić posortowane połówki. 732 00:33:33,941 --> 00:33:36,648 Teraz mamy zamiar po prostu wszyscy tam iz powrotem w ten sposób, 733 00:33:36,648 --> 00:33:38,620 bo niby trzeba niektóre miejsca na zarysowania. 734 00:33:38,620 --> 00:33:40,411 To prawie jak te faceci są na stole, 735 00:33:40,411 --> 00:33:42,460 i potrzebuję trochę miejsca ich przenoszenie na. 736 00:33:42,460 --> 00:33:44,170 Więc mam zamiar połączyć wy patrząc 737 00:33:44,170 --> 00:33:45,960 w lewej i prawej połowie połowę. 738 00:33:45,960 --> 00:33:48,740 I który oczywiście jest na pierwszym miejscu, w lewo lub w prawo, pół pół? 739 00:33:48,740 --> 00:33:52,710 Więc prawa połowa, więc przejdźmy Luke nad do pierwotnej pozycji Darrena. 740 00:33:52,710 --> 00:33:57,640 I teraz połączyć swoje lewą połowę w, Darren zamierza przenieść tam. 741 00:33:57,640 --> 00:33:59,750 >> Więc czuje się jak prawie Efekt sortowanie bąbelkowe, 742 00:33:59,750 --> 00:34:02,482 ale moim podstawowym algorytmem, bardzo różni się tym razem. 743 00:34:02,482 --> 00:34:04,815 Ale teraz jest, gdy robi się trochę denerwujące, bo ciebie 744 00:34:04,815 --> 00:34:06,810 trzeba przewinąć psychicznie Gdzie ja się. 745 00:34:06,810 --> 00:34:09,893 Właśnie połączyła posortowane połówki, co oznacza, że ​​jestem, gdzie w moim algorytmie? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Muszę uporządkować prawą połowę, prawda? 748 00:34:13,770 --> 00:34:15,910 >> Jeśli do tyłu, dosłownie na wideo, które będziesz 749 00:34:15,910 --> 00:34:18,339 widać, że mamy do tego punkt Łukasza i Darrenem 750 00:34:18,339 --> 00:34:21,370 sortując lewy połowa lewej połowy. 751 00:34:21,370 --> 00:34:23,430 Potem połączył te posortowane połówki, które 752 00:34:23,430 --> 00:34:27,941 oznacza, następnym krokiem jest sortowanie prawa połowa lewej połowy. 753 00:34:27,941 --> 00:34:29,649 Dobrze, więc niech to zrobić szybciej. 754 00:34:29,649 --> 00:34:33,282 Dobrze, sześć, idę zastrzeżenia jesteś teraz sortowane, dalej do przodu. 755 00:34:33,282 --> 00:34:33,990 Jak masz na imię? 756 00:34:33,990 --> 00:34:34,589 >> PUBLICZNOŚCI: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Głośnik: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano jest teraz posortowana. 759 00:34:36,010 --> 00:34:36,450 A jak masz na imię? 760 00:34:36,450 --> 00:34:37,080 >> PUBLICZNOŚCI: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Głośnik: Alex jest teraz posortowana. 762 00:34:38,379 --> 00:34:40,750 Lewa połowa, prawa połowa, co jest ostatnim krokiem? 763 00:34:40,750 --> 00:34:41,250 Merge. 764 00:34:41,250 --> 00:34:44,310 Dość banalna, więc jestem zamierza połączyć w sześciu, 765 00:34:44,310 --> 00:34:46,930 zrobić krok do tyłu, osiem, zrobić krok do tyłu. 766 00:34:46,930 --> 00:34:49,530 A teraz jest to zauważyć przydatne na wynos, co 767 00:34:49,530 --> 00:34:53,930 jest prawdziwe w lewej połowie lista, niezależnie od tego, jak zaczęliśmy? 768 00:34:53,930 --> 00:34:55,090 Jest klasyfikowane. 769 00:34:55,090 --> 00:34:57,750 >> Teraz to nie jest klasyfikowane w duży schemat rzeczy, 770 00:34:57,750 --> 00:35:00,250 ale są sortowane niezależnie z drugiej połowy. 771 00:35:00,250 --> 00:35:04,100 Teraz co krok jestem na razie trzymam przewijania, jak zaczęła historia? 772 00:35:04,100 --> 00:35:05,680 Teraz muszę uporządkować prawą połowę. 773 00:35:05,680 --> 00:35:07,630 Tak więc teraz jesteśmy w drodze powrotnej początek historii, 774 00:35:07,630 --> 00:35:08,921 i niech to zrobić szybciej. 775 00:35:08,921 --> 00:35:11,320 Więc idę do sortowania prawa połowa całej listy. 776 00:35:11,320 --> 00:35:13,060 Jaki jest następny krok? 777 00:35:13,060 --> 00:35:15,840 Sortować lewą połowę prawej połowie. 778 00:35:15,840 --> 00:35:18,715 Sortować lewą połowę Lewa połowa prawej połowy. 779 00:35:18,715 --> 00:35:19,590 A jak masz na imię? 780 00:35:19,590 --> 00:35:20,230 >> PUBLICZNOŚCI: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Głośnik: Omar, krok do przodu, zrobić. 782 00:35:21,970 --> 00:35:22,860 Lewa połowa jest posortowana. 783 00:35:22,860 --> 00:35:23,330 A jak masz na imię? 784 00:35:23,330 --> 00:35:23,820 >> PUBLICZNOŚCI: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Głośnik: Chris, zrobić krok do przodu, jesteś teraz sortowane. 786 00:35:25,620 --> 00:35:27,010 Co jest kluczowym krokiem teraz? 787 00:35:27,010 --> 00:35:27,510 Merge. 788 00:35:27,510 --> 00:35:30,509 Więc ktoś ma zamiar połączyć w miejscu tutaj, jeśli można zrobić krok do tyłu, 789 00:35:30,509 --> 00:35:32,930 i trzeci jest zamiar zrobić krok do tyłu, łączenia. 790 00:35:32,930 --> 00:35:38,080 Tak lewa połowa prawa połowa, jest teraz posortowana. 791 00:35:38,080 --> 00:35:41,747 Szczerze mówiąc, ten algorytm jest jak my Marnujesz sposób więcej czasu niż wcześniej, 792 00:35:41,747 --> 00:35:44,830 ale jeśli zrobił to w czasie rzeczywistym, to będzie zobaczyć, co będzie na wynos. 793 00:35:44,830 --> 00:35:47,970 Teraz jestem tutaj, w prawo połowę prawą połowę 794 00:35:47,970 --> 00:35:50,170 pozwól mi iść dalej i uporządkować lewą połowę. 795 00:35:50,170 --> 00:35:51,482 Krok do przodu, jak masz na imię? 796 00:35:51,482 --> 00:35:52,190 PUBLICZNOŚCI: Ramsey. 797 00:35:52,190 --> 00:35:53,210 Głośnik: Ramsey jest teraz posortowana. 798 00:35:53,210 --> 00:35:53,570 Jak masz na imię? 799 00:35:53,570 --> 00:35:54,200 >> PUBLICZNOŚCI: Marina. 800 00:35:54,200 --> 00:35:57,033 >> Prelegent: Marina jest obecnie klasyfikowane jako dobrze, jeśli wziąć jeden krok do przodu. 801 00:35:57,033 --> 00:36:00,690 Kluczowym krokiem jest tu teraz połączyć, jestem zamierza zerwać z moich dwóch listach, 802 00:36:00,690 --> 00:36:01,720 w lewo iw prawo. 803 00:36:01,720 --> 00:36:05,150 Pięć przyjdzie pierwszy, i siedem przyjdzie następny. 804 00:36:05,150 --> 00:36:06,410 I znowu, to jest celowe. 805 00:36:06,410 --> 00:36:08,535 Fakt, że są one przy kilka kroków do przodu i tyłu 806 00:36:08,535 --> 00:36:12,997 ma oznaczać, że nie możemy zrobić tego algorytmu w miejscu tak łatwo 807 00:36:12,997 --> 00:36:15,830 jak sortowanie bąbelkowe i wyboru rodzaju, i wprowadzenie sortowania, gdzie tylko 808 00:36:15,830 --> 00:36:16,960 przechowywane zamiana ludzi. 809 00:36:16,960 --> 00:36:19,940 Dosłownie trzeba coś w rodzaju z papieru, w którym na zarysowania 810 00:36:19,940 --> 00:36:21,827 umieścić tych ludzi a ja zrobić łączenie, 811 00:36:21,827 --> 00:36:23,410 a następnie można umieścić je z powrotem na miejsce. 812 00:36:23,410 --> 00:36:27,260 I to jest klucz, bo używam nowy zasób, przestrzeń, nie tylko czas. 813 00:36:27,260 --> 00:36:28,270 >> OK, to jest niesamowite. 814 00:36:28,270 --> 00:36:32,050 Lewa połowa jest posortowana, prawa połowa jest sortowane, teraz, że kluczem połączenia krok. 815 00:36:32,050 --> 00:36:33,450 Jak mam połączyć to? 816 00:36:33,450 --> 00:36:35,470 Więc jeśli będziesz śledzić moje Lewa ręka i prawa ręka, 817 00:36:35,470 --> 00:36:38,930 Zamierzam zwrócić moją lewą rękę w lewej połowie, moja prawa ręka 818 00:36:38,930 --> 00:36:42,680 na prawej połowie, a teraz muszę zdecydować, krok po kroku, do kogo się łączą w. 819 00:36:42,680 --> 00:36:44,650 Który oczywiście jest na pierwszym miejscu? 820 00:36:44,650 --> 00:36:45,150 Numer jeden. 821 00:36:45,150 --> 00:36:47,327 Więc chodź tu, Oto nasz notatnik. 822 00:36:47,327 --> 00:36:49,910 Więc teraz numerem jeden i zawiadomienia Co mam zrobić z moją prawą ręką, 823 00:36:49,910 --> 00:36:54,152 Mam zamiar przenieść z jednej strony prawo krok nad wskazać numer trzy, 824 00:36:54,152 --> 00:36:55,860 a teraz mam zrobić sama decyzja. 825 00:36:55,860 --> 00:36:58,387 I faktycznie stanąć w prawo Przód Łukasza tutaj jeśli można, 826 00:36:58,387 --> 00:36:59,720 bo to jest nasz notatnik. 827 00:36:59,720 --> 00:37:00,610 Więc kto jest następny? 828 00:37:00,610 --> 00:37:05,000 Mamy Łukasza z numerem dwa lub Chris z numerem trzy. 829 00:37:05,000 --> 00:37:07,460 Oczywiście Łukasza, numer dwa, więc tu przyjść. 830 00:37:07,460 --> 00:37:11,270 >> Ale teraz moja lewa ręka będzie być zwiększany, aby wskazać na Darrena, 831 00:37:11,270 --> 00:37:15,160 i tu jest klucz zabrać ze połączenia, mam zamiar robić to, 832 00:37:15,160 --> 00:37:17,340 Oczywiście, jeśli rodzaj z śledzić logikę. 833 00:37:17,340 --> 00:37:19,670 Ale moje ręce nie są zamiar iść do tyłu, 834 00:37:19,670 --> 00:37:23,861 co oznacza, że ​​ja nigdy nie porusza się tylko lewo z mojego procesu scalenia, 835 00:37:23,861 --> 00:37:26,360 i że będzie kluczem do nasza analiza za chwilę. 836 00:37:26,360 --> 00:37:27,859 >> Więc teraz niech to się szybko skończyć. 837 00:37:27,859 --> 00:37:31,650 Więc trzy przychodzi następny, następnie cztery przychodzi następny, 838 00:37:31,650 --> 00:37:38,750 a teraz pięć przychodzi następny, potem sześć, i siedem, a następnie w końcu osiem. 839 00:37:38,750 --> 00:37:42,960 Czuje się jak najwolniejszy algorytm jeszcze, ale nie, jeśli rzeczywiście 840 00:37:42,960 --> 00:37:45,510 uruchomić go w tym samym rodzaju z zegarem, tak aby 841 00:37:45,510 --> 00:37:48,106 mówić o sam tykanie zegara, jak wcześniej. 842 00:37:48,106 --> 00:37:48,605 Dlaczego? 843 00:37:48,605 --> 00:37:51,100 Cóż, weźmy spojrzeć na wynik końcowy. 844 00:37:51,100 --> 00:37:56,990 >> Wróćmy tutaj, niech mnie podciągnąć demonstrację wizualnie 845 00:37:56,990 --> 00:37:59,030 z tego, co właśnie zrobiłeś. 846 00:37:59,030 --> 00:38:06,110 Powiększanie tutaj, na tym strona tutaj, mówiąc Firefox 847 00:38:06,110 --> 00:38:08,200 że chcemy stać w kolejce się w tym polu, niech 848 00:38:08,200 --> 00:38:11,260 powiedzieć sortowania bąbelkowego, z których jesteśmy obecnie dobrze znane, 849 00:38:11,260 --> 00:38:14,130 Wybór rodzaju, który jest innym dość proste jeden, 850 00:38:14,130 --> 00:38:18,250 a teraz dzisiejsza seryjnej sortowanie, które będzie szczytowy nasz koniec. 851 00:38:18,250 --> 00:38:21,530 Przyczyną tego, że trwało to tak długo tu z ludźmi, a ja mowie to, 852 00:38:21,530 --> 00:38:23,480 oczywiście, ja tłumacząc każdy krok. 853 00:38:23,480 --> 00:38:26,920 Ale jeśli po prostu wykonać to, o wiele jak my sortowanie bąbelkowe i wybór 854 00:38:26,920 --> 00:38:30,890 sortowanie nie tylko wizualnie, zegarek , jak bardziej efektywnie 855 00:38:30,890 --> 00:38:33,330 tego efektu dźwigni z podziału i podboju 856 00:38:33,330 --> 00:38:39,150 może być stosowane, gdy w zestawie danych, który jest nawet wielkość ośmiu, a nawet znacznie, 857 00:38:39,150 --> 00:38:39,970 znacznie większe. 858 00:38:39,970 --> 00:38:44,585 Daję scalania sortowania, obok strona z innych algorytmów. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 To będzie się bolesne szybko, a zakończenie 861 00:38:58,530 --> 00:39:00,890 nie jest szczególnie szczytowy, po prostu skończyć sortowane. 862 00:39:00,890 --> 00:39:05,280 Ale kluczem jest to, że na wynos Zobacz, jak wiele szybciej połączyć sortowania 863 00:39:05,280 --> 00:39:08,110 było, chyba, że ​​myślisz, że jestem tylko rodzaj bawić się z tobą. 864 00:39:08,110 --> 00:39:13,100 Jeśli robimy to po raz ostatni, Zróbmy Przeładuj, wróćmy 865 00:39:13,100 --> 00:39:14,960 bubble rodzaj i wybierz, i tylko dla zabawy, 866 00:39:14,960 --> 00:39:17,330 niech wybrać wstawianie sortowania, tak na dokładkę. 867 00:39:17,330 --> 00:39:20,020 I tym razem znowu, niech wybierz seryjnej sortowanie i niech 868 00:39:20,020 --> 00:39:21,595 faktycznie uruchomić te obok siebie. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> I to nie jest, w rzeczywistości, fuks. 871 00:39:26,930 --> 00:39:31,140 Co mam zrobić, to skutecznie mam dzieli moje wejście na pół, jeszcze raz, 872 00:39:31,140 --> 00:39:32,240 i znowu, i znowu. 873 00:39:32,240 --> 00:39:35,590 I nie tylko tak wiele razy ty może podzielić wejście na połówki, w lewo 874 00:39:35,590 --> 00:39:36,240 i prawo. 875 00:39:36,240 --> 00:39:39,425 Co znajduje się formuła, że ​​ciągle widzę , który opisuje podział w połowie 876 00:39:39,425 --> 00:39:41,050 znowu, i znowu, i znowu, i znowu? 877 00:39:41,050 --> 00:39:41,890 >> PUBLICZNOŚCI: log n. 878 00:39:41,890 --> 00:39:42,760 >> Głośnik: log n. 879 00:39:42,760 --> 00:39:46,300 Ale to nie jest jeszcze jeden krok klucz, algorytm ten nie jest log n kroków. 880 00:39:46,300 --> 00:39:48,992 Jeśli to były tylko log n kroków, bylibyśmy w tym samym problemem 881 00:39:48,992 --> 00:39:51,200 jak wcześniej, gdy nie możemy być że wszystko jest posortowane. 882 00:39:51,200 --> 00:39:54,480 Musisz patrzeć na elementy minimalnie n aby upewnić się, n elementy są sortowane, 883 00:39:54,480 --> 00:39:55,950 w przeciwnym razie jest to skok wiary. 884 00:39:55,950 --> 00:39:59,810 >> Więc to jest minimalnie dziennika n kroków, ale co o tym kluczowym etapie scalenia 885 00:39:59,810 --> 00:40:04,370 gdzie połączyła moja lewa i prawa połowa pół i chodził po scenie? 886 00:40:04,370 --> 00:40:06,980 Ile kroków jest to, że aby połączyć? 887 00:40:06,980 --> 00:40:10,150 To n, ale nie tylko scalić czas ostateczny. 888 00:40:10,150 --> 00:40:15,089 Na każdej z tych zagnieżdżonych połączeń, na każde tych zagnieżdżonych scala, nadal klasyfikowane. 889 00:40:15,089 --> 00:40:18,380 I połączyła tych dwóch facetów, to te dwa Chłopaki, to te dwa chłopaki i tak dalej. 890 00:40:18,380 --> 00:40:19,955 >> Więc zrobiłem połączenie znowu, i znowu. 891 00:40:19,955 --> 00:40:20,580 Ile razy? 892 00:40:20,580 --> 00:40:23,510 I tak za każdym razem podzielone lista w połowie, zrobiłem seryjnej. 893 00:40:23,510 --> 00:40:25,460 Podzielić listę na pół, do korespondencji seryjnej. 894 00:40:25,460 --> 00:40:28,570 Więc jeśli dzieląc listę Można to zrobić razy log n, 895 00:40:28,570 --> 00:40:33,880 i łączenie ostatecznie wykonuje n kroki, jakie mogą być teraz górna 896 00:40:33,880 --> 00:40:37,000 związany z prowadzeniem Czas naszego algorytmu? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> I rzeczywiście, to właśnie udało nam się osiągnąć tutaj. 899 00:40:40,560 --> 00:40:44,650 Więc uważasz, że wizualnie, gdy widzisz te trzy rzeczy uruchomić obok siebie 900 00:40:44,650 --> 00:40:47,930 jest n do kwadratu na n kwadratu na n log n. 901 00:40:47,930 --> 00:40:51,010 Które zasadniczo zobaczymy, Nie tylko, ale już w przyszłości 902 00:40:51,010 --> 00:40:52,760 Jest o wiele szybciej. 903 00:40:52,760 --> 00:40:56,010 Brawa dla tych facetów, Będę nagradzać je z kulkami stresu. 904 00:40:56,010 --> 00:41:00,260 Miejmy odroczyć tu dzisiaj, i zobaczymy w poniedziałek. 905 00:41:00,260 --> 00:41:02,255