[MUZYKI] 

PROFESOR: Wszystko w porządku. Jest CS50 i jest po trzech tygodnia. Więc jesteśmy tu dzisiaj, nie w Sanders Teatr, a nie w Weidner Biblioteki. Wewnątrz której znajduje się studio znany jako Hauser Studio, lub powiemy Studio H, lub powinien mamy say-- Jeśli korzystają ten dowcip, to faktycznie od kolega, Mark, on-line, który zasugerował nawet za pośrednictwem Twittera. Teraz to, co jest fajnego będąc tutaj w studio jest to, że jestem otoczony przez te zielone ściany, zielony ekran lub chromakey, że tak powiem, co oznacza, że ​​CS50 na zespół produkcyjny, nie wiemy o mnie teraz, może być wprowadzenie mnie najbardziej na całym świecie, na lepsze lub na gorsze. 

Teraz to, co jest przed nami, ustawić problemem dwóch jest w Twoich rękach w tym tygodniu, ale z problemu ustawić trzy w nadchodzącym tygodniu będzie prowokacji tak zwana gra 15, stary partia łaska, że Może pamiętacie odbioru jako dziecko, że ma całą masę wartości, które mogą przesuwać się w górę, w dół, w lewo i prawo, a jest jedna szczelina w układanki, do którego może rzeczywiście przesunąć tych puzzli. Ostatecznie otrzymasz ten list puzzle w jakimś pół kolejności losowej, a celem jest rozwiązać to, od góry do dołu, od lewej do prawej, z jednego aż do góry do 15. 

Niestety, realizacja będziesz miał pod ręką będzie oprogramowanie opiera, nie fizycznie. Jesteś rzeczywiście będzie musiał napisać Kod z którymi student lub użytkownik może gry w 15. I rzeczywiście, w hakera edycja gry 15, musisz być wyzwaniem do realizacji, nie tylko gry z tej starej szkoły gry, ale raczej rozwiązywanie o tym, wdrażanie God Mode, że tak powiem, że rzeczywiście rozwiązuje zagadkę dla człowieka, poprzez zapewnienie im wskazówkę, po nutą, po podpowiedź. Więc więcej o tym następnym tygodniu. Ale to, co nas czeka. 

Na razie przypomnieć, że wcześniej w tym tygodniu mieliśmy ten cliffhanger, jeśli chcesz, przy czym najlepiej robiliśmy sortowania Mądry był górnej granicy Big O n do kwadratu. Innymi słowy, sortowanie bąbelkowe, Wybór rodzaju, Sortowanie przez wstawianie, wszystkie z nich, podczas gdy inna w ich realizacji, przekazane do n do kwadratu działa czas, w najgorszym przypadku. I na ogół zakładamy, że najgorszym przypadku sortowania to taki, który swoje wejścia są całkowicie do tyłu. I rzeczywiście, zajęło sporo kroki do realizacji każdego z tych algorytmów. 

Teraz na samym końcu klasy Przypomnijmy, że w porównaniu z bąbelkami rodzaju wobec wyboru rodzaju wobec siebie nawzajem które nazwaliśmy sortowanie przez scalanie w czasie, i proponuję, to biorąc Zaletą lekcji z tygodnia zero, dziel i rządź. I jakoś osiągnięcia pewnego rodzaju logarytmiczna czas pracy ostatecznie a nie coś to czysto kwadratowa. I to nie dość, logarytmiczna, to trochę więcej. Ale jeśli pamiętam z lekcji, jest to o wiele szybciej. Rzućmy okiem na którym skończyliśmy. 

Sortowanie bąbelkowe kontra wyboru Sortuj kontra sortowanie przez scalanie. Teraz oni wszyscy działa w teorią, w tym samym czasie. CPU obraca się z tą samą prędkością. Ale możesz czuć się jak nudne to jest bardzo szybko stanie się, i jak szybko, kiedy wstrzyknąć nieco algorytmów tygodniu Zero, możemy przyspieszyć. 

Więc znak swego wygląda niesamowicie. Jak możemy wykorzystać go w celu szybciej sortować numery. No pomyślmy powrotem do substancji, które miał z powrotem w tygodniu zerowym, że od szukając kogoś w książce telefonicznej, i przypomnieć, że pseudokod, który zaproponowaliśmy, za pomocą której można znaleźć ktoś taki jak Mike Smith, wyglądał na trochę coś takiego. 

Teraz spójrz w szczególności w linii 7 i 8 oraz 10 i 11, które wywołują tę pętlę, w której trzymaliśmy powrót do linii 3 znowu, i znowu, i jeszcze raz. Ale okazuje się, że możemy zobaczyć ten algorytm, tu w Pseudokod, trochę bardziej całościowo. W rzeczywistości, czego szukam w tutaj na ekranie jest algorytm poszukiwania Mike Smith wśród jakiegoś zestawu stron. I rzeczywiście, możemy uprościć ten Algorytm w tych liniach 7 i 8, oraz 10 i 11, aby po prostu powiedzieć, że to, które prezentowane tutaj mam na żółto. Innymi słowy, jeśli Mike Smith jest wcześniej w książce, nie musimy określić krok po kroku, teraz jak go poszukać. Nie mamy do określenia aby wrócić do linii 3, Dlaczego nie możemy po prostu, a nie, powiedzieć, ogólnie, szukaj Mike w Lewa połowa książki. 

I odwrotnie, jeśli Mike faktycznie później w książce, dlaczego nie możemy po prostu cytatu wyszukiwanie Mike'a w prawej połowie książki. Innymi słowy, dlaczego nie możemy po prostu rodzaj punt do siebie, mówiąc: szukaj Mike to podzbiorem książki, i pozostawić do naszych obecnych Algorytm nam powiedzieć jak szukać Mike że lewa połowa książki. Innymi słowy, nasze Algorytm działa, czy jest to książki telefonicznej tej grubości, to Grubość lub dowolnej grubości ogóle. Więc możemy rekursywnie zdefiniowanie tego algorytmu. Innymi słowy, na Ekran tutaj, jest algorytmem do poszukiwania Mike Smith wśród stronach książki telefonicznej. Tak więc w linii 7 i 10, niech tylko powiedzieć dokładnie to. I używam tego określenia chwilę temu, i rzeczywiście, rekurencja jest modne teraz, i to jest ten proces zrobić coś cyklicznego przez jakiś za pomocą kodu, który już masz, i nazywając go ponownie, i znowu, i znowu. Teraz to będzie ważne że jakoś na dole , i nie rób tego nieskończenie długo. W przeciwnym razie będziemy mają rzeczywiście nieskończoną pętlę. Ale zobaczymy, czy możemy pożyczyć ten pomysł z rekurencji, znów robi coś i znowu i znowu, aby rozwiązać Problem sortowania przez scalanie sortowania, bardziej efektywnie. 

