1 00:00:00,000 --> 00:00:03,332 >> [MUZYKI] 2 00:00:03,332 --> 00:00:06,490 >> ANDI PENG: Witamy w tygodniu 3 sekcji. 3 00:00:06,490 --> 00:00:09,550 Dzięki, chłopaki, na wszystko przychodzi do tej wcześniejszej godzinie rozpoczęcia dzisiaj. 4 00:00:09,550 --> 00:00:11,466 Mamy ładny, mały kameralna grupa dziś. 5 00:00:11,466 --> 00:00:14,570 Więc mam nadzieję, że wrócimy do wykończenie, być może, na początku, 6 00:00:14,570 --> 00:00:15,780 trochę wcześnie dzisiaj. 7 00:00:15,780 --> 00:00:22,057 Tak szybko, tylko niektóre Komunikaty dla porządku obrad dziś. 8 00:00:22,057 --> 00:00:23,890 Zanim zaczniemy, jesteśmy będzie po prostu przejść nad 9 00:00:23,890 --> 00:00:28,910 niektóre krótkie kwestie logistyczne, zbior pytania, zdać sprawozdanie, takie rzeczy. 10 00:00:28,910 --> 00:00:30,250 A potem będziemy nurkować w prawo. 11 00:00:30,250 --> 00:00:34,710 Będziemy używać debuggera GDB do nazwie rozpocząć obalania nasz kod, który David 12 00:00:34,710 --> 00:00:36,550 wyjaśnione w wykładzie na drugi dzień. 13 00:00:36,550 --> 00:00:39,420 Pójdziemy na czterech typów rodzajów. 14 00:00:39,420 --> 00:00:42,310 Pójdziemy na nich dość szybko ponieważ są one bardzo intensywne. 15 00:00:42,310 --> 00:00:45,710 Ale wiem, że wszystkie slajdy i Kod źródłowy jest zawsze online. 16 00:00:45,710 --> 00:00:50,810 Dlatego zachęcamy, co Lektura, do wrócić i spojrzeć na to. 17 00:00:50,810 --> 00:00:53,930 >> Pojedziemy przez notacji asymptotycznej, które 18 00:00:53,930 --> 00:00:55,944 tylko fantazyjny sposób na powiedzenie "czas pracy" 19 00:00:55,944 --> 00:00:58,360 gdzie mamy duże O, które David wyjaśnione w wykładzie. 20 00:00:58,360 --> 00:01:01,550 I mamy też Omega, które jest dolna granica czas pracy. 21 00:01:01,550 --> 00:01:06,450 I porozmawiamy nieco więcej szczegółowe dotyczące jak te prace. 22 00:01:06,450 --> 00:01:10,160 I wreszcie, pójdziemy nad wyszukiwania binarnego, ponieważ wielu z was, którzy mają już 23 00:01:10,160 --> 00:01:15,190 Spojrzał na swoich psets Zapewne wiesz, że że jest to kwestia, która jest w twoim pset. 24 00:01:15,190 --> 00:01:17,470 Więc wszyscy są szczęśliwi że obejmuje to dzisiaj. 25 00:01:17,470 --> 00:01:20,610 >> I wreszcie, na swoje feedback sekcja, tak naprawdę 26 00:01:20,610 --> 00:01:23,000 pozostawił około 15 minut w koniec po prostu przejść nad 27 00:01:23,000 --> 00:01:27,730 logistyka pset3, wszelkie pytania, może trochę wskazówek, jeśli chcesz, 28 00:01:27,730 --> 00:01:28,990 przed rozpoczęciem programowania. 29 00:01:28,990 --> 00:01:30,890 Więc spróbujmy dotrzeć materiał dość szybko. 30 00:01:30,890 --> 00:01:33,880 A potem możemy spędzić trochę czasu biorąc więcej pytań dotyczących zbior. 31 00:01:33,880 --> 00:01:35,230 OK. 32 00:01:35,230 --> 00:01:39,570 >> Szybko, więc tylko kilka Komunikaty zanim zaczniemy dziś. 33 00:01:39,570 --> 00:01:45,410 Po pierwsze, zapraszamy do dokonywania go przez dwóch swoich psets. 34 00:01:45,410 --> 00:01:49,432 I przyjrzał się your-- tak, niech dostać brawa dla tego jednego. 35 00:01:49,432 --> 00:01:51,140 Właściwie, to było naprawdę, naprawdę pod wrażeniem. 36 00:01:51,140 --> 00:01:55,800 I klasyfikowane pierwszy pset dla was w zeszłym tygodniu i zrobiliście niesamowite. 37 00:01:55,800 --> 00:01:58,290 >> Styl był na miejscu oprócz kilku uwag. 38 00:01:58,290 --> 00:02:00,660 Upewnij się, że jesteś zawsze Komentując swój kod. 39 00:02:00,660 --> 00:02:03,040 Ale twoje psets byli na miejscu. 40 00:02:03,040 --> 00:02:05,549 I tak trzymać. 41 00:02:05,549 --> 00:02:08,090 I to jest dobre dla równiarka do zobaczyć, że chłopaki stawiają 42 00:02:08,090 --> 00:02:10,704 w tyle wysiłku w swoim stylu i projektowania w kodzie 43 00:02:10,704 --> 00:02:12,120 że chcielibyśmy, aby zobaczyć. 44 00:02:12,120 --> 00:02:16,450 Więc jestem przekazując mojej wdzięczności do końca TAS. 45 00:02:16,450 --> 00:02:19,210 >> Jednak istnieje Kilka pytań debrief 46 00:02:19,210 --> 00:02:22,010 Chcę po prostu przejść nad tym pozwoliłoby zarówno moje życie 47 00:02:22,010 --> 00:02:24,900 i wiele druga TAs "mieszka nieco łatwiejsze. 48 00:02:24,900 --> 00:02:28,220 Po pierwsze, zauważyłem to obok week-- ilu z was 49 00:02:28,220 --> 00:02:32,301 zostały uruchomione check50 na kod Przed wysłaniem? 50 00:02:32,301 --> 00:02:32,800 OK. 51 00:02:32,800 --> 00:02:36,690 Tak więc każdy powinien robić check50, because-- secret-- faktycznie 52 00:02:36,690 --> 00:02:41,540 uruchomić check50 ramach naszej poprawności skrypty do testowania kodu. 53 00:02:41,540 --> 00:02:45,480 Więc jeśli twój kod zawodzi check50, według wszelkiego prawdopodobieństwa, 54 00:02:45,480 --> 00:02:47,570 to prawdopodobnie będzie nie nasz data, jak również. 55 00:02:47,570 --> 00:02:49,320 Czasami chłopaki mają prawo odpowiedzi. 56 00:02:49,320 --> 00:02:52,200 Podobnie jak w chciwy, niektóre masz odpowiednie numery, 57 00:02:52,200 --> 00:02:53,960 po prostu wydrukować kilka dodatkowych rzeczy. 58 00:02:53,960 --> 00:02:55,940 I że dodatkowe rzeczy faktycznie nie sprawdzić, 59 00:02:55,940 --> 00:02:58,440 ponieważ komputer nie naprawdę wiedzą, co to jest szukasz. 60 00:02:58,440 --> 00:03:00,981 I tak będzie po prostu uruchomić poprzez, zobaczyć, że wyjścia nie ma 61 00:03:00,981 --> 00:03:03,810 pasuje, czego oczekujemy odpowiedzi być, i zaznaczyć, że jest źle. 62 00:03:03,810 --> 00:03:06,560 >> I wiem, że stało się w niektóre z przypadków, w tym tygodniu. 63 00:03:06,560 --> 00:03:09,870 Wróciłem więc i ręcznie przeklasyfikowanie wszystkich na kod. 64 00:03:09,870 --> 00:03:12,780 W przyszłości jednak Proszę, upewnij się, 65 00:03:12,780 --> 00:03:14,570 że używasz sprawdzić 50 na kodzie. 66 00:03:14,570 --> 00:03:17,970 Bo to jest rodzaj bólu TA aby wrócić i ręcznie zmiana klasyfikacji 67 00:03:17,970 --> 00:03:21,197 każdy pset dla każdego pojedyncze, mało brakowało instancji. 68 00:03:21,197 --> 00:03:22,530 Więc nie ma się żadnych punktów. 69 00:03:22,530 --> 00:03:25,210 Myślę, że zdjął może jedna lub dwie projektowania. 70 00:03:25,210 --> 00:03:27,710 W przyszłości jednak, jeśli jesteś braku check50, 71 00:03:27,710 --> 00:03:31,330 punkty zostaną podjęte od poprawności. 72 00:03:31,330 --> 00:03:35,020 >> Ponadto psets są ze względu piątki w godz. 73 00:03:35,020 --> 00:03:38,990 Myślę, że istnieje siedem minut późnego okresu karencji, że daje. 74 00:03:38,990 --> 00:03:42,434 Na czas Harvarda, są dopuszczone do za siedem minut późno na wszystko. 75 00:03:42,434 --> 00:03:44,350 Więc tutaj w Yale, będziemy przestrzegać, że dobrze. 76 00:03:44,350 --> 00:03:47,910 Ale dość dużo, na 12:07, jeśli pset nie jest, 77 00:03:47,910 --> 00:03:49,720 to będzie oznaczone jako późno. 78 00:03:49,720 --> 00:03:53,160 I tak, gdy jest zaznaczone tak późno, TA-- jestem 79 00:03:53,160 --> 00:03:54,870 nadal będzie klasyfikacji swoich psets. 80 00:03:54,870 --> 00:03:56,760 Więc można jeszcze zobaczyć gatunek pojawiają. 81 00:03:56,760 --> 00:03:58,820 Jednak wiem, że na koniec semestru, 82 00:03:58,820 --> 00:04:02,270 wszystkie późne psets będzie tylko automatycznie zerowany przez komputer. 83 00:04:02,270 --> 00:04:04,490 >> Robimy to z dwóch powodów. 84 00:04:04,490 --> 00:04:09,220 Jeden z nich, czasem dostajemy usprawiedliwiona, jak wymówek dziekana, 85 00:04:09,220 --> 00:04:10,762 później, że nie wiem o jeszcze. 86 00:04:10,762 --> 00:04:13,761 Więc chcemy upewnić się, mamy klasyfikacji wszystko tylko w przypadku, jak, jestem 87 00:04:13,761 --> 00:04:15,080 brakuje pretekst dziekana. 88 00:04:15,080 --> 00:04:17,000 A po drugie, należy Umysł, nadal można 89 00:04:17,000 --> 00:04:19,370 upuść jeden pset, że ma pełne punkty zakresie. 90 00:04:19,370 --> 00:04:21,430 I tak lubimy klasy wszystkich psets tylko 91 00:04:21,430 --> 00:04:24,730 aby upewnić się, że oscyloskopu tam i że je spróbować. 92 00:04:24,730 --> 00:04:29,150 Więc nawet jeśli jest późno, będziesz nadal zaliczenia punktów zakresu, tak myślę. 93 00:04:29,150 --> 00:04:33,730 >> Więc morał tej historii jest, aby że twoje psets są na czas. 94 00:04:33,730 --> 00:04:38,350 A jeśli nie są one na czas, wiem, że to nie jest wielki. 95 00:04:38,350 --> 00:04:41,678 Tak, zanim przejdę, czy ktoś ma Wszelkie pytania dotyczące informacji zwrotnej pset? 96 00:04:41,678 --> 00:04:42,178 Tak. 97 00:04:42,178 --> 00:04:43,630 >> PUBLICZNOŚCI: Czy powiedzieć, że może spaść jedną z psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI PENG: Tak. 99 00:04:44,296 --> 00:04:47,050 Więc nie ma dziewięć psets ogólna w ciągu semestru. 100 00:04:47,050 --> 00:04:50,610 A jeśli masz zakres points-- więc zakres jest tak, 101 00:04:50,610 --> 00:04:53,567 dość dużo, jesteś usiłujących dokonania Problem, jesteś oddanie się w czasie, 102 00:04:53,567 --> 00:04:56,150 ty pokazując, że masz wykazać czytałeś spec. 103 00:04:56,150 --> 00:04:57,191 To dość dużo zakres. 104 00:04:57,191 --> 00:04:59,370 A jeśli spełniają Punkty zakres, mamy 105 00:04:59,370 --> 00:05:03,360 może spaść do najniższych jeden na pełnym zakresie. 106 00:05:03,360 --> 00:05:06,790 Więc to w swoją korzyść wypełnić i spróbować każdy pset. 107 00:05:06,790 --> 00:05:10,320 >> Nawet upload-- jeśli żaden z ich pracy, przesłać je wszystkie. 108 00:05:10,320 --> 00:05:13,711 A potem mamy nadzieję być w stanie Ci niektóre z tych punktów z powrotem. 109 00:05:13,711 --> 00:05:14,210 Chłodny. 110 00:05:14,210 --> 00:05:16,780 Jeszcze jakieś pytania? 111 00:05:16,780 --> 00:05:17,840 Wielki. 112 00:05:17,840 --> 00:05:21,960 >> Po drugie, biuro hours-- kilka szybkie notatki o godzinach urzędowania. 113 00:05:21,960 --> 00:05:24,300 Więc po pierwsze, chodź na początku tygodnia. 114 00:05:24,300 --> 00:05:26,909 Nikt nie jest nigdy w godziny pracy w poniedziałki. 115 00:05:26,909 --> 00:05:28,700 Christabel przyszedł godziny pracy zeszłej nocy. 116 00:05:28,700 --> 00:05:29,691 Tak, Christabel. 117 00:05:29,691 --> 00:05:32,190 A co mamy w biurze godzin w nocy, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> PUBLICZNOŚCI: Mieliśmy lody. 119 00:05:33,020 --> 00:05:36,160 >> ANDI PENG: Tak to prawda, mieliśmy lody w godzinach pracy w nocy. 120 00:05:36,160 --> 00:05:39,390 Chociaż nie mogę obiecać, że będziemy mieć lody w godzinach pracy 121 00:05:39,390 --> 00:05:43,230 co tydzień, co mogę ci obiecać jest to, że nie będzie to znacząco 122 00:05:43,230 --> 00:05:45,380 lepszy stosunek ucznia do TA. 123 00:05:45,380 --> 00:05:47,650 Podobnie jak prawda, to jak trzy do jednego. 124 00:05:47,650 --> 00:05:50,350 Mając na uwadze, że kontrastują z Czwartek, masz około 150 125 00:05:50,350 --> 00:05:52,830 Podkreślił dzieci i naprawdę nie lody. 126 00:05:52,830 --> 00:05:55,360 I to nie tylko wydajne dla każdego. 127 00:05:55,360 --> 00:05:58,730 Więc morał tej historii jest, przyjść wcześnie do godzin pracy biura i dobrych rzeczy 128 00:05:58,730 --> 00:06:00,310 stanie się. 129 00:06:00,310 --> 00:06:02,110 >> Ponadto, przygotowana do zadawania pytań. 130 00:06:02,110 --> 00:06:03,200 Wiesz? 131 00:06:03,200 --> 00:06:05,420 Niezależnie od tego, TAS I myślę, mówili, 132 00:06:05,420 --> 00:06:10,710 byliśmy coraz parę studentów którzy wchodzą w czwartek o, jak, 10:50 133 00:06:10,710 --> 00:06:15,100 nie po przeczytaniu specyfikacji jest jak mi pomóc, pomóż mi. 134 00:06:15,100 --> 00:06:18,200 Niestety w tym momencie nie ma nie wiele możemy zrobić, aby pomóc. 135 00:06:18,200 --> 00:06:19,590 Więc proszę przyjść na początku tygodnia. 136 00:06:19,590 --> 00:06:22,040 Przyjdź wcześniej do godzin pracy biura. 137 00:06:22,040 --> 00:06:23,350 Przygotowana do zadawania pytań. 138 00:06:23,350 --> 00:06:25,310 Upewnij się, że jako student, to miejsce, gdzie 139 00:06:25,310 --> 00:06:27,620 musisz być tak, że TAs może Cię razem, 140 00:06:27,620 --> 00:06:32,850 co jest, co godziny pracy powinien być przeznaczony na. 141 00:06:32,850 --> 00:06:37,380 >> Po drugie, tak, wiem, profesorów jak zaskoczyć nas z testów. 142 00:06:37,380 --> 00:06:39,439 Miałem profesor tych jak, yo, przy okazji, 143 00:06:39,439 --> 00:06:41,230 pamiętać, że śródokresową masz w następny poniedziałek. 144 00:06:41,230 --> 00:06:42,855 Tak, nie wiedziałem o tej perspektywie średnioterminowej. 145 00:06:42,855 --> 00:06:45,630 Więc mam zamiar być, że TA że przypomina ci cały ten quiz, 146 00:06:45,630 --> 00:06:47,270 0-- bo wiesz, że jesteśmy CS. 147 00:06:47,270 --> 00:06:50,730 Teraz, że zrobiliśmy tablice, można uzyskać dlaczego to jest quiz, 0, nie quizu 1, co? 148 00:06:50,730 --> 00:06:51,320 OK. 149 00:06:51,320 --> 00:06:52,490 Och, mam kilka chichocze na jednym. 150 00:06:52,490 --> 00:06:53,120 OK. 151 00:06:53,120 --> 00:06:59,710 >> Więc Quiz 0 będzie 14 października, jeśli jesteś w dziale poniedziałku do środy 152 00:06:59,710 --> 00:07:02,920 i 15 października, jeśli jesteś w sekcja wtorek-czwartek. 153 00:07:02,920 --> 00:07:05,630 Powyższe nie ma zastosowania do tych, na Harvardzie 154 00:07:05,630 --> 00:07:10,350 who-- Myślę, że wszyscy będziemy odrywania quizy na 14. 155 00:07:10,350 --> 00:07:13,560 >> Więc tak, w przyszłym tygodniu, jeśli David, w wykładzie, idzie, 156 00:07:13,560 --> 00:07:15,747 Tak, tak, o tym quiz, w przyszłym tygodniu, wszyscy 157 00:07:15,747 --> 00:07:17,580 nie będzie w szoku, ponieważ przyszedł do sekcji 158 00:07:17,580 --> 00:07:19,664 i wiesz, że Quiz 0 jest w dwa tygodnie. 159 00:07:19,664 --> 00:07:21,580 I będziemy mieli recenzję sesje i wszystko. 160 00:07:21,580 --> 00:07:26,360 Więc nie ma obaw o się bać za to. 161 00:07:26,360 --> 00:07:29,890 Wszelkie pytania before-- wszelkie pytania na wszystkich dotyczących zagadnień logistycznych, 162 00:07:29,890 --> 00:07:32,591 klasyfikacji, godziny pracy, sekcje? 163 00:07:32,591 --> 00:07:33,090 Tak. 164 00:07:33,090 --> 00:07:35,100 >> PUBLICZNOŚCI: Więc quiz będzie podczas wykładu? 165 00:07:35,100 --> 00:07:35,766 >> ANDI PENG: Tak. 166 00:07:35,766 --> 00:07:39,460 Więc quizu, jak sądzę, jest 60 minut przydzielone w tym przedziale czasowym 167 00:07:39,460 --> 00:07:42,240 że będziesz po prostu wziąć w sali wykładowej. 168 00:07:42,240 --> 00:07:44,810 Więc nie masz przyjść na, jak, losowej 7:00 PM. 169 00:07:44,810 --> 00:07:46,140 Wszystko jest dobrze. 170 00:07:46,140 --> 00:07:47,100 Tak. 171 00:07:47,100 --> 00:07:50,060 Chłodny. 172 00:07:50,060 --> 00:07:50,840 >> W porządku. 173 00:07:50,840 --> 00:07:54,330 Więc będziemy przedstawić koncepcję dla Ciebie 174 00:07:54,330 --> 00:08:00,760 w tym tygodniu, że David ma już rodzaj z poruszone w wykładzie w ubiegłym tygodniu. 175 00:08:00,760 --> 00:08:02,010 To się nazywa GDB. 176 00:08:02,010 --> 00:08:05,570 A ilu z was, podczas gdy w przebieg pisanie psets, 177 00:08:05,570 --> 00:08:09,981 Zauważyłem duży przycisk z napisem "Debug" na górze IDE? 178 00:08:09,981 --> 00:08:10,480 OK. 179 00:08:10,480 --> 00:08:13,770 Więc teraz my rzeczywiście się wydobyć tajemnica co to przycisk rzeczywiście 180 00:08:13,770 --> 00:08:14,270 robi. 181 00:08:14,270 --> 00:08:16,790 I gwarantuję Ci, że jest to piękna, piękna rzecz. 182 00:08:16,790 --> 00:08:20,740 >> Tak, aż do teraz, myślę, że nastąpiła dwie rzeczy 183 00:08:20,740 --> 00:08:23,320 Uczniowie byli zazwyczaj robi podczas debugowania psets. 184 00:08:23,320 --> 00:08:27,635 Jeden, to albo dodać printf () - więc co kilka linii, 185 00:08:27,635 --> 00:08:29,760 dodają w printf () - och, co to jest zmienna? 186 00:08:29,760 --> 00:08:32,551 Och, co to jest zmienna now-- i rodzaj zobaczyć postęp 187 00:08:32,551 --> 00:08:33,940 Twój kod, jak to działa. 188 00:08:33,940 --> 00:08:37,030 Albo druga metoda dzieci nie jest że wystarczy napisać całość 189 00:08:37,030 --> 00:08:38,610 a potem jak to w końcu. 190 00:08:38,610 --> 00:08:39,970 Mam nadzieję, że to działa. 191 00:08:39,970 --> 00:08:44,851 Gwarantuję Ci, GDB jest lepszy niż w obu tych metod. 192 00:08:44,851 --> 00:08:45,350 Tak. 193 00:08:45,350 --> 00:08:46,980 Więc to będzie twój nowy najlepszy przyjaciel. 194 00:08:46,980 --> 00:08:51,780 Bo to piękna rzecz że wizualnie wyświetla zarówno 195 00:08:51,780 --> 00:08:54,850 co robi Twój kod w określonym punkcie 196 00:08:54,850 --> 00:08:57,486 jak również to, co wszystkie swoje zmienne są nośne, 197 00:08:57,486 --> 00:08:59,610 jak to, co ich wartości, w tym konkretnym miejscu. 198 00:08:59,610 --> 00:09:02,670 I w ten sposób można naprawdę ustawić punkty przerwania w kodzie. 199 00:09:02,670 --> 00:09:04,350 Możesz przejrzeć linia po linii. 200 00:09:04,350 --> 00:09:07,324 I GDB będzie po prostu za Ci, wyświetlane dla Ciebie, 201 00:09:07,324 --> 00:09:09,490 co wszystkich zmiennych są, co robią, 202 00:09:09,490 --> 00:09:10,656 co się dzieje w kodzie. 203 00:09:10,656 --> 00:09:13,240 I w taki sposób, to jest o wiele łatwiej zobaczyć 204 00:09:13,240 --> 00:09:17,120 co się dzieje, zamiast printf-ing lub zapisywać swoje wypowiedzi. 205 00:09:17,120 --> 00:09:19,160 >> Więc zrobimy przykład tym później. 206 00:09:19,160 --> 00:09:20,660 Tak więc wydaje się nieco abstrakcyjne. 207 00:09:20,660 --> 00:09:23,490 Nie martw się, zrobimy przykłady. 208 00:09:23,490 --> 00:09:29,170 I tak w istocie, trzy największe, Najczęściej używane funkcje trzeba w GDB 209 00:09:29,170 --> 00:09:32,500 są Następnie Krok nad, i Krok do przycisków. 210 00:09:32,500 --> 00:09:34,860 Mam zamiar udać się nie, rzeczywiście, teraz. 211 00:09:34,860 --> 00:09:40,930 >> Więc można zobaczyć, że wszyscy faceci lub należy powiększyć trochę? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 Z tyłu, można zobaczyć, że? 214 00:09:44,470 --> 00:09:45,730 Powinny powiększać? 215 00:09:45,730 --> 00:09:46,480 Tylko trochę? 216 00:09:46,480 --> 00:09:49,390 Ok fajnie. 217 00:09:49,390 --> 00:09:50,280 No to jedziemy. 218 00:09:50,280 --> 00:09:50,960 OK. 219 00:09:50,960 --> 00:09:57,000 >> Więc mam tu, mój Implementacja chciwi. 220 00:09:57,000 --> 00:10:01,430 I choć wielu z was napisał chciwi w pętli while form--, że 221 00:10:01,430 --> 00:10:04,890 Jest to całkowicie dopuszczalne sposób to zrobić it-- inny sposób to zrobić, to po prostu 222 00:10:04,890 --> 00:10:06,280 podzielić w modulo. 223 00:10:06,280 --> 00:10:09,290 Bo wtedy można mieć wartość, a następnie mieć resztę. 224 00:10:09,290 --> 00:10:11,150 I wtedy można po prostu dodać to wszystko razem. 225 00:10:11,150 --> 00:10:13,390 Czy logikę, co robię tu sens dla wszystkich, 226 00:10:13,390 --> 00:10:14,117 zanim zaczniemy? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Rodzaj? 229 00:10:17,980 --> 00:10:18,710 Chłodny. 230 00:10:18,710 --> 00:10:19,210 Wielki. 231 00:10:19,210 --> 00:10:21,290 Jest to całkiem sexy kawałek kodu, powiedziałbym. 232 00:10:21,290 --> 00:10:23,502 Tak jak mówiłem, Dawid, w wykład, po pewnym czasie, 233 00:10:23,502 --> 00:10:25,960 wy wszyscy zaczynają kod obejrzeniu jako coś, co jest piękne. 234 00:10:25,960 --> 00:10:29,950 A czasami, gdy widzisz piękne Kod, to takie wspaniałe uczucie. 235 00:10:29,950 --> 00:10:35,410 >> Tak więc, podczas gdy ten kod jest bardzo piękne, to nie działa prawidłowo. 236 00:10:35,410 --> 00:10:37,750 Warto więc uruchomić check50 na ten temat. 237 00:10:37,750 --> 00:10:39,440 Sprawdzić 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Czy to pset2? 241 00:10:44,990 --> 00:10:46,870 Tak. 242 00:10:46,870 --> 00:10:47,520 Och, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 OK. 245 00:10:52,890 --> 00:10:53,900 Więc uruchomić check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> A jak wy można zobaczyć tutaj, to w przypadku braku kilku przypadkach. 248 00:11:07,170 --> 00:11:10,165 A dla niektórych z was, w Oczywiście robi swoje zestawy problemowe, 249 00:11:10,165 --> 00:11:11,110 jesteś jak, ach, dlaczego nie jest to praca. 250 00:11:11,110 --> 00:11:13,318 Dlaczego to działa dla niektórych wartości, ale nie dla innych? 251 00:11:13,318 --> 00:11:17,760 Cóż, GDB pomoże Ci dowiedzieć dlaczego te wejścia nie działa. 252 00:11:17,760 --> 00:11:18,320 >> OK. 253 00:11:18,320 --> 00:11:21,640 Zobaczmy więc, jedną z upadających mnie sprawdza w check50 254 00:11:21,640 --> 00:11:24,920 była wprowadzona wartość 0,41. 255 00:11:24,920 --> 00:11:27,830 Tak więc prawidłowa odpowiedź, że powinna być coraz to 4. 256 00:11:27,830 --> 00:11:33,090 Ale zamiast tego, co ja drukowanie jest 3-n, co jest nieprawidłowe. 257 00:11:33,090 --> 00:11:36,190 Więc po prostu uruchomić to ręcznie, po prostu upewnij się, że check50 działa. 258 00:11:36,190 --> 00:11:36,940 Zróbmy ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Ups, muszę zrobić chciwi. 261 00:11:43,340 --> 00:11:43,840 No to jedziemy. 262 00:11:43,840 --> 00:11:44,381 Teraz ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Ile jest winien? 265 00:11:47,670 --> 00:11:49,550 Zróbmy 0,41. 266 00:11:49,550 --> 00:11:52,590 A Tak, widzimy tutaj że to wyprowadzanie 3 267 00:11:52,590 --> 00:11:55,160 gdy poprawna odpowiedź, W rzeczywistości, należy mieć 4. 268 00:11:55,160 --> 00:12:01,460 Warto więc wprowadzić GDB i zobaczyć, jak Można zabrać go naprawić ten problem. 269 00:12:01,460 --> 00:12:03,992 >> Tak więc pierwszy krok w Zawsze debugowania kodu 270 00:12:03,992 --> 00:12:05,950 jest, aby ustawić punkt przerwania, lub punkt w którym 271 00:12:05,950 --> 00:12:09,079 chcą komputera lub debugger, aby rozpocząć patrząc na. 272 00:12:09,079 --> 00:12:11,120 Więc jeśli naprawdę nie wiedzieć, jaki jest twój problem, 273 00:12:11,120 --> 00:12:14,670 Zwykle, typowa rzecz chcemy zrobić, to ustawić naszą przerwania w głównym. 274 00:12:14,670 --> 00:12:18,520 Więc jeśli faceci mogą to zobaczyć czerwony przycisk tam, 275 00:12:18,520 --> 00:12:22,860 Tak, to było mi przypisać a granicznych wartości funkcji głównej. 276 00:12:22,860 --> 00:12:24,130 Klikam to. 277 00:12:24,130 --> 00:12:26,130 >> A potem mogę iść do mojego przycisk Debug. 278 00:12:26,130 --> 00:12:27,036 Uderzyłem ten przycisk. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Pozwól mi się widok, jeśli mogę. 281 00:12:36,555 --> 00:12:38,020 No to jedziemy. 282 00:12:38,020 --> 00:12:40,730 Tak więc mamy tu, w panelu po prawej stronie. 283 00:12:40,730 --> 00:12:43,680 Przykro mi, chłopaki z tyłu, można naprawdę nie można zobaczyć bardzo dobrze. 284 00:12:43,680 --> 00:12:49,090 Ale w zasadzie wszystko prawo to panel robi 285 00:12:49,090 --> 00:12:53,130 jest śledzenie zarówno podświetlony Linia, która jest linia kodu 286 00:12:53,130 --> 00:12:56,640 że komputer jest uruchomiony, jak również wszystkich zmiennych 287 00:12:56,640 --> 00:12:57,600 Tu na dole. 288 00:12:57,600 --> 00:13:00,487 >> Więc masz centów, monety, n, wszystkie zadeklarowane różnych rzeczy 289 00:13:00,487 --> 00:13:01,070 w tym momencie. 290 00:13:01,070 --> 00:13:04,850 Nie martw się, bo mamy w rzeczywistości nie inicjowane ich do jakichkolwiek zmiennych jeszcze. 291 00:13:04,850 --> 00:13:07,200 Więc w komputerze, twój Komputer po prostu widząc, 292 00:13:07,200 --> 00:13:14,376 och, 32767 była ostatnia funkcja używane tej przestrzeni pamięci w komputerze. 293 00:13:14,376 --> 00:13:16,000 I tak to gdzie centów jest obecnie. 294 00:13:16,000 --> 00:13:19,360 Ale nie, że po uruchomieniu kodu, powinno stać się zainicjowany. 295 00:13:19,360 --> 00:13:24,110 >> Warto więc przejść, linia po linia, co się tutaj dzieje. 296 00:13:24,110 --> 00:13:25,350 OK. 297 00:13:25,350 --> 00:13:29,400 Więc tutaj są trzy przyciski, które po prostu wyjaśnić. 298 00:13:29,400 --> 00:13:34,090 Masz Play, lub funkcji Run, Przycisk, masz Krok nad przyciskiem, 299 00:13:34,090 --> 00:13:36,600 i masz również krok w przycisku. 300 00:13:36,600 --> 00:13:41,260 A w zasadzie, wszystkie trzy im po prostu przejść przez kod 301 00:13:41,260 --> 00:13:42,690 i robić różne rzeczy. 302 00:13:42,690 --> 00:13:45,680 >> Więc zwykle, gdy jesteś debugowanie, Nie chcemy, aby po prostu wciskamy Play 303 00:13:45,680 --> 00:13:47,930 bo Grać będzie po prostu uruchomić Twój kod do końca. 304 00:13:47,930 --> 00:13:49,070 A wtedy nie będzie w rzeczywistości wiedzieć, co twój problem 305 00:13:49,070 --> 00:13:51,432 to chyba ustawić wiele punktów przerwania. 306 00:13:51,432 --> 00:13:53,890 Jeśli ustawisz kilka punktów przerwania, to będzie po prostu automatycznie 307 00:13:53,890 --> 00:13:56,030 uruchomić z jednego punktu przerwania, do drugiej, do drugiego. 308 00:13:56,030 --> 00:13:58,030 Ale w tym przypadku mamy wystarczy, że jeden, bo 309 00:13:58,030 --> 00:13:59,970 chcą wypracować sobie drogę z góry na dół do dołu. 310 00:13:59,970 --> 00:14:04,830 Więc będziemy ignorować ten przycisk teraz dla celów tego programu. 311 00:14:04,830 --> 00:14:08,230 >> Więc po kroku nad funkcją tylko Kroki ponad każdej linii 312 00:14:08,230 --> 00:14:11,510 i mówi, co komputer robi. 313 00:14:11,510 --> 00:14:14,630 Krok do funkcji idzie do rzeczywistej funkcji 314 00:14:14,630 --> 00:14:16,000 to jest na linii kodu. 315 00:14:16,000 --> 00:14:19,070 Tak na przykład, jak printf () że jest to funkcja, prawda? 316 00:14:19,070 --> 00:14:21,980 Gdybym chciał fizycznie krokiem do funkcji printf () 317 00:14:21,980 --> 00:14:25,610 Chciałbym rzeczywiście iść do kawałka Kod gdzie printf () został napisany i zobaczyć 318 00:14:25,610 --> 00:14:26,730 co się tam dzieje. 319 00:14:26,730 --> 00:14:29,924 >> Typowo jednak, zakładamy, że kod, który dajemy wam działa. 320 00:14:29,924 --> 00:14:31,340 Zakładamy, że printf () działa. 321 00:14:31,340 --> 00:14:33,170 Zakładamy, że GetInt () działa. 322 00:14:33,170 --> 00:14:35,170 Więc nie ma potrzeby krok do tych funkcji. 323 00:14:35,170 --> 00:14:37,170 Ale jeśli nie ma funkcji że piszesz siebie 324 00:14:37,170 --> 00:14:39,060 które chcesz sprawdzić się, co się dzieje, 325 00:14:39,060 --> 00:14:41,200 co chcesz krok w tej funkcji. 326 00:14:41,200 --> 00:14:43,940 >> Więc teraz jesteśmy po prostu się krok nad tym kawałkiem kodu. 327 00:14:43,940 --> 00:14:44,485 Więc zobaczymy. 328 00:14:44,485 --> 00:14:46,547 Och, druk, "Oh hai, jak wiele zmian jest winien? " 329 00:14:46,547 --> 00:14:47,130 Nie obchodzi. 330 00:14:47,130 --> 00:14:49,830 Wiemy, że to działa, więc krok nad nim. 331 00:14:49,830 --> 00:14:53,290 >> Więc n, które jest nasz pływak, że mamy initialized-- lub declared-- 332 00:14:53,290 --> 00:14:56,810 w górę w górę, jesteśmy teraz dorównujàcego do GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Więc krok nad tym. 334 00:14:57,810 --> 00:14:59,580 I widzimy u Dno tutaj, program 335 00:14:59,580 --> 00:15:03,360 monituje o wejściu wartość. 336 00:15:03,360 --> 00:15:08,580 Warto więc wprowadzić wartość chcemy testować tutaj, co jest 0,41. 337 00:15:08,580 --> 00:15:09,160 Wielki. 338 00:15:09,160 --> 00:15:12,780 >> Więc teraz n-- zrobić chłopaki zobaczyć tu, u bottom-- to 339 00:15:12,780 --> 00:15:15,140 stored-- dlatego, że jeszcze nie zaokrąglone, to 340 00:15:15,140 --> 00:15:19,540 zapisane w tym jak gigant Pływak, że jest ,4099999996, 341 00:15:19,540 --> 00:15:22,550 który jest na tyle blisko, aby nasze cele, teraz, do 0,41. 342 00:15:22,550 --> 00:15:26,090 A potem zobaczymy później, jak my nadal wzmocnienie nad programem, 343 00:15:26,090 --> 00:15:29,850 Po tu n stała zaokrąglone i stał się 41 centów. 344 00:15:29,850 --> 00:15:30,350 Wielki. 345 00:15:30,350 --> 00:15:32,230 Wiemy, że nasz zaokrąglenia w pracy. 346 00:15:32,230 --> 00:15:34,700 Wiemy, że mamy prawidłowa liczba centów, 347 00:15:34,700 --> 00:15:36,990 tak, wiemy, że to jest naprawdę nie problem. 348 00:15:36,990 --> 00:15:40,050 >> Więc nadal stepping na w tym programie. 349 00:15:40,050 --> 00:15:40,900 Chodziliśmy tam. 350 00:15:40,900 --> 00:15:46,139 I tak po tej linii kodu, możemy powinien wiedzieć, ile czwarte mamy. 351 00:15:46,139 --> 00:15:46,680 Jesteśmy krok nad. 352 00:15:46,680 --> 00:15:52,040 I widzisz, że nie w rzeczywistości mają jeden kwartał, ponieważ mamy odjąć 25 353 00:15:52,040 --> 00:15:53,790 z naszej wartości początkowej 41. 354 00:15:53,790 --> 00:15:55,890 I mamy 16 wyjechali do naszych centów. 355 00:15:55,890 --> 00:15:58,830 >> Czy wszyscy zrozumieć, jak program jest wzmocnienie przez 356 00:15:58,830 --> 00:16:02,980 i dlaczego centów stała się obecnie 16 i dlaczego teraz, monety stało się 1? 357 00:16:02,980 --> 00:16:04,610 Czy wszyscy po tej logiki? 358 00:16:04,610 --> 00:16:05,110 Chłodny. 359 00:16:05,110 --> 00:16:07,860 Tak więc, w tym momencie, działa program, prawda? 360 00:16:07,860 --> 00:16:09,797 Wiemy, że robi dokładnie to, co chcemy go. 361 00:16:09,797 --> 00:16:11,880 A my nie faktycznie trzeba wydrukować, och, co 362 00:16:11,880 --> 00:16:14,430 jest centów w tym momencie, monety, co jest w tym momencie. 363 00:16:14,430 --> 00:16:17,170 >> Kontynuujemy przechodzi programu. 364 00:16:17,170 --> 00:16:18,100 Krok nad. 365 00:16:18,100 --> 00:16:18,620 Chłodny. 366 00:16:18,620 --> 00:16:19,700 Jedziemy nad dziesięciocentówki. 367 00:16:19,700 --> 00:16:20,200 Wielki. 368 00:16:20,200 --> 00:16:22,367 Widzimy, że to jest zrobione od $ 0,10 na bilon. 369 00:16:22,367 --> 00:16:23,450 I teraz mamy dwie monety. 370 00:16:23,450 --> 00:16:25,260 To jest poprawne. 371 00:16:25,260 --> 00:16:31,555 >> Idziemy na grosze i widzimy, że mamy pozostały centów. 372 00:16:31,555 --> 00:16:32,680 Hmm, to dziwne. 373 00:16:32,680 --> 00:16:37,540 Tutaj na program, miałem mieć odjęte moje grosze. 374 00:16:37,540 --> 00:16:39,400 Być może po prostu nie było robi to prawo linii. 375 00:16:39,400 --> 00:16:42,190 I niestety, widać tutaj, bo wiemy, 376 00:16:42,190 --> 00:16:44,360 które intensyfikują poprzez linie 32 i 33, 377 00:16:44,360 --> 00:16:50,560 to gdzie nasz program nieprawidłowo miał zmienne uruchomić. 378 00:16:50,560 --> 00:16:55,136 Tak więc możemy patrzeć i widzieć, oh, Jestem odjęcie tutaj centów, 379 00:16:55,136 --> 00:16:57,010 ale nie jestem w rzeczywistości dodanie do mojej wartości monety. 380 00:16:57,010 --> 00:16:57,860 Dodaję do centów. 381 00:16:57,860 --> 00:17:00,234 A ja nie chcę, aby dodać do centów, chcę dodać do monet. 382 00:17:00,234 --> 00:17:05,420 Więc jeśli to zmienić do monet, mamy program pracy. 383 00:17:05,420 --> 00:17:06,730 Mogę uruchomić check50. 384 00:17:06,730 --> 00:17:11,063 Możesz po prostu wyjść z GDB prawo tutaj, a następnie ponownie uruchom check50. 385 00:17:11,063 --> 00:17:11,938 Może po prostu to zrobić. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Mam do chciwi. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 I tu, to drukowanie na właściwą odpowiedź. 390 00:17:22,819 --> 00:17:26,569 >> Tak jak chłopaki widzą, GDB Jest to naprawdę potężne narzędzie 391 00:17:26,569 --> 00:17:29,940 do kiedy mamy tak dużo kodu dzieje i tak wiele zmiennych, 392 00:17:29,940 --> 00:17:32,510 że trudno dla nas, jak człowiekiem, aby śledzić. 393 00:17:32,510 --> 00:17:35,360 Komputer, w GDB debugger, ma możliwość 394 00:17:35,360 --> 00:17:37,020 aby śledzić wszystko. 395 00:17:37,020 --> 00:17:40,480 Wiem, w Visionaire, prawdopodobnie chłopaki mogło trafić kilka usterek segmentacji 396 00:17:40,480 --> 00:17:43,150 dlatego, że zostały uruchomione poza granice swojej tablicy. 397 00:17:43,150 --> 00:17:46,510 W przykładzie z Cezara, to dokładnie to, co ja tu realizowane. 398 00:17:46,510 --> 00:17:50,060 >> Więc zapomniałem sprawdzić co by się stało, gdybym 399 00:17:50,060 --> 00:17:52,510 nie mieć dwa argumenty wiersza poleceń. 400 00:17:52,510 --> 00:17:53,880 Ja po prostu nie umieścić w tej kontroli. 401 00:17:53,880 --> 00:17:57,380 I tak, jeśli uruchomię Debug-- ustawić mój punkt przerwania tam prawo. 402 00:17:57,380 --> 00:17:58,055 Biegnę Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> OK. 405 00:18:16,550 --> 00:18:17,050 Tak. 406 00:18:17,050 --> 00:18:20,350 Tak naprawdę, GDB miał się, że powiedział mi, że 407 00:18:20,350 --> 00:18:22,300 Usterka nie była segmentacja. 408 00:18:22,300 --> 00:18:24,883 Nie wiem, co się dzieje właśnie tam, ale kiedy prowadził ją, 409 00:18:24,883 --> 00:18:25,590 to działa. 410 00:18:25,590 --> 00:18:29,410 Po uruchomieniu linii kodu przez i GDB może po prostu nagle rzucić się na ciebie, 411 00:18:29,410 --> 00:18:31,540 udać się i spójrz, co czerwone jest błąd. 412 00:18:31,540 --> 00:18:33,930 To będzie wam powiedzieć, hej, ty miał winy segmentacji, 413 00:18:33,930 --> 00:18:38,550 co oznacza, że ​​starał się dostęp miejsca w tablicy, który nie istnieje. 414 00:18:38,550 --> 00:18:39,050 Tak. 415 00:18:39,050 --> 00:18:43,280 >> Więc w następnym problemu określone w tym tygodniu, chłopaki 416 00:18:43,280 --> 00:18:45,600 będzie prawdopodobnie dużo Zmienne pływających wokół. 417 00:18:45,600 --> 00:18:48,560 Nie zamierzamy być pewien, co wszystkie one oznaczają w pewnym momencie. 418 00:18:48,560 --> 00:18:53,560 Więc GDB będzie naprawdę pomóc w zastanawianie z czego wszystkie są zrównując 419 00:18:53,560 --> 00:18:55,940 i jest w stanie zobaczyć, że wizualnie. 420 00:18:55,940 --> 00:19:01,995 Czy ktoś wiedzą jak żadnej z tych rzeczy działa? 421 00:19:01,995 --> 00:19:02,495 Chłodny. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 W porządku. 424 00:19:10,620 --> 00:19:14,260 Więc po tym, jesteśmy zamiar nurkować w prawo 425 00:19:14,260 --> 00:19:17,562 na cztery różne rodzaje rodzaju na ten tydzień. 426 00:19:17,562 --> 00:19:19,520 Jak wielu z was, najpierw wszystkim, zanim zaczniemy, 427 00:19:19,520 --> 00:19:23,020 Przeczytałem całą specyfikację dla pset3? 428 00:19:23,020 --> 00:19:23,824 OK. 429 00:19:23,824 --> 00:19:24,740 Jestem dumny z was. 430 00:19:24,740 --> 00:19:29,110 To tak, jakby połowa klasy, która jest znacznie więcej niż ostatnim razem. 431 00:19:29,110 --> 00:19:33,950 >> Tak, to świetnie, bo gdy mówimy o treści 432 00:19:33,950 --> 00:19:36,170 w lecture-- lub przykro, w section-- lubię 433 00:19:36,170 --> 00:19:38,210 odnoszą się wiele, że z powrotem do tego, co pset jest 434 00:19:38,210 --> 00:19:40,210 i jak chcesz wdrożenie, że w pset. 435 00:19:40,210 --> 00:19:42,400 Więc jeśli przyjdziesz o przeczytać specyfikację, to będziesz 436 00:19:42,400 --> 00:19:45,510 być o wiele łatwiejsze do zrozumienia to, co mówię, kiedy mówię, 437 00:19:45,510 --> 00:19:48,720 oh hej, to może być naprawdę Dobrym miejscem do realizacji tego rodzaju. 438 00:19:48,720 --> 00:19:52,870 Więc tych, którzy czytać spec wie, że w ramach swojej pset, 439 00:19:52,870 --> 00:19:54,900 będziesz musiał Napisać do rodzaju sortowania. 440 00:19:54,900 --> 00:19:58,670 Więc może to być bardzo pomocne dla wielu z was dzisiaj. 441 00:19:58,670 --> 00:20:01,760 >> Będziemy więc zacząć od, zasadniczo, najprostszy typ 442 00:20:01,760 --> 00:20:04,580 od rodzaju, rodzaj wyboru. 443 00:20:04,580 --> 00:20:06,800 Typowy algorytm jak pójdziemy na ten temat 444 00:20:06,800 --> 00:20:10,460 jest-- Dawid przeszedł przez to wszystko wykład, więc będę szybko poruszać się 445 00:20:10,460 --> 00:20:13,900 here-- jest w istocie, to mają tablicę wartości. 446 00:20:13,900 --> 00:20:17,170 A potem odnaleźć Najmniejsza wartość nieposortowane 447 00:20:17,170 --> 00:20:20,200 i zamienić tę wartość z pierwsza wartość nieposortowane. 448 00:20:20,200 --> 00:20:22,700 A potem po prostu powtarzać z resztą swojej listy. 449 00:20:22,700 --> 00:20:25,740 >> A oto wizualne wyjaśnienia o tym, jak to będzie działać. 450 00:20:25,740 --> 00:20:30,460 Tak na przykład, jeśli było rozpocząć z tablicą z pięciu elementów, indeks 451 00:20:30,460 --> 00:20:35,910 0 do 4, z 3, 5, 2, 6 i 4 Wartości umieszczony w array-- więc teraz, 452 00:20:35,910 --> 00:20:38,530 jesteśmy po prostu zamiar założyć że wszyscy są nieposortowane 453 00:20:38,530 --> 00:20:41,130 dlatego, że nie testowałem inaczej. 454 00:20:41,130 --> 00:20:44,130 >> Więc jak to swego wyboru będzie Praca jest, że będzie to pierwszy 455 00:20:44,130 --> 00:20:46,800 prowadzony przez całości z nieposortowanej tablicy. 456 00:20:46,800 --> 00:20:49,120 To wybrać się najmniejszą wartość. 457 00:20:49,120 --> 00:20:51,750 W tym przypadku, 3, tuż Teraz jest najmniejsza. 458 00:20:51,750 --> 00:20:52,680 To staje się 5. 459 00:20:52,680 --> 00:20:55,620 Nie, 5 nie jest większa than-- lub przykro, to nie mniej than-- 3. 460 00:20:55,620 --> 00:20:57,779 Tak więc wartość minimalna jest nadal 3. 461 00:20:57,779 --> 00:20:58,695 A następnie dostać się do 2. 462 00:20:58,695 --> 00:21:00,990 Widzi, oh komputer, 2 jest mniejsza niż 3. 463 00:21:00,990 --> 00:21:02,750 2 musi być teraz wartość minimalna. 464 00:21:02,750 --> 00:21:06,630 I tak 2 swapy z tej pierwszej wartości. 465 00:21:06,630 --> 00:21:10,702 >> Więc po jednym przejściu, możemy rzeczywiście zobaczyć że 2 i 3 są zamienione. 466 00:21:10,702 --> 00:21:13,910 A my po prostu będzie dalej robić to ponownie z resztą tablicy. 467 00:21:13,910 --> 00:21:17,660 Więc będziemy po prostu uruchomić poprzez ostatnie cztery indeksy tablicy. 468 00:21:17,660 --> 00:21:20,670 Zobaczymy, że 3 następna wartość minimalna. 469 00:21:20,670 --> 00:21:23,240 Tak więc mamy zamiar zamienić, że z 4. 470 00:21:23,240 --> 00:21:26,900 A potem po prostu zamiar utrzymać przebiegającej przez aż w końcu, ty 471 00:21:26,900 --> 00:21:33,730 dostać się do posortowanej tablicy, w której Wszystko 2, 3, 4, 5 i 6 są klasyfikowane. 472 00:21:33,730 --> 00:21:37,530 Czy wszyscy rozumieją logikę jak działa to swego wyboru? 473 00:21:37,530 --> 00:21:39,669 >> Wystarczy mieć jakiś o minimalnej wartości. 474 00:21:39,669 --> 00:21:41,210 Jesteś śledzenie, co to jest. 475 00:21:41,210 --> 00:21:45,170 A kiedy go znaleźć, można go wymienić od pierwszej wartości w array-- 476 00:21:45,170 --> 00:21:48,740 lub nie pierwszym value-- następna wartość w tablicy. 477 00:21:48,740 --> 00:21:50,150 Chłodny. 478 00:21:50,150 --> 00:21:55,460 >> Tak was rodzaj widziałem z krótkim spojrzenie, 479 00:21:55,460 --> 00:21:58,450 będziemy pseudocode to. 480 00:21:58,450 --> 00:22:02,510 Więc jeśli macie w plecy chcą tworzą grupę, wszyscy w tabeli 481 00:22:02,510 --> 00:22:06,170 mogą tworzyć trochę partnera, zamierzam dać wam jak trzy minuty 482 00:22:06,170 --> 00:22:08,190 po prostu porozmawiać przez logika, w języku angielskim, 483 00:22:08,190 --> 00:22:14,161 w jaki sposób możemy być w stanie realizować pseudokod napisać coś w rodzaju wyboru. 484 00:22:14,161 --> 00:22:14,910 I nie cukierki. 485 00:22:14,910 --> 00:22:16,118 Proszę przyjść i dostać cukierki. 486 00:22:16,118 --> 00:22:19,520 Jeśli jesteś w plecy i chcesz cukierki, słodycze mogę rzucić na ciebie. 487 00:22:19,520 --> 00:22:22,850 Właściwie, to you-- cool. 488 00:22:22,850 --> 00:22:23,552 Przepraszam. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 OK. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Więc jeśli chcemy, jak klasa, zapisu pseudokod 493 00:25:27,140 --> 00:25:30,466 w jaki sposób można się zbliżyć ten problem, po prostu czuć się swobodnie. 494 00:25:30,466 --> 00:25:32,340 Ja po prostu przejść się i, w porządku, poproś grupy 495 00:25:32,340 --> 00:25:35,065 do następnego wiersza co powinniśmy robić. 496 00:25:35,065 --> 00:25:37,840 Więc jeśli chcecie zacząć się, co jest pierwszą rzeczą, 497 00:25:37,840 --> 00:25:40,600 robić, gdy starasz się wdrożenie sposób, aby rozwiązać ten program 498 00:25:40,600 --> 00:25:43,480 do selektywnego posortować listę? 499 00:25:43,480 --> 00:25:46,349 Załóżmy po prostu my mają tablicę, dobrze? 500 00:25:46,349 --> 00:25:49,088 >> PUBLICZNOŚCI: Chcesz stworzyć niektóre rodzaj [niesłyszalne], że jesteś 501 00:25:49,088 --> 00:25:50,420 przebiegającej przez całe tablicy. 502 00:25:50,420 --> 00:25:51,128 >> ANDI PENG: Racja. 503 00:25:51,128 --> 00:25:54,100 Więc masz zamiar chcą iteracji na każdym miejscu, prawda? 504 00:25:54,100 --> 00:26:05,490 Tak, świetnie. 505 00:26:05,490 --> 00:26:08,600 Jeśli chcecie mi dać następna line-- tak, w plecy. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> PUBLICZNOŚCI: Sprawdź je wszystkie najmniejszego. 508 00:26:13,290 --> 00:26:14,248 >> ANDI PENG: Nie pójdziemy. 509 00:26:14,248 --> 00:26:17,438 Dlatego chcemy, aby przejść i sprawdzić, zobaczyć, co wartość minimalna jest, prawda? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Mam zamiar skrócić, że do "min." 512 00:26:24,840 --> 00:26:27,658 Co chcecie zrobić po znalazłeś minimalną wartość? 513 00:26:27,658 --> 00:26:28,533 >> PUBLICZNOŚCI: [niesłyszalne] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI PENG: Więc będziesz chciał przełączyć go pierwszy z tej tablicy, 516 00:26:33,150 --> 00:26:33,650 dobrze? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 To początek, mam zamiar powiedzieć. 519 00:26:46,850 --> 00:26:47,220 W porządku. 520 00:26:47,220 --> 00:26:50,386 Więc teraz, kiedy zamieniłem pierwszy jedno, co chcesz zrobić, po tym? 521 00:26:50,386 --> 00:26:54,840 Więc teraz wiemy, że ten tutaj musi być najmniejsza wartość, prawda? 522 00:26:54,840 --> 00:26:58,310 Wtedy masz dodatkowy odpoczynek tablicy, która jest bez sortowania. 523 00:26:58,310 --> 00:27:01,569 Więc to, co chcesz robić tutaj, jeśli Ciebie faceci chcą dać mi kolejną linię? 524 00:27:01,569 --> 00:27:04,610 PUBLICZNOŚCI: Więc chcesz iteracji w pozostałej części tablicy. 525 00:27:04,610 --> 00:27:05,276 ANDI PENG: Tak. 526 00:27:05,276 --> 00:27:09,857 A więc to, co jest iteracja rodzaj oznaczać będziemy prawdopodobnie potrzebować? 527 00:27:09,857 --> 00:27:10,440 Jaki rodzaj-- 528 00:27:10,440 --> 00:27:12,057 >> PUBLICZNOŚCI: Och, dodatkowa zmienna? 529 00:27:12,057 --> 00:27:13,890 ANDI PENG: Prawdopodobnie inny dla pętli, prawda? 530 00:27:13,890 --> 00:27:28,914 Więc pewnie będzie chciał iteracyjne through-- świetnie. 531 00:27:28,914 --> 00:27:31,830 I wtedy masz zamiar wrócić i Prawdopodobnie ponownie sprawdzić minimalną, 532 00:27:31,830 --> 00:27:32,100 dobrze? 533 00:27:32,100 --> 00:27:34,975 I masz zamiar powtarzać to, ponieważ pętle po prostu się 534 00:27:34,975 --> 00:27:36,010 biec, prawda? 535 00:27:36,010 --> 00:27:39,190 >> Tak jak chłopaki widzą, mamy Wystarczy ogólny Pseudokod 536 00:27:39,190 --> 00:27:41,480 od tego, jak chcemy ten program szukać. 537 00:27:41,480 --> 00:27:46,646 Ten iterate tutaj, co mamy zazwyczaj trzeba pisać w naszym kodzie 538 00:27:46,646 --> 00:27:49,270 jeśli chcemy iteracji przez tablica, jaki typ struktury? 539 00:27:49,270 --> 00:27:51,030 Myślę, że Christabel już powiedziałem tego wcześniej. 540 00:27:51,030 --> 00:27:51,500 >> PUBLICZNOŚCI: A dla pętli. 541 00:27:51,500 --> 00:27:52,160 >> ANDI PENG: A dla pętli? 542 00:27:52,160 --> 00:27:52,770 Dokładnie. 543 00:27:52,770 --> 00:27:56,060 Więc to jest chyba będzie na pętli. 544 00:27:56,060 --> 00:27:59,240 Co to jest kontrola tutaj będzie oznaczać? 545 00:27:59,240 --> 00:28:02,536 Zazwyczaj, jeśli chcesz sprawdzić jeśli coś jest coś else-- 546 00:28:02,536 --> 00:28:03,270 >> PUBLICZNOŚCI: Jeśli. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: AN jeśli, prawda? 548 00:28:06,790 --> 00:28:10,790 A następnie konwersja tutaj, będziemy przejść na później, bo David 549 00:28:10,790 --> 00:28:12,770 przeszedł, że w wykładzie, jak również. 550 00:28:12,770 --> 00:28:14,580 A potem drugi iterate implies-- 551 00:28:14,580 --> 00:28:15,120 >> PUBLICZNOŚCI: Kolejna pętla for. 552 00:28:15,120 --> 00:28:16,745 >> ANDI PENG: --another pętli, dokładnie. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Więc jeśli szukamy co to poprawnie, możemy 555 00:28:22,000 --> 00:28:24,680 Można zobaczyć, że jesteśmy prawdopodobnie będzie potrzebował zagnieżdżonych pętli for 556 00:28:24,680 --> 00:28:28,330 z instrukcji warunkowej w nie a następnie rzeczywisty fragment kodu, który jest 557 00:28:28,330 --> 00:28:31,360 zamiar zamienić wartości. 558 00:28:31,360 --> 00:28:35,980 Tak już po prostu ogólnie napisane kod tutaj pseudokod. 559 00:28:35,980 --> 00:28:38,910 I wtedy jesteśmy naprawdę dzieje fizycznie, jako klasa 560 00:28:38,910 --> 00:28:40,700 starają się realizować to dzisiaj. 561 00:28:40,700 --> 00:28:42,486 Wróćmy do tego IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> O o. 564 00:28:50,230 --> 00:28:51,754 Dlaczego jest to, że not-- tam jest. 565 00:28:51,754 --> 00:28:52,253 OK. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Niestety, pozwól mi spróbować przybliżyć nieco więcej. 568 00:28:57,500 --> 00:28:59,310 No to jedziemy. 569 00:28:59,310 --> 00:29:05,060 Wszystko robię tu stworzyłem program o nazwie "Wybór / sort.c." 570 00:29:05,060 --> 00:29:10,860 Stworzyłem tablicę dziewięciu Wartości, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Obecnie, jak można zobaczyć, że są nieuporządkowane. 572 00:29:14,370 --> 00:29:17,880 n będzie liczbą, że informuje o ilości wartości 573 00:29:17,880 --> 00:29:18,920 masz w tablicy. 574 00:29:18,920 --> 00:29:20,670 W tym przypadku mamy dziewięć wartości. 575 00:29:20,670 --> 00:29:23,760 A ja właśnie dostałem pętli for tutaj że wypisuje nieposortowanej tablicy. 576 00:29:23,760 --> 00:29:28,370 >> I na koniec, Ja również dostałem w Pętla, że ​​po prostu drukuje go ponownie. 577 00:29:28,370 --> 00:29:32,070 Więc teoretycznie, jeśli tego programu działa poprawnie, na koniec, 578 00:29:32,070 --> 00:29:35,670 powinieneś zobaczyć wydrukowane na pętli w której 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 są prawidłowo kolejności. 580 00:29:39,310 --> 00:29:43,410 >> Więc mamy naszą Pseudokod tutaj. 581 00:29:43,410 --> 00:29:46,090 Czy ktoś chce to-- jestem zamiar iść prosić o volunteers-- 582 00:29:46,090 --> 00:29:49,540 Powiedz mi dokładnie, co, jeśli typ Chcemy, aby, po pierwsze, po prostu iteracji 583 00:29:49,540 --> 00:29:52,840 przez początku tablicy? 584 00:29:52,840 --> 00:29:55,204 Co to jest linia kodu jestem Prawdopodobnie będzie trzeba tutaj? 585 00:29:55,204 --> 00:29:56,990 >> PUBLICZNOŚCI: [niesłyszalne] 586 00:29:56,990 --> 00:29:59,010 >> ANDI PENG: Tak, czuję wolne to-- Przepraszam Cię 587 00:29:59,010 --> 00:30:02,318 nie mają stanąć up-- dotyk swobodnie podnosić głos trochę. 588 00:30:02,318 --> 00:30:08,190 >> PUBLICZNOŚCI: Dla int i równa 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI PENG: Tak, dobrze. 590 00:30:10,690 --> 00:30:15,220 >> PUBLICZNOŚCI: i jest mniejsza niż długość tablicy. 591 00:30:15,220 --> 00:30:19,630 >> ANDI PENG: Tak trzymać się nic tu, bo 592 00:30:19,630 --> 00:30:23,060 nie mają funkcję, która mówi nam długość tablicy, 593 00:30:23,060 --> 00:30:25,790 Mamy już wartość, która przechowuje, że. 594 00:30:25,790 --> 00:30:27,920 Dobrze? 595 00:30:27,920 --> 00:30:31,010 Inną rzeczą, aby utrzymać w mind-- w tablicy 596 00:30:31,010 --> 00:30:33,940 z dziewięciu wartości, jakie są wskaźniki? 597 00:30:33,940 --> 00:30:38,720 Powiedzmy, że ta tablica była od 0 do 3. 598 00:30:38,720 --> 00:30:41,500 Zobaczysz, że ostatni Strona jest w rzeczywistości 3. 599 00:30:41,500 --> 00:30:45,530 Nie jest to 4, chociaż istnieje cztery wartości w tablicy. 600 00:30:45,530 --> 00:30:49,866 >> Więc tutaj, musimy być bardzo ostrożni, tego, co nasz warunek długości 601 00:30:49,866 --> 00:30:50,490 będzie. 602 00:30:50,490 --> 00:30:51,948 >> PUBLICZNOŚCI: Czy nie byłoby n minus 1? 603 00:30:51,948 --> 00:30:54,440 ANDI PENG: To będzie n minus 1, dokładnie. 604 00:30:54,440 --> 00:30:57,379 Czy to ma sens, dlaczego to n minus 1, każdy? 605 00:30:57,379 --> 00:30:58,920 To dlatego, że tablice są indeksowane od zera. 606 00:30:58,920 --> 00:31:02,010 Zaczynają się od 0 i uruchomić do n minus 1. 607 00:31:02,010 --> 00:31:03,210 Tak, to jest trochę skomplikowane. 608 00:31:03,210 --> 00:31:03,730 OK. 609 00:31:03,730 --> 00:31:05,929 I wtedy-- 610 00:31:05,929 --> 00:31:08,054 PUBLICZNOŚCI: Isnt'1, że już załatwione choć, 611 00:31:08,054 --> 00:31:11,400 Nie mówiąc po prostu "mniejsze lub równa się "i po prostu mówiąc" mniej niż? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI PENG: To bardzo dobre pytanie. 613 00:31:13,108 --> 00:31:13,630 Więc tak. 614 00:31:13,630 --> 00:31:17,410 Ale także sposób, w jaki jesteśmy realizacji prawa kontroli, 615 00:31:17,410 --> 00:31:19,120 trzeba porównać dwie wartości. 616 00:31:19,120 --> 00:31:21,009 Więc rzeczywiście chcesz zostawić "na" pusty. 617 00:31:21,009 --> 00:31:23,050 Bo jeśli porównać ten jeden, nie będziesz 618 00:31:23,050 --> 00:31:25,530 mają nic po nim porównać, prawda? 619 00:31:25,530 --> 00:31:27,460 Tak. 620 00:31:27,460 --> 00:31:29,297 Więc i ++. 621 00:31:29,297 --> 00:31:30,380 Dodajmy nasze uchwyty w. 622 00:31:30,380 --> 00:31:30,880 Ups. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Wielki. 625 00:31:34,710 --> 00:31:39,117 Mamy więc początek naszego zewnętrznej pętli. 626 00:31:39,117 --> 00:31:41,450 Więc teraz pewnie chce utworzyć zmienną o utrzymanie 627 00:31:41,450 --> 00:31:43,085 utwór najmniejszej wartości, prawda? 628 00:31:43,085 --> 00:31:45,751 Czy ktoś chce dać mi linia kodu, który miałby to robić? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Czego potrzebujemy, jeśli chcemy chciał zapisać coś? 631 00:31:53,570 --> 00:31:55,047 >> Dobrze. 632 00:31:55,047 --> 00:31:57,630 Może lepiej, że nazwa by być: "temp" całkowicie works-- 633 00:31:57,630 --> 00:32:00,655 może bardziej trafnie nazwany będzie, jeśli chcemy najmniejszą value-- 634 00:32:00,655 --> 00:32:01,624 >> PUBLICZNOŚCI: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI PENG: min, nie idziemy. 636 00:32:02,790 --> 00:32:05,230 min byłoby dobre. 637 00:32:05,230 --> 00:32:08,340 I tak oto, co my Aby zainicjować go? 638 00:32:08,340 --> 00:32:09,620 Jest to trochę skomplikowane. 639 00:32:09,620 --> 00:32:13,580 Bo teraz u początek tej tablicy, 640 00:32:13,580 --> 00:32:15,730 nie patrzył na nic, prawda? 641 00:32:15,730 --> 00:32:19,200 Więc co, automatycznie, jeśli jesteśmy po prostu na i jest równa 0, 642 00:32:19,200 --> 00:32:22,302 co chcemy zainicjować nasza pierwsza wartość minimalna do? 643 00:32:22,302 --> 00:32:22,802 PUBLICZNOŚCI: i. 644 00:32:22,802 --> 00:32:24,790 ANDI PENG: i dokładnie. 645 00:32:24,790 --> 00:32:27,040 Christabel, dlaczego chcemy sformatować ją do i? 646 00:32:27,040 --> 00:32:28,510 >> PUBLICZNOŚCI: Ponieważ, dobrze, Zaczynamy od 0. 647 00:32:28,510 --> 00:32:31,660 Tak, bo nie mamy nic do porównania jej minimalna będzie w końcu jest 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI PENG: Dokładnie. 649 00:32:32,451 --> 00:32:34,400 Więc ona jest dokładnie prawo. 650 00:32:34,400 --> 00:32:36,780 Ponieważ nie mamy w rzeczywistości spojrzał na cokolwiek jeszcze, 651 00:32:36,780 --> 00:32:38,680 nie wiemy, co nasz Minimalna wartość to. 652 00:32:38,680 --> 00:32:41,960 Chcemy po prostu zainicjować go ja, który obecnie jest tutaj. 653 00:32:41,960 --> 00:32:44,750 A jak będziemy ruch w dół tej tablicy, 654 00:32:44,750 --> 00:32:48,122 zobaczymy, że z każdym dodatkowe przejście, i zwiększa. 655 00:32:48,122 --> 00:32:49,830 I tak w tym punkcie, I prawdopodobnie będzie 656 00:32:49,830 --> 00:32:52,329 chce być minimalna, bo to będzie cokolwiek 657 00:32:52,329 --> 00:32:54,520 jest początkiem nieposortowanej tablicy. 658 00:32:54,520 --> 00:32:55,270 Chłodny. 659 00:32:55,270 --> 00:32:58,720 >> Więc teraz, że chcemy dodać pętli for tutaj to 660 00:32:58,720 --> 00:33:03,225 będzie iterację nieposortowane, czy reszta tej tablicy. 661 00:33:03,225 --> 00:33:05,808 Czy ktoś chce dać mi linia kodu, który miałby to robić? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- co musimy tutaj, w dół? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Co się dzieje w tym iść do pętli? 666 00:33:18,820 --> 00:33:19,465 Tak. 667 00:33:19,465 --> 00:33:21,590 PUBLICZNOŚCI: Więc my chcemy mieć inną liczbę całkowitą 668 00:33:21,590 --> 00:33:25,080 ponieważ jesteśmy uruchomiony przez resztę tablicy zamiast I, więc może 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI PENG: Tak, j brzmi dobrze dla mnie. 671 00:33:27,301 --> 00:33:27,850 Równa? 672 00:33:27,850 --> 00:33:33,930 >> PUBLICZNOŚCI: Więc byłoby ja plus 1, ponieważ zaczynasz na następnej wartości. 673 00:33:33,930 --> 00:33:40,395 A następnie do end-- Ponownie więc, j jest mniejszej niż n minus 1, a następnie j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI PENG: Świetnie. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> A potem tu, będziemy chcieli aby sprawdzić, czy nasz warunek jest spełniony, 677 00:33:52,750 --> 00:33:53,250 dobrze? 678 00:33:53,250 --> 00:33:55,740 Ponieważ chcesz Zmiana wartości minimalnej 679 00:33:55,740 --> 00:33:58,700 czy jest to w rzeczywistości mniejsze niż to, co jesteś porównując ją, prawda? 680 00:33:58,700 --> 00:34:01,146 Więc co będziemy chcieli tutaj? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Sprawdź. 683 00:34:04,897 --> 00:34:06,730 Jaki typ rachunku są prawdopodobnie będzie 684 00:34:06,730 --> 00:34:08,389 ti chcesz używać, jeśli chcę coś sprawdzić? 685 00:34:08,389 --> 00:34:09,360 >> PUBLICZNOŚCI: if. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: if. 687 00:34:10,485 --> 00:34:13,155 Więc if-- i co będzie warunkiem, że chcemy wewnątrz 688 00:34:13,155 --> 00:34:13,988 naszego if? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> PUBLICZNOŚCI: Jeżeli wartość j jest mniejsza od wartości ja-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI PENG: Dokładnie. 692 00:34:24,600 --> 00:34:27,480 Więc if-- więc ta tablica jest nazywany "tablica". 693 00:34:27,480 --> 00:34:27,980 Wielki. 694 00:34:27,980 --> 00:34:30,465 Więc jeśli array-- co to było? 695 00:34:30,465 --> 00:34:31,090 Powtórz to. 696 00:34:31,090 --> 00:34:39,590 >> PUBLICZNOŚCI: Jeśli tablica-j jest mniejsza niż tablica-i, to możemy zmienić min. 697 00:34:39,590 --> 00:34:41,590 Więc min będzie j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI PENG: Czy to ma sens? 700 00:34:47,249 --> 00:34:48,670 OK. 701 00:34:48,670 --> 00:34:52,929 A teraz tutaj, w rzeczywistości chcą wprowadzić swap, prawda? 702 00:34:52,929 --> 00:34:58,285 Więc przypominam, w wykładzie, że Dawid, kiedy próbował zamienić the--, co było 703 00:34:58,285 --> 00:34:59,996 it-- sok pomarańczowy i milk-- 704 00:34:59,996 --> 00:35:01,150 >> PUBLICZNOŚCI: To było obrzydliwe. 705 00:35:01,150 --> 00:35:02,816 >> ANDI PENG: Tak, to był rodzaj brutto. 706 00:35:02,816 --> 00:35:05,310 Ale to był całkiem dobry Pojęcie czasu wykazania. 707 00:35:05,310 --> 00:35:08,430 Więc myślę o swoich wartościach tutaj. 708 00:35:08,430 --> 00:35:10,794 Masz tablicę od min, tablica i, 709 00:35:10,794 --> 00:35:12,460 czy co staraliśmy się zamienić tutaj. 710 00:35:12,460 --> 00:35:15,310 I prawdopodobnie nie może przelać je do siebie w tym samym czasie, co? 711 00:35:15,310 --> 00:35:17,180 Więc co my teraz w celu trzeba utworzyć tutaj 712 00:35:17,180 --> 00:35:19,126 w celu wymiany wartości poprawnie? 713 00:35:19,126 --> 00:35:19,820 >> PUBLICZNOŚCI: Zmienna tymczasowa. 714 00:35:19,820 --> 00:35:21,370 >> ANDI PENG: Zmienna tymczasowa. 715 00:35:21,370 --> 00:35:22,570 Więc zróbmy int temp. 716 00:35:22,570 --> 00:35:25,681 Zobacz, to byłoby lepiej Czas to-- zaraz, co to było? 717 00:35:25,681 --> 00:35:26,180 OK. 718 00:35:26,180 --> 00:35:29,800 Więc to byłoby lepiej Czas nazwać zmienną "temp". 719 00:35:29,800 --> 00:35:30,730 Więc zróbmy int temp. 720 00:35:30,730 --> 00:35:32,563 Co my teraz ustawiona temp równą tutaj? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 PUBLICZNOŚCI: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI PENG: To trochę skomplikowane. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 To naprawdę nie ma znaczenia, w końcu. 727 00:35:44,880 --> 00:35:47,690 Nie ma znaczenia, co Kolejność zdecydujesz się zamienić w 728 00:35:47,690 --> 00:35:50,862 tak długo, jak jesteś upewniając się, że jesteś śledzenie, co masz zamiana. 729 00:35:50,862 --> 00:35:52,250 >> PUBLICZNOŚCI: To może być tablica-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI PENG: Tak, zróbmy tablicy-I. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 A potem, co jest następna linia kodu chcemy tu mamy? 733 00:35:59,305 --> 00:36:00,680 PUBLICZNOŚCI: tablica-i równa tablicy-J. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI PENG: I na koniec? 736 00:36:08,070 --> 00:36:12,070 PUBLICZNOŚCI: array tablica-j-i równa. 737 00:36:12,070 --> 00:36:14,525 Publiczność: Albo tablica-j równi tablica-temp-- lub temp. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI PENG: OK. 740 00:36:19,430 --> 00:36:21,510 Warto więc uruchomić to i zobaczyć jeśli to się uda. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Gdzie jest, że dzieje? 743 00:36:39,335 --> 00:36:40,210 Och, to jest problem. 744 00:36:40,210 --> 00:36:44,320 Zobacz, na linii 40, jesteśmy próby użycia tablicy-j? 745 00:36:44,320 --> 00:36:47,022 Ale gdzie j istnieją tylko w? 746 00:36:47,022 --> 00:36:48,402 >> PUBLICZNOŚCI: W pętli for. 747 00:36:48,402 --> 00:36:49,110 ANDI PENG: Racja. 748 00:36:49,110 --> 00:36:51,730 Tak więc to, co mamy zamiar zrobić? 749 00:36:51,730 --> 00:36:53,170 >> PUBLICZNOŚCI: Zdefiniuj go poza the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 PUBLICZNOŚCI: Tak, myślę, że masz użyć innego if, prawda? 752 00:37:00,610 --> 00:37:05,230 Więc jak, jeśli minimum-- Wszystko w porządku, niech pomyślę. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Peng: Chłopaki, spróbuj Pozwól, aby wziąć spojrzenie na 755 00:37:09,990 --> 00:37:11,270 zobacz, co się coś, co może zrobić tutaj? 756 00:37:11,270 --> 00:37:11,811 >> PUBLICZNOŚCI: OK. 757 00:37:11,811 --> 00:37:15,900 Tak więc, jeśli minimalna nie równa j-- więc jeśli minimalna jest nadal ja-- 758 00:37:15,900 --> 00:37:17,570 wtedy nie będzie musiał wymieniać. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI PENG: Czy to równe i? 761 00:37:24,712 --> 00:37:25,920 Co chcesz tu powiedzieć? 762 00:37:25,920 --> 00:37:30,494 >> PUBLICZNOŚCI: Albo tak, jeśli minimalna nie równy i, tak. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI PENG: OK. 765 00:37:40,210 --> 00:37:42,040 Dobrze, że rozwiązuje, rodzaj, nasze problemy. 766 00:37:42,040 --> 00:37:47,265 Ale to wciąż nie rozwiązuje Problem, co się stanie, jeśli j-- od j 767 00:37:47,265 --> 00:37:49,890 nie istnieje poza tym, to, co czy chcemy z nim zrobić? 768 00:37:49,890 --> 00:37:50,698 Zadeklarować go na zewnątrz? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Spróbujmy działa to. 771 00:38:02,730 --> 00:38:04,435 O o. 772 00:38:04,435 --> 00:38:06,200 Nasz jakby nie działa. 773 00:38:06,200 --> 00:38:10,060 >> Jak widać, nasz pierwotny Tablica miał te wartości. 774 00:38:10,060 --> 00:38:14,800 A potem powinien mieć była w 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 To nie działa. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Co robimy? 778 00:38:17,184 --> 00:38:17,850 PUBLICZNOŚCI: Debug. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI PENG: Wszystko w porządku, możemy spróbować. 781 00:38:23,370 --> 00:38:25,030 Możemy debugowania. 782 00:38:25,030 --> 00:38:26,042 Oddalanie się trochę. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Ustawmy naszą pułapkę. 785 00:38:33,656 --> 00:38:37,280 Chodźmy like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Tak, bo już wiemy, że te linie, 15 do 22, 787 00:38:40,444 --> 00:38:43,610 są working-- ponieważ wszystkie robię to po prostu iteracja i printing-- 788 00:38:43,610 --> 00:38:45,406 Mogę iść do przodu i pominięcia. 789 00:38:45,406 --> 00:38:47,280 Zacznijmy od linii 25. 790 00:38:47,280 --> 00:38:48,712 Oop, pozwól mi pozbyć się tego. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> PUBLICZNOŚCI: Więc Breakpoint gdzie zaczyna się debugowania? 793 00:38:54,057 --> 00:38:54,890 ANDI PENG: Albo przystanki. 794 00:38:54,890 --> 00:38:55,670 PUBLICZNOŚCI: Albo przystanki. 795 00:38:55,670 --> 00:38:55,930 ANDI PENG: Tak. 796 00:38:55,930 --> 00:38:58,640 Można ustawić kilka punktów przerwania i może po prostu przejść z jednego do drugiego. 797 00:38:58,640 --> 00:39:01,590 Ale w tym przypadku nie wiemy jeżeli błąd się dzieje. 798 00:39:01,590 --> 00:39:03,780 Więc po prostu chcą zacząć od góry do dołu. 799 00:39:03,780 --> 00:39:05,020 Tak. 800 00:39:05,020 --> 00:39:05,550 OK. 801 00:39:05,550 --> 00:39:08,460 >> Tak więc ta linia tutaj, możemy wkroczyć. 802 00:39:08,460 --> 00:39:11,499 Widać tu, mamy tablicę. 803 00:39:11,499 --> 00:39:13,290 To są wartości które są w tablicy. 804 00:39:13,290 --> 00:39:16,360 Czy widzisz, że, jak wskaźnik 0, to odpowiada value-- oh, 805 00:39:16,360 --> 00:39:17,526 Mam zamiar spróbować, aby powiększyć. 806 00:39:17,526 --> 00:39:20,650 Niestety, jest to naprawdę trudne do see-- na indeks tablicy 0, 807 00:39:20,650 --> 00:39:24,090 możemy mieć wartość 4, a Następnie tak dalej i tak dalej. 808 00:39:24,090 --> 00:39:25,670 Mamy zmiennych lokalnych. 809 00:39:25,670 --> 00:39:28,570 Teraz i jest równe 0, co chcemy go mieć. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> I tak trzymajmy Krokowe. 812 00:39:33,690 --> 00:39:36,850 Nasz minimalna jest równa 0, które my także chcemy go mieć. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 A potem wejść na nasz drugi do pętli, jeśli tablica-j jest mniejsza niż tablicy-i, 815 00:39:45,560 --> 00:39:46,380 którym nie jest. 816 00:39:46,380 --> 00:39:48,130 Więc nie widzisz, jak które pomijane, że? 817 00:39:48,130 --> 00:39:52,430 >> PUBLICZNOŚCI: Nie wolno również, jeśli Minimalna, wszystkie that-- nie powinien, że 818 00:39:52,430 --> 00:39:55,424 się wewnątrz pierwszej pętli? 819 00:39:55,424 --> 00:39:57,340 ANDI PENG: Nie, ponieważ nadal chcesz przetestować. 820 00:39:57,340 --> 00:40:00,329 Chcesz zrobić porównanie każdego czas, nawet po uruchomieniu przez niego. 821 00:40:00,329 --> 00:40:02,620 Nie można po prostu chcę to zrobić na pierwszym przełożenia. 822 00:40:02,620 --> 00:40:05,240 Chcesz to zrobić z każdy dodatkowy karnet ponownie. 823 00:40:05,240 --> 00:40:07,198 Więc chcesz sprawdzić Twój stan wewnątrz. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Więc jesteśmy po prostu będzie biec przez tutaj. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Dam ci faceci podpowiedź. 828 00:40:18,420 --> 00:40:23,910 Ma to związek z faktem, że kiedy jesteś sprawdzanie twój warunkowe, 829 00:40:23,910 --> 00:40:26,600 nie masz kontroli dla właściwego indeksu. 830 00:40:26,600 --> 00:40:32,510 Więc teraz jesteś sprawdzanie indeks tablicy z j jest mniejsza od tablicy 831 00:40:32,510 --> 00:40:33,970 indeks i. 832 00:40:33,970 --> 00:40:36,580 Ale co ty robisz się na początek pętli for? 833 00:40:36,580 --> 00:40:38,260 Czy nie ustawienie j równy I? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Tak, tak, możemy rzeczywiście wyjść tutaj debuggera. 836 00:40:45,415 --> 00:40:47,040 Warto więc przyjrzeć się naszej Pseudokod. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- będziemy zaczynają się i jest równa 0. 839 00:40:52,580 --> 00:40:54,760 Mamy zamiar iść do n minus 1. 840 00:40:54,760 --> 00:40:58,040 Sprawdźmy, czy mamy takie prawo? 841 00:40:58,040 --> 00:40:59,580 Tak, to była prawda. 842 00:40:59,580 --> 00:41:02,080 >> Tak więc w środku tu jesteśmy zamiar utworzenia wartości minimalnej 843 00:41:02,080 --> 00:41:03,630 i ustawić, że równe i. 844 00:41:03,630 --> 00:41:04,950 Czy mamy to zrobić? 845 00:41:04,950 --> 00:41:06,270 Tak, zrobiłem to. 846 00:41:06,270 --> 00:41:10,430 Teraz w naszej wewnętrznej pętli for, jesteśmy zamiar zrobić j równa i do n 1 minus. 847 00:41:10,430 --> 00:41:11,950 Czy mamy to zrobić? 848 00:41:11,950 --> 00:41:15,540 Rzeczywiście, zrobiliśmy to. 849 00:41:15,540 --> 00:41:19,922 >> Tak więc, co mamy porównanie tutaj? 850 00:41:19,922 --> 00:41:20,925 >> PUBLICZNOŚCI: j plus 1. 851 00:41:20,925 --> 00:41:21,716 ANDI PENG: Dokładnie. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 A potem będziesz chciał ustawić minimalna równa j plus 1 oraz. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Poszedłem więc przez to bardzo szybko. 856 00:41:32,640 --> 00:41:36,190 Czy wy zrozumieć dlaczego to jest j plus 1? 857 00:41:36,190 --> 00:41:36,890 OK. 858 00:41:36,890 --> 00:41:40,700 >> Tak więc w swojej tablicy, w Twoja pierwsza przechodzi przez, 859 00:41:40,700 --> 00:41:44,850 Twój pętli, na int i równa 0, po prostu 860 00:41:44,850 --> 00:41:46,740 Zakładamy, nie zostało jeszcze zmieniać. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Mamy tablicę, całkowicie, zaledwie cztery elementy nieposortowane, prawda? 863 00:41:56,760 --> 00:42:00,760 Dlatego chcemy, aby zainicjować i równej 0. 864 00:42:00,760 --> 00:42:03,650 A ja ma tylko prowadzony za pośrednictwem tej pętli. 865 00:42:03,650 --> 00:42:08,560 I tak w pierwszym przejeździe, jedziemy zainicjować zmienną o nazwie "min" 866 00:42:08,560 --> 00:42:11,245 które również jest równy i, dlatego, nie mamy minimalną wartość. 867 00:42:11,245 --> 00:42:12,870 Więc to jest obecnie równa 0, jak również. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 A potem mamy zamiar przejść. 870 00:42:17,640 --> 00:42:19,270 I chcemy ponownie iteracji. 871 00:42:19,270 --> 00:42:22,900 Teraz, gdy już znaleźli nasz minimalna jest, chcemy iteracji 872 00:42:22,900 --> 00:42:25,190 ponownie, aby sprawdzić, czy jest to porównanie, prawda? 873 00:42:25,190 --> 00:42:40,440 Więc j, tu się dzieje do jednakowego i, który jest 0. 874 00:42:40,440 --> 00:42:46,320 A potem, jeśli tablica j plus i, co to ten, który jest następny w ciągu, jako mniej 875 00:42:46,320 --> 00:42:49,270 niż co aktualnie minimum wartość, chcesz zamienić. 876 00:42:49,270 --> 00:42:56,850 >> Więc powiedzmy mamy ale, jak, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Właśnie teraz, i jest równe 0 i j wynosi 0. 878 00:43:01,610 --> 00:43:05,210 I to jest nasza wartość minimalna. 879 00:43:05,210 --> 00:43:09,950 Jeśli tablicy-j oraz ja-- więc jeśli jeden to po jednym Patrzymy 880 00:43:09,950 --> 00:43:13,450 jest większa niż przed nią to się stać minimalna. 881 00:43:13,450 --> 00:43:18,120 >> Więc widzimy, że 5 nie mniej. 882 00:43:18,120 --> 00:43:19,730 Więc to się nie być 5. 883 00:43:19,730 --> 00:43:23,580 Widzimy, że 1 jest mniejsza niż 2, prawda? 884 00:43:23,580 --> 00:43:32,970 Więc teraz wiemy, że nasze minimum to będzie wartość indeksu w 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Tak? 886 00:43:34,030 --> 00:43:39,170 I wtedy, gdy pojawi się tutaj, można zamienić poprawne wartości. 887 00:43:39,170 --> 00:43:42,610 >> Więc kiedy wy właśnie o j przed, nie patrząc na jednego 888 00:43:42,610 --> 00:43:43,260 po tym. 889 00:43:43,260 --> 00:43:44,520 Masz pomysł na ta sama wartość, która 890 00:43:44,520 --> 00:43:46,290 Dlatego po prostu nie robi nic. 891 00:43:46,290 --> 00:43:49,721 Czy to ma sens dla wszystkich, Dlatego potrzebne, że plus 1 tam? 892 00:43:49,721 --> 00:43:50,220 OK. 893 00:43:50,220 --> 00:43:53,345 Teraz wystarczy uruchomić po to, aby Upewnij się, że reszta kod jest poprawny. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Dlaczego to się dzieje? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ach, to jest to min tutaj. 898 00:44:16,364 --> 00:44:17,780 Byliśmy porównanie błędną wartość. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 O nie. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> O tak, tu byliśmy zamiana błędne wartości, jak również. 903 00:44:33,482 --> 00:44:34,940 Ponieważ byliśmy patrząc na i oraz j. 904 00:44:34,940 --> 00:44:36,440 To są ci, byliśmy kontroli. 905 00:44:36,440 --> 00:44:39,160 My rzeczywiście chcą zamienić minimalny prąd minimum, 906 00:44:39,160 --> 00:44:40,550 z tym, co na zewnątrz jest jeden. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 I jak faceci widzą w dół tutaj mamy posortowaną tablicę. 909 00:45:05,402 --> 00:45:07,110 To po prostu miał do czynienia z fakt, że przy 910 00:45:07,110 --> 00:45:09,350 byliśmy sprawdzania Wartości trakcie porównywania 911 00:45:09,350 --> 00:45:11,226 Nie szukaliśmy w odpowiednich wartości. 912 00:45:11,226 --> 00:45:13,850 Szukaliśmy w tym samym jednym tutaj, w rzeczywistości nie wymieniając go. 913 00:45:13,850 --> 00:45:17,135 Musisz spojrzeć na jeden obok do niego, a następnie można zamienić. 914 00:45:17,135 --> 00:45:19,260 Więc to, co było swego rodzaju podsłuch nasz kod wcześniej. 915 00:45:19,260 --> 00:45:22,460 I co ja tu jest wszystko debugger mógłby zrobić dla Ciebie 916 00:45:22,460 --> 00:45:23,810 Po prostu zrobił to na wyżywienie, ponieważ łatwiej 917 00:45:23,810 --> 00:45:26,320 aby zobaczyć, a nie stara aby powiększyć debuggera. 918 00:45:26,320 --> 00:45:29,391 Czy to ma sens dla każdego? 919 00:45:29,391 --> 00:45:29,890 Chłodny. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> W porządku. 922 00:45:35,410 --> 00:45:41,070 Możemy przejść do rozmowy o notacji asymptotycznej, które 923 00:45:41,070 --> 00:45:44,580 tylko fantazyjny sposób mówiąc runtimes wszystkich tych rodzajów. 924 00:45:44,580 --> 00:45:47,650 Tak wiem, Dawida, w wykładzie, poruszył czasy pracy. 925 00:45:47,650 --> 00:45:52,124 I poszedł przez cały wzoru od tego, jak obliczyć czas pracy. 926 00:45:52,124 --> 00:45:53,040 Nie martw się o to. 927 00:45:53,040 --> 00:45:54,660 Jeśli jesteś naprawdę ciekawa na, jak to działa, 928 00:45:54,660 --> 00:45:55,810 nie krępuj się mówić do mnie po sekcji. 929 00:45:55,810 --> 00:45:57,560 Możemy przejść przez wzory razem. 930 00:45:57,560 --> 00:46:00,689 Ale wszyscy macie naprawdę wie, że n do kwadratu ponad 2 931 00:46:00,689 --> 00:46:01,980 to samo jak n do kwadratu. 932 00:46:01,980 --> 00:46:04,710 Ponieważ największą liczbę, wykładnik, rośnie najbardziej. 933 00:46:04,710 --> 00:46:06,590 I tak, dla naszych celów, wszystkim dbamy o 934 00:46:06,590 --> 00:46:09,470 jest fakt, że gigantyczna liczba, która rośnie. 935 00:46:09,470 --> 00:46:13,340 >> Więc co jest najlepszym przypadku runtime wyboru rodzaju? 936 00:46:13,340 --> 00:46:15,830 Jeśli masz zamiar mieć do iteracji listy 937 00:46:15,830 --> 00:46:18,712 a następnie iterację reszta tej listy, 938 00:46:18,712 --> 00:46:20,420 ile razy są zamierzasz chyba, 939 00:46:20,420 --> 00:46:24,612 w najgorszym case-- w najlepszym przypadku, sorry-- uruchomić poprzez? 940 00:46:24,612 --> 00:46:27,070 Być może lepszym pytaniem jest zapytać, co jest najgorszym przypadku 941 00:46:27,070 --> 00:46:28,153 runtime wyboru rodzaju. 942 00:46:28,153 --> 00:46:29,366 PUBLICZNOŚCI: n do kwadratu. 943 00:46:29,366 --> 00:46:30,740 ANDI PENG: Jest n do kwadratu, w prawo. 944 00:46:30,740 --> 00:46:36,986 Więc to prosty sposób, aby myśleć o tym jest jak, za każdym razem masz dwie zagnieżdżone pętle, 945 00:46:36,986 --> 00:46:38,110 to będzie n do kwadratu. 946 00:46:38,110 --> 00:46:40,386 Bo nie tylko ty jesteś przebiegającej przez po raz kolejny, 947 00:46:40,386 --> 00:46:42,260 trzeba wrócić wokół i przepuszczano przez nią 948 00:46:42,260 --> 00:46:44,980 ponownie wewnątrz każdej wartości. 949 00:46:44,980 --> 00:46:48,640 Więc w tym przypadku, używasz n Czasy n do kwadratu, co jest-- przykro, 950 00:46:48,640 --> 00:46:50,505 n razy n, która równa się n do kwadratu. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> I sortowania jest również nieco unikalne w tym sensie 953 00:46:56,360 --> 00:46:59,774 to, że nie ma znaczenia, czy to Wartości są już w kolejności. 954 00:46:59,774 --> 00:47:01,440 To wciąż będzie przebiegać przez jakikolwiek. 955 00:47:01,440 --> 00:47:03,872 Powiedzmy, że jest to 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Niezależnie od tego, czy jest czy nie jest w Kolejność, to nadal byłby przebiegł 957 00:47:07,080 --> 00:47:08,620 i nadal sprawdzana wartość minimalną. 958 00:47:08,620 --> 00:47:10,100 Byłoby to uczyniły sama liczba kontroli 959 00:47:10,100 --> 00:47:12,780 za każdym razem, nawet jeśli nie faktycznie niczego dotykać. 960 00:47:12,780 --> 00:47:16,940 >> Więc w takim przypadku, najlepsze i najgorsze czasy pracy są rzeczywiście równoważne. 961 00:47:16,940 --> 00:47:19,160 Tak oczekiwany czas pracy od wyboru rodzaju, 962 00:47:19,160 --> 00:47:23,790 które wyznaczają symbolem theta, theta, w tym przypadku, 963 00:47:23,790 --> 00:47:24,790 będzie również n kwadratu. 964 00:47:24,790 --> 00:47:26,480 Wszystkie trzy z nich będą n do kwadratu. 965 00:47:26,480 --> 00:47:29,653 Czy wszyscy są jasne, dlaczego runtime jest n do kwadratu? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> W porządku. 968 00:47:33,980 --> 00:47:39,120 Więc jestem po prostu szybko uruchomić przez resztę rodzaju. 969 00:47:39,120 --> 00:47:41,137 Algorytm bańka sort-- pamiętać, 970 00:47:41,137 --> 00:47:43,220 to był pierwszy David podszedł w wykładzie. 971 00:47:43,220 --> 00:47:46,000 Zasadniczo, krok przez całą listę 972 00:47:46,000 --> 00:47:48,950 i swap-- Cię tylko porównać dwa na raz. 973 00:47:48,950 --> 00:47:51,350 A jeśli jest większa, niż ty po prostu zamienić je. 974 00:47:51,350 --> 00:47:53,590 Więc jeśli są większe, należy zamienić. 975 00:47:53,590 --> 00:47:56,180 Mam oficjalne tutaj. 976 00:47:56,180 --> 00:47:59,100 >> Więc powiedzmy, że trzeba było 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Można by porównaj 8 i 6. 978 00:48:00,571 --> 00:48:01,570 Trzeba by zamienić je. 979 00:48:01,570 --> 00:48:02,610 Będziesz porównaj 8 i 4. 980 00:48:02,610 --> 00:48:03,609 Trzeba by zamienić je. 981 00:48:03,609 --> 00:48:07,000 Jeśli masz do wymiany 8 i pozycji 2, zmienić je dobrze. 982 00:48:07,000 --> 00:48:10,760 Więc w takim sensie, można zobaczyć, odtwarzane w ciągu długiego okresu czasu, 983 00:48:10,760 --> 00:48:13,730 jaki rodzaj wartości od bańki do końce, dlatego nazywamy je 984 00:48:13,730 --> 00:48:15,320 sortowanie bąbelkowe. 985 00:48:15,320 --> 00:48:19,950 >> Chcemy po prostu uruchomić poprzez ponownie nasz drugi przebieg, a nasz Trzeci przebieg, 986 00:48:19,950 --> 00:48:21,150 a nasz czwartego przebiegu. 987 00:48:21,150 --> 00:48:25,820 Zasadniczo, sortowanie bąbelkowe prostu działa dopóki nie tworzyć kolejnych swapów. 988 00:48:25,820 --> 00:48:31,109 Więc w tym sensie, jest to po prostu ogólna pseudokod dla niego. 989 00:48:31,109 --> 00:48:32,650 Nie martw się, to wszystko będzie w Internecie. 990 00:48:32,650 --> 00:48:34,990 Nie mamy rzeczywiście przejść nad tym. 991 00:48:34,990 --> 00:48:38,134 >> Po prostu zainicjować licznik zmienna, która rozpoczyna się od 0. 992 00:48:38,134 --> 00:48:39,800 A my iterację całej tablicy. 993 00:48:39,800 --> 00:48:43,420 A jeśli jedna wartość jest-- jeśli wartość jest większa od tej wartości, 994 00:48:43,420 --> 00:48:44,610 masz zamiar zamienić je. 995 00:48:44,610 --> 00:48:46,860 A potem po prostu będzie dalej. 996 00:48:46,860 --> 00:48:47,970 I masz zamiar się liczyć. 997 00:48:47,970 --> 00:48:50,845 A ty po prostu się to robić ten czas licznika jest większa 998 00:48:50,845 --> 00:48:53,345 niż 0, co oznacza, że za każdym razem masz do wymiany, 999 00:48:53,345 --> 00:48:55,220 wiesz, że chcesz iść z powrotem i spróbuj ponownie. 1000 00:48:55,220 --> 00:48:59,510 Chcesz zachować kontrolę, aż wiesz, że nie masz do wymiany już. 1001 00:48:59,510 --> 00:49:05,570 >> Więc jakie są najlepsze i najgorsze środowisko wykonawcze dla przypadku bańki rodzaju? 1002 00:49:05,570 --> 00:49:09,300 I hint-- to jest rzeczywiście inna od wyboru rodzaju w tym sensie, 1003 00:49:09,300 --> 00:49:11,810 te dwie odpowiedzi nie są takie same. 1004 00:49:11,810 --> 00:49:14,709 Pomyśl o tym, co by się stało, w przypadek, gdy było już klasyfikowane. 1005 00:49:14,709 --> 00:49:16,500 I myśleć o tym, co by było, gdyby to było 1006 00:49:16,500 --> 00:49:18,372 W przypadku, w którym nie został przydzielony. 1007 00:49:18,372 --> 00:49:20,580 I można rodzaju uruchomić poprzez dlatego, że się dzieje. 1008 00:49:20,580 --> 00:49:22,954 Dam wam, jak, 30 sekundy, aby myśleć o tym. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> OK. 1011 00:49:53,540 --> 00:49:57,462 Czy ktoś ma przypuszczenie na co Najgorszy czas pracy sortowanie bąbelkowe jest? 1012 00:49:57,462 --> 00:49:57,962 Tak. 1013 00:49:57,962 --> 00:50:07,810 >> PUBLICZNOŚCI: byłoby to, jak, n razy n minus 1 lub coś w tym stylu? 1014 00:50:07,810 --> 00:50:10,650 Podobnie jak za każdym razem działa, to jest po prostu, jak, jeden wymiany mniej 1015 00:50:10,650 --> 00:50:10,960 że cokolwiek to było. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI PENG: Tak, tak, jesteś całkowicie prawo. 1017 00:50:12,668 --> 00:50:15,940 I to jest sprawa, w której swoje Odpowiedź była w rzeczywistości bardziej skomplikowane 1018 00:50:15,940 --> 00:50:17,240 niż ten, musimy dać. 1019 00:50:17,240 --> 00:50:19,772 Więc to będzie run-- jestem zamierza usunąć to wszystko tutaj. 1020 00:50:19,772 --> 00:50:20,480 Czy wszyscy są dobre? 1021 00:50:20,480 --> 00:50:21,869 Czy mogę wymazać tego? 1022 00:50:21,869 --> 00:50:22,368 OK. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Będziesz prowadzony przez n Czasy po raz pierwszy, prawda? 1025 00:50:30,320 --> 00:50:33,200 A oni będą przebiegać przez n minus 1 drugi raz, prawda? 1026 00:50:33,200 --> 00:50:37,130 A potem idziesz do utrzymania dzieje, n moje 2, et cetera. 1027 00:50:37,130 --> 00:50:40,210 David zrobił to w wykładzie, gdzie, jeśli zsumować wszystkie te wartości, 1028 00:50:40,210 --> 00:50:48,080 masz coś, co jest like-- yeah-- ponad 2, które w istocie po prostu zmniejsza 1029 00:50:48,080 --> 00:50:49,784 do n do kwadratu. 1030 00:50:49,784 --> 00:50:51,700 Masz zamiar dostać dziwne część tam. 1031 00:50:51,700 --> 00:50:53,892 I tak, po prostu wiem, że n do kwadratu zawsze 1032 00:50:53,892 --> 00:50:55,350 ma pierwszeństwo przed frakcji. 1033 00:50:55,350 --> 00:50:58,450 I tak w tym przypadku, w najgorszym czas pracy byłby n do kwadratu. 1034 00:50:58,450 --> 00:51:00,210 Jeśli to było w porządku malejącym Kolejność, myślę, ci 1035 00:51:00,210 --> 00:51:02,530 trzeba dokonać wymiany za każdym razem. 1036 00:51:02,530 --> 00:51:05,170 >> Co byłoby, potencjalnie, najlepszym przypadku czas pracy? 1037 00:51:05,170 --> 00:51:08,580 Powiedzmy tylko, jeśli lista już było w porządku, co by runtime być? 1038 00:51:08,580 --> 00:51:09,565 >> PUBLICZNOŚCI: brak. 1039 00:51:09,565 --> 00:51:10,690 ANDI PENG: Jest n, dokładnie. 1040 00:51:10,690 --> 00:51:11,600 I dlaczego jest to n? 1041 00:51:11,600 --> 00:51:13,850 PUBLICZNOŚCI: Bo Ciebie tylko trzeba sprawdzić na sobie raz. 1042 00:51:13,850 --> 00:51:14,770 ANDI PENG: Dokładnie. 1043 00:51:14,770 --> 00:51:17,150 Więc w najlepszym możliwym czasie wykonywania, jeśli ta lista już było 1044 00:51:17,150 --> 00:51:20,270 sorted-- powiedzmy, 1, 2, 3, 4-- ci po prostu przejść, należy sprawdzić, 1045 00:51:20,270 --> 00:51:21,720 to zobaczysz, och, wszystkie one ułoży. 1046 00:51:21,720 --> 00:51:22,636 Nie miałem do wymiany. 1047 00:51:22,636 --> 00:51:23,370 Mam dość. 1048 00:51:23,370 --> 00:51:26,500 Więc w tym przypadku, to tylko n lub liczba kroków po prostu 1049 00:51:26,500 --> 00:51:29,870 musiał sprawdzić w pierwszej listy. 1050 00:51:29,870 --> 00:51:33,990 >> I po, teraz hit Sortowanie przez wstawianie, gdzie 1051 00:51:33,990 --> 00:51:39,260 algorytm jest zasadniczo podzielić że na część sortowane i niesortowane. 1052 00:51:39,260 --> 00:51:42,810 A następnie jeden po drugim wartości nieposortowane są 1053 00:51:42,810 --> 00:51:46,880 włożony w ich właściwe pozycje na początku listy. 1054 00:51:46,880 --> 00:51:52,120 >> Tak na przykład, mamy Lista 3, 5, 2, 6, 4 ponownie. 1055 00:51:52,120 --> 00:51:54,750 Wiemy, że jest to obecnie nieposortowane, ponieważ mamy tylko 1056 00:51:54,750 --> 00:51:57,030 zaczął patrząc na niego. 1057 00:51:57,030 --> 00:52:00,610 Przyjrzymy i wiemy, że pierwsza wartość jest posortowana, prawda? 1058 00:52:00,610 --> 00:52:04,190 Jeśli szukasz tylko na tablicy Rozmiar, wiesz, że to jest klasyfikowane. 1059 00:52:04,190 --> 00:52:08,230 >> Tak więc wiemy, że Pozostałe cztery są nieposortowane. 1060 00:52:08,230 --> 00:52:10,980 Idziemy przez i widzimy, że wartość. 1061 00:52:10,980 --> 00:52:11,730 Wracajmy. 1062 00:52:11,730 --> 00:52:13,130 Zobacz, że wartość 5? 1063 00:52:13,130 --> 00:52:14,110 Możemy spojrzeć na niego. 1064 00:52:14,110 --> 00:52:15,204 Porównując go do 3. 1065 00:52:15,204 --> 00:52:17,870 Wiemy, że jest większa niż 3, więc wiemy, że to jest klasyfikowane. 1066 00:52:17,870 --> 00:52:22,940 Więc teraz wiemy, że dwa pierwsze są klasyfikowane, a trzy ostatnie nie są. 1067 00:52:22,940 --> 00:52:24,270 >> Możemy spojrzeć na 2. 1068 00:52:24,270 --> 00:52:25,720 Najpierw sprawdź to z 5. 1069 00:52:25,720 --> 00:52:26,700 Jest to mniej niż 5? 1070 00:52:26,700 --> 00:52:27,240 To nie jest. 1071 00:52:27,240 --> 00:52:29,510 Więc musimy zachować patrząc w dół. 1072 00:52:29,510 --> 00:52:30,940 Następnie należy sprawdzić 2 od 3. 1073 00:52:30,940 --> 00:52:31,850 Czy jest to mniej niż? 1074 00:52:31,850 --> 00:52:32,350 Nie. 1075 00:52:32,350 --> 00:52:35,430 Więc wiesz, 2 musi być włożona do przodu, 3 i 5 1076 00:52:35,430 --> 00:52:38,200 oba muszą być wypchnięty. 1077 00:52:38,200 --> 00:52:42,190 Czy to znowu z 6 i 4. 1078 00:52:42,190 --> 00:52:48,962 A my po prostu zaglądać w istocie, gdzie po prostu sprawdzić, sprawdzić, sprawdzić. 1079 00:52:48,962 --> 00:52:51,170 I dopóki to w prawo pozycja, my niby tylko 1080 00:52:51,170 --> 00:52:54,890 włóż ją do właściwej pozycji, czyli tam, gdzie nazwa pochodzi. 1081 00:52:54,890 --> 00:52:59,830 >> Więc to tylko algorytm, pseudokod per se, rodzaj, 1082 00:52:59,830 --> 00:53:04,990 w jaki sposób będziemy realizować sortowania wstawiania. 1083 00:53:04,990 --> 00:53:05,954 Pseudokod jest tutaj. 1084 00:53:05,954 --> 00:53:06,620 To wszystko jest w Internecie. 1085 00:53:06,620 --> 00:53:10,720 Nie martw się, jeśli jesteście próbuje skopiować ten dół. 1086 00:53:10,720 --> 00:53:14,500 Więc jeszcze raz, sam question-- co byłoby najlepsze i najgorsze czasy pracy 1087 00:53:14,500 --> 00:53:16,120 do wstawiania rodzaju? 1088 00:53:16,120 --> 00:53:17,750 To jest bardzo podobna do tej ostatniej kwestii. 1089 00:53:17,750 --> 00:53:20,479 Dam wam, jak, 30 sekundy, aby myśleć o tym, jak dobrze. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Czy ktoś chce daj mi najgorszy czas pracy? 1092 00:53:50,071 --> 00:53:50,570 Tak. 1093 00:53:50,570 --> 00:53:51,490 >> PUBLICZNOŚCI: n do kwadratu. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI PENG: Jest n do kwadratu. 1095 00:53:52,573 --> 00:53:53,730 I dlaczego jest to n do kwadratu? 1096 00:53:53,730 --> 00:53:57,562 >> PUBLICZNOŚCI: Ponieważ w odwrotnej kolejności, trzeba 1097 00:53:57,562 --> 00:54:02,619 przejść przez n razy n, które jest-- 1098 00:54:02,619 --> 00:54:03,660 ANDI PENG: Tak, dokładnie. 1099 00:54:03,660 --> 00:54:06,610 Tak samo jak w bubble rodzaju. 1100 00:54:06,610 --> 00:54:08,720 Jeśli ta lista jest w kolejności malejącej, jesteś 1101 00:54:08,720 --> 00:54:11,240 będzie musiał sprawdzić pierwszy raz. 1102 00:54:11,240 --> 00:54:13,470 A potem z każdym Dodatkowym atutem, jesteś 1103 00:54:13,470 --> 00:54:16,390 będzie musiał sprawdzić je przed każda wartość, prawda? 1104 00:54:16,390 --> 00:54:20,290 A tak w ogóle, masz zamiar zrobić an razy n karnetów kolejny n przejść, które 1105 00:54:20,290 --> 00:54:21,750 n jest kwadratowy. 1106 00:54:21,750 --> 00:54:22,860 Co najlepszym przypadku? 1107 00:54:22,860 --> 00:54:24,360 Tak. 1108 00:54:24,360 --> 00:54:28,840 >> PUBLICZNOŚCI: n minus 1, ponieważ Pierwszy z nich jest już do kwadratu. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI PENG: Tak, blisko. 1110 00:54:30,270 --> 00:54:31,850 Odpowiedź jest n. 1111 00:54:31,850 --> 00:54:37,189 Ponieważ, podczas gdy pierwszy z nich jest sortowane, że nie może to actually-- 1112 00:54:37,189 --> 00:54:38,980 po prostu pecha, w że przykładem, że 2 1113 00:54:38,980 --> 00:54:40,930 stało się najmniejsza liczba. 1114 00:54:40,930 --> 00:54:43,680 Ale nie zawsze tak było. 1115 00:54:43,680 --> 00:54:48,040 Jeśli 2 jest już posortowana na początku ale wyglądasz i tam 1 tutaj, 1116 00:54:48,040 --> 00:54:49,144 W 1 ma zamiar go uderzyć. 1117 00:54:49,144 --> 00:54:51,060 I to się skończy się być wpadł jakikolwiek. 1118 00:54:51,060 --> 00:54:56,250 >> Tak więc, w najlepszym przypadku, to faktycznie tylko będzie n. 1119 00:54:56,250 --> 00:54:59,090 Jeśli masz 1, 2, 3, 4, 5, 6, 7, 8, jesteś 1120 00:54:59,090 --> 00:55:00,940 będzie przebiegać przez że cała lista raz 1121 00:55:00,940 --> 00:55:03,430 aby sprawdzić, czy wszystko jest w porządku. 1122 00:55:03,430 --> 00:55:07,390 Czy wszyscy są jasne, na prowadzeniu Czasy selekcji, jak również? 1123 00:55:07,390 --> 00:55:09,960 Wiem, że przeżywa to naprawdę szybko. 1124 00:55:09,960 --> 00:55:13,330 Ale po prostu wiem, że jeśli wiesz, że ogólne koncepcje, powinno być dobrze. 1125 00:55:13,330 --> 00:55:16,070 OK. 1126 00:55:16,070 --> 00:55:19,790 Więc ja po prostu dać wam może, jak, minutę, aby porozmawiać z sąsiadami 1127 00:55:19,790 --> 00:55:21,890 co to tylko niektóre z głównych różnic 1128 00:55:21,890 --> 00:55:23,540 pomiędzy tymi typami rodzaju. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Pójdziemy nad tym wkrótce. 1131 00:56:25,570 --> 00:56:26,444 PUBLICZNOŚCI: Och, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI PENG: Tak. 1133 00:56:27,320 --> 00:56:28,380 OK. 1134 00:56:28,380 --> 00:56:33,420 Cool, niech się ponownie zebrać w klasie. 1135 00:56:33,420 --> 00:56:34,330 OK. 1136 00:56:34,330 --> 00:56:37,579 Więc to był swego rodzaju pytanie otwarte, w tym sensie, 1137 00:56:37,579 --> 00:56:39,120 że jest wiele odpowiedzi na nie. 1138 00:56:39,120 --> 00:56:40,746 I pójdziemy na niektóre z nich krótko. 1139 00:56:40,746 --> 00:56:43,411 Chciałem się was myśląc o tym, co zróżnicowane 1140 00:56:43,411 --> 00:56:44,530 wszystkie trzy typy rodzaju. 1141 00:56:44,530 --> 00:56:47,440 I usłyszałem, także wielki question-- co to sortowanie przez scalanie zrobić? 1142 00:56:47,440 --> 00:56:50,110 Dobre pytanie, bo to co mamy obejmujące obok. 1143 00:56:50,110 --> 00:56:52,850 >> Więc sortowanie przez scalanie jest jeden rodzaj, który działa 1144 00:56:52,850 --> 00:56:56,100 bardzo odmienny od innych rodzajów. 1145 00:56:56,100 --> 00:56:58,180 Jak wy może see-- Dawid zrobić tego demo 1146 00:56:58,180 --> 00:57:01,130 gdzie miał wszystkie fajne odgłosy widząc, jak połączyć 1147 00:57:01,130 --> 00:57:04,010 jakby biegł, jak nieskończenie szybciej niż dwa inne rodzaje? 1148 00:57:04,010 --> 00:57:04,510 OK. 1149 00:57:04,510 --> 00:57:07,580 Więc to dlatego scalanie Sortuj realizuje tę przepaść 1150 00:57:07,580 --> 00:57:11,020 i podbić pojęcia, że ​​mamy rozmawialiśmy o wielu w wykładzie. 1151 00:57:11,020 --> 00:57:14,550 W tym sensie, że chcemy pracować mądrzej, a nie ciężej, po podzieleniu 1152 00:57:14,550 --> 00:57:18,120 i podbić problemy i je łamać w dół, a następnie umieścić je razem, 1153 00:57:18,120 --> 00:57:19,930 dobre rzeczy zawsze się zdarzają. 1154 00:57:19,930 --> 00:57:21,960 >> Więc drogi, które łączą Sortuj zasadniczo działa 1155 00:57:21,960 --> 00:57:24,660 jest to, że dzieli nieposortowane tablica na pół. 1156 00:57:24,660 --> 00:57:26,500 I to ma dwie połówki tablic. 1157 00:57:26,500 --> 00:57:28,220 I to właśnie sortuje te dwie połówki. 1158 00:57:28,220 --> 00:57:31,750 To po prostu utrzymuje dzieląc na pół, w pół, na pół, dopóki wszystko nie jest posortowana 1159 00:57:31,750 --> 00:57:33,680 a następnie rekurencyjnie stawia to wszystko razem. 1160 00:57:33,680 --> 00:57:36,550 >> Więc to jest bardzo abstrakcyjne. 1161 00:57:36,550 --> 00:57:38,750 Więc to jest tylko trochę Pseudokod. 1162 00:57:38,750 --> 00:57:41,040 Czy to ma sens w sposób to działa? 1163 00:57:41,040 --> 00:57:43,870 Więc powiedzmy użytkownik posiada Tablica n elementów, prawda? 1164 00:57:43,870 --> 00:57:45,450 Jeśli n jest mniejsze niż 2, można wrócić. 1165 00:57:45,450 --> 00:57:49,040 Bo wiesz, że jeśli nie ma tylko jedna rzecz, to musi być sortowane. 1166 00:57:49,040 --> 00:57:52,600 Indziej, sortowania lewą połowę, a następnie posortować prawą połowę, 1167 00:57:52,600 --> 00:57:54,140 a następnie scalić. 1168 00:57:54,140 --> 00:57:56,979 >> Tak więc, że wygląda naprawdę łatwe, w rzeczywistości, o tym myśleć to 1169 00:57:56,979 --> 00:58:00,270 rodzaj trudne. Ponieważ jesteś podobny, Dobrze, że to rodzaj działa na siebie. 1170 00:58:00,270 --> 00:58:00,769 Dobrze? 1171 00:58:00,769 --> 00:58:02,430 To działa na siebie. 1172 00:58:02,430 --> 00:58:05,479 Więc w tym sensie, David dotknął na rekursji w klasie. 1173 00:58:05,479 --> 00:58:07,270 I to jest koncepcja porozmawiamy o więcej. 1174 00:58:07,270 --> 00:58:11,430 To, że w tym, te dwie linie tutaj, w rzeczywistości jest tylko program 1175 00:58:11,430 --> 00:58:13,860 informując go uruchomić się z innym wejściem. 1176 00:58:13,860 --> 00:58:17,230 Tak więc, zamiast uruchomić się z całość n elementów, 1177 00:58:17,230 --> 00:58:20,530 można złamać go w dół do Lewa połowa i prawa połowa 1178 00:58:20,530 --> 00:58:22,680 a następnie uruchom go ponownie. 1179 00:58:22,680 --> 00:58:26,050 >> A potem będziemy patrzeć na to wizualnie, bo jestem wzrokowcem. 1180 00:58:26,050 --> 00:58:27,270 To działa lepiej dla mnie. 1181 00:58:27,270 --> 00:58:29,890 Więc zobaczymy wizualny przykład tutaj. 1182 00:58:29,890 --> 00:58:36,237 >> Powiedzmy, że mamy tablicę, sześć Elementy, 3, 5, 2, 6, 4, 1, bez sortowania. 1183 00:58:36,237 --> 00:58:37,820 W porządku, jest wiele na tej stronie. 1184 00:58:37,820 --> 00:58:43,179 Więc jeśli faceci mogą spojrzeć na Pierwszy etap tutaj, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 można podzielić ją na pół. 1186 00:58:44,220 --> 00:58:45,976 Masz 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Wiesz, że to aren't-- was nie wiem, czy są one klasyfikowane czy nie, 1188 00:58:48,850 --> 00:58:52,517 tak trzymać rozbijając ich w połowie, na pół, w połowie, aż ostatecznie 1189 00:58:52,517 --> 00:58:53,600 masz tylko jeden element. 1190 00:58:53,600 --> 00:58:56,790 A jednym z elementów jest zawsze posortowana, prawda? 1191 00:58:56,790 --> 00:59:01,560 >> Wiemy, że 3, 5, 2, 4, 6, 1, przez siebie, są klasyfikowane. 1192 00:59:01,560 --> 00:59:05,870 A teraz możemy umieścić je z powrotem. 1193 00:59:05,870 --> 00:59:07,510 Więc wiemy, 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Stawiamy te razem. 1195 00:59:08,510 --> 00:59:09,617 Wiemy, że jest sortowane. 1196 00:59:09,617 --> 00:59:10,450 W 2 nadal tam jest. 1197 00:59:10,450 --> 00:59:11,830 Możemy umieścić na 4 i 6 razem. 1198 00:59:11,830 --> 00:59:13,996 Wiemy, że to jest klasyfikowane, więc umieścić, że razem. 1199 00:59:13,996 --> 00:59:14,940 A 1 ma. 1200 00:59:14,940 --> 00:59:18,720 >> A potem po prostu spojrzeć na te dwie połówki tutaj. 1201 00:59:18,720 --> 00:59:21,300 Masz 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Możesz po prostu porównują początek wszystkiego. 1203 00:59:23,465 --> 00:59:26,340 Bo wiesz, że to jest posortowana i wiesz, że to jest klasyfikowane. 1204 00:59:26,340 --> 00:59:29,360 Tak więc nawet nie trzeba porównanie 5, wystarczy porównać 3. 1205 00:59:29,360 --> 00:59:32,070 I 2 jest mniejsza niż 3, tak, wiesz 2 musi iść w końcu. 1206 00:59:32,070 --> 00:59:33,120 >> Samo tam. 1207 00:59:33,120 --> 00:59:34,740 W 1 musi udać się tutaj. 1208 00:59:34,740 --> 00:59:37,330 A potem, gdy idziesz do wprowadzenia razem te dwie wartości, 1209 00:59:37,330 --> 00:59:39,950 wiesz, że to jest sortowane i wiesz, że to jest klasyfikowane. 1210 00:59:39,950 --> 00:59:43,240 Więc to 1 a 2, 1 jest mniejsza niż 2. 1211 00:59:43,240 --> 00:59:45,570 Który mówi, że 1 powinien udać się na koniec tego 1212 00:59:45,570 --> 00:59:47,480 nawet nie patrząc na 3 lub 5. 1213 00:59:47,480 --> 00:59:50,100 A następnie na 4, można po prostu sprawdzić, to idzie się w tutaj. 1214 00:59:50,100 --> 00:59:51,480 Nie musisz patrzeć na 5. 1215 00:59:51,480 --> 00:59:52,570 Samo z 6. 1216 00:59:52,570 --> 00:59:55,860 Wiesz, że 6-- to tylko nie musi być postrzegana. 1217 00:59:55,860 --> 00:59:57,870 >> I tak, w ten sposób, że jesteś tylko oszczędność siebie 1218 00:59:57,870 --> 00:59:59,526 wiele kroków, gdy porównujemy. 1219 00:59:59,526 --> 01:00:02,150 Nie musisz porównać każdego Element w stosunku do innych elementów. 1220 01:00:02,150 --> 01:00:05,230 Wystarczy porównać z tymi że trzeba porównać je przed. 1221 01:00:05,230 --> 01:00:06,870 Więc to rodzaj abstrakcyjnego pojęcia. 1222 01:00:06,870 --> 01:00:10,540 Nie martw się, jeśli nie jest dość uderzając cię jeszcze rację. 1223 01:00:10,540 --> 01:00:14,740 Ale zwykle jest to jak sortowanie przez scalanie działa. 1224 01:00:14,740 --> 01:00:17,750 Pytania, szybkie pytania, zanim przejdę? 1225 01:00:17,750 --> 01:00:18,550 Tak. 1226 01:00:18,550 --> 01:00:22,230 >> PUBLICZNOŚCI: Tak powiedział Pan, że bierzesz W 1, a następnie 4 i 6 1227 01:00:22,230 --> 01:00:23,860 i umieścić je w. 1228 01:00:23,860 --> 01:00:26,800 Więc nie są those-- nie są Patrzysz na nich 1229 01:00:26,800 --> 01:00:28,544 jako oddzielne elementy, a nie jako całości? 1230 01:00:28,544 --> 01:00:29,210 ANDI PENG: Tak. 1231 01:00:29,210 --> 01:00:32,020 Więc co się dzieje jest to, że w zasadzie 1232 01:00:32,020 --> 01:00:33,650 Tworzymy nową tablicę. 1233 01:00:33,650 --> 01:00:36,690 Więc wiesz, że tutaj mam dwie tablice wielkości 3, prawda? 1234 01:00:36,690 --> 01:00:39,600 Więc wiesz, że moja posortowanej tablicy musi mieć sześć elementów. 1235 01:00:39,600 --> 01:00:42,270 Więc po prostu stworzyć Nowa ilość pamięci. 1236 01:00:42,270 --> 01:00:44,270 Więc jesteś trochę jak jest marnotrawstwem pamięci, 1237 01:00:44,270 --> 01:00:46,186 ale to nie ma znaczenia dlatego, że jest tak mały. 1238 01:00:46,186 --> 01:00:48,590 Więc spójrz na 1 i spojrzeć na 2. 1239 01:00:48,590 --> 01:00:50,770 I wiesz, że 1 jest mniejszy niż 2. 1240 01:00:50,770 --> 01:00:53,840 Więc wiesz, że jeden powinien iść w początek wszystkie z nich. 1241 01:00:53,840 --> 01:00:55,850 >> Nie trzeba nawet patrzeć w pozycji 3 i 5. 1242 01:00:55,850 --> 01:00:57,400 Więc wiesz, jeden idzie. 1243 01:00:57,400 --> 01:00:59,300 Potem w zasadzie odciąć 1. 1244 01:00:59,300 --> 01:01:00,370 To, jak, żyje nam. 1245 01:01:00,370 --> 01:01:03,690 Następnie musimy tylko 2, 3, 5 i 4 i 6. 1246 01:01:03,690 --> 01:01:06,270 I wtedy wiesz, że Cię porównaj 4 i 2, 1247 01:01:06,270 --> 01:01:07,560 Och, 2 powinien tam wejść. 1248 01:01:07,560 --> 01:01:09,685 Więc rzuć na 2 w dół, odcinamy. 1249 01:01:09,685 --> 01:01:12,060 Więc po prostu mają 3 i 5 w 4 i 6. 1250 01:01:12,060 --> 01:01:14,650 I po prostu zachować siekanie go aż umieścić je w tablicy. 1251 01:01:14,650 --> 01:01:17,110 >> PUBLICZNOŚCI: Więc jesteś po prostu zawsze porównanie [niesłyszalne]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI PENG: Dokładnie. 1253 01:01:17,710 --> 01:01:19,590 Więc w tym sensie, że jesteś tylko porównanie, zasadniczo, 1254 01:01:19,590 --> 01:01:21,240 numer jeden przed drugim numerem. 1255 01:01:21,240 --> 01:01:22,990 A bo wiesz, że to jest klasyfikowane, ciebie 1256 01:01:22,990 --> 01:01:24,350 nie trzeba patrzeć przez wszystkich numerów. 1257 01:01:24,350 --> 01:01:25,870 Trzeba tylko spojrzeć na pierwszego. 1258 01:01:25,870 --> 01:01:27,582 A potem po prostu rzuć im się, bo wiesz, 1259 01:01:27,582 --> 01:01:29,640 należą gdzie trzeba należeć. 1260 01:01:29,640 --> 01:01:31,030 Tak. 1261 01:01:31,030 --> 01:01:32,920 Dobre pytanie. 1262 01:01:32,920 --> 01:01:35,290 >> A jeśli ktoś z was są nieco ambitny, 1263 01:01:35,290 --> 01:01:38,660 Zapraszam do zapoznania się z tym kodem. 1264 01:01:38,660 --> 01:01:40,680 To jest rzeczywiście Realizacja fizyczna 1265 01:01:40,680 --> 01:01:42,150 od tego, jak będziemy pisać sortowanie przez scalanie. 1266 01:01:42,150 --> 01:01:44,070 I widać, że to bardzo krótka. 1267 01:01:44,070 --> 01:01:46,310 Ale Idee że są dość skomplikowane. 1268 01:01:46,310 --> 01:01:50,865 Więc jeśli czujesz się jak rysunek na to uwagę w swojej pracy domowej dziś wieczorem, nie krępuj się. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> OK. 1271 01:01:54,740 --> 01:01:58,070 Dawid udał się nad tym w wykładzie. 1272 01:01:58,070 --> 01:02:00,660 Jakie są najlepsze case czasy pracy, czasy pracy najgorszego przypadku, 1273 01:02:00,660 --> 01:02:05,680 i oczekiwane czasy pracy sortowanie przez scalanie? 1274 01:02:05,680 --> 01:02:07,260 Kilka sekund myśleć. 1275 01:02:07,260 --> 01:02:11,198 Jest to dość trudne, ale rodzaj intuicyjne, jeśli myślisz o tym. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 W porządku. 1278 01:02:23,054 --> 01:02:25,269 >> PUBLICZNOŚCI: Czy najgorszy przypadek n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI PENG: Dokładnie. 1280 01:02:26,060 --> 01:02:29,380 I dlaczego jest n log n. 1281 01:02:29,380 --> 01:02:32,230 >> PUBLICZNOŚCI: Czy to nie dlatego, że staje się wykładniczo szybciej, 1282 01:02:32,230 --> 01:02:35,390 tak to jest jak funkcja, która zamiast po prostu będąc n 1283 01:02:35,390 --> 01:02:37,529 kwadratu, czy coś? 1284 01:02:37,529 --> 01:02:38,320 ANDI PENG: Dokładnie. 1285 01:02:38,320 --> 01:02:40,750 Zatem powodem Czas pracy na to n log 1286 01:02:40,750 --> 01:02:44,310 n jest because-- co ty robi w każdym z tych etapów? 1287 01:02:44,310 --> 01:02:46,190 Jesteś po prostu siekanie go na pół, tak? 1288 01:02:46,190 --> 01:02:48,750 I tak, gdy jesteśmy robi log, wszystko, co robi 1289 01:02:48,750 --> 01:02:53,150 dzieli problem w połowie na pół, w połowie, w większej części. 1290 01:02:53,150 --> 01:02:56,430 I w tym sensie, można rodzaju lub wyeliminowanie model liniowy 1291 01:02:56,430 --> 01:02:57,510 które używaliśmy. 1292 01:02:57,510 --> 01:03:00,254 Bo kiedy chop rzeczy w połowie, to jest dziennik. 1293 01:03:00,254 --> 01:03:02,420 To tylko matematyczne sposobem reprezentowania go. 1294 01:03:02,420 --> 01:03:06,310 >> I w końcu, w końcu, jesteś tylko co raz ostatni przechodzą przez 1295 01:03:06,310 --> 01:03:07,930 umieścić je wszystkie w porządku, prawda? 1296 01:03:07,930 --> 01:03:10,330 I tak, jeśli po prostu trzeba sprawdzić jedną rzecz, to n. 1297 01:03:10,330 --> 01:03:13,420 A więc jesteś rodzaju mnożąc dwa razem. 1298 01:03:13,420 --> 01:03:17,660 Tak to jest jak masz, że ostateczna sprawdzić n tu z dziennika n 1299 01:03:17,660 --> 01:03:18,390 tu na górze. 1300 01:03:18,390 --> 01:03:21,060 A jeśli pomnożyć im, że to n log n. 1301 01:03:21,060 --> 01:03:26,100 >> A więc najlepszym przypadku i najgorsze Sprawa i oczekiwane są n log n. 1302 01:03:26,100 --> 01:03:27,943 Jest to także jak w innym rodzaju. 1303 01:03:27,943 --> 01:03:30,090 To jak wybór rodzaju w tym sensie, że 1304 01:03:30,090 --> 01:03:32,131 nie ma znaczenia, co się Lista jest, to po prostu się 1305 01:03:32,131 --> 01:03:34,801 aby zrobić to samo za każdym razem. 1306 01:03:34,801 --> 01:03:35,300 OK. 1307 01:03:35,300 --> 01:03:39,950 Tak jak chłopaki widzą, choć sortuje, że zaszliśmy through-- n 1308 01:03:39,950 --> 01:03:41,660 kwadratu, to nie jest bardzo wydajny. 1309 01:03:41,660 --> 01:03:47,060 I nawet to n log n nie najbardziej skuteczny. 1310 01:03:47,060 --> 01:03:49,720 Jeśli jesteście ciekawi, tam mechanizmy sortowania 1311 01:03:49,720 --> 01:03:54,310 które są tak skuteczne, że są one prawie zasadniczo płaska w czasie pracy. 1312 01:03:54,310 --> 01:03:55,420 >> Masz jakiś log n-tych. 1313 01:03:55,420 --> 01:03:58,190 Masz jakiś log log n-tych. 1314 01:03:58,190 --> 01:04:00,330 Nie dotykamy nimi w tej klasie teraz. 1315 01:04:00,330 --> 01:04:02,663 Ale jeśli jesteście ciekawi, zapraszam do google, co jest 1316 01:04:02,663 --> 01:04:04,392 najbardziej efektywne mechanizmy sortowania. 1317 01:04:04,392 --> 01:04:06,350 Nie wiem, nie są kilka naprawdę zabawnych te, 1318 01:04:06,350 --> 01:04:09,860 like-- tam kilka naprawdę śmieszne te, które ludzie robią. 1319 01:04:09,860 --> 01:04:12,210 I zastanawiasz się, w jaki sposób Myślałeś kiedyś o tym. 1320 01:04:12,210 --> 01:04:15,730 Więc google, jeśli masz trochę wolnego Czas, na jakie są jakieś zabawne sposoby 1321 01:04:15,730 --> 01:04:17,730 że people-- jak również wydajne ways-- ludzi 1322 01:04:17,730 --> 01:04:20,371 była w stanie realizować rodzaju. 1323 01:04:20,371 --> 01:04:20,870 OK. 1324 01:04:20,870 --> 01:04:22,880 A tutaj jest po prostu mało poręczne wykres. 1325 01:04:22,880 --> 01:04:26,850 Wiem, że wszyscy z was, przed tym quizie 0, będzie w pokoju, prawdopodobnie próbując 1326 01:04:26,850 --> 01:04:27,960 zapamiętać, że. 1327 01:04:27,960 --> 01:04:30,940 Tak, że miło się tam dla was. 1328 01:04:30,940 --> 01:04:37,120 Tylko nie zapomnij, logikę, że made-- dlaczego te liczby miały miejsce. 1329 01:04:37,120 --> 01:04:39,870 Jeśli zawsze stracone, tylko zrobić pewien, że wiesz, co rodzaju są. 1330 01:04:39,870 --> 01:04:40,820 I można uruchomić poprzez im w głowie 1331 01:04:40,820 --> 01:04:42,903 dowiedzieć się, dlaczego ci, Odpowiedzi są te odpowiedzi. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> W porządku. 1334 01:04:47,600 --> 01:04:49,680 Tak więc mamy zamiar przenieść na końcu, w celu wyszukiwania. 1335 01:04:49,680 --> 01:04:51,638 Bo jak ci z was, którzy czytali pset, 1336 01:04:51,638 --> 01:04:55,175 Wyszukiwanie jest również częścią Problem w tym tygodniu zestawy. 1337 01:04:55,175 --> 01:04:57,300 Zostaniesz poproszony do wdrożenia dwa rodzaje wyszukiwań. 1338 01:04:57,300 --> 01:05:00,070 Jednym z nich jest przeszukiwanie liniowe i jeden jest przeszukiwanie binarne. 1339 01:05:00,070 --> 01:05:01,760 >> Więc przeszukiwanie liniowe jest dość łatwe. 1340 01:05:01,760 --> 01:05:04,070 Po prostu chcesz, aby szukać elementu z listy, aby zobaczyć, czy się uda. 1341 01:05:04,070 --> 01:05:05,444 Musisz tylko iterację. 1342 01:05:05,444 --> 01:05:08,170 A jeśli jest równa coś, możesz po prostu odesłać go, prawda? 1343 01:05:08,170 --> 01:05:10,890 Ale ten, że jesteśmy najbardziej zainteresowany rozmową na temat 1344 01:05:10,890 --> 01:05:14,550 jest przeszukiwanie binarne, prawo, które jest Dziel i rządź mechanizm 1345 01:05:14,550 --> 01:05:18,190 Dawid wykazując w wykładzie. 1346 01:05:18,190 --> 01:05:20,810 >> Pamiętaj przykład książki telefonicznej że wciąż wychowuje, 1347 01:05:20,810 --> 01:05:23,960 ten, że rodzaj zmagał nieco na ten ostatni rok, 1348 01:05:23,960 --> 01:05:27,530 gdzie można podzielić problem na pół, na pół, na pół, znowu i znowu, 1349 01:05:27,530 --> 01:05:30,730 aż znajdziesz to, czego szukasz? 1350 01:05:30,730 --> 01:05:33,727 I masz runtime, że dobrze. 1351 01:05:33,727 --> 01:05:35,810 I widać, że to znacznie bardziej wydajne 1352 01:05:35,810 --> 01:05:39,080 niż jakikolwiek inny rodzaj wyszukiwania. 1353 01:05:39,080 --> 01:05:41,880 >> Więc sposób, że pójdziemy na temat wdrożenie przeszukiwanie binarne 1354 01:05:41,880 --> 01:05:46,510 to, gdybyśmy mieli tablicę, Strona 0 do 6, siedem elementów, 1355 01:05:46,510 --> 01:05:49,790 możemy spojrzeć w środku, prawy-- Przepraszam, jeśli nasze pytanie first-- 1356 01:05:49,790 --> 01:05:53,840 jeśli chcemy zadać pytanie, czy tablica zawiera element 7, 1357 01:05:53,840 --> 01:05:56,840 Oczywiście, jest ludzi, posiadające taka mała tablica, jest to dla nas łatwe 1358 01:05:56,840 --> 01:05:58,210 powiedzieć tak. 1359 01:05:58,210 --> 01:06:05,750 Ale sposób, aby wdrożyć binarny wyszukiwarka będzie wyglądać w środku. 1360 01:06:05,750 --> 01:06:08,020 >> Wiemy, że indeks 3 jest w środku, bo 1361 01:06:08,020 --> 01:06:09,270 wiem, jest siedem elementów. 1362 01:06:09,270 --> 01:06:10,670 Co 7 podzielona przez 2? 1363 01:06:10,670 --> 01:06:12,850 Możesz odciąć, że dodatkową 1. 1364 01:06:12,850 --> 01:06:14,850 Masz 3 w środku. 1365 01:06:14,850 --> 01:06:17,590 Więc jest tablica z 3 równe 7? 1366 01:06:17,590 --> 01:06:18,900 To nie jest, prawda? 1367 01:06:18,900 --> 01:06:21,050 Ale możemy zrobić kilka kontroli. 1368 01:06:21,050 --> 01:06:25,380 Czy tablica 3 mniej niż 7 lub jest tablica z 3 większa niż 7? 1369 01:06:25,380 --> 01:06:27,240 >> I wiemy, że jest to mniej niż 7. 1370 01:06:27,240 --> 01:06:30,259 Więc wiemy, że och, to musi nie być w lewej połówce. 1371 01:06:30,259 --> 01:06:32,300 Wiemy, że musi być w prawej połowie, prawda? 1372 01:06:32,300 --> 01:06:34,662 Więc może po prostu odciąć połowę tablicy. 1373 01:06:34,662 --> 01:06:36,370 Nie trzeba nawet spojrzeć na to już. 1374 01:06:36,370 --> 01:06:38,711 Ponieważ wiemy, że połowa naszej problem-- 1375 01:06:38,711 --> 01:06:41,210 wiemy, że odpowiedź jest w prawo połowa naszego problemu. 1376 01:06:41,210 --> 01:06:42,580 Więc po prostu patrzeć na to teraz. 1377 01:06:42,580 --> 01:06:44,860 >> Teraz przyjrzymy się Środek to, co pozostało. 1378 01:06:44,860 --> 01:06:46,880 Że wskaźnik 5. 1379 01:06:46,880 --> 01:06:50,200 Znów zrobić to samo sprawdzanie i widzimy, że jest mniejszy. 1380 01:06:50,200 --> 01:06:52,050 Więc patrzymy na lewo od tego. 1381 01:06:52,050 --> 01:06:53,430 A potem widzimy, że czek. 1382 01:06:53,430 --> 01:06:57,600 Czy wartość tablicy w Strona 4 równe 7? 1383 01:06:57,600 --> 01:06:58,260 To jest. 1384 01:06:58,260 --> 01:07:03,580 Tak więc możemy wrócić prawda, bo okazało się, że wartość naszej liście. 1385 01:07:03,580 --> 01:07:06,738 Czy drogę przeszedłem to ma sens dla każdego? 1386 01:07:06,738 --> 01:07:08,760 OK. 1387 01:07:08,760 --> 01:07:11,670 Dam wam może, jak, trzy, cztery minuty, aby dowiedzieć się, 1388 01:07:11,670 --> 01:07:13,270 jak pseudocode o tym. 1389 01:07:13,270 --> 01:07:18,070 >> Więc wyobraź sobie, poprosiłem, aby napisać Funkcja o nazwie wyszukiwania (), który powrócił 1390 01:07:18,070 --> 01:07:20,640 wartość, wartość logiczna, to było prawdziwe, czy false-- jak, 1391 01:07:20,640 --> 01:07:22,970 prawda, jeśli okazało się, że wartość false jeśli nie. 1392 01:07:22,970 --> 01:07:25,230 A potem były przeszedł w wartości można 1393 01:07:25,230 --> 01:07:28,410 szukaliśmy na wartości, które jest array-- och, zdecydowanie umieścić 1394 01:07:28,410 --> 01:07:29,410 że w niewłaściwym miejscu. 1395 01:07:29,410 --> 01:07:29,580 OK. 1396 01:07:29,580 --> 01:07:31,829 W każdym razie, że powinien mieć było na prawo od wartości. 1397 01:07:31,829 --> 01:07:36,280 A następnie int n jest liczbą elementów w tej tablicy. 1398 01:07:36,280 --> 01:07:39,430 Jak byś go o próby do pseudocode ten problem? 1399 01:07:39,430 --> 01:07:41,630 Dam wam jak trzy minuty, aby to zrobić. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Nie, myślę, że jest only-- Tak, jest jedna aż tutaj. 1402 01:08:02,595 --> 01:08:03,261 PUBLICZNOŚCI: Czy mogę? 1403 01:08:03,261 --> 01:08:04,388 ANDI PENG: Tak, mam ciebie. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Czy to działa? 1406 01:08:11,050 --> 01:08:12,290 Ok fajnie. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> OK. 1409 01:10:44,720 --> 01:10:47,630 W porządku chłopaki, jesteśmy zamiar powstrzymania go. 1410 01:10:47,630 --> 01:10:49,730 OK. 1411 01:10:49,730 --> 01:10:54,020 Więc zakładamy, że mamy ten piękny mała tablica z n wartości w nim. 1412 01:10:54,020 --> 01:10:55,170 Nie rysować linie. 1413 01:10:55,170 --> 01:10:58,649 Ale jak pójdziemy na temat próbuje pisać to? 1414 01:10:58,649 --> 01:11:00,440 Czy ktoś chce dał mi pierwszą linię? 1415 01:11:00,440 --> 01:11:02,814 Jeśli chcesz dać mi Pierwsza linia tego Pseudokod. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> PUBLICZNOŚCI: [niesłyszalne] 1418 01:11:08,430 --> 01:11:10,138 PUBLICZNOŚCI: czego chcesz iteracyjne through-- 1419 01:11:10,138 --> 01:11:11,094 PUBLICZNOŚCI: Jeszcze jeden dla pętli? 1420 01:11:11,094 --> 01:11:11,760 PUBLICZNOŚCI: --for. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI PENG: Więc ta jest nieco kłopotliwe. 1423 01:11:17,780 --> 01:11:23,130 Pomyśl about-- chcesz biec tej pętli 1424 01:11:23,130 --> 01:11:27,950 kółko do momentu, kiedy? 1425 01:11:27,950 --> 01:11:30,819 >> PUBLICZNOŚCI: Do [niesłyszalne] wartość jest równa tej wartości. 1426 01:11:30,819 --> 01:11:31,610 ANDI PENG: Dokładnie. 1427 01:11:31,610 --> 01:11:33,900 Więc może faktycznie po prostu write-- możemy nawet uprościć go więcej. 1428 01:11:33,900 --> 01:11:35,630 Możemy po prostu zrobić pętli while, prawda? 1429 01:11:35,630 --> 01:11:39,380 Więc może po prostu trzeba loop-- Wiemy, że jest to jednocześnie. 1430 01:11:39,380 --> 01:11:42,850 Ale na razie, zamierzam powiedzieć "pętlę" - przez co? 1431 01:11:42,850 --> 01:11:46,640 Pętla until-- to, co jest nasz kończąc warunek? 1432 01:11:46,640 --> 01:11:47,510 Myślę, że to usłyszałem. 1433 01:11:47,510 --> 01:11:48,530 Słyszałem, jak ktoś powiedzieć. 1434 01:11:48,530 --> 01:11:51,255 >> WIDOWNI: Wartości równe pola. 1435 01:11:51,255 --> 01:11:52,255 ANDI PENG: Powiedz to jeszcze raz. 1436 01:11:52,255 --> 01:11:54,470 PUBLICZNOŚCI: Albo, aż Wartość szukacie 1437 01:11:54,470 --> 01:11:58,470 , jest równa średniej wartości. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI PENG: Co zrobić, jeśli nie jest w środku? 1439 01:12:00,280 --> 01:12:03,113 Co zrobić, jeśli wartość szukacie , nie jest ona w tej tablicy? 1440 01:12:03,113 --> 01:12:05,890 PUBLICZNOŚCI: powrót 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI PENG: Ale to, co chcemy Pętla do czasu, gdy mamy stan? 1442 01:12:08,850 --> 01:12:09,350 Tak. 1443 01:12:09,350 --> 01:12:11,239 >> PUBLICZNOŚCI: Dopóki istnieje tylko jedna wartość? 1444 01:12:11,239 --> 01:12:13,530 ANDI PENG: Można pętli until-- więc wiesz, że jesteś 1445 01:12:13,530 --> 01:12:15,714 będzie mieć wartość maksymalną, prawda? 1446 01:12:15,714 --> 01:12:18,130 A wiesz, że masz zamiar mieć wartość min, prawda? 1447 01:12:18,130 --> 01:12:20,379 Bo też, że coś Zapomniałem powiedzieć wcześniej, 1448 01:12:20,379 --> 01:12:22,640 że coś, co jest krytycznie wyszukiwania binarnego 1449 01:12:22,640 --> 01:12:24,182 jest to, że tablica jest już posortowana. 1450 01:12:24,182 --> 01:12:26,973 Ponieważ nie ma sposobu prowadzenia tego, czy są wartości tylko losowe. 1451 01:12:26,973 --> 01:12:29,190 Nie wiesz, jeśli jest większe niż inne, prawda? 1452 01:12:29,190 --> 01:12:32,720 >> Więc wiesz, że max i Twoje minut tu, prawda? 1453 01:12:32,720 --> 01:12:35,590 Jeśli masz zamiar być dostosowanie Twój max w swoim minut i mid-- 1454 01:12:35,590 --> 01:12:38,470 niech po prostu zakładamy, że wartość średniej jest tuż here-- 1455 01:12:38,470 --> 01:12:43,910 będziesz w zasadzie pętli, aż minimalna jest 1456 01:12:43,910 --> 01:12:47,510 o tym samym jako max, w prawo lub jeśli max nie jest taka sama, jak min. 1457 01:12:47,510 --> 01:12:48,040 Dobrze? 1458 01:12:48,040 --> 01:12:51,340 Bo gdy tak się dzieje, wiesz, że już w końcu uderzył w samą wartość. 1459 01:12:51,340 --> 01:12:59,135 Więc chcesz pętli aż do min jest mniejsza niż lub równa to-- mmm 1460 01:12:59,135 --> 01:13:01,510 nie mniejsza niż lub równa odwrotnie around-- max jest. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Czy to ma sens? 1463 01:13:16,160 --> 01:13:18,810 Zrobiłem kilka prób, aby uzyskać to prawo. 1464 01:13:18,810 --> 01:13:21,869 Ale pętli aż do maksymalnej wartości jest w zasadzie prawie mniej 1465 01:13:21,869 --> 01:13:23,410 lub równą do minimum, tak? 1466 01:13:23,410 --> 01:13:25,201 To jest, gdy wiesz, że już zbieżne. 1467 01:13:25,201 --> 01:13:29,290 PUBLICZNOŚCI: Kiedy będzie maksymalna wartość może być mniejsza niż minimum? 1468 01:13:29,290 --> 01:13:31,040 ANDI PENG: Jeśli będziecie zachowywać dostosowując go, co 1469 01:13:31,040 --> 01:13:32,380 jest to, co mamy zamiar robić w tym. 1470 01:13:32,380 --> 01:13:33,460 Czy to ma sens? 1471 01:13:33,460 --> 01:13:35,750 Minimalna i maksymalna są tylko liczby całkowite, które są prawdopodobnie 1472 01:13:35,750 --> 01:13:39,260 będzie chciał stworzyć, aby utrzymać utwór z których szukamy. 1473 01:13:39,260 --> 01:13:41,790 Ponieważ tablicy istnieje niezależnie od tego, co robimy. 1474 01:13:41,790 --> 01:13:45,030 Podobnie jak, nie jesteśmy w rzeczywistości fizycznie odcięcie tablicy, prawda? 1475 01:13:45,030 --> 01:13:47,261 Jesteśmy po prostu dostosowanie gdzie szukamy. 1476 01:13:47,261 --> 01:13:48,136 Czy to ma sens? 1477 01:13:48,136 --> 01:13:48,472 >> PUBLICZNOŚCI: Tak. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI PENG: OK. 1479 01:13:49,110 --> 01:13:57,090 Więc jeśli jest to warunek naszej pętli, co chcemy wewnątrz tej pętli? 1480 01:13:57,090 --> 01:13:58,700 Co będziemy się chce zrobić? 1481 01:13:58,700 --> 01:14:02,390 Więc teraz, że mamy max i min, w prawo, 1482 01:14:02,390 --> 01:14:04,962 prawdopodobnie stworzył tu gdzieś. 1483 01:14:04,962 --> 01:14:07,170 Mamy zamiar prawdopodobnie chcesz znaleźć środku, prawda? 1484 01:14:07,170 --> 01:14:08,450 Jak będziemy się w stanie znaleźć w środku? 1485 01:14:08,450 --> 01:14:09,491 Co się mathematical-- 1486 01:14:09,491 --> 01:14:11,079 PUBLICZNOŚCI: Max oraz min podzielić przez 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI PENG: Dokładnie. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Czy to ma sens? 1490 01:14:21,620 --> 01:14:25,780 A czy wy, dlaczego my nie tylko use-- dlaczego to zrobił 1491 01:14:25,780 --> 01:14:27,850 zamiast robić po prostu n dzieli się przez 2? 1492 01:14:27,850 --> 01:14:30,310 To dlatego, że n jest wartością że zamierza pozostać taka sama. 1493 01:14:30,310 --> 01:14:30,979 Dobrze? 1494 01:14:30,979 --> 01:14:34,020 Ale jak możemy dostosować naszą minimalną i wartości maksymalne, że będziemy zmieniać. 1495 01:14:34,020 --> 01:14:36,040 I w rezultacie, nasz środkowy zmieni zbyt. 1496 01:14:36,040 --> 01:14:37,873 Więc dlatego chcemy aby to zrobić tutaj. 1497 01:14:37,873 --> 01:14:38,510 OK. 1498 01:14:38,510 --> 01:14:41,600 >> A potem, teraz, Odkryliśmy our-- tak. 1499 01:14:41,600 --> 01:14:44,270 >> PUBLICZNOŚCI: Wystarczy szybkie question-- kiedy mówisz, min i max, 1500 01:14:44,270 --> 01:14:46,410 zakładając, że jesteśmy to już klasyfikowane? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI PENG: Tak, to rzeczywiście Warunkiem wstępnym poszukiwania binarnego, 1502 01:14:48,400 --> 01:14:49,816 że trzeba wiedzieć, że jest klasyfikowane. 1503 01:14:49,816 --> 01:14:53,660 Dlatego właśnie rodzaju, piszesz w swojej Problem ustawione przed wyszukiwania binarnego. 1504 01:14:53,660 --> 01:14:55,910 OK. 1505 01:14:55,910 --> 01:14:58,876 Więc teraz, że wiemy, gdzie nasz punkt środkowy jest, co chcesz tu zrobić? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> PUBLICZNOŚCI: Chcemy, aby porównać że w drugiej. 1508 01:15:04,319 --> 01:15:05,110 ANDI PENG: Dokładnie. 1509 01:15:05,110 --> 01:15:12,280 Więc masz zamiar porównać średniej wartości, prawda? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 I co to mówi nam, gdy porównamy? 1512 01:15:18,670 --> 01:15:22,226 Co chcemy zrobić potem? 1513 01:15:22,226 --> 01:15:25,389 >> PUBLICZNOŚCI: Jeśli wartość jest większa niż w połowie, chcemy go odciąć. 1514 01:15:25,389 --> 01:15:26,180 ANDI PENG: Dokładnie. 1515 01:15:26,180 --> 01:15:33,940 Tak więc, jeśli wartość jest większa niż w połowie, jesteśmy 1516 01:15:33,940 --> 01:15:36,550 będzie chciał zmienić te Minimalne i maxes, prawda? 1517 01:15:36,550 --> 01:15:38,980 Co chcemy zmienić? 1518 01:15:38,980 --> 01:15:42,145 Tak więc, jeśli wiemy, że wartość jest gdzieś tu, co prawda, że ​​do zmiany? 1519 01:15:42,145 --> 01:15:44,758 Chcemy zmienić nasze Minimalna się w połowie, prawda? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 A potem jeszcze, czy jest w tym połowę, co chcemy zmienić? 1522 01:15:54,292 --> 01:15:55,306 >> PUBLICZNOŚCI: Twoja maksymalna. 1523 01:15:55,306 --> 01:15:55,972 ANDI PENG: Tak. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 I to jesteś po prostu się zachować zapętlenie, prawda? 1526 01:16:04,680 --> 01:16:08,920 Bo teraz, po jednej iteracji dzięki, masz max tutaj. 1527 01:16:08,920 --> 01:16:10,760 A potem można przeliczyć w połowie. 1528 01:16:10,760 --> 01:16:11,990 I wtedy można porównać. 1529 01:16:11,990 --> 01:16:14,766 I masz zamiar jechać dalej aż minut i maxes 1530 01:16:14,766 --> 01:16:15,890 są zasadniczo zbieżne. 1531 01:16:15,890 --> 01:16:17,890 I to jest, gdy wiesz, że musisz trafić na koniec. 1532 01:16:17,890 --> 01:16:20,280 I albo już go znajdziesz albo nie mają w tym momencie. 1533 01:16:20,280 --> 01:16:23,170 >> Czy to ma sens dla każdego? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 OK. 1536 01:16:26,770 --> 01:16:27,900 To jest bardzo ważne, bo będziesz miał 1537 01:16:27,900 --> 01:16:29,760 napisać to w dzisiejszy wieczór kodu. 1538 01:16:29,760 --> 01:16:32,660 Ale faceci mają całkiem dobry poczucie tego, co należy robić, 1539 01:16:32,660 --> 01:16:34,051 co jest dobre. 1540 01:16:34,051 --> 01:16:34,550 OK. 1541 01:16:34,550 --> 01:16:38,840 Tak więc mamy około siedmiu minut lewej sekcji. 1542 01:16:38,840 --> 01:16:43,170 Tak więc mamy zamiar rozmawiać o Ten zbior, że będziemy robić. 1543 01:16:43,170 --> 01:16:46,410 Tak więc pset jest podzielony na dwie części. 1544 01:16:46,410 --> 01:16:50,230 Pierwsza połowa dotyczy wdrożenie find 1545 01:16:50,230 --> 01:16:54,210 w którym piszesz przeszukiwanie liniowe, A przeszukiwanie binarne i algorytm sortowania. 1546 01:16:54,210 --> 01:16:56,690 >> Więc to jest pierwszy Czas w pset gdzie 1547 01:16:56,690 --> 01:17:00,050 będziemy dając wam to, co się nazywa Kod dystrybucji, która jest kod 1548 01:17:00,050 --> 01:17:02,740 że mamy wstępnie napisane, ale tylko w lewo niektóre kawałki off 1549 01:17:02,740 --> 01:17:04,635 , aby zakończyć pisanie. 1550 01:17:04,635 --> 01:17:07,510 Więc chłopaki, jeśli spojrzeć na to Kod, można dostać naprawdę bać. 1551 01:17:07,510 --> 01:17:08,630 Jeśli jesteś po prostu lubię, ahh, I nie wiem co to robi, 1552 01:17:08,630 --> 01:17:11,670 Nie wiem, jak, który wydaje tak skomplikowane, ahh, zrelaksować się. 1553 01:17:11,670 --> 01:17:12,170 Jest ok. 1554 01:17:12,170 --> 01:17:12,930 Przeczytaj specyfikację. 1555 01:17:12,930 --> 01:17:16,920 Spec wyjaśni dokładnie, Co wszystkie te programy robią. 1556 01:17:16,920 --> 01:17:20,560 >> Na przykład, generate.c to program że przyjdzie z pset. 1557 01:17:20,560 --> 01:17:24,060 W rzeczywistości nie ma go dotknąć, ale należy zrozumieć, co robi. 1558 01:17:24,060 --> 01:17:28,550 I generate.c, wszystko co robi jest albo generowanie liczb losowych 1559 01:17:28,550 --> 01:17:32,400 czy można dać ziarno, jak umówiony numer, który trwa, 1560 01:17:32,400 --> 01:17:34,140 i generuje więcej numerów. 1561 01:17:34,140 --> 01:17:37,170 Więc nie ma specyficzny sposób wdrożenie generate.c, w którym 1562 01:17:37,170 --> 01:17:42,760 można po prostu zrobić kilka numerów , aby sprawdzić swoje inne sposoby na. 1563 01:17:42,760 --> 01:17:45,900 >> Więc jeśli chcesz, na Przykładem, sprawdzić swoje znalezisko, 1564 01:17:45,900 --> 01:17:48,970 co chcesz uruchomić generate.c, generować kilka numerów, 1565 01:17:48,970 --> 01:17:50,880 a następnie uruchomić funkcję pomocników. 1566 01:17:50,880 --> 01:17:53,930 Twoja funkcja pomocnicy, gdzie jesteś faktycznie fizycznie pisania kodu. 1567 01:17:53,930 --> 01:17:59,330 I pomyśleć pomocników w postaci pliku biblioteki piszesz, że znalezisko dzwoni. 1568 01:17:59,330 --> 01:18:02,950 I tak w ciągu helpers.c, będziesz zrobić wyszukiwania i sortowania. 1569 01:18:02,950 --> 01:18:06,500 >> A potem będziesz zasadniczo wystarczy umieścić je wszystkie razem. 1570 01:18:06,500 --> 01:18:10,350 Spec powie, jak umieścić, że w linii poleceń. 1571 01:18:10,350 --> 01:18:14,880 I będziesz w stanie sprawdzić, czy nie twoja sortowania i wyszukiwania pracy. 1572 01:18:14,880 --> 01:18:15,870 Chłodny. 1573 01:18:15,870 --> 01:18:18,720 Czy ktoś już się rozpoczął, a napotkane problemy lub pytania 1574 01:18:18,720 --> 01:18:20,520 mają teraz z tym? 1575 01:18:20,520 --> 01:18:21,020 OK. 1576 01:18:21,020 --> 01:18:21,476 >> PUBLICZNOŚCI: Czekaj. 1577 01:18:21,476 --> 01:18:21,932 Mam pytanie. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI PENG: Tak. 1579 01:18:22,844 --> 01:18:28,390 >> PUBLICZNOŚCI: Więc zacząłem robić wyszukiwanie liniowe w helpers.c 1580 01:18:28,390 --> 01:18:29,670 i nie było naprawdę działa. 1581 01:18:29,670 --> 01:18:34,590 Ale później okazało się, że po prostu trzeba go usunąć i wykonać przeszukiwanie binarne. 1582 01:18:34,590 --> 01:18:36,991 Więc to ma znaczenie, jeśli to nie działa? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI PENG: Krótka odpowiedź brzmi: nie. 1585 01:18:41,510 --> 01:18:42,642 Ale ponieważ jesteśmy not-- 1586 01:18:42,642 --> 01:18:44,350 PUBLICZNOŚCI: Ale nikt nie rzeczywiście sprawdzanie. 1587 01:18:44,350 --> 01:18:46,058 ANDI PENG: Nigdy nie jesteśmy zobaczymy, że. 1588 01:18:46,058 --> 01:18:49,590 Ale prawdopodobnie chcesz, aby upewnić się, że wyszukiwarka działa. 1589 01:18:49,590 --> 01:18:51,700 Bo jeśli liniowa wyszukiwarka nie działa, 1590 01:18:51,700 --> 01:18:54,410 to są szanse, binarny wyszukiwarka nie będzie działać, jak również. 1591 01:18:54,410 --> 01:18:56,646 Bo masz podobny Logika w obu z nich. 1592 01:18:56,646 --> 01:18:58,020 I nie, to nie ma znaczenia. 1593 01:18:58,020 --> 01:19:01,300 Więc jedyne będziesz kolei w to sortowanie i wyszukiwanie binarne. 1594 01:19:01,300 --> 01:19:02,490 Tak. 1595 01:19:02,490 --> 01:19:06,610 >> A także, wiele dzieci były próbuje skompilować helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Nie jesteś w rzeczywistości dozwolone aby to zrobić, ponieważ helpers.c 1597 01:19:09,550 --> 01:19:11,200 nie posiada głównej funkcji. 1598 01:19:11,200 --> 01:19:13,550 I tak powinieneś tylko być właściwie kompilacją 1599 01:19:13,550 --> 01:19:18,670 generowanie i znaleźć, bo znaleźć połączenia helpers.c i funkcji w nim. 1600 01:19:18,670 --> 01:19:20,790 Więc sprawia, że ​​debugowanie ból w tyłek. 1601 01:19:20,790 --> 01:19:22,422 Ale to, co mamy do zrobienia. 1602 01:19:22,422 --> 01:19:23,880 PUBLICZNOŚCI: Ty po prostu zrobić wszystko, prawda? 1603 01:19:23,880 --> 01:19:27,290 ANDI PENG: Można po prostu uczynić wszystko, jak również, tak. 1604 01:19:27,290 --> 01:19:28,060 OK. 1605 01:19:28,060 --> 01:19:32,570 Więc to w kategoriach co pset prosi wszystkich do zrobienia. 1606 01:19:32,570 --> 01:19:35,160 Jeśli masz jakiekolwiek pytania, nie wahaj do zadawania mi po sekcji. 1607 01:19:35,160 --> 01:19:37,580 Będę tu przez jakieś 20 minut. 1608 01:19:37,580 --> 01:19:40,500 >> I tak, gdy pset użytkownika naprawdę nie jest tak źle. 1609 01:19:40,500 --> 01:19:41,680 Wy powinno być OK. 1610 01:19:41,680 --> 01:19:43,250 Te, wykonaj następujące wytyczne. 1611 01:19:43,250 --> 01:19:47,840 Niby mają poczucie, logicznie, co powinno się dziać, a wszystko będzie w porządku. 1612 01:19:47,840 --> 01:19:48,690 Nie należy się bać. 1613 01:19:48,690 --> 01:19:50,220 Jest dużo kodu już tam jest napisane. 1614 01:19:50,220 --> 01:19:53,011 Nie należy się bać, jeśli nie zrozumieć, co to wszystko znaczy. 1615 01:19:53,011 --> 01:19:54,749 Jeśli jest to dużo, to jest całkowicie w porządku. 1616 01:19:54,749 --> 01:19:55,790 I przychodzą do godzin pracy biura. 1617 01:19:55,790 --> 01:19:57,520 Pomożemy Ci spojrzeć. 1618 01:19:57,520 --> 01:20:00,810 >> PUBLICZNOŚCI: z dodatkowym funkcje, możemy spojrzeć ci się? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI PENG: Tak, to są w kodzie. 1620 01:20:03,417 --> 01:20:05,750 W grze 15 połowa to już napisany dla Ciebie. 1621 01:20:05,750 --> 01:20:09,310 Więc te funkcje są już w kodzie. 1622 01:20:09,310 --> 01:20:12,020 Tak. 1623 01:20:12,020 --> 01:20:12,520 W porządku. 1624 01:20:12,520 --> 01:20:14,000 Cóż, powodzenia. 1625 01:20:14,000 --> 01:20:15,180 To jest obrzydliwe dni. 1626 01:20:15,180 --> 01:20:19,370 Więc mam nadzieję, że chłopaki nie czują się zbyt źle o pobyt wewnątrz i kodowania. 1627 01:20:19,370 --> 01:20:22,133