>> [MUZYKI]
>> David J. MALAN: Jest CS50.
I to jest początek trzeciego tygodnia.
Mamy więc dużo ekscytujące rzeczy na pokrycie dziś.
Wiele możliwości Wolontariusze na scenie.
I w końcu, dzisiaj jest nie chodzi o kod w ogóle.
Ale tu chodzi o pomysły, a to o algorytmach,
i faktycznie przywraca niektóre Wnioski wyciągnięte z tygodnia zerowej,
gdzie przypomnieć, że wprowadził tę potworność.
I pożyczki inspiracji z tym, aby rozpocząć
rozwiązać coraz bardziej wyrafinowane Problemy algorytmicznie.
Ale najpierw kilka ogłoszeń.
Tak jeden, jeśli chcesz się przyłączyć Personel i koledzy CS50 jest w porze lunchu
w ten piątek, zarówno tutaj, jak iw Cambridge oraz w New Haven,
odwiedź kurs na stronę internetową, gdzie można znaleźć adresu URL.
Wykład w środę będzie Nie będzie tu Sanders.
To będzie tylko online, więc dostroić się na stronie internetowej CS50, w
czy tu, w Cambridge lub New Haven, jak również.
>> A potem problemu ustawić dwa jest już w Twoich rękach.
Jeśli nie masz jeszcze zanurkował w, pozwala mi zaoferować silnie sformułowane sugestię
, że zwłaszcza teraz, jak problem ustawia zaliczki,
naprawdę chcesz rozpocząć już teraz, jeśli nie babrać się nieco na weekend lub przed
kiedy po raz pierwszy wyjść na Piątki, bo będziesz
okaże się, że nie są one koniecznie coraz dłuższe i bardziej wymagające na
se.
Myślę, że przekonasz się, że w Ogólnie rzecz biorąc, mają tendencję do podejmowania grubsza
około samym czasie.
Ale to oczywiście zależy na ucznia, a to
zależy od sposobu myślenia z którym się do niego zbliżasz.
Ale zawsze, będziesz uruchomić przeciwko jakiejś ścianie,
i masz zamiar trafić jakiś błąd, a ty po prostu
nie będzie mógł się nad nim w pewnym momencie.
I to jest niezwykle cenne, aby móc odejść, wrócić następnego dnia,
udać się do godzin pracy biura, post CS50 Dyskutuj lub tym podobne, aby rzeczywiście uzyskać odblokowane.
Miejcie to na uwadze.
Począwszy najwcześniej, jak to możliwe jest najlepszą rzeczą, jaką możesz zrobić.
Tak tu, gdzie zaczęliśmy klasa, ponad w tygodniu zerowym.
I możemy się wolontariuszem tutaj, aby pomóc mi znaleźć mikrofony?
OK.
Wstał już.
Chodź na górę.
Domyślam się, że to się uda.
Jak masz na imię?
ALAN ESTRADA: Alan Estrada.
David J. MALAN: Alan Estrada.
Chodź na górę.
Miło cię poznać.
ALAN ESTRADA: Miło cię poznać.
David J. MALAN: I tu był z nami w tym tygodniu zerowym, oczywiście.
ALAN ESTRADA: byłem.
Byłem.
>> David J. MALAN: Więc można iść do przodu i znaleźć dla nas Mike Smith,
tak szybko, jak to możliwe?
Tak szybko, jak to tylko możliwe.
Dosłownie rozrywając problem w połowie, jak trzeba.
>> ALAN ESTRADA: Um.
David J. MALAN: Dosłownie łzawienie problem w połowie.
>> ALAN ESTRADA: Och.
Mm.
Bardzo dobrze.
>> David J. MALAN: OK.
Dobry.
Dziękuję.
ALAN ESTRADA: Bardzo dobry.
OK.
>> David J. MALAN: A więc teraz, już stopniała w dół
połowie wielkości tego problemu.
Teraz jesteśmy w dół do kwartału.
Czy zwracać uwagę na po której stronie jesteśmy utrzymanie?
>> [LAUGHING]
>> ALAN ESTRADA: Tak, ja think--
>> David J. MALAN: Co sekcja jesteśmy?
ALAN ESTRADA: Tłumiki, tak.
>> David J. MALAN: OK.
Ale Mike Smith jedzie być po Tłumiki.
Więc--
>> [LAUGHING]
>> W porządku.
ALAN ESTRADA: Gdzie szukamy?
David J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
David J. MALAN: Teraz jesteśmy w chirurgiczna.
Teraz lekarze.
Now--
>> ALAN ESTRADA: Let's- chodźmy z rzeczywistością.
Realne.
>> David J. MALAN: Biura.
OK.
Jeśli potrzebujesz rzeczywistym.
Teraz, w jaki sposób jest Mike Smith?
>> ALAN ESTRADA: ten sposób.
>> David J. MALAN: Którędy?
ALAN ESTRADA: Czekaj.
Prawo M jest--?
Zaczęliśmy with--
>> David J. MALAN: Tak.
Oni zostawili.
Masz rację.
>> ALAN ESTRADA: Tak.
>> David J. MALAN: Więc Mike tutaj.
ALAN ESTRADA: Co?
>> [LAUGHING]
>> Zły przykład, chłopaki.
Przepraszam.
David J. MALAN: To nauczy można skakać z krzesła.
>> ALAN ESTRADA: Och.
Och.
Mam cię.
Och.
To jest-- OK, mam ciebie.
Smith tutaj?
>> David J. MALAN: Smith, dziękuję.
Więc będę patrząc Smith?
>> ALAN ESTRADA: O, tak.
Nie nie nie.
O nie.
To jest moje.
>> David J. MALAN: Och, masz Smith.
OK.
>> ALAN ESTRADA: Tak, ale Smith tutaj.
Przepraszam chłopaki.
Myślałem Michael-- mamy szukaliśmy Michała.
Przepraszam.
>> David J. MALAN: Jest OK.
Dobra, teraz jesteśmy w Paccini and Sons.
>> ALAN ESTRADA: Paccini i synowie.
David J. MALAN: Tylko ty i ja w to.
OK.
Znajdź nas Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> David J. MALAN: Smith.
Jesteśmy w R na śmieci.
ALAN ESTRADA: Javascript.
Och.
To zajmie trochę czasu.
>> [LAUGHING]
David J. MALAN: Buty.
Jesteśmy w butach.
>> ALAN ESTRADA: Teraz jesteśmy gonna--
>> David J. MALAN: Nicea.
ALAN ESTRADA: Which--
[LAUGHING]
Och, to jest świetne.
[LAUGHING]
>> David J. MALAN: Jest OK.
>> ALAN ESTRADA: Och, to jest dobre.
Nie sądzę, że będę mają PSAT kumpli po tym.
David J. MALAN: Dobra.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
David J. MALAN: OK.
Warto więc oderwać to w połowie.
Jest ok.
To i tak kończy się źle, ponieważ Mike Smith nie będzie na żółtych stronach.
>> ALAN ESTRADA: Aw.
>> David J. MALAN: Nie, to jest OK.
Ale niech udawać, on jest na tej stronie.
Więc teraz, już stopniała problem dół z jednej strony, a okazało się, Mike Smith.
>> [Doping]
Ok dziękuję.
OK.
To było niezwykłe.
Ale to było jeszcze szybciej niż wyszukiwania liniowego,
w którym możemy rozpocząć się początku książki,
i ruszamy naszą drogę od lewej do prawej, w końcu szuka Mike Smith.
I tak, jeśli książka telefoniczna miał może z 1000 stron,
Może zajęłoby nas 10 lub tak strona łzy.
>> Ale może masz dźwignią dotknął założenie
Podczas tego wszystkiego, to znaczy że książka telefoniczna z góry było, co?
PUBLICZNOŚCI: Sortowanie.
David J. MALAN: To jest klasyfikowane.
Dobrze?
To sortowane alfabetycznie, więc że wszystkie z tych nazw i numerów
są klasyfikowane od A do danego Z, a alfabetycznie pomiędzy.
Ale dzisiaj, teraz zapytać pytanie, dobrze,
Jak Verizon lub telefon Firma dostać go w tym stanie?
>> Bo to jest jedna rzecz, aby wykorzystać to założenie, a zatem,
rozwiązać problem z Algorytm bardziej efektywnie.
Ale nigdy tak naprawdę zapytał w tygodniu zerowym, dobrze,
ile to kosztowało Verizon lub ktoś inny
aby dostać tę książkę telefoniczną w uporządkowanej kolejności?
>> Dobrze?
To nie ma znaczenia, czy patrząc Mike Smith
jest super szybki, jeśli to ma się do rok do sortowania stron początkowo.
Dobrze?
Równie dobrze można po prostu przesiać przez randomizowanym książce telefonicznej,
jeśli to będzie bardzo drogie, aby je rozwiązać.
Więc, jeśli możemy mieć inny wolontariusz.
Przyjrzyjmy się patrzeć tutaj w jak might-- przychodzimy na up-- jak
Może pójdziemy na temat sortowania tych.
>> A jeśli Jordan mógł rzeczywiście dołącz do nas tu na scenie.
Chodź na chwilę.
Jak masz na imię?
CAROLINE: Caroline.
David J. MALAN: Caroline, chodź na górę.
I będziesz dołączył przeze mnie i Jordanii tutaj.
Caroline, dziękuję.
W porządku.
Tak więc to, co mamy tutaj Caroline jest 26 niebieskie książki
że FAS używa do zarządzania niektóre egzaminy końcowe.
Są one coraz trudne do znalezienia, ale to, co zrobiliśmy z góry
jest to, że umieściliśmy czyjeś imię z przodu każdego z nich,
ale trzymałem to proste przez potem gasił pełne nazwy.
Więc chcemy umieścić osobę z nazwą L, D, J, B, całą drogę od A do Z,
ale są w przypadkowej kolejności.
I tak, jeśli będzie, mówi swojej drogę problemu jak ty
zrób to można iść do przodu i posortować je dla nas, od A do Z.
>> PUBLICZNOŚCI: OK, więc jest jak L, środkowy.
C zaczyna.
B. J przed L. B, P.
>> David J. MALAN: Trzymaj, że że na jedną sekundę.
W przeciwnym razie, to jest dopiero interesujące dla ciebie, mnie i Jordanii.
No to jedziemy.
PUBLICZNOŚCI: [niesłyszalne].
R.
David J. MALAN: OK.
Co ty robisz?
>> CAROLINE: M przychodzi po O.
>> David J. MALAN: OK.
>> CAROLINE: O.
David J. MALAN: O, dobrze.
>> CAROLINE: E.
>> David J. MALAN: E, F. Tak.
>> CAROLINE: T, U, V
>> David J. MALAN: V, T, U, V, więc Wygląda na to, że jesteś making-- dalej.
Wygląda na to, że robisz wielki stos tutaj,
i niby wielki stos tam.
Tak więc pierwsza połowa alfabetu, Druga połowa alfabetu.
OK.
Dobry.
Rodzaj podziału problemu na dwa.
M, N, X. Tak.
CAROLINE: K.
David J. MALAN: OK.
K. Więc rodzaj wyboru je jeden po drugim,
wprowadzenie go z lewej lub prawej, lub Z, dzieje się na podłodze.
OK.
>> CAROLINE: Z dzieje się na podłodze.
>> David J. MALAN: OK.
Tak dzieje się na podłodze.
Teraz możemy umieścić X.
>> CAROLINE: G.
David J. MALAN: będzie lewo G.
S będzie dobrze.
Wszystko w porządku, A będzie całą drogę w lewo.
>> CAROLINE: A, B, C, D.
>> David J. MALAN: Teraz dobrze.
Mamy A, B, C. W dzieje tam na dole.
Dobrze, T.
>> CAROLINE: H, I, J
David J. MALAN: H, I, J Dobra.
CAROLINE: W centrum, jestem gonna--
David J. MALAN: OK.
Więc teraz, będziemy rodzaju od połączyć te różne stosy.
Więc od A do C, to widzę, D, E i F i G i H oraz I. Nicea.
J, K. A potem, to stos jest do góry nogami, ale to jest OK.
Pewnie.
Możemy wyciąć niektóre zakątki.
OK.
A potem musimy W, X, Y, Z.
>> CAROLINE: Tak.
>> David J. MALAN: Excellent.
Więc wielkie dziękuję Caroline do sortowania tych.
>> [Doping]
>> Dziękuję.
Dziękuję Ci bardzo.
A teraz spójrzmy na chwilę jak Caroline chodził, czyniąc to,
i co dokładnie mamy byli w stanie to-- jak
udało się rozwiązać ten Problem, gdy byliśmy po prostu
podana cała masa przypadkowych wejść.
>> Cóż, wygląda na to, że był nieco systemu tam?
Dobrze.
Więc wcześniejszych listów w alfabecie, ona
było wprowadzenie na lewo, a później litery alfabetu,
ona wprowadzenie do prawa.
I jak tylko znalazła niektóre bliższe litery, ones
że go tuż obok siebie, ona umieścić te w porządku.
A więc my niby miał to małe stosy segregowanych wejść występujących.
>> A więc to jest zupełnie jak co większość z nas ludzi zrobi.
Chcemy rodzaj przesiać przez niego, a my rodzaju posiadają mechanizm.
Ale może to być trudne do napisania to w formule per se.
Czułem się trochę bardziej ekologiczne niż.
Zobaczmy więc, czy możemy teraz związany problem z mniejszą ilością wejść.
>> Zamiast 26, niech zrobić coś o wiele mniej
z tylko powiedzieć, siedem, za te drzwi, że tak powiem.
Czy istnieje tylko siedem numery?
A jeśli celem teraz w ręka jest znaleźć wartość,
Zobaczmy, jak skutecznie możemy za to zabrać.
I zobaczymy, czy możemy teraz zaczyna się stosować kilka liczb,
lub niektóre formuły, z którym do opisania efektywność naszej książki telefonicznej
Algorytm, nasz algorytm egzamin książka, i Bardziej ogólnie, wyszukiwania informacji.
>> Więc na to, pozwól mi iść do przodu, a na ekranie dotykowym tutaj,
umieścić na przeglądarkę internetową, która ma dokładnie te siedem drzwi.
A jeśli możemy dostać jeszcze jeden dobrowolnie chodź tutaj,
Mam umieścić te same drzwi tutaj.
Szybkie wolontariuszy.
>> Ten jedno- dema będą na szybsze i szybsze teraz.
Zejdź na dół.
Jak masz na imię?
TREVOR: Trevor.
>> David J. MALAN: Trevor?
Dobrze, Trevor, chodź na dół.
Więc Trevor zgłosił się na ochotnika, żeby zrobić podobny problem, ale taki, który jest
węższy zakres, i to się dzieje aby umożliwić nam spróbować sformalizować teraz
proces sortowania tych numerów.
>> Więc Trevor, miło cię poznać.
Więc tutaj jest tablicą, więc do mówić, listę siedmiu drzwi.
Śmiało i znaleźć nam numer 50.
A następnie po fakcie, powiedz nam jak znalazł.
Powinno być: wszystko w porządku.
Tak, to jest ten jeden tutaj?
O o.
OK.
Kliknąłeś tego.
Dobry.
>> I dobrze.
Teraz kliknięciu tego.
I pozwól mi dać mikrofon, tak, że masz go za chwilę.
Śmiało i kliknij obok, którzy zamierzają.
Tak dobrze.
TREVOR: Czy mogę unclick drzwi?
David J. MALAN: Nie, nie możesz usunąć zaznaczenie.
TREVOR: OK.
Ten.
David J. MALAN: Gdzie chcesz iść?
Który?
>> TREVOR: To jedno.
>> David J. MALAN: Nie
>> TREVOR: OK.
Ten.
>> David J. MALAN: Tak.
To było dobre.
W porządku.
Więc jaki był twój algorytm lub Procedura robi to, Trevor?
>> TREVOR: Właśnie przeszedł drzwi, aż znalazłem 50.
David J. MALAN: OK.
Doskonały algorytm.
Tak to jest w porządku.
Bo w rzeczywistości, jeśli ujawnię, co jest za tymi dwoma innymi drzwiami, co
Znajdziemy tutaj jest to, że mamy tylko wejście losowe.
Tak to było w rzeczywistości, jak dobre, jak można dostać.
I faktycznie, masz lepiej niż wyczerpująco przeszukując cały szereg,
bo byłoby naprawdę pecha jeśli trafił numer
50 w ostatniej drzwi.
Ale co, jeśli zamiast dał ci założenie.
Przypuśćmy, że jakby wszystkie drzwi te wokół,
tak, że masz numery klasyfikowane ten czas,
ale tym razem to faktycznie different-- ten czas,
to faktycznie posortowane dla Ciebie.
A teraz celem pod ręką jest trafienie numer 50.
>> TREVOR: OK.
>> David J. MALAN: Co Twój algorytm będzie?
>> TREVOR: Cóż, jeśli to klasyfikowane, to albo będzie
aby być: jeśli największym na największym, malejąco, to będzie pierwszy,
lub jeśli jest odwrotnie, to będzie ostatni.
Więc ja po prostu wybierz te drzwi, a a potem po prostu dotknij ostatnie drzwi.
David J. MALAN: Excellent.
W porządku.
Tak więc okazało się, że numer 50.
Więc jak tylko wiedział, były sortowane, my
były w stanie wykorzystać to założenie.
Tak więc są one zbyt podobne przykład książka telefoniczna.
Jak tylko masz, nawet z mały problem w ten sposób,
Twoje wejścia wstępnie posortowane, możemy rzeczywiście znaleźć wartość zapewne
bardziej efektywnie.
>> I nie powiedzieć, czy to było klasyfikowane małych do dużych lub dużych do małych,
i tak było bardzo rozsądne rozpocząć się na jednym końcu i drugi
faktycznie okaże się, że wartość docelową.
Więc dziękujemy Trevor również.
A ja propose-- ładnie wykonane.
Mamy trochę klip, w rzeczywistości, że jest jednym z naszych ulubionych momentów w CS50,
przy czym czasami te dema Nie bardzo idzie zgodnie z planem.
I rzeczywiście, w tej chwili, ja zatrzymał się w niewłaściwy interfejs
z którym do korzystania z ekranu dotykowego.
Więc to nie była moja wina.
>> Więc to będzie dla przyszłoroczny klip jako
dlaczego ja na moim ekranie było kliknięcie.
Ale rzućmy okiem na to, co się stało w zeszłym roku
z Jay, który przyszedł się, dużo jak Trevor tutaj, na ochotnika,
iw tym krótkim klipie, zobaczysz jak to samo demo nie dość
ujawnienia tych samych doświadczeń.
[ODTWARZANIE]
-Wszystkie Chcę, żebyś teraz zrobić, to znaleźć dla mnie, i dla nas,
Naprawdę, numer 50 krok po kroku.
>> -The Liczba 50?
>> -The Numer 50.
I można ujawnić, co jest Za każdym z tych drzwi
po prostu przez dotknięcie palcem.
Cholera.
>> [LAUGHING]
>> [Zakończyć odtwarzanie]
David J. MALAN: Tak, że poszło bardzo dobrze.
To były nieposortowane drzwi.
I Jay, oczywiście, znaleźć to wszystko zbyt szybko.
Trevor zrobił o wiele lepiej w kategoriach teachable chwili
że tak powiem, w tym roku w trwa dłużej, aby go znaleźć.
Oczywiście, to daliśmy Jay drugą szansę,
w którym możemy klasyfikowane drzwi, tak jak zrobiliśmy to dla Trevor,
i Trevor zrobił bardzo dobrze ten czas.
Ale Jay zrobił to w połowie tak szybko.
[ODTWARZANIE]
-The Celem jest teraz również znaleźć nam numer 50,
ale zrobić algorytmicznie, i Powiedz nam, jaki masz zamiar o tym.
>> -OK.
>> -A Jeśli go znaleźć, zachować ten film.
Jeśli nie znajdziesz, możesz go oddać.
>> -Człowiek.
>> Oh!
>> - [Niesłyszalne] OK.
Więc mam zamiar sprawdzić końce Pierwszy celu określenia, czy there's-- OH.
>> [APPLAUSE]
>> [Zakończyć odtwarzanie]
David J. MALAN: OK.
Więc sortowania drzwi wyraźnie prowadzi do większej wydajności.
I tak dwa razy szybciej to miałem na myśli nie.
I tak miał szczęście Jay zarówno razy.
I on też ma szczęście, że w ubiegłym roku, zamówiłem kilka płyt Blu-ray
faktycznie dać się.
Przykro mi tym roku, nie miało to samo, Trevor.
Ale jeszcze lepiej było kilka lat temu.
A niektórzy z was wiedzą o tym kolega, Sean, który gdy był w CS50,
została zakwestionowana z dokładną sam problem, choć w SD,
a szybko przekonasz się, z powrotem w dzień.
A przekonasz się, że nie tylko on nieco dłużej niż Jay,
trochę dłużej niż Trevor, był właściwie to wspaniała okazja
angażować się niemal wszyscy w Tłum a la Price is Right, zachęcanie
żeby znaleźć numer szukaliśmy.
Miejmy. rzucić okiem.
>> [ODTWARZANIE]
>> -OK.
Tak więc twoim zadaniem tutaj, Sean jest następujący.
Ukryłem się za nich Drzwi numer siedem.
Ale schowany w niektórych z tych drzwi jak również są inne liczby ujemne.
A twoim celem jest, że z tym górnym rzędzie cyfr
jak tylko tablicę, lub po prostu Sekwencja kawałków papieru
z numerami za nimi.
I twoim celem jest, tylko przy użyciu górę Tablica tu znaleźć mi numer siedem.
A my wtedy będziemy krytykować jak go o to robi.
-W porządku.
-Find Nam numer siedem, proszę.
Nie.
Pięć, 19, 13.
>> [LAUGHING]
>> To nie jest podchwytliwe pytanie.
Jeden.
>> [LAUGHING]
W tym momencie, Twój wynik nie jest bardzo dobre, więc równie dobrze można iść dalej.
Trzy.
>> [LAUGHING]
>> Iść.
Szczerze mówiąc, nie mogę pomóc, ale zastanawiam się, to, czego nawet nie myśląc o, SO-
>> [LAUGHING]
Tylko górny rząd, więc masz trzy lewo.
Więc znajdź mi siedem.
>> [LAUGHING]
17.
Siedem.
>> [APPLAUSE]
>> W porządku.
>> [Zakończyć odtwarzanie]
>> David J. MALAN: Więc mogliśmy oglądać je przez cały dzień.
Oczywiście, niektóre z tegoroczne pokazy być może
będzie teraz kończy się w przyszłym Tegoroczny wideo, jak również.
Więc teraz niech rzeczywiście skupić się na algorytmach
tu, i zobacz, czy nie możemy teraz zaczynają sformalizować
jak możemy go o uzyskanie nasze dane w takim stanie, że to jest klasyfikowane,
sposób, że ostatecznie możemy rzeczywiście szukaj go bardziej efektywnie.
I mimo, że mamy zamiar używać dość małych zbiorów danych,
jak my osiem numerów mam tu na pokładzie,
w rezultacie mogą stosować te same pomysły 1000 wejść, milion wejść,
4 mld wejścia, ponieważ algorytmy będą zasadniczo takie same.
>> I tak to jest nasz ostatni szansa dla wolontariuszy dzisiaj
ale chyba najbardziej zaangażowany jeden, dla których musimy ośmiu wolontariuszy
wymyślić i chodź z nami poprzez Proces sortowania, co wkrótce
być na tych muzyki tutaj stoi.
Zacznę tutaj.
>> Więc jeden w turquoise-- zielony to jest?
Czy popełnienie?
Dwa.
Zejdź na dół.
OK.
Trzy.
Cztery.
Niech me-- OK, pięć.
Jesteś jest nominowany przez znajomego.
Sześć, siedem, osiem.
Chodź na górę.
W porządku.
Dziękuję bardzo.
Chodź na górę.
>> W porządku.
Więc co mamy here-- i to jest jednym z bardziej kłopotliwych tych,
od tego, że konieczna będzie humor mi na tylko trochę czasu.
Powinien być numerem jeden.
Jak masz na imię?
>> ANNAN: Annan.
>> David J. MALAN: Annan.
David.
Jak masz na imię?
>> Joseph Joseph.
>> David J. MALAN: Józef, jesteś numer dwa.
>> SERENA: Serena, numer trzy.
Stefan, numer cztery.
CYNTHIA: Cynthia.
David J. MALAN: Cynthia, numer pięć.
[Niesłyszalne]
David J. MALAN: [niesłyszalne].
David, numer sześć.
MATT: Matt.
David J. MALAN: Matta numer siedem.
I?
>> WAVERLY: Waverly.
>> David J. MALAN: Waverly, numer osiem.
W porządku.
Jeśli could-- okrzyki.
Jeśli was wszystkich, jak twój Pierwszym wyzwaniem, nie
osiem stoiska muzyczne tutaj twarzą do publiczności.
Jeśli można umieścić swoje numery te pulpity w taki sposób,
oni się tej linii z same numery na płycie.
Więc upewnij się wyglądać przez oddanie numery na tych muzyki
stoi tutaj.
Doskonały do ​​tej pory.
>> Doskonałe.
OK.
Więc teraz mamy zamiar zapytać pytanie w kilka różnych sposobów.
Jak możemy go o sortowaniu ci ludzie tutaj?
Ponieważ mieliśmy kilka podejść wcześniej, w którym byliśmy
rodzaju co dwa różne wiadra.
A potem były na ogół składając rzeczy razem.
Jak tylko zobaczyłem dwa numery że należeli razem,
możemy je połączyć.
Dwa listy, które należą razem.
>> Ale zobaczymy, czy możemy Nie można sformalizować to,
tak, że w końcu mają niektóre pseudo-kod będzie,
z którym można rozwiązać te problemy.
Więc teraz szukam się na te numery tutaj.
I widzę całą masę błędów.
Docelowo chcę jeden na w lewo i osiem po prawej stronie.
>> I tak patrzę na te dwa, cztery i dwa.
A w czym problem, oczywiście?
Tak.
Więc.
Dwa oczywiście jest przed cztery, więc wiesz co?
Pozwól mi wziąć chciwy podejście, jeśli będzie, podobnie jak problem,
ustawić jedno-, czy pamiętacie z Standard Edition problemu Set One,
gdzie tylko lokalnie rozwiązać problem to właśnie tu, w moich oczach
i zobaczyć, dokąd prowadzi mnie.
>> OK.
Więc dwa i cztery, pozwól mi odejść dalej i po prostu zamienić ci dwa.
Jeśli można fizycznie przenieść Sami i twój papier,
Wydaje mi się zdobyć listy w lepszym stanie.
>> Teraz są one dobre.
Mam zamiar przejść, cztery i sześć, wygląda dobrze.
To nie problem.
Sześć i osiem, OK.
Osiem i inny problem.
Bo to, co prawda, o ósmej i jeden?
Jedna jest przed ośmiu, i tak to, co powinniśmy zrobić?
Miejmy zamienić te dwa.
Jeden i osiem.
A teraz, mam zamiar iść dalej.
Zamierzam zachować patrząc w przyszłość.
I zobaczmy, co się stanie.
Osiem i trzy, z Oczywiście, nie w porządku.
Miejmy swapa.
Osiem i siedem, oczywiście.
Nieczynny.
Miejmy swapa.
Osiem i pięć, oczywiście, niech wymiany.
W porządku.
Lista jest posortowana.
tak?
>> OK, oczywiście nie.
Ale to jest trochę lepiej, prawda?
Ponieważ informacja, co się stało.
Za każdym razem przeprowadziliśmy swap mniejszy Numer rodzaj perkolacji w ten sposób,
i większa liczba perkolacji w ten sposób, albo będziesz
rozpocząć powiedzenie przepuszcza do lewo lub w postaci pęcherzyków w prawo.
>> Teraz, to nie wystarczy, bo w najlepszym wiele może
zostały przeniesione jedno miejsce do przodu, lub co gorsza,
liczba może mieć przeniósł się jedno miejsce dalej.
Więc wiesz co, tego rodzaju od pracował bardzo dobrze do tej pory.
Pozwól mi po prostu spróbować ponownie.
Dwa i cztery, są OK.
Cztery i sześć, są OK.
Sześć i jeden, w porządku.
Warto więc zamienić cię dwa.
A teraz, zauważysz problem na zaczyna znów się trochę lepiej.
Sześć i trzy, w porządku.
Miejmy zamienić cię dwa.
Sześć i siedem, jesteś dobry.
Siedem i pięć, oczywiście, nie w porządku.
Siedem i osiem, w porządku.
A teraz, może muszę zrobić jeszcze kilka razy.
A w rzeczywistości, myśleć za siebie być może, ile razy maksymalnie
Mogę chodzić tam iz powrotem?
>> Wrócimy do tego.
Więc dwa i cztery są nadal OK.
Cztery i jeden, nope.
Tak, niech swapa.
I znowu zauważyć wizualnie z nich jest rodzaj bulgotanie
po lewej stronie, gdzie powinien być.
Cztery i trzy wymiany.
Cztery i sześć.
Sześć i pięć wymiany.
Sześć i siedem.
Siedem i osiem są dobre.
>> Dobry.
Dostajemy nawet lepiej.
Więc zobaczymy.
Teraz mamy dwa do jednego.
Oczywiście, zamienić.
Dwa i trzy, trzy i cztery, cztery i pięć, sześć i siedem, siedem i osiem.
Dobry.
I wiesz co?
Bo ja się nie jedną zmianę, pozwól mi zrobić jedną testow.
Pozwól mi przejść całą drogę powrót do początku.
OK.
Jeden, two-- yup, widzisz?
Coś było nie tak.
Trzy, cztery, pięć, sześć, siedem, osiem.
I w tym ostatnim przejściu, są komfortowe z moim teraz
twierdząc, że jest posortowana?
OK.
Wizualnie jest to absolutnie prawdziwe.
Ale funkcjonalnie, co czy też po prostu się stało
w tym ostatnim przejściu, która pozwala aby potwierdzić, że ta lista jest rzeczywiście
klasyfikowane?
>> Co mam zrobić, czy nie zrobić tego ostatniego przepustkę?
PUBLICZNOŚCI: Nie było żadnych zmian.
David J. MALAN: Słucham?
PUBLICZNOŚCI: Nie było żadnych zmian.
David J. MALAN: Nie było żadnych zmian.
Więc byłoby głupie z mojej strony zrobić tego samego algorytmu ponownie
gdybym nie dokonywała zmienia się po raz pierwszy.
A państwo nie zmienił.
Na pewno nie zamierzam zrobić Wszelkie zmiany po raz drugi.
I tak, to teraz jest bezpieczny powiedzieć, lista jest sortowana.
>> I rzeczywiście, to jest teraz coś, czego będziesz ogólnie
rozmowa sortowanie bąbelkowe, przy czym parami, ponownie poprawić błędy,
i znowu, i znowu, i ci utrzymać się tam iz powrotem,
oraz w przód iw tył, aż do ciebie aby nie takie swapy, w którym momencie
można mieć pewność, tak, zakończeniu mocowania wszystkich błędów.
Miejmy zresetować i spróbować innego podejścia.
Jeśli wam się wrócić do kolejność byłeś przed chwilą,
który wyglądał jak ten.
Teraz weźmy zbliżyć się trochę jak książki do egzaminu,
w którym byliśmy stale wybierając literę alfabetu
że niby chciał do czynienia z następnym.
Może to była duża litera, jak A, lub niskim litery Z.
>> Tak więc każdy z powrotem w tej kolejności.
A teraz pozwól mi to zrobić.
Zobaczmy, wiem, że mam tutaj osiem numerów.
Mam zamiar iść do przodu i po prostu świadomie wybrać
najmniejszych elementów.
Dobrze?
To wydaje się zbyt intuicyjne.
Dlaczego nie mogę znaleźć najmniejszą Element, umieścić go tam, gdzie należy,
następnie dostać następną najmniejszy element, umieścić że tam, gdzie należy, i po prostu powtórzyć.
>> Ponieważ intuicyjnie, który powinien działać też.
Tak więc cztery, to jest dość mała liczba.
Idę sobie przypomnieć, gdzie to jest.
Poczekaj minutkę.
Nimi jest mniejszy.
Chciałbym teraz przypomnieć, gdzie dwa jest, i zapomnieć o cztery.
Zajmiemy się tym później.
Sześć, nie jestem zainteresowany.
Osiem, nie jestem zainteresowany.
Jednym z nich jest moja nowa mała liczba.
Więc będę pamiętał, gdzie się jest.
Trzy, nie interesuje.
Siedem, nie interesuje.
Pięć, nie interesuje.
>> Więc nie spadając scena w tym roku,
Mam zamiar chwycić liczby jedno- a co jeszcze było na imię?
>> ANNAN: Annan.
>> David J. MALAN: Annan.
I jeśli można dołączyć do mnie na początek listy
postawmy cię tam, gdzie twoje miejsce.
Unfortunately-- jak masz na imię?
>> STEFAN: Stefan.
>> David J. MALAN: Stefan jest w drodze.
Więc zanim Stefan rozwiązuje ten problem Problem, co powinniśmy zrobić?
Co robimy ze Stefanem?
>> PUBLICZNOŚCI: [niesłyszalne].
David J. MALAN: OK.
Więc możemy to zrobić.
Mogliśmy jakby się Stefan i jego cztery, i po prostu umieścić ją w zmiennej
i przytrzymaj go przez jakiś czas,
a tym samym pokoju na numer jeden.
I to nie jest źle.
Mogę zasugerować, dlaczego nie po prostu umieścić tutaj Stefan?
Dlaczego może to naruszyć jeden pomysłów zaczęliśmy
mówi o ostatnim czasie, w zeszłym tygodniu?
Tak?
>> PUBLICZNOŚCI: [niesłyszalne].
>> David J. MALAN: Nie ma indeksu dla niego.
Jeśli myślisz o tym, rzeczywiście, jako Tablica ta jest jak negatywny,
więc nie ma pamięci w rzeczywistości tu, czy to jest rzeczywiście tablicą,
jak to oświadczył w ubiegłym tygodniu w wykładzie.
Tak więc nie powinniśmy tego robić.
Możemy go przechowywać w zmiennej.
>> Albo wiesz co?
Słyszałem ktoś inny go sugerują.
Co jeszcze możemy zrobić ze Stefanem?
Dlaczego nie możemy po prostu wyrzucić go i umieścić go na których numer jeden był.
Więc jeśli chcesz iść tam.
I rzeczywiście, że jest to całkiem dobre rozwiązanie.
Teraz z jednej strony, mam rodzaj Made problem gorzej.
Cztery jest teraz dalej z którego powinno być.
Powinien on być w kierunku tej połowy.
>> Ale wiesz co?
To mogło być pecha.
Może numer osiem było.
I tak, być może będzie zdobyć szczęście,
i pchnął osiem bliżej końca.
Tak więc na koniec dnia to niby wszystkie średnie out.
Nie musimy się martwić o cztery.
Wszystko zależy mi teraz jest wybraniu najmniejszy element.
>> A teraz, co mam zamiar zrobić, to zapomnieć o numer jeden
na stałe, ponieważ wiem, że Lista za mną jest teraz posortowana.
Więc moja lista była wcześniej rozmiar osiem.
Teraz to od wielkości siedem.
Więc mój problem jest coraz mniejsze, chociaż liniowo.
Więc teraz, mam zamiar wybrać prąd najmniejszy element, dwa.
Sześć, osiem, cztery, trzy, siedem, pięć.
To był najmniejszy element.
Więc co mam zamiar zrobić with-- co znowu masz na imię?
>> Joseph Joseph.
>> David J. MALAN: Józef?
Mamy zamiar opuścić Józefa w miejscu.
Teraz mam zamiar udawać że ci faceci are-- dobrze,
Wiem, że te dwa są już klasyfikowane.
Skupmy się teraz na Pozostała część listy.
Sześć jest obecny najmniejsza.
Osiem jest większy.
Cztery jest teraz obecny najmniejsza.
Trzy jest teraz obecny najmniejsza.
A więc teraz, mam zamiar wybrać trzy, którzy jest-- jak masz na imię jeszcze raz?
SERENA: Serena.
David J. MALAN: Serena, jeśli można chwycić liczby i zamianę with--
Kalsang: Kalsang.
David J. MALAN: Kalsang.
Wracaj, a my jesteśmy zamiar zamienić te dwa.
A teraz postawmy to na autopilota.
Mam zamiar iść i pozostawić do was Aby wybrać następny najmniejsze elementy.
Dun, dun, dun, dun.
Numer cztery, co należy zrobić?
Doskonałe.
Teraz mam zamiar dokonać innego przepustkę.
Dun, dun, dun, dun.
Widzę pięć jest następna najmniejsza.
Teraz mam zamiar podjąć kolejną przepustkę.
Dun, dun, dun, dun.
Sześć jest najmniejsza.
Dobry.
Siedem jest najmniejsza.
Bez zmiany.
Osiem jest najmniejsza.
Gotowe.
>> Więc co my właśnie zrobić poprzez iteracyjne wybranie jednego elementu po drugim
jest zaimplementować coś, że jesteśmy zamierza sformalizować jak wybór rodzaju.
I to jest być może nawet łatwiejsze do wyjaśnienia,
na tym, że dosłownie wszystko co chcesz zrobić, to utrzymać
tam iz powrotem po liście wybranie, następny najmniejszy element,
dopóki nie skończysz.
>> Więc jest to jeszcze prostsze, być może intuicyjnie, niż w ubiegłym.
Spróbujmy jeden ostatni.
Jeśli moglibyście sobie zresetować w następujących pozycjach
po raz ostatni, zobaczmy, czy nie możemy teraz sformalizować jedno inne podejście.
W rzeczywistości, by ktoś tam Proponujemy
jak inaczej moglibyśmy za to zabrać?
Bez rzucając się słowa-wytrychy lub rodzaju odpowiedzi, które są już znane,
tylko intuicyjnie, co możemy zrobić?
>> PUBLICZNOŚCI: [niesłyszalne].
David J. MALAN: Tak.
Więc jest jakaś wielka intuicja nie.
Dobre rzeczy wydają się zdarzyć tak daleko w informatyce, gdy dzielimy
i podbić problemu podzielenie go na pół i pół na pół.
I tak sądzimy, może zacząć to robić.
A w rzeczywistości, że będzie, będziemy zobacz, jeden z naszych najlepszych rozwiązań jeszcze.
Ale wróćmy do tego niebawem.
W rzeczywistości, mamy zamiar zrobić że nieco później w tym tygodniu.
Co jeszcze możemy zrobić, aby rozwiązać ten problem?
Więc wszyscy tu jest Kolejność pozornie przypadkowe.
Wiesz co?
Zamiast iść tam iz powrotem, tam iz powrotem, tam iz powrotem
za każdym razem, to czuje się jak Robię dużo chodzenia.
Dlaczego nie mogę po prostu zaczynają się początek listy
i po prostu umieścić cztery, gdzie należy?
Więc pozwól mi założyć, na chwilę, że moja lista jest tylko ten pierwszy element.
Czy cztery klasyfikowane w tej chwili w czasie, jeśli wszystko zależy mi na to wszystko, co tutaj?
Jest to rodzaj trywialnie prawdziwe, prawda?
Podobnie jak listy zawierającej jeden numer i że numer cztery jest oczywiście klasyfikowane.
>> Więc pozwól mi tylko zastrzec, że ta lista jest posortowana.
Ale teraz mam resztę tej listy.
Więc teraz, spotykam dwa.
Gdzie dwóch oczywiście należą w odniesieniu do czterech?
Przed czterech.
Więc co można zrobić tutaj?
Jeszcze raz, jak masz na imię?
>> Joseph Joseph.
>> David J. MALAN: Józef, jeśli można cofnąć
na chwilę ze swoim numerem.
A teraz to, co powinno Stefan zrobić tutaj?
Miejmy przesunąć Stefan tutaj.
A teraz, niech Józef tu przyjść.
A teraz pozwól mi twierdzić, że wszystko tu jest posortowana.
Tak więc, podobny wynik, lecz zasadniczo różne podejścia.
I nawet nie spojrzał, co tam jest.
Ja po prostu zachować przy elementy jak są one przekazane do mnie,
i radzić sobie z nimi.
>> Więc teraz, widzę numer sześć.
Gdzie jest numer sześć należą?
Mamy dwa, cztery, sześć.
Dokładnie tam, gdzie ona jest teraz.
Więc zostawmy to w spokoju, a teraz twierdzą, że części listy
jest teraz posortowana.
I tak, to czuje się całkowicie różni się tym, że jestem po prostu
poruszanie się po liście tutaj liniowo, a ja nigdy nie podwaja się.
Tak.
W porządku.
Więc osiem, gdzie należysz?
Dokładnie tutaj.
Doskonały.
Więc teraz, jeden.
O o.
To czuje się jak to jest będzie drogie.
Teraz w poprzednim algorytmu Po prostu zamieniłem ludzi.
Więc mogę umieścić go przez całą drogę na początek, ale potem przeniósł Józefa.
Ale jeśli przeniosę Józefa teraz co dzieje się źle?
>> Teraz mam rodzaju undone-- mam podjęta jeden krok do przodu, a następnie
jeden krok wstecz, bo teraz Joseph byłoby w porządku.
Więc zróbmy to.
Jeśli można wziąć numer jeden i cofnąć się na chwilę.
Jak możemy put-- co znowu masz na imię?
>> ANNAN: Annan.
>> David J. MALAN: Annan w miejscu?
Co musi się zdarzyć w odniesieniu do dwóch, czterech, sześciu, do ośmiu?
Wszyscy oni muszą się zmieniać.
Więc jeśli ośmiu chciałby przesunąć , potem sześć, potem cztery, potem dwa.
A następnie Annan, gdybyś lubię tu przychodzić, dobra.
Ale tutaj mamy tylko rodzaj zapłacił cenę
w innym momencie w algorytmie.
Podczas gdy ostatni raz z wyboru sortowanie, a nawet sortowanie bąbelkowe,
Idę z powrotem i powrotem, tam iz powrotem,
który jest na pewno dodanie czas-mądry, i dosłownie krok po kroku.
>> Sortowanie przez wstawianie, na początku rzut oka, wygląda to
bardzo inteligentne, w które jestem co powoli, przyrostowe postępy,
ale ja nie zamierzam tego tam iz powrotem.
Ale jeśli ktoś jest rzeczywiście z zamówienia, zawiadomienia
wszystkie prace po prostu musiałem to zrobić.
Musiałem przenieść połowę listy wystarczy, aby zrobić miejsce numer jeden.
Więc to jest ta sama ilość pracy do tej pory go
czuje, tylko inny rodzaj pracy.
>> Kontynuujmy.
Więc teraz wiemy, że każdy od jednego do ośmiu są klasyfikowane.
Tutaj, mam numer trzy.
Jeśli chcesz, aby podnieść numer trzy, krok wstecz jeden.
I co wy trzeba zrobić?
Tak.
Tak, że jest jeszcze jeden, dwa, trzy kroki.
Trzy jednostki czasu, że po prostu kosztować ja, tak, że trzy mogą zmieścić.
Wreszcie, siedem.
>> Idziemy do przodu i mieć Ci zrobić krok do tyłu.
To będzie nas kosztować tylko jedna jednostka czasu, ale to jest OK.
A teraz, pięć, dzieje się być trochę droższe.
Jeśli chcesz, aby cofnąć.
Musimy przenieść osiem, siedem i sześć.
A potem wszyscy są teraz sortowane.
Tak wielka ręka tutaj naszych wolontariuszy.
Dziękuję bardzo.
>> [APPLAUSE]
>> Dziękuję Wam wszystkim.
Dziękuję Wam wszystkim.
Zobaczmy teraz, jak kosztowne wszystko to było.
Rozważmy być może Najprostszy z nich, sortowanie bąbelkowe.
I mówię najprostszy, tylko dlatego, można rozwiązać je łapczywie po prostu
naprawić parami problem tutaj.
Fix parami problemu tu znowu i znowu
i znów, powtarzając aż razy, ile faktycznie potrzeba.
>> Tak więc okazuje się, że z bańki rodzaju, dobrze,
ile kroków muszę wziąć na pierwszy przebieg tego algorytmu?
Mógłbym take-- niech see-- jeden, dwa, trzy, cztery, pięć, sześć, siedem.
I nie ma osiem elementów tutaj.
Tak to jest jak n minus 1 kroków się od początku listy
na koniec listy.
>> Ale z wyboru rodzaju, przypominam sobie, że jestem ciągle liczbę elementów
i znowu to najmniejszy, Kładę go na miejscu,
ale nie jestem patrząc za mnie.
Więc myślę, że to trochę bardziej jasne to, że po raz pierwszy, to może
wziąć wszystko n minus 1 kroki znaleźć najmniejszy element.
Następnie umieścić je w miejscu, a ja eksmisji, kto był tu wcześniej.
>> Ale wtedy nie trzeba zachować się w tym elemencie,
bo wiem, że to Już najmniejsze.
Więc teraz, mogę patrzeć na to siedem elementy, następnie sześć elementów,
następnie pięć elementów, a następnie cztery elementy.
I tak Matematycznie, jeżeli n jest liczba elementów lub liczb
że zaczęliśmy, można sobie wyobrazić, który jest taki sam jak n minus 1,
oraz n minus 2 stopnie, oraz n minus 3 stopnie,
+ N minus 4 stopnie, wszystko dół do jednego kroku.
A ja jestem na mojej ostatniej osoby.
>> A jeśli przypomnieć, że wiele z książek i Statystyki książek matematycznych
mają te wzory na twarda tyłu lub z przodu z nich,
Okazuje się, że tej serii można wyrazić prościej
jak n razy n minus 1 na 2.
I to jest w porządku, jeśli nie jest to na czele swojego umysłu.
Ale to jest rzeczywiście prawda.
To tylko prostszy sposób pisania.
A jeśli myślisz z powrotem do szkoły podstawowej,
po prostu zacząć pomnożenie rzeczy z, to oczywiście,
jest po prostu n do kwadratu minus n dzieli się przez 2.
Wszystko robiłem to poszerzyć tam wyrażenia.
A więc niech to przepisać to trochę inaczej.
To się n do kwadratu podzielić przez 2 minus n / 2.
>> Więc jeszcze raz, jestem po prostu rodzaj stosowania niektóre zasady nie arytmetyczne.
Ale zauważ, że teraz największym termin w tej wypowiedzi, że tak powiem,
jest to, że n kwadratu.
Więc tak, jest to n do kwadratu podzielić przez 2, minus n / 2.
>> Generalnie jednak, jeśli n jest będzie duża wartość,
Zamierzam twierdzą, że n do kwadratu będzie dominującym czynnikiem.
To jest po prostu będzie większy współpracownikiem
liczby etapów niż n / 2.
Więc co mam przez to na myśli?
Spróbujmy prosty przykład, nawet choć matematyka staje się trochę duży.
>> Więc załóżmy, że mieliśmy 1 mln ludzi na scenie, lub 1 milion rzeczy
że chcemy rozwiązać.
Miejmy podłączyć milion w dokładnie tym wzorem
aby zobaczyć, ile kroków potrzeba łącznie sortowanie milion elementów za pomocą powiedzmy,
Wybór rodzaju.
>> Więc my mamy ten sam wzór jak poprzednio.
Chciałbym podłączyć miliona, tak aby uzyskać milion kwadratu podzielić przez 2,
minus milion podzielić przez 2.
Jeśli to zrobić matematyki z góry tutaj mamy 500 miliardów
minus 500 tysięcy, które daje nam 499999500000,
co jest cholernie duża.
>> W rzeczywistości, jeśli porównać teraz 499 miliardów 999 milionów
500000 przeciwko naszej pierwotnej wartości, 500 miliardów, to tak cholernie blisko.
Dobrze? n do kwadratu podzielić przez 2 daje us-- czy raczej n do kwadratu podzielić przez 2
dał nam 500 miliardów.
To cholernie blisko do 499,999,500,000,
to znaczy, odejmując 500.000 lub, bardziej ogólnie, odejmując
n do kwadratu, nie naprawdę wielkiego.
N do kwadratu sprawia, że ​​te numery rosną bardzo szybko.
>> Obecnie, to jest tylko o tyle istotne, jak my, jako informatycy,
nie są na ogół dzieje się tak przejmujesz o niuanse tych wzorach
i co dokładnie precyzyjne odpowiedzi są.
Dbamy tylko, że wiesz, co?
Na koniec dnia, to wzór jest rzędu n kwadratu.
>> Tak, jesteśmy podzielenie przez 2 tam.
Tak, jesteśmy odjęcie od n minus 2.
A na koniec dnia, termin które naprawdę nas boli i kosztuje nas
dużo schodów jest to, że kwadrat termin.
A więc to, co informatyk będzie na ogół nie
jest ignorowanie wszystkich tych, mniejsze terminy zamówień,
i po prostu patrzeć na tego, który przyczynia się najbardziej do kosztów.
>> I to jest miłe, bo możemy teraz rozmawiać w znacznie większej ogólności
o algorytmach i można je porównać.
A fakt, że jestem Korzystając z tej O jest celowe.
Kiedy mówię, że na zlecenie o, jestem specjalnie
odnoszące się do czegoś zwane duże O. i Big O
jest zapis, że komputer naukowiec używa do opisania
górną granicę na coś.
>> Jeśli więc powiedzieć, że algorytm jest w dużym O n do kwadratu,
jak zaproponowałem tylko Chwilę temu, że środki
że w zakresie jego biegania Czas i jego skuteczność,
to ma na celu n do kwadratu kroki.
Może więcej, może mniej.
Ale to na kolejność n do kwadratu.
I to jest górna granica.
To nie będzie bardziej bolesne niż to.
To nie będzie n pokrojone w kostkę, lub 2 do n, czy coś znacznie większego.
Jest to górna granica na cokolwiek to koszt jest.
Tak więc biorąc pod uwagę, że, powiedzmy, rozważyć tylko kilka przykładów.
I to jest właśnie lista skończona Czasy bardzo popularne uruchomione
dla algorytmów, które jest przeznaczone do ilustracją niektórych sprawach, przez które
widziałem już.
>> Tak na przykład, w przypadku Wybór rodzaju, co mi twierdząc tutaj
jest prowadzenie tego wyboru Sortuj w Czas jest rzędu n do kwadratu.
W najgorszym przypadku, będę mieć cała masa liczb losowych tutaj.
I jak widzieliśmy matematycznie, gdybym zachować spaceru
poprzez liście, poprzez lista, wybierając następna najmniejsza
Element ponownie i ponownie, jeśli I faktycznie spisać wszystkie kroki
Zabieram się zaproponowałem formulaically wcześniej, to na porządku n kwadratu
kroki, które biorę.
>> I okazuje się, że bańka sortowanie i Sortowanie przez wstawianie
są tak powolne, w najgorszym przypadku.
Zastanów się, na przykład, Sortowanie przez wstawianie, bardzo ostatnio algorytm którymi mieliśmy do czynienia,
który miał nam spojrzeć na elemencie, a następnie wstawić go tam, gdzie należy.
A potem spojrzał na następny element, i wstawia go tam, gdzie należy.
>> Więc rozważyć najlepszy możliwy scenariusz.
Załóżmy, że ochotnicy miałem linii dosłownie tak, jeden do osiem,
już klasyfikowane.
Ile kroków jest Sortowanie przez wstawianie zajmie się rozwiązać osiem osób,
jeżeli dotrą na scenie patrząc w ten sposób?
>> Osiem osób już klasyfikowane.
I używam Sortowanie przez wstawianie.
To ostatni z algorytmów.
No cóż, reaktywują naprawdę szybko.
Więc jeśli zacznę tutaj, widzę jeden.
Gdzie jeden należą?
Należy tutaj.
Widzę dwa.
Gdzie dwóch należą?
Dokładnie tutaj.
Widzę trzy.
Skąd trzy należą?
Dokładnie tutaj.
>> Widzę cztery.
Dokładnie tutaj.
Pięć, sześć, siedem, osiem.
Nie ma powodu, aby powtarzać.
I tak, to jak wiele kroków jest to, że chodzi o n?
To rzędu n Kroki, prawda? n minus 1.
Ale wziąłem numer liniowy kroków, a teraz mam zrobić.
Więc to najlepszy przypadek, choć.
A co w najgorszym przypadku?
Co osiem były tam, siedem były tam,
i jeden i dwa były tutaj, więc że lista była naprawdę odwrócić?
>> Cóż, co dzieje się w rzeczywistości Jeśli jest to liczba?
I zrobimy tylko kilka przykładów.
Co zrobić, jeśli rzeczywiście numer osiem jest tutaj, a number-- okrzyki.
Więc co, jeśli rzeczywiście liczba osiem jest aż tutaj,
i używam Sortowanie przez wstawianie?
>> OK.
Twierdzę, w tej chwili jest to na miejscu.
Ale teraz, seven-- skąd siedem przejść?
Oczywiście, idzie tutaj.
Więc muszę przenieść osiem nad jednym miejscu.
Teraz sześć, tam gdzie to idzie?
No, dobrze.
Teraz muszę przenieść osiem nad miejsce, a siedem na miejscu,
a potem rzuć się sześć.
>> Tak więc po raz pierwszy, to koszt mnie jeden krok, aby naprawić rzeczy,
to kosztowało mnie dwa kroki, aby naprawić rzeczy.
Ile kroków jest to zajmie naprawić
Atrakcje umieścić pięć we właściwym miejscu?
Trzy.
Bo teraz muszę przenieść jeden, dwa, trzy.
Ile kroków jest to zajmie umieścić cztery w odpowiednim miejscu?
4 plus 5 plus 6, oraz 7.
>> A więc jest to matematycznie identyczne co opisano dla wyboru rodzaju.
Mamy tę serię że po prostu rośnie.
1 plus 2 plus 3 oraz 4, lub odwrotnie, 7 oraz 6
oraz 5 oraz 4 dodaje się na dzisiejszym cele do rzędu n do kwadratu.
>> Więc pozwól mi przewidują też, że Sortowanie bąbelkowe jest również w n do kwadratu.
Ponieważ z bańki rodzaju, każdego razem przejść przez liście,
Biorę z grubsza, jak wiele kroków?
Za każdym razem, dosłownie spacerem od tam istnieje?
Około n kroków.
Ale ile razy mogę trzeba przejść przez liście?
>> No, mniej więcej n czas.
Może n minus 1, ale mniej więcej n razy.
Cóż, to dlaczego?
Cóż, z bańki rodzaju, jeśli zaczynamy sortowanie bąbelkowe,
z listy w najgorszy z możliwych Sytuacja, która ponownie jest zupełnie
do tyłu, co się wydarzy?
I przejść przez liście, a liczba jeden należy całą drogę tam.
>> Ale z bańki rodzaju, jak daleko ma jeden przenieść na mojej pierwszego przejścia przez liście?
Ile miejsc ma on się bliżej prawidłowej kolejności?
Tylko jeden.
Tak więc, jeśli rodzaj powód, przez to, za każdym razem przez ten algorytm,
Biorąc około n kroków Dawida.
Ale ilu przechodzi poprzez lista jest to
zamiar wziąć na jeden z bańki w lewo, gdzie należy?
>> Musi poruszać się jak, n spacji w ten sposób.
Więc po prostu zrobić sortowanie listy, Muszę chodzić tam iz powrotem n razy.
I za każdym razem, jestem patrząc na n elementów.
Więc co zrobić n n razy na kolejność n do kwadratu.
>> Teraz zobaczymy, w niektórych z szorty, które
są osadzone w kolejnym problemem CS50 jest ustawić, innego podejścia w nich,
ale teraz, po prostu rozważyć innym razem z systemem,
zwłaszcza jeśli ci się sortujących trochę czasu, by zatopić się w.
Co to jest algorytm już widzieliśmy że bierze na zlecenie n krokach?
>> Co należy wziąć numer liniowy kroków, które widzieliśmy do tej pory?
Co to?
Wyszukiwanie katalogu telefonów.
Pierwszy algorytm.
Dobrze?
Gdzie jesteśmy liniowo szukając Mike Smith?
W rzeczy samej.
Od tygodnia zera, kiedy zacząłem obracając jedną stronę na raz,
i nawet powiedział, że to był rodzaj algorytmu liniowego uczucie,
i mieliśmy ten obraz na Płyta z prostej czerwonej linii
i prosto żółty linia, to były rzeczywiście
Algorytmy, które są w dużym O n.
>> Bo znaleźć Mike Smith w telefonie Księga n stron, w najgorszym przypadku,
może mi n kroki podjąć.
Co przy frekwencji?
Jeden dwa trzy cztery pięć sześć.
Jaki jest czas pracy tego Algorytm przy frekwencji?
Big O n, ponieważ w teorii I muszą wskazać wszystkich w pokoju.
>> Teraz tak na marginesie, co z inne optymalizacja z tygodnia zera?
Dwa, cztery, sześć, osiem, 10, 12.
Informatykiem będzie sobie sprawę, chwileczkę,
to jest na porządku n dzieli się przez dwa etapy.
Dobrze?
Ponieważ robię dwie osoby na raz.
Ale będziemy ignorować te niższe terminy zamówień,
a my po prostu się wyrzucić podzielić przez 2,
i po prostu powiedzieć, Big O n do tego algorytmu, jak również.
>> A co z tym?
Będziemy pominąć niektóre z nich, ale to, co był algorytm, który był log n?
To trwało około log n kroki?
Podział i przejęcie.
Dokładnie.
Podobnie jak w przykładzie z książki telefonicznej w tydzień zero i dzisiaj wcześniej,
gdzie dzieli problem znowu i znowu i znowu.
Mamy wyciągnął go na pokładzie w tym tygodniu zera jako zakrzywiony zielonej linii
i powiedział, że dnia było logarytmiczną algorytm.
>> I rzeczywiście, liczba kroków, przyjmuje do wykonania dziel i rządź,
lub przeszukiwanie binarne, jak zaczniemy nazywając ją, tak jak w książce telefonicznej,
jest na zlecenie dziennika i kroków.
I to jest trochę dziwne jeden.
>> Czym zajmuje jeden krok, lub bardziej szczegółowo
stała liczba kroków?
Może to dwa, może to trzy, ale informatyk tylko
Upraszcza to jako wielki O 1, niektóre stała liczba kroków.
Co znajduje się w coś, co można zrobić, że ma stałą liczbę kroków?
>> Jaki jest czas pracy klaskać?
Stała czasowa.
Dobrze?
Jak, co to jest czas pracy cokolwiek, które ma tylko jeden
Operacja, jak drukować F Hello World.
Które mogą być uznane za stałą czasową, chyba mniej przypadku rogu z druku F,
Co może czas pracy druku F faktycznie?
I czemu?
Co to jest pomiarowy n w tym przypadku?
>> PUBLICZNOŚCI: [niesłyszalne].
David J. MALAN: Dokładnie.
Liczba znaków chcemy wydrukować.
Więc to jest bardzo kontekstowa.
Dziś mamy skupia się wiele na Tutaj litery i cyfry na tablicy.
Ale może to być również znaki w rzeczywistej ciąg.
Tak więc okazuje się, że jest inny środek, który rozpocznie dbając o,
i to jest przeciwieństwem z Big O, tak powiem.
>> To zapis omega.
Podczas gdy duże O, co oznacza, The górne ograniczenie na czas pracy?
Maksymalnie, ile czasu może coś zabrać?
Omega-- przykro to ciągle pojawia up-- jest przeciwieństwem tego,
przy czym jest to dolna granica na ilość czasu coś może potrwać.
>> Więc. na przykład, co jest algorytm że ma zawsze n kwadratowe kroki?
Cóż, jeden z algorytmów widzieliśmy Obecnie, w rzeczywistości, może być tak, że również.
Sortuj wybór.
Wybór rodzaju całkiem głupi.
Nawet jeśli algorithm-- przykro, nawet jeśli tablica jest już posortowana,
Wybór rodzaju będzie zachować spaceru po liście
aby upewnić się, że ma najmniejszy Element znowu i znowu i znowu.
I nawet jeśli ludzie w Publiczność wie, że zaraz,
już przeszedł najmniejszy element, komputer
nie wie, że dopóki to wygląda przez całą drogę listy.
Podobnie, dolna granica, że może być również brane pod uwagę
Czas może być liniowa.
>> Ile czasu potrzeba, aby Elementy sortowania n w najlepszy
Sprawa bańki za pomocą czegoś takiego rodzaju?
Załóżmy, że lista jest już posortowana.
Powiedzieliśmy, sortowanie bąbelkowe nabiera kolejność n do kwadratu kroki.
Ale co, jeśli to już klasyfikowane?
Co zrobić, jeśli uświadomić sobie, po jedno przejście przez tablicę
że nie zrobiłeś swapy?
Czy trzeba zachować co więcej przechodzi?
>> Nie.
Więc dolną granicę sortowanie bąbelkowe Można powiedzieć, liniowy.
Omega n.
I możemy spojrzeć na inni z nich, jak również.
Więc rzućmy okiem co tylko wizualizacji tutaj
aby zobaczyć, jak te wyróżniają się.
Mam zamiar iść na dół do tego Strona to jest dostępne na stronie internetowej C50, w
ale to będzie ból, aby dostać pracę, ponieważ wykorzystuje technologię o nazwie
Apletów Java, które jest w dużej mierze obsługiwane w tych dniach,
co najmniej przez Chrome i niektórych innych.
>> I pozwól mi iść do przodu i przyspieszyć ten się i wyjaśnić, co się dzieje.
Jest to demonstracja bańki rodzaju, pierwszy algorytm przyjrzeliśmy.
I to jest wizualizacja tym, że każdy z tych prętów stanowi liczbę.
Im większy jest bar, im większa liczba.
Im mniejszy jest bar, Im mniejsza liczba.
A co możesz zobaczyć wizualnie, nawet choć to będzie super szybki,
jest to, że czerwony pasek jest podobny do mnie, chodzenie tam iz powrotem rozwiązywania problemów.
Widać, że większe elementy rzeczywiście się pęcherzyków w prawo
i mniejsze elementy są pęcherzyków do lewej.
I tutaj, jeśli będziemy faktycznie przyjrzeć się bliżej,
faktycznie możemy liczyć liczba porównań i swapy
które były wykonane.
>> Ale zamiast tego, spójrzmy w drugim algorytmem
przyjrzeliśmy się wcześniej z naszym wolontariuszy, wybór rodzaju.
Wizualnie, posiada bardzo różny efekt.
Ale to znowu bardzo intuicyjny w że trzymamy wybierając następna najmniejsza
elementem, i mieliśmy trochę szczęścia.
Że czuł się zasadniczo szybciej.
Ale jeśli prowadził to znowu i znowu i znowu z wieloma wejściami,
to widzimy, że jest to w istocie nadal w dużym O n do kwadratu.
>> Zróbmy jeden ostatni tutaj, Sortowanie przez wstawianie,
która była trzecim algorytmem przyjrzeliśmy się i wycofywania
że ten zajmuje się elementy, jak napotka je,
Ale wtedy być może zmiany rzeczy, nad, aby zrobić miejsce,
wstawiania elementów do której należą.
>> I to też kończy się dając ostateczny wynik. Teraz wszystkie trzy z tych,
czułem się dość szybko.
I rzeczywiście, wpadłem je w całkiem dobrym klipu.
Ale zasadniczo, oni wszyscy dość straszne, szczerze mówiąc.
Wszystkie z tych algorytmów dotychczas że prowadzony w Big O n do kwadratu
zabrać sporo czas, aby uruchomić w końcu.
>> I rzeczywiście, możemy zobaczyć i czuć to wreszcie
jeśli podciągnąć ten trzeci i ostatni demo.
Jest to kolejny wizualizacji, które będzie
sortowanie bąbelkowe pokazać po lewej stronie, Wybór rodzaju w środku,
i coś, jako jeden z naszych ręka podnosi wcześniej zasugerował,
sortowanie przez scalanie po prawej stronie.
Podział i przejęcie Strategia na prawo.
I to jest w rzeczywistości, co mamy przyjrzymy się w środę.
, Ale niech czas te na prowadzenie równolegle.
To jest w przybliżeniu taka sama ilość Elementy wszystkim działa w tym samym czasie.
Sortowanie bąbelkowe vs wyboru Sortuj vs sortowanie przez scalanie.
>> Teraz oni wszyscy działa W teorii, w tym samym czasie.
Procesor pracuje z z tą samą prędkością, ale
może czuć się jak nudne to jest bardzo szybko stanie się,
i jak szybko, kiedy możemy wstrzyknąć trochę tygodnia
Algorytmy Zero może możemy przyspieszyć.
>> A teraz porównajmy tych w jednej ostatniej postaci.
Mam zamiar iść do przodu na stronie CS50, gdzie
mamy to ostatnie ogniwo na dziś, gdzie ktoś w internecie
prosimy umieścić razem film, który rejestruje to, co innego sortowania
Algorytmy brzmieć.
To Sortowanie przez wstawianie.
>> [DŹWIĘKOWY]
>> W którym starasz się częstotliwość na podstawie wysokości Bar.
Jest to sortowanie bąbelkowe.
>> [Warped DŹWIĘKOWY]
>> Jadąc obok jest-- nadchodzi w przyszłym jest-- wybór rodzaju,
gdzie znów mamy wyboru następny najmniejszy element,
i widzimy, że rośnie od lewej do prawej.
>> Sortowanie przez scalanie, nasz zwycięzca tej pory dzisiaj.
Zauważ, jak to podzielenie rzeczy do [niesłyszalne] połowie i kwartałów.
Gnome rodzaju, które nie mamy mówił o, i tworzy wizualnie
i audally trochę inny kształt i dźwięk.
Tam iz powrotem, czyszczenia rzeczy.
Sprawdź również sortowanie przez kopcowanie na stronie internetowej tego faceta.
>> I to wszystko.
Będziemy zobaczenia następnym razem.
>> [WHOOSHING I MUZYKA]