Więc dam ci sortowanie przez scalanie. Spójrzmy. Więc tutaj jest pseudokod, z które moglibyśmy wdrożyć sortowania, za pomocą tego algorytmu o nazwie sortowanie przez scalanie. I jest to po prostu to. Na wejściu elementów n, innymi słowy, jeśli jesteś podane n elementów i numerów oraz litery lub cokolwiek pomiarowej, jeśli podane elementy n, jeśli n jest mniejsze niż 2, po prostu wrócić. Dobrze? Dlatego, gdy n jest mniejsze niż 2, który Oznacza to, że moja lista elementów albo o rozmiarze 0 i 1, a W obu tych trywialne przypadkach lista jest już posortowana. Jeśli nie ma listy, jest klasyfikowane. A jeśli istnieje lista długości 1, jest to oczywiście klasyfikowane. Tak algorytm musi jedynie Naprawdę coś ciekawego, jeśli mamy dwa lub więcej Elementy nam dany. Więc spójrzmy na magii wtedy. Jeszcze uporządkować lewą połowę elementów, następnie posortować prawą połowę elementów, następnie scalić posortowane połówki. A co to za umysłu gięcia tutaj jest to, że tak naprawdę nie Wydaje się, że mówiłem coś jeszcze, prawda? Wszystko, co powiedziałem jest, biorąc pod uwagę listę n elementów, posortować lewą połowę, a następnie w prawo w połowie, a następnie scalić posortowane połówki, ale gdzie jest rzeczywista tajne sos? Gdzie jest algorytm? Cóż okazuje się, że tych dwóch linii Pierwszy, jakby opuścił połowę elementów, i prawa połowa sortowania elementów, są wywołania rekurencyjne, że tak powiem. 

Po tym wszystkim, w tym punkt w czasie, mam algorytm, z którymi się sortować całą masę elementów? Tak. To właśnie tutaj. To tutaj, na ekranie, a więc mogę korzystać z tego samego zestawu kroków sortowanie lewą połowę, jak mogę prawa połowa. I rzeczywiście, jeszcze raz, i jeszcze raz. Więc tak czy inaczej, a my wkrótce zobaczyć, magię sortowanie przez scalanie jest osadzony w które bardzo ostateczna linii, łączących posortowane połówki. I to wydaje się dość intuicyjne. Weź dwie połówki, a ci, jakoś połączyć je ze sobą, i zobaczymy to konkretnie w jednej chwili. 

Ale to jest kompletny algorytm. I zobaczmy, dlaczego. Przypuszczać, że dostaniemy te same Tutaj osiem elementów na ekranie, jeden przez osiem lat, ale są w celu pozornie losowej. A cel w zasięgu ręki jest posortować te elementy. Cóż, jak można przejść o robi to za pomocą znowu sortowanie przez scalanie, jak na tym Pseudokod? I znowu, zakorzeniony w tym w twój umysł, na chwilę. Pierwszy przypadek jest dość trywialne, jeśli jest mniejsza niż 2, po prostu wrócić, nie ma do zrobienia. Tak naprawdę istnieje tylko trzy Kroki, aby naprawdę mieć na uwadze. Znowu, i znowu, jestem będzie chciał mieć sortowanie lewą połowę, sortować prawą połowę, a następnie po ich dwie połówki są klasyfikowane, Chcę połączyć je razem w jednym posortowanej listy. Miejcie to na uwadze. 

Więc tutaj jest oryginalna lista. Miejmy traktują to jako tablica, jak zaczęliśmy W każdym tygodniu, co jest ciągły blok pamięci. W tym przypadku, zawiera osiem numery, z powrotem do tyłu na plecach. I niech teraz zastosować sortowanie przez scalanie. Więc najpierw chcesz sortować lewa połowa z tej listy, i niech zatem koncentrują się na 4, 8, 6, i 2. 

Teraz jak mam go o Sortowanie listy wielkości 4? Cóż mam teraz rozważyć sortowanie lewej strony lewej połowie. Ponownie, niech tyłu na chwilę. Jeśli pseudokod jest to, i mam podane osiem elementów, 8 jest oczywiście większa niż lub równą 2. Więc w pierwszym przypadku nie ma zastosowania. Więc do sortowania osiem elementów, po raz pierwszy sortować lewą połowę elementów, następnie sortować prawą połowę, a następnie scalić dwa posortowane połówki, każda o wielkości 4. OK. 

Ale jeśli właśnie powiedział mi, posortować Lewa połowa, która jest wielkości 4, Jak sortować lewą połowę? Cóż, jeśli mam mieć Wejście czterech elementów Pierwszy raz posortować lewo dwa, a następnie w prawo dwa, a potem połączyć je razem. Więc jeszcze raz, staje się nieco z umysłu gięcia gra tutaj bo ty, rodzaju, muszą pamiętaj, gdzie jesteś w tej historii, a na koniec dnia podano żadnej liczby elementów najpierw chcesz posortować Lewa połowa, a następnie w prawo w połowie, następnie połączyć je razem. Zacznijmy zrobić dokładnie to. Oto wejście z ośmiu elementów. Teraz patrzymy na lewej połowie tutaj. Jak sortować cztery elementy? Cóż najpierw uporządkować lewą połowę. Teraz jak mam rozwiązać lewą połowę? Cóż Dostałem dwa elementy. Warto więc uporządkować te dwa elementy. 2 jest większa niż lub równa 2, oczywiście. Tak, że pierwsza sprawa nie dotyczy. 

