1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Więc w CS50 dowiedzieliśmy się o
różnych sortowania i wyszukiwania

3
00:00:08,900 --> 00:00:09,442
algorytmy.

4
00:00:09,442 --> 00:00:11,400
A czasami może to być
trochę trudne do utrzymania

5
00:00:11,400 --> 00:00:14,161
utwór z tego, co algorytm co robi.

6
00:00:14,161 --> 00:00:15,910
Mamy naprawdę tylko
odtłuszczonego powierzchnię zbyt,

7
00:00:15,910 --> 00:00:18,740
istnieje wiele innych wyszukiwanie
i algorytmów sortowania.

8
00:00:18,740 --> 00:00:21,780
Więc w tym filmie niech
po prostu wziąć kilka minut

9
00:00:21,780 --> 00:00:24,980
spróbować i destylować każdy algorytm
do jej podstawowych elementów

10
00:00:24,980 --> 00:00:27,810
tak można zapamiętać najbardziej
Ważne informacje o nich

11
00:00:27,810 --> 00:00:31,970
i być w stanie artykułować
różnice, jeśli to konieczne.

12
00:00:31,970 --> 00:00:34,220
>> Pierwszym z nich jest wybór rodzaju.

13
00:00:34,220 --> 00:00:38,210
Podstawową ideą wyboru rodzaju
jest znaleźć najmniejszą niesegregowanych elementu

14
00:00:38,210 --> 00:00:42,890
w tablicy i zamień go z
Pierwszy nieposortowane elementem tej tablicy.

15
00:00:42,890 --> 00:00:46,620
Powiedzieliśmy, że najgorszy
uruchomić czas, który został n do kwadratu.

16
00:00:46,620 --> 00:00:50,060
A jeśli chcesz przypomnieć sobie, dlaczego się
Spojrzenie na wideo wyboru sortowania.

17
00:00:50,060 --> 00:00:54,560
Czas pracy najlepszym przypadku
jest również n do kwadratu.

18
00:00:54,560 --> 00:00:58,910
>> Sortowanie bąbelkowe, idea, że
jeden jest, aby zamienić parę sąsiednich.

19
00:00:58,910 --> 00:01:01,730
Więc to jest klucz, który pomaga
pamiętam różnicę tutaj.

20
00:01:01,730 --> 00:01:04,920
Wybór rodzaju jest, jak dotąd,
znaleźć smallest-- bańki

21
00:01:04,920 --> 00:01:06,790
Sortowanie zamienić parę sąsiednich.

22
00:01:06,790 --> 00:01:08,710
Możemy zamienić parę sąsiednich
elementów, jeśli

23
00:01:08,710 --> 00:01:12,530
są w porządku, co skutecznie
pęcherzyki większe elementy do prawej,

24
00:01:12,530 --> 00:01:17,060
i w tym samym czasie również zaczyna
przenieść mniejsze elementy do lewej strony.

25
00:01:17,060 --> 00:01:20,180
Najgorszy czas przypadku uruchomienia
bubble rodzaju jest n do kwadratu.

26
00:01:20,180 --> 00:01:23,476
Czas pracy najlepszym przypadku
bubble sort jest n.

27
00:01:23,476 --> 00:01:25,350
Ponieważ w tej sytuacji
nie actually--

28
00:01:25,350 --> 00:01:27,141
możemy nie muszą
dokonywać żadnych swapów w ogóle.

29
00:01:27,141 --> 00:01:31,026
Mamy tylko do jednego
przejść przez wszystkie n elementów.

30
00:01:31,026 --> 00:01:34,600
>> W wstawiania sortowanie,
Podstawowym założeniem jest tu przeniesienie.

31
00:01:34,600 --> 00:01:36,630
To jest kluczowe dla Sortowanie przez wstawianie.

32
00:01:36,630 --> 00:01:39,630
Jedziemy do kroku raz przez
tablica z lewej do prawej.

33
00:01:39,630 --> 00:01:41,670
A jak my jesteśmy
zamiar przenieść elementy

34
00:01:41,670 --> 00:01:46,260
widzieliśmy już, aby zrobić miejsce dla
mniejsze, które muszą zmieścić gdzieś

35
00:01:46,260 --> 00:01:48,080
sortowane się w tej części.

36
00:01:48,080 --> 00:01:51,600
Więc budujemy posortowaną tablicę jednym
Element w czasie, od lewej do prawej,

37
00:01:51,600 --> 00:01:54,740
i przesuwać rzeczy, aby pokój.

38
00:01:54,740 --> 00:01:58,650
Najgorszy czas pracy
Sortowanie przez wstawianie jest n do kwadratu.

39
00:01:58,650 --> 00:02:02,380
Najbardziej przypadku czas pracy jest n.

40
00:02:02,380 --> 00:02:05,380
>> Scalanie sort-- słowo kluczowe
tutaj jest dzielenia i łączenia.

41
00:02:05,380 --> 00:02:08,949
Podzieliliśmy całą tablicę, czy
jest to sześć elementów, osiem elementów,

42
00:02:08,949 --> 00:02:13,790
10000 elements-- podzieliliśmy go
w dół o połowę, o połowę, o połowę

43
00:02:13,790 --> 00:02:17,720
dopóki mamy pod tablicę
n jednego elementu macierzy.

44
00:02:17,720 --> 00:02:19,470
Zestaw tablic n jednego elementu.

