>> Głośnik: Dobrze, to jest CS50.
Jest to koniec trzy tygodnie, a gdy nie skorzystało już,
wiem, że nie będzie obiad jak zwykle w piątek, gdzie
można cieszyć się dobrą rozmowę i jedzenie w Fire and Ice
niektóre z CS50 jest Pracownicy i koledzy.
Udaj się do tego adresu URL tutaj.
>> Teraz możesz sobie przypomnieć, czy jesteś może szybko zapoznać się z,
te rzeczy, które tutaj podane są na końcu
semestru dla wielu klas.
Tak zwany egzamin niebieski książek, w których napisać swoje odpowiedzi do egzaminów.
Teraz mam tutaj 26 takich niebieskie książki, na każdą z nich
jest napisane imię, A do Z. I rzeczywiście nazwy są takie proste,
przez Z. I jeden z cele w ręku dzisiaj
będzie kontynuować co zaczęliśmy w poniedziałek, który nie jest
tak patrząc na kod, ale naprawdę patrząc na pomysły i rozwiązywania problemów.
Jednym z celów i Obietnice tego kursu
jest, aby nauczyć się myśleć starannie, bardziej metodycznie,
i sprawne rozwiązanie problemów.
I rzeczywiście, można to zrobić bardzo bez dotykania linii kodu.
Mam więc kilka słoni się tu dzisiaj, pomarańczowy i niebieski,
czy możemy dostać jednego wolontariusza, być może z powrotem dalej niż zwykle.
Jak się tam, chodź na dół.
Celem, który ma być do pomóc Plus podawać ten egzamin tutaj.
Jak masz na imię?
>> PUBLICZNOŚCI: Mary Beth.
Głośnik: Mary Beth, dalej w górę.
Pozwól mi mikrofon tu dla Ciebie.
Miło cię poznać.
>> PUBLICZNOŚCI: Miło cię poznać.
Głośnik: Dobrze, więc mam o niebieskie książki od A do Z,
i będę udawać, że Mam jeden z uczniów,
i jedziesz w nieco losowo na koniec trzy godziny egzaminu bloku
więc oni kończący się w niektórych semi-losowa kolejność tak.
Teraz Twoja praca za chwilę będzie aby być: to jest rzeczywiście jak się dostać
Okazało się przy końcu Klasa, najprawdopodobniej.
Twoim zadaniem jest teraz będzie, całkiem po prostu, aby sortować te niebieskie książek dla nas
od A do Z.
>> PUBLICZNOŚCI: Och, to jest będzie trwać wiecznie.
>> Głośnik: I będziemy oglądać jak to zrobić, nie ma ciśnienia.
PUBLICZNOŚCI: Nie, nie ma ciśnienia, ani nic.
>> Głośnik: A dla zabawy, postawmy się zegar.
>> PUBLICZNOŚCI: Tyle radości, tyle zabawy.
>> Głośnik: mogę trzymać mikrofon dla Ciebie.
Wszystko w porządku, właśnie podwoił naszą prędkość.
Więc w międzyczasie, niech stanowią co będzie pytanie do Mary Beth
jest to, co ona robi, jak jest ona idzie o rozwiązanie tego?
I rzeczywiście, nie może mieć kiedykolwiek myślałeś o czymś
tak proste, jak przy odbiorze aż 26 książek takich jak ta,
które mają naturalne Zamawiając do nich.
Co to jest proces że faktycznie korzysta?
Jest to dość losowo tylko zbieranie się pierwszy widoczny
i wprowadzenie go w jego miejsce?
Czy najpierw przenieść swoje ręce wokół Szukam następnie szuka B?
Czy warto zapoznać się Para strony je stronie
i po prostu powiedzieć: chwileczkę, to nie jest w porządku, a następnie zamienić kolejność?
Widzieliśmy już w poniedziałek że istnieje wiele sposobów,
w którym możemy to zrobić, i Rzeczywiście, kiedy w pobliżu końca tutaj
Chciałbym zwrócić uwagę może czego Mary Beth robi.
Mamy kilka pali się wydaje, większy, trzy mniejsze.
>> PUBLICZNOŚCI: Jestem ich zamawianiu kiedy znajdę dwie litery
Wiem, że są ze sobą w sekwencji, I umieścić je razem tak, że ja nie
muszą się martwić o utrzymanie utwór z całego szeregu książek.
To jest po prostu, no, to po pierwsze, Mam ten stos tutaj.
Głośnik: Tak, prawie jak a kawałki układanki, które
mają odpowiedni kształt zgadza się ze sobą.
PUBLICZNOŚCI: Dość dużo, tak.
Głośnik: OK, doskonałe.
Teraz każdy z nich pale jest prawdopodobnie sortowane?
>> PUBLICZNOŚCI: Tak.
>> Głośnik: Dobra, przez Z. Wszystkie Dobrze, gratulacje, udało ci się.
Masz wybór.
Niebieski?
Wszystko w porządku, dziękuję za to.
Więc nie zaproponować Mary Beth co jej podejście było,
ale to, co jest inne podejście, w jaki sposób Sortowanie może iść o te rzeczy?
Co byś zrobił?
Rekord do pobicia byłby jednej minuty, 50 sekund lub tak,
Plus te zapomniałem liczyć.
Co byś zrobił?
Tak?
PUBLICZNOŚCI: Weź stos.
Zacznij od początku.
Sprawdź swoje papiery.
I jeśli jedna górna jest większa niż, być może, że są,
dolny jest wyższy, a następnie przełączyć je.
>> Głośnik: OK, więc zaczynając Na górze i na dole
a następnie na swój sposób pracy do wewnątrz tak, zamieniając je?
OK, więc trochę podobna w duchu do bańki rodzaju,
ale wybór skrajności nie sąsiadujące pary.
Ale krótkie jest to, że nie ma na pewno kilka różnych sposobów
możemy to zrobić, i Szczerze mówiąc, myślę, że rodzaj
przyjęła kilka podejść, prawda?
Zrobiłeś coś w rodzaju czterech segregowanych pali, i następnie skutecznie połączył je razem.
A to, śmiem twierdzić, inny całkowicie techniką.
Nie traktują go jako jeden wielki stos, można podzielić na cztery problem quadów,
jeśli chcesz, a następnie w jakiś sposób połączono je na końcu.
>> Warto więc rozważyć, ostatecznie, jak inaczej moglibyśmy to zrobić.
Mamy sformalizowane pojęcie bubble sort ostatnim czasie,
i wycofanie bubble sort był Algorytm że wizualizowane
z ośmioma kolegami się tutaj, pozornie przypadkowo sortowane w pierwszej kolejności.
I wtedy zdecydowaliśmy parami, jeśli dwa elementy są w porządku,
po prostu zamienić je.
Tak więc cztery i dwa są oczywiście w porządku,
więc te dwa koledzy pozycji włączony.
A potem powtórzyć z czterech do sześciu, następnie sześć i osiem na każdej iteracji,
przemieszcza się na prawo.
>> Tak więc biorąc pod uwagę osiem osób, ile parami porównania zrobiłem podczas spaceru z
od lewej do prawej w jednej iteracji tego?
Ile porównań?
Siedem, prawda?
Bo jeśli jest osiem osób, ale trzeba parę
im i ruszać po jednym z prawej
nie będziemy mieć osiem porównania, ponieważ nie można porównać
Element na sobie, albo byłoby po prostu bez sensu, więc trzeba siedem.
Lub, bardziej ogólnie, gdy mamy n ludzi, my
do porównań n minus 1 z bańki rodzaju.
>> Rozważmy więc teraz, jak dobre lub złe sortowanie bąbelkowe faktycznie było, i spróbuj
dać sobie słownictwo z które do algorytmów krytyki jak to,
i wkrótce nasz własny.
Więc pierwszego przejścia przez sortowanie bąbelkowe, pierwszy raz
Chodziłem od lewej do prawej etap, wziął mnie n minus 1 porównań.
I to będzie mój jednostka miary, prawda?
Miałam rozmowy i spacery, dość szybko, trochę powolny
więc licząc mojego liczbę sekund nie jest szczególnie mówiąc,
a zliczanie liczby Operacje, które zrobiłem w poniedziałek,
Porównując dwie osoby, które uważa jak miły jednostki miary.
>> Więc n minus 1 kroki po raz pierwszy, ale to, co się stało potem?
Co jeden plus z jednym przejściu poprzez listy inaczej niesegregowanych?
Co możesz mi powiedzieć o elemencie który był aż tam?
Tak?
To był największy elementem, prawda?
Numer osiem, mimo że rozpoczął tutaj, za każdym razem kiedy
porównano ją do sąsiad, trzymała
pęcherzyków do prawej strony listy.
I rzeczywiście, to gdzie Algorytm dostaje swoją nazwę.
>> Teraz o tym logiki, ile porównania muszę zrobić na raz drugi
Robię to podanie z lewej do prawej?
n minus 2, prawda?
To byłoby marnować mój czas, gdybym zachować porównanie ośmiu przeciwko komuś
indziej, bo już wiemy, była w odpowiednim miejscu.
Więc to jest trochę optymalizacja, więc następnego przejścia
będzie Plus n minus dwa stopnie, gdzie n oznacza liczbę osób.
Teraz możesz rodzaju ekstrapolacji, nawet jeśli nie jesteś informatykiem,
jak to się kończy.
Pod koniec tego algorytmu przypuszczalnie masz tylko jedno porównanie lewo.
Musisz trochę naprawić początku listy w przypadku dwóch
i jeden jest w porządku i powinna być jeden i dwa
tak więc długość, przy Plus 1 ostateczne porównanie.
>> Teraz kropka, kropka, kropka rodzaj fal jest ręce na niektóre z bardziej soczyste szczegóły,
ale niech po prostu iść do przodu i uproszczenia.
Jeśli pamiętacie z wysokiej Szkoła, szczerze mówiąc, wiele z was
miały książki matematyczne, które miały trochę ściągawki
na okładce lub tylna pokrywa, że ​​pokazałem
sumowania, co seria, jak to ostatecznie dodana do.
W ogólnym przypadku, jeśli masz Zmienna jak n, a nawet ten,
jeśli spojrzał na swoje stara szkoła książka matematyka,
to zobaczysz, że to naprawdę dodaje do tej sumy tutaj,
n razy n minus 1 wszystko podzielić przez 2.
Więc teraz niech mi tylko zastrzec, to prawda, więc na skok wiary,
to właśnie ta podsumowuje do, i mogliśmy
dowodzą, że w bardziej ogólnym przypadku.
Ale teraz niech poszerzyć to.
Warto więc pomnożyć to, więc to n do kwadratu minus n, wszystko podzielić przez 2.
To naprawdę n do kwadratu, podzielić przez 2, minus n nad 2,
tak, to wszystko ładne i ciekawe.
Ale co się stanie, jeśli teraz plug-in o wartości?
Załóżmy, że nie miałem osiem osób, ale powiedzieć milion.
I tylko dlatego, że miliony jest to dość duża liczba,
niech wtyczkę i zobaczyć, co się dzieje.
Więc jeśli podłączyć mln w tym wzorze Mam zamiar dostać milion do kwadratu,
podzielić przez 2, minus mln, podzielić przez 2.
Teraz co to będzie równe?
Więc 500 miliardów, minus 500.000.
I jeśli faktycznie że matematyka się, że środki
że sortowanie milion osoby o sortowanie bąbelkowe
może zająć mi 499999500000 kroków lub porównania w celu
jesteśmy po prostu ekstrapolację.
>> Że czuje się dość wolno, ale szczerze wejście do pomiaru jednego konkretnego
tak, to nie wszystko, że wiadomo.
Ale w rzeczywistości to nie sugeruje, że jak n dostaje coraz większy, to algorytm
rodzaj czuje się gorzej i gorzej, lub że naprawdę
zacznie odczuwać ból, że potęgowanie, że n do kwadratu,
który dodaje się dość szybko.
I to nie jest detal stracił na ludzi, w rzeczywistości
kilka lat temu pewien senator, który był kampanii, usiadł na rozmowę
z Google'a Eric Schmidt, CEO w czasie,
i został zakwestionowany w pytaniu podobnie jak badamy dzisiaj.
Rzućmy okiem.
>> [ODTWARZANIE]
>> -Senator, Że tu jesteś w Google, i lubię
myśleć o prezydenturę jak rozmowy kwalifikacyjnej.
Teraz, to jest trudne do uzyskania praca jako prezydent,
i przechodzisz rygorów teraz.
Trudno też, aby dostać pracę w Google.
Mamy pytania, a my zapytaj naszych kandydatów na pytania,
i ten jest z Larry Schwimmer.
Co-- myślicie, że jestem żartuję, że to właśnie tutaj.
Jaki jest najbardziej efektywny sposób sortować milion 32-bitowe liczby całkowite?
>> -Well--
>> -Przepraszam, Maybe--
>> Nie, nie, nie.
Myślę, że coś w rodzaju bańki byłoby tak droga.
>> Daj spokój, który powiedział mu to?
Nie widziałem komputer Nauka w tle.
>> -Mamy Naszych szpiegów tam.
>> -OK, Zapytajmy inaczej Wywiad pytanie.
>> [KONIEC ODTWARZANIE]
>> Głośnik: Tak mówi o choć, konkretne numery
nie będzie wszystko, co użyteczne.
To nie jest życie, że bańka lekcja sortowania, ponieważ milion wejść,
może zająć aż 500 miliardów kroków.
Naprawdę nie można generalizować z tego zbyt skutecznie
i podejmować dobre decyzje projektowe podczas pisania programów.
Więc skupmy się jednak, w jaki sposób możemy uprościć ten wynik.
>> Więc ja tu zaznaczony na żółto Wynik n kwadratu podzielony przez 2,
tak mln kwadratu dzielona przez 2, a potem
Podświetlony, co mam Najlepsza odpowiedź była
raz możemy odjąć od n dzieli się przez 2.
I roszczenia Zamierzam zrobić to, kto do cholery obchodzi, jeśli odjąć od
trochę stary n nad 2, gdy pierwszy część tej formuły jest więc znacznie większy?
Dominuje inne Termin, n do kwadratu podzielić przez 2
jest więc znacznie większy, wyraźnie, jak n pobiera duże jak milion,
że tam jest naprawdę duża różnica w Koniec dni pomiędzy 500000000000
i 499999500000?
Nie bardzo.
A więc to, co mamy zamiar zrobić, jak to informatycy
zignorować te warunki zamówienia i niższe wziąć coś takiego i naprawdę
tylko do uproszczenia Określenie, że będzie to znaczenia.
Większe nasze zbiory danych, tym większe nasze bazy danych, tym więcej stron internetowych
musimy szukać, więcej przyjaciele masz na Facebooku.
>> Jak n staje się większy, że jesteśmy naprawdę zamiar dbać o największym
Termin w takiej analizie nasza wydajność algorytmów.
I mam zamiar powiedzieć, że wiesz, co, Sortowanie bąbelkowe jest na porządku Big O,
rzędu n do kwadratu.
To nie jest dokładnie n kwadratu, jak widzieliśmy,
ale kogo to obchodzi chodzi o tych mniejszych,
i szczerze mówiąc, kto naprawdę obchodzi, dzielimy przez 2?
To tylko czynnikiem stałym.
I jest w porównaniu do 250 500 miliardów mld naprawdę to nic wielkiego?
Mogę tylko czekać na jeden rok, niech mój laptop dosłownie
się dwa razy szybciej w sprzęcie, i tego rodzaju różnicy
po prostu zniknie w sposób naturalny w czasie.
>> Co dbamy o to Wyrażenie część
wyrażenia, które będzie się zmieniać jako nasz wkład robi się coraz większy i większy.
I rzeczywiście, w prawdziwym świecie, że to, co dzieje się w coraz większym stopniu
ma wejść do naszych problemów i Algorytmy są coraz większe.
Tak duże O będzie zapis, asymptotycznej zapis, że po prostu
używać jako informatycy, aby opisać wydajność, lub czas pracy,
algorytmu.
Tak, że możemy porównać algorytmy pisanych na różnych komputerach
przez różne osoby, stosując niektóre zasadniczo podobny metryczne
jak liczby porównań jesteś co, a może liczby swapów
robisz.
>> Co my nie zamierzamy Ilość jest czas
który przechodzi na zegarze na typowo ścianie.
Co nie będziemy się martwić o to, ile pamięci
używasz dzisiaj na najmniej, choć to
inny zasób możemy zmierzyć.
Mamy zamiar spróbować oprzeć nasze analizy na zaledwie podstawowych operacji, te,
szczerze, że można zobaczyć najbardziej wizualnie.
Więc coś jak Big O n do kwadratu, to twierdzą, że O n do kwadratu
jest górne ograniczenie tzw czas bubble rodzaju systemem.
Innymi słowy, jeśli chciał twierdzić, że nie ma
ta górna granica liczby kroków algorytmu może podjąć,
to będzie w wielkim O n obrobione w tym przypadku górna granica.
>> Co zrobić, jeśli zamiast zmienić historia się nie o sortowanie bąbelkowe,
ale o to górna granica.
Można myśleć o algorytmie że poznaliśmy już wcześniej
którego górna granica, maksymalna pomiaru czasu lub działań,
to być uznane za ograniczone przez n, funkcja liniowa,
nie jeden, który znajduje się kwadratowa zakrzywiona?
Co to jest algorytm, który zawsze trwa dłużej
nie jak krokach n, lub 2n kroków, lub kroki 3n?
Tak?
>> PUBLICZNOŚCI: Znalezienie Najwięcej na liście?
>> GŁOŚNIK: Perfect, znalezienie Najwięcej na liście.
Jeśli mam podano listę osób, na przykład,
każdy kto trzyma numer, co jest maksymalną liczbę
kroków powinien wziąć mnie, rozsądnie inteligentny człowiek,
znaleźć największą osoby na tej liście?
n, w porządku?
Ponieważ w najgorszym przypadku, w którym Największą wartość może być?
Prawo, aż w końcu.
Tak więc w najgorszym przypadku górna granica, mogę
musiał przejść całą drogę tu i być jak,
O, tu jest numer osiem, lub cokolwiek to jest wartość nie jest.
Teraz byłoby to po prostu głupie jeśli ja ruszyłem, prawda?
Szukasz więcej i więcej elementów jeśli ostatni z nich jest tam?
Więc na pewno, n jest górna granica.
Nie trzeba podejmować więcej kroków niż to.
>> Więc co, jeśli zamiast tego proponuje się, istnieją algorytmy, które w tym świecie
mają czas, który jest systemem ograniczona przez duże O. dziennika n, log n?
Gdzie widzieliśmy tego wcześniej?
Tak?
>> PUBLICZNOŚCI: W książce telefonicznej problemu?
Głośnik: Jak problemu książki telefonicznej.
Co było miarą wiele czasu i ile łez IT
zajęło mi znaleźć kogoś takiego jak Mike Smith w książce telefonicznej?
Twierdziliśmy, że to log n, a nawet jeśli nie zna albo jest
trochę zamglone, co logarytm lub wykładnik był,
Wystarczy pamiętać, że log n ogólnie odnosi się do procesu
W tym przypadku dzielenia coś w połowie znowu, i znowu,
i i znów, tak, że staje się coraz bardziej mały, jak to zrobić.
>> Więc zalogować n odnosi, na pewno, na przykład w książce telefonicznej,
do wyszukiwania binarnego w teorii, kiedy miał drzwi wirtualnych na pokładzie,
lub gdy Sean szukając czegoś.
Gdyby stosować wyszukiwanie binarne, log n byłaby górną granicę ile
czas, który zajmuje.
Ale te algorytmy, które biegły w log n zakłada Jaki klucz szczegół?
Że lista została posortowana, tak?
Twój algorytm jest nie tak, jeśli Twój wkład nie jest klasyfikowane,
i jeszcze używasz coś jak wyszukiwanie binarne
ponieważ można skakać tuż nad elementem
nie zdając sobie sprawy, że to rzeczywiście nie.
>> Teraz co to może oznaczać, Big O jednego?
To nie znaczy, że twój algorytm trwa jeden i tylko jeden krok,
to po prostu oznacza, że ​​trwa stałej liczby kroków.
Może to 1, może to 10, może to 1000,
ale to jest niezależne od Wielkość tego problemu.
Bez względu na to, jak duże n, Stała czasowa algorytmu
ma zawsze tę samą liczbę stopni.
Więc co może być algorytm Rozmawialiśmy o lub po prostu
intuicyjnie, że przychodzi do ciebie, że przebiega zawsze w tak zwanym stałym czasie?
Tak?
>> PUBLICZNOŚCI: Dodaj dwie liczby.
Głośnik: Dodaj dwie liczby, 2 plus 2 równa się 4, zrobione.
Tak, że może działać, co jeszcze?
Jak o bardziej realnym świecie, tak?
>> PUBLICZNOŚCI: Znalezienie Pierwszą rzeczą, na liście.
Głośnik: Znalezienie pierwszy elementu na liście, na pewno.
Mamy faktycznie rozmawia o już tablic,
jak masz na Pierwszy element tablicy
niezależnie od tego, jak długo Tablica jest w kod C?
Po prostu użyć jak wspornika Zapis zero, bam, że tam jesteś.
I rzeczywiście, jak tablice, na bok, Wsparcie coś ogólnie znane
jako losowy dostęp losowy dostęp pamięci, ponieważ można dosłownie
przejście do jednego miejsca.
Możemy to zrobić jeszcze prościej możemy przewinąć do tygodnia zerowego
kiedy zrobiliśmy Scratch.
Ile czasu zajęło Say w Scratch do wykonania?
Tylko stały czas, prawda?
Powiedz coś, powiedzieć coś, to nie ma znaczenia
Jak duży Rysy świat jest, to zawsze będzie mieć taką samą ilość czasu
po prostu coś powiedzieć.
>> Więc to jest stała czasowa, ale co druga strona?
Jeśli to była górna granice, co, jeśli chcemy
opisać dolną granicę naszych algorytmów działa czas?
Prawie najlepszym przypadku potencjalnie, jeśli chcesz,
choć terminy te mogą mieć zastosowanie do najlepiej skrzynki, najgorszych przypadkach średnie przypadki więcej
ogólnie, ale niech po prostu skupić się na dolnych granicach ogólnie.
Co to jest algorytm, który ma dolna granica n krokach,
lub 2n kroków, lub kroki 3n?
Niektóre czynnik n krokach, to jej dolnej granicy.
Tak?
>> PUBLICZNOŚCI: Bubble sort?
>> Głośnik: Bubble sort bierze Ci minimalnie n kroków, dlaczego?
Dlaczego tak jest?
Dlaczego warto, że początek przyjść do Ciebie intuicyjnie, nawet jeśli to nie wystarczy
jeszcze?
Tak?
>> PUBLICZNOŚCI: [niesłyszalne].
Głośnik: Dokładnie.
W najlepszy możliwy scenariusz Sortowanie bąbelkowe i wiele algorytmów,
jeśli oddam ci osiem osób którzy są już posortowane,
byłoby głupotą dla Ciebie, algorytm,
do tam iz powrotem więcej niż raz, prawda?
Bo jak tylko Ciebie przejść przez listy raz,
należy zdać sobie sprawę, och, nie zrobiłem swapy, ta lista jest posortowana, zjazd.
Ale to zajmie ci n kroków.
>> I odwrotnie, co jest kolejnym sposób myślenia o nim?
Sortowanie bąbelkowe jest omega, że tak powiem, n,
bo jeśli spojrzeć na mniej niż n elementów, co
Zasadniczą kwestią jest tam?
Nie wiem, czy to jest klasyfikowane, prawda.
My, ludzie, może spojrzenie na ośmiu osób i być jak, och, to sortowane,
że nie wziął mnie n kroków, ale to zrobiłem.
Twoje oczy, nawet jeśli rodzaj z ma duże pole widzenia,
spojrzał na ośmiu elementów, spojrzał na osiem osób,
to osiem stopni skutecznie.
I tylko wtedy, gdy idę przez cały lista nie rozumiem, tak, sortowane.
Gdybym przerwanie myśli, wszystko Dobrze, że to całkiem klasyfikowane do tej pory,
jakie są szanse, że nie sortowane?
Że nie będzie algorytmy prawidłowe.
Może być szybsze, ale błędne.
>> Więc teraz mamy drogę Opisywanie niższe granice,
i co o stałym czasie?
Co jest algorytmem, który ma niższe związany od jego czasu pracy w jednym?
1 krok, 2 stopnie, 10 stopni, ale stała, niezależnie od n,
Powierzchnia wejścia?
Tak, w plecy.
>> PUBLICZNOŚCI: printf?
Głośnik: Co to jest?
PUBLICZNOŚCI: printf?
GŁOŚNIK: printf.
OK, na pewno.
Więc to ma stałą liczbę kroków.
I mam teraz-- teraz mówimy o kod C
i nie podstaw, coś jak powiedzmy, z printf,
powinniśmy zacząć się uważać.
Ponieważ printf bierze wejście, to ciąg,
i łańcuchy nie mają długość technicznie.
Jeśli więc teraz chcą odebrać na ciebie, jeśli nie masz nic przeciwko,
technicznie możemy twierdzić, że printf bierze wejście zmiennej długości,
i na pewno może zająć więcej Czas wydrukowania ciąg tak długo,
od tej długości.
>> Więc co, jeśli weźmiemy pod uwagę tylko sortowanie i wyszukiwanie przykładów?
Co Mike Smith w telefonie książka, lub bardziej ogólnie binarne wyszukiwania?
W najlepszym przypadku, co może się zdarzyć?
Otworzyć książkę telefoniczną i, bam, jest liczba Mike Smith.
Mogę zadzwonić do niego od razu.
>> Zrobił krok, może dwa kroki, a stałą ilość kroków
jeśli mam szczęście.
I szczerze mówiąc, widzieliśmy na Poniedziałek twój kolega
się dość szczęśliwy dwa razy z rzędu.
I to było rzeczywiście stała czas w niższych granicach
algorytmu określonego do znalezienia Numer 50 za te zamknięte
drzwi.
>> Teraz, jak na bok, jeśli odkryjesz że zarówno duże O, górne,
i omega, dolna granica, są jedna identyczne,
Jest w ten sam wzór nawiasy, można również
powiedzieć, po prostu być wyszukane, że coś jest w teta
n lub teta innej wartości.
To oznacza, że ​​gdy duże O i omega są takie same.
Teraz to, co o wybór rodzaju?
Użyjmy tego nowego słownictwa.
W selekcji rodzaju, co byliśmy robi znowu, i znowu, i znowu?
Byłem tam iz powrotem przez listę, szukając kogo?
Najmniejsza liczba.
>> Tak jak wiele kroków, jak I zrobił wiele porównań
trzeba zrobić, aby dowiedzieć się, kto najmniejszy element listy jest?
n minus 1, prawda?
Bo jeśli po prostu zacząć z jednego jestem podane i zaczynam porównanie mu,
następnie go lub ją, nim albo ona, on czy ona, że
można powiązać tylko elementy razem n minus 1 razy.
Więc wybór sortowania podobnie trwa n minus 1 kroki po raz pierwszy.
>> Ile kroków zajmuje mi znajdź drugi najmniejszy element?
n minus 2, bo jest głupi jestem jeśli Ciągle patrząc na tych samych ludzi,
ponownie, jeśli go już wybrany lub jej i umieścić je w ich miejsce.
Oraz trzeci krok, n minus 3, to n minus 4.
Widzieliśmy ten wzór Przed i rzeczywiście
Wybór sortowania podobnie ma górnej granicy
n do kwadratu, jeśli robimy się, że sumowanie.
Co jest jej dolnej granicy, wybór sortowania?
Minimalnie, ile czasu musi wybór Sortuj wziąć, jak określono to w poniedziałek?
Proponuję dwie opcje.
Może to n, jak poprzednio.
Może to n do kwadratu, jak to jest teraz w górnej granicy.
>> PUBLICZNOŚCI: n do kwadratu.
Głośnik: n do kwadratu.
Dlaczego?
>> PUBLICZNOŚCI: Bo masz zdefiniować [niesłyszalne].
>> Głośnik: Dokładnie.
Przynajmniej jak zdefiniowano wyboru rodzaju to dość naiwne, nie poddawać się,
Najkorzystniejsze najmniejszy element.
Idź jeszcze raz, znaleźć najmniejszy element.
Nie ma rodzaj tam, że optymalizacja
może dać mi przerwać po tylko brak lub tak kroki.
Tak więc w rzeczywistości, wybór sortowania, omega n do kwadratu.
>> Co wstawiania rodzaju, gdzie odbył który dostałem, a potem koleś go
lub jej we właściwym miejscu?
Potem udał się do drugiej osoby, koleś go lub ją w odpowiednim miejscu.
Potem następna osoba, koleś go lub ją w odpowiednim miejscu.
Zauważ, że jest to bardzo liniowa, że ​​tak powiem.
Jestem prosta, jestem nie tam iz powrotem,
Nigdy nie oglądając się naprawdę, ale co się dzieje po włożeniu go
lub jej na początku lista jak my w poniedziałek?
Co się dzieje?
Tak?
PUBLICZNOŚCI: [niesłyszalne].
Głośnik: Tak, był haczyk, prawda?
Może pamiętacie z Twoi koledzy z klasy, jeśli
robili żadnego ruchu z ich stopy, to było działanie.
Więc gdyby nie było tu trzy osoby Nowa osoba należała droga tam,
na długim etapie, jak to, na pewno, że lub może po prostu udać się do samego końca.
Ale jeśli myślimy o komputer i tablica pamięci,
osoby te będą mieć na shuffle
aby zrobić miejsce dla tej osoby.
I tak, że n minus 1 shufflings, n minus 2 shufflings, n
minus 3 shufflings tylko rodzaj dzieje za mną, nie przede mną
, jak powyżej, w pewnym sensie.
Teraz, jak na bok, a jak mogłeś online
jeśli zaczniesz grzebać o rodzaju, nie ma tak wiele różnych te
tam, niektóre z nich lepiej niż inne.
Rzeczywiście, jest bogosort to rodzaj zabawy, aby sprawdzić.
Bogosort wykonuje szereg numery lub powiedzieć talię kart,
losowo tasuje je i sprawdza, czy są one klasyfikowane.
A jeśli nie, to czy go ponownie.
Jeśli nie, to robi to ponownie.
Niewiarygodnie głupi.
>> I rzeczywiście, jeśli czytasz jak Wikipedia,
jego nick to głupi rodzaj.
Doprowadzi pracy, miejmy nadzieję, że wystarczająco dużo czasu,
ale, że czas może zająć trochę czasu.
Więc jeśli mogę, niech przyspieszyć się od przykładu Mary Beth wcześniej,
mając jeszcze kilka elementów, ale jeszcze dwa procesory.
Dwie osoby, jeśli Ciebie nie przeszkadza łączenie mnie.
Jak o 1 tutaj, i niech go-- nikogo tam?
Nikt tam?
OK.
Ci z czarnym koszula, tak, chodź na dół.
Dobra, jak masz na imię?
>> PUBLICZNOŚCI: Peter.
>> Głośnik: Co to jest?
>> PUBLICZNOŚCI: Peter.
Głośnik: Peter David, miło cię poznać.
Dobra, mamy tu Peter, jeśli Ciebie chce przyjść na stół tutaj.
A jak masz na imię?
>> PUBLICZNOŚCI: Elena.
Głośnik: Elena.
OK, miło cię poznać.
Elena spotykają Peter.
Peter, Elena.
I musimy Andrew się również tutaj, proszę.
A twój wyzwaniem będzie się uporządkować talię kart.
A jeśli nie znają, talia kart powinna ostatecznie
być klasyfikowane trochę coś jak tego, gdzie zrobimy kluby, a następnie
te piki, kiery i wtedy diamenty, od asa jako jeden,
wszystko aż do króla.
>> Karty Zamierzam dać będą 52 w ilości.
Jedziemy do podobnie Czas cię za chwilę.
Mamy zamiar rzucić Andrew na ekranie tutaj
tak, aby przyglądać się, jak to zrobić.
I tak że wszystko Jest to szczególnie widoczne
są to karty dostałem na Amazon.
Więc są już losowo sortowane i będziemy razem, gdy.
I będziemy keep it real tym razem,
więc mamy zamiar spróbować na Ciebie naciskać bo inaczej to będzie nudne
szybko.
Jeśli można przystąpić do sortowania 52 elementy ze sobą za pośrednictwem niektórych środków, teraz.
>> I znowu, jak oglądać te robicie to, co w końcu
będzie produkować oczywiste Wynik, myśleć o naprawdę
jak oni sobie robią, jak można to opisać.
Ponieważ znów są Wszystkie procesy, algorytmy
które bierzemy za pewnik, jako człowiek.
Ale to prawdopodobnie dawna intuicja, jeszcze na długo przed tobą
myślał o podjęciu ci klasy informatyka
Może miał intuicję z który do rozwiązywania problemów, takich jak ten.
Ale kiedy uznają wzorce i rozpocząć
sformalizowanie czynności, z którymi jesteś rozwiązywania tych problemów,
przekonasz się, że można rozwiązać wiele ciekawsza i dużo bardziej skomplikowana
problemy szybko.
Więc ktoś z publiczności, co jest co najmniej jeden element algorytmu
że używamy tutaj?
>> PUBLICZNOŚCI: [niesłyszalne]
Głośnik: Co to jest?
PUBLICZNOŚCI: Przez kolorze.
Głośnik: Przez kolorze.
Więc najpierw ich grupowanie wszystkich diamentów razem
Wydaje się, że wszyscy serca razem jak się wydaje,
i tak dalej, bez odniesieniu dla numerów na kartach.
Teraz pojawiają się, na przykład, do sortowania ich liczby.
Bardzo dobre.
>> Dobra, więc co się końcowy etap to tutaj?
Raz mamy cztery posortowane garnitury, co musimy zrobić do czterech palach
W celu osiągnięcia jednego sortowane pokład, po prostu?
Więc musimy połączyć je ponownie.
>> Więc jest to ciekawy pomysł, który ponownie, śmiem twierdzić, jest bardzo intuicyjne, nawet
jeśli nigdy nie mogło uderzył że rodzaj etykiety na nim.
To fundamentalne pojęcie podzielenie Problem nie w połowie tego czasu
lecz co najmniej na cztery kawałki.
Rozwiązywanie prawie zasadniczo identyczne problemy
oddzielnie od siebie, a następnie łączenie wyniki.
I, doskonała, zrobione.
Wszystko w porządku, duży okrągły oklasków, jeśli można.
>> [Aplauz]
>> Głośnik: nie mam pojęcia, co będzie z tym zrobić, ale tutaj jesteś.
Dziękuję bardzo.
Zobaczmy więc, dwie minuty i osiem sekund
jeśli chcesz, aby zmierzyć się z przyjaciółmi.
Co to będzie będzie zabrać z tego
że możemy wykorzystać bardziej ogólnie?
Dobrze, że powrót do Ta tablica z numerami,
i wracam teraz do niektórych pseudokod pisaliśmy w przeszłości,
i był to pseudokod dla rozwiązania problemu z książki telefonicznej.
Przy czym w pseudokod I wyliczone bardziej metodyczny,
opisać, jak ja bardzo intuicyjny Algorytm podziału ludzki telefon
książka w połowie, powtarzać, powtarzać, powtarzać, dopóki nie znajdę kogoś takiego jak Mike Smith,
jeśli jest on rzeczywiście w książce telefonicznej.
>> Ale rodzaj stosowany co zadzwonię bardzo iteracyjne podejście tutaj,
w szczególności zawiadomienia linia linia 8 i 11.
To są dowody iteracyjny podejście, podejście pętli,
bo to jest dokładnie zachowanie ich wywoływać.
Linie te mówią idź do obu Linia trzy, i można trochę
myśleć, że w Oko umysłu jako pętla.
To mówi ci, aby wrócić do kroku trzy i powtarzam jeszcze raz, i jeszcze raz,
i znowu.
>> Ale co, jeśli wykorzystać kluczową ideę tutaj, że nie po raz ostatni,
i uproszczenie linii 8 i Linia 11 i ich sąsiedzi
jak tylko ten, w kolorze żółtym.
To nie jest zasadniczo skraca pseudokod bardzo,
ale to zasadniczo zmienia charakter mojego algorytmu.
Co mam teraz powiedzieć W etapie 7, w kroku 10,
jest, aby szukać Mike w ten sam sposób,
lecz tylko w lewej połowa lub prawa połowa.
>> Tak więc, innymi słowy, jeśli Zacznę od pierwszego kroku,
odebrać książkę telefoniczną, otwarty na środku z książki telefonicznej, spojrzeć na nazwiska,
jeśli Smith jest jednym na imię, zadzwoń Mike, jeszcze
jeśli Smith jest wcześniej w książce Krok siódmy szukaj Mike lewej połowie książki.
Ale że niby czuje się jak pozostawiając mnie to wisi, prawda?
W kolorze żółtym, jest instrukcji, ale w jaki sposób
szukaj Mike w lewo połowa z książki telefonicznej?
Gdzie mam Algorytm z którą
może szukać kogoś takiego jak Mike Smith?
Cóż, to gapi nam w twarz.
Mogę dosłownie użyć dokładnie to samo Program skutecznie idzie do góry
ponownie i ponownie uruchomiony te same linie kodu.
>> Tak więc mimo, że powinien to poczuć jak trochę definicji cyklicznej
dokąd się wybierasz, odpowiadając na czyjeś Pytanie tylko o rodzaj prośbą
samo pytanie jeszcze raz, jak, dlaczego, dlaczego, dlaczego?
W rzeczywistości jest to trudne, ponieważ mamy zakodowane Kilka specjalnych linii, etap 4,
który, jeśli a etap 12, która jest faktycznie inny oddział,
ponieważ mamy te środki prowizorka, algorytm ten wygasa, jeżeli
znaleźć Mike, lub jeśli nie mamy.
Ale w kroku 7 i 10 Teraz mamy to, co my nazywamy algorytmu rekurencyjnego.
A rekurencja jest rzeczywiście potężna idea to trochę umysł gięcia w pierwszym,
, które można obecnie stosować w sposób następujący.
>> Merge sort będzie ostatni sort, że przyjrzymy się, co najmniej w klasie formalnie.
I jest to zasadniczo różne z tych trzech ostatnich, a na pewno
Ostatnie cztery jeśli to bogosort.
Oto pseudokod do seryjnej rodzaju.
Gdy na wejściu n elementów, więc biorąc pod uwagę Tablica wielkości n, gdy n jest mniejsze niż 2,
powrót.
Więc dlaczego mam, że rozsądek sprawdzić w pierwszej kolejności?
Co jest implikacja jeśli oddam ci Tablica o długości n jest mniejsze niż 2?
To już posortowane, oczywiście, prawda?
Ponieważ lista albo ma jeden element, który jest trywialny
sortowane, bo to Jedyne, co tam.
Albo, że to z wielkości zerowej, co oznacza, nie ma nic do sortowania, więc z natury
jest klasyfikowane.
Nie tylko nic złego nie.
Więc to jest nasza tzw wariant podstawowy.
>> Który jest podobny w duchu do tego, co zrobiliśmy z Mike.
Jeśli Mike w książce telefonicznej, zadzwonić do niego.
Jeśli go tam nie ma, zrezygnować.
To tak zwane bazowym, aby upewnić algorytm na koniec dnia
zatrzyma się w pewnych okolicznościach.
>> Ale tutaj jest skok wiary teraz, jeszcze, sortować lewą połowę elementów,
następnie posortować prawo połowa elementów
a następnie połączyć posortowane połówki.
I tu czuje jakbyśmy copping się.
Poprosiłem cię do sortowania n elementów, a ja jestem
mówiąc: OK, czy to przez sortowanie w lewo i prawo do sortowania.
Ale mówię jeden Inna rzecz, i to
jest kluczowym tematem wydaje się w intuicji dotąd
jest to trzeci etap łączenia.
Które, mimo to wydaje się tak głupie w duchu,
jak tylko połączyć rzeczy łącznie, wydaje
być kluczowym krokiem w kierunku ponowny montaż dwóch problemów, które
podzielono ostatecznie na pół.
>> Więc scalanie sortowanie, zróbmy to, jeśli będziesz humor mi, z jednej większej demonstracji,
po prostu tak, że mamy jakiś numery pracować.
Czy mogę wymienić osiem stres Piłki dla ośmiu osób?
Dobrze, jak o tobie trzy, to cztery w niniejszej sekcji, pięć, sześć, a niech
nie 7, 8, dalej w górę.
OK, tak OK.
Minus 8, tam idziemy plus 1.
Doskonałe.
Dobra chodź, niech szybko daje numery.
Numer dwa, numer trzy, numer cztery, numer pięć, sześć, siedem, osiem.
Zrobiłem osiem poprawnie tym razem.
>> OK, więc śmiało, jeśli można, i niech sortować w oryginalnej kolejności
że mieliśmy wczoraj który wyglądał tak, jeśli nie masz nic przeciwko.
I zróbmy to przed tabelą.
W porządku, więc scalić rodzaju.
To jest, gdzie to się dzieje aby uzyskać rodzaju ciekawych,
bo wydaje się dawać sobie więc dziś znacznie mniej informacji.
>> Więc łączyć przede wszystkim sortowania na wejściu n elementów,
i oczywiście nie mniej niż dwa, to osiem, więc mam jeszcze trochę do zrobienia.
Więc teraz my jako psychicznie klasy są obecnie w branży innego,
co oznacza, że ​​trzy kroki.
Po pierwsze, muszę uporządkować Lewa połowa elementów.
Więc jak mam to zabrać?
Cóż, mam zamiar trochę psychicznie podzielić listę tutaj,
nie masz do fizycznie przenieść, a ja jestem
zamiar skupić się tylko na lewa połowa tu elementów.
Więc jak mam go o sortowaniu lista teraz wielkości czterech?
Jaki jest mój algorytm?
Najpierw sprawdź to n mniej niż dwa, nie, więc przejść do bloku innego.
Sortuj opuścił połowę elementów.
>> Teraz znowu, psychicznie, i tam
należy zdobyć wiele Historia psychicznego, jeśli będzie.
Teraz jestem w lewo sortowania połowa lewej połowy.
Dobrze, więc teraz ja nazywam moją samą seryjnej algorytm sortowania, to N mniej niż dwa?
Nie, to jest dwa, więc mam do sortowania Lewa połowa i prawa połowa.
Więc zaczynamy, uporządkować lewą połowę.
Dlaczego nie można po prostu jeden krok do przodu.
Jak masz na imię?
>> PUBLICZNOŚCI: Darren.
>> Głośnik: Dan.
Dan podszedł.
>> PUBLICZNOŚCI: Darren.
Głośnik: Darren, zrobione.
Powiedziałeś Darren lub Dan?
>> PUBLICZNOŚCI: Darren.
>> Głośnik: Darren.
OK, Darren zwiększyła do przodu, a on jest teraz posortowana.
I to jest prawie idiotyczny zarzut, prawda?
I naprawdę nie wydaje się być osiągnięcie cokolwiek, ale przejdźmy.
Teraz pozwól mi uporządkować prawo połowa elementów.
Jak masz na imię?
>> PUBLICZNOŚCI: Luke.
>> Prelegent: Łukasz.
Chodź, krok do przodu.
Sporządzono, mam posortowane Luke.
Lewa połowa jest obecnie klasyfikowane i prawa połowa jest teraz posortowana,
ale znowu, jest kluczowym krokiem tutaj.
Czego potrzebujesz, aby zrobić następny?
Scalić posortowane połówki.
Teraz mamy zamiar po prostu wszyscy tam iz powrotem w ten sposób,
bo niby trzeba niektóre miejsca na zarysowania.
To prawie jak te faceci są na stole,
i potrzebuję trochę miejsca ich przenoszenie na.
Więc mam zamiar połączyć wy patrząc
w lewej i prawej połowie połowę.
I który oczywiście jest na pierwszym miejscu, w lewo lub w prawo, pół pół?
Więc prawa połowa, więc przejdźmy Luke nad do pierwotnej pozycji Darrena.
I teraz połączyć swoje lewą połowę w, Darren zamierza przenieść tam.
>> Więc czuje się jak prawie Efekt sortowanie bąbelkowe,
ale moim podstawowym algorytmem, bardzo różni się tym razem.
Ale teraz jest, gdy robi się trochę denerwujące, bo ciebie
trzeba przewinąć psychicznie Gdzie ja się.
Właśnie połączyła posortowane połówki, co oznacza, że ​​jestem, gdzie w moim algorytmie?
Muszę uporządkować prawą połowę, prawda?
>> Jeśli do tyłu, dosłownie na wideo, które będziesz
widać, że mamy do tego punkt Łukasza i Darrenem
sortując lewy połowa lewej połowy.
Potem połączył te posortowane połówki, które
oznacza, następnym krokiem jest sortowanie prawa połowa lewej połowy.
Dobrze, więc niech to zrobić szybciej.
Dobrze, sześć, idę zastrzeżenia jesteś teraz sortowane, dalej do przodu.
Jak masz na imię?
>> PUBLICZNOŚCI: Adriano.
>> Głośnik: Adriano.
Adriano jest teraz posortowana.
A jak masz na imię?
>> PUBLICZNOŚCI: Alex.
>> Głośnik: Alex jest teraz posortowana.
Lewa połowa, prawa połowa, co jest ostatnim krokiem?
Merge.
Dość banalna, więc jestem zamierza połączyć w sześciu,
zrobić krok do tyłu, osiem, zrobić krok do tyłu.
A teraz jest to zauważyć przydatne na wynos, co
jest prawdziwe w lewej połowie lista, niezależnie od tego, jak zaczęliśmy?
Jest klasyfikowane.
>> Teraz to nie jest klasyfikowane w duży schemat rzeczy,
ale są sortowane niezależnie z drugiej połowy.
Teraz co krok jestem na razie trzymam przewijania, jak zaczęła historia?
Teraz muszę uporządkować prawą połowę.
Tak więc teraz jesteśmy w drodze powrotnej początek historii,
i niech to zrobić szybciej.
Więc idę do sortowania prawa połowa całej listy.
Jaki jest następny krok?
Sortować lewą połowę prawej połowie.
Sortować lewą połowę Lewa połowa prawej połowy.
A jak masz na imię?
>> PUBLICZNOŚCI: Omar.
>> Głośnik: Omar, krok do przodu, zrobić.
Lewa połowa jest posortowana.
A jak masz na imię?
>> PUBLICZNOŚCI: Chris.
>> Głośnik: Chris, zrobić krok do przodu, jesteś teraz sortowane.
Co jest kluczowym krokiem teraz?
Merge.
Więc ktoś ma zamiar połączyć w miejscu tutaj, jeśli można zrobić krok do tyłu,
i trzeci jest zamiar zrobić krok do tyłu, łączenia.
Tak lewa połowa prawa połowa, jest teraz posortowana.
Szczerze mówiąc, ten algorytm jest jak my Marnujesz sposób więcej czasu niż wcześniej,
ale jeśli zrobił to w czasie rzeczywistym, to będzie zobaczyć, co będzie na wynos.
Teraz jestem tutaj, w prawo połowę prawą połowę
pozwól mi iść dalej i uporządkować lewą połowę.
Krok do przodu, jak masz na imię?
PUBLICZNOŚCI: Ramsey.
Głośnik: Ramsey jest teraz posortowana.
Jak masz na imię?
>> PUBLICZNOŚCI: Marina.
>> Prelegent: Marina jest obecnie klasyfikowane jako dobrze, jeśli wziąć jeden krok do przodu.
Kluczowym krokiem jest tu teraz połączyć, jestem zamierza zerwać z moich dwóch listach,
w lewo iw prawo.
Pięć przyjdzie pierwszy, i siedem przyjdzie następny.
I znowu, to jest celowe.
Fakt, że są one przy kilka kroków do przodu i tyłu
ma oznaczać, że nie możemy zrobić tego algorytmu w miejscu tak łatwo
jak sortowanie bąbelkowe i wyboru rodzaju, i wprowadzenie sortowania, gdzie tylko
przechowywane zamiana ludzi.
Dosłownie trzeba coś w rodzaju z papieru, w którym na zarysowania
umieścić tych ludzi a ja zrobić łączenie,
a następnie można umieścić je z powrotem na miejsce.
I to jest klucz, bo używam nowy zasób, przestrzeń, nie tylko czas.
>> OK, to jest niesamowite.
Lewa połowa jest posortowana, prawa połowa jest sortowane, teraz, że kluczem połączenia krok.
Jak mam połączyć to?
Więc jeśli będziesz śledzić moje Lewa ręka i prawa ręka,
Zamierzam zwrócić moją lewą rękę w lewej połowie, moja prawa ręka
na prawej połowie, a teraz muszę zdecydować, krok po kroku, do kogo się łączą w.
Który oczywiście jest na pierwszym miejscu?
Numer jeden.
Więc chodź tu, Oto nasz notatnik.
Więc teraz numerem jeden i zawiadomienia Co mam zrobić z moją prawą ręką,
Mam zamiar przenieść z jednej strony prawo krok nad wskazać numer trzy,
a teraz mam zrobić sama decyzja.
I faktycznie stanąć w prawo Przód Łukasza tutaj jeśli można,
bo to jest nasz notatnik.
Więc kto jest następny?
Mamy Łukasza z numerem dwa lub Chris z numerem trzy.
Oczywiście Łukasza, numer dwa, więc tu przyjść.
>> Ale teraz moja lewa ręka będzie być zwiększany, aby wskazać na Darrena,
i tu jest klucz zabrać ze połączenia, mam zamiar robić to,
Oczywiście, jeśli rodzaj z śledzić logikę.
Ale moje ręce nie są zamiar iść do tyłu,
co oznacza, że ​​ja nigdy nie porusza się tylko lewo z mojego procesu scalenia,
i że będzie kluczem do nasza analiza za chwilę.
>> Więc teraz niech to się szybko skończyć.
Więc trzy przychodzi następny, następnie cztery przychodzi następny,
a teraz pięć przychodzi następny, potem sześć, i siedem, a następnie w końcu osiem.
Czuje się jak najwolniejszy algorytm jeszcze, ale nie, jeśli rzeczywiście
uruchomić go w tym samym rodzaju z zegarem, tak aby
mówić o sam tykanie zegara, jak wcześniej.
Dlaczego?
Cóż, weźmy spojrzeć na wynik końcowy.
>> Wróćmy tutaj, niech mnie podciągnąć demonstrację wizualnie
z tego, co właśnie zrobiłeś.
Powiększanie tutaj, na tym strona tutaj, mówiąc Firefox
że chcemy stać w kolejce się w tym polu, niech
powiedzieć sortowania bąbelkowego, z których jesteśmy obecnie dobrze znane,
Wybór rodzaju, który jest innym dość proste jeden,
a teraz dzisiejsza seryjnej sortowanie, które będzie szczytowy nasz koniec.
Przyczyną tego, że trwało to tak długo tu z ludźmi, a ja mowie to,
oczywiście, ja tłumacząc każdy krok.
Ale jeśli po prostu wykonać to, o wiele jak my sortowanie bąbelkowe i wybór
sortowanie nie tylko wizualnie, zegarek , jak bardziej efektywnie
tego efektu dźwigni z podziału i podboju
może być stosowane, gdy w zestawie danych, który jest nawet wielkość ośmiu, a nawet znacznie,
znacznie większe.
Daję scalania sortowania, obok strona z innych algorytmów.
To będzie się bolesne szybko, a zakończenie
nie jest szczególnie szczytowy, po prostu skończyć sortowane.
Ale kluczem jest to, że na wynos Zobacz, jak wiele szybciej połączyć sortowania
było, chyba, że ​​myślisz, że jestem tylko rodzaj bawić się z tobą.
Jeśli robimy to po raz ostatni, Zróbmy Przeładuj, wróćmy
bubble rodzaj i wybierz, i tylko dla zabawy,
niech wybrać wstawianie sortowania, tak na dokładkę.
I tym razem znowu, niech wybierz seryjnej sortowanie i niech
faktycznie uruchomić te obok siebie.
>> I to nie jest, w rzeczywistości, fuks.
Co mam zrobić, to skutecznie mam dzieli moje wejście na pół, jeszcze raz,
i znowu, i znowu.
I nie tylko tak wiele razy ty może podzielić wejście na połówki, w lewo
i prawo.
Co znajduje się formuła, że ​​ciągle widzę , który opisuje podział w połowie
znowu, i znowu, i znowu, i znowu?
>> PUBLICZNOŚCI: log n.
>> Głośnik: log n.
Ale to nie jest jeszcze jeden krok klucz, algorytm ten nie jest log n kroków.
Jeśli to były tylko log n kroków, bylibyśmy w tym samym problemem
jak wcześniej, gdy nie możemy być że wszystko jest posortowane.
Musisz patrzeć na elementy minimalnie n aby upewnić się, n elementy są sortowane,
w przeciwnym razie jest to skok wiary.
>> Więc to jest minimalnie dziennika n kroków, ale co o tym kluczowym etapie scalenia
gdzie połączyła moja lewa i prawa połowa pół i chodził po scenie?
Ile kroków jest to, że aby połączyć?
To n, ale nie tylko scalić czas ostateczny.
Na każdej z tych zagnieżdżonych połączeń, na każde tych zagnieżdżonych scala, nadal klasyfikowane.
I połączyła tych dwóch facetów, to te dwa Chłopaki, to te dwa chłopaki i tak dalej.
>> Więc zrobiłem połączenie znowu, i znowu.
Ile razy?
I tak za każdym razem podzielone lista w połowie, zrobiłem seryjnej.
Podzielić listę na pół, do korespondencji seryjnej.
Więc jeśli dzieląc listę Można to zrobić razy log n,
i łączenie ostatecznie wykonuje n kroki, jakie mogą być teraz górna
związany z prowadzeniem Czas naszego algorytmu?
n log n.
>> I rzeczywiście, to właśnie udało nam się osiągnąć tutaj.
Więc uważasz, że wizualnie, gdy widzisz te trzy rzeczy uruchomić obok siebie
jest n do kwadratu na n kwadratu na n log n.
Które zasadniczo zobaczymy, Nie tylko, ale już w przyszłości
Jest o wiele szybciej.
Brawa dla tych facetów, Będę nagradzać je z kulkami stresu.
Miejmy odroczyć tu dzisiaj, i zobaczymy w poniedziałek.