Więc teraz mam do sortowania lewo połowa z tych dwóch elementów. Lewa połowa, oczywiście, jest tylko 4. Więc jak mam sortować listy jednego elementu? No to teraz, to szczególny przypadek bazowy do góry, że tak powiem, ma zastosowanie. 1 jest mniejsza niż 2, a mój Lista jest rzeczywiście wielkości 1. Więc po prostu wrócić. Ja nic nie robię. I rzeczywiście, spójrz na to, co mam zrobione, 4 jest już posortowana. Jak ja już jestem częściowym sukcesem tutaj. 

Teraz to wydaje się głupie zastrzeżenia, ale to prawda. 4 znajduje się lista wielkości 1. To już klasyfikowane. To jest lewa połowa. Teraz sortować prawą połowę. Mój wkład jest jednym z elementów, 8 podobnie, już klasyfikowane. Głupi, zbyt, ale znowu, Ta podstawowa zasada ma pozwolić nam teraz budować na wierzchu tego pomyślnie. 4 klasyfikowane, 8 jest posortowana, teraz co to było ostatni krok? Więc trzeci i ostatni krok, każda Czas jesteś sortowania listy, wycofanie, było połączenie dwóch połówek, lewa i prawa. Warto więc zrobić dokładnie to. Moja lewa połowa jest, oczywiście, 4. Moja prawa połowa jest 8. 

Więc zróbmy to. Po pierwsze mam zamiar przeznaczyć niektóre dodatkowa pamięć, że będę reprezentować tutaj, jak tylko wtórnym tablicy, to jest wystarczająco duży, aby zmieścić to. Ale można sobie wyobrazić rozszerzenia że prostokąt na całej długości, jeśli potrzebujesz więcej później. Jak zrobić 4 i 8, i połączyć te dwie listy wielkości 1 razem? Tutaj również bardzo proste. 4 jest na pierwszym miejscu, to jest 8. Bo jeśli chcę, aby posortować Lewa połowa, a następnie w prawo w połowie, a następnie połączyć te dwie połówki razem, w uporządkowanej kolejności, 4 jest na pierwszym miejscu, to jest 8. 

Tak więc wydaje się, że robi postępy, nawet choć nie robiłem żadnej pracy. Ale pamiętaj, gdzie jesteśmy w tej historii. Początkowo wziął ośmiu elementów. Mamy klasyfikowane lewą połowę, czyli 4. Potem klasyfikowane lewą połowę w lewej części, która była 2. I jedziemy. Skończyliśmy z tego kroku. 

Więc jeśli mamy posortowane lewa połówka 2, teraz my trzeba posortować prawą połowę 2. Tak więc prawo połowa 2 jest te dwie wartości tutaj, 6 i 2. Więc teraz trzeba wejście wielkości 2 i sortować lewą połowę, a następnie prawa połowa, a następnie połączyć je razem. Cóż, jak posortować listę rozmiarów 1, zawierający tylko numer 6? Mam już zrobione. Wykaz wielkości 1 jest posortowana. 

Jak sortować kolejną listę rozmiar 1, tak zwane prawa połowa. No cóż, to też jest już posortowana. Numer 2 jest sam. Więc teraz mam dwie połowy, w lewo i Dobra, muszę połączyć je razem. Pozwól mi dać sobie trochę wolnego miejsca. 2 i umieścić tam, następnie 6 w nie, a tym samym sortowania tej listy, w lewo i prawo, i połączenie go razem ostatecznie. Więc jestem w nieco lepszej formie. Jeszcze nie skończyłem, bo wyraźnie 4, 8, 2, 6 nie jest ostateczna kolejność, że chcę. Ale teraz mam dwie listy wielkości 2, które oba odpowiednio posortowane. Więc teraz, jeśli do tyłu w wyobraźni oko, skąd nam pozostaje? Zacząłem z ośmiu elementów, to ja stopniała go do lewej połowie 4, to lewa połowa 2 oraz następnie w prawo połowa 2, I zakończona, zatem sortowanie lewej połowa 2, a prawa połowa 2, więc co jest trzecim i ostatnim etapem tutaj? Muszę połączyć razem dwie listy wielkości 2. Więc śmiało. A na ekranie tutaj, dają mi trochę dodatkowej pamięci, choć technicznie, zauważysz, że mam dostałem całą masę pustej przestrzeni do góry nie. Jeśli chcę być szczególnie wydajne miejsca mądry, Może po prostu ruszyć elementy w przód iw tył, góra i dół. Ale dla jasności wizualnej, Mam zamiar umieścić go w dół poniżej, do przechowywania rzeczy ładne i czyste. 

Więc mam dwie listy wielkości 2. Pierwsza lista ma 4 i 8. Druga lista ma 2 i 6. Miejmy połączyć te razem w uporządkowanej kolejności. 2, oczywiście, jest na pierwszym, potem 4, potem 6, a następnie 8. A teraz wydaje się być coraz gdzieś interesujące. Teraz już klasyfikowane połowa listy, i przypadkowo, to wszystkie parzyste, lecz jest rzeczywiście tylko zbieg okoliczności. I teraz nie klasyfikowane w lewo pół tak, że znajdują się 2, 4, 6 i 8. Nic nie jest w porządku. Że czuje się jak postępy. 

Teraz czuje się jak mam Rozmawiałem na zawsze teraz więc to, co okaże się, czy to Algorytm jest rzeczywiście bardziej skuteczne. Ale jedziemy przez to bardzo metodycznie. Komputer oczywiście zrobi to tak. Więc gdzie jesteśmy? Zaczęliśmy z ośmiu elementów. I klasyfikowane lewą połowę 4. Wydaje mi się zrobić z tym. Teraz kolejnym krokiem jest sortować prawą połowę 4. I ta część możemy iść przez trochę więcej szybko, choć jesteś Zapraszamy do tyłu lub pauzy, po prostu przez to, że w swoim własnym tempie, ale to, co mamy teraz jest okazją do to dokładnie ten sam algorytm na czterech różne numery. 

