[Powered by Google Translate] [Sekcja 3 - bardziej komfortowe]
[Rob Bowden - Harvard University]
>> [To jest CS50. - CS50.TV]
>> Więc pierwsze pytanie jest dziwnie sformułowane.
GDB pozwala "debugować" programu, a dokładniej, co to pozwala zrobić?
Odpowiem, że jeden, a ja nie wiem, co się dokładnie z oczekiwaniami,
więc zgaduję, że to coś na wzór tego pozwala krok po kroku
chodzić w ramach programu, interakcji z nią, zmienne zmienić, zrobić wszystkie te rzeczy -
w zasadzie całkowicie kontrolować wykonywania programu
i sprawdzić dowolną część realizacji programu.
Więc te funkcje pozwalają debugować rzeczy.
Okay.
Dlaczego poszukiwanie binarne wymagają array być posortowane?
Kto chce odpowiedzieć?
[Uczeń] Bo to nie działa, jeśli nie jest posortowane. >> Tak. [Śmiech]
Jeśli nie jest posortowane, a potem, że to niemożliwe, aby podzielić go na pół
i wiem, że wszystko, na lewo jest mniej i wszystko w prawo
jest większa niż wartość środkowa.
Więc musi być sortowane.
Okay.
Dlaczego jest sortowanie bąbelkowe w O n kwadratu?
Czy ktoś najpierw chce dać bardzo szybki przegląd na wysokim poziomie, co sortowanie bąbelkowe jest?
[Uczeń] Jesteś zasadniczo przejść przez każdy element i sprawdzić kilka pierwszych elementów.
Jeśli są z którym zamienić je, a następnie sprawdzić kilka następnych elementów i tak dalej.
Gdy dojdziesz do końca, to wiesz, że największy element jest umieszczony na końcu,
więc ignorować, że jeden potem dalej przechodzi,
i za każdym razem trzeba sprawdzić jeden mniej elementu dopóki nie wprowadzi zmian. >> Tak.
To się nazywa sortowanie bąbelkowe bo jeśli odwrócić tablicę na boku, więc jest w górę iw dół, pionowy,
wówczas duże wartości będzie opadają na dno, a małe wartości będą bubble do góry.
Tak to ma swoją nazwę.
I tak, po prostu przejść.
Ciągle przechodzi tablicy, zamiana większą wartość
, aby uzyskać największe wartości dolnej.
>> Dlaczego jest to O n kwadratu?
Po pierwsze, czy ktoś chce powiedzieć, dlaczego to O n do kwadratu?
[Uczeń] Ponieważ na każdym biegu idzie n razy.
Można być pewnym, że już podjęte była największym elementowi w dół,
następnie trzeba powtórzyć, że dla tak wielu elementów. >> Tak.
Pamiętaj więc, co big O oznacza i co oznacza duże Omega.
Big O to jak górna granica jak wolno może rzeczywiście działać.
Tak więc, mówiąc, że to O n. kwadratu, to nie jest O n albo będzie w stanie uruchomić
w czasie liniowym, ale do sześcianu O n
ponieważ jest ograniczony przez O n sześcienny.
Jeśli jest ograniczony przez O n kwadratu, to jest to ograniczone również przez n do sześcianu.
Więc to jest n do kwadratu, w absolutnej najgorszym wypadku nie można zrobić lepiej niż n kwadratów,
dlatego, że to wy z n do kwadratu.
Tak więc, aby zobaczyć, w jaki sposób nieznaczny matematyki to wychodzi się n do kwadratu,
jeśli mamy pięć rzeczy w naszej liście, pierwszy raz, jak wiele możemy swaps potencjalnie trzeba uczynić
aby otrzymać? Miejmy właściwie tylko -
Ile swapy będziemy musieli zrobić w pierwszej serii sortowanie bąbelkowe w tablicy?
[Uczeń] n - 1. >> Tak.
>> Jeśli są 5 elementów, będziemy potrzebować do n - 1.
Następnie na drugim ile swapy będziemy musieli zrobić?
[Uczeń] n - 2. >> Tak.
I trzeci będzie N - 3, a następnie dla wygody będzie napisać dwóch ostatnich
jak wtedy będziemy potrzebować, aby 2 swapy i 1 SWAP.
Chyba ostatnia może lub nie może faktycznie trzeba się zdarzyć.
Czy wymiany? Nie wiem.
Więc to są łączne kwoty transakcji swap lub przynajmniej porównanie masz zrobić.
Nawet, jeśli nie zamienić, trzeba jeszcze, aby porównać wartości.
Tak więc istnieje n - 1 porównań w pierwszej serii przez tablicę.
Jeśli zmienić te rzeczy, niech zarabia na sześć rzeczy, więc rzeczy stos ładnie,
i zrobię 3, 2, 1.
Więc po prostu przekształcenie tych kwot, chcemy zobaczyć, jak wiele porównań dokonujemy
w całym algorytmu.
Więc jeśli wprowadzą te chłopaki tu,
to mamy jeszcze tylko podsumowanie jednak wiele porównań były.
Ale jeśli podsumować te i podsumować te i podsumować te,
To wciąż ten sam problem. My po prostu sumować tych szczególnych grup.
>> Więc teraz podsumowując 3 n-tych. To nie jest tylko 3 n-tych.
To zawsze będzie n / 2 n-tych.
Mamy tu więc zdarzy się, że 6.
Gdybyśmy mieli 10 rzeczy, to możemy zrobić to ugrupowania 5 różnych par rzeczy
i kończy się z n + n + n + n + n.
Więc zawsze dostanie n / 2 n, a więc to my jot go do n do kwadratu / 2.
A więc nawet jeśli jest to czynnik pół, co zdarza się w
ze względu na to, że za pomocą każdego iteracji przez tablicy 1 mniej porównać
tak to w jaki sposób dostać się na 2, ale wciąż jest n do kwadratu.
Nie dbamy o stały współczynnik o połowę.
Tak wiele dużych rzeczy O tak zależy tylko rodzaju robi ten rodzaj matematyki,
robi sum arytmetycznych i geometrycznych rzeczy serii,
ale większość z nich w tym kursie są dość oczywiste.
Okay.
Dlaczego sortowania wstawiania Omega n? Co omega oznacza?
[Dwóch studentów mówiących naraz - niezrozumiały] >> Tak.
Omega możesz myśleć jak dolna granica.
>> Tak więc bez względu na to, jak skuteczne Twój algorytm sortowania wstawiania jest,
niezależnie od tego, który jest na liście przyjętej w, to zawsze musi porównać co najmniej n rzeczy
lub musi iterować n rzeczy.
Dlaczego tak jest?
[Uczeń] Bo jeśli lista jest już posortowana, potem przez pierwsze powtórzenie
można jedynie zagwarantować, że pierwszy element jest najmniej,
i drugiej iteracji można gwarantować jedynie dwa pierwsze są
bo nie wiesz, że reszta listy są sortowane. >> Tak.
Jeśli przechodzą w zupełnie sortowanie listy, przynajmniej masz iść na wszystkie elementy
widząc, że nic nie trzeba przemieszczać.
Więc pomijając listę i mówią oh, to jest już posortowane,
niemożliwe jest, aby wiedzieć, to posortowane aż sprawdzić każdy element
aby zobaczyć, że są one w uporządkowanej kolejności.
Więc dolną granicę sortowanie wstawiania jest Omega n.
Co w najgorszym przypadku czas pracy sortowanie korespondencji seryjnej,
w najgorszym przypadku jest O wielkie jeszcze raz?
Tak więc w najgorszym przypadku, w jaki sposób sort merge uruchomić?
[Uczeń] N log n. >> Tak.
Najszybsze ogólne algorytmy sortowania są n log n. Nie można zrobić lepiej.
>> Istnieją szczególne przypadki, a jeśli mamy czas dziś - ale prawdopodobnie won't -
możemy zobaczyć jeden, który nie lepiej niż n log n.
Jednak w ogólnym przypadku nie można zrobić lepiej niż n log n.
I scalania sort bywa jeden należy wiedzieć na ten kurs, który jest n log n.
I tak będziemy faktycznie wykonywania tego dzisiaj.
I wreszcie, w nie więcej niż trzech zdaniach, jak działa sort wyboru?
Czy ktoś chce odpowiedzieć, a ja liczyć swoje wyroki
bo jeśli iść na 3 -
Czy ktoś pamięta rodzaju selekcja?
Sort wybór jest zazwyczaj dość łatwe do zapamiętania tylko z nazwy.
Po prostu iteracyjne nad tablicy znaleźć cokolwiek największa wartość jest lub najmniejszy -
cokolwiek by pan sortowania w.
Powiedzmy więc, że mamy do sortowania od najmniejszych do największych.
Iteracyjne nad tablicy, szukamy jakiegoś minimum elementem,
zaznacz go, a następnie po prostu zamienić, co jest na pierwszym miejscu.
, A następnie w drugim przejściu nad tablicy, szukać minimalnym elementem ponownie
zaznacz go, a następnie zamień go z tym co jest na drugiej pozycji.
Więc to tylko wybór, minimalne wartości
i wkładanie ich do przodu, aż do tablicy jest sortowany.
Pytania na temat tego?
>> To nieuchronnie pojawiają się w formach trzeba wypełnić, gdy jesteś złożeniem PSET.
Są to w zasadzie odpowiedzi na te.
Ok, więc teraz kodowanie problemów.
Już wysłane na e-mail - Czy nikt uzyskać e-mail? Okay.
Już wysłane na e-mail przestrzeń, że będziemy się przy użyciu,
i po kliknięciu na moje nazwisko - tak myślę, że będzie na dnie
ze względu na wsteczną r - ale jeśli klikniesz na moje nazwisko zobaczysz 2 wersje.
Wersja 1 zostanie już kopiować i wklejać kod do przestrzeni
na rzecz wyszukiwania będziesz mieć do wykonania.
Wersja 2 i będzie rzeczą sort że realizujemy po.
Więc możesz kliknąć na mojej wersji 1 i pracować tam.
A teraz chcemy zaimplementować wyszukiwania binarnego.
>> Czy ktoś chce się po prostu dać pseudokod wysokiego szczebla wyjaśnienie
z tego, co zamierzamy zrobić dla wyszukiwania? Tak.
[Uczeń] Wystarczy wziąć środek tablicy i zobaczyć, czy to, czego szukasz
jest mniejsza niż lub więcej.
A jeśli jest to mniej, idziesz do połowy, która jest mniejsza,
i jeśli jest więcej, można przejść do pół to więcej i powtórzyć, że aż po prostu jedno.
[Bowden] Tak.
Zauważ, że nasza tablica liczby jest już posortowane,
i tak, że to oznacza, że ​​możemy skorzystać z tego i możemy najpierw sprawdzić,
okay, szukam numeru 50.
Więc mogę iść do środka.
Bliski jest trudne do zdefiniowania, kiedy jest jeszcze wiele rzeczy,
ale powiedzmy, my zawsze obciąć do środka.
Więc tutaj mamy 8 rzeczy, więc środek będzie 16.
Szukam 50, więc 50 jest większa niż 16.
Więc teraz mogę w zasadzie traktuję tablicy jako tych elementów.
Mogę wyrzucić wszystko z 16 powyżej.
Teraz moja tablica jest po prostu te 4 elementy, powtarzam.
Więc chcę, aby znaleźć środek ponownie, co będzie 42.
42 jest mniejsza niż 50, więc mogę wyrzucić te dwa elementy.
To jest moja pozostała tablica.
Zamierzam znaleźć środek ponownie.
Chyba 50 był zły przykład, bo zawsze wyrzucać rzeczy, na lewo,
ale przez sam środek, jeśli szukam czegoś
i jest to mniej niż element Jestem obecnie patrzysz,
potem zamierzam wyrzucić wszystko do prawej.
Więc teraz musimy wdrożyć to.
Zauważ, że musimy przekazać w wielkości.
Nie możemy również muszą ciężko wielkości kodu.
Więc jeśli pozbędziemy się, że # define -
Okay.
Jak można dowiedzieć się, co ładnie rozmiar tablicy numerów jest obecnie?
>> Ile elementów znajduje się w tablicy liczb?
[Animacja] Liczby, wsporniki,. Długość?
[Bowden] To nie istnieje w języku C.
Potrzebujesz. Długość.
Tablice nie posiadają właściwości, więc nie ma właściwość length tablicy
że będzie po prostu dać Ci jednak długo zdarza się.
[Uczeń] Zobacz, ile pamięci ma i podzielić przez ile - >> Tak.
Więc jak możemy zobaczyć, ile pamięci ma? >> [Uczeń] sizeof. >> Tak, sizeof.
Sizeof jest operatorem, który zamierza powrócić na rozmiar tablicy numerów.
I że będzie to jednak wiele liczb całkowitych istnieją razy rozmiar integer
ponieważ jest to ilość pamięci to faktycznie podejmowania.
Więc jeśli chcesz, wiele rzeczy w tablicy,
następnie będę chciał podzielić przez wielkość liczby całkowitej.
Okay. Tak, że pozwala mi przejść w rozmiarze tutaj.
Dlaczego muszę przechodzić w wielkości w ogóle?
Dlaczego nie można po prostu zrobić tutaj int size = sizeof (stóg siana) / sizeof (int)?
Dlaczego to nie działa?
[Uczeń] Nie globalna zmienna jest.
[Bowden] Haystack istnieje i jesteśmy przechodząc w ilościach stogu siana
i jest to swego rodzaju zapowiedzią tego, co nadchodzi. Tak.
[Uczeń] Haystack jest tylko odniesienie do niej, więc byłoby wrócić jak duży, że odniesienie jest.
Tak.
Wątpię w wykładzie, który widziałem stos jeszcze bardzo, prawda?
Właśnie mówili o tym.
Więc stos jest gdzie wszystkie zmienne zostaną zapisane.
>> Każde wspomnienie, które jest przeznaczone dla zmiennych lokalnych dzieje w stosie,
i każda funkcja dostaje swoją własną przestrzeń na stos, jego własne ramki stosu jest to, co się nazywa.
Więc główny ma swoje ramki stosu, a wewnątrz niego istnieć będzie tę tablicę numerów,
i to będzie z sizeof wielkości (numery).
To będzie mieć wielkość liczb podzielonych według wielkości elementów,
ale wszystkie mieszka w ramce stosu funkcji main.
Gdy dzwonimy wyszukiwanie, wyszukiwarka ma swój własny ramki stosu,
własnego miejsca do przechowywania wszystkich swoich zmiennych lokalnych.
Ale te argumenty - tak stóg nie kopię tej całej tablicy jest.
Nie przekazujemy w całej tablicy jako kopia do wyszukiwania.
To po prostu przechodzi przez odniesienie do tej tablicy.
Więc wyszukiwania może dostęp do tych numerów przez ten odnośnik.
To wciąż dostępu do rzeczy, które żyją wewnątrz ramki stosu funkcji main,
ale w zasadzie, kiedy dotrzemy do wskaźników, które powinny być szybko,
to, co wskaźniki są.
Wskaźniki są tylko odniesienia do rzeczy, i można użyć wskaźników dostępu do rzeczy
które są w ramkach innych rzeczy "komin.
Więc nawet jeśli liczba jest lokalny główny, nadal możemy uzyskać do niego dostęp za pomocą tego wskaźnika.
Ale ponieważ jest to tylko wskaźnik, a to tylko odniesienie,
sizeof (stóg siana) po prostu zwraca wielkość odsyłającego.
Nie zwraca wielkość rzeczy to wskazuje.
Nie zwraca rzeczywisty rozmiar liczb.
I tak to nie będzie działać jak my chcemy.
>> Pytania na temat tego?
Wskaźniki zostaną szczegółowo włożono znacznie bardziej krwawym w tygodniach.
I dlatego wiele rzeczy, które widzisz, większość rzeczy wyszukiwania lub rzeczy sortowania,
oni prawie wszystko będzie trzeba podjąć rzeczywisty rozmiar tablicy,
bo w C, nie mamy pojęcia, co rozmiar tablicy jest.
Trzeba ręcznie przenieść go w.
I nie można ręcznie przekazać w całej tablicy, bo jesteś tylko przejazdem w odwołaniu
i nie można uzyskać rozmiaru z odniesienia.
Okay.
Więc teraz chcemy zaimplementować co wyjaśniono wcześniej.
Można pracować na nim przez chwilę,
i nie musisz martwić się o wszystko idealnie 100% pracy.
Wystarczy napisać do Pseudokod pół dla jak myślisz powinno działać.
Okay.
Nie trzeba być całkowicie wykonane z tym jeszcze.
Ale czy ktokolwiek czuł się komfortowo z tym, co do tej pory,
jak coś możemy pracować razem?
Czy ktoś chce zostać wolontariuszem? Lub będzie losowo wybierać.
To nie musi być w porządku pod każdym względem, ale coś możemy zmodyfikować do stanu roboczego.
[Uczeń] Jasne. >> Okay.
Więc można zapisać zmiany, klikając na małą ikonę Zapisz.
Jesteś Ramya, prawda? >> [Uczeń] Tak. >> [Bowden] Dobra.
Więc teraz mogę zobaczyć swoją wersję i każdy może wyciągnąć rewizji.
I tu mamy - Dobra.
Więc Ramya poszedł z rekurencyjnej rozwiązaniu, które jest na pewno ważne rozwiązanie.
Istnieją dwa sposoby, które można zrobić z tym problemem.
Można to zrobić iteracyjnie lub rekurencyjnie.
Większość problemów można napotkać, że można zrobić rekurencyjnie można zrobić iteracyjnie.
Więc zrobiliśmy to rekurencyjnie.
>> Czy ktoś chce zdefiniować, co to znaczy, aby funkcja rekurencyjna?
[Uczeń] Kiedy masz funkcję wywoła się
i skontaktować się aż wychodzi z prawdą i prawda. >> Tak.
Funkcja rekurencyjna to tylko funkcja, która zwraca się.
Istnieją trzy wielkie rzeczy, że funkcja rekurencyjna musi mieć.
Pierwszy jest oczywiście, że wzywa się.
Drugi wariant podstawowy.
Więc w pewnym momencie funkcja musi przestać nazywać siebie,
i to, co jest dla bazowym.
Więc wiemy, że należy się zatrzymać, należy zrezygnować w poszukiwaniu
podczas startu wynosi koniec - i pojedziemy nad tym, co to znaczy.
Ale w końcu, ostatnią rzeczą, że to ważne dla funkcji rekurencyjnych:
funkcje musi jakoś podejść do sprawy podstawowej.
Lubię, jeśli nie masz nic faktycznie aktualizacji podczas dokonywania sekundy wywołanie rekurencyjne,
jeśli jesteś dosłownie wywołanie funkcji ponownie z tymi samymi argumentami
i nie zmienne globalne zmieniło czy coś,
nigdy nie dotrze do przypadku bazowego, w tym przypadku, że jest źle.
To będzie nieskończonej rekurencji i przepełnienie stosu.
Ale tutaj widzimy, że aktualizacja się dzieje ponieważ aktualizujemy rozpocząć + End / 2,
mamy aktualizację argument kończy się tutaj, jesteśmy aktualizacji argument Kliknij tutaj.
Tak więc we wszystkich rekurencyjnych wywołań Aktualizujemy coś. Okay.
Chcesz iść z nami przez Twojego rozwiązania? >> Jasne.
Używam SearchHelp tak, że za każdym razem robię to wywołanie funkcji
Mam początek gdzie szukam w tablicy i koniec
, gdzie szukam tablicy.
>> Na każdym kroku, gdzie jest to, mówiąc, że to środkowy element, który jest start + end / 2,
jest równa, co szukasz?
A jeśli tak jest, to okazało się to, i myślę, że zostanie przeniesiony do poziomów rekursji.
A jeśli to nie jest prawda, to musimy sprawdzić, czy środkowa wartość w tablicy jest zbyt duża,
w tym przypadku patrzymy na lewej połowie tablicy przechodząc od początku do środkowym indeksu.
I inaczej robimy pół zakończenia.
[Bowden] Dobra.
To brzmi dobrze.
Ok, więc kilka rzeczy, i rzeczywiście, jest to bardzo wysoki poziom, co
że nigdy nie będzie trzeba wiedzieć o tym oczywiście, ale to jest prawda.
Funkcje rekurencyjne, zawsze słyszę, że są one złe ofertę
bo jeśli nazywasz siebie rekurencyjnie zbyt wiele razy, można uzyskać przepełnienie stosu
ponieważ, jak powiedziałem wcześniej, każda funkcja ma swój własny ramki stosu.
Więc każde wywołanie rekurencyjnej funkcji otrzymuje własną ramkę stosu.
Więc jeśli się 1.000 rekurencyjnych wywołań, dostajesz 1.000 stosu ramki,
i szybko można doprowadzić do zbyt wielu ramek stosu i miejscach po prostu złamać.
Więc dlatego funkcje rekurencyjne są na ogół złe.
Ale jest ładny podzbiór funkcji rekurencyjnych nazywa tail-rekurencyjnych funkcji,
a to akurat jest przykładem jednego gdzie jeśli kompilator napotka na
i powinien, jak sądzę - w Clang jeśli podajesz go flag-O2
to będzie to zauważyć, jest ogon recursive i zrobić rzeczy dobre.
>> Będzie używać tego samego ramki stosu kółko każdego rekurencyjnego wywołania.
I tak, ponieważ używasz tego samego ramki stosu, nie musisz się martwić o
coraz stosu brzegi, a w tym samym czasie, tak, jak wspomniano wcześniej,
gdzie kiedyś wrócisz prawda, to musi wrócić do tych wszystkich ramek stosu
oraz 10. wywołanie SearchHelp musi powrócić do 9, ma, aby powrócić do 8..
Tak, że nie musi się zdarzyć, gdy funkcje są ogon rekurencyjne.
A więc to, co sprawia, że ​​ta funkcja tail recursive jest zauważyć, że dla każdego zaproszenia do searchHelp
wywołanie rekurencyjne, że robi to, co to jest powrót.
Tak więc w ramach pierwszego zaproszenia do SearchHelp, to albo natychmiast zwróci false,
niezwłocznie zwróci true, lub robimy wywołania rekurencyjnego SearchHelp
gdzie co mamy powrót co, że połączenie jest powrót.
I nie mogliśmy tego robić, jeśli zrobiliśmy coś int x = SearchHelp, return x * 2,
tylko niektóre losowo zmiana.
>> Więc teraz to wywołanie rekurencyjne, to int x = SearchHelp wywołanie rekurencyjne,
nie jest już ogon recursive ponieważ rzeczywiście ma powrócić
Powrót do poprzedniej ramki stos, tak że do poprzedniego połączenia funkcji
może wtedy coś z wartości zwracanej.
Więc to nie ogon recursive jest, ale to, co mieliśmy przed jest ładnie ogon rekurencyjne. Tak.
[Uczeń] nie powinno sekund bazowym zostać najpierw sprawdzone
bo nie może być sytuacji, w której podczas przekazywania jej argumentu
masz zacząć = koniec, ale są one wartość igła.
Pytanie nie możemy uruchomić w przypadku, gdy koniec jest wartość igła
lub uruchom = koniec, odpowiednio, start = koniec
i nie zostały faktycznie sprawdziliśmy, że szczególną wartość jeszcze,
uruchom + End / 2 jest tylko będzie taka sama wartość.
Ale my już zwróciło fałszywe i nigdy rzeczywiście sprawdził wartość.
Więc przynajmniej w pierwszej rozmowy, jeśli rozmiar jest 0, to chcemy, aby powrócić false.
Ale jeśli rozmiar jest 1, a następnie start nie będzie równego końca,
a my przynajmniej sprawdzić jeden element.
Ale myślę, że masz rację, że możemy skończyć w przypadku, gdy rozpoczęcie + End / 2,
początek kończy się takie same, jak uruchomianie końcowego / 2
ale nigdy tak naprawdę sprawdzić ten element.
>> Jeśli więc najpierw sprawdzić, jest środkowym elementem wartości szukamy,
wtedy możemy natychmiast zwróci true.
Inaczej, jeśli są równe, to nie ma sensu w kontynuowaniu
ponieważ jesteśmy po prostu będzie zaktualizować do przypadku, w którym jesteśmy na tablicy pojedynczego elementu.
Jeśli to pojedynczy element, nie ten, którego szukamy jest
wtedy wszystko jest w porządku. Tak.
[Uczeń] jest to, że od wielkości, jest rzeczywiście większa niż liczba elementów w tablicy,
istnieje już offset - >> Tak będzie rozmiar -
[Uczeń] Powiedz jeśli tablica był rozmiar 0, a następnie SearchHelp rzeczywiście sprawdzić stogu siana 0
pierwszego połączenia.
Tablica ma rozmiar 0, więc 0 jest - >> Tak.
Jest jeszcze jedna rzecz, która - może być dobry. Zastanówmy się.
Więc jeśli tablica miała 10 elementów i środkowy będziemy sprawdzać to index 5,
jesteśmy więc sprawdzenie 5, a powiedzmy, że wartość jest mniejsza.
Więc jesteśmy rzucając wszystko od 5 wzwyż.
Więc zacznij + end / 2 będzie nasz nowy koniec,
więc tak, to zawsze tam na pobyt poza koniec tablicy.
Jeśli to przypadek, czy to parzyste lub nieparzyste, to możemy sprawdzić, powiedzmy, 4,
ale nadal wyrzucać -
Więc tak, koniec jest zawsze będzie poza aktualne końca tablicy.
Więc elementów skupiamy się, koniec jest zawsze będzie jeden po.
A jeśli tak nie zawsze równy początek końca, jesteśmy w tablicy o rozmiarze 0.
>> Inna sprawa, to myślałem, że aktualizujemy początek należy uruchomić + End / 2,
więc to jest tak, że mam problemy z, gdzie start + End / 2
jest elementem sprawdzamy.
Powiedzmy, że mieliśmy tego 10-tablicy. Cokolwiek.
Więc zacznij + end / 2 będzie coś jak to,
a jeśli nie jest to wartość, że chcemy, aby zaktualizować.
Wartość jest większa, więc chcemy patrzeć na to pół tablicy.
Więc jak mamy aktualizację początek, mamy aktualizację początek teraz ten element.
Ale to może nadal działać, lub co najmniej, można zrobić początek + koniec / 2 + 1.
[Uczeń] Nie trzeba zacząć + END [niesłyszalne] >> Tak.
Mamy już sprawdzony ten element i wiem, że nie jest jedynym, którego szukamy.
Tak więc nie trzeba aktualizować zaczynają być ten element.
Możemy po prostu pominąć i aktualizacji rozpocznie się ten element.
I jest tam kiedykolwiek przypadek, powiedzmy, że to był koniec,
tak, to będzie to początek, zacznij + End / 2 będzie to,
rozpocząć + END - Tak, myślę, że to może skończyć się w nieskończonej rekursji.
Powiedzmy, że jest to po prostu tablica wielkości 2 lub tablicy o wielkości 1. Myślę, że to będzie działać.
Tak więc obecnie, jest to, że początek i koniec elementu jest 1 poza nią.
Tak więc element, który mamy zamiar sprawdzić jest ten jeden,
a następnie, gdy aktualizujemy start, jesteśmy aktualizacji zaczynają być 0 + 1/2,
który skończy się nam z powrotem zacząć się ten element.
>> Więc sprawdzamy ten sam element w kółko.
Więc to jest przypadek, w którym każdy wywołanie rekurencyjne muszą faktycznie zaktualizować coś.
Więc trzeba zrobić początek + End / 2 + 1, albo tam sprawa
gdzie nie faktycznie aktualizowanie start.
Każdy widzi?
Okay.
Czy ktoś ma pytania dotyczące tego rozwiązania lub komentarze więcej?
Okay. Czy ktoś ma rozwiązanie iteracyjne, że wszyscy możemy patrzeć?
Czy my wszyscy go rekurencyjnie?
Albo też myślę, że jeśli otworzył jej, to możesz mieć przesłonięte poprzedniego.
Czy to automatycznie zapisać? Nie jestem pewien.
Czy ktoś ma iteracyjną?
Możemy przejść przez to razem, jeśli nie.
Pomysł będzie taki sam.
Iteracyjnego rozwiązania.
Będziemy chcieli zrobić w zasadzie ten sam pomysł
gdzie chcemy śledzić nowej końca tablicy i nowy początek tablicy
i zrobić to w kółko.
A jeśli, co mamy śledzenie jako początek i koniec zawsze przecinają się,
wówczas nie znaleźliśmy go i możemy powrócić false.
Więc jak mam to zrobić? Ktoś ma sugestie lub kod dla mnie, by podciągnąć?
[Student] Czy pętlę while. >> Tak.
Będziesz chcą zrobić pętlę.
>> Czy masz kod mogłem wyciągnąć, czy co chciałeś zasugerować?
[Uczeń] Myślę, że tak. >> Dobrze. To sprawia, że ​​łatwiej. Co było na imię?
[Uczeń] Lucas.
Wersja 1. Okay.
Niski jest to, co nazywa się rozpocząć wcześniej.
Up nie jest całkiem co nazwaliśmy koniec wcześniej.
Faktycznie, koniec jest teraz w tablicy. To element powinien rozważyć.
Jest tak niskie, 0, jest się rozmiar tablicy - 1
i teraz jesteśmy pętli, jak również sprawdza -
Myślę, że można przez nie przejść.
Jakie było Twoje myślenie przez to? Spacer z nami przez kodzie.
[Uczeń] Jasne. Sprawdź wartość stogu siana w środku i porównaj je igłą.
Więc jeśli jest większy niż igły, a następnie chcesz - oh, faktycznie, że powinno być odwrotnie.
Będziesz chcą wyrzucić prawą połowę, a więc tak, to powinno być mowy.
[Bowden] Więc to powinno być mniej? Czy to, co pan powiedział? >> [Uczeń] Tak.
[Bowden] Dobra. Mniej.
Więc jeśli to czego szukamy w jest mniejszy niż to, co chcemy,
to tak, chcemy wyrzucić lewą połowę,
co oznacza, że ​​aktualizujemy wszystko mówimy o
niskie przesuwając na prawo tablicy.
To wygląda dobrze.
Myślę, że ma ten sam problem, że powiedział na poprzedniej,
gdzie jeśli niski jest 0 i wyżej jest 1, to niski + up / 2 będzie ustawiony jako samo ponownie.
>> I nawet jeśli to nie jest przypadek, to jest jeszcze bardziej wydajny przynajmniej
po prostu wyrzucić element po prostu spojrzał na którym wiemy, że jest źle.
Tak niskie + up / 2 + 1 - >> [uczeń] To powinno być inaczej.
[Bowden] albo powinno to - 1, a druga należy + 1.
[Uczeń] I nie powinno być podwójne znaku równości. >> [Bowden] Tak.
[Uczeń] Tak.
Okay.
I wreszcie, że teraz mamy tego + 1 - 1 rzecz,
jest to - to nie może być - jest to zawsze możliwe, niskie do końca się z wartości większej niż up?
Myślę, że tylko w ten sposób może się zdarzyć - Czy to możliwe? >> [Uczeń] I nie wiem.
Ale jeśli to ma obcięty i następnie dostaje minus, że 1, a następnie - >> Tak.
[Uczeń] To może się zawiedli.
Myślę, że powinno być dobre tylko dlatego, że
bo do końca się niższe musiałyby one być równe, tak myślę.
Ale jeśli są one równe, to nie zrobiłby podczas pętli na początek
i po prostu by się zwróciło wartość. Więc myślę, że jesteśmy dobrzy teraz.
Należy zauważyć, że nawet jeśli nie jest problemem rekurencyjne,
samego rodzaju pomysłów zastosowania, gdy widzimy, jak to tak łatwo nadaje się
do rekurencyjnego roztworu przez to, że jesteśmy po prostu aktualizuje indeksy w kółko,
robimy problemu mniejsze, skupiamy się na podzbiorze tablicy.
[Tablica] Jeśli jest niska jest do 0 i 1, to one być 0 + 1/2, które go do 0,
i jeden będzie + 1, jeden będzie - 1.
[Uczeń] Gdzie my sprawdzenie równości?
Lubię gdy środkowy jest faktycznie igła?
Nie jesteśmy obecnie robi? Oh!
Jeśli it's -
Tak. Nie możemy po prostu zrobić test na dół, bo powiedzmy pierwszej połowie -
[Uczeń] To faktycznie jak nie wyrzucać przywiązani.
Więc jeśli wyrzucić bound, trzeba go najpierw sprawdzić czy cokolwiek innego.
Ah. Tak. >> [Uczeń] Tak.
Więc teraz mamy wyrzucać tego, ale aktualnie patrzy,
co oznacza, że ​​teraz trzeba mieć
if (stóg [(niski + up) / 2] == igły), to możemy wrócić true.
I czy mogę umieścić indziej lub po prostu wtedy, gdy oznacza to dosłownie to samo
ponieważ byłoby to zwróciło true.
Więc Powiem else if, ale to nie ma znaczenia.
>> Więc jeśli jeszcze to, jeszcze to, i to jest wspólne, co robię
gdzie nawet jeśli jest to przypadek, w którym wszystko jest dobre tutaj,
jak nisko nigdy nie może być większa niż w górę, nie warto o tym, czy rozumowanie, że to prawda jest.
Tak więc, jak można powiedzieć, a również niskie jest mniejsza niż lub równa
lub gdy jest mniejsza niż niskiej
więc jeśli kiedykolwiek równa lub niskie zdarza, żeby odpuścić,
to możemy wyjść z tej pętli.
Pytania, problemy, komentarze?
Okay. To wygląda dobrze.
Teraz chcemy zrobić sortowanie.
Jeśli idziemy do mojego drugiego przeglądu, widzimy te same numery,
ale teraz już nie są w uporządkowanej kolejności.
I chcemy realizować przy użyciu dowolnego rodzaju algorytmu w O n log n.
Więc który algorytm myślisz powinniśmy wdrażać tutaj? >> [Uczeń] sort Merge.
[Bowden] Tak. Merge sort jest O (n log n), więc to, co będziemy robić.
A problem będzie bardzo podobne,
gdzie łatwo nadaje się do rozwiązania rekurencyjnej.
Możemy również wymyślić iteracyjnego rozwiązania, jeśli chcemy,
ale rekurencja będzie łatwiej tu i powinniśmy zrobić rekursji.
Chyba będziemy chodzić przez sortowanie seryjnej pierwszy,
choć nie jest to piękny film na sortowanie seryjnej już. [Śmiech]
Więc seryjnej sortowanie Nie - Jestem tracić tak dużo tej pracy.
Och, jest tylko jeden.
Więc seryjnej.
O, 1, 3, 5.
Okay.
Merge ma dwa osobne tablice.
Indywidualnie te dwie tablice są zarówno posortowane.
Więc ta tablica, 1, 3, 5, sortowane. Ta tablica, 0, 2, 4, posortowane.
Teraz to, co należy zrobić, to merge połączyć je w jednej tablicy, która sama jest posortowane.
Więc chcemy tablicę wielkości 6, które ma mieć te elementy w jej wnętrzu
w uporządkowanej kolejności.
>> I tak możemy skorzystać z faktu, że te dwie tablice są sortowanie
to zrobić w czasie liniowym,
liniowy znaczenie czas, jeśli tablica jest x rozmiar i to jest y rozmiar,
a następnie powinien być całkowita Algorytm O (x + y). Okay.
Więc sugestie.
[Student] Czy możemy zacząć od lewej strony?
Więc umieścić 0 w dół, a potem 1 i tutaj jesteś w 2.
Więc to jest trochę jak masz kartę, która porusza się w prawo. >> [Bowden] Tak.
Dla obu tych tablic, jeśli po prostu skupić się na skrajnym lewym elemencie.
Ponieważ obie tablice są sortowane, wiemy, że te 2 elementy
Są to najmniejsze elementy obu macierzy.
To znaczy, że 1 2 tych elementów muszą być w naszym najmniejszy element połączonego tablicy.
Tak się składa, że ​​najmniejszy jest jedno po prawej tej chwili.
Więc bierzemy 0, włóż go na lewo, ponieważ 0 jest mniejsza niż 1,
więc wziąć 0, włóż ją do naszej pierwszej pozycji, a potem zaktualizować to
do skoncentrowania się obecnie na pierwszym elemencie.
A teraz mamy powtórzyć.
Więc teraz porównaj 2 i 1. 1 jest mniejszy, więc będziemy wstawiać 1.
Aktualizujemy ten wskaźnik, aby wskazywał tego faceta.
Teraz możemy zrobić to jeszcze raz, więc 2. Spowoduje to aktualizację, porównać te 2, 3.
Aktualizuje, potem 4 i 5.
Więc to jest merge.
>> Powinno być oczywiste, że jest to czas liniowy ponieważ wystarczy przejść przez każdego elementu raz.
I to jest największy krok do realizacji sort merge to robi.
I to nie jest takie trudne.
Kilka rzeczy się martwić o to, powiedzmy byliśmy połączenie 1, 2, 3, 4, 5, 6.
W tym przypadku kończy się w sytuacji, w której ten ktoś ma zamiar być mniejsze,
potem aktualizować ten wskaźnik, ten będzie mniejszy, zaktualizować to
ten jest mniejszy, a teraz trzeba uznać
kiedy już rzeczywiście zabraknie elementów do porównania z.
Skoro już z całą tę tablicę,
wszystko w tej tablicy jest teraz po prostu wstawiony tutaj.
Więc jeśli kiedykolwiek biegać do punktu, w którym jeden z naszych tablic jest całkowicie połączyła się już,
a następnie po prostu się wszystkie elementy drugiej tablicy i umieścić je w koniec tablicy.
Więc może po prostu wstawić 4, 5, 6. Okay.
To jest jedna rzecz, aby uważać.
Wykonawcze, które powinny być krokiem 1.
Scalanie sortować następnie na tej podstawie, to 2 kroki, 2 głupie kroki.
Miejmy tylko dać tej tablicy.
Więc seryjnej sortowanie, krok 1 jest rekurencyjnie złamać tablicę do połowy.
Więc podzielić tę tablicę na połówki.
Mamy obecnie 4, 15, 16, 50 i 8, 23, 42, 108.
A teraz możemy to zrobić ponownie i dzielimy je na połówki.
Po prostu będzie to zrobić na tej stronie.
Tak więc 4, 15 i 16, 50.
Chcemy zrobić to samo tutaj.
A teraz mamy podzielić ją na pół ponownie.
I mamy 4, 15, 16, 50.
Więc to jest nasza sprawa bazy.
Po tablice są wielkości 1, to kończy się na podziale na połówki.
>> Teraz co mamy z tym zrobić?
Mamy w końcu będzie to również dzielą się na 8, 23, 42 i 108.
Więc teraz, że jesteśmy w tym miejscu, teraz krok dwa sortowanie korespondencji seryjnej jest tylko łączenie par do wykazów.
Dlatego chcemy, aby połączyć te. Po prostu zadzwoń seryjnej.
Wiemy merge zwróci je w uporządkowanej kolejności.
4, 15.
Teraz chcemy to połączyć i że zwróci listę z tymi, w uporządkowanej kolejności,
16, 50..
Łączymy te - nie mogę pisać - 8, 23 i 42, 108.
Więc mamy scalonych par raz.
Teraz musimy połączyć ponownie.
Należy zauważyć, że każdy z tych list jest sortowana w sobie,
a może po prostu połączyć te listy, aby uzyskać listę wielkości 4, która jest posortowana
i połączyć te dwie listy, aby uzyskać listę wielkości 4, które są sortowane.
I wreszcie, możemy połączyć te dwie listy wielkości 4, aby uzyskać jeden wykaz wielkości 8, które są sortowane.
Tak więc, aby zobaczyć, że jest to całkowita n log n, już zobaczył, że merge jest liniowy,
tak, gdy mamy do czynienia z połączenia tych, więc jak całkowity koszt scalenia
dla obu tych list jest tylko 2, bo -
Albo dobrze, to O n, ale n tutaj jest tylko te 2 elementy, więc to 2.
A te 2 będą 2 i te 2 będą 2 i te 2 będą 2,
więc po wszystkich scala, które musimy zrobić, to w końcu robi n.
Jak 2 + 2 + 2 + 2 jest 8, który jest N,
więc koszt połączenia w zestawie jest N.
, A następnie to samo tutaj.
Będziemy łączyć te 2, to te 2 i indywidualnie to merge weźmie cztery operacje,
to merge weźmie cztery operacje, ale po raz kolejny, pomiędzy tym wszystkim,
kończymy połączenie n suma rzeczy, a więc ten krok zajmuje n.
I tak każdy poziom ma n elementów zostały połączone.
>> A ile poziomy są tam?
Na każdym poziomie, nasza tablica rośnie o wielkości 2.
Tutaj nasze tablice są wielkości 1, tutaj są wielkości 2, tutaj są wielkości 4,
i wreszcie, że są wielkości 8.
Tak więc, ponieważ jest dwukrotnie, nie będą łącznie log N tych poziomach.
Więc z log n poziomów, każdy poziom przy n suma operacji,
otrzymujemy log n n algorytm.
Pytania?
Czy ludzie już poczyniła postępy w zakresie sposobu realizacji tego?
Czy ktoś jest już w stanie, w którym można po prostu wyciągnąć swój kod?
Mogę dać chwilę.
Ten będzie dłuższy.
Gorąco polecam powtórzy -
Nie musisz robić rekursji do scalenia
bo zrobić rekursji dla korespondencji seryjnej, będziesz musiał przejść kilka różnych rozmiarach.
Można, ale jest to denerwujące.
Ale rekursji dla rodzaju sam w sobie jest całkiem proste.
Wystarczy dosłownie nazwać swego rodzaju na lewej połowie, sortowanie na prawej połowie. Okay.
Każdy ma coś można podciągnąć jeszcze?
Albo dam minut.
Okay.
Ktoś ma coś, co możemy pracować?
Albo będziemy po prostu pracować z tym, a następnie rozwiń stamtąd.
>> Każdy, kto ma więcej niż to, że można wyciągnąć?
[Uczeń] Tak. Można podciągnąć moją. >> Dobrze.
Tak!
[Uczeń] Było wiele warunków. >> Och, strzelać. Można -
[Uczeń] Mam go zapisać. >> Tak.
Więc zrobiliśmy scalania oddzielnie.
Oh, ale to nie jest tak źle.
Okay.
Więc sort jest sama po prostu wywołanie mergeSortHelp.
Wyjaśnij nam co mergeSortHelp robi.
[Uczeń] MergeSortHelp prawie robi dwa główne etapy,
które jest do sortowania każdej połowie tablicy, a następnie połączenie ich obu.
[Bowden] Okay, więc daj mi chwilę.
Myślę, że to - >> [uczeń] muszę -
Tak. Brakuje mi czegoś.
W korespondencji seryjnej, zdaję sobie sprawę, że trzeba utworzyć nową tablicę
ponieważ nie mogłem zrobić to na miejscu. >> Tak. Nie możesz. Poprawić.
[Uczeń] Więc utworzyć nową tablicę.
Zapomniałem w końcu łączą się ponownie zmienić.
Okay. Potrzebujemy nowej tablicy.
W sortowanie korespondencji seryjnej, to prawie zawsze prawdziwe.
Część kosztów lepszego algorytmu mądrej czasu
jest prawie zawsze konieczności użycia nieco więcej pamięci.
Więc, nie ważne jak to zrobić scalania sortowanie,
byś nieuchronnie trzeba użyć trochę więcej pamięci.
On lub ona stworzyła nową tablicę.
I wtedy można powiedzieć na koniec, że wystarczy skopiować nową tablicę do oryginalnej tablicy.
[Uczeń] Myślę, że tak.
Nie wiem, czy to działa w zakresie liczenia przez odniesienie lub cokolwiek -
Tak, to będzie działać. >> [Uczeń] Dobra.
Czy spróbować uruchomić to? >> [Uczeń] Nie, jeszcze nie. >> Okay.
Spróbuj uruchomić go, a następnie porozmawiam o tym przez chwilę.
[Uczeń] Muszę mieć wszystkie prototypy funkcji i wszystko, prawda?
Prototypy funkcji. Och, masz na myśli - Tak.
Sortuj dzwoni mergeSortHelp.
>> Tak, aby rodzaj, aby zadzwonić mergeSortHelp, mergeSortHelp musi albo zostały zdefiniowane
przed sortowanie lub po prostu potrzebujesz prototyp. Po prostu skopiuj i wklej to.
I podobnie, mergeSortHelp dzwoni połączenie,
ale seryjnej nie został jeszcze określony, więc możemy po prostu pozwolić mergeSortHelp wiedzieć
że to co łączyć będzie wyglądać, i to jest to.
Więc mergeSortHelp.
Mamy problem, tu, gdzie nie mamy przypadek bazowy.
MergeSortHelp jest cykliczne, więc każda funkcja rekurencyjna
będzie potrzebować jakiegoś przypadku bazowego wiedzieć kiedy przestać rekurencyjnie nazywając siebie.
Co jest naszym bazowym będzie tutaj? Tak.
[Uczeń] Jeśli rozmiar jest 1? >> [Bowden] Tak.
Tak jak widzieliśmy tam, zatrzymaliśmy dzielenie tablic
gdy dotarliśmy na tablice o rozmiarze 1, co nieuchronnie są posortowane siebie.
Więc jeśli rozmiar wynosi 1, wiemy, tablica jest już posortowane,
więc możemy po prostu wrócić.
>> Zauważ, że jest nieważna, więc nie zwraca niczego szczególnego, po prostu wrócić.
Okay. Więc to jest nasza sprawa bazy.
Chyba naszym przypadku baza może być również, jeśli zdarzy nam się łączyć tablicę wielkości 0
zapewne chce się zatrzymać w pewnym momencie,
tak więc można powiedzieć, o rozmiarze mniejszym niż 2 lub mniej niż lub równe 1
tak, że to będzie działać dla każdej tablicy teraz.
Okay.
Więc to jest nasza sprawa bazy.
Teraz chcesz iść z nami przez seryjnej?
Co wszystkie te przypadki oznaczają?
Tutaj, po prostu robi to sam pomysł, -
[Uczeń] I trzeba przechodząc rozmiar wszystkich połączeń mergeSortHelp.
I dodaje rozmiar jako dodatkowy podstawowych i go tam nie ma, podobnie jak rozmiar / 2.
[Bowden] Oh, rozmiar / 2, rozmiar / 2. >> [Uczeń] Tak, jak również w wyżej, jak również funkcji.
[Bowden] Tutaj? >> [Uczeń] Just rozmiar. >> [Bowden] Oh. Rozmiar, rozmiar? >> [Uczeń] Tak.
[Bowden] Dobra.
Niech pomyślę o sekundy.
Czy możemy uruchomić do problemu?
Jesteśmy zawsze traktując lewo jako 0. >> [Uczeń] L.
To jest złe też. Przepraszam. Powinien być początek. Tak.
[Bowden] Dobra. Podoba mi się to lepiej.
I koniec. Okay.
Więc teraz chcesz iść z nami przez seryjnej? >> [Uczeń] Dobra.
Jestem po prostu chodzenie po tej nowej tablicy, który stworzyłem.
Jej rozmiar jest wielkość części tablicy, że chcemy być sortowane
i próbuje znaleźć element, który należy umieścić w nowym kroku tablicy.
Tak więc, aby to zrobić, najpierw sprawdza, czy jestem lewa połowa tablicy nadal masz więcej elementów,
a jeśli nie, to idź do tego innego stanu, który tylko mówi
okay, to musi być w dobrym tablicy, a my umieścić, że w bieżącym indeksie newArray.
>> A następnie w przeciwnym wypadku jestem sprawdzania czy prawa strona tablicy jest również zakończona,
w takim przypadku po prostu umieścić w lewej.
W rzeczywistości, że może nie być konieczne. Nie jestem pewien.
Ale tak czy inaczej, dwa pozostałe sprawdzić, które z tych dwóch są mniejsze w lewo lub w prawo.
, A także w każdym przypadku, jestem inkrementacji zależności zastępczy I przyrost.
[Bowden] Dobra.
To wygląda dobrze.
Czy ktoś ma uwagi lub wątpliwości lub pytania?
Więc czterech spraw, które musimy przynieść rzeczy do po prostu - a wygląda na to, pięć -
ale musimy rozważyć, czy lewa tablica zabrakło rzeczy musimy się łączyć,
czy prawo array zabrakło rzeczy musimy scalić -
Jestem wskazując na nic.
Tak czy lewa tablica zabrakło rzeczy lub prawa tablica zabrakło rzeczy.
To są dwa przypadki.
Potrzebujemy także trywialny przypadek czy lewo rzeczą jest mniejsza niż dobrze.
Następnie chcemy wybrać lewy rzeczy.
To są przypadki.
Więc to było w porządku, więc to jest to.
Array lewo. Jest 1, 2, 3,. Okay. Więc tak, to są cztery rzeczy, może chcemy zrobić.
A my nie będziemy w iteracyjnego rozwiązania.
Nie polecam -
Scalanie sortowania jest przykład funkcji, która jest zarówno nie tail recursive,
to nie jest łatwe do wykonania go tail recursive,
ale nie jest to bardzo łatwe do wykonania go wielokrotnie.
To jest bardzo proste.
Ta implementacja sortowanie korespondencji seryjnej,
seryjnej, nie ważne co robisz, masz zamiar zbudować scalania.
>> Więc scalić sort zbudowany na seryjnej rekurencyjnie jest tylko te trzy linie.
Iteracyjnie, to jest bardziej denerwujące i trudniej myśleć.
Zauważmy jednak, że to nie jest ogon recursive od mergeSortHelp - gdy nazywa się -
nadal musi robić rzeczy po tym rekurencyjnych zwróceniu.
Więc ta ramka stosu musi nadal istnieć nawet po wywołaniu tego.
A potem, kiedy będzie się nazywać, ramka stosu musi nadal istnieć
bo nawet po tej samej rozmowy, wciąż musimy scalić.
I to wcale trywialne, aby ten ogon rekurencyjne.
Pytania?
Dobrze.
Więc wracając do sortowania - oh, nie dwie rzeczy, które chcesz pokazać. Okay.
Wracając do rodzaju, zrobimy to szybko.
Lub wyszukiwania. Sortuj? Sortuj. Tak.
Wracając do początków rodzaju.
Chcemy stworzyć algorytm, który sortuje tablicy przy użyciu dowolnego algorytmu
w O n.
Więc jak to jest możliwe? Czy ktoś ma jakiś rodzaj -
Wspomniałem wcześniej o -
Jeśli mamy zamiar poprawić z N log N-O n,
musimy poprawić naszą algorytm time-mądry,
co oznacza, że ​​co my będzie trzeba zrobić, aby się na to?
[Uczeń] Space. >> Tak. Będziemy używać więcej miejsca.
I nawet nie tylko więcej miejsca, to wykładniczo więcej miejsca.
Więc myślę, że tego typu algorytmu jest pseudo coś wielomian pseudo -
pseudo - ja nie pamiętam. Pseudo coś.
Ale to dlatego, że musimy użyć tak wiele miejsca
To, że jest możliwe, ale nie realne.
>> I w jaki sposób to osiągnąć?
Możemy to osiągnąć, jeśli mamy gwarancję, że jakiś szczególny element w tablicy
jest poniżej pewnego rozmiaru.
Więc powiedzmy, że rozmiar to 200,
każdy element tablicy jest poniżej rozmiar 200.
I to jest rzeczywiście bardzo realistyczne.
Można bardzo łatwo mieć tablicę, że wiesz wszystko, co w nim
będzie poniżej pewnej liczby.
Lubię, jeśli masz jakieś absolutnie ogromny wektor lub coś
ale wiesz, wszystko będzie między 0 i 5,
wtedy będzie to znacznie szybciej to zrobić.
I związany na każdym z elementów jest 5
więc to ograniczenie, to ile pamięci masz zamiar używać.
Tak związany jest 200.
W teorii jest zawsze związany z całkowitą od może wynosić do 4 mld
ale to jest nierealne, ponieważ wtedy bylibyśmy wykorzystania przestrzeni
w postanowieniu z dnia 4 mld euro. Więc to jest nierealne.
Ale tutaj powiemy naszym związany jest 200.
Sztuczka robi to w O n to robimy kolejną tablicę o nazwie zliczenia wielkości związane.
Właściwie, jest to skrót - Ja naprawdę nie wiem, czy Clang to robi.
Ale w GCC przynajmniej - Jestem Clang zakładając robi to też -
to będzie tylko zainicjować całą tablicę być 0s.
Więc jeśli nie chcesz tego robić, wtedy będę mógł oddzielnie zrobić for (int i = 0;
i <BOUND; i + +) i liczy [i] = 0;
Więc teraz wszystko jest inicjowane na 0.
I iteracyjne nad mojej tablicy,
i to, co robię, jest mi liczenie każdego - Chodźmy na dół.
Mamy 4, 15, 16, 50, 8, 23, 42, 108.
Co Liczę jest liczba wystąpień każdego z tych elementów.
Miejmy rzeczywiście dodać jeszcze kilka tutaj z niektórych powtórzeń.
Tak więc mamy tu wartość, wartość, która ma być tablica [i].
Więc val może być 4 lub 8 lub cokolwiek.
A teraz liczę, ile z tej wartości widziałem,
to liczy [Val] +;
Po wykonaniu tej operacji, liczy będzie wyglądać podobnie jak 0001.
Zróbmy liczy [wartość] - Bound + 1.
>> Teraz to tylko do odpowiedzialności za to, że zaczynamy od 0.
Więc jeśli 200 będzie nasza największa liczba,
następnie 0 do 200 to 201 rzeczy.
Więc liczy się, to będzie wyglądać jak 00001, ponieważ mamy jeden 4.
Wtedy będziemy mieli 0001, gdzie będziemy mieć 1 w 8. indeksu count.
Będziemy mieć 2 w 23. indeksu count.
Będziemy mieć 2 w indeksie 42-te hrabiego.
Więc możemy użyć count.
Więc num_of_item = liczy [i].
A jeśli tak jest num_of_item 2, co oznacza, że ​​chcemy wstawić 2 liczby i.
do naszego posortowanej tablicy.
Musimy więc śledzić, jak daleko jesteśmy do tablicy.
So = index 0.
Array - ja po prostu pisać.
Counts -
tablica [indeks + +] = i;
Czy to, co chcę? Myślę, że to, co chcę.
Tak, to wygląda dobrze. Okay.
Więc nie wszyscy rozumieją, jaki jest cel mojej tablicy liczy jest?
Liczy liczby wystąpień każdego z tych numerów.
Wtedy jestem iteracja tej tablicy liczy,
i-ty pozycji w tablicy liczy
jest liczba i to, które powinny pojawić się w moim posortowanej tablicy.
Dlatego liczy się z 4 będzie 1
i hrabiowie 8 będzie 1, liczy się od 23 będzie 2.
Więc tak jak wielu z nich chcę wstawić do mojej posortowanej tablicy.
Potem po prostu to zrobić.
Jestem włożeniem num_of_item i nic mi do posortowanej tablicy.
>> Pytania?
I znowu, to jest czas liniowy, ponieważ jesteśmy tylko iterowanie raz,
ale jest również liniowa, co ta liczba bywa,
i tak mocno zależy na tym, co związane jest.
Z związaną z 200, to nie jest tak źle.
Jeśli związany będzie 10.000, to jest trochę gorzej,
ale jeśli związany będzie 4 mld to kompletnie nierealne
i ta tablica będzie miała być wielkości 4 miliardów, co jest nierealne.
Więc to jest to. Pytania?
[Niesłyszalne reakcja studentów] >> Ok.
Uświadomiłem sobie jedną rzecz, kiedy przechodziliśmy.
Myślę, że problemem było w Lucasa i chyba każdy jeden widzieliśmy.
Zupełnie zapomniałem.
Jedyne co chciałem skomentować to, że gdy masz do czynienia z rzeczy jak indeksów
nigdy tak naprawdę nie zobaczyć, kiedy piszesz do pętli,
ale technicznie, gdy masz do czynienia z tych indeksów
należy prawie zawsze do czynienia z liczb całkowitych bez znaku.
Powodem tego jest to, gdy masz do czynienia z podpisanych liczb całkowitych,
więc jeśli masz 2 podpisane liczby całkowite i dodać je razem
i kończy się zbyt duży, to możesz skończyć z liczby ujemnej.
Więc to, co jest przepełnienie całkowitoliczbowe.
>> Jeśli dodać 2 miliardy, a 1 mld zł, I skończyć z ujemnym 1 miliarda euro.
W ten sposób całkowite pracować na komputerach.
Więc problem z użyciem -
To jest w porządku, chyba że dzieje się niski 2 mld euro a nawet zdarza się 1 mld
to ta będzie ujemna 1 miliard, a następnie jedziemy do podziału, że 2
i kończy się z ujemnej 500 mln EUR.
Więc jest to tylko problem, jeśli zdarzy ci się być na przeszukiwaniu tablicy
miliardów rzeczy.
Ale jeśli niski + up dzieje się przelewem, to jest to problem.
Tak szybko, jak my je niepodpisane, to 2 miliardy plus 1 mld 3 mld euro.
3 miliardów podzielone przez 2 jest 1,5 mld euro.
Tak szybko, jak one są niepodpisane, wszystko jest idealne.
A więc to jest również kwestia, kiedy jesteś pisania dla pętli,
i faktycznie, to pewnie robi to automatycznie.
To właściwie tylko krzyczeć na Ciebie.
Więc jeśli ta liczba jest zbyt duża, aby być tylko liczbą całkowitą, ale byłoby to zmieścić w unsigned integer,
będzie krzyczeć na ciebie, więc dlatego tak naprawdę nie napotkasz problemu.
Można zobaczyć, że indeks nie będzie ujemny,
i tak, gdy jesteś iteracja tablicy
można prawie zawsze mówią unsigned int i, ale naprawdę nie trzeba.
Wszystko będzie działać prawie tak samo dobrze.
Okay. [Szepcze] Która godzina?
Ostatnią rzeczą, chciałem pokazać - a ja po prostu to zrobić bardzo szybko.
Wiesz, jak mamy # define więc możemy # define MAX jako 5, czy coś?
Nie róbmy MAX. # Define PRZESTRZEGANIE jak 200. To, co zrobiliśmy wcześniej.
Która definiuje stałe, które jest tylko będzie kopiowane i wklejane
gdziekolwiek się napisać związany.
>> Tak naprawdę możemy zrobić więcej # definiuje.
Możemy # define funkcji.
Oni nie są tak naprawdę funkcji, ale my nazywamy ich funkcje.
Przykładem może być coś jak MAX (x, y) jest zdefiniowana jako (x <y y: x). Okay.
Więc należy się przyzwyczaić do składni operatora trójskładnikowych
ale x mniejsze od y? Powrót y, else return x.
Więc widać, można zrobić tego oddzielną funkcję,
a funkcja może być jak bool MAX ma 2 argumenty, zwrócić.
Jest to jedna z najczęstszych z nich widzę uczyniły tak. Nazywamy je makr.
To makro.
To jest tylko składnia dla niego.
Można napisać makro robić, co chcesz.
Jesteś często zobaczyć makr do debugowania printfs i rzeczy.
Więc typu printf, istnieją specjalne stałe w C jak podkreślają LINE podkreślenia,
2 podkreśla LINE podkreślenia,
i jest tam także myślę, że 2 podkreślenia FUNC. To może być to. Coś w tym stylu.
Te rzeczy zostanie zastąpiony nazwą funkcji
lub numer linii, na której jesteś.
Często piszesz debugowania printfs że tu mogę po prostu pisać
DEBUG i będzie drukować numer linii i funkcji, które zdarza mi się być w
że spotkałem takiego oświadczenia DEBUG.
Można także wydrukować inne rzeczy.
Więc jedna rzecz, należy zwrócić uwagę na to, jeśli zdarzy mi się # define DOUBLE_MAX
za coś takiego jak 2 * y, a 2 * x.
Więc dla powodu czegokolwiek, zdarzy ci się zrobić wiele.
Więc zrób to makro.
To jest rzeczywiście uszkodzony.
Nazwałbym go coś jak DOUBLE_MAX (3, 6).
Więc co należy zwrócić?
[Uczeń] 12.
Tak, 12 powinien być zwrócony, a 12 jest zwracana.
3 jest zastępowany dla x, 6 zostanie zastąpiony na y, a wracamy 2 * 6, czyli 12.
Teraz to, co na ten temat? Co powinno zostać zwrócone?
[Uczeń] 14. >> Idealnie 14.
Problemem jest to, że jak hash definiuje pracę, pamiętaj, że jest to dosłowne kopiowanie i wklejanie
wszystkiego dość dużo, więc co to ma być interpretowane jako
jest 3 mniej niż 1 plus 6, 2 razy 1 plus 6, 2 razy 3.
>> Więc z tego powodu prawie zawsze zawinąć wszystko w nawiasach.
Każda zmienna prawie zawsze zawinąć w nawiasach.
Istnieją przypadki, kiedy nie trzeba, tak jak wiem, że nie muszę tego robić tutaj
bo mniej niż jest to prawie zawsze po prostu się do pracy,
chociaż to może nawet nie być prawdą.
Jeśli coś jest śmieszne jak DOUBLE_MAX (1 == 2),
wtedy, że zamierza się zastąpić 3 mniej niż 1 równa jest równa 2,
i tak to jest to zrobić 3 mniejsza niż 1, to się równa 2,
co jest nie to, co chcemy.
Dlatego aby uniknąć ewentualnych problemów pierwszeństwa operatora,
zawsze zawinąć w nawiasach.
Okay. I to, 5:30.
Jeśli masz jakieś pytania dotyczące PSET, daj nam znać.
Powinno być zabawne, a także wydanie haker jest bardziej realistyczny
niż wydanie hakerów zeszłorocznego, więc mamy nadzieję, że wielu z was spróbować.
Ostatni rok był bardzo przytłaczające.
>> [CS50.TV]