45
00:02:19,470 --> 00:02:22,640
Więc zaczęliśmy z jednym
Tablica 1000 elementów,

46
00:02:22,640 --> 00:02:26,550
i dostać się do punktu, w którym
mają jeden 1000 tablic elementów.

47
00:02:26,550 --> 00:02:30,990
Potem zaczynają się łączyć te tablice sub
powrotem w prawidłowej kolejności.

48
00:02:30,990 --> 00:02:34,860
Więc bierzemy dwie tablice jednego elementu
i stworzyć tablicę dwóch elementów.

49
00:02:34,860 --> 00:02:38,180
Bierzemy dwie tablice dwóch elementów
i stworzyć tablicę czterech elementów

50
00:02:38,180 --> 00:02:43,900
i tak dalej i tak dalej, dopóki nie
przebudowany jeden n element tablicy.

51
00:02:43,900 --> 00:02:48,410
>> Najgorszy czas pracy
sortowanie przez scalanie znaczy n razy log n.

52
00:02:48,410 --> 00:02:52,390
Mamy n elementów, ale
ten proces rekombinacji

53
00:02:52,390 --> 00:02:56,960
trwa log n kroków, aby uzyskać
powrót do pełnej tablicy.

54
00:02:56,960 --> 00:03:01,160
Najlepszy przypadek czas pracy jest również n log
n, ponieważ proces ten naprawdę nie ma

55
00:03:01,160 --> 00:03:04,090
obchodzi, czy tablica była
sortowane, czy nie zacząć.

56
00:03:04,090 --> 00:03:07,590
Proces jest taki sam, to jest
nie sposób krótkich rzeczy obwodów.

57
00:03:07,590 --> 00:03:11,610
Więc n log n w najgorszym przypadku,
n log n w najlepszym przypadku.

58
00:03:11,610 --> 00:03:13,960
>> Rozmawialiśmy o dwóch
poszukiwania algorytmów.

59
00:03:13,960 --> 00:03:16,230
Więc przeszukiwanie liniowe jest o iteracji.

60
00:03:16,230 --> 00:03:19,500
Wychodzimy naprzeciwko tablicy
raz, od lewej do prawej,

61
00:03:19,500 --> 00:03:21,950
starając się znaleźć numer
że szukamy.

62
00:03:21,950 --> 00:03:24,550
Najgorszy czas pracy jest duże O n.

63
00:03:24,550 --> 00:03:27,610
To może nas iteracji
poprzek każdego elementu

64
00:03:27,610 --> 00:03:30,660
znaleźć element szukamy
na, albo w ostatniej pozycji,

65
00:03:30,660 --> 00:03:31,630
lub wcale.

66
00:03:31,630 --> 00:03:34,720
Ale nie możemy potwierdzić, że do
poznaliśmy już wszystko.

67
00:03:34,720 --> 00:03:36,730
M najlepszym razie możemy znaleźć natychmiast.

68
00:03:36,730 --> 00:03:41,060
Najbardziej przypadku czas pracy
przeszukiwanie liniowe jest omega 1.

69
00:03:41,060 --> 00:03:43,689
>> Wreszcie, nie było przeszukiwanie binarne,
która wymaga wyśmienitymi tablicę.

70
00:03:43,689 --> 00:03:45,605
Pamiętaj, że to bardzo
istotnym czynnikiem

71
00:03:45,605 --> 00:03:47,155
podczas pracy z wyszukiwaniem binarnym.

72
00:03:47,155 --> 00:03:50,180
Jest to niezbędny warunek do korzystania it--
tablica, że ​​jesteś patrząc przez

73
00:03:50,180 --> 00:03:52,160
muszą być sortowane.

74
00:03:52,160 --> 00:03:54,500
W przeciwnym razie, słowo kluczowe
jest dziel i rządź.

75
00:03:54,500 --> 00:03:58,310
Podzielić tablicę na pół, a
wyeliminować pół elementów

76
00:03:58,310 --> 00:04:00,780
za każdym razem, jak przejść przez.

77
00:04:00,780 --> 00:04:04,330
Z powodu tej dziel i rządź
i rzeczy, dzielenie na pół podejścia,

78
00:04:04,330 --> 00:04:07,450
czas pracy najgorszy
od wyszukiwania binarnego

79
00:04:07,450 --> 00:04:11,730
log n, która jest zasadniczo
lepiej niż liniowej wyszukiwania w n.

80
00:04:11,730 --> 00:04:13,570
Najbardziej przypadku czas pracy jest jeszcze jeden.

81
00:04:13,570 --> 00:04:17,010
>> Możemy go znaleźć natychmiast
Pierwszy raz dokonać podziału, ale,

82
00:04:17,010 --> 00:04:19,339
ponownie, należy pamiętać, że
choć wyszukiwania binarnego

83
00:04:19,339 --> 00:04:24,030
znacznie lepiej niż wyszukiwania liniowego
dzięki temu, że w porównaniu do n log n,

84
00:04:24,030 --> 00:04:27,110
może trzeba przejść przez pracę
sortowania swoją tablicę pierwszym, który

85
00:04:27,110 --> 00:04:32,010
może uczynić go mniej skuteczne w zależności
o wielkości iteracji sortowane.

86
00:04:32,010 --> 00:04:35,250
>> Jestem Doug Lloyd, to CS50.

87
00:04:35,250 --> 00:04:36,757