Więc śmiało, a skupić się na prawa połowa, co tu jesteśmy. Lewa połowa, że prawa połowa, a teraz Lewa połowa z lewej połowa tej prawej połowie, i jak mogę sortować listy rozmiarów 1 zawierające tylko numer 1? To już zrobione. Jak mogę zrobić to samo dla listy wielkości 1 zawierającym tylko 7? To już zrobione. Krok trzeci w tym połowa to jest, aby połączyć te dwa elementy do nowej listy wielkości 2, 1 i 7. Nie wydaje się, że zrobiłeś wszystko że wiele interesująca praca. Zobaczymy, co będzie dalej. Właśnie klasyfikowane w lewej połowie Prawa połowa mojego pierwotnego wejścia. Teraz uporządkować prawo pół, który zawiera 5 i 3. Chodźmy znów spojrzeć na lewo połowa, sortowane, prawa połowa, sortowane, i połączyć te dwa razem, do jakiegoś dodatkowego miejsca, 3 jest na pierwszym miejscu, to jest 5. A więc teraz, mamy posortowane Lewa połowa prawej połowy pierwotnego problemu i prawo połowa prawej połowie pierwotnego problemu. Co znajduje się trzeci i ostatni etap? Dobrze, aby połączyć te dwie połówki. Więc pozwól mi sobie niektóre dodatkowe miejsce, ale, znowu, może być wolną przestrzeń przy użyciu tego się szczyt. Ale mamy zamiar utrzymać to proste wizualnie. Pozwólcie mi połączyć się teraz, 1, oraz Następnie 3, a następnie 5 i 7. Tym samym zostawiając mnie teraz z Prawa połowa oryginalnego problemu który jest doskonale klasyfikowane. 

Co więc pozostaje? Czuję się jak zachować mówiąc same rzeczy znowu, i znowu, ale to odblaskowe z Fakt, że używamy rekursji. Proces stosując Algorytm znowu, i znowu, mniejszych podgrup oryginalny problemem. Więc teraz mam lewy klasyfikowane połowy pierwotnej problemu. Mam prawo posortowaną połowę pierwotnego problemu. Co znajduje się w trzecim i ostatnim krokiem? Och, to połączenie. Więc zróbmy to. Miejmy przeznaczyć pewne dodatkowe pamięci, ale mój Boże, może go umieścić w dowolnym miejscu teraz. Mamy tak wiele miejsca dostępne do nas, ale my keep it simple. Zamiast iść do tyłu i dalej z naszym oryginalnym pamięci, Zróbmy to wizualnie dół poniżej, aby zakończyć się scalanie Lewa połowa i prawa połowa. 

Tak więc w wyniku połączenia, co muszę zrobić? Chcę zabrać elementy w porządku. Więc patrząc na lewej połowie, Widzę, że pierwsza liczba to 2. Patrzę na prawej połowie, Widzę pierwszy numer wynosi 1, więc oczywiście, które Numer chcę się wyrwać, i umieścić pierwszy w moim ostatnim liście? Oczywiście, 1. Teraz chcę zadać to samo pytanie. Na lewej połowie, mam wciąż mam numer 2. Na prawej połowie Mam numer 3. Który z nich chcę wybrać? Oczywiście, numer 2 A teraz zauważyć kandydatów są 4 po lewej stronie, 3 po prawej stronie. Powiedzmy, oczywiście, wybrać 3. Teraz kandydaci są 4 na lewa, 5 po prawej stronie. My, oczywiście, wybrać 4. 6 w lewo, 5 po prawej stronie. My, oczywiście, wybrać 5. 6 w lewo, 7 na prawo. Wybieramy 6, a potem wybrać 7, a następnie wybieramy 8. Voila. 

Tak ogromna ilość słów później, są klasyfikowane do tej listy ośmiu elementów w liście od jeden do osiem, który jest zwiększenie z każdym krokiem, ale ile czasu tak zajmie nam to zrobić. Cóż mam celowo ułożone rzeczy z obrazowo tutaj, tak, że możemy rodzaju zobaczyć i docenić podział w zdobywaniu, że się działo. 

Rzeczywiście, jeśli spojrzeć na ślad, Zostawiłam wszystkie z tych linii przerywanych w posiadaczy miejsce, można, rodzaj, zobaczyć, w odwrotnej kolejności, jeśli rodzaj spojrzeć w Historia teraz, moja oryginalna lista Jest, oczywiście, od wielkości 8. A następnie wcześniej, byłem do czynienia z dwoma listami wielkości 4, a następnie cztery listy wielkości 2, a następnie osiem list wielkości 1. 

Więc co to robi, rodzaj, przypomina? Cóż, rzeczywiście, każdy z algorytmy mamy spojrzał na tak daleko, gdzie dzielenie i dzielenie i dzielenie, zachować o rzeczy jeszcze raz, i znowu, skutkuje tym ogólnej idei. I tak jest coś logarytmiczna tutaj dzieje. I to nie dość log n, ale jest składnikiem logarytmiczna do tego, co właśnie zrobił. 

Rozważmy teraz, jak to jest w rzeczywistości. Więc zalogować n, znowu wielki czas pracy, gdy zrobiliśmy coś jak przeszukiwanie binarne, jak teraz nazywają, strategia dziel i rządź poprzez które znaleźliśmy Mike Smith. Teraz technicznie. To baza log 2 n, nawet choć w większości klas matematycznych, 10 jest zazwyczaj baza, że ​​można zakładać. Ale informatycy prawie zawsze myśleć i mówić w kategoriach podstawy 2, tak na ogół po prostu powiedzieć dziennik n, zamiast bazy log2 n ale są dokładnie jeden i ten same w świecie komputera nauki, a na marginesie, jest stałym czynnikiem Różnica między nimi, dlatego Moot tak, więcej powodów formalnych. 

Ale teraz, co dbamy o to w tym przykładzie. Więc niech nie udowodnienia przez przykład, ale w przynajmniej używać przykład numerów pod ręką jako test dla pewności, jeśli będzie. Więc wcześniej formuła była baza dziennika 2 n, n, ale to, co jest w tym przypadku. Miałem n oryginalne numery, lub 8 od liczby oryginalnym specjalnie. Teraz to już trochę jednocześnie, ale jestem upewnić się, że baza log 2 wartości 8 wynosi 3, i rzeczywiście, co jest miłe o tym jest 3, który jest dokładnie szereg razy które można podzielić listę o długości 8 znowu, i znowu, i znowu, dopóki jesteś w lewo z listami tylko wielkości 1. Dobrze? 8 przechodzi do 4, przechodzi do 2, idzie do 1, a to odzwierciedla dokładnie to obraz mieliśmy przed chwilą. Więc trochę zdrowego rozsądku, aby sprawdzić, gdzie logarytm jest rzeczywiście zaangażowana. 

