1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Неделя 3, продолжение]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Малан - Гарвардский университет]

3
00:00:04,110 --> 00:00:07,130
>> [Это CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Хорошо. Добро пожаловать обратно. Это CS50 и это в конце недели 3.

5
00:00:11,010 --> 00:00:14,680
>> Так что для тех, кто незнаком, в прошлом году Гарвардский начал, что называется инновационной лаборатории,

6
00:00:14,680 --> 00:00:18,530
или я-лаборатория, которая является прекрасным зданием через реку на территории кампуса в HBS

7
00:00:18,530 --> 00:00:22,640
, которая открыта для студентов, GSAS, студенты со всего кампуса,

8
00:00:22,640 --> 00:00:27,000
в том числе профессорско-преподавательский состав, и это место, чтобы собраться вместе, чтобы работать на инновационные вещи,

9
00:00:27,000 --> 00:00:29,180
Особенно предпринимательской вещи

10
00:00:29,180 --> 00:00:33,410
если вы и 0 или более друзей думаете делать что-то предпринимательских

11
00:00:33,410 --> 00:00:37,080
либо во время этого класса, после этого класса, или за его пределами.

12
00:00:37,080 --> 00:00:41,540
>> Таким образом, одна из вещей, которые они делают в течение срока J эти поездки,

13
00:00:41,540 --> 00:00:44,510
одним из которых является Нью-Йорк, одна из которых заключается в Силиконовой долине.

14
00:00:44,510 --> 00:00:47,530
Пространство очень ограничено, но это возможность пообщаться с МВА

15
00:00:47,530 --> 00:00:52,200
и аспирантов по кампусу и фактически провести время в этих соответствующих областях

16
00:00:52,200 --> 00:00:55,500
болтая стартапов, в чате предпринимателей и тому подобное.

17
00:00:55,500 --> 00:00:57,870
Так что, если интересно, проверить этот адрес здесь.

18
00:00:57,870 --> 00:01:01,220
Она также доступна на слайдах онлайн.

19
00:01:01,220 --> 00:01:04,610
>> Можем ли мы смягчить дом аудио чуть-чуть?

20
00:01:04,610 --> 00:01:08,640
Если вы хотите присоединиться к нам на обед в эту пятницу, в 1:15 вечера огонь и лед, пожалуйста, возглавить там.

21
00:01:08,640 --> 00:01:11,390
Извинения, если форма уже заполнены раз, когда вы туда добраться.

22
00:01:11,390 --> 00:01:13,750
Но мы будем продолжать эту традицию и далее.

23
00:01:13,750 --> 00:01:17,350
>> Сегодня мы по-прежнему высокий уровень обсуждения различных проблем, которые мы можем решить,

24
00:01:17,350 --> 00:01:21,330
фокусировки гораздо меньше, сегодня по крайней мере, на код и многое другое на идеи.

25
00:01:21,330 --> 00:01:24,720
Так вспомните недели 0, когда мы разорвали телефонную книгу в два раза,

26
00:01:24,720 --> 00:01:28,260
целью которой было что-то делать, правда, немного драматических

27
00:01:28,260 --> 00:01:32,360
а послать такой степени, что поиск не должно быть, обязательно,

28
00:01:32,360 --> 00:01:35,100
как очевидные на первый взгляд, как вы могли бы подумать.

29
00:01:35,100 --> 00:01:40,200
И решение проблемы в целом не обязательно всегда быть лучшим -

30
00:01:40,200 --> 00:01:44,130
Наиболее очевидное решение не обязательно может быть лучшим.

31
00:01:44,130 --> 00:01:47,300
Поэтому мы вынуждены были это телефонную книгу и, честно говоря, мы все в этой комнате было инстинктов,

32
00:01:47,300 --> 00:01:51,470
скорее всего, начнется в середине при поиске Майк Смит, а затем перейдите влево или вправо

33
00:01:51,470 --> 00:01:54,280
основанный на любые буквы алфавита мы случайно попадают на.

34
00:01:54,280 --> 00:01:57,560
>> Но это простая идея, что мы, люди, само собой разумеющимся, так долго

35
00:01:57,560 --> 00:02:00,670
действительно должны начать выходят на передний план в своем уме

36
00:02:00,670 --> 00:02:03,900
потому как проблем получить гораздо сложнее, чем телефонную книгу,

37
00:02:03,900 --> 00:02:07,420
те же простые, блестящие идеи являются тем, что происходит, чтобы позволить нам

38
00:02:07,420 --> 00:02:10,259
решать гораздо более сложные и более интересные проблемы,

39
00:02:10,259 --> 00:02:12,930
Среди них некоторые вещи, которые мы считаем само собой разумеющимся, уже в эти дни.

40
00:02:12,930 --> 00:02:15,720
Миллиарды веб-страниц там, и в то же Google и Bing и т.п.

41
00:02:15,720 --> 00:02:17,660
в состоянии найти вещи для нас в этом роде.

42
00:02:17,660 --> 00:02:22,300
Это не происходит с помощью линейного поиска, поиска по всем возможным веб-страниц.

43
00:02:22,300 --> 00:02:25,290
Facebook в состоянии сказать вам, кто все ваши друзья или друзья друзей,

44
00:02:25,290 --> 00:02:28,250
и, что тоже может быть сделано, казалось бы в одно мгновение в эти дни

45
00:02:28,250 --> 00:02:30,820
даже если они имеют миллионы пользователей.

46
00:02:30,820 --> 00:02:34,250
>> И так как мы на самом деле решать проблемы такого масштаба в конечном счете, снижению

47
00:02:34,250 --> 00:02:37,830
на идеи, которые мы рассматривали в неделю 0 и немного больше сегодня.

48
00:02:37,830 --> 00:02:42,320
Мы не будем повторно выполнить этот алгоритм, но помните, мы также сделали в неделю 0 это упражнение

49
00:02:42,320 --> 00:02:44,780
где мы все встать, взять на себя № 1,

50
00:02:44,780 --> 00:02:48,720
и тогда нам пришлось все самостоятельно, рассортированные по спариванию выключен, добавив числа вместе,

51
00:02:48,720 --> 00:02:51,930
Затем половина банды сел на каждой итерации.

52
00:02:51,930 --> 00:02:56,750
И мы пошли от 500 до 250 студентов в 125 и так далее.

53
00:02:56,750 --> 00:03:00,080
Но, как мы сказали в понедельник, мощная идея существует

54
00:03:00,080 --> 00:03:02,460
в том, что если мы удвоили размер этой проблеме

55
00:03:02,460 --> 00:03:06,480
и все дети от правосудия или EC 10 вернулся в комнату и присоединился к нам,

56
00:03:06,480 --> 00:03:09,510
Ну, мы могли бы рассчитывать, что вся совокупность группы

57
00:03:09,510 --> 00:03:13,380
только с 1 еще большие итерации, потому что они бы, может быть, только в два раза больше

58
00:03:13,380 --> 00:03:15,630
или в 10-Ec случае немного больше чем в два раза.

59
00:03:15,630 --> 00:03:18,440
И поэтому мы должны были бы потратить немного больше времени,

60
00:03:18,440 --> 00:03:22,000
но мы не должны были бы потратить 400 или 700 больше шагов.

61
00:03:22,000 --> 00:03:26,550
>> Просто, чтобы нарисовать эту картину в способе, которым это немного менее абстрактным, давайте не будем иметь все встают.

62
00:03:26,550 --> 00:03:31,100
Но если те, кто выбрал сидеть в оркестре сегодня не возражал бы стоя,

63
00:03:31,100 --> 00:03:34,580
Давайте посмотрим, если мы можем выяснить, кто из вас самый высокий человек

64
00:03:34,580 --> 00:03:36,730
делая такой же сравнительный алгоритм.

65
00:03:36,730 --> 00:03:41,830
Так что, если вы сидите в оркестре, мои извинения, но шаг 1, встаньте;

66
00:03:41,830 --> 00:03:44,650
шаг 2, на пары с кем рядом вы,

67
00:03:44,650 --> 00:03:49,360
выяснить, кто выше, и сесть, если вы короче.

68
00:03:49,360 --> 00:03:51,360
Затем повторите.

69
00:03:51,360 --> 00:03:56,280
[Студентам ропот]

70
00:04:13,450 --> 00:04:15,320
>> Хорошо.

71
00:04:15,320 --> 00:04:19,010
Хорошо. Один из них остался стоять. Как тебя зовут? >> Андрей.

72
00:04:19,010 --> 00:04:21,959
>> Андрей, ты самый высокий человек в разделе оркестр сегодня.

73
00:04:21,959 --> 00:04:28,100
>> Поздравляю. [Аплодисменты и крики] Хорошо. Присаживайтесь. Таким образом, мы обнаружили, Андрей.

74
00:04:28,100 --> 00:04:30,870
Но как долго бы он взял меня, например, найти Эндрю

75
00:04:30,870 --> 00:04:33,740
В этом оркестре раздел 50 + или так люди?

76
00:04:33,740 --> 00:04:36,900
Я мог бы принимать довольно простой подход и начать здесь.

77
00:04:36,900 --> 00:04:39,270
А у меня 2 людей встать, и я просто сравнить их,

78
00:04:39,270 --> 00:04:42,120
и тогда я говорю к тому, кто немного короче: "Хорошо, вы садитесь,"

79
00:04:42,120 --> 00:04:44,380
и Я буду помнить, кто выше человек был.

80
00:04:44,380 --> 00:04:49,030
Тогда я повторяю, повторяю, повторяю, и я повесить на самое высокое человек

81
00:04:49,030 --> 00:04:51,920
пока я не найду кого-то немного выше, чем у них, и в этот момент

82
00:04:51,920 --> 00:04:54,950
немного короче, человек должен потом сесть.

83
00:04:54,950 --> 00:04:57,690
Но в этом алгоритме в этом разделе оркестр, если есть п о вас,

84
00:04:57,690 --> 00:05:00,480
сколько шагов алгоритма является то, что собирается взять? >> [Студент] N.

85
00:05:00,480 --> 00:05:03,580
>> Он собирается взять п, правильно, потому что в худшем случае, так сказать,

86
00:05:03,580 --> 00:05:09,090
самый высокий человек самый последний человек, что я получаю только от случайных неудач.

87
00:05:09,090 --> 00:05:14,260
Таким образом, в худшем случае, время работы, что алгоритм является линейным, это я,

88
00:05:14,260 --> 00:05:18,070
где п-общее число людей в пространстве, размер проблемы.

89
00:05:18,070 --> 00:05:19,600
Что об этом алгоритме?

90
00:05:19,600 --> 00:05:22,080
Тот факт, что вы все встали и опять половина из вас сел,

91
00:05:22,080 --> 00:05:23,950
половина из вас сел, половина из вас сел.

92
00:05:23,950 --> 00:05:26,070
Сколько шагов следует, что взяли, если есть п вы здесь?

93
00:05:26,070 --> 00:05:30,200
[Студент] N журнал п. >> Это было бы хуже. Вход с.

94
00:05:30,200 --> 00:05:32,930
>> Так что войти я, даже если вы не помните точно, что логарифм,

95
00:05:32,930 --> 00:05:38,410
сейчас, просто понять, что он относится к этому как-то наполовину, а наполовину, а наполовину.

96
00:05:38,410 --> 00:05:41,000
Она не должна быть в 2 раза. Это может быть в 3 раза.

97
00:05:41,000 --> 00:05:46,560
Но это повторение одного и того же вида, что фактор размера проблема начинается здесь

98
00:05:46,560 --> 00:05:49,620
но затем сразу переходит здесь, то здесь, то тут, то здесь.

99
00:05:49,620 --> 00:05:53,580
Вы не принимая маленькие кусочки из этой проблемы, вы действительно рубки далеко в этом

100
00:05:53,580 --> 00:05:56,160
с большим махом каждый раз.

101
00:05:56,160 --> 00:06:00,810
Поэтому мы вынуждены были 50 человек, потом 25, потом 12 ½ или 13 человек, стоя,

102
00:06:00,810 --> 00:06:05,370
Затем 6 ½ и так далее, пока, наконец, просто Андрей остался стоять.

103
00:06:05,370 --> 00:06:08,710
Так что мы собираемся называть это журнал п, и вы можете себе это следующим образом.

104
00:06:08,710 --> 00:06:12,570
Напомним, эта картина здесь, где линейный алгоритм похож на красную линию там,

105
00:06:12,570 --> 00:06:17,520
желтая линия была подсчете по алгоритму 2s, которые мы использовали для подсчета студентов

106
00:06:17,520 --> 00:06:22,300
В прошлом, но сегодня Святой Грааль будет оставаться эта зеленая линия

107
00:06:22,300 --> 00:06:25,470
где, если мы удвоили количество людей в оркестре раздел или только что сказал,

108
00:06:25,470 --> 00:06:29,170
ад, давайте все в целую комнату встать, не такое уж большое дело

109
00:06:29,170 --> 00:06:31,560
потому что мы примерно в два раза, сколько людей здесь,

110
00:06:31,560 --> 00:06:33,500
Еще 1 итерации, не проблема.

111
00:06:33,500 --> 00:06:36,200
>> Мы обнаружили, Андрей или тот, кто окажется выше, чем Андрей

112
00:06:36,200 --> 00:06:38,770
В мезонине или на балконе.

113
00:06:38,770 --> 00:06:42,140
Таким образом, эта простая идея, что мы взяли столько само собой разумеющимся в телефонной книге,

114
00:06:42,140 --> 00:06:46,170
понимаю, что есть очень много различных мест, в которых мы можем применить его.

115
00:06:46,170 --> 00:06:50,810
Просто, чтобы хлопнуть некоторые жаргоне - на самом деле, а не жаргон, во-первых,

116
00:06:50,810 --> 00:06:52,750
отпусти меня к этой картине здесь.

117
00:06:52,750 --> 00:06:56,970
Сейчас мы говорили о п и п / 2, а затем войти п,

118
00:06:56,970 --> 00:07:00,500
но мы, безусловно, может придумать, как мы будем в течение семестра,

119
00:07:00,500 --> 00:07:05,130
другого рода математические формулы, чтобы описать это общее понятие времени работы.

120
00:07:05,130 --> 00:07:07,580
Это из контекста сейчас, потому что мы увидим в скором времени

121
00:07:07,580 --> 00:07:09,900
Алгоритмы, что это на самом деле представляют.

122
00:07:09,900 --> 00:07:17,990
>> Но заметьте, здесь линейной п, прямая, на самом деле очень низкой указывая прямо сейчас.

123
00:07:17,990 --> 00:07:22,950
Это своего рода оптические иллюзии в том, что мы просто изменить то, что оси абсцисс

124
00:07:22,950 --> 00:07:26,130
и оси у, и мы можем сделать прямо точки линию в любом направлении мы хотим.

125
00:07:26,130 --> 00:07:30,350
Но причина того, что это так, казалось бы плоскую сейчас

126
00:07:30,350 --> 00:07:35,690
потому, что нам нужно, чтобы освободить место на этом графике гораздо медленнее работает раза.

127
00:07:35,690 --> 00:07:39,030
Сейчас, знаю, что есть некоторые довольно плохие алгоритмов в жизни,

128
00:07:39,030 --> 00:07:43,790
некоторые из которых не принимают п шагов или, еще лучше, войдите п шагов, но больше.

129
00:07:43,790 --> 00:07:48,820
Таким образом, выше линии п здесь внизу есть уведомление п раз журнал п,

130
00:07:48,820 --> 00:07:51,410
и мы увидим, что это значит в скором времени.

131
00:07:51,410 --> 00:07:56,010
Прежде, которая п квадратов, и мы ни разу не видели п квадратов алгоритмы, но мы собираемся.

132
00:07:56,010 --> 00:07:57,660
И это выглядит действительно плохо.

133
00:07:57,660 --> 00:08:01,610
Там в 2 к N, то экспоненциальный, который чувствует себя еще хуже.

134
00:08:01,610 --> 00:08:05,760
И все же, как ни странно, то есть п кубе, который, если вы вроде Думая о будущем,

135
00:08:05,760 --> 00:08:10,000
Если вы вид делают математику, от 2 до п на самом деле становится гораздо прямее,

136
00:08:10,000 --> 00:08:15,930
гораздо выше, чем п кубе, если вы посмотрите на осях достаточно далеко.

137
00:08:15,930 --> 00:08:19,890
Таким образом, заметил прямо сейчас эти оси произвольно от 2 до 10 на оси х.

138
00:08:19,890 --> 00:08:21,770
>> А что это значит?

139
00:08:21,770 --> 00:08:23,890
Это означает, что 2 человек до 10 человек в комнате.

140
00:08:23,890 --> 00:08:27,200
Вот и все средства х: размер проблемы, независимо от контекста.

141
00:08:27,200 --> 00:08:30,420
И вертикальной оси, сейчас это количество секунд или количество шагов -

142
00:08:30,420 --> 00:08:31,840
некоторые единицу времени.

143
00:08:31,840 --> 00:08:34,740
Но обратите внимание, что это от 0 до 60 и от 0 до 10.

144
00:08:34,740 --> 00:08:38,549
Но если мы как-то уменьшить масштаб, как вы могли в Excel или несколько графических программ,

145
00:08:38,549 --> 00:08:43,370
и идем до 200.000, обратите внимание, что нечто подобное от 2 до п

146
00:08:43,370 --> 00:08:47,520
будет полностью подавить времени работы п в квадрате,

147
00:08:47,520 --> 00:08:50,960
N в кубе, п § п - все, что мы говорили о до сих пор.

148
00:08:50,960 --> 00:08:54,190
И все же загвоздка в том, когда вы начинаете говорить о вещах, как Facebook

149
00:08:54,190 --> 00:08:57,150
где вы много, много, много людей все взаимосвязано,

150
00:08:57,150 --> 00:09:00,650
Вы русские люди, каждый из которых может иметь столько, сколько друзей п

151
00:09:00,650 --> 00:09:02,860
если все рода приятель в мире,

152
00:09:02,860 --> 00:09:08,100
Ну, это п п раз уже, так что это п квадратов возможно дружба,

153
00:09:08,100 --> 00:09:10,950
по крайней мере в 1-м направлении, п квадратов возможно дружеские отношения.

154
00:09:10,950 --> 00:09:15,330
Так что уже предполагает, что поиски социальный граф Facebook, так сказать,

155
00:09:15,330 --> 00:09:18,090
может начать быть выражено в этих видах формул.

156
00:09:18,090 --> 00:09:19,820
>> Мы вернемся и сделать это гораздо более конкретное,

157
00:09:19,820 --> 00:09:23,280
но сейчас цель на ближайшие несколько недель

158
00:09:23,280 --> 00:09:27,170
будет, чтобы не идти о реализации алгоритмов или код

159
00:09:27,170 --> 00:09:29,870
, что в конечном итоге принимать столько времени, сколько что-то вроде этого.

160
00:09:29,870 --> 00:09:33,110
Но увлекательная вещь об информатике, если вы продолжать в этой области

161
00:09:33,110 --> 00:09:38,320
принимая классы, как CS121, CS124, оба из которых теория курсов,

162
00:09:38,320 --> 00:09:41,300
то, что есть на самом деле некоторые проблемы, которые существуют в этом мире

163
00:09:41,300 --> 00:09:45,710
Принципиально, что, насколько мы знаем, не может быть решена быстрее

164
00:09:45,710 --> 00:09:48,880
чем худшая из этих графов на самом деле предлагает.

165
00:09:48,880 --> 00:09:53,660
Таким образом, есть много открытых проблем в этом мире, чтобы сделать намного лучше, чем у людей до сих пор.

166
00:09:53,660 --> 00:09:56,130
>> Итак, давайте начнем тогда с этим примером.

167
00:09:56,130 --> 00:09:59,650
Мы видели, Шон борьбы с этим на камеру, слишком неловко на видео.

168
00:09:59,650 --> 00:10:05,270
Но на самом деле было, когда Шону было поручено найти на доске, как это число 7,

169
00:10:05,270 --> 00:10:10,300
Напомню, что я сказал, что: "Существует где-то за эти бумажки или белые двери

170
00:10:10,300 --> 00:10:12,570
"Номер 7. Шон, найти его для нас".

171
00:10:12,570 --> 00:10:14,200
И это было удивительно неловко смотреть

172
00:10:14,200 --> 00:10:15,790
потому что он действительно борется с этой проблемой.

173
00:10:15,790 --> 00:10:19,720
Но реальность оказалась Шон сделал, как и любой в комнате мог бы сделать.

174
00:10:19,720 --> 00:10:21,890
Он взял немного дольше, чем обычный человек может иметь,

175
00:10:21,890 --> 00:10:24,760
Но он предположил, что была некоторая уловка, чтобы эту проблему,

176
00:10:24,760 --> 00:10:26,590
Он предположил, что он чего-то не хватает.

177
00:10:26,590 --> 00:10:29,320
И это не помогло, что сотни глаз надвигалась на него.

178
00:10:29,320 --> 00:10:34,250
>> Но в действительности, если вход к этой проблеме куча случайных чисел

179
00:10:34,250 --> 00:10:37,120
и вас просят, чтобы найти 1 такой номер,

180
00:10:37,120 --> 00:10:39,770
Лучшее, что вы можете сделать, это линейный поиск.

181
00:10:39,770 --> 00:10:44,060
Начните с левой, двигаться вправо или начать справа, двигайтесь влево.

182
00:10:44,060 --> 00:10:48,300
Задним числом мы могли бы думать ", Шон, почему бы вам просто не начать с другого конца?"

183
00:10:48,300 --> 00:10:52,120
Ну, 7 могли бы так же легко здесь случайно,

184
00:10:52,120 --> 00:10:54,980
Но я сознательно положил его туда, потому что я полагал, что он не собирается начинать с конца.

185
00:10:54,980 --> 00:10:59,320
Таким образом, я как бы манипулировал ситуацией, но по случайности 7 может быть где угодно.

186
00:10:59,320 --> 00:11:02,380
Так, начиная с правого конца, возможно, были лучше, чем,

187
00:11:02,380 --> 00:11:04,320
Но что, если в следующем году я перехожу 7 в другом месте?

188
00:11:04,320 --> 00:11:06,830
Это не принципиально новое решение проблемы -

189
00:11:06,830 --> 00:11:10,520
начиная с 1 конец или другой - когда вам дают никаких других предположений.

190
00:11:10,520 --> 00:11:13,620
Так Шон начал искать по номерам, и он сказал: "5. Это не здесь".

191
00:11:13,620 --> 00:11:17,280
Тогда он пошел сюда и увидел 19, то он сделал паузу в течение 20 секунд,

192
00:11:17,280 --> 00:11:22,330
Затем он открыл это для 13, а затем стало очевидно,

193
00:11:22,330 --> 00:11:24,270
, что, кажется, не быть образцом здесь.

194
00:11:24,270 --> 00:11:28,090
Это было не 1, 2, 3, 4 или тому подобное. Были пробелы в цифры, которые не помогли.

195
00:11:28,090 --> 00:11:32,320
А также тот факт, что я использовал эти дешевые бумажки, чтобы прикрыть номера

196
00:11:32,320 --> 00:11:35,270
на самом деле преднамеренно, потому что если я удалил все эти бумажки,

197
00:11:35,270 --> 00:11:38,760
Большинство из нас, Шон включены, вероятно, было бы посмотрела рода макроскопически

198
00:11:38,760 --> 00:11:43,410
на доске и сказал: «О, 7, очевидно, прямо там." Мы сделали это мгновенно.

199
00:11:43,410 --> 00:11:46,460
>> И это может быть путь человеческий мозг работает в некоторой степени,

200
00:11:46,460 --> 00:11:50,730
но на самом деле, глаза или ум, вероятно, скользя числа справа налево,

201
00:11:50,730 --> 00:11:55,190
Слева направо, на средней из - что-то происходит физиологически

202
00:11:55,190 --> 00:11:57,640
так, что он чувствовал, что это происходит мгновенно,

203
00:11:57,640 --> 00:12:01,360
но вполне вероятно, даже внутренне был своего рода методологию поиска 7.

204
00:12:01,360 --> 00:12:05,160
И в самом деле, теперь, когда мы говорим о массивов и структур данных

205
00:12:05,160 --> 00:12:08,780
и памяти внутри компьютера, единственное, что мы, люди, можем сделать

206
00:12:08,780 --> 00:12:13,070
Достаточно посмотреть на отдельные ячейки памяти 1 за один раз.

207
00:12:13,070 --> 00:12:16,600
>> Таким образом, каждый другом месте могли бы также быть покрыты с некоторыми бумаге

208
00:12:16,600 --> 00:12:21,170
потому что мы не можем видеть это в любом случае. Мы можем сделать только 1 вещь за один раз.

209
00:12:21,170 --> 00:12:25,030
Таким образом, в данном случае, в случае Шона, мы пошли сюда, а затем мы пошли сюда

210
00:12:25,030 --> 00:12:31,040
и затем мы пошли здесь, здесь, здесь, здесь, есть умное к концу

211
00:12:31,040 --> 00:12:34,450
и только отчасти пропустили эту произвольно и, найдены 7 там.

212
00:12:34,450 --> 00:12:37,470
Этот не был особенным. Это тоже было не в порядке.

213
00:12:37,470 --> 00:12:39,530
Но он, наконец, нашел 7.

214
00:12:39,530 --> 00:12:45,360
Но сейчас еду на дом действительно является то, что лучшее, что вы можете сделать, когда не дали информации

215
00:12:45,360 --> 00:12:50,400
кроме случайно отсортированный чисел начинать с левого или начать с правой стороны.

216
00:12:50,400 --> 00:12:54,950
Или, черт возьми, вы можете случайно открыть двери, но даже тогда, что это значит быть случайной?

217
00:12:54,950 --> 00:12:57,220
Ну, мы должны были бы как-то формализовать, что значит начать здесь,

218
00:12:57,220 --> 00:13:01,150
Затем идите сюда, потом здесь. Шон сделал большой, и это было просто интересно смотреть.

219
00:13:01,150 --> 00:13:06,340
Что, если вместо этого мы изменить проблема немного и воспитывать Шон этом году, если вы будете?

220
00:13:06,340 --> 00:13:09,460
Кто-нибудь быть удобно придумывать на сцене и решения несколько иной задачи

221
00:13:09,460 --> 00:13:12,330
и появляться на камеру?

222
00:13:12,330 --> 00:13:15,720
>> Давайте выходить за рамки оркестра, потому что вы, ребята, были весьма участие уже сегодня.

223
00:13:15,720 --> 00:13:21,430
Как насчет в розовом, в шляпе? Идем вниз. Как тебя зовут? >> Алекс. >> Алекс. Хорошо.

224
00:13:21,430 --> 00:13:24,580
Так что Алекс будет Sean этого года и появится в ближайшие несколько лет

225
00:13:24,580 --> 00:13:27,770
стоит из CS50 лекции.

226
00:13:27,770 --> 00:13:30,340
Алекс, приятно встретиться с вами. >> Приятно познакомиться с вами.

227
00:13:30,340 --> 00:13:33,470
Задача под рукой для вас, что у вас есть это немного легче

228
00:13:33,470 --> 00:13:38,950
в том, что я говорю вам то же самое номера здесь, но теперь они сортируются.

229
00:13:38,950 --> 00:13:41,800
Так что теперь ваша цель, чтобы найти номер 7.

230
00:13:41,800 --> 00:13:45,370
А на самом деле, мы действительно должны сделать это - ты вид обмана, как компьютер не будет,

231
00:13:45,370 --> 00:13:47,990
смотря на то, что цифры были минуту назад.

232
00:13:47,990 --> 00:13:50,360
С мелом это на самом деле не собирается помогать всем, что многое,

233
00:13:50,360 --> 00:13:52,810
но давайте представим, что вы не знаете, какой оригинальный массив.

234
00:13:52,810 --> 00:13:56,600
Все теперь вы знаете, что у вас есть массив отсортированный номера

235
00:13:56,600 --> 00:14:00,360
, которые могут иметь пробелов между ними, и вашей целью является найти номер 7.

236
00:14:00,360 --> 00:14:05,080
Как бы вы, разумное человеческое существо, идти о поиске число 7?

237
00:14:05,080 --> 00:14:07,770
>> Переход от низкой до высокой? >> Хорошо. Перейти низкой до высокой.

238
00:14:07,770 --> 00:14:10,990
И не оторвать от них. Давайте просто поднять их, чтобы мы могли использовать их.

239
00:14:10,990 --> 00:14:14,730
Итак, 1. Подождите. Прежде чем продолжать, это было 1, явно не так.

240
00:14:14,730 --> 00:14:17,270
Так что же происходит в вашем уме следующий? Каким будет ваш следующий шаг?

241
00:14:17,270 --> 00:14:23,250
Следующий. >> Хорошо. Следующий. Хорошо. 3, так неправильно. Каким будет ваш следующий шаг?

242
00:14:23,250 --> 00:14:27,670
Продолжайте идти. >> Все правильно. Продолжайте идти. 5.

243
00:14:27,670 --> 00:14:31,110
Так что продолжайте идти, и позвольте мне вручить вам это для потомков.

244
00:14:31,110 --> 00:14:35,720
7. >> Отлично. Очень хорошо. Найдено номер 7. [Аплодисменты]

245
00:14:35,720 --> 00:14:39,720
Так что было хорошо, но Шон тоже нашел номер 7.

246
00:14:39,720 --> 00:14:44,490
И я утверждаю, что вы действительно не воспользовался этим дополнительным источником информации,

247
00:14:44,490 --> 00:14:47,780
которых является то, что эти цифры сортируются.

248
00:14:47,780 --> 00:14:51,520
Таким образом, мы можем сделать лучше? Любые предложения здесь? Да, в спину.

249
00:14:51,520 --> 00:14:54,710
[Студент] двоичного поиска. >> Я не знаю, что бинарный поиск.

250
00:14:54,710 --> 00:14:58,030
>> [Студент] Начало в середине. >> Начало в середине. Хорошо. Итак, давайте посмотрим, если мы можем туда добраться.

251
00:14:58,030 --> 00:15:02,580
Так что, если вместо этого вы сказали начать с середины, идти вперед и открыть среднюю дверь.

252
00:15:02,580 --> 00:15:04,580
Там в 8 из них, так что вы будете иметь, чтобы произвольно выбрать тот,

253
00:15:04,580 --> 00:15:09,800
немного влево или вправо. Хорошо. 7! [Аплодисменты] Очень красиво.

254
00:15:09,800 --> 00:15:11,410
Хорошо, но где же мы собираемся с этим?

255
00:15:11,410 --> 00:15:14,990
Давайте предположим, что просто разорвать связь вы начали здесь

256
00:15:14,990 --> 00:15:16,670
потому что в равной степени могло случиться, как хорошо.

257
00:15:16,670 --> 00:15:19,540
Мы только что произошло, чтобы узнать, что 7 был там. Так что это 13.

258
00:15:19,540 --> 00:15:21,980
Так что, если они сортируются и мы только начали в середине,

259
00:15:21,980 --> 00:15:24,600
что было бы оптимальным следующий шаг был?

260
00:15:24,600 --> 00:15:27,740
Перейти слева. И вот приходит пример телефонную книгу снова.

261
00:15:27,740 --> 00:15:30,130
Если 13 является здесь и мы знаем, что список отсортирован,

262
00:15:30,130 --> 00:15:33,900
Затем все эти кусочки бумаги неинтересными для нас сейчас

263
00:15:33,900 --> 00:15:37,400
потому что мы уже знаем, что 7 должны быть слева

264
00:15:37,400 --> 00:15:39,510
если эти цифры сортируются, и мы нашли 13.

265
00:15:39,510 --> 00:15:42,500
>> Так что ваш следующий шаг здесь? >> Перейти в левой. >> Ладно, хорошо.

266
00:15:42,500 --> 00:15:45,080
Так что идите к левой, и - ждать, эй, эй, эй. Это обман.

267
00:15:47,140 --> 00:15:51,350
Таким образом, вы нашли 7, но то, что было алгоритму мы просто применять?

268
00:15:51,350 --> 00:15:56,450
Начало в середине. >> Хорошо. Так в чем же логическое продолжение той же идеей?

269
00:15:56,450 --> 00:15:58,970
О, это просто. >> Именно так. >> Так что я начинаю здесь. >> Хорошо.

270
00:15:58,970 --> 00:16:02,020
Итак, теперь мы пошли немного левее снова. Это 3.

271
00:16:02,020 --> 00:16:05,310
Но самое интересное вынос теперь какой из них вам не придется заботиться о?

272
00:16:05,310 --> 00:16:08,040
Эти 2. Эти >> 2. Так что теперь это можно уйти, это можно уходить.

273
00:16:08,040 --> 00:16:12,330
Теперь проблема, которая была 8, то был размером 4 теперь является размер 2.

274
00:16:12,330 --> 00:16:16,430
Мы получаем довольно близко. Снова идем к середине этих 2-х элементов.

275
00:16:16,430 --> 00:16:20,430
>> Хорошо. Так что это своего рода жаль, что теперь мы всегда будем ушел, потому что мы округления.

276
00:16:20,430 --> 00:16:25,150
Но это нормально, потому что теперь мы бросаем эту сторону и все остальное, оставив нам только 7.

277
00:16:25,150 --> 00:16:30,490
Давайте аплодисментами. Найдено 7 раз. [Аплодисменты] Хорошо. Конечно.

278
00:16:30,490 --> 00:16:32,220
Держись всего за 1 больше секунды.

279
00:16:32,220 --> 00:16:36,630
Хотя, что в следующем роде процесс занял чуть дольше, чем мы чувствовали, что это будет,

280
00:16:36,630 --> 00:16:40,150
честно говоря, ваша первая инстинкты были лучше, не так ли? Найдено 7 мгновенно.

281
00:16:40,150 --> 00:16:46,740
Но мы нашли бы 7 быстрее, несмотря ни на что, в этом примере по сравнению с этим

282
00:16:46,740 --> 00:16:50,100
потому что если эти номера все сортируется, так же, как страницы в телефонной книге,

283
00:16:50,100 --> 00:16:54,580
Вы действительно можете нарезать половина проблемы снова и снова и снова.

284
00:16:54,580 --> 00:16:56,740
И это не так просто, чтобы видеть это всего 8 номеров

285
00:16:56,740 --> 00:17:00,100
в отличие от 1000-страницы телефонной книги, где вы действительно видите его визуально,

286
00:17:00,100 --> 00:17:03,120
но в данном случае здесь, когда Шон искал 7,

287
00:17:03,120 --> 00:17:06,020
сколько шагов в худшем случае бы он взял его? >> [Студент] 7.

288
00:17:06,020 --> 00:17:11,670
7 в худшем случае. Ну, в худшем случае не 7, если есть 8 дверей здесь.

289
00:17:11,670 --> 00:17:13,440
Было бы взяли его 8 шагов.

290
00:17:13,440 --> 00:17:18,170
>> Так что, если есть п двери, она могла бы пойти Шон пару лет назад п шагов.

291
00:17:18,170 --> 00:17:21,520
Теперь, в вашем случае, Алекс, учитывая, что эти цифры сортируются -

292
00:17:21,520 --> 00:17:25,130
и мы можем вида выводить это от того, где мы были до сих пор в этой истории -

293
00:17:25,130 --> 00:17:28,300
что время работы более интеллектуальный алгоритм Алекса

294
00:17:28,300 --> 00:17:30,770
из начиная с середины, а затем повторить?

295
00:17:30,770 --> 00:17:36,490
[Студент] 3. >> Так это будет 3, грубо говоря, если вы идете с 8 до 4 до 2 к 1.

296
00:17:36,490 --> 00:17:40,660
Таким образом, 3 шага или, более общо, это журнал N раз.

297
00:17:40,660 --> 00:17:43,380
Каждый раз, когда вы наполовину, а наполовину, а наполовину, а наполовину,

298
00:17:43,380 --> 00:17:45,290
это выражение эта идея журнала с.

299
00:17:45,290 --> 00:17:48,140
И так, что бы вас взял всего 3 шага, и это действительно так сделали

300
00:17:48,140 --> 00:17:50,890
После того как мы открыли двери вдвое и вдвое,

301
00:17:50,890 --> 00:17:53,770
в то время как это заняло бы Шон около 7 или 8 шагов.

302
00:17:53,770 --> 00:17:56,330
Так что спасибо вам за то, что с нами в этом году. >> Спасибо. Приятно было познакомиться.

303
00:17:56,330 --> 00:18:00,170
Спасибо Алексу. >> Аналогично. [Аплодисменты]

304
00:18:00,170 --> 00:18:02,150
>> Что то реальные последствия этого?

305
00:18:02,150 --> 00:18:06,050
Теперь представьте, что это не 8 дверей, которые, откровенно говоря, все мы могли бы найти что-то

306
00:18:06,050 --> 00:18:10,430
за 8 дверей довольно быстро, просто рвет листы бумаги и происходит с нашими инстинктами.

307
00:18:10,430 --> 00:18:14,430
Но что, если это миллион дверей? Что, если это 4 миллиарда двери?

308
00:18:14,430 --> 00:18:19,630
В случае 4 млрд. двери, вы действительно собираетесь хотите, чтобы пойти с алгоритмом Алекса,

309
00:18:19,630 --> 00:18:23,150
бинарный поиск, как мы начнем, назвав его или разделяй и властвуй, более общо,

310
00:18:23,150 --> 00:18:25,220
где вы храните вдвое и вдвое проблемы,

311
00:18:25,220 --> 00:18:30,510
потому что, если у вас есть 4 миллиарда двери, сколько раз вы можете нарезать 4 млрд в половину?

312
00:18:30,510 --> 00:18:33,870
[Студент] 32. >> Это на самом деле 32. Вы можете работать это на бумаге или в голове.

313
00:18:33,870 --> 00:18:38,490
Вы идете 4 млрд до 2 млрд до 1 млрд до половины миллиарда до 250 миллионов, точка, точка, точка.

314
00:18:38,490 --> 00:18:41,620
И если вы делаете из математики, вы собираетесь получить действительно 32,

315
00:18:41,620 --> 00:18:44,950
и что на самом деле относится к информатике, потому что мы обычно рассчитывать по степеням 2.

316
00:18:44,950 --> 00:18:47,600
От 2 до 32, случается, 4 миллиарда долларов.

317
00:18:47,600 --> 00:18:51,440
Таким образом, есть много, имеющие отношение к такого рода полномочия 2 в компьютерные науки.

318
00:18:51,440 --> 00:18:55,120
>> Но то, что около 8 миллиардов? Сколько шагов является то, что собирается предпринять, если есть 8 миллиардов двери?

319
00:18:55,120 --> 00:19:00,350
[Студент] 33. >> Так 33. Что делать, если есть 16 миллиардов двери? Сколько шагов является то, что собираетесь предпринять?

320
00:19:00,350 --> 00:19:05,020
[Студент] 34. >> 34. Мы могли бы видом продолжать это до бесконечности. Но это сильная вещь.

321
00:19:05,020 --> 00:19:09,430
Вы можете ввести миллиардов больше входов к вашей проблеме, но ничего страшного,

322
00:19:09,430 --> 00:19:14,140
Вы просто взять 1 дополнительный кусок из нее и таким образом дает нам что-то вроде бинарного поиска

323
00:19:14,140 --> 00:19:15,920
или разделяй и властвуй, в целом.

324
00:19:15,920 --> 00:19:17,990
Но я немного обманывает, да?

325
00:19:17,990 --> 00:19:22,410
В случае алгоритм Алекса, она имела преимущество над Шоном.

326
00:19:22,410 --> 00:19:27,780
Она знала, что эти цифры были отсортированы, но Алекс не должны сортировать их сама.

327
00:19:27,780 --> 00:19:30,520
Я заранее подошел к доске и сделал вид, что

328
00:19:30,520 --> 00:19:33,670
что я обратил их всех в определенном порядке, то я покрыл их бумаги.

329
00:19:33,670 --> 00:19:35,850
Но сколько же работы, что меня принимаете?

330
00:19:35,850 --> 00:19:40,110
Если бы мы начали с этих цифр в некоторых, казалось бы случайном порядке -

331
00:19:40,110 --> 00:19:43,320
В этом случае эти простые цифры, от 1 до 8 здесь -

332
00:19:43,320 --> 00:19:46,090
как же нам идти о сортировке этих ценностей?

333
00:19:46,090 --> 00:19:52,530
Если бы вы были человеческие данного эту задачу, какую интуитивный подход вы бы взяли

334
00:19:52,530 --> 00:19:54,800
для сортировки целую кучу цифр?

335
00:19:54,800 --> 00:19:57,050
Эти вещи были разложены, как кусочки головоломки. Да.

336
00:19:57,050 --> 00:19:59,950
>> [Студент] Я бы каждый номер и сравнить его с каждой

337
00:19:59,950 --> 00:20:03,180
и продолжайте идти налево. >> Ладно, хорошо.

338
00:20:03,180 --> 00:20:05,720
Так что берите каждый номер, сравнить его с тем, рядом с ним,

339
00:20:05,720 --> 00:20:09,610
а потом просто продолжать двигаться по списку, вроде rejiggering вещи, как вы идете.

340
00:20:09,610 --> 00:20:13,800
Итак, у нас есть шанс, может быть, еще несколько людей, чтобы вмешиваться.

341
00:20:13,800 --> 00:20:16,290
Есть ли у нас еще 8 добровольцев, которые хотели бы прийти?

342
00:20:16,290 --> 00:20:23,950
Чуть меньше давления, так как вы не единственный. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Идем вниз. Вы, ребята, собираетесь быть цифры от 1 до 8.

344
00:20:28,190 --> 00:20:36,050
Давайте посмотрим, если мы не можем это сделать сортировку для Алекса во многом так же, как я сделал это заранее.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Идите вперед и, если бы Вы, выстраиваются на сцене между пюпитр и меня здесь

347
00:20:40,760 --> 00:20:44,960
в том же порядке, что и слайдов на экране.

348
00:20:47,910 --> 00:20:49,680
Ой-ой.

349
00:20:50,370 --> 00:20:53,230
Мы будем работать вас в следующем примере. Ой, подождите, подождите. Здесь мы идем. Подождите.

350
00:20:53,230 --> 00:20:57,570
В следующем примере в настоящее время. Здесь вы идете. Номер 8. Поднимайся.

351
00:20:57,570 --> 00:21:00,270
Хорошо. Сортировать сами в соответствии с этим.

352
00:21:00,270 --> 00:21:03,620
Слайд только немного в стороне от музыки стоять здесь.

353
00:21:03,620 --> 00:21:12,310
Итак, мы имеем 4, 2, 6 - попасть туда, сюда, прямо там - 3.

354
00:21:12,310 --> 00:21:17,570
Да. Хорошо. Вы идете сюда. Нет, вы остаетесь там.

355
00:21:17,570 --> 00:21:21,840
Да, прямо здесь. Нет, я неправильно. Прямо там. Хорошо, очень хорошо. Хорошо.

356
00:21:21,840 --> 00:21:24,930
А теперь давайте отсортировать их в порядке возрастания.

357
00:21:24,930 --> 00:21:26,210
>> Как я могу идти об этом?

358
00:21:26,210 --> 00:21:28,630
Алгоритм, который был предложен еще минуту назад было, почему бы нам просто не сравнить

359
00:21:28,630 --> 00:21:31,970
люди, которые являются своего рода рядом друг с другом, а затем исправить любые ошибки,

360
00:21:31,970 --> 00:21:33,540
двигаясь слева направо.

361
00:21:33,540 --> 00:21:36,580
Таким образом, здесь мы имеем 4 и 2, очевидно, вышел из строя. Давайте обмениваться вас. Хорошо.

362
00:21:36,580 --> 00:21:40,760
Так что теперь я собираюсь двигаться вниз линию. 4 и 6, нет. [Смех]

363
00:21:40,760 --> 00:21:45,010
6 и 8, довольно хорошо. 8 и 1, позвольте мне поменять вас, ребята. Хорошо.

364
00:21:45,010 --> 00:21:48,030
Таким образом, 8 и 3, обменять вас, ребята.

365
00:21:48,030 --> 00:21:52,280
8 и 7, позвольте мне поменять вас, ребята. 5 и 8, отлично.

366
00:21:52,280 --> 00:21:54,820
Я даю вам отсортированный список.

367
00:21:54,820 --> 00:21:56,860
Хорошо. Таким образом, не совсем.

368
00:21:56,860 --> 00:22:01,180
Но это лучше, потому что большие числа - случай в пункте 8 -

369
00:22:01,180 --> 00:22:04,030
были вид пропускали по сравнению с левого на правый.

370
00:22:04,030 --> 00:22:08,010
Так что я получил 1 из них прав, но он чувствует, как это не вполне решить эту проблему.

371
00:22:08,010 --> 00:22:11,150
>> Так что же вы предлагаете нам делать дальше? >> [Студент] Продолжайте делать это. >> Мы продолжаем это делать.

372
00:22:11,150 --> 00:22:13,740
И понимаю, мы снова установить вещи простым, имеющие все люди

373
00:22:13,740 --> 00:22:17,180
рода разумно организовать себя на основе этой картины,

374
00:22:17,180 --> 00:22:19,040
но теперь мы должны быть гораздо более методично.

375
00:22:19,040 --> 00:22:21,510
Мы должны быть алгоритмическим об этом, как будто мы пишем код -

376
00:22:21,510 --> 00:22:23,520
В этом случае словесного псевдокод.

377
00:22:23,520 --> 00:22:26,040
Итак, позвольте мне просто попробовать еще раз. Это работало очень хорошо. Он не решить.

378
00:22:26,040 --> 00:22:30,400
Но когда он сомневается, просто попробуйте и попробуйте снова. Таким образом, 2 и 4, не помогло больше.

379
00:22:30,400 --> 00:22:33,200
4 и 6. Ах! 6 и 1, немного лучше.

380
00:22:33,200 --> 00:22:39,740
6 и 3, хорошо. 6 и 7, 7 и 5, 7 и 8, хорошо.

381
00:22:39,740 --> 00:22:44,060
И вы знаете, я, вероятно, может игнорировать 8 сейчас, потому что он в конце списка.

382
00:22:44,060 --> 00:22:47,250
Может быть, нам не придется беспокоиться о ком-то, проходя мимо него.

383
00:22:47,250 --> 00:22:49,240
Но давайте посмотрим, если это безопасное предположение.

384
00:22:49,240 --> 00:22:52,340
Сейчас в списке - черт - не сортируются. Давайте попробуем это снова.

385
00:22:52,340 --> 00:22:56,440
Таким образом, 2 и 4, 4 и 1, 4 и 3.

386
00:22:56,440 --> 00:22:59,230
4 и 6, хорошо. 6 и 5, хорошо.

387
00:22:59,230 --> 00:23:04,890
6, 7, и 8, хорошо. Но заметьте, я могу просто остановиться здесь, сейчас и остановимся здесь сейчас?

388
00:23:04,890 --> 00:23:07,770
[Студент] Да. >> Да?

389
00:23:07,770 --> 00:23:11,160
Что делать, если один из вас был номер 9 на всем пути там?

390
00:23:11,160 --> 00:23:13,640
Это было бы отсортировать. >> Хорошо. Было бы были отсортированы в первый раз.

391
00:23:13,640 --> 00:23:16,050
Хорошо. Так что давайте вернемся снова. Мы почти на месте.

392
00:23:16,050 --> 00:23:22,800
1 и 2, 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 7, 7 и 8.

393
00:23:22,800 --> 00:23:26,640
>> Я сделал сейчас, но, опять же, я компьютер, который может делать только то, что я сказал, чтобы сделать,

394
00:23:26,640 --> 00:23:30,120
и мое единственное воспоминание сейчас, что я на самом деле просто сделал немного работы.

395
00:23:30,120 --> 00:23:31,700
Что-то изменилось здесь.

396
00:23:31,700 --> 00:23:37,100
Так что я технически не подтверждено визуально или алгоритмически, что этот список действительно отсортированы.

397
00:23:37,100 --> 00:23:40,720
Так что для хорошей мерой, просто чтобы быть анальный об этом, давайте сделаем это еще 1 раз.

398
00:23:40,720 --> 00:23:44,040
Таким образом, 1 и 2, 2 и 3, 3 и 4. И вы знаете что?

399
00:23:44,040 --> 00:23:46,190
Просто для хорошей мерой, я буду следить на моей руке этот раз

400
00:23:46,190 --> 00:23:51,110
сколько свопов я делаю просто так, что я знаю, как много работы я на самом деле сделал.

401
00:23:51,110 --> 00:23:56,930
3 и 4, 4 и 5, 5 и 6, 6 и 7, 7 и 8. Нет свопов.

402
00:23:56,930 --> 00:24:00,800
Так что теперь я бы законно быть идиотом, чтобы сделать это снова

403
00:24:00,800 --> 00:24:03,330
потому что если я не работал через этот проход людей,

404
00:24:03,330 --> 00:24:06,710
то, очевидно, что это произойдет снова, если ни один из них является своего рода случайным

405
00:24:06,710 --> 00:24:10,410
adversarially движущихся вокруг себя. Так что теперь я могу остановиться.

406
00:24:10,410 --> 00:24:15,120
Теперь давайте зададимся вопросом, сколько работы было это на самом деле взять меня?

407
00:24:15,120 --> 00:24:18,260
Сколько шагов сделал, что взять? >> N в квадрате.

408
00:24:18,260 --> 00:24:20,400
Да, так п в квадрате. Где вы получаете п квадрат от?

409
00:24:20,400 --> 00:24:22,660
Вы должны проверить каждое число -

410
00:24:22,660 --> 00:24:26,530
Существует п чисел, и вы должны проверить каждый номер с другими числами п.

411
00:24:26,530 --> 00:24:29,030
Хорошо. >> Так что это п квадрат. >> Хорошо.

412
00:24:29,030 --> 00:24:31,060
>> Таким образом, он чувствует, как она вполне может быть п квадрат, верно?

413
00:24:31,060 --> 00:24:33,820
Там это п из этих парней, 8 конкретно в данном случае,

414
00:24:33,820 --> 00:24:37,590
но каждый раз, когда я прошел через этот список я сравнивал первые лица, в отношении второго,

415
00:24:37,590 --> 00:24:39,650
второго к третьему снова и снова, и снова,

416
00:24:39,650 --> 00:24:42,450
и когда я добрался до конца, что же мне делать? Я переделал его.

417
00:24:42,450 --> 00:24:46,280
Таким образом, если мы обобщим это объяснение, мы русские люди

418
00:24:46,280 --> 00:24:51,090
и я делаю, очевидно, 8 шагов, п шагов, каждый раз, когда я иду по этому алгоритму.

419
00:24:51,090 --> 00:24:56,070
Но сколько раз в худшем случае мне придется пройти через это список людей?

420
00:24:56,070 --> 00:24:59,370
[Студент] N раз. >> Наверное, я, право, потому что в худшем случае,

421
00:24:59,370 --> 00:25:03,410
, что, вероятно, в худшем случае расположения этих парней с самого начала идти?

422
00:25:03,410 --> 00:25:06,520
Если они совершенно обратном порядке

423
00:25:06,520 --> 00:25:09,310
потому что только предположить, мысленно, let's - Как тебя зовут? >> Боуэн.

424
00:25:09,310 --> 00:25:12,510
Боуэн. Хорошо. Так Боуэн, иди сюда на минутку.

425
00:25:12,510 --> 00:25:16,150
>> Предположим, что Боуэн был здесь в начале алгоритма,

426
00:25:16,150 --> 00:25:19,790
и мы не знаем, что все остальные, но Боуэн здесь, в соответствии с этим алгоритмом -

427
00:25:19,790 --> 00:25:23,820
и если вы хотите просто прогуляться со мной - будет пузыриться, как он это делал в первый раз,

428
00:25:23,820 --> 00:25:25,740
весь путь до конца.

429
00:25:25,740 --> 00:25:29,400
Но предположим, что человек рядом с Bowen был номер 7.

430
00:25:29,400 --> 00:25:33,450
Я должен вернуться и получить номер 7, который означает, что я должен пройти весь путь сюда.

431
00:25:33,450 --> 00:25:36,980
Теперь я должен иметь тот же прогулка с человеком, который является номером 7.

432
00:25:36,980 --> 00:25:40,140
Но что, если затем номер 6 был рядом с ним, а?

433
00:25:40,140 --> 00:25:42,180
Тогда я должен вернуться назад и получить 6.

434
00:25:42,180 --> 00:25:46,490
Итак, еще раз, на каждой итерации этого цикла я обращаюсь к каждому из русского народа,

435
00:25:46,490 --> 00:25:50,090
и я мог бы сделать п из этих прогулок, чтобы убедиться, что я потянув

436
00:25:50,090 --> 00:25:53,760
Все из крупнейших элементов назад и назад и обратно в самом конце списка.

437
00:25:53,760 --> 00:25:58,230
Таким образом, N Things п раз просто п раз п или п квадрат.

438
00:25:58,230 --> 00:26:02,050
>> И вот уже у нас есть алгоритм, который уже не я, это не журнал п,

439
00:26:02,050 --> 00:26:04,820
это на самом деле хуже, чем все, что мы делали раньше.

440
00:26:04,820 --> 00:26:09,840
Так Алекс вида повезло в том, что я сделал всю работу по-видимому фронт для нее,

441
00:26:09,840 --> 00:26:14,690
Все дорогие работы, так что она могла наслаждаться в этом алгоритм двоичного поиска,

442
00:26:14,690 --> 00:26:16,420
который журнал с.

443
00:26:16,420 --> 00:26:18,240
Но это согласуется с темой понедельник.

444
00:26:18,240 --> 00:26:23,260
Мы дали немного больше пространства, мы использовали больше битов для того, чтобы ускорить наше время работы.

445
00:26:23,260 --> 00:26:26,170
Так много, что есть это компромисс между временем и пространством,

446
00:26:26,170 --> 00:26:31,060
там также может быть просто компромисс между времени впереди рода получении вещей готовы пойти

447
00:26:31,060 --> 00:26:35,000
и фактического выполнения алгоритма как поиск. Давайте попробуем еще один.

448
00:26:35,000 --> 00:26:39,050
Если вы, ребята, не возражал бы просто быстро переставляя себя, чтобы соответствовать это снова,

449
00:26:39,050 --> 00:26:42,240
Давайте попробуем что-то немного отличается, где это не так просто,

450
00:26:42,240 --> 00:26:45,760
как только исправить все ошибки попарно, что это очень интуитивно.

451
00:26:45,760 --> 00:26:48,150
Давайте вместо этого быть немного более тщательно и сделать это.

452
00:26:48,150 --> 00:26:51,010
Это один тоже я хотел бы предложить, вероятно, довольно интуитивно.

453
00:26:51,010 --> 00:26:55,070
>> Давайте выберем наименьшее человека из списка снова и снова. Таким образом, здесь мы идем.

454
00:26:55,070 --> 00:26:57,350
4, вы наименьшее человек, которого я так видел до сих пор,

455
00:26:57,350 --> 00:27:00,520
так что я мысленно помнить, что, просто указывая на вас на данный момент.

456
00:27:00,520 --> 00:27:05,020
2. Ох! Забудьте про номер 4. Я только что нашел новый наименьший элемент в этом списке.

457
00:27:05,020 --> 00:27:07,410
Я собираюсь вид помнить об этом. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ох! 1. До свидания. Так что теперь я буду помнить номер 1.

459
00:27:11,190 --> 00:27:14,790
Мы знаем, что 1 является наименьшим, но я компьютер. Что делать, если есть 0?

460
00:27:14,790 --> 00:27:17,140
Что делать, если есть -1? Я должен продолжать идти.

461
00:27:17,140 --> 00:27:20,990
Таким образом, 3, 7, 5, нет. Хорошо. Так номером 1 был самым маленьким.

462
00:27:20,990 --> 00:27:23,640
Позвольте мне вам выбрать из списка - МЫ идти по этому пути -

463
00:27:23,640 --> 00:27:27,760
и поставить вас произвольно в начале списка.

464
00:27:27,760 --> 00:27:29,740
Сейчас, подожди минутку. Я как бы обманутыми.

465
00:27:29,740 --> 00:27:34,010
Если эти ребята представляют собой не список из 8 человек, но массиве,

466
00:27:34,010 --> 00:27:37,050
8 кусков непрерывной памяти - вы не возражаете, отступив всего на данный момент?

467
00:27:37,050 --> 00:27:39,060
Там на самом деле нет места для тебя прямо здесь.

468
00:27:39,060 --> 00:27:41,840
Так как же нам освободить место для - как тебя зовут? >> Сэмми. >> Сэмми.

469
00:27:41,840 --> 00:27:43,710
Как мы можем сделать пространство для Сэмми?

470
00:27:43,710 --> 00:27:46,760
>> Мы движемся п, которые до меня. >> Хорошо.

471
00:27:46,760 --> 00:27:48,850
Таким образом, мы могли двигаться русского народа, которые перед ним,

472
00:27:48,850 --> 00:27:52,400
так что если вы, ребята, хотите принимать по 1 преднамеренным, драматический шаг влево.

473
00:27:52,400 --> 00:27:57,000
Они все сделали это в унисон, но последний раз я написал код,

474
00:27:57,000 --> 00:27:59,740
Вы не можете сортировать, перемещать много вещей сразу.

475
00:27:59,740 --> 00:28:02,450
Мы можем сделать это в цикле, движущихся каждый раз в то время.

476
00:28:02,450 --> 00:28:04,340
Так что, если вы, ребята, не возражал бы отступая вправо,

477
00:28:04,340 --> 00:28:07,230
и Сэмми, если бы вы могли сделать шаг назад, потому что до сих пор нет места для тебя,

478
00:28:07,230 --> 00:28:11,420
Теперь давайте сделаем это. Где был Сэмми минуту назад? Прямо там.

479
00:28:11,420 --> 00:28:16,140
Так что разрыв есть. Таким образом, можно двигаться в месте Сэмми.

480
00:28:16,140 --> 00:28:20,580
Теперь следующий человек, и теперь следующий человек, в настоящее время следующего человека. Теперь у нас есть место для Сэмми.

481
00:28:20,580 --> 00:28:23,490
Теперь, кто-то из зала, - что было хорошо, что было правильно,

482
00:28:23,490 --> 00:28:27,070
он чувствовал себя немного времени - что быстрее? Да.

483
00:28:27,070 --> 00:28:29,440
[Студент] Новый массив? >> Что это такое? >> [Студент] Новый массив? >> Ладно, хорошо.

484
00:28:29,440 --> 00:28:33,200
>> Таким образом, в соответствии с этой темой просто компромисс, то почему бы мне не сделать новый массив

485
00:28:33,200 --> 00:28:36,570
 , а затем Сэмми будут плавать в пространстве перед этими людьми, например,

486
00:28:36,570 --> 00:28:39,600
и мы можем только начать заполнение нового массива в целом. Это тоже будет работать.

487
00:28:39,600 --> 00:28:42,450
Но я не заинтересован в тратить больше пространства сегодня. Что другой подход?

488
00:28:42,450 --> 00:28:46,630
[Студент] Swap. >> Хорошо. Мы могли бы просто поменять эти 2 парня. Как тебя зовут?

489
00:28:46,630 --> 00:28:49,390
Марио. >> Марио. Таким образом, Марио, вы в настоящее время здесь.

490
00:28:49,390 --> 00:28:52,480
Сэмми, вы можете создать резервную копию на мгновение? Марио был здесь.

491
00:28:52,480 --> 00:28:55,830
У нас нет места для тебя больше, так что если вы не возражаете, где собираются Сэмми,

492
00:28:55,830 --> 00:29:02,430
мы поставим Sammy здесь, и теперь я бы утверждать, что замена операции Сэмми был намного быстрее.

493
00:29:02,430 --> 00:29:06,370
Мы сделали 1 операцию, чтобы поменять эти парни, или, может быть от 2 до обменять эти ребята,

494
00:29:06,370 --> 00:29:11,210
но мы не делаем 1, 2, 3, 4, так что чувствует себя лучше. Сейчас, подожди минутку.

495
00:29:11,210 --> 00:29:14,660
Я как бы сделал эту проблему еще хуже, потому что номер 4 был отчасти близко к началу.

496
00:29:14,660 --> 00:29:19,470
Сейчас число 4 является чуть ближе к этой цели, но я действительно не знал, или заботятся об этом.

497
00:29:19,470 --> 00:29:23,330
Так что это просто невезение, что число 4 является чуть дальше от своего предназначенного места.

498
00:29:23,330 --> 00:29:25,110
Итак, давайте повторять этот алгоритм.

499
00:29:25,110 --> 00:29:28,410
>> Напомним, что до тех пор, как эта история была, все, что мы делали, было пройтись по списку

500
00:29:28,410 --> 00:29:31,130
ищет наименьший номером человек.

501
00:29:31,130 --> 00:29:34,530
Итак, теперь давайте сделаем это снова. Мы не должны беспокоиться о Сэмми больше.

502
00:29:34,530 --> 00:29:37,590
Мы можем просто пойти сюда. Ох! Номер 2. Это довольно малое число.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Ладно, хорошо.

504
00:29:41,180 --> 00:29:43,770
И к счастью, по стечению обстоятельств, у меня нет для перемещения - >> Вилли.

505
00:29:43,770 --> 00:29:45,910
Вилли, потому что он в свое правильное место сейчас.

506
00:29:45,910 --> 00:29:48,110
Давайте сделаем это снова и игнорировать эти 2 парня.

507
00:29:48,110 --> 00:29:50,460
6. Это довольно малое число. Ох! 8, безусловно, больше.

508
00:29:50,460 --> 00:29:53,410
4. Давайте сосредоточимся на 4. Ох! 3 еще лучше.

509
00:29:53,410 --> 00:29:58,290
7 и 5. Итак, что же нам теперь делать с - >> Роджер. >> Роджер?

510
00:29:58,290 --> 00:30:00,250
Давайте обменять его с номером 6.

511
00:30:00,250 --> 00:30:03,570
Так что если 6 и 3 хотелось бы поменять,

512
00:30:03,570 --> 00:30:07,320
Мы сейчас вид получил повезло в том, что 6 ближе туда, где она должна быть,

513
00:30:07,320 --> 00:30:10,300
но это просто совпадение здесь. Итак, давайте теперь иди сюда.

514
00:30:10,300 --> 00:30:13,430
8 представляет собой довольно малое число. Ох! 4 является меньшим.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Что мы сейчас делаем? >> Swap. >> Именно так.

516
00:30:17,130 --> 00:30:19,010
Итак, давайте делать такого рода быстрее.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Где 5 перейти? Хорошо. Хорошо.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 получает оставаться там, где она есть. Как тебя зовут? >> Розали.

519
00:30:28,380 --> 00:30:31,770
Розали получает оставаться там, где она есть. 7 получает до - Давайте посмотрим. 7, 8. Хорошо.

520
00:30:31,770 --> 00:30:35,100
Таким образом, 7 получает оставаться там, где она есть. Как тебя зовут? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Так Amna получает оставаться там, где она есть, и № 8 уже, где он сейчас и должно быть.

522
00:30:39,670 --> 00:30:43,960
Ладно, хорошо. По ощущениям, мы просто создаем для себя работу здесь, однако.

523
00:30:43,960 --> 00:30:47,440
Что в конечном счете, время работы этого алгоритма?

524
00:30:47,440 --> 00:30:51,900
Если мы думаем об этих людях не как 8, но как п? >> Это с.

525
00:30:51,900 --> 00:30:55,440
Это п шагов, но мы проверяем каждый раз.

526
00:30:55,440 --> 00:30:57,570
Хорошо. N, но вы проверяете каждый раз?

527
00:30:57,570 --> 00:31:03,450
Хорошо, но если он п шагов, не должен я был в состоянии разобраться вам просто будет 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
О! Хорошо, что есть большая разница.

529
00:31:05,590 --> 00:31:08,050
Таким образом, п квадрат почему? Что на самом деле происходит?

530
00:31:08,050 --> 00:31:12,130
Там в русском народе в этот список, но найти наименьшее лица в список

531
00:31:12,130 --> 00:31:16,200
В худшем случае, сколько шагов я должен взять? Н. >>

532
00:31:16,200 --> 00:31:19,160
>> N, правильно, потому что в худшем случае, номер 1 все пути туда,

533
00:31:19,160 --> 00:31:20,990
так что я должен пойти получить его или ее.

534
00:31:20,990 --> 00:31:25,500
А потом, когда я, наконец, понимаю, 1 был маленьким, то это довольно быстро, чтобы поменять их местами.

535
00:31:25,500 --> 00:31:28,450
Но сейчас я должен начать с самого начала и искать кто?

536
00:31:28,450 --> 00:31:31,980
Следующее наименьшее человек, что на 2. Где в худшем случае составляет 2?

537
00:31:31,980 --> 00:31:34,320
О, мой Бог. Это все пути сюда в конце.

538
00:31:34,320 --> 00:31:37,000
Так что теперь я только что сделал другой п шагов, другой п шагов.

539
00:31:37,000 --> 00:31:41,200
И если у нас есть русские люди и в худшем случае наименьшее человек п шагов,

540
00:31:41,200 --> 00:31:45,230
вот опять п п раз, и поэтому мы вновь п квадрат.

541
00:31:45,230 --> 00:31:47,280
Это не чувствовал себя так хорошо.

542
00:31:47,280 --> 00:31:52,150
И в самом деле, даже в лучшем случае - предполагать, что они начинают отсортированный -

543
00:31:52,150 --> 00:31:59,080
сколько шагов требуется для меня с помощью этого алгоритма для сортировки этих русских людей?

544
00:31:59,080 --> 00:32:01,010
N в квадрате. >> Я слышал п квадрат. Почему п квадрат?

545
00:32:01,010 --> 00:32:05,240
Потому что вы все равно должны проверить каждый раз. >> Да.

546
00:32:05,240 --> 00:32:08,060
И вы должны поменять их местами. >> Хотя мы, люди, вид всеведущего

547
00:32:08,060 --> 00:32:10,770
в том смысле, визуально, что мы можем только отчасти видеть, что это сортируется,

548
00:32:10,770 --> 00:32:12,140
Компьютер не то, что умный.

549
00:32:12,140 --> 00:32:14,040
Это будет посмотреть здесь и здесь и здесь,

550
00:32:14,040 --> 00:32:16,610
но если то, что он ищет это наименьший элемент,

551
00:32:16,610 --> 00:32:22,110
Вы только знаете, что вы нашли наименьший элемент на какой момент? Как только вы в конце.

552
00:32:22,110 --> 00:32:25,880
Но в этот момент вы только нашли в настоящее время наименьший элемент.

553
00:32:25,880 --> 00:32:28,810
Вам не обязательно знать ничего о состоянии мира.

554
00:32:28,810 --> 00:32:30,880
Таким образом, вы должны пойти снова и снова, и снова.

555
00:32:30,880 --> 00:32:34,880
>> Поэтому на этот раз я действительно выглядят немыми, потому что я проверяю, ладно, 2, ты маленький,

556
00:32:34,880 --> 00:32:37,530
Но я не знаю, что в общем пока нет.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Ладно, хорошо. 2 был действительно самым маленьким.

558
00:32:41,090 --> 00:32:43,150
Теперь давайте найдем следующий по величине. Хорошо.

559
00:32:43,150 --> 00:32:48,350
3, вы в настоящее время самым маленьким. Давайте посмотрим. 4, 5, 6, 7, 8. Ладно, опять повезло.

560
00:32:48,350 --> 00:32:53,170
3 был действительно в нужном месте. Но я собираюсь продолжать делать это снова и снова и снова.

561
00:32:53,170 --> 00:32:55,990
Как мы можем сделать чуть-чуть лучше?

562
00:32:55,990 --> 00:33:00,120
Вместо того, чтобы люди пузырь попарно от наименьшего к наибольшему

563
00:33:00,120 --> 00:33:04,350
и вместо того, чтобы идти вперед и назад по списку выбора, то наименьшее человек,

564
00:33:04,350 --> 00:33:09,780
Почему бы нам не вставить вместо этих людей в список новый шаг за шагом?

565
00:33:09,780 --> 00:33:13,080
Давайте попробуем это. Теперь позвольте мне называть такого рода вещи вставки.

566
00:33:13,080 --> 00:33:17,250
И вот мы здесь. Номер 1. Я не забочусь ни о ком другом в этом списке.

567
00:33:17,250 --> 00:33:21,310
Моя цель сейчас это поставить номер 1 в начале отсортированного списка.

568
00:33:21,310 --> 00:33:23,910
И я собираюсь предложить, так как я только 8 участков памяти,

569
00:33:23,910 --> 00:33:28,670
произвольно сейчас я стену между моей якобы несортированный список,

570
00:33:28,670 --> 00:33:32,740
и тех, кто находится позади меня, я буду утверждать, сортируется.

571
00:33:32,740 --> 00:33:34,680
Так что теперь у нас есть номер 1.

572
00:33:34,680 --> 00:33:39,240
Я хочу, чтобы вставить его в свой отсортированный список, так что я просто хочу, чтобы двигать стены здесь,

573
00:33:39,240 --> 00:33:43,930
и теперь я утверждаю, этот список отсортирован, этот список несортированные - по крайней мере, насколько я знаю.

574
00:33:43,930 --> 00:33:46,070
Я не могу видеть все номера сразу.

575
00:33:46,070 --> 00:33:49,000
>> Теперь я, случается, сталкиваются с номером 2. Что мне делать с ним?

576
00:33:49,000 --> 00:33:54,380
Я вставляю Вы сейчас в отсортированном списке. Но обратите внимание, как легко это было.

577
00:33:54,380 --> 00:33:59,650
Мне просто нужно смотреть. Номер 1 есть. О, очевидно, 2 идет в сторону номер 1.

578
00:33:59,650 --> 00:34:03,700
И что теперь мне делать с 3? Я вставляю Вас в упорядоченный список. Но это было просто супер.

579
00:34:03,700 --> 00:34:07,250
Это супер просто, это просто супер, это просто супер, супер просто, супер просто.

580
00:34:07,250 --> 00:34:12,790
А теперь все отсортировано позади меня, и сколько шагов было, что взять?

581
00:34:12,790 --> 00:34:15,620
[Студентов] Н. >> Так это только п. Нам повезло.

582
00:34:15,620 --> 00:34:18,860
Это было только п почему? >> [Студент] Поскольку список был отсортирован.

583
00:34:18,860 --> 00:34:21,630
Список уже отсортирован. Так что нам повезло.

584
00:34:21,630 --> 00:34:25,639
Но мы разработали алгоритм этого времени, которая использует такую ​​удачу,

585
00:34:25,639 --> 00:34:29,420
что лучшем случае,, не теряя лишнее время.

586
00:34:29,420 --> 00:34:31,750
Таким образом, мы теперь имеем то, что мы называем пузырь виды

587
00:34:31,750 --> 00:34:33,949
где люди вроде пузырь попарно.

588
00:34:33,949 --> 00:34:38,100
Теперь у нас есть выбор рода, где мы вырвать наименьшее человек снова и снова.

589
00:34:38,100 --> 00:34:42,350
И теперь у нас есть сортировка вставкой, где мы вроде как активно ставить людей, где они принадлежат

590
00:34:42,350 --> 00:34:45,000
В более упорядоченный список.

591
00:34:45,000 --> 00:34:49,679
Если бы мы могли, аплодисменты для этих парней здесь. [Аплодисменты]

592
00:34:49,679 --> 00:34:52,310
Давайте возьмем наш 5-минутный перерыв здесь.

593
00:34:52,310 --> 00:34:55,139
А когда мы вернемся, мы будем взрывать все эти алгоритмы из воды

594
00:34:55,139 --> 00:35:00,260
с чем-то лучше. Хорошо. Большое спасибо. Вы можете держать их в качестве сувениров.

595
00:35:01,710 --> 00:35:04,330
Хорошо. Мы вернулись.

596
00:35:04,330 --> 00:35:08,420
>> И чтобы резюмировать очень быстро, у нас были эти 3 различных подходов к сортировке,

597
00:35:08,420 --> 00:35:13,000
Весь смысл которой было добраться до точки, где кто-то, как Алекс

598
00:35:13,000 --> 00:35:16,930
может искать список номеров быстрее, чем кто-то, как Шон мог.

599
00:35:16,930 --> 00:35:19,830
И хотя у нас есть такие простые примеры с 8 числа,

600
00:35:19,830 --> 00:35:24,000
Вы можете легко экстраполировать до 8 веб-страниц, 8 миллиардов веб-страниц,

601
00:35:24,000 --> 00:35:26,680
или 800 миллионов друзей на Facebook.

602
00:35:26,680 --> 00:35:30,090
Таким образом, эти алгоритмы, безусловно, может масштабироваться до тех видах ценностей,

603
00:35:30,090 --> 00:35:32,300
и идеи в конечном счете то же самое.

604
00:35:32,300 --> 00:35:36,140
Так пузырьковой сортировки была первой, где мы вроде пропускают самую большую человек

605
00:35:36,140 --> 00:35:39,110
все до упора вправо, меняя людей попарно.

606
00:35:39,110 --> 00:35:42,040
Тогда мы имели то, что мы называем выбора рода, где я немного более сознательно

607
00:35:42,040 --> 00:35:46,480
смотрел по списку, выбрав наименьшее число снова и снова и снова,

608
00:35:46,480 --> 00:35:49,530
Логическим результатом которого является то, что список, в конечном счете отсортированы.

609
00:35:49,530 --> 00:35:53,780
Тогда в третьем, я вставил людей в соответствующее место,

610
00:35:53,780 --> 00:35:57,720
и мы сделали очень надуманный пример в том, что список уже отсортирован,

611
00:35:57,720 --> 00:36:01,100
но это было отправить сообщение, что в случае сортировки вставкой, в

612
00:36:01,100 --> 00:36:02,670
Вы можете получить повезло.

613
00:36:02,670 --> 00:36:07,930
Если число уже отсортированы, он будет только у вас п шагов, чтобы подтвердить столько же,

614
00:36:07,930 --> 00:36:10,870
в то время как выбор рода вы немного более туннельное зрение

615
00:36:10,870 --> 00:36:14,360
и вы никогда не понимаете, что список уже отсортирован.

616
00:36:14,360 --> 00:36:16,830
Итак, давайте посмотрим пузырьковой сортировки в действии здесь.

617
00:36:16,830 --> 00:36:19,590
В следующем примере, мы собираемся, чтобы увидеть вертикальные полосы

618
00:36:19,590 --> 00:36:23,030
, высота которых представляют числа, так что мы можем сортировать визуализировать сортировка происходит.

619
00:36:23,030 --> 00:36:26,630
Чем меньше бара, чем меньше число, тем больше бара, тем больше число.

620
00:36:26,630 --> 00:36:28,860
>> И мы будем играть на этой скорости по умолчанию.

621
00:36:28,860 --> 00:36:33,460
Это будет двигаться слишком быстро сейчас, но красные это то, что показывает 2 бара

622
00:36:33,460 --> 00:36:35,480
сравниваются бок о бок.

623
00:36:35,480 --> 00:36:39,520
И если вы посмотрите внимательно, что происходит, что если бара вышли из строя,

624
00:36:39,520 --> 00:36:42,300
меньшего перемещен влево, больший вправо,

625
00:36:42,300 --> 00:36:44,360
а затем вы продолжаете двигаться вперед.

626
00:36:44,360 --> 00:36:48,520
Так что, если мы будем делать это снова и снова, заметил, что наименьшее баров

627
00:36:48,520 --> 00:36:51,090
собираетесь держать толчковой пути к левой

628
00:36:51,090 --> 00:36:54,130
и крупнейшего бара собираются держать толчковой их до упора вправо.

629
00:36:54,130 --> 00:36:58,490
И действительно, мы начинаем видеть картину полностью на правой стороне

630
00:36:58,490 --> 00:37:04,790
так же, как мы видели, 8 и затем 7 в конечном итоге бьет ключом к дальнему концу нашей человеческой списка.

631
00:37:04,790 --> 00:37:08,750
Так что это будет очень быстро получить немного утомительно, поэтому позвольте мне остановиться на мгновение.

632
00:37:08,750 --> 00:37:10,980
Позвольте мне изменить скорость будет намного быстрее.

633
00:37:10,980 --> 00:37:15,380
Я не изменяя алгоритм, я просто сделать анимацию произойдет быстрее.

634
00:37:15,380 --> 00:37:18,410
Тем не менее пузырьковой сортировки, тот же алгоритм,

635
00:37:18,410 --> 00:37:21,910
но теперь вы можете видеть гораздо быстрее, чем наша словесная демонстрация

636
00:37:21,910 --> 00:37:25,900
что самая большая элементы действительно бьет ключом к вершине.

637
00:37:25,900 --> 00:37:29,860
>> Как и в сторону, эти маленькие квадраты в нижней левой и нижней правой

638
00:37:29,860 --> 00:37:33,520
просто маленькие напоминания о том, как много сравнений вы делаете.

639
00:37:33,520 --> 00:37:37,620
Но сейчас, мы можем сосредоточиться на пирамиду которая складывается, и там она идет.

640
00:37:37,620 --> 00:37:41,510
Наименьший элемент находится на левом, самый большой на правой, а все остальное между ними.

641
00:37:41,510 --> 00:37:44,470
Теперь давайте вместо этого взглянем на выбор рода.

642
00:37:44,470 --> 00:37:47,260
Я собираюсь идти вперед и ударил Stop. Мы собираемся, чтобы получить новый случайный набор баров.

643
00:37:47,260 --> 00:37:50,930
Выбор рода, напомним, проходит через список снова и снова, и снова,

644
00:37:50,930 --> 00:37:54,900
выщипывание наименьший элемент. Так вот выбор рода.

645
00:37:54,900 --> 00:37:58,390
Похоже, там меньше работы происходит сейчас, потому что мы не сравниваем попарно

646
00:37:58,390 --> 00:38:02,590
но мы только вид cherry выбора наименьшего элемента справа налево.

647
00:38:02,590 --> 00:38:06,890
Это заняло очень мало времени, так что дихотомия уже.

648
00:38:06,890 --> 00:38:11,820
Просто потому, что алгоритм сказали взять п квадратов время, как пузырьковой сортировки

649
00:38:11,820 --> 00:38:16,100
и, как выбор рода, те действительно худшем случае работает раза.

650
00:38:16,100 --> 00:38:21,790
Например, в случае, скажем, выбор сортировки,

651
00:38:21,790 --> 00:38:27,240
Я на самом деле имею в выборе наименьшего человека и положить его или ее здесь,

652
00:38:27,240 --> 00:38:29,620
Затем я делаю это снова, то я делаю это снова,

653
00:38:29,620 --> 00:38:32,070
но там была небольшая оптимизация я мог бы сделать.

654
00:38:32,070 --> 00:38:35,040
>> Как только я переехал номер 1 здесь - Сэмми в этом случае -

655
00:38:35,040 --> 00:38:38,630
Что же я должен делать с ним после этого? >> [Студент] Оставь его.

656
00:38:38,630 --> 00:38:40,140
Оставь его, не так ли? Ничего.

657
00:38:40,140 --> 00:38:44,310
Мне не нужно, чтобы когда-либо поговорить с Сэмми снова, потому что, если бы я выбрал наименьший элемент

658
00:38:44,310 --> 00:38:48,580
и положил его здесь, зачем тратить время собирается до конца моих весь список?

659
00:38:48,580 --> 00:38:54,590
На следующей итерации позвольте мне на самом деле двигаться только на номер 2, только номер 3.

660
00:38:54,590 --> 00:38:57,640
Таким образом, в действительности, я не делаю вещей п п раз.

661
00:38:57,640 --> 00:39:05,380
Я делал вещи п, то п - 1 вещи, то п - 2 вещи, то п - 3 вещи,

662
00:39:05,380 --> 00:39:07,080
то п - 4, точка, точка, точка.

663
00:39:07,080 --> 00:39:09,470
У нас есть немного геометрической прогрессии, которая просто означает, что

664
00:39:09,470 --> 00:39:11,450
Вы добавляете вверх постепенно меньших количествах.

665
00:39:11,450 --> 00:39:17,940
Не N + N + N + N, а N + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
И что это вообще работает, чтобы быть -

667
00:39:21,380 --> 00:39:24,280
Я собираюсь испортить мой совет здесь на мгновение -

668
00:39:24,280 --> 00:39:28,990
, что будет работать, чтобы быть чем-то вроде п (п - 1) / 2

669
00:39:28,990 --> 00:39:31,930
если мы просто вид взгляда на задней математике книгу, где у вас есть все шпаргалок

670
00:39:31,930 --> 00:39:33,410
для формул.

671
00:39:33,410 --> 00:39:37,760
Если вы только добавить что-то N + N - 1 + п - 2, то выходит, должно быть что-то вроде этого.

672
00:39:37,760 --> 00:39:42,320
И если мы просто какая-то умножить на это, это п квадрате минус п / 2.

673
00:39:42,320 --> 00:39:46,400
Я все время говорил п квадратов, хотя, и это потому, что я был отчасти с психическими контекстном

674
00:39:46,400 --> 00:39:51,950
потому что в действительности, п квадрате минус п делится на 2, действительно, истинное число шагов

675
00:39:51,950 --> 00:39:55,510
что алгоритм выбора рода, как бы, если мы действительно подсчитали

676
00:39:55,510 --> 00:39:58,800
все эти сравнения и все немного занят работой мы делаем.

677
00:39:58,800 --> 00:40:03,210
Но, честно говоря, как только п добирается, чтобы быть как миллион или миллиард, кто, черт возьми заботится

678
00:40:03,210 --> 00:40:07,160
если вы делаете млрд. квадрате минус миллиард разделить на 2?

679
00:40:07,160 --> 00:40:09,320
Млрд. квадратов огромное количество.

680
00:40:09,320 --> 00:40:13,580
Вы можете взять еще один миллиард покинуть его с - п. Это не такое уж большое дело.

681
00:40:13,580 --> 00:40:18,770
Таким образом, чем больше номер, тем меньше важны эти нижние упорядоченной термины.

682
00:40:18,770 --> 00:40:24,230
Какая разница, если вы разделите на 2, если вы говорите о квадриллионы число шагов?

683
00:40:24,230 --> 00:40:29,710
>> Так что в целом, компьютерные ученые, как правило, выбрасывают все, но самый большой срок,

684
00:40:29,710 --> 00:40:33,140
и мы только отчасти упростить мир и сказать, что алгоритм

685
00:40:33,140 --> 00:40:38,130
потребовалось около п квадрат шаги. Это время работы алгоритма.

686
00:40:38,130 --> 00:40:40,760
Таким образом, мы вернемся к этому через минуту с некоторыми конкретными примерами,

687
00:40:40,760 --> 00:40:45,940
но сейчас, это своего рода интуитивное мотивация просто упрощение нашего мира

688
00:40:45,940 --> 00:40:51,170
и говорить о наиболее важных терминов, а не получать во все эти фантазии формул.

689
00:40:51,170 --> 00:40:53,540
Так, чтобы был выбор рода, и мы получили немного повезло.

690
00:40:53,540 --> 00:40:57,360
Давайте посмотрим на сортировку вставками. Позвольте мне пойти дальше и начать это одно, а.

691
00:40:57,360 --> 00:41:00,330
Теперь обратите внимание, что картины происходит немного иначе,

692
00:41:00,330 --> 00:41:03,410
и мы начали с случайных чисел,

693
00:41:03,410 --> 00:41:06,890
Но если мы на самом деле подсчитать количество шагов в худшем случае,

694
00:41:06,890 --> 00:41:11,070
Если в списке начал полностью в правильном порядке,

695
00:41:11,070 --> 00:41:13,380
мы только взять п шагов по реализации так много.

696
00:41:13,380 --> 00:41:18,240
>> Но если этот список были на самом деле в обратном направлении - например, в данном случае здесь -

697
00:41:18,240 --> 00:41:23,860
то заметите, что мы на самом деле нужно сделать еще очень много работы в этом случае.

698
00:41:23,860 --> 00:41:27,080
И это должно отчасти чувствую к тебе, как это один вид работать труднее

699
00:41:27,080 --> 00:41:30,900
чтобы получить эти мелкие элементы слева, и это потому, что мы не повезло.

700
00:41:30,900 --> 00:41:34,210
В списке были отсортированы случайно в обратном направлении.

701
00:41:34,210 --> 00:41:38,110
С другой стороны, со вставкой рода, если мы имитировать то, что мы сделали с нашим людям здесь

702
00:41:38,110 --> 00:41:42,670
, начиная с каждого сортируются, а затем начать, это довольно хороший алгоритм, правильно?

703
00:41:42,670 --> 00:41:45,010
Это уже, по сути, сортируются.

704
00:41:45,010 --> 00:41:48,670
Итак, давайте попробуем обобщить точно, сколько времени эти вещи с нами

705
00:41:48,670 --> 00:41:52,360
путем введения только немного жаргона или обозначения, которые на самом деле гораздо проще,

706
00:41:52,360 --> 00:41:54,320
по сравнению с крутостью рода предложения.

707
00:41:54,320 --> 00:41:59,030
Эта вещь здесь, это большая вывода на экран, это то, что ученый обычно используют

708
00:41:59,030 --> 00:42:03,640
Для описания худшем случае время выполнения алгоритма.

709
00:42:03,640 --> 00:42:07,360
>> Опять же, по худшем случае, это полностью зависит от контекста.

710
00:42:07,360 --> 00:42:10,890
Что мы подразумеваем под худшем случае полностью меняется в зависимости от проблемы, которую мы сейчас говорим.

711
00:42:10,890 --> 00:42:14,550
Но в случае сортировки, что самое худшее из возможных сценариев?

712
00:42:14,550 --> 00:42:17,860
Все назад, потому что он просто чувствует, что это означает, что много работы для нас.

713
00:42:17,860 --> 00:42:21,330
Я набросал несколько алгоритмов, которые мы видели до сих пор:

714
00:42:21,330 --> 00:42:24,930
линейный поиск, бинарный поиск, как с телефонной книгой или кусочки бумаги,

715
00:42:24,930 --> 00:42:28,960
Затем пузырьковой сортировки, отбора сортировки и сортировки вставкой, как мы видели, с нашими людьми,

716
00:42:28,960 --> 00:42:31,770
, а затем 1 друга, что в конечном счете будет называться сортировки слиянием.

717
00:42:31,770 --> 00:42:37,710
Таким образом, в линейный поиск в худшем случае, сколько шагов нужно для того, чтобы найти номер 7

718
00:42:37,710 --> 00:42:40,690
если есть п двери, как Шон лицом? >> [Студент] N.

719
00:42:40,690 --> 00:42:44,180
N. Таким образом, мы собираемся написать большую O н.

720
00:42:44,180 --> 00:42:47,010
Я просто хочу, чтобы заполнить некоторые пробелы. Это просто сетку пробелы.

721
00:42:47,010 --> 00:42:52,990
Но в лучшем случае с линейным поиском, 7, возможно, был в самом начале списка,

722
00:42:52,990 --> 00:42:55,520
Шон и, возможно, начали искать в начале списка.

723
00:42:55,520 --> 00:42:58,940
Так что, если вы используете линейный поиск и просто проверка слева направо или, может быть, справа налево -

724
00:42:58,940 --> 00:43:02,650
они эквивалентны - в лучшем случае, сколько шагов может линейного поиска,

725
00:43:02,650 --> 00:43:05,550
Алгоритм, как Шон, возьми? Всего в 1 шаг.

726
00:43:05,550 --> 00:43:09,450
>> Так что я собираюсь сказать, что это омега обозначений.

727
00:43:09,450 --> 00:43:11,570
Это просто столица омега.

728
00:43:11,570 --> 00:43:15,000
Omega просто сексуальный способ сказать лучшем случае время работы.

729
00:43:15,000 --> 00:43:18,900
Таким образом, в лучшем случае время выполнения одного шага или постоянное число шагов -

730
00:43:18,900 --> 00:43:24,270
1 в этом случае - но в худшем случае, большие О, это на самом деле п шагов.

731
00:43:24,270 --> 00:43:28,110
И это здесь, тета, на самом деле мы не будем смотреть на прямо сейчас.

732
00:43:28,110 --> 00:43:30,090
Это не относится к данному конкретном примере.

733
00:43:30,090 --> 00:43:31,990
А теперь давайте попробуем бинарный поиск.

734
00:43:31,990 --> 00:43:35,990
В худшем случае с бинарный поиск, сколько шагов он собирается предпринять, чтобы найти номер 7

735
00:43:35,990 --> 00:43:38,340
или что мы ищем? >> [Студент] Вход с.

736
00:43:38,340 --> 00:43:40,980
Тем не менее собираюсь взять журнал п, так как Алекс не повезло

737
00:43:40,980 --> 00:43:44,030
Когда мы действительно работали по проблеме методично

738
00:43:44,030 --> 00:43:48,220
и она не нашла номер 7 до самой последней двери, она посмотрела на,

739
00:43:48,220 --> 00:43:51,720
хотя, справедливости ради, она получила выбрасывать определенные двери по пути,

740
00:43:51,720 --> 00:43:56,920
бинарный поиск в худшем случае имеет время работы § п.

741
00:43:56,920 --> 00:43:59,230
И снова, что говорит на этот деления и завоевания.

742
00:43:59,230 --> 00:44:01,140
Но что в лучшем случае?

743
00:44:01,140 --> 00:44:04,790
А Алекс на самом деле испытали, что лучшем случае правы, когда она вышла на сцену.

744
00:44:04,790 --> 00:44:07,290
Сколько шагов сделал, что взять в бинарный поиск? >> [Студент] 1.

745
00:44:07,290 --> 00:44:09,380
1, только потому, что повезло.

746
00:44:09,380 --> 00:44:12,520
Но это нормально, потому что омега относится к лучшим сценариям,

747
00:44:12,520 --> 00:44:15,770
лучшем случае входов, даже если это всего лишь случайное удача.

748
00:44:15,770 --> 00:44:18,900
>> Теперь, это тоже мы собираемся просто какая-то отпуск пустой на данный момент.

749
00:44:18,900 --> 00:44:21,010
Как насчет сейчас пузырьковой сортировки?

750
00:44:21,010 --> 00:44:24,290
В худшем случае с пузырьковой сортировки, все в обратном порядке,

751
00:44:24,290 --> 00:44:26,380
так что мы должны сделать много пузырьков.

752
00:44:26,380 --> 00:44:30,190
Но сколько шагов является то, что собирается взять в худшем случае? >> [Студент] N в квадрате.

753
00:44:30,190 --> 00:44:32,550
Это был указан в квадрате, потому что если вы думаете об этом,

754
00:44:32,550 --> 00:44:36,410
если список полностью назад - 8, сюда, 1, здесь -

755
00:44:36,410 --> 00:44:40,530
как вещи начинают пузыриться, номер 8 будет двигаться таким образом, таким образом,

756
00:44:40,530 --> 00:44:44,540
Таким образом, этот способ, но где число 7 в худшем случае?

757
00:44:44,540 --> 00:44:47,720
Здесь она все еще там. Таким образом, мы должны делать это снова и снова.

758
00:44:47,720 --> 00:44:53,190
И вот, когда мы получаем п шагов, то п - 1 шагов, то п - 2 шага.

759
00:44:53,190 --> 00:44:55,960
И если вы верьте мне на слово, - что если вы вид умножить его,

760
00:44:55,960 --> 00:45:00,110
Это примерно п квадрат в конце концов с некоторыми другими условиями, которые мы будем просто игнорировать сейчас -

761
00:45:00,110 --> 00:45:06,890
Затем в худшем пузырьковой сортировки случае п в квадрате, плюс-минус.

762
00:45:06,890 --> 00:45:09,490
Но как насчет лучшем случае с пузырем рода?

763
00:45:09,490 --> 00:45:13,050
Что является лучшим сценарием? Все номера сортируются уже.

764
00:45:13,050 --> 00:45:15,920
И то, что было эвристический я использовал, уловка, которую я использовал,

765
00:45:15,920 --> 00:45:20,110
чтобы понять, что я не сделал работу и поэтому может остановить рано?

766
00:45:20,110 --> 00:45:23,590
[Студент] Проверьте это раз. >> Проверьте это раз. Но то, что я делаю на этом пути?

767
00:45:23,590 --> 00:45:26,130
Я был отслеживать, сколько свопа я сделал.

768
00:45:26,130 --> 00:45:30,650
И я понял, если бы я не считал любую свопы на пальцах, то я не сделал работу.

769
00:45:30,650 --> 00:45:34,300
Я, конечно, не следует пытаться делать никакой работы снова, так что я могу просто остановиться.

770
00:45:34,300 --> 00:45:37,830
>> Таким образом, в лучшем случае пузырьковой сортировки, когда список уже отсортирован,

771
00:45:37,830 --> 00:45:41,530
что бы вы сказали обозначения омега есть, в лучшем случае время работы?

772
00:45:41,530 --> 00:45:48,040
Это просто п. Мы должны сделать некоторую работу, но мы только должны сделать стоит 1 прогулка на работу.

773
00:45:48,040 --> 00:45:50,490
И здесь я собираюсь оставить эту часть пустым.

774
00:45:50,490 --> 00:45:52,430
И теперь выбор рода.

775
00:45:52,430 --> 00:45:56,010
Выбор подобного не мне, выщипывание наименьшее человек снова и снова.

776
00:45:56,010 --> 00:45:58,380
И что же мы говорим, что время работы, что было?

777
00:45:58,380 --> 00:46:00,590
Это был п квадрат в худшем случае.

778
00:46:00,590 --> 00:46:05,220
И, к сожалению, в лучшем случае он также п квадрат

779
00:46:05,220 --> 00:46:08,840
потому что у меня нет такого рода всезнающий вид на весь мир;

780
00:46:08,840 --> 00:46:13,140
Я знаю только после полной итерации, что я действительно нашел наименьшую человек.

781
00:46:13,140 --> 00:46:15,860
Таким образом, выбор рода вид сосет в том смысле,

782
00:46:15,860 --> 00:46:17,920
но Достоинством является то, что это отчасти интуитивно.

783
00:46:17,920 --> 00:46:21,470
Это довольно легко закодировать, потому что все, что вам нужно сделать, это написать несколько вложенных циклов,

784
00:46:21,470 --> 00:46:24,620
Обычно, которая проходит через ищем наименьший элемент

785
00:46:24,620 --> 00:46:27,840
а затем помещает наименьший элемент, где он находится в конце списка.

786
00:46:27,840 --> 00:46:29,900
Так что здесь тоже есть это будет компромисс.

787
00:46:29,900 --> 00:46:34,440
Количество времени, которое требуется, чтобы вы думали, и на самом деле что-то разрабатывать путем написания кода

788
00:46:34,440 --> 00:46:39,460
вполне может занять больше времени, если вы хотите лучше алгоритма и повышения производительности.

789
00:46:39,460 --> 00:46:41,780
>> Но если вы действительно только отчасти код что-то быстро и грязно

790
00:46:41,780 --> 00:46:45,000
и только отчасти взять на себя глупой идеей возможной Вы можете думать,

791
00:46:45,000 --> 00:46:47,580
, которые могут у вас несколько минут, чтобы код, но с большими наборами данных

792
00:46:47,580 --> 00:46:49,580
ваш алгоритм может занять несколько часов, чтобы бежать.

793
00:46:49,580 --> 00:46:51,690
И даже я в аспирантуре иногда сделать эти компромиссы.

794
00:46:51,690 --> 00:46:55,660
Было бы 3 часа ночи, я пытался проанализировать некоторые очень больших наборов данных

795
00:46:55,660 --> 00:46:59,650
связанных с безопасностью исследований я делаю, и это было либо потратить 5 минут

796
00:46:59,650 --> 00:47:03,210
настройки моей программы для анализа данных и пойти спать

797
00:47:03,210 --> 00:47:08,420
или провести 8 часов получить его правой так, он работает сразу, а не спать.

798
00:47:08,420 --> 00:47:10,530
И так там тоже своего рода сознательное решение.

799
00:47:10,530 --> 00:47:12,740
Менее время разработки, больше спать.

800
00:47:12,740 --> 00:47:14,780
Оглядываясь назад, я, вероятно, не следует поощрять, что

801
00:47:14,780 --> 00:47:19,120
когда цель здесь заключается в оптимизации качества кода,

802
00:47:19,120 --> 00:47:21,280
но это тоже в реальном мире это очень разумный компромисс.

803
00:47:21,280 --> 00:47:25,130
Меньше времени, меньше производительность, или наоборот.

804
00:47:25,130 --> 00:47:28,110
Так вот мы, наконец, получили возможность говорить о тета.

805
00:47:28,110 --> 00:47:32,830
Theta обозначения чего-то компьютере ученые могут поднять в разговоре

806
00:47:32,830 --> 00:47:36,160
При большом O и омега случится то же самое.

807
00:47:36,160 --> 00:47:40,160
Вы говорите, что тета, чтобы действительно отправить сообщение, что это вид плотно связаны.

808
00:47:40,160 --> 00:47:43,340
Независимо от того, является ли сценарий, хорошо это или плохо, это п квадрат.

809
00:47:43,340 --> 00:47:46,510
Так что это просто не имеет значения в этих историях здесь.

810
00:47:46,510 --> 00:47:48,560
Вставка рода является последним мы смотрели на,

811
00:47:48,560 --> 00:47:50,830
где я был просто вставляете всех в нужное место.

812
00:47:50,830 --> 00:47:54,930
В лучшем случае то, что было время работы сортировки вставками, как мы видели его здесь?

813
00:47:54,930 --> 00:47:57,250
[Студент] лучшем случае? >> Лучшем случае.

814
00:47:57,250 --> 00:48:00,100
>> Было п, потому что в лучшем случае все сортируется,

815
00:48:00,100 --> 00:48:02,580
и Сэмми и никто действительно было двигаться.

816
00:48:02,580 --> 00:48:04,610
Они уже были на своих местах.

817
00:48:04,610 --> 00:48:08,570
Так сортировки вставкой в ​​лучшем случае, в данном случае, с.

818
00:48:08,570 --> 00:48:12,770
Но в худшем случае это вроде п квадрат. Почему?

819
00:48:12,770 --> 00:48:16,230
Если мой список людей в обратном порядке,

820
00:48:16,230 --> 00:48:21,260
Я сначала начать с номером 8 и вставить его или ее в правильное положение, которое прямо здесь.

821
00:48:21,260 --> 00:48:25,270
Я как бы движение в сторону. Эти ребята несортированные, он или она сортируется.

822
00:48:25,270 --> 00:48:28,970
Но теперь я, случается, выяснить, кто следующий? >> [Студент] 7.

823
00:48:28,970 --> 00:48:31,250
7, в худшем случае, потому что это в обратном порядке.

824
00:48:31,250 --> 00:48:34,920
>> Так вот 7. Где 7 принадлежите? Определенно у меня за спиной.

825
00:48:34,920 --> 00:48:39,460
Но сейчас 7 на самом деле принадлежит не сразу позади меня, но за № 8,

826
00:48:39,460 --> 00:48:41,880
так что я должен сказать: "Извините, номер 8, пожалуйста, вы можете двигаться таким образом,

827
00:48:41,880 --> 00:48:44,640
"Чтобы освободить место для 7?" Сейчас я сталкиваюсь 6.

828
00:48:44,640 --> 00:48:48,530
"Ах, извините, № 8 и № 7, вы можете двигаться, чтобы освободить место для 6?"

829
00:48:48,530 --> 00:48:52,360
Итак, другими словами, со вставкой рода, хотя я не делаю много движений,

830
00:48:52,360 --> 00:48:56,330
люди за меня делают еще очень много работы, и это должен стоить раз, когда кто-то.

831
00:48:56,330 --> 00:48:58,000
Это будет стоить машинного времени.

832
00:48:58,000 --> 00:49:01,450
Таким образом, в случае введения подобного мы до сих пор страдаем.

833
00:49:01,450 --> 00:49:06,260
Если вы начинаете сложения общее число шагов, мы в конечном итоге удара примерно п квадрат

834
00:49:06,260 --> 00:49:11,160
потому что эти парни нужны, чтобы освободить место для человека должен быть вставлен обратно в этот список.

835
00:49:11,160 --> 00:49:15,960
И поэтому в данном случае тета просто не применима к конкретной истории под рукой.

836
00:49:15,960 --> 00:49:21,100
Это все хорошо и хорошо. У нас есть эти 3 различных способа говорить о времени работы.

837
00:49:21,100 --> 00:49:26,370
Но что это на самом деле означает в реальном выражении, если мы на самом деле пытаются код до алгоритма?

838
00:49:26,370 --> 00:49:31,620
>> Позвольте мне предложить, что есть еще лучше, алгоритм там

839
00:49:31,620 --> 00:49:33,740
, который сам имеет некоторые компромиссы.

840
00:49:33,740 --> 00:49:36,890
Мы будем называть его сортировки слиянием, и это своего рода этом волшебном алгоритм

841
00:49:36,890 --> 00:49:42,840
, который просто работает быстрее так или иначе, и это так легко выразить, по крайней мере в псевдокоде.

842
00:49:42,840 --> 00:49:46,900
Реализация данного алгоритма сортировки слиянием будет следующим образом.

843
00:49:46,900 --> 00:49:50,860
Когда вам дают п элементов - N чисел, русские люди, независимо - первая есть здравомыслие проверка.

844
00:49:50,860 --> 00:49:56,340
Если п меньше, чем 2, сортировка слиянием просто останавливается. Он возвращается, так сказать.

845
00:49:56,340 --> 00:50:00,830
Почему бы вам остановиться, если N меньше, чем 2? >> [Неразборчиво ответ студента]

846
00:50:00,830 --> 00:50:04,480
Право. И снова, п не номер в списке, п является размер списка.

847
00:50:04,480 --> 00:50:07,660
Если п меньше, чем 2, это означает, что список является либо 1,

848
00:50:07,660 --> 00:50:09,640
где вы, очевидно, отсортированный если это 1 номер,

849
00:50:09,640 --> 00:50:11,710
или 0, в этом случае нет ничего, чтобы разобраться,

850
00:50:11,710 --> 00:50:13,570
поэтому мы должны такого рода базовым сценарием.

851
00:50:13,570 --> 00:50:20,350
Если в списке так мало, что там просто нечего делать, в буквальном смысле не делать ничего. Возвращение.

852
00:50:20,350 --> 00:50:25,090
В противном случае отсортировать левую половину элементов, а затем отсортировать правую половину элементов,

853
00:50:25,090 --> 00:50:27,410
затем объединить 2 Упорядочить половины.

854
00:50:27,410 --> 00:50:32,130
>> Этот вид кажется немного обмануть которой я прошу вас, как отсортировать элементы

855
00:50:32,130 --> 00:50:34,900
и ты говоришь мне, "Сортировка левой половине, сортировать правую половину".

856
00:50:34,900 --> 00:50:37,240
Я, как: "Все в порядке. Как сортировать левую половину?"

857
00:50:37,240 --> 00:50:40,670
"Сортировать левую половину левой половине, сортировать правой половине левой половине, а затем сделать".

858
00:50:40,670 --> 00:50:44,060
Ты вид циклически определения того, что это означает для сортировки,

859
00:50:44,060 --> 00:50:46,790
но оказывается, что на самом деле блестящая в этом случае.

860
00:50:46,790 --> 00:50:50,230
Это не по-настоящему этот порочный круг, который никогда не заканчивается

861
00:50:50,230 --> 00:50:52,550
потому что оно закончится, когда? >> [Студент] Когда Вы достигнете 1 вещь.

862
00:50:52,550 --> 00:50:54,220
Когда вы достигнете 1 вещь.

863
00:50:54,220 --> 00:50:57,850
Поэтому, даже если вы можете начать с 8 человек, и я говорю: "Сортировка левая половина из этих людей,

864
00:50:57,850 --> 00:51:00,480
этих 4-х человек ", то я говорю:« Как сортировать левую половину? "

865
00:51:00,480 --> 00:51:03,450
"Ну, вроде 2 человека здесь". И тогда вы, как: "Хорошо, хорошо".

866
00:51:03,450 --> 00:51:05,520
"Как вы сортировать левой половины этих людей?"

867
00:51:05,520 --> 00:51:09,040
"Просто разобраться в этом 1 человек здесь". Что такое блестящее откровение сейчас?

868
00:51:09,040 --> 00:51:13,050
У меня есть для сортировки 1 человек. Готово. Я не должен делать любую работу.

869
00:51:13,050 --> 00:51:16,580
Но теперь я должен разобраться в этом человеке, но они одним человеком, делать нечего.

870
00:51:16,580 --> 00:51:21,490
>> Таким образом, магия по-видимому, в этом третий шаг: слияния отсортированных половинки.

871
00:51:21,490 --> 00:51:25,770
Таким образом, сортировка слиянием принимает эту блестящую понимание того, что если вы нарушите большая проблема вниз

872
00:51:25,770 --> 00:51:28,650
на 2 меньше, одинаково размера проблемы

873
00:51:28,650 --> 00:51:32,710
, а затем просто вид клея меньше решений вместе в конце,

874
00:51:32,710 --> 00:51:34,720
Я полагаю, что мы можем сделать гораздо, гораздо лучше [нажав звук]

875
00:51:34,720 --> 00:51:38,050
чем любой из рода отбор или сортировку вставками.

876
00:51:38,050 --> 00:51:40,690
Я на самом деле игнорировал, что в течение получаса, но я действительно не знаю, что происходит

877
00:51:40,690 --> 00:51:45,040
за пределами сегодня. [Жужжащий звук] [смех]

878
00:51:45,040 --> 00:51:49,660
Итак, давайте посмотрим, если мы можем увидеть это с небольшой помощью от нашего друга Роба Боуден.

879
00:51:49,660 --> 00:51:52,810
Есть 2 большие шаги в процессе сортировки слиянием.

880
00:51:52,810 --> 00:51:56,400
Во-первых, непрерывно разделить список чашки пополам

881
00:51:56,400 --> 00:51:59,610
до тех пор пока у нас есть куча списков только с 1 чашкой в ​​них.

882
00:51:59,610 --> 00:52:02,150
Не волнуйтесь, если список содержит нечетное число

883
00:52:02,150 --> 00:52:04,830
и вы не можете сделать идеально чистый срез между ними.

884
00:52:04,830 --> 00:52:08,740
Просто произвольно выбрать, какой список, включив дополнительную чашку дюйма

885
00:52:08,740 --> 00:52:11,320
Так что давайте разделить эти списки.

886
00:52:12,420 --> 00:52:14,570
Теперь у нас есть 2 списка.

887
00:52:18,930 --> 00:52:20,930
Теперь у нас есть 4 списков.

888
00:52:25,730 --> 00:52:28,740
Теперь у нас есть 8 списков с одной чашки в каждом списке.

889
00:52:28,740 --> 00:52:31,520
Так вот оно что на шаге 1.

890
00:52:31,520 --> 00:52:37,280
Для шаге 2 мы неоднократно слияния пары списков с использованием алгоритма слияния мы узнали раньше.

891
00:52:37,280 --> 00:52:44,320
Слияние 108 и 15 мы в конечном итоге со списком 15, 108.

892
00:52:45,240 --> 00:52:51,330
Слияние 50 и 4, мы в конечном итоге с 4, 50.

893
00:52:51,330 --> 00:52:56,950
Слияние 8 и 42 мы в конечном итоге с 8, 42.

894
00:52:57,790 --> 00:53:04,360
И слияние 23 и 16, мы в конечном итоге с 16, 23.

895
00:53:04,360 --> 00:53:08,030
Теперь все наши списки размера 2.

896
00:53:08,030 --> 00:53:10,980
Обратите внимание, что каждый из 4 списков сортируется,

897
00:53:10,980 --> 00:53:14,230
так что мы можем начать слияние пары списки.

898
00:53:14,230 --> 00:53:22,150
Слияние 15 и 108, а 4 и 50 мы сначала взять 4, то 15,

899
00:53:22,150 --> 00:53:26,250
то 50, то 108.

900
00:53:26,250 --> 00:53:33,020
Слияние 8, 42 и 16, 23 мы сначала взять 8, затем 16,

901
00:53:33,020 --> 00:53:37,170
то 23, то 42.

902
00:53:37,170 --> 00:53:42,490
Так что теперь у нас есть всего 2 списки размер 4, каждая из которых сортируется.

903
00:53:42,490 --> 00:53:45,940
Итак, теперь мы объединить эти 2 списка.

904
00:53:45,940 --> 00:53:54,230
Сначала мы берем 4, то мы берем 8, то мы берем 15

905
00:53:54,230 --> 00:54:05,280
и 16 и 23 и 42 и 50 и 108.

906
00:54:05,280 --> 00:54:09,020
И мы сделали. Теперь у нас есть отсортированный список.

907
00:54:09,020 --> 00:54:13,740
>> Роб был отчасти воспользовавшись что-то, что мы еще не сделали.

908
00:54:13,740 --> 00:54:16,540
Было высказано мнение, но мы на самом деле не делать.

909
00:54:16,540 --> 00:54:19,230
Он делал что-то физически с чашками, который предполагает

910
00:54:19,230 --> 00:54:23,680
он проводил некоторый ресурс, кроме времени. >> [Студент] пространства. >> Это было пространство.

911
00:54:23,680 --> 00:54:27,360
Тот факт, что он был такого рода двухуровневая таблица, где он был пространство здесь

912
00:54:27,360 --> 00:54:31,960
и пространство здесь было на самом деле это означает, что он использует два раза больше места

913
00:54:31,960 --> 00:54:36,390
как любой из наших алгоритмов до сих пор - сортировка вставкой, пузырьковая сортировка, или выбор рода -

914
00:54:36,390 --> 00:54:40,780
но он был использованию этого дополнительного пространства для вида ходу вещей и обратно

915
00:54:40,780 --> 00:54:42,600
, сохраняя при этом порядок.

916
00:54:42,600 --> 00:54:47,540
И хотя он чувствует, как мы добрались до отсортированный список, который чувствовал, что это потребовалось время.

917
00:54:47,540 --> 00:54:51,060
В действительности, то, что Роб делал именно этот алгоритм.

918
00:54:51,060 --> 00:54:56,780
Он первым принял проблема размера п, разделил его на левую половину и правую половины.

919
00:54:56,780 --> 00:54:59,380
Вот когда он переехал чашки. Затем он повторил этот процесс.

920
00:54:59,380 --> 00:55:03,390
Он разделил 4 в 2 подхода из 2 здесь и здесь.

921
00:55:03,390 --> 00:55:08,520
Затем он повторил, что процесс и разделить 2 на 2 комплекта 1 для каждого из этих различных кубков.

922
00:55:08,520 --> 00:55:11,000
И вот, когда блестящая возможность.

923
00:55:11,000 --> 00:55:15,840
В этот момент в истории, Роб был 8 списков размер 1,

924
00:55:15,840 --> 00:55:18,860
все из которых были отсортированы уже.

925
00:55:18,860 --> 00:55:20,630
>> Итак, что же он продолжить делать?

926
00:55:20,630 --> 00:55:25,260
Парные он взял это отсортированный список, и это отсортированный список и объединить их.

927
00:55:25,260 --> 00:55:28,200
Затем он взял эту и объединить их, то это одно и объединить их,

928
00:55:28,200 --> 00:55:30,670
то это одно и объединить их.

929
00:55:30,670 --> 00:55:32,390
А то, что он сделал дальше?

930
00:55:32,390 --> 00:55:36,580
Он затем снова объединить большие списки, а затем снова объединить большие списки.

931
00:55:36,580 --> 00:55:41,170
И если вы думаете об этом просто интуитивно сейчас, то, что он действительно делает?

932
00:55:41,170 --> 00:55:45,450
Он был делением проблема в два раза, в два раза, в два раза, в два раза

933
00:55:45,450 --> 00:55:47,600
для того, чтобы получить эти сверхмалые списки.

934
00:55:47,600 --> 00:55:51,290
Тогда он был добр объединения двухместные, двухместные, двухместные, двухместные.

935
00:55:51,290 --> 00:55:54,120
Так он делал в два раза больше работы, чем мы видели до сих пор

936
00:55:54,120 --> 00:55:56,930
с чем с участием разделяй и властвуй, но не большая проблема.

937
00:55:56,930 --> 00:55:59,630
В два раза больше работы не такое уж большое дело. Это всего лишь постоянным множителем.

938
00:55:59,630 --> 00:56:03,920
И так же, как наши арифметические выражения и раньше, я просто хочу, чтобы вычеркнуть постоянными коэффициентами

939
00:56:03,920 --> 00:56:10,170
как раз 2. Кого это волнует? Если это 2 млрд. раза 2, что еще много шагов.

940
00:56:10,170 --> 00:56:13,160
Так что это слияние шагом, кажется, ключевым пониманием.

941
00:56:13,160 --> 00:56:17,000
Давайте пройдем через это только численно раньше - О, это не будет продолжаться еще нет.

942
00:56:17,000 --> 00:56:22,890
Давайте пройдемся по этим численно просто на самом деле увидеть, как это теряет значение.

943
00:56:22,890 --> 00:56:25,940
Это в основном только анимация немного бедного человека.

944
00:56:25,940 --> 00:56:27,750
Давайте предлагать это.

945
00:56:27,750 --> 00:56:31,480
Время работы сортировки слиянием - мы просто нужен способ говорить об этом.

946
00:56:31,480 --> 00:56:34,380
Это не математика, это просто какая-то краткий способ выразить себя.

947
00:56:34,380 --> 00:56:39,080
Таким образом, T представляет собой время и п представляет то, что? >> [Студент] размер -

948
00:56:39,080 --> 00:56:41,400
>> [Малан] Размер проблемы, число людей.

949
00:56:41,400 --> 00:56:45,470
Так что я утверждая, что время для сортировки русского народа будет 0 количество времени

950
00:56:45,470 --> 00:56:50,290
если п меньше 2, потому что, если у вас есть 1 чашка или нет чашки, у вас нет ничего, чтобы отсортировать.

951
00:56:50,290 --> 00:56:55,160
Но в целом, я собираюсь предложить, что время для сортировки п элементов

952
00:56:55,160 --> 00:56:59,350
будет время, необходимое для сортировки левой половины плюс правой половины

953
00:56:59,350 --> 00:57:03,110
плюс - то, что это дополнительное + п? >> [Студент] Слияние рода.

954
00:57:03,110 --> 00:57:07,260
[Малан] Это на самом деле слияния, потому что, если у вас есть п / 2 элементов здесь

955
00:57:07,260 --> 00:57:11,500
и у вас есть п / 2 элементов здесь, сколько времени нужно, чтобы их объединить?

956
00:57:11,500 --> 00:57:15,050
Так же, как Роб, вы должны вырвать эту сюда, может быть, вырвать здесь,

957
00:57:15,050 --> 00:57:17,120
срывать здесь, вырви здесь, вырви здесь.

958
00:57:17,120 --> 00:57:19,400
Вы должны коснуться каждого из стакана один раз.

959
00:57:19,400 --> 00:57:22,030
И если есть 4 чашки плюс 4 чашки, это 8 чашек

960
00:57:22,030 --> 00:57:25,200
или, более общо, 8 п чашки.

961
00:57:25,200 --> 00:57:28,470
Таким образом, слияние шаге мы можем выразить, как я,

962
00:57:28,470 --> 00:57:31,330
и что буквально включает в себя несколько раз Роб физически коснулся

963
00:57:31,330 --> 00:57:33,410
один из тех пенополистирола чашки.

964
00:57:33,410 --> 00:57:35,850
Итак, давайте делать произвольные пример.

965
00:57:35,850 --> 00:57:41,850
Если есть 16 чашек, что время работы сортировки, используя алгоритм Роба, 16 чашек?

966
00:57:41,850 --> 00:57:44,710
Это в 2 раза количество времени, затрачиваемое на сортировку 8 чашек

967
00:57:44,710 --> 00:57:46,920
потому что у нас здесь 8 чашек, 8 чашек здесь.

968
00:57:46,920 --> 00:57:51,520
Я не знаю, как долго это берет, так что мы обобщающих его как T на данный момент.

969
00:57:51,520 --> 00:57:53,320
Кто знает, что это такое?

970
00:57:53,320 --> 00:57:58,990
Но теперь я могу сортировать рекурсивно или несколько раз задать тот же вопрос.

971
00:57:58,990 --> 00:58:01,920
Сколько времени нужно для того, чтобы отсортировать 8 чашек?

972
00:58:01,920 --> 00:58:07,030
8 чашек я собираюсь сказать, занимает количество времени, затрачиваемое на сортировку 4 чашки плюс 4 чашки,

973
00:58:07,030 --> 00:58:08,880
затем объединять их вместе.

974
00:58:08,880 --> 00:58:13,080
Хорошо. Мы входим в цикл уже. Сколько времени это займет, чтобы отсортировать 4 чашки?

975
00:58:13,080 --> 00:58:19,150
Время, необходимое для сортировки 4 стакана составляет 2 чашки плюс 2 чашки плюс сортировка процесс слияния.

976
00:58:19,150 --> 00:58:21,440
Хорошо. Сколько времени это займет, чтобы отсортировать 2 чашки?

977
00:58:21,440 --> 00:58:26,290
2 чашки является количество времени, необходимое для сортировки 1 чашка плюс время, необходимое для сортировки еще одну чашку

978
00:58:26,290 --> 00:58:29,040
плюс количество времени, необходимое для слияния, которое находится всего в 2.

979
00:58:29,040 --> 00:58:33,340
>> Хорошо. Последний вопрос. Сколько времени это займет, чтобы отсортировать 1 стакан?

980
00:58:33,340 --> 00:58:37,260
Вот базовый вариант, что мы и предсказывали мы бы ударить раньше.

981
00:58:37,260 --> 00:58:42,250
Дело в том, что он принимает никаких работ вообще, чтобы разобраться наименьшей из проблем

982
00:58:42,250 --> 00:58:44,120
означает, что теперь, вроде класс стиля школы,

983
00:58:44,120 --> 00:58:46,460
мы можем просто пойти начать подключение этих цифр масштаб

984
00:58:46,460 --> 00:58:50,630
Мы теперь знаем, что T 1 является, таким образом я могу подключить 0 при Т 1.

985
00:58:50,630 --> 00:58:54,420
Это даст мне ответ на T 2, который я потом можно подключить выше.

986
00:58:54,420 --> 00:58:56,930
Это даст мне Т 4, который я могу подключить выше.

987
00:58:56,930 --> 00:58:58,920
Это даст мне T 8, который я могу подключить выше.

988
00:58:58,920 --> 00:59:04,330
А если я на самом деле, что математика, подключив эти ответы,

989
00:59:04,330 --> 00:59:08,590
Я тогда получим T от 16 64.

990
00:59:08,590 --> 00:59:12,090
А что значит 64 представляют?

991
00:59:12,090 --> 00:59:15,700
Если Т 16, да, это в 16 раз 4.

992
00:59:15,700 --> 00:59:20,120
Таким образом, я утверждаю теперь, что время работы, что называется сортировка слиянием -

993
00:59:20,120 --> 00:59:22,590
и это будет самый необычный из тех, что мы видели до сих пор -

994
00:59:22,590 --> 00:59:26,160
будет называться п § п

995
00:59:26,160 --> 00:59:31,140
потому что сколько раз может лишить разделить целую кучу чашки пополам? Вход с.

996
00:59:31,140 --> 00:59:34,370
Это то же самое, например, телефонную книгу, это так же, как самостоятельного подсчета пример.

997
00:59:34,370 --> 00:59:36,380
>> Сколько раз Вы можете что-то делить пополам?

998
00:59:36,380 --> 00:59:38,410
Однако, есть это слияние шагом.

999
00:59:38,410 --> 00:59:42,920
Возможно, вам придется делить чашки пополам снова и снова, и снова,

1000
00:59:42,920 --> 00:59:45,640
но каждый раз, когда вы будете иметь, чтобы слияние.

1001
00:59:45,640 --> 00:59:48,270
И мы сказали ранее, что слияние п чашки занимает п шагов

1002
00:59:48,270 --> 00:59:52,060
потому что вы должны вырвать из чашки, вырвать из чашки, и вы должны коснуться каждого стакана один раз,

1003
00:59:52,060 --> 00:59:53,510
так же, как Роб сделал.

1004
00:59:53,510 --> 00:59:59,430
Таким образом, если мы делаем что-то журнал N раз, и мы делаем п вещей на каждый из этих итераций,

1005
00:59:59,430 --> 01:00:03,090
каждый из этих полураспадов, у нас есть п раз журнал с.

1006
01:00:03,090 --> 01:00:07,220
Поэтому, если мы подключить 16 в этом примере, в 16 раз войти в 16 -

1007
01:00:07,220 --> 01:00:10,600
Не волнуйтесь о том, почему это так, на данный момент, потому что я не обращала базы -

1008
01:00:10,600 --> 01:00:16,100
но журнал базе 2 из 16 в 4, 16 раза 4, 64.

1009
01:00:16,100 --> 01:00:22,350
Но в отличие от, если бы мы использовали пузырьковой сортировки и сортировки выбором сортировки или вставке с 16 числа,

1010
01:00:22,350 --> 01:00:26,420
что бы время работы было, если п 16?

1011
01:00:26,420 --> 01:00:33,310
Это будет 16 квадратов, которая является 256, что, даже если вы не совсем следовал всем математике,

1012
01:00:33,310 --> 01:00:38,390
256 это больше, чем 64. Это действительно волшебный вынос здесь.

1013
01:00:38,390 --> 01:00:41,990
И понимаю, что работать через это в меньшей примеры, как вы будете на PSET

1014
01:00:41,990 --> 01:00:44,260
делает его еще более интуитивным.

1015
01:00:44,260 --> 01:00:49,070
Но что это означает в терминах чувства этого алгоритма заключается в следующем:

1016
01:00:49,070 --> 01:00:54,520
Если мы на самом деле смотрим на сортировка слиянием здесь - дайте мне потяните его вверх в этом окне здесь -

1017
01:00:54,520 --> 01:00:58,560
это немного другой пример, которому мы должны все 3 из этих алгоритмов -

1018
01:00:58,560 --> 01:01:01,440
Пузырь, отбора и слияния - просто бок о бок.

1019
01:01:01,440 --> 01:01:03,740
>> Они все началось со случайной баров, и это хорошо.

1020
01:01:03,740 --> 01:01:06,240
Никто не имеет фундаментальное преимущество над другими.

1021
01:01:06,240 --> 01:01:09,500
Я собираюсь в момент щелкните каждый из этих анимации - Пуск, Пуск, Пуск -

1022
01:01:09,500 --> 01:01:13,270
так быстро, как могу, так что, грубо говоря, все они начинаются в то же время,

1023
01:01:13,270 --> 01:01:17,450
и давайте считать, что худшем случае пузырьковой сортировки по времени работы это что? >> [Студент] N в квадрате.

1024
01:01:17,450 --> 01:01:21,560
N в квадрате. Худшем случае выбора рода бежит время? N в квадрате.

1025
01:01:21,560 --> 01:01:25,150
И сортировка слиянием видимо - даже если вы не совсем понимаю всю математику сейчас,

1026
01:01:25,150 --> 01:01:30,610
это станет значительно более интуитивным в течение долгого времени - это, мы утверждаем, п § п раз.

1027
01:01:30,610 --> 01:01:35,210
И потому, что § п строго меньше п раз у нас есть большие номера,

1028
01:01:35,210 --> 01:01:40,230
п § п раз меньше, чем раз п п или п квадрат.

1029
01:01:40,230 --> 01:01:44,410
Так что же это чувствует, чтобы быть на самом деле лучший алгоритм с точки зрения времени работы,

1030
01:01:44,410 --> 01:01:50,380
п § п раз, в отличие от п квадратов? Здесь мы идем. Клик, клик, клик.

1031
01:01:55,690 --> 01:01:58,650
>> Вот что значит использовать что-то вроде сортировки слиянием.

1032
01:01:58,650 --> 01:02:01,680
У нас есть время. Давайте посмотрим, что происходит здесь.

1033
01:02:09,440 --> 01:02:12,440
[Смеется] Чьи деньги на пузырьковой сортировки?

1034
01:02:14,960 --> 01:02:16,730
Это скорее зависит от входного иногда.

1035
01:02:16,730 --> 01:02:18,120
Давайте посмотрим.

1036
01:02:18,120 --> 01:02:23,320
Пойдем. Он чувствует, как он догоняет. >> [Студент]: пойди, пузырьковой сортировки!

1037
01:02:23,320 --> 01:02:27,370
[Студентам ропот]

1038
01:02:27,370 --> 01:02:29,120
[Малан] Да, да.

1039
01:02:29,120 --> 01:02:34,520
[Студентам ропот] Иди, иди, иди!

1040
01:02:37,210 --> 01:02:40,450
[Все аплодисменты] [аплодисменты]

1041
01:02:40,450 --> 01:02:46,240
Так что теперь с 1 последний, окончательный демо, если это немного хитро, чтобы обернуть ваш разум вокруг математике

1042
01:02:46,240 --> 01:02:49,280
или своего рода визуализация есть, вы можете услышать скорости

1043
01:02:49,280 --> 01:02:51,000
различных алгоритмов по-разному.

1044
01:02:51,000 --> 01:02:53,900
Это анимация кто-то сделал, что на самом деле звучит партнеров

1045
01:02:53,900 --> 01:02:56,980
с процессом замены и высота баров.

1046
01:02:56,980 --> 01:03:00,440
Как мы увидим здесь, есть несколько алгоритмов сортировки, что там люди не подумал.

1047
01:03:00,440 --> 01:03:03,660
Это первая будет сортировку вставками, и это будет пролететь через

1048
01:03:03,660 --> 01:03:07,090
и дать вам звуковой смысле, как эти различные алгоритмы работы.

1049
01:03:07,090 --> 01:03:09,080
Вот сортировки вставкой.

1050
01:03:09,080 --> 01:03:18,410
[Электронный звуковой сигнал]

1051
01:03:18,410 --> 01:03:20,730
[Малан] Bubble рода.

1052
01:03:20,730 --> 01:03:46,850
[Быстрый электронный звуковой сигнал]

1053
01:03:46,850 --> 01:03:48,950
[Малан] Выбор рода.

1054
01:03:48,950 --> 01:04:03,580
[Быстрый электронный звуковой сигнал]

1055
01:04:03,580 --> 01:04:05,770
[Малан] Слияние рода.

1056
01:04:05,770 --> 01:04:17,270
[Электронный звуковой сигнал]

1057
01:04:17,270 --> 01:04:20,180
[Звуковой сигнал замедляется] [смех]

1058
01:04:20,180 --> 01:04:22,590
[Малан] Gnome рода.

1059
01:04:22,590 --> 01:04:38,580
[Электронный звуковой сигнал]

1060
01:04:39,740 --> 01:04:46,150
>> Это CS50. Увидимся на следующей неделе. [Аплодисменты и крики]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]