>> [Odtwarzanie muzyki]
DAVID MALAN: W porządku.
Dobrze, witamy z powrotem.
Więc to jest Tydzień 4, początek nich, już.
A przypomnijmy sobie, że w zeszłym tygodniu, stawiamy kod na bok tylko trochę
i zaczęliśmy rozmawiać trochę więcej wysokim poziomie, o rzeczy, jak
wyszukiwanie i sortowanie, które choć dość proste pomysły, są
reprezentatywne klasy problemów zaczniesz rozwiązywać szczególnie
jak zacząć myśleć o final projekty i ciekawe rozwiązania można
może mieć do rzeczywistych problemów.
Teraz sortowanie bąbelkowe był jednym z najprostszych takie algorytmy, i to
pracował poprzez te małe liczby na liście lub w rodzaju tablicy z
bubble drogę do góry i duże cyfry przejść swoją drogę w dół do
koniec tej listy.
>> I pamiętam, że możemy wizualizować Sortowanie bąbelkowe mało
coś takiego.
Więc pozwól mi iść dalej i kliknij przycisk Start.
Ja wstępnie rodzaju bańki.
A jeśli przypomnieć, że wyższy blue linie reprezentują duże cyfry, małe
niebieskie linie oznaczają małe liczby, jak możemy przejść przez to jeszcze raz i jeszcze raz i
ponownie, porównywanie dwóch prętów obok siebie inne w kolorze czerwonym, jedziemy do wymiany
Największy i najmniejszy jeśli są one w porządku.
>> Więc to będzie iść i iść i iść dalej, a zobaczysz, że większe
elementy są torują sobie drogę do prawo, a mniejsze elementy są
torują sobie drogę do lewej.
Ale zaczęliśmy ilościowo wydajność,
Jakość tego algorytmu.
A my powiedzieliśmy, że w najgorszym przypadku, algorytm ten wziął
w przybliżeniu, ile kroków?
>> Więc n do kwadratu.
A co było n?
>> PUBLICZNOŚCI: Ilość elementów.
>> DAVID MALAN: Tak n było Ilość elementów.
I tak będziemy robić to częściej.
Za każdym razem chcemy rozmawiać o wielkości problemu lub rozmiar
input, lub czas potrzebny do standardu, my będziemy po prostu
co uogólnione wejście jest jako n.
Więc z powrotem w tygodniu 0, liczba stron w książce telefonicznej był n.
Liczba studentów w pomieszczeniu się N.
Więc i tu mamy po że wzór.
>> Teraz n do kwadratu nie jest szczególnie szybko, więc staraliśmy się zrobić lepiej.
I tak patrzyliśmy na kilka inne algorytmy, z których
były rodzaju wybór.
Wybór był więc sort trochę inaczej.
To było prawie prostsze, ośmielę się powiedzieć, zgodnie z którą zacząłem na początku
Lista naszych wolontariuszy i po prostu ponownie i znowu i znowu przeszedł
lista, wyrywanie najmniejsza elementem w czasie i oddanie go lub
jej na początku listy.
>> Ale to też kiedyś zaczynaliśmy myśleć przez matematykę i większe
obraz, myślałem o tym, jak wiele razy Byłem tam iz powrotem iz powrotem
i do przodu, my powiedzieliśmy, w najgorszym przypadku, sort wybór też był, co?
n do kwadratu.
Teraz w świecie rzeczywistym, to może rzeczywiście być nieznacznie szybciej.
Bo znowu, nie mam do utrzymania Cofając się raz miałem posortowane
najmniejsze elementy.
Ale jeśli myślimy o bardzo dużych n, a jeśli rodzaj zrobić z matematyki jako
I tak na pokładzie, z n do kwadratu minus coś, wszystko inne
oprócz n do kwadratu, raz n robi się naprawdę duża, nie
naprawdę aż tak istotne.
Więc jak informatyków, mamy coś w rodzaju przymknąć oko na mniejsze
czynniki i skupić się tylko na czynnik Wyrażenie, które zamierza dokonać
Największa różnica.
>> No, wreszcie spojrzał w rodzaju wstawiania.
I to było podobne w duchu, ale zamiast przejść iteracyjnie i
wybierz najmniejszy element o razem, a nie wziął rękę, że
została rozpatrzona, i postanowiłem, wszystko Dobrze, że należysz tutaj.
Potem przeniósł się do następnego elementu i postanowił, że on lub
należała tutaj.
A potem przeniosłem się na i na.
I może się, po drodze, przeniesienie tych ludzi w celu
zrobić miejsce dla nich.
Więc to było coś w rodzaju psychicznego odwrócenia z rodzaju selekcji, że
nazywa rodzaj wstawiania.
>> Więc te tematy, które pojawiają w świecie rzeczywistym.
Jeszcze kilka lat temu, gdy pewien senator został na prezydenta,
Eric Schmidt, w czasie CEO Google, rzeczywiście miał okazję
przeprowadzić z nim wywiad.
I myśleliśmy, że będziemy dzielić tę YouTube przypiąć na Ciebie, czy możemy włączyć się
objętość.
>> [PLAYBACK VIDEO]
>> -Teraz, Senator, jesteś tutaj w Google, a ja lubię myśleć o prezydenturę
jak rozmowy kwalifikacyjnej.
>> [Śmiech]
>> -Teraz trudno dostać zadaniem jako prezydenta.
I idziesz przez rygory teraz.
Trudno też, aby dostać pracę w Google.
Mamy pytania i prosić nasi kandydaci pytania.
A ten jest z Larry Schwimmer.
>> [Śmiech]
-Myślicie, że żartuję?
Jest tutaj.
Co to jest najbardziej skuteczny sposób sortować milion dwa-bitowe liczby całkowite?
>> [Śmiech]
>> -No cóż, uh -
>> -Przepraszam.
Może powinniśmy -
>> -Nie, nie, nie, nie, nie.
>> -To nie jest -
OK.
>> -Myślę, że byłoby bubble sort być nie tak droga.
>> [Śmiech]
>> [CHEERING i oklaski]
>> -Chodź, który powiedział mu to?
OK.
>> [END PLAYBACK VIDEO]
>> DAVID MALAN: Więc nie masz.
Więc zaczęliśmy ilościowego nich działa razy, że tak powiem, z czymś
nazywa asymptotycznej notacji, która jest tylko w odniesieniu do naszego rodzaju toczenia
przymknąć oko na te czynniki i mniejsze tylko patrząc w czasie jazdy,
Wydajność tych algorytmów, jak n ma naprawdę duży w czasie.
A więc wprowadziliśmy duże O. i Big O reprezentował coś, co myśleliśmy,
jako górna granica.
I rzeczywiście, Barry, możemy obniżyć niż mikrofon nieco mało?
>> Myśleliśmy, że to jest górna granica.
Tak duże O z n do kwadratu oznacza, że ​​w w najgorszym przypadku, coś jak
Wybór odbędzie sort n kwadratu kroki.
Albo coś w rodzaju wstawiania by n kwadratu kroki.
Teraz coś wstawiania sort, co było najgorszym przypadku?
Biorąc pod uwagę, array, co jest najgorsze możliwy scenariusz, który może się okazać,
się w obliczu?
>> Jest to całkowicie do tyłu, prawda?
Bo jeśli jest to całkowicie do tyłu, co musisz zrobić dużo pracy.
Bo jeśli jesteś całkowicie do tyłu, masz zamiar znaleźć
Największym elementem tutaj, choć należy, tam na dole.
Więc masz zamiar powiedzieć, dobrze, co ten moment w czasie, tutaj mają miejsce,
więc zostawić ją w spokoju.
>> Wtedy zdajesz sobie sprawę, oh, cholera, muszę przenieść ten nieco mniejszy element, do
lewo od Ciebie.
Potem muszę zrobić to jeszcze raz i znowu i znowu.
I gdybym chodził w tę iz powrotem, można to coś w rodzaju czuć wydajność
że algorytm, ponieważ ciągle jestem tasowanie wszyscy w
array, aby zrobić miejsce dla niego.
Więc to jest najgorszy przypadek.
>> Natomiast -
i to był cliffhanger ostatnio -
możemy powiedzieć, że rodzaj wstawiania była omega z czego?
Jaki jest najlepszy-case running czas sortowania wstawiania?
Więc to faktycznie n.
To było puste, że wyszliśmy na pokładzie ostatni raz.
>> I to jest omega n bo dlaczego?
No, w najlepszym przypadku, co jest sort wstawiania będzie przekazany?
Cóż, lista, która jest całkowicie posortowane już, minimal do zrobienia.
Ale to, co jest miłe o rodzaju wstawiania jest to, że dlatego, że zaczyna się tutaj i
decyduje, oh, jesteś numer jeden, należysz tutaj.
Och, co za szczęście.
>> Jesteś numer dwa.
Ty również tutaj.
Numer trzy, a nawet lepiej, należysz tutaj.
Tak szybko, jak to robi się do końca liście, od sortowania wstawiania w pseudokod
że szliśmy przez ustnie Ostatni raz, to się robi.
Ale selekcji Ilość natomiast, robiłem co?
>> Ruszyłem listę znowu i znowu i znowu.
Ponieważ klucz insight był tylko kiedy już spojrzał na drodze do
koniec listy możesz być pewien, że element był wybrany
rzeczywiście obecnie najmniejszy element.
Więc te różne modele mentalne end up uzyskując pewne bardzo realne-świat
Różnice dla nas, jak i te teoretyczne asymptotyczne różnice.
>> Przypomnę więc tylko, to, big O n kwadratu, widzieliśmy kilka takich
algorytmy do tej pory.
Big O n?
Co to jest algorytm, który może uznać big O n?
W najgorszym przypadku, trwa liniowa ilość etapów.
>> OK, linear search.
, A w najgorszym przypadku, w którym jest Element szukasz kiedy
stosując liniowy wyszukiwania?
>> OK, w najgorszym przypadku, to nie jest nawet tam.
A w drugim przypadku najgorszego, to aż w końcu, co jest
Plus-czy-minus jeden etap różnica.
Tak więc na koniec dnia, możemy powiedzieć, że jest liniowa.
Big O n będzie liniowa search, gdyż w najgorszym przypadku,
element nie jest nawet tam lub to aż w końcu.
>> Cóż, big O log n.
Nie rozmawialiśmy szczegółowo o tego, ale widziałem go wcześniej.
, Co prowadzi w logarytmicznej tzw czas, w najgorszym przypadku?
>> Tak, tak, binary search.
I binary search w najgorszym przypadku może posiadać element gdzieś
średnim, czy gdzieś wewnątrz tablicy.
Ale znaleźć tylko raz Ciebie podzielić listę na pół, w
pół, na pół, na pół.
I wtedy voila, że ​​tam jest.
Albo znowu, w najgorszym przypadku, to nie jest nawet tam.
Ale nie wiesz, że to nie istnieje aż rodzaju osiągnięcia, które ostatnio
bottom-większość elementów przez połowę i zmniejszenie o połowę i połowę.
>> Big O 1.
Więc mogliśmy duże O z 2, Big O 3 lat.
Anytime chcesz tylko stałą liczbę, my tak jakby po prostu uproszczenia
że jak Big O z 1.
Nawet jeśli realistycznie, trwa 2 lub nawet 100 kroków, jeśli jest to
stałą liczbę kroków, po prostu powiedzieć, big O 1.
Co to jest algorytm w Big O z dnia 1?
>> PUBLICZNOŚCI: Znajdowanie długości zmiennej.
>> DAVID MALAN: Znalezienie długość zmiennej?
>> PUBLICZNOŚCI: No, długość jeśli jest już posortowane.
>> DAVID MALAN: Dobry.
OK, więc znalezienie długości coś jeżeli długość tego czegoś, podobnie jak
tablicy, są przechowywane w jakimś zmiennej.
Bo może po prostu czytać zmienną, lub wydrukować zmienną, lub
tylko ogólnie dostęp do tej zmiennej.
I voila, że ​​ma stały czas.
>> Natomiast, że z powrotem do zera.
Pomyśl pierwszym tygodniu C, dzwoni tylko printf i drukowanie
coś na ekranie jest zapewne stały czas, bo to po prostu trwa
niektóre liczba cykli procesora, aby pokazać że tekst na ekranie.
Albo czekać - to robi?
Jak inaczej możemy modelować wydajność printf?
Czy ktoś jak się nie zgadzam, że może to nie naprawdę stały czas jest?
W jakim sensie może printf ucieka czas, rzeczywiście drukuje ciąg na
ekran, być czymś inne niż stałe.
>> PUBLICZNOŚCI: [niesłyszalne].
>> DAVID MALAN: Tak.
Więc to zależy od naszego punktu widzenia.
Jeśli rzeczywiście myśleć o wejściu do printf jako ciąg znaków, a
Dlatego pomiaru wielkości, które wejście od jej długości - tak nazwijmy
że długość n, jak również -
zapewne, printf jest sama wielka O n bo to będzie cię n kroków
wydrukować każdy z tych n znaków, najprawdopodobniej.
Co najmniej w takim zakresie, że zakładamy że być może jest za pomocą pętli for
pod maską.
>> Ale my musimy patrzeć na to Kod do zrozumienia, że ​​lepiej.
I rzeczywiście, gdy chłopaki zaczynają analizowania własnych algorytmów, będziesz
dosłownie nie tylko to.
Sortuj gałki ocznej kod i myśleć o - wszystko w porządku, mam tej pętli
tutaj lub mam pętli zagnieżdżonych tutaj, że zrobi wszystko n n razy,
i można sortować rozumu drogę za pośrednictwem kodu, nawet jeśli jest to
pseudokod, a nie rzeczywisty kod.
>> Więc co z omega n do kwadratu?
Jaki był algorytm, który w najlepszy Sprawa nadal trwało n kwadratu kroki?
Tak?
>> PUBLICZNOŚCI: [niesłyszalne].
>> DAVID MALAN: Więc rodzaj selekcji.
Ponieważ w tym problemu naprawdę zmniejszona na to, że znowu nie wiem
Znalazłem prąd najmniejszy, aż I zostały sprawdzone wszystkie elementy cerować.
Tak, Omega, powiedzmy, n, po prostu przyszedł z jednym.
Sort Insertion.
Jeśli lista stanie się być sortowane już, w najlepszym przypadku mamy tylko
do jednego przejścia przez nią, w którym momencie jesteśmy pewni.
A następnie, że można powiedzieć, że jest liniowa, na pewno.
>> Co omega 1?
Co, w najlepszym przypadku, może podjąć stała liczba kroków?
Więc linear search, jeśli po prostu miał szczęście i element szukasz
jest na samym początku listy, jeśli to gdzie jesteś rozpoczęciem
liniowe przechodzenie tej listy.
>> I to jest prawda wiele rzeczy.
Na przykład, nawet binarny wyszukiwanie jest omega z 1.
Bo co, jeśli się naprawdę cholernie szczęście i klaskać-zimnica w środku
Twoja tablica jest liczba szukasz?
Więc można mieć szczęście tam, jak dobrze.
>> Ten wreszcie omega n log n.
Więc n log n, tak naprawdę nie mówić o jeszcze, ale -
>> PUBLICZNOŚCI: Scalanie rodzaju?
>> DAVID MALAN: sort Merge.
To był cliffhanger ostatniej chwili gdzie zaproponowano, i pokazaliśmy
wizualnie, że są algorytmy.
I połączyć rodzaj tylko jeden taki algorytm, który jest zasadniczo szybciej
niż niektóre z tych innych facetów.
Faktycznie, połączenie jest układ nie tylko w najlepszym przypadku n n dziennika, w najgorszym
Przypadek n n dziennika.
A kiedy masz ten zbieżność omega a big O jest to samo?
Możemy właściwie opisać, że jak to, co jest nazywa theta, choć to
nieco mniej powszechne.
Ale to po prostu oznacza, dwie granice, w tym przypadku, są takie same.
>> Więc połączyć rodzaju, co to naprawdę sprowadzają się do nas?
Cóż, pamiętam motywację.
Pozwól mi wyciągnąć kolejną animację nie patrzeć na ostatni raz.
Ten jeden, ten sam pomysł, ale jest trochę większy.
I zamierzam iść do przodu i podkreślić pierwsze - mamy coś w rodzaju wstawiania na
w lewym górnym rogu, a następnie rodzaj selekcji, sortowanie bąbelkowe, kilka innych rodzajów -
shell i szybkie - że nie rozmawiał o, i sterty i scalić rodzaju.
>> Tak przynajmniej spróbować skupić wzrok na trójce na lewo, a następnie
scalić sortowanie po kliknięciu ta zielona strzałka.
Ale dam wszystkie z nich uruchomić, po prostu daje poczucie różnorodności
algorytmy, które istnieją w świecie.
Mam zamiar dać ten bieg w ciągu kilku sekund.
A jeśli skupić oczy - pick Algorytm, skupić się na nim przez zaledwie
sekunda - zaczniesz widzieć wzór, że to wdrożenie.
>> Merge sort, zawiadomienia, jest wykonywana.
Sort Heap, szybkie sortowanie, shell -
więc wydaje się, wprowadziliśmy trzy Najgorsze algorytmy w zeszłym tygodniu.
Ale to dobrze, że jesteśmy tu dzisiaj, aby zajrzeć rodzaju łączenia, który jest jednym z
tym łatwiej ci jest patrzeć, nawet choć pewnie będą stawać zdanie
tylko trochę.
Tutaj widzimy, jak wiele sort wybór jest do bani.
>> Ale w odwrotną stronę, to bardzo łatwe do wdrożenia.
A może za komplet P 3, to jeden z Algorytmy wybrałeś do wdrożenia
w standardowej wersji.
Perfekcyjnie, idealnie poprawne.
>> Ale znowu, jak n ma duże, jeśli Decydując się na zastosowanie szybszego algorytmu
jak połączyć rodzaju, kursy są w większe i większe nakłady, kod jest tylko
będzie działać szybciej.
Twoja strona będzie działać lepiej.
Użytkownicy będą szczęśliwsi.
A więc są te efekty faktycznie daje
nam pewne głębsze myśli.
>> Warto więc przyjrzeć się, co łączyć sort faktycznie chodzi.
Fajne jest to, że scalanie sortowania jest właśnie to.
To jest znowu to, co nazwaliśmy pseudokod, pseudokod byt
English-like składni.
A prostota jest rodzaju fascynujące.
>> Tak więc na wejściu elementów n - tak, że oznacza po prostu, tutaj jest tablica.
Ma n rzeczy w nim.
To wszystko, co mówimy nie.
>> Jeśli n wynosi mniej niż 2, powrót.
Więc to jest po prostu banalna sprawa.
Jeśli n wynosi mniej niż 2, to oczywiście jest 1 lub 0, w tym przypadku rzeczą
jest już posortowane lub nie istnieje, tak po prostu wrócić.
Nie ma nic do zrobienia.
Więc to jest prosta sprawa, aby wyrwać się.
>> Else, mamy trzy etapy.
Sortowanie lewą połowę elementów, sortowania Prawa połowa elementów,
a następnie scalić posortowane połówki.
Co ciekawe jest to, że Jestem trochę punting, prawda?
Jest to rodzaj okrągłego definicji do tego algorytmu.
W jakim sensie jest to algorytm tych okólnik definicja?
>> PUBLICZNOŚCI: [niesłyszalne].
>> DAVID MALAN: Tak, mój algorytm sortowania, dwa z jego etapów są "sort
coś. "I tak, że błaga pytanie, dobrze, co mam zamiar użyć
sortować lewą połowę i prawa połowa?
A piękno jest to, że nawet jeśli ponownie, to jest umysł-gięcie
część potencjalnie można użyć tego samego Algorytm sortowania lewą połowę.
>> Ale chwileczkę.
Kiedy powiedziałem, aby posortować lewa połowa, jakie są dwa
kroków będzie następny?
Będziemy sortować lewą połowę Lewa połowa i prawa
połowa lewej połowie.
Cholera, jak mam rozwiązać te dwa połówki lub ćwiartki, a teraz?
>> Ale to jest OK.
Mamy algorytm sortowania tutaj.
I choć może się martwić o Najpierw jest to rodzaj infinite
pętla, to cykl, który nigdy nie jest się skończy - to będzie
końca po co się dzieje?
Gdy N jest mniejsze niż 2.
Które w końcu się stanie, bo jeśli trzymać połowę i
zmniejszenie o połowę w połowę tych połówek, z pewnością w końcu masz zamiar do końca
up z zaledwie 1 lub 0 elementów.
W tym momencie, ten algorytm mówi gotowe.
>> Więc prawdziwa magia w tym Algorytm wydaje się być w
że ostatni krok, łączenie.
To prosty pomysł, po prostu połączenie dwóch rzeczy, to jest to, co ostatecznie będzie
co pozwala nam posortować tablicę, powiedzmy, osiem elementów.
Więc mam osiem więcej piłeczki antystresowe się tutaj, osiem kawałków papieru, a jeden
Google Glass -
co mam zachować.
>> [Śmiech]
>> DAVID MALAN: Jeśli moglibyśmy się osiem wolontariuszy, a zobaczymy, czy możemy
grać to się, więc.
Wow, OK.
Informatyka jest miejsce zabawy.
Dobrze.
Więc jak można trzy, Największy ręcznie tam.
Cztery z tyłu.
A co zrobimy ci trzy w tym wierszu?
I cztery z przodu.
Więc osiem, dalej w górę.
>> [Śmiech]
>> DAVID MALAN: Jestem rzeczywiście nie wiem co to jest.
Czy kulki stres?
Lampy biurko?
Materiał?
Internet?
>> OK.
Więc chodź na górę.
Kto chce -
zachować wymyślanie.
Zobaczymy.
A to stawia się w miejscu -
jesteś w miejsce jednego.
Uh-oh, poczekaj chwilę.
1, 2, 3, 4, 5, 6, 7 - oh, dobrze.
Dobra, jesteśmy dobrzy.
W porządku, więc wszyscy mają siedzibę, ale nie na szybie Google.
Pozwól mi stać w kolejce te góry.
Jak masz na imię?
>> Michelle: Michelle.
>> DAVID MALAN: Michelle?
Dobra, masz wyglądać geek, czy to jest OK.
Cóż, ja też, jak sądzę, na chwilę.
Dobrze, standby.
Próbujemy wymyślić przypadek użycia dla Google Glass, a my
pomyślałem, że fajnie będzie po prostu zrobić tego, kiedy ludzie są na scenie.
Będziemy nagrywać świat z ich perspektywy.
Dobrze.
Chyba nie, co Google przeznaczone.
W porządku, jeśli nie masz nic przeciwko sobie ta przez następne minuty niewygodnych,
to byłoby wspaniałe.
>> Dobrze, więc mamy tu tablicę elementów, a tej tablicy, jak na
kawałki papieru w tych ludzi " ręce, jest obecnie bez sortowania.
>> Michelle: Och, to takie dziwne.
>> DAVID MALAN: To dość dużo losowo.
A za chwilę, będziemy próbować do wdrożenia seryjnej rodzaju razem
i zobaczyć, gdzie ten klucz wgląd jest.
I tu z rodzaju sztuczka seryjnej jest coś, czego jeszcze nie przyjęły.
My rzeczywiście potrzebują dodatkowa przestrzeń.
Więc co będzie szczególnie Ciekawe jest to, że te
Chłopaki będą się poruszać trochę nieco, bo mam zamiar założyć, że
jest dodatkowa tablica z miejsca, powiedzieć, tuż za nimi.
>> Więc jeśli są za ich fotelu, to średnie array.
Jeśli są one osadzone tutaj, to Podstawowym array.
Ale to jest zasób, który mamy nie wykorzystała dotąd z bańki
sort, z rodzaju selekcji, z rodzaju wstawiania.
Przypomnijmy, w ubiegłym tygodniu, wszyscy po prostu rodzaj tasuje w miejscu.
Nie używać żadnych dodatkowych pamięci.
Zrobiliśmy miejsce dla ludzi, ruchu ludzi wokół.
>> Więc to jest klucz insight, too.
Jest to kompromis, w ogóle w informatyka, zasobów.
Jeśli chcesz przyspieszyć coś jak czas, będziesz
zapłacić cenę.
I jeden z tych cen jest bardzo często przestrzeń, ilość pamięci lub twarde
miejsca na dysku, które używasz.
Albo, mówiąc, kwota czasu programista.
Ile czasu zajmuje Ci, ludzką, faktycznie realizować kilka
skomplikowany algorytm.
Ale na dzisiaj, trade-off jest czas i przestrzeń.
>> Jeśli więc wy chłopaki możecie trzymać swoje numerów, dzięki czemu możemy zobaczyć, że jesteś
Rzeczywiście dopasowanie 4, 2, 6, 1, 3, 7, 8.
Excellent.
Więc mam zamiar spróbować zgrać rzeczy, jeśli faceci mogą tylko
za mną tutaj.
>> Więc idę do realizacji w pierwszej kolejności, Pierwszy etap Pseudokod, który jest
na wejściu n elementów, jeśli n jest mniej niż 2, a następnie wrócić.
Oczywiście, że nie apply, więc ruszamy dalej.
Więc sortować lewą połowę elementów.
To znaczy, mam zamiar skupić się moje uwaga na chwilę na nich
czterech facetów tutaj.
Dobra, co mam dalej robić?
>> PUBLICZNOŚCI: Sortowanie lewą połowę.
>> DAVID MALAN: Więc teraz mam do sortowania Lewa połowa tych facetów.
Bo znowu, zakładają na siebie w Celem jest, aby posortować lewą połowę.
Jak ty to robisz?
Wystarczy postępować zgodnie z instrukcjami, a nawet choć robimy to ponownie.
Więc sortować lewą połowę.
Teraz jestem sortowania tych dwóch facetów.
Co będzie dalej?
>> PUBLICZNOŚCI: Sortowanie lewą połowę.
>> DAVID MALAN: Sortowanie lewą połowę.
Więc teraz to, to miejsce jest tutaj, Jest to lista wielkości 1.
A jakie jest twoje imię?
>> PRINCESS DAISY: Księżna Daisy.
>> DAVID MALAN: Księżna Daisy jest tutaj.
A więc ona jest już posortowane, bo Lista jest wielkości 1.
Co mam dalej robić?
OK, powrót, bo lista jest Wielkość 1, która jest mniejsza niż 2.
Więc jaki jest następny krok?
A teraz masz do rodzaju backtrack w swoim umyśle.
>> Sortowanie prawą połowę, co jest -
jak masz na imię?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
A więc co robimy teraz, że mamy listę wielkości 1?
>> PUBLICZNOŚCI: Powrót.
>> DAVID MALAN: Ostrożnie.
Wracamy po pierwsze, a teraz trzeci step - rodzaj i gdybym od przedstawiają go
obejmując dwa miejsca teraz, teraz ja trzeba połączyć te dwa elementy.
Więc teraz, niestety, elementy są w porządku.
Ale to jest, gdy proces scalania zaczyna się przekonujące.
>> Jeśli więc wy może bronić tylko chwila, będę potrzebny, w
chwila, krok za swoim krześle.
A jeśli Linda, ponieważ 2 jest mniejsza niż 4, to dlaczego nie zrobić
przychodzisz pierwszy?
Zostań tam.
Więc Linda, przyjdziesz po pierwsze.
>> Teraz w rzeczywistości, czy jest to po prostu tablica może po prostu przesunąć ją w czasie rzeczywistym
z tego krzesła do tego miejsca.
Więc wyobraź sobie, że miała pewne stałe Liczba kroków 1.
A teraz -
ale musimy umieścić w Pierwsza lokalizacja tutaj.
>> A teraz, jeśli można się wokół, jak dobrze, idziemy do
znajdować się w miejscu dwóch.
I mimo, że to jest jak jest biorąc chwilę, co jest ładne to
że lewa połowa Lewa połowa jest teraz posortowana.
Tak więc to, co było kolejnym krokiem, jeśli teraz przewinąć dalej w tej historii?
>> PUBLICZNOŚCI: Right pół.
>> DAVID MALAN: Sortowanie prawą połowę.
Więc macie to zrobić, jak również.
Więc jeśli można wstać na chwilę?
A jak masz na imię?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, więc Jess jest teraz w lewo połowę prawą połowę.
A więc ona jest lista wielkości 1.
Ona oczywiście posortowane.
A masz na imię?
>> Michelle: Michelle.
>> DAVID MALAN: Michelle jest oczywiście lista wielkości 1.
Ona już posortowane.
Więc teraz dzieje się magia, Proces scalania.
Więc kto będzie na pierwszym miejscu?
Oczywiście Michelle.
Więc jeśli można podjechać z powrotem.
Miejsca mamy do dyspozycji dla niej teraz jest tuż za tym krześle tutaj.
A teraz, jeśli można wrócić, jak również, mamy teraz, aby być jasne, dwa
połówek, każda o wymiarach 2 -
i tylko obraz nędzy, jeśli może zrobić trochę miejsca -
jeden lewy pół tutaj, jeden prawa połowa tutaj.
>> Przewiń dalej w historii.
Co krok to dalej?
>> PUBLICZNOŚCI: Merge.
>> DAVID MALAN: Więc teraz musimy połączyć.
Więc OK, więc teraz, na szczęście, mamy tylko uwolnił się cztery krzesła.
Użyliśmy więc dwa razy więcej pamięci, ale możemy dać klapać między
dwie tablice.
Więc jaki numer jest na pierwszym miejscu?
Więc Michelle, oczywiście.
Więc się wokół i podjąć twoje miejsce tu.
A potem numer 2 jest oczywiście następny, więc tu przyjść.
Numer 4, numer 6.
I znów, choć jest Trochę spaceru zaangażowany,
naprawdę, to może się zdarzyć, natychmiast, przesuwając jeden -
OK, dobrze zagrane.
>> [Śmiech]
>> DAVID MALAN: I teraz jesteśmy w bardzo dobrej formie.
Lewa połowa całego Wejście została posortowana.
W porządku, więc ci ludzie mieli Zaletą mojej -
jak to w końcu wszystkie dziewczyny na w lewo i wszyscy chłopcy na prawo?
>> OK, więc chłopaki 'kolej.
Więc nie będę Cię przez kroki.
Zobaczymy, czy możemy zastosować ponownie same pseudokod.
Jeśli chcesz iść do przodu i wstać, a wy, pozwól mi dać mikrofon.
Zobacz, czy nie można powtórzyć to, co właśnie zrobiliśmy tu na
Drugi koniec listy.
Kto musi mówić pierwszy, w oparciu o algorytm?
Tak więc wyjaśnić, co robisz przed Wprowadzenie jakichkolwiek ruchów stopy.
>> SPEAKER 1: Dobra, więc od Jestem lewa połowa
lewa połowa, wracam.
Prawda?
>> DAVID MALAN: Dobry.
>> SPEAKER 1: A potem -
>> DAVID MALAN: Kto robi mic przejść do następnego?
>> SPEAKER 1: Następny numer.
>> Głośnik 2: Jestem więc prawa połowa z lewej połowie
lewa połowa, i wrócę.
>> DAVID MALAN: Dobry.
Powrót.
Więc teraz, co dalej się z wami?
>> Głośnik 2: Chcemy zobaczyć, kto jest mniejszy.
>> DAVID MALAN: Dokładnie.
Chcemy połączyć.
Przestrzeń będziemy używać do łączenia ty do, chociaż jest to
oczywiście posortowane już, idziemy się według tego samego algorytmu.
Więc kto idzie z powrotem w pierwszej kolejności?
3 Tak więc, a następnie 7.
A teraz mic idzie do tych facetów, OK?
>> SPEAKER 3: Jestem więc prawa połowa lewa połowa, a mój n jest mniejsza niż
1, więc mam zamiar przejść -
>> DAVID MALAN: Dobry.
>> GŁOŚNIK 4: Jestem prawa połowa Prawa połowa prawej połowie, a ja jestem
także jedna osoba, więc jestem zamiar wrócić.
Więc teraz możemy scalania.
>> SPEAKER 3: Więc wracamy.
>> DAVID MALAN: Więc idziesz do tyłu.
Tak więc 5 idzie pierwszy, a następnie 8.
A teraz publiczność, która jest kroku musimy teraz przewinąć
tyłu, aby w naszych umysłach?
>> PUBLICZNOŚCI: Merge.
>> DAVID MALAN: Połączenie lewej i prawej połowy połowy początkowej lewej połowie.
Więc teraz -
i po prostu zrobić to jasne, zrobić trochę miejsca
między wami chłopaki.
Więc teraz, że to dwie listy, w lewo i prawo.
Więc jak teraz połączyć Ci faceci w przedni rząd siedzeń ponownie?
>> 3 pierwszy.
Następnie 5, oczywiście.
Następnie 7, a teraz 8.
OK, a teraz jesteśmy?
>> PUBLICZNOŚCI: Nie wykonano.
>> DAVID MALAN: Nie wykonano, ponieważ oczywiście, jest jeszcze jeden krok pozostały.
Ale znowu, powód używam tego żargon jak "do tyłu w swoim umyśle,"
to dlatego, że naprawdę co się dzieje.
Jedziemy przez te wszystkie etapy, ale jesteśmy jakby zatrzymując
Moment, nurkowanie w głąb Algorytm, zatrzymując się na chwilę,
nurkować głębiej w algorytmie, a teraz musimy posortować od przewijania w naszym
umysły i cofnąć wszystkie z tych warstw że mamy jakby zawieszone.
>> Więc teraz mamy dwie listy wielkości 4.
Jeśli ludzie mogą stać się po raz ostatni i zrobić trochę miejsca, żeby
jasno, że jest to w lewo połowa z oryginału,
Prawa połowa oryginału.
Kto jest pierwszy numer, że trzeba pociągnąć do tyłu?
Michelle, oczywiście.
>> Więc stawiamy Michelle tutaj.
A kto ma numer 2?
Numer 2 jest on z powrotem także.
Numer 3?
Excellent.
Numer 4, nr 5, nr 6, numer 7 i nr 8.
>> OK, więc czułem się dużo kroków, na pewno.
Ale teraz zobaczymy, jeśli nie możemy potwierdzić jakby intuicyjnie, że to
Algorytm gruntu, zwłaszcza n ma naprawdę duże, jak widzieliśmy
z animacjami, jest zasadniczo szybciej.
Więc mam prawo tego algorytmu, w najgorszym przypadku, a nawet w najlepszym przypadku,
jest duże O n razy log n.
Oznacza to, że istnieje jakiś aspekt tego algorytm, który podejmuje działania w N, ale
jest jeszcze jeden aspekt gdzieś w że iteracja, że ​​pętli, które
podejmuje działania n log.
Możemy umieścić nasz palec na co te dwa numery na myśli?
Cóż, w którym -
Gdzie mic iść?
>> SPEAKER 1: Jak zarejestrować n być Podaje nam się na dwie -
dzielenia przez dwa, zasadniczo.
>> DAVID MALAN: Dokładnie.
Za każdym razem, widzimy w każdym algorytmie tym samym dotąd, nie był to wzór
podziału, podziału, podziału.
I to zazwyczaj zmniejszona do czegoś, co jest
logarytmiczne, logarytm o podstawie 2.
Ale tak naprawdę to może być wszystko, ale zarejestrować bazę 2.
>> Teraz co z n?
Widzę, że my niby dzieli cię Chłopaki - dzieli się, dzieli się,
dzieli się, dzieli Cię.
Gdzie koniec pochodzi?
>> Więc jest to połączenie.
Bo o tym myśleć.
Podczas scalania osiem osób razem, przy czym połowa z nich to zestaw czterech
a druga połowa jest inna zestaw czterech, jak go
o zrobieniu połączenia?
Cóż, to zrobiliście dość intuicyjnie.
>> Ale jeśli zamiast tego zrobił to trochę więcej metodycznie, mógłbym wskazać na
lewej osoba najpierw moja lewa strony, wskazał na osoby najbardziej na lewo
z tego połowa z mojej prawej strony, a tylko następnie przeszedł przez
list, wskazując na najmniejszy element za każdym razem, przesuwając palcem nad i
W razie potrzeby na całej listy.
Ale to, co jest kluczem o tym połączeniu Proces jest mi porównanie tych par
elementów.
Z prawej połowy i z lewej pół, nigdy nie jestem po wycofywania.
>> Tak samo jest przy merge nie więcej niż n kroków.
A ile razy nie mam zrobić to połączenie?
Cóż, nie więcej niż n, a my po prostu zobaczył, że z ostatecznego scalenia.
I tak, jeśli zrobisz coś, że trwa zaloguj kroki n n razy, lub odwrotnie,
to będzie nam n razy log n.
>> I dlaczego jest to lepsze?
Cóż, jeśli już wiemy, że dziennik n jest lepszy niż n - prawda?
Widzieliśmy w poszukiwania binarnego, książkę telefoniczną Przykładem, log n był zdecydowanie
lepszy niż liniowy.
To znaczy, n razy log n jest zdecydowanie lepiej niż n razy inny
n, AKA n do kwadratu.
I to jest to, co w końcu poczuć.
>> Więc wielkie brawa, jeśli mogliśmy, dla tych facetów.
>> [APPLAUSE]
>> DAVID MALAN: A twoje prezenty rozstanie - można zachować numery,
jeśli chcesz.
A prezent rozstanie, jak zwykle.
Oh, a my wyślemy ci footage, Michelle.
Dziękuję.
Dobrze.
Pomóż sobie w piłkę na stres.
>> I pozwól mi wyciągnąć, w międzyczasie, nasz przyjaciel Rob Bowden do zaoferowania
nieco inne spojrzenie na to, ponieważ można myśleć o nich
kroków dzieje się w nieco inny sposób.
W rzeczywistości, set-up na co Rob jest o aby pokazać nam, zakłada, że ​​mamy
już zrobione podzielenie się big list do ośmiu małych list,
każda z wielkości 1.
>> Liczymy więc, zmieniając pseudokod Trochę tylko do rodzaju dostać w
Istotą sposobu łączenia prac.
Ale czas pracy co on o to, aby zrobić to jeszcze
będzie taki sam.
I znowu, set-up jest to, że on jest rozpoczęła z ośmioma listami wielkości 1.
Więc brakowało części, gdzie znajduje się faktycznie wykonane dziennika n, log n, log n
podzielenie wejścia.
>> [PLAYBACK VIDEO]
>> -To jest to na etapie pierwszym.
W etapie drugim, wielokrotnie łączy pary list.
>> DAVID MALAN: Hm.
Tylko dźwięk nadchodzi z mojego komputera.
Spróbujmy jeszcze raz.
>> -Just dowolnie wybrać, które - teraz mamy cztery listy.
Dowiedz się wcześniej.
>> DAVID MALAN: Nie pójdziemy.
>> -Połączenie 108 i 15, to w końcu się z listy 15, 108.
Połączenie 50 i 4, ale kończy się z 4, 50.
Połączenie 8 i 42, to kończy się z 8, 42.
A połączenie 23 i 16, to kończy się z 16, 23.
>> Teraz wszystkie nasze listy są wielkości 2.
Należy zauważyć, że każdy z cztery listy są sortowane.
Tak więc możemy rozpocząć scalanie par list ponownie.
Połączenie 15 i 108, 4 i 50, to najpierw wziąć 4, potem 15, a następnie
50, a następnie 108.
Połączenie 8, 42 i 16, 23, musimy najpierw podjąć 8, potem 16, potem 23,
następnie 42.
>> Więc teraz mamy tylko dwa wykazy wielkości 4, z których każdy jest sortowany.
Więc teraz możemy połączyć te dwie listy.
Po pierwsze, bierzemy 4, to bierzemy 8, a następnie weźmiemy 15, potem 16, a następnie
23, potem 42, potem 50, a potem 108.
>> [END PLAYBACK VIDEO]
>> DAVID MALAN: Ponownie, zawiadomienie, że nigdy dotknął dany filiżankę więcej niż jeden raz
po pogłębianie poza nim.
Tak że nigdy nie powtarza.
Więc on jest zawsze w ruchu w bok, i tam dostaliśmy n.
>> Dlaczego nie pozwolił mi wyciągnąć jedną animację że widzieliśmy już wcześniej, ale tym razem
koncentrując się tylko na sortowanie korespondencji seryjnej.
Pozwólcie mi iść do przodu i powiększyć w to tutaj.
Najpierw pozwól mi wybrać losową wejście, powiększ to i można sortować of zobaczyć
co braliśmy za pewnik, wcześniej, scalić sort faktycznie robi.
>> Tak więc zauważysz, że masz te połówki lub te czwarte lub te ósmych
Problem, który się nagle zacząć brać dobrą formę.
I w końcu, można zobaczyć na bardzo end że bam,
wszystko jest połączone ze sobą.
>> To są tylko trzy różne trwa na tej samej idei.
Ale klucz wgląd, jak przepaści i przejęcie w klasie pierwszej,
było to, że zdecydowaliśmy się jakoś podzielić Problem w coś wielkiego, w
sort coś identyczne w duchu, , ale mniejsze i mniejsze i mniejsze
i mniejsze.
>> Teraz kolejny świetny sposób, aby sortować z myślą o nich, nawet jeśli nie jest to
zamiar dać same intuicyjne zrozumienie, jest
Poniższa animacja.
Więc to jest ktoś video ułożyła że wiąże się inna
dźwięków o różnych operacji na sort wstawiania na sortowanie korespondencji seryjnej, a
na kilka innych.
Tak więc w chwili, mam zamiar uderzyć Odtwórz.
To około minuty długości.
I choć wciąż można zobaczyć wzory dzieje, tym razem co możliwe
również usłyszeć, jak te algorytmy są wykonywania inaczej i
nieco inne wzory.
>> To jest swego rodzaju wprowadzenie.
>> [TONES GRA]
>> DAVID MALAN: To znowu próbuje wstawić każdy element
do których należy.
To jest swego rodzaju bańki.
>> [TONES GRA]
>> DAVID MALAN: A można sortować z wyczuciem jak stosunkowo mało pracy to robi
na każdym etapie.
To jest to, co tediousness brzmi.
>> [TONES GRA]
>> DAVID MALAN: To jest rodzaj selekcji, gdzie wybrać element, który chcemy by
przechodzi znowu i znowu i znowu i umieszczenie go na początku.
>> [TONES GRA]
>> DAVID MALAN: To jest scalanie sort, które można naprawdę zacząć czuć.
>> [TONES GRA]
>> [Śmiech]
>> DAVID MALAN: Coś o nazwie gnome sort, który nie patrzeli.
>> [TONES GRA]
>> DAVID MALAN: Więc pokaż mi, a teraz, rozproszony, jak mam nadzieję, że to przez
muzyka, czy mogę trochę poślizgu Trochę matematyki tutaj.
Więc jest czwarty sposób, że możemy myśleć o tym, co to znaczy, to
funkcje, aby być szybciej niż te, które , które widzieliśmy wcześniej.
A jeśli jesteś w trakcie z background matematyki, można
rzeczywiście wie, że może już może uderzyć termin na tej techniki -
mianowicie rekurencja, funkcja że w jakiś sposób zwraca się.
>> I znowu przypomnieć, że rodzaj scalania pseudokod było cykliczne w sensie
że jeden z sortowania Merge w krokach było zadzwonić rodzaju -
to jest sama.
Ale na szczęście, bo mieliśmy dzwoniąc rodzaju, lub połączyć rodzaju,
specjalnie na mniejsze i mniejsze i mniejszych list, w końcu
dno dzięki czemu będziemy nazywać wariant podstawowy, zakodowane tak, że
powiedział, że jeśli lista jest mała, mniejsza niż 2 w tym przypadku, po prostu wrócić natychmiast.
Jeśli nie ma tego szczególnego przypadku, Algorytm nigdy by bottom out,
i może rzeczywiście dostać się do nieskończonej pętli naprawdę zawsze.
>> Ale załóżmy, że chcemy teraz szuka niektóre numery na to, ponownie, stosując n
jako wielkości wejściowych.
A ja chciałem zapytać, co jest Całkowity czas zaangażowany w
działa sortowanie korespondencji seryjnej?
Lub, bardziej ogólnie, co jest Koszt to w czasie?
>> Cóż to jest dość łatwe do ustalenia, że.
Jeśli n jest mniejsze niż 2, czas zaangażowany w sortowania n elementów,
w którym n oznacza 2, 0..
Bo po prostu wrócić.
Nie ma wiele do zrobienia.
Teraz prawdopodobnie, być może jest to jeden krok lub dwa kroki, aby dowiedzieć się ilość
działa, ale na tyle blisko 0, że Mam zamiar powiedzieć nie praca jest
wymagane, jeśli lista jest tak mała, być nieciekawe.
>> Ale ta sprawa jest interesująca.
Cykliczne sprawa była gałąź pseudokod, który powiedział jeszcze, sort
lewa połowa, uporządkować prawo pół, połączyć dwie połówki.
Teraz dlaczego to wyrażenie stanowią, że koszty?
Cóż, T n oznacza po prostu czas, aby posortować n elementów.
I wtedy na prawej stronie znak równości tam, T n podzielona
przez 2 odnosi się do kosztów co?
Sortowanie lewą połowę.
Inne T n dzieli się przez 2 jest prawdopodobnie odnosi się do kosztów
sortować prawą połowę.
>> A potem n Plus?
Czy połączenie.
Bo jeśli masz dwie listy, jedna z n rozmiar ponad 2, a drugi od wielkości n
ponad 2, trzeba przede wszystkim dotykać każdy z tych elementów, tak jak Rob
dotknęła każdego z kubków, a tylko Jak wskazaliśmy w każdym z
Wolontariusze na scenie.
Więc n jest koszt połączenia.
>> Teraz, niestety, ta formuła jest również sama cykliczne.
Więc jeśli zadał pytanie, czy n jest, powiedzmy, 16, jeżeli jest 16 osób na scenie
lub 16 kubków w filmie, jak wiele razem kroki trzeba zrobić, aby posortować je
z rodzaju korespondencji seryjnej?
To nie jest właściwie oczywista odpowiedź, bo teraz masz do rodzaju
rekurencyjnie odebrać tę formułę.
>> Ale to jest OK, bo chciałbym zaproponować które należy wykonać następujące czynności.
Czas zaangażowany do sortowania 16 osób lub 16 filiżanek będzie reprezentowany
ogólnie T z dnia 16.
Ale równa według naszych Poprzedni wzór, 2 razy więcej niż
Czas potrzebny do sortowania 8 filiżanek i 16.
I znowu plus 16 jest czas, aby połączyć, i dwa razy T z 8 jest
czas, aby uporządkować lewą połowę i prawo pół.
>> Ale znowu, to nie wystarczy.
Mamy nurkować głębiej.
To oznacza, że ​​musimy odpowiedzieć pytanie, co to jest T z 8?
Cóż T z 8 jest tylko 2 razy T z 4 plus 8.
No i co w T 4?
T 4 jest zaledwie 2 razy T z 2 plus 4.
Cóż, co T z 2?
T z 2 znajduje się zaledwie 2 razy T 1 plus 2.
>> I znowu jesteśmy trochę się tkwi w tym cyklu.
Ale to jest o trafienie, które tzw. wariant podstawowy.
Bo co to T 1, nie twierdzimy?
0.
Więc teraz w końcu możemy działać wstecz.
>> Jeśli T 1 jest 0, mogę teraz wrócić do jednego wiersz do tego gościa tutaj, i ja mogę
wtyczka w 0 dla T 1.
Więc to znaczy, że jest równy 2 razy zero, zwie 0 oraz 2.
I tak, że całe wyrażenie jest 2.
>> Teraz, jeśli biorę T z 2, którego odpowiedź wynosi 2, podłącz go do środkowej linii, T
4, że daje mi 2 razy 2 oraz 4, 8, tak.
Jeśli następnie podłączyć 8 do poprzedniego Linia, która daje mi 2 razy 8, 16.
A jeśli to nadal, że z 24, dodając w 16, to w końcu się
wartość 64.
>> Teraz tego rodzaju w sobie od mówi nic do notacji n,
duże O, omega, że ​​mamy mówił o.
Ale okazuje się, że 64 jest w istocie 16, wielkości wejściowych,
zaloguj bazy 2 z 16.
A jeśli jest to trochę zna, tylko wracam, i będzie ona wrócić
do Ciebie w końcu.
Jeśli jest to podstawa log 2, to jak 2 podniesiony do co daje 16?
Och, to jest 4, więc jest 16 razy 4.
>> I znowu, nie jest to wielka sprawa, jeśli to jest jakby zamglony pamięci teraz.
Ale na razie się na wierze że 16 log 16 jest 64.
I tak naprawdę, z tego prostego rozsądku sprawdzić, mamy potwierdzone -
ale nie udowodnione formalnie -
, że czas pracy seryjnej sort jest rzeczywiście n log n.
>> Więc nie jest źle.
To zdecydowanie lepiej niż Algorytmy, które widzieliśmy do tej pory, i
to dlatego, że mamy wykorzystała jeden, technika zwana rekurencji.
Ale bardziej interesujące niż to, że Pojęcie Dziel i rządź.
Ponownie, naprawdę tydzień 0 rzeczy, które nawet teraz jest powtarzające się w
bardziej przekonujące sposób.
>> Teraz trochę zabawnych ćwiczeń, jeśli masz nigdy nie zrobił tego - i prawdopodobnie
nie ma, bo jakby normalny ludzie nie sądzę, aby to zrobić.
Ale jeśli pójdę do google.com i jeśli Chcę dowiedzieć się czegoś o
rekurencja, Enter.
>> [Śmiech]
[Śmiech]
DAVID MALAN: Bad żart powoli rozprzestrzenia.
[Śmiech]
DAVID MALAN: wypadek, to tam.
I nie pisze to źle, i jest żart.
Dobrze.
Wyjaśnij ludzie obok ciebie, jeśli nie dość kliknął jeszcze.
Ale rekursji, bardziej ogólnie, odnosi w procesie funkcji wywołującej
sama, lub bardziej ogólnie, dzieląc Problem w coś, co może być
rozwiązany fragmentaryczne rozwiązując identyczne Problemy reprezentatywne.
>> Cóż, zmiana biegów na chwilę.
Chcemy do końca niektórych Cliffhangers, więc zacznijmy ustawić
etap, przez kilka minut, na bardzo prosty pomysł -
że wymiany dwóch elementów, prawda?
Wszystkie te algorytmy byliśmy mówi o ostatnich kilku
Wykłady obejmują niektóre rodzaj wymiany.
Dzisiaj to uwidoczniono przez nich coraz się z krzeseł i
chodzą, ale w kodzie, chcielibyśmy po prostu wziąć element z jednej tablicy
i plusk do innego.
>> Więc jak to zabrać?
Cóż, pozwól mi pójść dalej i napisać szybkie Program tutaj.
Mam zamiar iść do przodu i robić To, co poniżej.
Nazwijmy to -
Co chcemy nazwać ten jeden?
>> W rzeczywistości, nie ma.
Pozwól mi cofnąć.
Nie chcę, aby to zrobić cliffhanger jeszcze.
Będzie psuć zabawy.
Zróbmy to w zamian.
>> Załóżmy, że chcę napisać trochę Program, a teraz obejmuje to
Pomysł rekursji.
I niby ma przed siebie tam.
Zamierzam wykonać następujące czynności.
>> Po pierwsze, szybkie m.in. standardowej io.h, jak również warte wymienienia są z cs50.h.
A potem mam zamiar iść do przodu i stwierdzenie nieważności główny int
w zwykły sposób.
Zdałem sobie sprawę, jakie misnamed plik, tak Pozwólcie mi dodać rozszerzenie. c tutaj tak
że możemy go skompilować poprawnie.
Uruchom tę funkcję.
>> A funkcja chcę napisać, dość po prostu, to taki, który zwraca
Użytkownik w szeregu, a następnie dodaje się wszystkie numery między który
liczba i, powiedzmy, 0.
Więc najpierw mam zamiar iść do przodu i zadeklarować int n.
Następnie skopiować kod, który używaliśmy przez jakiś czas.
Podczas gdy coś jest prawdą.
Wrócę do tego za chwilę.
>> Co chcę zrobić?
Chcę powiedzieć printf pozytywne całkowita proszę.
A potem mam zamiar powiedzieć n ma dostać int.
Więc znowu, jakiś kod boilerplate które używaliśmy wcześniej.
I zamierzam to zrobić gdy n jest mniejsze niż 1.
Tak więc będzie to zapewnić, że użytkownik daje mi całkowitą dodatnią.
>> A teraz mam zamiar wykonać następujące czynności.
Chcę dodać wszystkie numery między 1 a i n, lub 0, a n,
równoważnie, aby uzyskać całkowitą sumę.
Tak duży symbol sigma że można przypomnieć.
Więc mam zamiar to zrobić pierwszego powołania Funkcja o nazwie Sigma,
przechodzącej w n, a następnie zamierzam powiedzieć, printf, odpowiedź jest tuż, tuż.
>> Tak w skrócie, mam i int od użytkownika.
I zapewniają, że to pozytywne.
Oświadczam zmienną odpowiedź int typ i przechowywać w nim powrót
wartość sigma, przekazując n jako wejście.
A potem wydrukować tę odpowiedź.
>> Niestety, choć brzmi sigma jak coś, co może być w
plik math.h, jego oświadczenie, to nie jest w rzeczywistości.
Więc to jest OK.
Można zaimplementować ten sam.
Idę do realizacji funkcji o nazwie sigma, a to zajmie
parametr -
niech po prostu nazwać to m, po prostu tak jest inaczej.
A potem się tutaj, mam zamiar powiedzieć, oraz, jeżeli m jest mniejsze niż 1 - jest to
bardzo nieciekawy program.
Więc mam zamiar iść do przodu i natychmiast powrócić 0.
To po prostu nie ma sensu, aby dodać wszystkie numery od 1 do m, jeżeli m
to samo 0 lub ujemna.
>> A potem mam zamiar iść do przodu i zrobić to bardzo iteracyjnie.
Mam zamiar zrobić ten rodzaj starej szkoły, i mam zamiar iść do przodu
i powiedzieć, że będę deklarowania kwoty do 0.
Wtedy będę mieć dla pętli int -
i pozwól mi zrobić, to dopasować nasze Kod dystrybucji, więc masz kopię
w domu. int i dostaje 1 na maksymalnie I jest mniejsza lub równa m.
i Plus Plus.
A następnie wewnątrz tego pętli for -
Jesteśmy prawie na miejscu -
suma dostaje sumę plus 1.
A potem mam zamiar powrócić sumę.
>> Więc zrobiłem to szybko, całkiem prawda.
Ale znowu, główną funkcją jest dość proste, oparte na kodzie mamy
napisane do tej pory.
Używa podwójną pętlę, aby uzyskać pozytywne int od użytkownika.
I następnie przekazać tę int do nowej funkcji nazywane sigma, wzywając go, ponownie, n.
I przechowywania wartości zwracanej, odpowiedź z czarnej skrzynki obecnie
Wiadomo jak Sigma, w zmiennym nazywa odpowiedź.
Następnie wydrukować go.
>> Jeśli teraz kontynuować historię, jak jest sigma realizowane?
Proponuję wprowadzić w następujący sposób.
Po pierwsze, trochę kontroli błędów , aby upewnić się, że użytkownik nie jest
bawić się ze mną i przekazując niektóre negatywne lub 0 wartość.
Potem deklaruje zmienną o nazwie Podsumowując i ustawić ją na 0.
>> I teraz zaczynają się poruszać z i równa 1, aż do i włącznie m,
bo chcę to wszystko numery od jednego do m włącznie.
A w środku tego dla pętli, po prostu zrobić suma dostaje cokolwiek to jest teraz, oraz
wartość i.
Plus wartość i.
>> Tak na marginesie, jeśli nie widziałem tego wcześniej, istnieje pewne syntaktyczne cukru
W przypadku tej linii.
Mogę przepisać to jako Plus równa i, tylko zapisać sobie kilka klawiszy
i spojrzeć trochę chłodniej.
Ale to wszystko.
To funkcjonalnie samo.
>> Niestety, ten kod-tych nie zamierza skompilować jeszcze.
Jeśli uruchomić make sigma 0, jak am I będzie się krzyknął?
Co to będzie nie podoba?
>> PUBLICZNOŚCI: [niesłyszalne].
>> DAVID MALAN: Tak, nie ogłoszono Funkcja do góry, tak?
C jest głupie, w to, że tylko robi to, co możesz powiedzieć to zrobić, a ty
trzeba to zrobić w tej kolejności.
I tak, jeśli uderzę Wpisz tutaj, będę dostać ostrzeżenie o sigma niejawny
deklaracja.
>> Oh nie, to problem.
Mogę iść do góry, a ja mogę powiedzieć, wszystko w porządku, poczekaj.
Sigma jest funkcja, która zwraca int i oczekuje
int jako wejścia, średnikiem.
Albo może umieścić całą funkcję nad głównym, ale w ogóle, ja bym
odradzam, że ponieważ jest to miło zawsze głównym na górze, aby
można nurkować w prawo i wie, co Program robi czytając główny pierwszy.
>> Więc teraz pozwól mi wyczyścić ekran.
Sigma 0 Remake.
Wszystko wydaje się sprawdzić.
Pozwólcie mi biegać sigma 0.
Pozytywna inter.
Dam mu numer 3 keep it simple.
Tak, że powinna dać mi 3 Plus 2 plus 1, czyli 6.
Wejdź i rzeczywiście mam 6.
>> Mogę zrobić coś większego -
50, 12, 75.
Podobnie jak stycznej, mam zamiar zrobić coś absurdalnego jak naprawdę duży
liczba, Oh, że faktycznie udało -
eh, nie sądzę, że to prawda.
Zobaczymy.
Niech naprawdę zadzieraj z nim.
>> To jest problem.
Co się dzieje?
Kod nie jest tak źle.
To wciąż liniowa.
Gwizd jest dobry efekt, choć.
Co się dzieje?
>> Nie wiem, czy to usłyszałem.
Okazuje się - i to jest tak na bok.
To nie jest kluczowy dla Pomysł rekursji.
Okazuje się, bo staram się stanowią tak dużą ilość, najbardziej
może to być błędnie przez C, jak wielu nie pozytywnego,
ale liczba ujemna.
>> Nie rozmawialiśmy o tym, ale to Okazuje się, że są liczby ujemne
W świecie oprócz do liczb dodatnich.
A sposób, w którym można reprezentują liczbę ujemną
w istocie jest, można użyć jednego specjalny bit do wskazania
pozytywne nad negatywnymi.
To jest trochę bardziej skomplikowane niż to, ale to jest podstawowa idea.
>> Więc niestety, jeśli C jest mylące jednego z tych bitów, jak w rzeczywistości oznacza,
oh, to jest liczba ujemna, moja pętla tu, na przykład, nie jest w rzeczywistości
zamierza wypowiedzieć.
Więc jeśli coś faktycznie drukowania znowu i znowu, chcielibyśmy
zobacz dużo.
Jednak ponownie, to obok punktu.
To jest naprawdę tylko rodzaj dociekliwość, że uda nam się
tyłu, aby ostatecznie.
Ale teraz, to jest poprawna Realizacja jeśli założymy, że
Użytkownik zapewni ints że dopasowanie ciągu liczb całkowitych.
>> Ale twierdzą, że ten kod, szczerze mówiąc, można zrobić o wiele więcej po prostu.
Jeśli cel w kasie jest podjąć szereg jak m i dodać wszystkie
numery między nim a 1 lub odwrotnie między 1 a, I twierdzą
że mogę pożyczyć ten pomysł, który łączy sort miał, który brał problem
tej wielkości podzielonej na coś mniejszego.
Może nie pół, ale mniejszy, ale reprezentatywnie same.
Sam pomysł, ale mniejszy problem.
>> Więc jestem w rzeczywistości - pozwól mi zapisać ten plik z innym numerem wersji.
Nazwijmy tę wersję 1 zamiast 0.
I twierdzą, że w rzeczywistości może reimplement to w tego rodzaju
umysłów sposób.
>> Mam zamiar zostawić część to sam.
I powiem, jeśli m jest mniejsza niż lub nawet równa 0 -
Jestem po prostu będzie trochę Tym razem bardziej anal
z mojego sprawdzania błędów -
Mam zamiar iść do przodu i zwraca 0.
To jest arbitralne.
Jestem po prostu podejmowaniu decyzji, czy użytkownik daje mi liczbę ujemną, jestem
powrocie 0, a powinni byli przeczytać Dokumentacja bliżej.
>> Else -
zauważyć, co mam zamiar zrobić.
Else I zamierzam wrócić m powiększonej -
co jest sigma z m?
Cóż, sigma m powiększonej m minus 1, oraz m minus 2 plus m minus 3.
Nie chcę pisać wszystko to.
Dlaczego nie mogę po prostu punt?
Rekursywnie nazywają siebie z lekko mniejszy problem, średnik,
i nazywają to dzień?
>> Prawda?
Teraz i tu można czuć lub martwić że jest to pętla nieskończona, że ​​jestem
wywołujących, przy czym jestem realizacji sigma poprzez wywołanie sigma.
Ale to jest zupełnie OK, bo że przed dodane, które linie?
>> PUBLICZNOŚCI: [niesłyszalne].
>> DAVID MALAN: 23 do 26, która jest mój, jeśli warunek.
Bo to, co jest ładne o odejmowanie tutaj, bo trzymam
oddaniem sigma mniejsze problemy, mniejsze problemy, mniejsze - to nie jest
połowę mniejsza.
To tylko krok dziecko mniejsze, ale to jest OK.
Bo w końcu, będziemy pracować nasza droga w dół do 1 lub 0.
I po raz trafiliśmy 0, sigma nie zacznie nazywać siebie więcej.
To będzie natychmiast wrócić 0.
>> Więc efekt, jeśli rodzaj wiatru to się w głowie, jest dodanie M oraz
m minus 1 plus m minus 2 plus m minus 3 plus kropka, kropka, kropka, m minus
m, w końcu daje 0, a Efekt jest ostatecznie dodać wszystkie
te rzeczy razem.
Więc nie mamy z rekurencji, rozwiązać problem, że
nie można rozwiązać przed.
Rzeczywiście, 0 wersja tego, a każdy Problem do tej pory, nie było rozwiązywalne
się tylko za pomocą pętli for lub podczas pętle lub podobnych konstrukcji.
>> Ale rekurencja, śmiem twierdzić, daje nam inny sposób myślenia o
problemów, przy czym jeśli możemy Problem, podzielić go z czegoś
dość duża w coś cierpkawym mniejsze, I twierdzą, że możemy go rozwiązać
może trochę bardziej elegancko w kategoriach konstrukcji, z mniejszą ilością kodu
a może nawet rozwiązać problemy, które być trudniejsze, a my będziemy w końcu
zobacz, rozwiązywaniu czysto iteracyjnie.
>> Ale cliffhanger, że zrobiłem chce zostawić nas na to było.
Pozwólcie mi iść do przodu i otworzyć się plik z -
faktycznie, pozwól mi odejść i zrobić to naprawdę szybko.
Pozwólcie mi iść dalej i zaproponować dodaje.
Wśród dzisiejszych kod jest ten plik tutaj.
Ten tutaj, noswap.
>> Więc to jest głupie mały program, który I bita się, że roszczenia do zrobienia
dodaje.
W głównym, najpierw deklaruje int o nazwie x i przypisuje go
wartość 1.
Następnie oświadcza, int y, a przypisuje jej wartość 2.
Następnie wypisuje co x i y jest.
Potem mówi, zamiana, dot dot dot.
>> Następnie twierdzi, że jest wywołanie funkcji nazywa swapa, przekazując xi
y, którego idea jest taka, że ​​mam nadzieję, że x i y będą wracać
inna, przeciwnie.
Następnie twierdzą zamienione!
z wykrzyknikiem.
Następnie wypisuje x i y.
>> Ale okazuje się, że to bardzo prosta demonstracja w dół
tutaj jest rzeczywiście buggy.
Mimo, że jestem oświadczając chwilowy zmienna i tymczasowo wprowadzenie w
to, czym jestem realokacja Wartość B -
który czuje się uzasadnione, ponieważ nie mam zapisywane kopie w temp..
Następnie zaktualizować b, aby równe co było w temp..
Ten rodzaj gry powłoki ruchomych do b i b do za pomocą tego
middle-temp czuje człowiek, który nazywał całkowicie uzasadnione.
>> Ale twierdzą, że gdy ten Kod, jak zrobię teraz -
pozwól mi iść do przodu i wklej go tutaj.
Zadzwonię do tego noswap.c.
I jak sama nazwa wskazuje, nie jest to będzie właściwy program.
Marka noswap. / Nie wymiany.
x oznacza 1, y oznacza 2, zamianę, zamienione.
x oznacza 1, y oznacza 2.
To jest z gruntu fałszywe, nawet choć wydaje się to doskonale
rozsądne do mnie.
I nie ma powodu, ale nie jesteśmy zamierza ujawnić powód jeszcze.
>> Na razie drugiej cliffhanger chciałem pozostawić Państwu to,
Ogłoszenie rodzaju na kupon kody.
Nasze innowacje w tym roku pod koniec dni wywołał numer nietrywialne
pytań, które było Nie jest naszym zamiarem.
Intencją tych kupon kody, przy czym, jeśli nie część problemu
ustawiony na początku, tym samym uzyskanie dodatkowych dni, było naprawdę pomóc wam pomóc
się rozpocząć na początku, sortowanie z przez incentivizing ciebie.
Pomaga nam w dystrybucji obciążenia na godziny pracy tak, aby lepiej
To coś w rodzaju win-win.
>> Niestety, myślę, że moje instrukcje nie były do ​​tej pory, bardzo jasne, więc
Wróciłem w ten weekend i aktualizowane spec większy, tekst odważniejsze do
wyjaśnić kul jak te.
I właśnie to powiedzieć bardziej ogólnie, przez domyślnych, zestawy zadań są spowodowane czwartek
w południe, na programie nauczania.
Jeśli zaczynasz wcześnie, kończąc część Problem ustawić się w środę o 12:00
PM, część, która dotyczy kuponu Kod, idea jest taka, że ​​można rozszerzyć
Twój termin P zestaw do piątku.
Oznacza to, że nieco off malutkiej części P ustawiony w stosunku do tego, co zazwyczaj jest
większy problem, a kupisz się dodatkowy dzień.
Ponownie, to dostaje się myśleć o zestaw problemem, dostaje do
godziny pracy wcześniej.
Ale problem kupon jest nadal konieczne, nawet jeśli nie przedstawia go.
>> Ale bardziej nieodparcie to.
(Scenicznym szeptem) I ci ludzie, pozostawiając Już to będzie żałował.
Jak są ludzie, na balkonie.
Przepraszam z góry do ludzi na balkon z powodów, które będą
wyczyścić za chwilę.
>> Więc mamy to szczęście, że jeden z Dawni towarzysze CS50 łeb na nauczanie
Firma o nazwie dropbox.com.
Mają bardzo hojnie podarowane kod kuponu tutaj to dużo miejsca,
która jest od góry Zwykłe 2 gigabajty.
Więc to, co myślałem, że robimy w tej sprawie Ostatnia uwaga jest zrobić trochę gratisów,
przy czym za chwilę, będziemy ujawniać Zwycięzca i kto ma kupon
kod, który następnie można przejść do ich strona www, wpisz ją i voila, uzyskać
dużo więcej miejsca Dropbox dla swojego Urządzenie i plików osobistych.
>> I pierwsza, którzy chcieliby wziąć udział na tym rysunku?
OK, teraz sprawia, że ​​jeszcze bardziej zabawne.
Osoba, która otrzymuje ten 25-gigabajt kupon - co jest o wiele
bardziej przekonujące niż późno dzień teraz, być może -
jest tym, który siedzi na szczycie siedzisko pod którym jest
że kupon.
Możesz teraz spojrzeć pod Twój siedzisko.
>> [PLAYBACK VIDEO]
>> -Raz, dwa, trzy.
>> [SCREAMING]
>> -Masz samochód!
Masz samochód!
>> DAVID MALAN: Zobaczymy Ci w środę.
>> -Masz samochód!
Masz samochód!
>> DAVID MALAN: ludzie balkon, chodź tu do przodu,
gdzie mamy dodatki.
>> -Każdy ma samochód!
Każdy ma samochód!
>> [END PLAYBACK VIDEO]
>> Narrator: Na następnym CS50 -
>> Głośnik 5: O mój Boże gosh gosh gosh jejku jejku jejku jejku jejku jejku -
>> [SZTUKI UKELELE]