Więc teraz, co jeszcze jest zaangażowany tutaj? n. Tak więc zauważyć, że każdy Czas podzielić listę, choć w odwrotnej kolejności w historii tutaj, ja wciąż robi n rzeczy. To połączenie krokiem wymagane, I dotknąć każdego z numerów, aby wsunąć ją na jego właściwe miejsce. Dlatego, mimo że wysokość tego Schemat jest od wielkości dziennika n n lub 3, W szczególności, innymi słowy Zrobiłem trzy dywizje tutaj. Ile pracy zrobiłem poziomo wzdłuż tej tabeli za każdym razem? 

Cóż, ja n kroki pracować, bo jeśli mam dostał cztery żywioły i cztery żywioły, i muszę połączyć je razem. Muszę przejść przez te cztery, a te cztery, ostatecznie je połączyć z powrotem do ośmiu elementów. Jeśli przeciwnie mam osiem palców tu, czego nie robić, a osiem fingers-- sorry-- Jeśli mam ma cztery palce tutaj, które robię, cztery palce tu, co robię, to jest to samo Przykładem, jak wcześniej, jeśli to zrobię osiem palców choć w Łączna, które mogą, rodzaj, zrobić. Mogę dokładnie zrobić tutaj, to mogę z pewnością połączyć wszystkie z tych list wielkości 1 razem. Ale na pewno trzeba szukać na każdy element dokładnie raz. Tak więc wysokość tego procesu jest log n, szerokość tego procesu, by tak rzec, jest n, więc to, co wydaje się aby ostatecznie jest czas działa od wielkości n razy log n. 

Innymi słowy, podzielone lista, log n razy, ale za każdym razem, gdy to zrobił, mieliśmy dotknąć każdego z elementów aby je połączyć razem, co został n krok, więc mamy n razy log n, lub jako informatyk powie, asymptotycznie, które byłoby wielkie słowo opisać górny zobowiązany na czas pracy, prowadzimy w Big O log n czas, że tak powiem. 

Obecnie jest to istotne, ponieważ przypomnieć sobie czasy uruchomione były z bańki sortowania i selekcji sortowanie i Sortowanie przez wstawianie, i jeszcze kilka innych, które istnieją, n do kwadratu było gdzie byliśmy. I może, rodzaj, zobaczyć tutaj. Jeśli n do kwadratu jest oczywiście n razy n, ale tutaj mamy n razy log n, i wiemy już od tygodnia zero, że log n, logarytmiczna, jest lepsze niż coś liniowych. Po tym wszystkim, przywołać obraz z czerwonym i żółtym i zielone linie, które sporządziły, tym Zielona linia logarytmiczna była znacznie niższa. I w związku z tym, o wiele lepiej i szybciej od prostych linii żółtych i czerwonych, n razy log n jest rzeczywiście lepsza niż n razy n lub n do kwadratu. 

Tak więc wydaje się, że zidentyfikowali seryjnej algorytmu sortowania, który działa w znacznie krótszy czas, i rzeczywiście, dlatego, na początku tego tygodnia, kiedy Widzieliśmy, że konkurs między bańki sortowanie, wybór rodzaju i połączyć sortowania, sortowanie przez scalanie naprawdę wygrał. I rzeczywiście, my nawet nie czekaj dla bubble rodzaju i wyboru rodzaju skończyć. 

Teraz rzućmy jeszcze jedną przepustkę na to, z nieco bardziej formalnego punktu widzenia, tylko w Sprawa ta rezonuje lepiej od tej wyższej dyskusji na poziomie. Więc oto kolejny algorytm. Zapytajmy siebie, co czas pracy jest to algorytmy różne kroki? Załóżmy, podzielić go na pierwszym sprawa, a druga sprawa. IF, a inny w przypadku, gdy, Jeśli n jest mniejsza niż 2, po prostu wrócić. Czuję się jak w czasie stałym. To, rodzaj, podobnie jak w dwóch etapach, Jeśli n jest mniejsza niż 2, a następnie powrót. Ale jak powiedział w poniedziałek, stałą czasową, lub duże o 1, może być dwa kroki, trzy kroki, a nawet 1000 kroków. Liczy się to, że jest to stałą liczbę kroków. Więc żółte podświetlone Pseudokod tutaj przebiega, będziemy go nazywać, Stała czasowa. Więc bardziej formalnie, a jedziemy to-- to będzie zakres, w którym sformalizowanie tego prawo now-- T n, czas pracy na problem że bierze n latków jako wejście, równa się duża o jednej, Gdy n jest mniejsze niż 2. Więc jest to uzależnione od tego. Więc być jasne, jeśli N jest mniejsza niż 2, mamy bardzo krótką listę, a następnie czas pracy, T n, gdzie n jest 1 lub 0, w tym konkretnym przypadku, to jest po prostu będzie stała czasowa. To zajmie jeden krok, dwa kroki, cokolwiek. Jest to stała liczba kroków. 

Więc soczyste część na pewno musi być w drugi przypadek w Pseudokod. W przypadku innego. Sortuj lewa połowa elementów, sortowanie prawo połowa elementów, łączenia połówek posortowane. Jak długo każdy z tych etapów ma? Cóż, jeśli działa czas, aby uporządkować elementy n jest, nazwijmy to bardzo ogólnie, T n, następnie sortowanie lewo połowa elementów to, rodzaj, jak mówi, T n dzieli się przez 2, i podobnie sortowania prawą połowę elementów jest trochę, jakby powiedzieć, T n dzieli 2, a następnie scalenie posortowane połówki. Cóż, jeśli mam niektóre Liczba elementów tutaj jak cztery, a niektóre liczby elementów tutaj, podobnie jak cztery, i muszę połączyć każdy z tych czterech W, a każdy z tych czterech, jedna Po drugie, dzięki czemu ostatecznie mam osiem elementów. Czuje się jak to jest duże o n krokach? Jeśli mam n palce i każdy z im ma być połączone w miejscu, to jak kolejne etapy n. 

