>> DOUG LLOYD: Więc w CS50 dowiedzieliśmy się o różnych sortowania i wyszukiwania
algorytmy.
A czasami może to być trochę trudne do utrzymania
utwór z tego, co algorytm co robi.
Mamy naprawdę tylko odtłuszczonego powierzchnię zbyt,
istnieje wiele innych wyszukiwanie i algorytmów sortowania.
Więc w tym filmie niech po prostu wziąć kilka minut
spróbować i destylować każdy algorytm do jej podstawowych elementów
tak można zapamiętać najbardziej Ważne informacje o nich
i być w stanie artykułować różnice, jeśli to konieczne.
>> Pierwszym z nich jest wybór rodzaju.
Podstawową ideą wyboru rodzaju jest znaleźć najmniejszą niesegregowanych elementu
w tablicy i zamień go z Pierwszy nieposortowane elementem tej tablicy.
Powiedzieliśmy, że najgorszy uruchomić czas, który został n do kwadratu.
A jeśli chcesz przypomnieć sobie, dlaczego się Spojrzenie na wideo wyboru sortowania.
Czas pracy najlepszym przypadku jest również n do kwadratu.
>> Sortowanie bąbelkowe, idea, że jeden jest, aby zamienić parę sąsiednich.
Więc to jest klucz, który pomaga pamiętam różnicę tutaj.
Wybór rodzaju jest, jak dotąd, znaleźć smallest-- bańki
Sortowanie zamienić parę sąsiednich.
Możemy zamienić parę sąsiednich elementów, jeśli
są w porządku, co skutecznie pęcherzyki większe elementy do prawej,
i w tym samym czasie również zaczyna przenieść mniejsze elementy do lewej strony.
Najgorszy czas przypadku uruchomienia bubble rodzaju jest n do kwadratu.
Czas pracy najlepszym przypadku bubble sort jest n.
Ponieważ w tej sytuacji nie actually--
możemy nie muszą dokonywać żadnych swapów w ogóle.
Mamy tylko do jednego przejść przez wszystkie n elementów.
>> W wstawiania sortowanie, Podstawowym założeniem jest tu przeniesienie.
To jest kluczowe dla Sortowanie przez wstawianie.
Jedziemy do kroku raz przez tablica z lewej do prawej.
A jak my jesteśmy zamiar przenieść elementy
widzieliśmy już, aby zrobić miejsce dla mniejsze, które muszą zmieścić gdzieś
sortowane się w tej części.
Więc budujemy posortowaną tablicę jednym Element w czasie, od lewej do prawej,
i przesuwać rzeczy, aby pokój.
Najgorszy czas pracy Sortowanie przez wstawianie jest n do kwadratu.
Najbardziej przypadku czas pracy jest n.
>> Scalanie sort-- słowo kluczowe tutaj jest dzielenia i łączenia.
Podzieliliśmy całą tablicę, czy jest to sześć elementów, osiem elementów,
10000 elements-- podzieliliśmy go w dół o połowę, o połowę, o połowę
dopóki mamy pod tablicę n jednego elementu macierzy.
Zestaw tablic n jednego elementu.
Więc zaczęliśmy z jednym Tablica 1000 elementów,
i dostać się do punktu, w którym mają jeden 1000 tablic elementów.
Potem zaczynają się łączyć te tablice sub powrotem w prawidłowej kolejności.
Więc bierzemy dwie tablice jednego elementu i stworzyć tablicę dwóch elementów.
Bierzemy dwie tablice dwóch elementów i stworzyć tablicę czterech elementów
i tak dalej i tak dalej, dopóki nie przebudowany jeden n element tablicy.
>> Najgorszy czas pracy sortowanie przez scalanie znaczy n razy log n.
Mamy n elementów, ale ten proces rekombinacji
trwa log n kroków, aby uzyskać powrót do pełnej tablicy.
Najlepszy przypadek czas pracy jest również n log n, ponieważ proces ten naprawdę nie ma
obchodzi, czy tablica była sortowane, czy nie zacząć.
Proces jest taki sam, to jest nie sposób krótkich rzeczy obwodów.
Więc n log n w najgorszym przypadku, n log n w najlepszym przypadku.
>> Rozmawialiśmy o dwóch poszukiwania algorytmów.
Więc przeszukiwanie liniowe jest o iteracji.
Wychodzimy naprzeciwko tablicy raz, od lewej do prawej,
starając się znaleźć numer że szukamy.
Najgorszy czas pracy jest duże O n.
To może nas iteracji poprzek każdego elementu
znaleźć element szukamy na, albo w ostatniej pozycji,
lub wcale.
Ale nie możemy potwierdzić, że do poznaliśmy już wszystko.
M najlepszym razie możemy znaleźć natychmiast.
Najbardziej przypadku czas pracy przeszukiwanie liniowe jest omega 1.
>> Wreszcie, nie było przeszukiwanie binarne, która wymaga wyśmienitymi tablicę.
Pamiętaj, że to bardzo istotnym czynnikiem
podczas pracy z wyszukiwaniem binarnym.
Jest to niezbędny warunek do korzystania it-- tablica, że ​​jesteś patrząc przez
muszą być sortowane.
W przeciwnym razie, słowo kluczowe jest dziel i rządź.
Podzielić tablicę na pół, a wyeliminować pół elementów
za każdym razem, jak przejść przez.
Z powodu tej dziel i rządź i rzeczy, dzielenie na pół podejścia,
czas pracy najgorszy od wyszukiwania binarnego
log n, która jest zasadniczo lepiej niż liniowej wyszukiwania w n.
Najbardziej przypadku czas pracy jest jeszcze jeden.
>> Możemy go znaleźć natychmiast Pierwszy raz dokonać podziału, ale,
ponownie, należy pamiętać, że choć wyszukiwania binarnego
znacznie lepiej niż wyszukiwania liniowego dzięki temu, że w porównaniu do n log n,
może trzeba przejść przez pracę sortowania swoją tablicę pierwszym, który
może uczynić go mniej skuteczne w zależności o wielkości iteracji sortowane.
>> Jestem Doug Lloyd, to CS50.