Więc rzeczywiście formulaically, możemy wyrazić to, choć trochę przerażająco w pierwszym rzut oka, ale to jest coś która rejestruje dokładnie tę logikę. Czas pracy, T n, gdy n jest większa niż lub równa 2. W tym przypadku, w przypadku innego, T n podzielić przez 2, oraz T n dzieli się przez 2, oraz Big O n, niektóre numer liniowy kroki, być może dokładnie n, może 2 razy n, ale jest to mniej więcej, kolejność n. Więc to też jest, jak się da wyrazić formulaically. Teraz nie wiem, to chyba już nagrał ją w swoim umyśle, lub wyszukać go w z tyłu podręcznika, które może mieć trochę Ściągawka na końcu, ale to jest rzeczywiście będzie dają nam duży o n log n, ponieważ nawroty, że widzisz tu na ekranie, jeśli faktycznie go z nieskończenie wiele przykładów, czy to zrobiłeś formulaically, byś zobaczyć, że to, bo tego wzoru Sam jest rekurencyjne, z t n na coś po prawej stronie, a t n na po lewej stronie, może to rzeczywiście być wyrażona, w ostatecznym rozrachunku, tak duża, przejdź n log n. Jeśli nie przekonany, że to dobrze teraz, po prostu przyjąć na wiarę, że to, w istocie, co powoduje, że nawroty, ale jest to tylko nieco więcej matematyczne podejście do patrzenia w czasie trwania sortowanie przez scalanie oparciu o Pseudokod sam. 

Teraz rzućmy trochę odpowietrznik od wszystkich, że, i spojrzeć na pewne, były senator, który może wyglądać trochę znajomo, który usiadł z Google Eric Schmidt, jakiś czas temu, w jednym z wywiadów na scenie, przed całym gronem ludzi, rozmawiając ostatecznie o to temat, który dość już znane. Spójrzmy. 

Eric Schmidt: Teraz senator, jesteś tutaj w Google, i lubię myśleć o Prezydencja w rozmowie kwalifikacyjnej. Teraz trudno jest dostać pracę jako prezydenta. Prezydent Obama: Racja. Eric Schmidt: A ty jesteś zrobi [niesłyszalne] teraz. Trudno też, aby dostać pracę w Google. Prezydent Obama: Racja. 

Eric Schmidt: Mamy pytania, i prosi swoich kandydatów pytania, a ten jest z Larrym Schwimmer. 

Prezydent Obama: OK. 

Eric Schmidt: Co? Myślicie, że żartuję? To właśnie tutaj. Jaki jest najbardziej efektywny sposób sortować milion 32-bitowe liczby całkowite? 

Prezydent Obama: Well-- Eric Schmidt: Czasami, Może mi przykro, maybe-- Prezydent Obama: Nie, nie, nie, nie, nie, ja think-- Eric Schmidt: To nie it-- Prezydent Obama: I myślę, myślę, że bańki Sortuj byłoby złym rozwiązaniem. Eric Schmidt: Chodź. Kto powiedział mu to? OK. Nie zrobił informatyka on-- 

Prezydent Obama: Mamy Dostaliśmy nasze szpiegów tam. PROFESOR: Wszystko w porządku. Zostawmy za nami teraz teoretyczna świecie algorytmów w asymptotycznej analizy jego, i powrócić do niektórych tematów od tygodnia zera do jedności, a początek usunąć niektóre koła szkolenia, Jeśli będziesz. Tak, że naprawdę można zrozumieć ostatecznie od podstaw, co jest dzieje się pod maską, kiedy Napisać, kompilacji i uruchamiania programów. Przypomnijmy, w szczególności, że było to pierwszy program w C przyjrzeliśmy się, kanoniczna, prosty program rodzajów, relatywnie rzecz biorąc, w którym, drukuje, Hello World. I przypominam, że powiedziałem, proces że kod źródłowy przechodzi jest dokładnie to. Bierzesz kodu źródłowego, przechodzą to przez kompilator, jak Clang, i obecnie jest kod obiektu, który może wyglądać tak, zer i jedynek że procesor komputera, centralne Jednostka przetwarzania lub mózgu, w końcu zrozumie. 

Okazuje się, że to jest trochę w uproszczeniu, że jesteśmy teraz w sposób Pozycja na celu wyodrębnienie aby zrozumieć, co tak naprawdę było dzieje się pod maską przy każdym uruchomieniu Szczęk, albo bardziej ogólnie za każdym razem zrobić program, przy użyciu Marka i CF 50 IDE. W szczególności, takie rzeczy Jest to pierwszy generowane kiedy po raz pierwszy skompilować program. Innymi słowy, kiedy wziąć swój kod źródłowy i skompilować go, co jest pierwszym jest przesyłany przez Clang jest coś, znany jako kod montażowej. I rzeczywiście, wygląda dokładnie tak jak ten. 

Pobiegłem polecenie w wiersz poleceń wcześniej. Clang Dash stolicy s hello.c, i to utworzony plik dla mnie zwanych hello.s, wewnątrz którego były dokładnie te treści, a trochę więcej wyżej i trochę więcej poniżej, ale ja umieścić juiciest Informacje tu na ekranie. A jeśli przyjrzeć się bliżej, zobaczysz co najmniej kilka znanych słów kluczowych. Mamy głównym na górze. Mamy printf w środku. I mamy też hello world odwrotny ukośnik n w cudzysłowie dół poniżej. 

I wszystko inne tutaj Instrukcja jest na bardzo niskim poziomie że procesor komputera rozumie. Instrukcje CPU, które poruszają pamięci się, że struny obciążeń w pamięci, i ostatecznie, do druku rzeczy na ekranie. Teraz to, co się stanie, jeśli po Zespół ten kod generowany jest? Ostatecznie możesz zrobić, rzeczywiście, nadal generować kod wynikowy. Ale kroki, które mają naprawdę toczy się pod maską wygląda trochę bardziej tak. Kod źródłowy staje się kod montaż, Kod, który staje się przedmiotem, i zeby słowa są tu, że podczas kompilacji kodu źródłowego, obecnie jest kod montaż, a następnie podczas montażu kod montażu, obecnie jest kod wynikowy. 

Teraz Clang jest super zaawansowany, jak wiele kompilatorów, i to nie wszystkie z tych etapów razem, a niekoniecznie Wyjście pośredniego pliki, które można nawet zobaczyć. To po prostu kompiluje rzeczy, który jest ogólny termin opisuje cały ten proces. Ale jeśli naprawdę chcesz być szczególnie tam o wiele więcej dzieje się również tam. 

Ale niech też uważają teraz, że nawet że bardzo prosty program, hello.c, nazywa się funkcją. To nazywa się printf. Ale ja nie napisałem printf, rzeczywiście, że pochodzi z, c, że tak powiem. To wycofanie funkcja to zadeklarowane w standardowym io.h, które plik jest nagłówek, który Jest to temat, będziemy rzeczywiście zanurzyć się głębiej niebawem. Ale plik nagłówka jest zwykle towarzyszy przez plik kodu źródłowego, pliku kodu, tak podobnie jak istnieje standardowy io.h. 

Jakiś czas temu ktoś, lub czyjąś, napisał plik o nazwie Standard io.c, w które opiszemy, lub implementacje printf, i kiście innych funkcji, nie zostaną zapisane. Tak więc biorąc pod uwagę, że, jeśli weźmiemy pod uwagę konieczności tu w lewo, hello.c, że kiedy kompilowane, daje nam hello.s, nawet jeśli Clang nie przeszkadza oszczędności w miejscu możemy ją zobaczyć, i że kod montaż zostanie złożone w hello.o, które jest, rzeczywiście, domyślna nazwa biorąc pod uwagę, kiedy tylko skompilować źródła kod na kod obiektu, ale nie są dość gotowy do wykonania tego jeszcze, bo innego kroku musi się wydarzyć, i ma wydarzyło się w ciągu ostatnich kilku tygodnie, być może nie wiemy o was. 

Konkretnie gdzieś w CS50 IDE, i to, też będzie trochę w uproszczenie na chwilę, nie jest, lub był, dawno temu, plik o nazwie Standard io.c, że ktoś kompilowane do Standardowe io.s lub równoważne, że ktoś to zmontowane do standardowego io.o, lub okaże się w nieco inny plik format, który może mieć różny rozszerzenie pliku w ogóle, ale w teorii i koncepcyjnie, dokładnie te kroki, musiało się zdarzyć w jakiejś formie. To znaczy, że teraz kiedy piszę program, hello.c, że po prostu mówi, hello world, i używam kod cudzego jak printf, która była kiedyś na Dzikim Czas, w pliku o nazwie Standard io.c, potem jakoś muszę wziąć moje Kod obiektu, moje zer i jedynek, i przedmiot tej osoby kodu lub zer i jedynek, i jakoś połączyć je ze sobą w jeden końcowy plik o nazwie hello, że ma wszystkie zera i te z mojej podstawowej funkcji, i wszystkie zera i te, dla printf. 

I rzeczywiście, ten ostatni proces jest nazywa, łącząc swój kod wynikowy. Którego wyjście jest to plik wykonywalny. Więc w sprawiedliwości, u koniec dnia, nic zmieniła się od jednego tygodnia, kiedy Pierwszy rozpoczął kompilacji programów. W istocie, wszystko to jest dzieje się pod maską, ale teraz jesteśmy w stanie gdzie możemy rzeczywiście odciąć te różne kroki. I rzeczywiście, w celu dnia, wciąż jesteśmy lewo z zer i jedynek, które jest rzeczywiście wielki segue teraz z inną możliwością C, to nie miałem wykorzystać najbardziej prawdopodobne do tej pory znany jako operatory bitowe. Innymi słowy, jak dotąd, w każdej chwili mamy do czynienia z danymi w C lub zmiennych w C, mieliśmy takie rzeczy jak znaków i pływaki oraz ins i tęskni i dwuosobowe i tym podobne, ale wszystkie te są co najmniej osiem bitów. Nigdy nie jeszcze w stanie manipulować poszczególnych bitów, chociaż pojedynczego bitu, że wie, może reprezentować 0 i 1. Teraz okazuje się, że w C, to Można uzyskać dostęp do poszczególnych bitów, jeśli wiesz, składni, z którym, aby dostać się do nich. 

Warto więc spojrzeć na operatorów bitowe. Więc na zdjęciu kilka symbole my, rodzaj, rodzaj, widział. Widzę ampersanda pionowa bar, a inne, jak również, i przypomnieć, że ampersand ampersanda jest coś, czego nie widział. Logiczne i operatora, gdzie trzeba dwa z nich razem, czy logiczny OR Operator, w którym mają dwa pionowe pasy. Operatory bitowe, które będziemy zobacz działają na bitach indywidualnie, wystarczy użyć jednego znaku handlowego, A pojedynczy pionowy pasek, daszek symbolem będzie dalej, mały tyldy, a następnie w lewo Wspornik lewy wspornik, lub prawy nawias prawy nawias. Każdy z nich ma różne znaczenia. 

W rzeczywistości, rzućmy okiem. Chodźmy stara szkoła dzisiaj i wykorzystanie ekran dotykowy z przeszłości, znany jako tablicy. I to tablicy ma umożliwić nam wyrazić kilka dość prostych symboli, czy raczej niektóre dość proste wzory, że możemy następnie ostatecznie dźwigni finansowej, w celu aby uzyskać dostęp do poszczególnych bity w programie C. Innymi słowy, zróbmy to. Niech najpierw porozmawiać przez Moment o ampersand, co jest logicznym i operatora. Innymi słowy, jest to operator, który pozwala mnie mieć zmienną po lewej stronie zazwyczaj, a zmienna z prawej strony, lub indywidualna wartość, że jeśli I je razem, daje mi wynik końcowy. Więc co mam na myśli? Jeśli w programie, masz zmienną która przechowuje jeden z tych wartości, albo niech keep it simple, i po prostu pisać zer i jedynek indywidualnie, Oto jak działa operator znaku &. 0 handlowe i 0 będzie równa 0. Teraz to dlaczego? 

Jest bardzo podobna do Wyrażeń logicznych, że mamy omówione do tej pory. Jeśli uważasz, że po tym wszystkim, 0 jest fałszywe, 0 false false false jest, jak już omówione logicznie, również fałszywe. Więc mamy 0 również tutaj. Jeśli wziąć 0 ampersanda 1, oraz, że również ma wartość 0, gdyż w tym Wyrażenie po lewej stronie, aby mogło być prawdziwe lub 1, to muszą być prawdziwe i prawdziwe. Ale tutaj mamy fałszywe i prawdziwe, lub 0 i 1. Teraz znowu, jeśli mamy 1 ampersanda 0, to też będzie 0, a jeśli mamy 1 ampersanda 1, w końcu mamy do 1 bit. Więc innymi słowy, nie robimy coś ciekawego z tego operatora jeszcze, operator znaku &. To bitowe i operatora. Ale to są składniki poprzez które możemy zrobić ciekawe rzeczy, jak to już wkrótce. 

Teraz przyjrzyjmy się tylko pojedynczy tu pionowy pasek po prawej stronie. Jeśli mam 0 trochę i ja ALBO to z, logicznym Operator OR, inny bit 0, że będzie mi dać 0. Jeśli wezmę 0 trochę i OR go z 1-bitowe, a potem mam zamiar dostać 1. W rzeczywistości, tylko jasność, pozwól mi wrócić, tak, że moje pionowe pasy Nie pomylić z 1-ki. Pozwól mi przepisać wszystko mój 1 trochę więcej wyraźnie, tak, że w przyszłym zobaczyć, jeśli posiada 1 lub 0, że to będzie 1, a jeśli mam 1 lub 1, że, także ma być 1. Tak więc widać, że logicznie LUB Operator zachowuje się zupełnie inaczej. To daje mi 0 LUB 0 daje mi 0, ale każda inna kombinacja daje mi 1. Tak długo, jak mam jeden 1 w Wzór wynik będzie 1. 

Natomiast z AND Operator, Ampersand, tylko wtedy, gdy mam dwie 1 jest w Równanie, mogę rzeczywiście dostać 1. Teraz istnieje kilka innych operatorzy, jak również. Jednym z nich jest trochę bardziej zaangażować. Więc pozwól mi iść do przodu i usunąć tego, aby zwolnić trochę miejsca. I rzućmy okiem na Daszek symbolem, na chwilę. Jest to typowo znaków można wpisać na klawiaturze, przytrzymanie klawisza Shift i to jeden z numerów na szczycie swojej USA klawiatura. 

Więc to jest wyłącznym Operator OR, XOR. Więc po prostu zobaczył operatora OR. To jest wyłącznym operatorem OR. Co znajduje się w rzeczywistości różnica? Dobrze niech wystarczy spojrzeć na wzór, i używać tego jako składników ostatecznie. 0 XOR 0. Mam zamiar powiedzieć to zawsze 0. To definicja XOR. 0 XOR 1 będzie 1. 1 XOR 0 będzie 1, i 1 XOR 1 będzie? Nie tak? Lub prawo? Nie wiem. 0. Teraz to, co się tu dzieje? Dobrze, że o Nazwa tego operatora. Exclusive OR, tak jak nazwa, rodzaj, sugeruje, Odpowiedź jest tylko będzie 1, jeśli dane wejściowe są cenami, wyłącznie inna. Więc tutaj wejścia są same, więc wyjście 0. Tutaj wejścia są same, więc wyjście 0. Oto wyjścia są różne, są cenami, a więc wyjście to 1. Więc to jest bardzo podobne do I jest to bardzo podobne, czy raczej jest to bardzo podobne do OR, ale tylko w sposób wyłączny. Ten nie jest 1, bo mamy dwa 1-tych, i nie tylko, tylko jeden z nich. W porządku. A co z innymi? Cóż tyldy, w międzyczasie, naprawdę ładne i proste, na szczęście. I jest to jednoskładnikowa Operator, który oznacza Jest ono stosowane tylko do jednego wejścia, jeden argument, że tak powiem. Nie w lewo i prawo. Innymi słowy, jeśli wziąć tyldy z 0, odpowiedź będzie przeciwny. A jeśli wziąć tyldy od 1, Odpowiedź nie będzie przeciwny. Więc operator tyldy jest sposób negując trochę, lub odwrócenie się nieco od 0 do 1 lub 1 do 0 ° C. 

I że pozostawia nas w końcu z zaledwie dwóch operatorów końcowych, tak zwane przesunięcie w lewo, a tak zwane prawo operatora przesunięcia. Rzućmy okiem na jak te prace. Operatora przesunięcia w lewo, napisane z dwoma nawiasami ostrymi jak to, działa w następujący sposób. Jeśli mój wkład, albo mój argument, z lewej Operator przesunięcia jest po prostu 1. I powiedz komputer do Lewy Shift, że 1, powiedzieć, siedem miejsc, wynik jest tak, jakbym przyjąć, że 1 i przenieść go ponad siedem miejsc do lewa i domyślnie, będziemy zakładać, że przestrzeń na prawo ma być wypełniane zerami. Innymi słowy, 1 lewy shift 7 będzie dać mi, 1, a następnie 1, 2, 3, 4, 5, 6, 7 zerami. Więc w taki sposób, że pozwala na wziąć małą liczbę jak 1, i wyraźnie, aby go dużo o wiele większa w taki sposób, ale my naprawdę zobaczymy więcej mądrych podejścia do niego zamiast, jak również, 

W porządku. To wszystko na trzech tygodniu. Będziemy zobaczenia następnym razem. To był CS50. 

[MUZYKI] 

Głośnik 1: Był na przekąskę bar jedzenia hot krówki lody. Miał go na całej twarzy. Ma na sobie, że czekolada jak brodą GŁOŚNIK 2: Co ty robisz? GŁOŚNIK 3: Hmmm? Co? 

GŁOŚNIK 2: Czy wystarczy dwukrotnie dip? Dwukrotne świateł chip. GŁOŚNIK 3: Przepraszam. GŁOŚNIK 2: świateł chip, można ugryzł i ponownie zanurzył. GŁOŚNIK 3: GŁOŚNIK 2: Więc to jest jak stawianie cała prawda usta w kąpieli. Następnym razem wybrać się na układ, po prostu zanurzyć go raz, a zakończyć go. 

GŁOŚNIK 3: Wiesz co, Dan? Zanurzyć drogę, którą chcesz zanurzyć. Będę zanurzyć tak, że chcę, aby zanurzyć.