1
00:00:00,000 --> 00:00:11,904
>> [Играет музыка]

2
00:00:11,904 --> 00:00:12,910
>> ПРОФЕССОР: Все правильно.

3
00:00:12,910 --> 00:00:16,730
Это CS50, и это
конец недели три.

4
00:00:16,730 --> 00:00:20,230
Так что мы здесь сегодня, а не в Сандерс
Театр, вместо этого в Weidner библиотеки.

5
00:00:20,230 --> 00:00:23,170
Внутри которого является студия
известный как Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
или, скажем, студия H, или должны
мы say-- если вам понравилось, что шутка,

7
00:00:28,310 --> 00:00:30,540
это на самом деле от
одноклассник, Марк, онлайн,

8
00:00:30,540 --> 00:00:32,420
который предложил столько с помощью Twitter.

9
00:00:32,420 --> 00:00:34,270
Теперь то, что это круто о
будучи здесь в студии

10
00:00:34,270 --> 00:00:38,410
является то, что я окружен эти зеленые
стены, зеленый экран или цветности,

11
00:00:38,410 --> 00:00:43,290
так сказать, что означает, что CS50-х
Производство команда, без моего ведома

12
00:00:43,290 --> 00:00:47,380
Прямо сейчас, может быть положить
меня больше нигде в мире,

13
00:00:47,380 --> 00:00:48,660
лучше или хуже.

14
00:00:48,660 --> 00:00:51,800
>> Теперь то, что лежит впереди, установить проблема
двух в ваших руках в течение этой недели,

15
00:00:51,800 --> 00:00:53,830
но с проблемой установить
три на следующей неделе,

16
00:00:53,830 --> 00:00:56,600
Вы будете вызов с
так называемый игра 15,

17
00:00:56,600 --> 00:00:58,960
старый вечере, что
Вы могли бы вспомнить приема

18
00:00:58,960 --> 00:01:02,030
как ребенок, который имеет целый букет
чисел, которые могут скользить вверх, вниз,

19
00:01:02,030 --> 00:01:05,790
слева и справа, и есть один пробел
в головоломки, в которую вы

20
00:01:05,790 --> 00:01:07,840
может на самом деле эти слайд кусочки головоломки.

21
00:01:07,840 --> 00:01:11,150
В конечном итоге вы получите это письмо
головоломка, в какой-то полу случайном порядке,

22
00:01:11,150 --> 00:01:12,940
и цель заключается в
сортировать его, сверху донизу,

23
00:01:12,940 --> 00:01:16,310
слева направо, от одного
весь путь через 15.

24
00:01:16,310 --> 00:01:19,360
>> К сожалению, реализация
вы будете иметь под рукой

25
00:01:19,360 --> 00:01:21,590
будет обеспечение
на основе, не физически.

26
00:01:21,590 --> 00:01:25,280
Вы на самом деле придется написать
Код, с которой студент или пользователь может,

27
00:01:25,280 --> 00:01:26,760
играть в игру 15.

28
00:01:26,760 --> 00:01:29,030
И в самом деле, в хакера
издание игры 15,

29
00:01:29,030 --> 00:01:32,155
Вы будете вызов для реализации,
не только игра в этой старой школы

30
00:01:32,155 --> 00:01:35,010
игра, но, скорее, решение
это, реализации режима бога,

31
00:01:35,010 --> 00:01:38,280
так сказать, что на самом деле
решает головоломки для человека,

32
00:01:38,280 --> 00:01:41,080
путем предоставления им намек,
после намека, после намека.

33
00:01:41,080 --> 00:01:42,280
Так больше на этом на следующей неделе.

34
00:01:42,280 --> 00:01:43,720
Но это то, что лежит впереди.

35
00:01:43,720 --> 00:01:47,610
>> Сейчас вспоминаю, что ранее на этой неделе
у нас была эта Скалолаз, если хотите,

36
00:01:47,610 --> 00:01:52,560
в результате чего лучше мы делали сортировки
мудрый был верхний предел Big O п

37
00:01:52,560 --> 00:01:53,210
в квадрате.

38
00:01:53,210 --> 00:01:56,520
Другими словами, пузырьковой сортировки,
Выбор рода, сортировка вставками,

39
00:01:56,520 --> 00:01:59,120
все из них, в то время как другая
в их реализации,

40
00:01:59,120 --> 00:02:03,480
переданы в п квадрате работает
время в самом худшем случае.

41
00:02:03,480 --> 00:02:06,010
И мы, как правило предположить, что
очень худшем случае для сортировки

42
00:02:06,010 --> 00:02:08,814
это то, что ваша входы
полностью в обратном направлении.

43
00:02:08,814 --> 00:02:11,980
И в самом деле, он взял довольно много шагов
для осуществления каждого из этих алгоритмов.

44
00:02:11,980 --> 00:02:15,110
>> Теперь в самом конце класса
Напомним, мы сравнили пузырьковой сортировки

45
00:02:15,110 --> 00:02:19,390
против выбора рода в отношении одного другой
что мы назвали сортировки слиянием в то время,

46
00:02:19,390 --> 00:02:22,120
и я предлагаю, чтобы он принимает
Преимущество урока от недели

47
00:02:22,120 --> 00:02:24,060
нулю, разделяй и властвуй.

48
00:02:24,060 --> 00:02:28,810
И как-то достижения какой-то
логарифмическая время работы, в конечном счете,

49
00:02:28,810 --> 00:02:31,024
вместо чего-то
это чисто квадратичной.

50
00:02:31,024 --> 00:02:33,440
И это не совсем логарифмическая,
это немного больше, чем это.

51
00:02:33,440 --> 00:02:36,520
Но если вы помните из класса,
это было гораздо, гораздо быстрее.

52
00:02:36,520 --> 00:02:38,210
Давайте взглянем на то, где мы остановились.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Пузырь рода против выбора
Сортировать по сравнению с сортировки слиянием.

55
00:02:45,370 --> 00:02:47,700
Теперь они все работает, в
Теория, в то же время.

56
00:02:47,700 --> 00:02:50,510
Процессор работает с такой же скоростью.

57
00:02:50,510 --> 00:02:54,990
Но вы можете чувствовать себя как скучно это
очень быстро станет,

58
00:02:54,990 --> 00:02:58,790
и только, как быстро, когда мы вводим
немного алгоритмов за неделю Зеро,

59
00:02:58,790 --> 00:03:00,080
мы можем ускорить.

60
00:03:00,080 --> 00:03:01,630
>> Так знак рода выглядит потрясающе.

61
00:03:01,630 --> 00:03:05,220
Как мы можем использовать его для того,
сортировать число быстрее.

62
00:03:05,220 --> 00:03:07,140
Ну давайте вспомним
к ингредиента, что

63
00:03:07,140 --> 00:03:10,380
был вернуться к нулевой неделе, что из
ища кого-то в телефонной книге,

64
00:03:10,380 --> 00:03:12,380
и вспомнить, что
псевдокод, что мы предложили,

65
00:03:12,380 --> 00:03:14,560
с помощью которых мы можем найти
кто, как Майк Смит,

66
00:03:14,560 --> 00:03:16,310
выглядел немного что-то вроде этого.

67
00:03:16,310 --> 00:03:20,820
>> Теперь взгляните в частности
в строке 7 и 8, и 10 и 11,

68
00:03:20,820 --> 00:03:25,240
которые индуцируют что цикл, в котором мы сохранили
возвращаясь к строке 3 снова, и снова,

69
00:03:25,240 --> 00:03:26,520
и опять.

70
00:03:26,520 --> 00:03:31,790
Но оказывается, что мы можем смотреть
этот алгоритм, здесь, в псевдокоде,

71
00:03:31,790 --> 00:03:33,620
немного более целостно.

72
00:03:33,620 --> 00:03:35,960
В самом деле, что я ищу
на здесь на экране,

73
00:03:35,960 --> 00:03:41,180
алгоритм для поиска
Майк Смит среди некоторого множества страниц.

74
00:03:41,180 --> 00:03:45,520
И в самом деле, мы могли бы упростить это
Алгоритм в этих строках 7 и 8,

75
00:03:45,520 --> 00:03:49,860
и 10, и 11, чтобы просто сказать, что это,
которые я представил здесь в желтый цвет.

76
00:03:49,860 --> 00:03:52,210
Другими словами, если Mike
Смит ранее в книге,

77
00:03:52,210 --> 00:03:55,004
мы не должны указать шаг
за шагом теперь, как пойти и найти его.

78
00:03:55,004 --> 00:03:56,920
Мы не должны указать
вернуться к строке 3,

79
00:03:56,920 --> 00:03:58,960
почему бы нам просто не вместо,
скажем, в более общем смысле,

80
00:03:58,960 --> 00:04:01,500
искать Майка в
левая половина книги.

81
00:04:01,500 --> 00:04:03,960
>> И наоборот, если Майк
на самом деле в книге позже,

82
00:04:03,960 --> 00:04:07,540
почему бы нам просто не процитировать Unquote поиска
Майка в правой половине книги.

83
00:04:07,540 --> 00:04:11,030
Другими словами, почему бы нам просто не
вроде плоскодонки на себя говорю,

84
00:04:11,030 --> 00:04:13,130
искать Майка в этом
подмножество книги,

85
00:04:13,130 --> 00:04:16,279
и оставить его для наших существующих
Алгоритм, чтобы сообщить нам

86
00:04:16,279 --> 00:04:18,750
как искать Майка в
что левая половина книги.

87
00:04:18,750 --> 00:04:20,750
Другими словами, наш
Алгоритм работы будь то

88
00:04:20,750 --> 00:04:24,670
телефонная книга этой толщины, это
Толщина или любой толщины вообще.

89
00:04:24,670 --> 00:04:27,826
Таким образом, мы можем рекурсивно
определить этот алгоритм.

90
00:04:27,826 --> 00:04:29,950
Другими словами, на
Экран здесь, является алгоритм

91
00:04:29,950 --> 00:04:33,130
для поиска Майк Смит
среди страниц телефонной книги.

92
00:04:33,130 --> 00:04:37,410
Таким образом, в линии 7 и 10, давайте
просто сказать, что именно.

93
00:04:37,410 --> 00:04:40,250
И я использую этот термин мгновение
назад, и, действительно, рекурсия

94
00:04:40,250 --> 00:04:42,450
это модное слово сейчас,
и это этот процесс

95
00:04:42,450 --> 00:04:47,210
делать что-то, каким-то циклический
с помощью кода, у вас уже есть,

96
00:04:47,210 --> 00:04:49,722
и призывая его снова,
и снова, и снова.

97
00:04:49,722 --> 00:04:51,930
Теперь это будет важно
что мы как-то снизу

98
00:04:51,930 --> 00:04:53,821
из, и не делать, что бесконечно долго.

99
00:04:53,821 --> 00:04:56,070
В противном случае мы будем
есть действительно бесконечный цикл.

100
00:04:56,070 --> 00:04:59,810
Но давайте посмотрим, если мы можем заимствовать эту идею
из рекурсии, делать что-то снова

101
00:04:59,810 --> 00:05:03,600
и снова, и снова, чтобы решить
сортировка проблема с помощью слияния

102
00:05:03,600 --> 00:05:05,900
рода, тем более эффективно.

103
00:05:05,900 --> 00:05:06,970
>> Так я даю вам объединить рода.

104
00:05:06,970 --> 00:05:07,920
Давайте взглянем.

105
00:05:07,920 --> 00:05:10,850
Так вот псевдокод, с
которые мы могли бы реализовать сортировку,

106
00:05:10,850 --> 00:05:12,640
с помощью этого алгоритма под названием сортировка слиянием.

107
00:05:12,640 --> 00:05:13,880
И это довольно просто это.

108
00:05:13,880 --> 00:05:15,940
На входе п элементов,
Другими словами, если вы

109
00:05:15,940 --> 00:05:18,830
учитывая п элементов и числа и
письма или что-то, то вход,

110
00:05:18,830 --> 00:05:22,430
если вы дали п элементов, если
п меньше, чем 2, только возвращаться.

111
00:05:22,430 --> 00:05:22,930
Правильно?

112
00:05:22,930 --> 00:05:26,430
Потому что, если п меньше, чем 2, что
означает, что мой список элементов

113
00:05:26,430 --> 00:05:30,446
либо размера 0 или 1, и
В обоих этих более сложных случаях

114
00:05:30,446 --> 00:05:31,570
список уже отсортирован.

115
00:05:31,570 --> 00:05:32,810
Если нет никакого списка, это сортируется.

116
00:05:32,810 --> 00:05:35,185
А если есть список длины
1, то, очевидно, сортируются.

117
00:05:35,185 --> 00:05:38,280
Таким образом, алгоритм должен только
действительно что-то интересное,

118
00:05:38,280 --> 00:05:40,870
если у нас есть два или более
элементы дано нам.

119
00:05:40,870 --> 00:05:42,440
Итак, давайте посмотрим на то магии.

120
00:05:42,440 --> 00:05:47,500
Остальное отсортировать левую половину элементов,
Затем сортировать правую половину элементов,

121
00:05:47,500 --> 00:05:49,640
Затем слить, отсортированные половинки.

122
00:05:49,640 --> 00:05:52,440
И то, что вроде умопомрачительным
здесь является то, что я на самом деле не

123
00:05:52,440 --> 00:05:56,190
кажется, уже говорил вам
ничего просто еще, верно?

124
00:05:56,190 --> 00:05:59,560
Все, что я сказал, это, учитывая список
п элементов, сортировать левую половину,

125
00:05:59,560 --> 00:06:01,800
то правая половина, то
объединить упорядоченные половинки,

126
00:06:01,800 --> 00:06:03,840
но где фактическое секрет соуса?

127
00:06:03,840 --> 00:06:05,260
Где алгоритм?

128
00:06:05,260 --> 00:06:09,150
Ну получается, что этих двух линий
Сначала вроде левая половина элементов,

129
00:06:09,150 --> 00:06:13,970
и вроде правая половина элементов,
рекурсивные вызовы, так сказать.

130
00:06:13,970 --> 00:06:16,120
>> В конце концов, в этом
момент времени, у меня есть

131
00:06:16,120 --> 00:06:18,950
алгоритм с которым
сортировать целую кучу элементов?

132
00:06:18,950 --> 00:06:19,450
Да.

133
00:06:19,450 --> 00:06:20,620
Это прямо здесь.

134
00:06:20,620 --> 00:06:25,180
Это прямо здесь, на экране, и
так что я могу использовать тот же набор шагов

135
00:06:25,180 --> 00:06:28,500
сортировать левую половину,
как я могу правая половина.

136
00:06:28,500 --> 00:06:30,420
И в самом деле, снова, и снова.

137
00:06:30,420 --> 00:06:34,210
Так или иначе, а мы скоро
убедиться в этом, магию сортировки слиянием

138
00:06:34,210 --> 00:06:37,967
встроен в том, что очень финале
линия, слияния отсортированных половинки.

139
00:06:37,967 --> 00:06:39,300
И это, кажется довольно интуитивно.

140
00:06:39,300 --> 00:06:41,050
Вы берете две половинки, и вам,
так или иначе, объединить их вместе,

141
00:06:41,050 --> 00:06:43,260
и мы увидим, это
конкретно в данный момент.

142
00:06:43,260 --> 00:06:45,080
>> Но это полная алгоритм.

143
00:06:45,080 --> 00:06:46,640
И давайте посмотрим, почему.

144
00:06:46,640 --> 00:06:50,912
Ну предположим, что нам дают эти же
восемь элементов здесь на экране, один

145
00:06:50,912 --> 00:06:53,120
через восемь, но они
в, казалось бы, случайном порядке.

146
00:06:53,120 --> 00:06:55,320
И цель под рукой
сортировать эти элементы.

147
00:06:55,320 --> 00:06:58,280
Ну, как я могу идти о
делать это с помощью, опять же,

148
00:06:58,280 --> 00:07:00,407
сортировка слиянием, в соответствии с настоящим псевдокоде?

149
00:07:00,407 --> 00:07:02,740
И опять, вселить это в
Ваш ум, на мгновение.

150
00:07:02,740 --> 00:07:05,270
Первый случай является довольно
тривиально, если это меньше, чем 2,

151
00:07:05,270 --> 00:07:07,060
просто вернуть, нет ни работы, чтобы сделать.

152
00:07:07,060 --> 00:07:09,290
Так на самом деле есть только три
шаги, чтобы действительно держать в уме.

153
00:07:09,290 --> 00:07:11,081
Опять и опять, я
захочет иметь

154
00:07:11,081 --> 00:07:13,980
сортировать левую половину,
сортировать правую половину,

155
00:07:13,980 --> 00:07:15,890
а затем, как только их
две половинки сортируются,

156
00:07:15,890 --> 00:07:18,710
Я хочу, чтобы объединить их вместе
в один отсортированный список.

157
00:07:18,710 --> 00:07:19,940
Так что имейте это в виду.

158
00:07:19,940 --> 00:07:21,310
>> Так вот первоначальный список.

159
00:07:21,310 --> 00:07:23,510
Давайте относиться к этому как
Массив, как мы начали

160
00:07:23,510 --> 00:07:25,800
в неделю два, который является
непрерывный блок памяти.

161
00:07:25,800 --> 00:07:28,480
В этом случае, содержащий восемь
номера, спина к спине к спине.

162
00:07:28,480 --> 00:07:30,700
И пусть теперь применим сортировки слиянием.

163
00:07:30,700 --> 00:07:33,300
Так что я сначала хочу, чтобы отсортировать
левая половина этого списка,

164
00:07:33,300 --> 00:07:37,370
И давайте, следовательно,
сосредоточиться на 4, 8, 6, и 2.

165
00:07:37,370 --> 00:07:41,000
>> Теперь, как я могу идти о
сортировка списка размера 4?

166
00:07:41,000 --> 00:07:45,990
Ну у меня есть, чтобы рассмотреть в настоящее время
сортировка слева от левой половины.

167
00:07:45,990 --> 00:07:47,720
Опять же, давайте назад на мгновение.

168
00:07:47,720 --> 00:07:51,010
Если псевдокод это,
и я дал восемь элементов,

169
00:07:51,010 --> 00:07:53,230
8, очевидно, больше
чем или равно 2.

170
00:07:53,230 --> 00:07:54,980
Так что с первым случаем не применяется.

171
00:07:54,980 --> 00:07:58,120
Таким образом, чтобы разобраться восемь элементов, я впервые
сортировать левую половину элементов,

172
00:07:58,120 --> 00:08:01,930
затем сортировать правую половину, то я объединить
два отсортированных половинки, каждая из размеров 4.

173
00:08:01,930 --> 00:08:02,470
ХОРОШО.

174
00:08:02,470 --> 00:08:07,480
>> Но если вы только что сказали мне, сортировать
левая половина, которая в настоящее время размер 4,

175
00:08:07,480 --> 00:08:09,350
Как отсортировать левую половину?

176
00:08:09,350 --> 00:08:11,430
Ну, если у меня есть
вход из четырех элементов,

177
00:08:11,430 --> 00:08:14,590
Я впервые отсортировать левую
два, то право два,

178
00:08:14,590 --> 00:08:16,210
а потом я их объединить вместе.

179
00:08:16,210 --> 00:08:18,700
Итак, еще раз, это становится немного
из умопомрачительным игра здесь,

180
00:08:18,700 --> 00:08:21,450
потому что вы, вроде, должны
помните, где вы находитесь в этой истории,

181
00:08:21,450 --> 00:08:23,620
но в конце концов,
учитывая любое число элементов,

182
00:08:23,620 --> 00:08:25,620
Вы сначала хочу отсортировать
левая половина, то правая половина,

183
00:08:25,620 --> 00:08:26,661
а затем объединить их вместе.

184
00:08:26,661 --> 00:08:28,630
Давайте начнем делать именно это.

185
00:08:28,630 --> 00:08:30,170
Вот вход из восьми элементов.

186
00:08:30,170 --> 00:08:31,910
Теперь мы смотрим на левой половине здесь.

187
00:08:31,910 --> 00:08:33,720
Как сортировать четырех элементов?

188
00:08:33,720 --> 00:08:35,610
Ну я сначала отсортировать левую половину.

189
00:08:35,610 --> 00:08:37,720
Теперь, как мне отсортировать левую половину?

190
00:08:37,720 --> 00:08:39,419
Ну мне дали два элемента.

191
00:08:39,419 --> 00:08:41,240
Итак, давайте разберемся этих двух элементов.

192
00:08:41,240 --> 00:08:44,540
2 больше или
равно 2, конечно.

193
00:08:44,540 --> 00:08:46,170
Так что первый случай не распространяется.

194
00:08:46,170 --> 00:08:49,010
>> Так что я теперь должен разобраться левую
половина из этих двух элементов.

195
00:08:49,010 --> 00:08:50,870
Левая половина, конечно, находится всего в 4.

196
00:08:50,870 --> 00:08:54,020
Так как мне отсортировать список одного элемента?

197
00:08:54,020 --> 00:08:57,960
Ну, что специальная база случай
наверху, так сказать, относится.

198
00:08:57,960 --> 00:09:01,470
1 меньше, чем 2, и моя
Список действительно размера 1.

199
00:09:01,470 --> 00:09:02,747
Так что я просто вернуться.

200
00:09:02,747 --> 00:09:03,580
Я ничего не делать.

201
00:09:03,580 --> 00:09:06,770
И в самом деле, посмотрите на то, что я
сделано, 4 уже отсортированы.

202
00:09:06,770 --> 00:09:09,220
Как Я уже
частично успешными здесь.

203
00:09:09,220 --> 00:09:11,750
>> Теперь, кажется, своего рода глупо
требовать, но это правда.

204
00:09:11,750 --> 00:09:13,700
4 приведен список размера 1.

205
00:09:13,700 --> 00:09:15,090
Это уже отсортированы.

206
00:09:15,090 --> 00:09:16,270
Это левая половина.

207
00:09:16,270 --> 00:09:18,010
Теперь я сортировать правую половину.

208
00:09:18,010 --> 00:09:22,310
Мой вход один элемент, 8
Точно так же, уже отсортированы.

209
00:09:22,310 --> 00:09:25,170
Глупо, слишком, но опять же,
это основной принцип

210
00:09:25,170 --> 00:09:28,310
собирается, чтобы позволить нам в настоящее время строить
на вершине этого успешно.

211
00:09:28,310 --> 00:09:32,260
4 сортируются, 8 сортируется, теперь
то, что было, что последний шаг?

212
00:09:32,260 --> 00:09:35,330
Таким образом, третий и последний шаг, любое
раз вы сортировки списка, напомним,

213
00:09:35,330 --> 00:09:38,310
было объединить две половинки,
левая и правая.

214
00:09:38,310 --> 00:09:39,900
Так что давайте делать именно это.

215
00:09:39,900 --> 00:09:41,940
Моя левая половина, конечно, 4.

216
00:09:41,940 --> 00:09:43,310
Моя правая половина 8.

217
00:09:43,310 --> 00:09:44,100
>> Так давайте сделаем это.

218
00:09:44,100 --> 00:09:46,410
Сначала я собираюсь выделить
некоторые дополнительные памяти,

219
00:09:46,410 --> 00:09:48,680
что я буду представлять здесь,
как просто вторичным массива,

220
00:09:48,680 --> 00:09:49,660
что это достаточно большой, чтобы соответствовать этим.

221
00:09:49,660 --> 00:09:52,243
Но вы можете себе представить, расширяя
что прямоугольник вся длина,

222
00:09:52,243 --> 00:09:53,290
если нам нужно больше позже.

223
00:09:53,290 --> 00:09:58,440
Как я беру 4 и 8, и объединить
эти два списка размере 1 вместе?

224
00:09:58,440 --> 00:10:00,270
Здесь тоже довольно просто.

225
00:10:00,270 --> 00:10:03,300
4 приходит первым, а затем приходит 8.

226
00:10:03,300 --> 00:10:07,130
Потому что, если я хочу, чтобы отсортировать
левая половина, то правая половина,

227
00:10:07,130 --> 00:10:09,900
а затем объединить эти две половинки
вместе, в отсортированном порядке,

228
00:10:09,900 --> 00:10:11,940
4 приходит первым, а затем приходит 8.

229
00:10:11,940 --> 00:10:15,810
>> Таким образом, мы, кажется, делает успехи, даже
хотя я не сделал никакого фактическую работу.

230
00:10:15,810 --> 00:10:17,800
Но помните, где мы находимся в истории.

231
00:10:17,800 --> 00:10:19,360
Мы изначально приняли восемь элементов.

232
00:10:19,360 --> 00:10:21,480
Мы отсортировали левую половину, которая 4.

233
00:10:21,480 --> 00:10:24,450
Тогда мы отсортировали левую половину
в левой половине, которая была 2.

234
00:10:24,450 --> 00:10:25,270
И здесь мы идем.

235
00:10:25,270 --> 00:10:26,920
Мы сделали с этим шагом.

236
00:10:26,920 --> 00:10:29,930
>> Так что, если мы сортируются
левая половина 2, теперь мы

237
00:10:29,930 --> 00:10:32,130
есть для сортировки правую половину 2.

238
00:10:32,130 --> 00:10:35,710
Таким образом, правая половина 2
эти два значения здесь, 6 и 2.

239
00:10:35,710 --> 00:10:40,620
Так теперь давайте вход размера
2, и сортировать левую половину, а затем

240
00:10:40,620 --> 00:10:42,610
правая половина, а затем
объединить их вместе.

241
00:10:42,610 --> 00:10:45,722
Ну, как мне отсортировать список размеров
1, содержащий только номер 6?

242
00:10:45,722 --> 00:10:46,430
Я уже сделал.

243
00:10:46,430 --> 00:10:48,680
Это список размере 1 сортируется.

244
00:10:48,680 --> 00:10:52,140
>> Как мне отсортировать список еще
размер 1, так называемая правая половина.

245
00:10:52,140 --> 00:10:54,690
Ну, тоже уже отсортированы.

246
00:10:54,690 --> 00:10:56,190
2 номер один.

247
00:10:56,190 --> 00:11:00,160
Так что теперь у меня есть две половинки, слева и
Право, мне нужно, чтобы объединить их вместе.

248
00:11:00,160 --> 00:11:01,800
Позвольте мне дать себе некоторое дополнительное пространство.

249
00:11:01,800 --> 00:11:05,580
И положил 2 там,
затем 6 в там, таким образом,

250
00:11:05,580 --> 00:11:10,740
сортировка этот список, слева и справа,
и слияние их вместе, в конечном счете,.

251
00:11:10,740 --> 00:11:12,160
Так что я нахожусь в немного лучшей форме.

252
00:11:12,160 --> 00:11:16,250
Я не сделал, потому что ясно 4, 8, 2,
6 не является окончательным заказа, что я хочу.

253
00:11:16,250 --> 00:11:20,640
Но теперь у меня есть два списка размер 2, что
оба, соответственно, были отсортированы.

254
00:11:20,640 --> 00:11:24,580
Так что теперь, если вы назад в вашем воображении
глаз, откуда, что нам дает?

255
00:11:24,580 --> 00:11:28,520
Я начал с восьми элементов, то я
свел его к левой половине 4,

256
00:11:28,520 --> 00:11:31,386
Затем левая половина 2 и
Затем правая половина 2,

257
00:11:31,386 --> 00:11:34,510
Я закончил, поэтому, сортировка левую
половина 2, а правая половина 2,

258
00:11:34,510 --> 00:11:37,800
так что третий и последний шаг здесь?

259
00:11:37,800 --> 00:11:41,290
Я должен объединить вместе
два списка размера 2.

260
00:11:41,290 --> 00:11:42,040
Так что давайте идти вперед.

261
00:11:42,040 --> 00:11:43,940
И на экране тут, дать
мне некоторые дополнительные памяти,

262
00:11:43,940 --> 00:11:47,170
хотя технически, заметили, что я имею
получил целую кучу пробелом наверху

263
00:11:47,170 --> 00:11:47,670
Там.

264
00:11:47,670 --> 00:11:50,044
Если я хочу, чтобы быть особенно
офисные помещения мудрый,

265
00:11:50,044 --> 00:11:52,960
Я мог бы просто начать двигаться элементы
назад и вперед, сверху и снизу.

266
00:11:52,960 --> 00:11:55,460
Но только для наглядности,
Я собираюсь поставить его вниз,

267
00:11:55,460 --> 00:11:56,800
чтобы держать вещи красивым и чистым.

268
00:11:56,800 --> 00:11:58,150
>> Так что я получил два списка размера 2.

269
00:11:58,150 --> 00:11:59,770
Первый список содержит 4 и 8.

270
00:11:59,770 --> 00:12:01,500
Второй список имеет 2 и 6.

271
00:12:01,500 --> 00:12:03,950
Давайте объединять тех,
вместе в определенном порядке.

272
00:12:03,950 --> 00:12:09,910
2, конечно, на первом месте,
затем 4, затем 6, затем 8.

273
00:12:09,910 --> 00:12:12,560
И теперь мы, кажется, становятся
где интересно.

274
00:12:12,560 --> 00:12:15,720
Теперь я сортируются половина
список, и по совпадению, это

275
00:12:15,720 --> 00:12:18,650
все четные числа, а что
это, действительно, просто совпадение.

276
00:12:18,650 --> 00:12:22,220
И я теперь сортируются влево
половина, так что это 2, 4, 6 и 8.

277
00:12:22,220 --> 00:12:23,430
Ничего не в порядке.

278
00:12:23,430 --> 00:12:24,620
Это чувствует, как прогресс.

279
00:12:24,620 --> 00:12:26,650
>> Теперь он чувствует себя, как я
говорили навеки,

280
00:12:26,650 --> 00:12:29,850
так, что еще предстоит увидеть, если это
Алгоритм, по сути, более эффективным.

281
00:12:29,850 --> 00:12:31,766
Но мы собираемся через
это супер методично.

282
00:12:31,766 --> 00:12:34,060
Компьютер, конечно,
будет делать это так.

283
00:12:34,060 --> 00:12:34,840
Так где же мы?

284
00:12:34,840 --> 00:12:36,180
Мы начали с восьми элементов.

285
00:12:36,180 --> 00:12:37,840
Я сортируются левую половину 4.

286
00:12:37,840 --> 00:12:39,290
Я, кажется, с этим покончено.

287
00:12:39,290 --> 00:12:42,535
Так что теперь следующий шаг заключается в
сортировать правую половину 4.

288
00:12:42,535 --> 00:12:44,410
И эта часть мы можем пойти
через немного больше

289
00:12:44,410 --> 00:12:47,140
быстро, хотя вы
Добро пожаловать, чтобы перемотать или приостановить, просто

290
00:12:47,140 --> 00:12:49,910
думаю, через него
Ваш собственный темп, но то, что

291
00:12:49,910 --> 00:12:53,290
мы имеем сейчас возможность
сделать то же алгоритм на четыре

292
00:12:53,290 --> 00:12:54,380
разные номера.

293
00:12:54,380 --> 00:12:57,740
>> Так что давайте идти вперед, а сосредоточиться на
правая половина, которую мы здесь.

294
00:12:57,740 --> 00:13:01,260
Левая половина того, что
Правая половина, и в настоящее время

295
00:13:01,260 --> 00:13:04,560
левая половина слева
половина этого правой половине,

296
00:13:04,560 --> 00:13:08,030
и как мне отсортировать список размеров
1, содержащий только номер 1?

297
00:13:08,030 --> 00:13:09,030
Уже сделано.

298
00:13:09,030 --> 00:13:11,830
Как сделать то же самое для списка
размер 1, содержащей всего 7?

299
00:13:11,830 --> 00:13:12,840
Уже сделано.

300
00:13:12,840 --> 00:13:16,790
Шаг три для половины, то
является объединить эти два элемента

301
00:13:16,790 --> 00:13:20,889
в новый список размеров 2, 1 и 7.

302
00:13:20,889 --> 00:13:23,180
Есть, кажется, не сделали все
что многое интересная работа.

303
00:13:23,180 --> 00:13:24,346
Давайте посмотрим, что произойдет дальше.

304
00:13:24,346 --> 00:13:29,210
Я просто сортируются левую половину из
Правая половина моей первоначальной вход.

305
00:13:29,210 --> 00:13:32,360
Теперь давайте разберёмся право
половина, которая содержит 5 и 3.

306
00:13:32,360 --> 00:13:35,740
Давайте раз взглянуть на левой
половина, сортируется, правая половина, сортировать,

307
00:13:35,740 --> 00:13:39,120
и объединить эти два вместе,
в какой-то дополнительное пространство,

308
00:13:39,120 --> 00:13:41,670
3 приходит первым, а затем приходит 5.

309
00:13:41,670 --> 00:13:46,190
И вот теперь, мы отсортированы
левая половина правой половине

310
00:13:46,190 --> 00:13:49,420
исходной задачи и
правая половина правой половине

311
00:13:49,420 --> 00:13:50,800
исходной задачи.

312
00:13:50,800 --> 00:13:52,480
Что третий и последний шаг?

313
00:13:52,480 --> 00:13:54,854
Ну, чтобы объединить эти две половинки вместе.

314
00:13:54,854 --> 00:13:57,020
Итак, позвольте мне получить себе некоторые
дополнительное пространство, но, опять же, я

315
00:13:57,020 --> 00:13:58,699
может быть с помощью этого свободное пространство наверху.

316
00:13:58,699 --> 00:14:00,490
Но мы собираемся, чтобы держать
это просто визуально.

317
00:14:00,490 --> 00:14:07,070
Позвольте мне теперь сливаются в 1, и
Затем 3, а затем 5, затем 7.

318
00:14:07,070 --> 00:14:10,740
Таким образом, оставив меня теперь с
Правая половина исходной задачи

319
00:14:10,740 --> 00:14:12,840
Это совершенно отсортированы.

320
00:14:12,840 --> 00:14:13,662
>> Так что же остается?

321
00:14:13,662 --> 00:14:16,120
Я чувствую, что я держу заявив
те же самые вещи снова и снова,

322
00:14:16,120 --> 00:14:18,700
но это отражать
То, что мы используем рекурсию.

323
00:14:18,700 --> 00:14:21,050
Процесс используя
Алгоритм снова, и снова,

324
00:14:21,050 --> 00:14:23,940
на небольших подмножеств
исходная задача.

325
00:14:23,940 --> 00:14:27,580
Так что я теперь левая сортируются
половина исходной задачи.

326
00:14:27,580 --> 00:14:30,847
У меня есть право отсортированный половину
исходной задачи.

327
00:14:30,847 --> 00:14:32,180
Что третий и последний шаг?

328
00:14:32,180 --> 00:14:33,590
О, это слияние.

329
00:14:33,590 --> 00:14:34,480
Так давайте сделаем это.

330
00:14:34,480 --> 00:14:36,420
Выделим некоторые дополнительные
памяти, но мой бог, мы

331
00:14:36,420 --> 00:14:37,503
может поставить его в любом месте в настоящее время.

332
00:14:37,503 --> 00:14:40,356
У нас есть так много свободного места
для нас, но мы будем держать это простым.

333
00:14:40,356 --> 00:14:42,730
Вместо того, чтобы идти вперед и
вперед с нашей первоначальной памяти,

334
00:14:42,730 --> 00:14:44,480
давайте просто делать это
визуально сюда ниже,

335
00:14:44,480 --> 00:14:47,240
чтобы закончить слияние
левая половина и правая половина.

336
00:14:47,240 --> 00:14:49,279
>> Так путем слияния, то, что мне нужно делать?

337
00:14:49,279 --> 00:14:50,820
Я хочу, чтобы взять элементы в порядке.

338
00:14:50,820 --> 00:14:53,230
Так, глядя на левой половине,
Я вижу, что первое число 2.

339
00:14:53,230 --> 00:14:55,230
Я смотрю на правой половине,
Я вижу первый номер

340
00:14:55,230 --> 00:14:58,290
1, так что, очевидно, которая
Количество я хочу вырвать,

341
00:14:58,290 --> 00:15:00,430
и поставить первым в моей окончательный список?

342
00:15:00,430 --> 00:15:01,449
Конечно, 1.

343
00:15:01,449 --> 00:15:02,990
Теперь я хочу спросить, что же вопрос.

344
00:15:02,990 --> 00:15:05,040
На левой половине, у меня
еще есть номер 2.

345
00:15:05,040 --> 00:15:07,490
На правой половине,
Я получил номер 3.

346
00:15:07,490 --> 00:15:08,930
Какой я хочу, чтобы выбрать?

347
00:15:08,930 --> 00:15:11,760
Конечно, число 2 и
Теперь обратите внимание на кандидатов

348
00:15:11,760 --> 00:15:13,620
являются 4 слева, 3 справа.

349
00:15:13,620 --> 00:15:15,020
Давайте, конечно, выбрать 3.

350
00:15:15,020 --> 00:15:18,020
Теперь кандидаты на 4
левая, 5 справа.

351
00:15:18,020 --> 00:15:19,460
Мы, конечно, выбрать 4.

352
00:15:19,460 --> 00:15:21,240
6 слева, 5 справа.

353
00:15:21,240 --> 00:15:22,730
Мы, конечно, выбрать 5.

354
00:15:22,730 --> 00:15:25,020
6 слева, 7 справа.

355
00:15:25,020 --> 00:15:29,320
Мы выбираем 6, а затем мы
выбрать 7, а затем мы выбираем 8.

356
00:15:29,320 --> 00:15:30,100
Вуаля.

357
00:15:30,100 --> 00:15:34,370
>> Таким образом, огромное количество слов позже, мы
отсортировали это список из восьми элементов

358
00:15:34,370 --> 00:15:38,450
в список одного до восьми,
который растет с каждым шагом,

359
00:15:38,450 --> 00:15:40,850
но сколько раз сделал
это взять нас, чтобы сделать это.

360
00:15:40,850 --> 00:15:43,190
Ну, я намеренно
возложили вещи из графически

361
00:15:43,190 --> 00:15:46,330
здесь, так что мы можем вид
см или оценить разделение

362
00:15:46,330 --> 00:15:49,060
в завоевании, который был происходит.

363
00:15:49,060 --> 00:15:52,830
>> Действительно, если вы посмотрите на поминках,
Я оставил все эти пунктирными линиями

364
00:15:52,830 --> 00:15:55,660
в место держателей, вы можете,
вид, видите, в обратном порядке,

365
00:15:55,660 --> 00:15:58,800
если вы вроде оглянуться в
История теперь, мой первоначальный список

366
00:15:58,800 --> 00:16:00,250
есть, конечно, от размера 8.

367
00:16:00,250 --> 00:16:03,480
А потом уже, я был
имеем дело с двумя списками размером 4,

368
00:16:03,480 --> 00:16:08,400
а затем четыре списки размер 2,
а затем восемь списков размера 1.

369
00:16:08,400 --> 00:16:10,151
>> Так что это делает,
вид, вам напоминает?

370
00:16:10,151 --> 00:16:11,858
Ну, в самом деле, любой из
алгоритмы мы

371
00:16:11,858 --> 00:16:14,430
посмотрел на до сих пор, где мы
разделяй и деления и деления,

372
00:16:14,430 --> 00:16:19,500
держать имея вещи снова, и
снова, приводит в этой общей идеи.

373
00:16:19,500 --> 00:16:23,100
И так есть что-то
логарифмическая здесь происходит.

374
00:16:23,100 --> 00:16:26,790
И это не совсем журнал п, но
есть логарифмическая компонент

375
00:16:26,790 --> 00:16:28,280
на то, что мы только что сделали.

376
00:16:28,280 --> 00:16:31,570
>> Теперь давайте рассмотрим, как это есть на самом деле.

377
00:16:31,570 --> 00:16:34,481
Так, авторизуйтесь п, снова
прекрасное время работает,

378
00:16:34,481 --> 00:16:36,980
когда мы сделали что-то вроде
бинарный поиск, как мы теперь называем,

379
00:16:36,980 --> 00:16:40,090
разделяй и властвуй стратегия
через который мы нашли Майка Смита.

380
00:16:40,090 --> 00:16:41,020
Теперь технически.

381
00:16:41,020 --> 00:16:43,640
Это журнал Основание 2 п, даже
хотя в большинстве математических классов,

382
00:16:43,640 --> 00:16:45,770
10, как правило, база, что вы взять на себя.

383
00:16:45,770 --> 00:16:48,940
Но ученые-компьютерщики почти всегда
думать и говорить в терминах базы 2,

384
00:16:48,940 --> 00:16:52,569
таким образом, мы вообще просто сказать, журнал
п, а журнала базы 2 п,

385
00:16:52,569 --> 00:16:55,110
но они точно одно и то
то же самое в мире компьютер

386
00:16:55,110 --> 00:16:57,234
наука, и, как в сторону,
есть постоянный фактор

387
00:16:57,234 --> 00:17:01,070
Разница между ними, так что
спорный во всяком случае, для более формальным причинам.

388
00:17:01,070 --> 00:17:04,520
>> Но сейчас, то, что мы заботимся
о это пример.

389
00:17:04,520 --> 00:17:08,520
Так что давайте не доказать, например, но в
мере использовать пример чисел

390
00:17:08,520 --> 00:17:10,730
под рукой для проверки отсутствия ошибок, если вы будете.

391
00:17:10,730 --> 00:17:14,510
Так, ранее формула была база журнала
2 п, но то, что п в этом случае.

392
00:17:14,510 --> 00:17:18,526
Я был п оригинальные номера, или 8
из исходного числа специально.

393
00:17:18,526 --> 00:17:20,359
Теперь это было немного
в то время как, но я уверен,

394
00:17:20,359 --> 00:17:25,300
Убедитесь, что журнал основание 2
от стоимости 8 3,

395
00:17:25,300 --> 00:17:29,630
и, действительно, то, что приятно об этом является
3, что именно количество раз

396
00:17:29,630 --> 00:17:33,320
что вы можете разделить список
длины 8 раз, и снова,

397
00:17:33,320 --> 00:17:36,160
и снова, пока вы оставили
со списками только размер 1.

398
00:17:36,160 --> 00:17:36,660
Правильно?

399
00:17:36,660 --> 00:17:40,790
8 идет на 4, идет до 2,
идет в 1, и это

400
00:17:40,790 --> 00:17:43,470
отражает именно это
картина у нас было всего лишь мгновение назад.

401
00:17:43,470 --> 00:17:47,160
Так немного здравомыслия проверить, куда
на самом деле участвует логарифм.

402
00:17:47,160 --> 00:17:50,180
>> Так что теперь, что еще тут дело? п.

403
00:17:50,180 --> 00:17:53,440
Так заметить, что каждый
раз я разделить список,

404
00:17:53,440 --> 00:17:58,260
хотя и в обратном порядке в истории
здесь, я все еще делаю п вещи.

405
00:17:58,260 --> 00:18:02,320
Это слияние шаг требуется,
Я прикасаюсь каждый из номеров,

406
00:18:02,320 --> 00:18:05,060
для того, чтобы скользить его в
его подходящим местом.

407
00:18:05,060 --> 00:18:10,760
Поэтому, даже если высота этого
диаграмма размера журнала п п или 3,

408
00:18:10,760 --> 00:18:13,860
В частности, другими словами,
Я сделал три дивизии здесь.

409
00:18:13,860 --> 00:18:18,800
Сколько работы я сделал по горизонтали
по этой схеме каждый раз?

410
00:18:18,800 --> 00:18:21,110
>> Ну, я сделал п шагов
работать, потому что, если я

411
00:18:21,110 --> 00:18:24,080
получил четыре элемента и четыре элемента,
и мне нужно, чтобы объединить их вместе.

412
00:18:24,080 --> 00:18:26,040
Мне нужно, чтобы пройти через
эти четыре, и они четыре,

413
00:18:26,040 --> 00:18:28,123
в конечном счете, объединить их
назад в восьми элементов.

414
00:18:28,123 --> 00:18:32,182
Если, наоборот, я получил восемь пальцев
здесь, что я не делаю, и восемь

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- если я
получил четыре пальца сюда,

416
00:18:34,390 --> 00:18:37,380
что я и делаю, четыре пальца
здесь, что я делаю,

417
00:18:37,380 --> 00:18:40,590
то, что то же самое,
Пример, как и прежде, если я

418
00:18:40,590 --> 00:18:44,010
восемь пальцев, хотя в
Всего которые я могу, вроде, сделать.

419
00:18:44,010 --> 00:18:47,950
Я могу точно сделать здесь,
то я, конечно

420
00:18:47,950 --> 00:18:50,370
объединить все эти списки
размер 1 вместе.

421
00:18:50,370 --> 00:18:54,050
Но я, конечно, придется искать
каждый элемент ровно один раз.

422
00:18:54,050 --> 00:18:59,640
Таким образом, высота этого процесса журнала N,
ширина этого процесса, так сказать,

423
00:18:59,640 --> 00:19:02,490
является н, так, что мы, кажется,
чтобы, в конечном счете, это

424
00:19:02,490 --> 00:19:06,470
бегущий время размер п раз войти н.

425
00:19:06,470 --> 00:19:08,977
>> Другими словами, мы разделили
список, журнал N раз,

426
00:19:08,977 --> 00:19:11,810
но каждый раз мы сделали это, мы были
коснуться каждого из элементов

427
00:19:11,810 --> 00:19:13,560
для того, чтобы объединить их
Все вместе, что

428
00:19:13,560 --> 00:19:18,120
шаг был п, так что мы должны п раз войти н,
или как ученый скажет,

429
00:19:18,120 --> 00:19:20,380
асимптотически, что
будет большое слово

430
00:19:20,380 --> 00:19:22,810
для описания верхний
связаны на времени работы,

431
00:19:22,810 --> 00:19:28,010
мы бежим в Big O
лог н время, так сказать.

432
00:19:28,010 --> 00:19:31,510
>> Теперь это важно, потому что
вспомнить, что бегущие времена были

433
00:19:31,510 --> 00:19:34,120
с пузырьковой сортировки, отбора и
сортировать и сортировка вставками,

434
00:19:34,120 --> 00:19:38,200
и даже некоторые другие, которые существуют,
п квадрате было, где мы были в.

435
00:19:38,200 --> 00:19:39,990
И вы можете, вид, увидеть это здесь.

436
00:19:39,990 --> 00:19:45,720
Если п квадрате, очевидно, п раз
п, но здесь мы имеем п раз войти н,

437
00:19:45,720 --> 00:19:48,770
и мы уже знаем, от недели
нулю, что журнал п, логарифмическая,

438
00:19:48,770 --> 00:19:50,550
лучше, чем что-то линейной.

439
00:19:50,550 --> 00:19:52,930
В конце концов, вспомнить картину
с красным и желтым

440
00:19:52,930 --> 00:19:56,500
и зеленые линии, которые мы нарисовали, тем
зеленый логарифмическая линия была значительно ниже.

441
00:19:56,500 --> 00:20:00,920
И, следовательно, гораздо лучше и быстрее,
чем прямой желтый и красных линий,

442
00:20:00,920 --> 00:20:05,900
п раз войти н, действительно, лучше
чем п раз п, или н квадрате.

443
00:20:05,900 --> 00:20:09,110
>> Таким образом, мы, кажется, есть
определили слияние алгоритм

444
00:20:09,110 --> 00:20:11,870
вроде тех, что работает в гораздо
минимальное время, и, действительно,

445
00:20:11,870 --> 00:20:16,560
Вот почему, в начале этой недели, когда
мы увидели, что конкурс между пузыря

446
00:20:16,560 --> 00:20:20,750
сортировать, выбор сортировки и слияния
сортировать, сортировка слиянием действительно, действительно выиграл.

447
00:20:20,750 --> 00:20:23,660
И в самом деле, мы даже не ждать
для пузырьковой сортировки и отбора рода

448
00:20:23,660 --> 00:20:24,790
заканчивать.

449
00:20:24,790 --> 00:20:27,410
>> Теперь давайте еще один проход
При этом из несколько более

450
00:20:27,410 --> 00:20:31,030
формальный перспективе, только в
случай, этот отклик лучше

451
00:20:31,030 --> 00:20:33,380
чем этого высшего уровня обсуждения.

452
00:20:33,380 --> 00:20:34,880
Так вот алгоритм снова.

453
00:20:34,880 --> 00:20:36,770
Давайте спросим себя,
то, что время работы

454
00:20:36,770 --> 00:20:39,287
является это алгоритмы различные шаги?

455
00:20:39,287 --> 00:20:41,620
Давайте разделим его на первое
Корпус и второй случай.

456
00:20:41,620 --> 00:20:46,280
ПЧ и еще в том случае, если,
Если N меньше, чем 2, только возвращаться.

457
00:20:46,280 --> 00:20:47,580
По ощущениям постоянной времени.

458
00:20:47,580 --> 00:20:50,970
Это, своего рода, как два этапа,
Если N меньше, чем 2, а затем вернуться.

459
00:20:50,970 --> 00:20:54,580
Но, как мы сказали, в понедельник,
постоянная времени, или Big O 1,

460
00:20:54,580 --> 00:20:57,130
может быть два, три шага
шаги, даже 1000 шагов.

461
00:20:57,130 --> 00:20:59,870
Важно то, что это
постоянное число шагов.

462
00:20:59,870 --> 00:21:03,240
Таким образом, желтый выделенный псевдокод
здесь работает в, мы будем называть его,

463
00:21:03,240 --> 00:21:04,490
постоянная времени.

464
00:21:04,490 --> 00:21:06,780
Так более формально, и
мы собираемся, целью которых это

465
00:21:06,780 --> 00:21:09,910
будет степень, в которой мы
оформить это право now-- Т п,

466
00:21:09,910 --> 00:21:15,030
время работы задачи
который принимает п нечто в качестве входных,

467
00:21:15,030 --> 00:21:19,150
равна Big O из одного,
Если N меньше, чем 2.

468
00:21:19,150 --> 00:21:20,640
Так что это обусловлено, что.

469
00:21:20,640 --> 00:21:24,150
Таким образом, чтобы быть ясным, если п меньше
2, у нас есть очень короткий список, то

470
00:21:24,150 --> 00:21:29,151
время работает, Т п, где п
1 или 0, в этом очень конкретном случае,

471
00:21:29,151 --> 00:21:30,650
это просто будет постоянная времени.

472
00:21:30,650 --> 00:21:32,691
Это займет один
шаг, два шага, что угодно.

473
00:21:32,691 --> 00:21:33,950
Это фиксированное число шагов.

474
00:21:33,950 --> 00:21:38,840
>> Таким образом, сочная часть должна быть в безусловно
другой случай в псевдокоде.

475
00:21:38,840 --> 00:21:40,220
Дело в другом месте.

476
00:21:40,220 --> 00:21:44,870
Сортировать левая половина элементов, отсортируйте право
половина элементов, слияния отсортированных половинки.

477
00:21:44,870 --> 00:21:46,800
Как долго каждый из этих шагов взять?

478
00:21:46,800 --> 00:21:49,780
Ну, если работает
Время сортировать п элементов

479
00:21:49,780 --> 00:21:53,010
, давайте называть его очень
в общем, Т п,

480
00:21:53,010 --> 00:21:55,500
затем сортировки левой
половина элементов

481
00:21:55,500 --> 00:21:59,720
это, вроде, как и говорили:
Т п делится на 2,

482
00:21:59,720 --> 00:22:03,000
и аналогично сортировке правую половину
из элементов, вроде, как и говорили:

483
00:22:03,000 --> 00:22:06,974
Т п делится 2, а затем
слияния отсортированных половинки.

484
00:22:06,974 --> 00:22:08,890
Ну, если я получил некоторые
Количество элементов здесь,

485
00:22:08,890 --> 00:22:11,230
как четыре, и некоторое количество
элементов здесь, как четыре,

486
00:22:11,230 --> 00:22:14,650
и я должен объединить каждого из этих четырех
В, и каждый из них четыре в, один

487
00:22:14,650 --> 00:22:17,160
за другим, так что
в конечном счете, у меня есть восемь элементов.

488
00:22:17,160 --> 00:22:20,230
Он чувствует, как это Big O из п шагов?

489
00:22:20,230 --> 00:22:23,500
Если я получил п пальцы и каждый из
им должен быть объединены в месте,

490
00:22:23,500 --> 00:22:25,270
это как еще п шагов.

491
00:22:25,270 --> 00:22:27,360
>> Так действительно formulaically,
мы можем выразить это,

492
00:22:27,360 --> 00:22:29,960
хотя немного пугающе сначала
взгляд, но это что-то

493
00:22:29,960 --> 00:22:31,600
что захватывает именно эту логику.

494
00:22:31,600 --> 00:22:35,710
Время работы, Т п, если п
больше или равно 2.

495
00:22:35,710 --> 00:22:42,500
В этом случае, в случае ELSE, Т п
делится на 2, плюс Т N делится на 2,

496
00:22:42,500 --> 00:22:45,320
плюс Big O п, некоторые
линейный ряд шагов,

497
00:22:45,320 --> 00:22:51,630
возможно ровно п, может быть, в 2 раза
п, но это примерно, порядок п.

498
00:22:51,630 --> 00:22:54,060
Так что, тоже, как мы можем
выразить это formulaically.

499
00:22:54,060 --> 00:22:56,809
Теперь вы не знали бы, это, если
вы записали его в своем уме,

500
00:22:56,809 --> 00:22:58,710
или посмотреть его в
назад учебника, что

501
00:22:58,710 --> 00:23:00,501
может иметь немного
шпаргалку в конце концов,

502
00:23:00,501 --> 00:23:03,940
но это, действительно, собирается
дать нам Big O н журнала п

503
00:23:03,940 --> 00:23:06,620
потому что рецидив
Вы видите здесь, на экране,

504
00:23:06,620 --> 00:23:09,550
если вы на самом деле это, с
бесконечное число примеров,

505
00:23:09,550 --> 00:23:13,000
или вы сделали это formulaically, вы бы
видеть, что это, потому что этой формуле

506
00:23:13,000 --> 00:23:17,100
само по себе является рекурсивным, с т
п над чем-то справа,

507
00:23:17,100 --> 00:23:21,680
и т п над слева, это может
фактически быть выражена, в итоге,

508
00:23:21,680 --> 00:23:24,339
как большой идут н журнала п.

509
00:23:24,339 --> 00:23:26,130
Если не убежден, что это
хорошо сейчас, просто

510
00:23:26,130 --> 00:23:28,960
принять на веру, что это, в самом деле,
что это рецидив приводит к,

511
00:23:28,960 --> 00:23:31,780
но это всего лишь немного больше
Математический подход к поиску

512
00:23:31,780 --> 00:23:36,520
на времени работы сортировки слиянием
на основании его псевдокода в покое.

513
00:23:36,520 --> 00:23:39,030
>> Теперь давайте немного
передышку от всего этого,

514
00:23:39,030 --> 00:23:41,710
и принять взглянем на
уверен бывший сенатор, который

515
00:23:41,710 --> 00:23:44,260
может выглядеть немного знакомы,
кто сел с Эриком от Google

516
00:23:44,260 --> 00:23:48,410
Шмидт, некоторое время назад, для интервью
на сцене, перед целым букетом

517
00:23:48,410 --> 00:23:53,710
людей, в конечном счете, о говорить
тема, это довольно уже знакомы.

518
00:23:53,710 --> 00:23:54,575
Давайте взглянем.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Эрик Шмидт: Теперь сенатор,
Вы здесь Google,

521
00:24:03,890 --> 00:24:09,490
и я хотел бы думать о
Председательство в собеседовании.

522
00:24:09,490 --> 00:24:11,712
Теперь это трудно получить работу в качестве президента.

523
00:24:11,712 --> 00:24:12,670
ПРЕЗИДЕНТ ОБАМА: Хорошо.

524
00:24:12,670 --> 00:24:13,940
Эрик Шмидт: И ты
собирается делать [неразборчиво] в настоящее время.

525
00:24:13,940 --> 00:24:15,523
Это также трудно получить работу в Google.

526
00:24:15,523 --> 00:24:17,700
ПРЕЗИДЕНТ ОБАМА: Хорошо.

527
00:24:17,700 --> 00:24:21,330
>> Эрик Шмидт: У нас есть вопросы,
и мы просим наших кандидатов вопросы,

528
00:24:21,330 --> 00:24:24,310
и это одна из Ларри является Швиммер.

529
00:24:24,310 --> 00:24:25,890
>> ПРЕЗИДЕНТ ОБАМА: Хорошо.

530
00:24:25,890 --> 00:24:27,005
>> Эрик Шмидт: Что?

531
00:24:27,005 --> 00:24:28,130
Вы, ребята, думаете, что я шучу?

532
00:24:28,130 --> 00:24:30,590
Это прямо здесь.

533
00:24:30,590 --> 00:24:33,490
Что является наиболее эффективным способом
сортировать миллион 32 битные целые?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> ПРЕЗИДЕНТ ОБАМА: Well--

536
00:24:38,979 --> 00:24:41,020
Эрик Шмидт: Иногда,
может быть, мне жаль, maybe--

537
00:24:41,020 --> 00:24:42,750
ПРЕЗИДЕНТ ОБАМА: Нет, нет,
нет, нет, нет, я think--

538
00:24:42,750 --> 00:24:43,240
Эрик Шмидт: Это не it--

539
00:24:43,240 --> 00:24:45,430
ПРЕЗИДЕНТ ОБАМА: Я
думаю, я думаю, что пузырь

540
00:24:45,430 --> 00:24:46,875
Сортировать бы неправильный путь.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Эрик Шмидт: Ну.

543
00:24:50,535 --> 00:24:52,200
Кто сказал ему это?

544
00:24:52,200 --> 00:24:54,020
ХОРОШО.

545
00:24:54,020 --> 00:24:55,590
Я не сделал информатика on--

546
00:24:55,590 --> 00:24:58,986
>> ПРЕЗИДЕНТ ОБАМА: Мы уже
получили наши шпионы там.

547
00:24:58,986 --> 00:24:59,860
ПРОФЕССОР: Все правильно.

548
00:24:59,860 --> 00:25:03,370
Давайте оставим позади нас теперь
Теоретическая мир алгоритмов

549
00:25:03,370 --> 00:25:06,520
в асимптотического анализа
их, и вернуться к некоторым темам

550
00:25:06,520 --> 00:25:09,940
от недели нулем и единицей, и начала
удалить некоторые учебные колеса,

551
00:25:09,940 --> 00:25:10,450
если вы будете.

552
00:25:10,450 --> 00:25:13,241
Так что вы действительно понимаете,
в конечном счете, от начала до конца, что

553
00:25:13,241 --> 00:25:16,805
происходит под капотом, когда вы
писать, компилировать и выполнять программы.

554
00:25:16,805 --> 00:25:19,680
Напомним, в частности, что это было
первая программа С мы смотрели на,

555
00:25:19,680 --> 00:25:22,840
канонический, простая программа
рода, условно говоря,

556
00:25:22,840 --> 00:25:24,620
где она печатает, Hello World.

557
00:25:24,620 --> 00:25:27,610
И вспоминаю, что я сказал, то процесс
что исходный код проходит через

558
00:25:27,610 --> 00:25:28,430
является именно это.

559
00:25:28,430 --> 00:25:31,180
Вы берете исходный код, пройти
это через компилятор, как Clang,

560
00:25:31,180 --> 00:25:34,650
и прибывает объектный код, что
может выглядеть как это, нулей и единиц

561
00:25:34,650 --> 00:25:37,880
что процессор компьютера, центральное
Блок обработки или головного мозга,

562
00:25:37,880 --> 00:25:39,760
в конечном счете, понимает.

563
00:25:39,760 --> 00:25:42,460
>> Оказывается, что это
немного упрощением,

564
00:25:42,460 --> 00:25:44,480
что мы теперь в
положение, чтобы дразнить друг от друга

565
00:25:44,480 --> 00:25:46,720
чтобы понять, что действительно был
происходит под капотом

566
00:25:46,720 --> 00:25:48,600
каждый раз, когда вы запустите
Лязг, или в более общем,

567
00:25:48,600 --> 00:25:53,040
каждый раз, когда вы делаете программу,
с помощью Марка и CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
В частности, такие вещи, как
Это первый генерируется,

569
00:25:56,760 --> 00:25:58,684
когда вы впервые скомпилировать программу.

570
00:25:58,684 --> 00:26:00,600
Другими словами, когда вы
принять ваш исходный код

571
00:26:00,600 --> 00:26:04,390
и скомпилировать его, то, что первый
время выводимый Clang

572
00:26:04,390 --> 00:26:06,370
что-то известный как ассемблере.

573
00:26:06,370 --> 00:26:08,990
И в самом деле, это выглядит именно так.

574
00:26:08,990 --> 00:26:11,170
>> Я побежал команды на
командной строки раньше.

575
00:26:11,170 --> 00:26:16,260
Лязг Dash большой буквы hello.c,
и это создало файл

576
00:26:16,260 --> 00:26:19,490
для меня, называемых hello.s,
внутри которого были точно

577
00:26:19,490 --> 00:26:22,290
это содержание, и немного больше
выше, и немного больше ниже,

578
00:26:22,290 --> 00:26:25,080
но я поставил сочные
Информация здесь на экране.

579
00:26:25,080 --> 00:26:29,190
И если вы внимательно посмотрите, вы увидите,
по крайней мере, несколько знакомых ключевые слова.

580
00:26:29,190 --> 00:26:31,330
У нас есть главный в верхней.

581
00:26:31,330 --> 00:26:35,140
Мы PRINTF посередине.

582
00:26:35,140 --> 00:26:38,670
И мы также имеем привет мир
Обратная косая черта н в кавычки вниз ниже.

583
00:26:38,670 --> 00:26:42,450
>> А все остальное здесь
является Инструкция по очень низкого уровня

584
00:26:42,450 --> 00:26:45,500
что процессор компьютера понимает.

585
00:26:45,500 --> 00:26:50,090
Инструкции ЦП, которые движутся память
вокруг, что струны груз из памяти,

586
00:26:50,090 --> 00:26:52,750
и в конечном счете, печати
вещи на экране.

587
00:26:52,750 --> 00:26:56,780
Теперь то, что происходит, хотя после
эта сборка генерируется код?

588
00:26:56,780 --> 00:26:59,964
В конечном счете, вы, в самом деле,
еще генерировать объектный код.

589
00:26:59,964 --> 00:27:02,630
Но шаги, которые действительно
уже на под капотом

590
00:27:02,630 --> 00:27:04,180
выглядеть немного больше, как это.

591
00:27:04,180 --> 00:27:08,390
Исходный код становится ассемблера,
который затем становится объектом код,

592
00:27:08,390 --> 00:27:11,930
и оперативные слова здесь, что,
при компиляции исходного кода,

593
00:27:11,930 --> 00:27:16,300
прибывает ассемблерный код, а затем
при сборке кода сборки,

594
00:27:16,300 --> 00:27:17,800
прибывает объектный код.

595
00:27:17,800 --> 00:27:20,360
>> Теперь Clang супер сложные,
как много компиляторов,

596
00:27:20,360 --> 00:27:23,151
и он делает все эти шаги
вместе, и это не обязательно

597
00:27:23,151 --> 00:27:25,360
Выход любой промежуточный
файлы, которые вы можете даже увидеть.

598
00:27:25,360 --> 00:27:28,400
Это просто компилирует вещи,
который является общим термином, который

599
00:27:28,400 --> 00:27:30,000
описывает весь этот процесс.

600
00:27:30,000 --> 00:27:32,000
Но если вы действительно хотите
чтобы быть частности, есть

601
00:27:32,000 --> 00:27:34,330
намного больше там происходит, а также.

602
00:27:34,330 --> 00:27:38,860
>> Но давайте также рассмотреть теперь, даже
что супер простая программа, hello.c,

603
00:27:38,860 --> 00:27:40,540
называется функцией.

604
00:27:40,540 --> 00:27:41,870
Он призвал Printf.

605
00:27:41,870 --> 00:27:46,900
Но я не написать Printf, действительно,
который поставляется с с, так сказать.

606
00:27:46,900 --> 00:27:51,139
Это функция напомним, что это
заявил в стандартном io.h, который

607
00:27:51,139 --> 00:27:53,180
файл заголовка, который
это тема, которую мы будем на самом деле

608
00:27:53,180 --> 00:27:55,780
погрузиться в глубины, прежде чем более длинные.

609
00:27:55,780 --> 00:27:58,000
Но файл заголовка
как правило, сопровождается

610
00:27:58,000 --> 00:28:02,920
файлом кода, файл исходного кода, так
так же, как существует стандартная io.h.

611
00:28:02,920 --> 00:28:05,930
>> Некоторое время назад, кто-то,
или кому-то, также написал

612
00:28:05,930 --> 00:28:11,040
файл называется стандартным io.c, в
которые фактические определения,

613
00:28:11,040 --> 00:28:15,220
или реализации Printf,
и гроздья других функций,

614
00:28:15,220 --> 00:28:16,870
на самом деле написано.

615
00:28:16,870 --> 00:28:22,140
Поэтому, учитывая, что, если мы считаем, имея
здесь, на левом, hello.c, что, когда

616
00:28:22,140 --> 00:28:26,250
составлен, дает нам hello.s, даже если
Clang не беспокоит сохранение в месте

617
00:28:26,250 --> 00:28:31,360
мы можем увидеть его, и что сборка код
получает собраны в hello.o, который

618
00:28:31,360 --> 00:28:34,630
это, действительно, имя по умолчанию
учитывая при компиляции источник

619
00:28:34,630 --> 00:28:39,350
код в объектный код, но не
вполне готовы выполнить его еще,

620
00:28:39,350 --> 00:28:41,460
потому что еще один шаг
должно произойти, и имеет

621
00:28:41,460 --> 00:28:44,440
что происходило на протяжении последних нескольких
недели, возможно, без ведома к вам.

622
00:28:44,440 --> 00:28:47,290
>> В частности где-то
в CS50 IDE, а это,

623
00:28:47,290 --> 00:28:49,870
тоже будет чем-то вроде
упрощение на мгновение,

624
00:28:49,870 --> 00:28:54,670
есть, или был на то время,
файл называется стандартным io.c,

625
00:28:54,670 --> 00:28:58,440
что кто-то собраны в
Стандартные io.s или эквивалент,

626
00:28:58,440 --> 00:29:02,010
что кто-то затем собраны
в стандартной io.o,

627
00:29:02,010 --> 00:29:04,600
или оказывается в
немного другой файл

628
00:29:04,600 --> 00:29:07,220
Формат, который может иметь разные
расширение файла в целом,

629
00:29:07,220 --> 00:29:11,720
но в теории и концептуально, точно
эти шаги были произойти в какой-то форме.

630
00:29:11,720 --> 00:29:14,060
Что и говорить, что в настоящее время
когда я пишу программу,

631
00:29:14,060 --> 00:29:17,870
hello.c, что просто говорит, привет мир,
и я с помощью кода чужой

632
00:29:17,870 --> 00:29:22,480
как Printf, который был давным-
Время, в файле под названием стандарт io.c,

633
00:29:22,480 --> 00:29:26,390
потом как-то я должен принять мои
объектного кода, мои нули и единицы,

634
00:29:26,390 --> 00:29:29,260
и объект этого человека
код, или нули и единицы,

635
00:29:29,260 --> 00:29:34,970
и как-то связать их вместе в
один последний файл, называется привет, что

636
00:29:34,970 --> 00:29:38,070
имеет все нули и
те из моей главной функции,

637
00:29:38,070 --> 00:29:40,830
и все нули
и те, для Printf.

638
00:29:40,830 --> 00:29:44,900
>> И в самом деле, что в прошлом процесс
называется, связывая свой объектный код.

639
00:29:44,900 --> 00:29:47,490
Выход которого
представляет собой исполняемый файл.

640
00:29:47,490 --> 00:29:49,780
Таким образом, в справедливости, на
Конец дня, ничего не

641
00:29:49,780 --> 00:29:52,660
изменилось с одной недели, когда мы
впервые начал компиляции программы.

642
00:29:52,660 --> 00:29:55,200
Действительно, все это уже было
происходит под капотом,

643
00:29:55,200 --> 00:29:57,241
но теперь мы в состоянии
где мы можем на самом деле

644
00:29:57,241 --> 00:29:58,794
дразнить друг от друга эти различные шаги.

645
00:29:58,794 --> 00:30:00,710
И в самом деле, в конце
в день, мы по-прежнему

646
00:30:00,710 --> 00:30:04,480
осталось нулей и единиц, которые
на самом деле большая переходить в настоящее время

647
00:30:04,480 --> 00:30:08,620
другому возможностью C, что
у нас не было, чтобы использовать, скорее всего,

648
00:30:08,620 --> 00:30:11,250
на сегодняшний день, известный как побитовые операторы.

649
00:30:11,250 --> 00:30:15,220
Другими словами, до сих пор, мы в любое время
дело с данными в C или переменных в C,

650
00:30:15,220 --> 00:30:17,660
у нас было что-то вроде
символы и поплавки и модули

651
00:30:17,660 --> 00:30:21,990
и жаждет и двухместных и т.п., но
все те, по крайней мере восемь бит.

652
00:30:21,990 --> 00:30:25,550
Мы никогда еще не был в состоянии
манипулировать отдельных битов,

653
00:30:25,550 --> 00:30:28,970
даже если отдельный бит, мы
Знаете, может представлять 0 и 1.

654
00:30:28,970 --> 00:30:32,640
Теперь выясняется, что в C, вы
может получить доступ к отдельным битам,

655
00:30:32,640 --> 00:30:35,530
если вы знаете синтаксис,
с которой, чтобы добраться до них.

656
00:30:35,530 --> 00:30:38,010
>> Итак, давайте взглянем
у операторов побитовых.

657
00:30:38,010 --> 00:30:41,700
Так на фото, вот несколько символов, которые
мы, вроде, вроде, видел.

658
00:30:41,700 --> 00:30:45,580
Я вижу амперсанд, вертикальный
бар, и некоторые другие, а также,

659
00:30:45,580 --> 00:30:49,430
и вспомнить, что амперсанд амперсанд
это то, что мы видели раньше.

660
00:30:49,430 --> 00:30:54,060
Логический оператор И, где у вас есть
два из них вместе, или логическое ИЛИ

661
00:30:54,060 --> 00:30:56,300
Оператор, где вы
Две вертикальные полоски.

662
00:30:56,300 --> 00:31:00,550
Битовые операторы, которые мы будем
см работать на бит по отдельности,

663
00:31:00,550 --> 00:31:03,810
просто использовать один амперсанд, А
один вертикальный бар, каретка символ

664
00:31:03,810 --> 00:31:06,620
приходит следующий, маленький
Тильда, а затем оставил

665
00:31:06,620 --> 00:31:08,990
Кронштейн левой скобки, или
правая скобка правая скобка.

666
00:31:08,990 --> 00:31:10,770
Каждый из них имеет разные значения.

667
00:31:10,770 --> 00:31:11,950
>> В самом деле, давайте взглянем.

668
00:31:11,950 --> 00:31:16,560
Давайте старой школы сегодня, и использование
сенсорный экран с прошлого,

669
00:31:16,560 --> 00:31:18,002
известный как белая доска.

670
00:31:18,002 --> 00:31:19,710
И это белая доска
собирается, чтобы позволить нам

671
00:31:19,710 --> 00:31:27,360
чтобы выразить некоторые довольно простые символы,
или, скорее, некоторые довольно простые формулы,

672
00:31:27,360 --> 00:31:29,560
что мы можем в конечном счете, то
рычаги, для того,

673
00:31:29,560 --> 00:31:33,230
Для доступа к отдельным
Биты в пределах программы C.

674
00:31:33,230 --> 00:31:34,480
Другими словами, давайте сделаем это.

675
00:31:34,480 --> 00:31:37,080
Давайте сначала поговорим
момент о амперсанд,

676
00:31:37,080 --> 00:31:39,560
который является побитовое И оператора.

677
00:31:39,560 --> 00:31:42,130
Другими словами, это
оператор, который позволяет

678
00:31:42,130 --> 00:31:45,930
мне есть переменная левая
как правило, и переменная правая,

679
00:31:45,930 --> 00:31:50,640
или индивидуальное значение, что, если мы и
их вместе, дает мне конечный результат.

680
00:31:50,640 --> 00:31:51,560
Так что я имею в виду?

681
00:31:51,560 --> 00:31:54,840
Если в программе, у вас есть переменная
что магазины одной из этих значений,

682
00:31:54,840 --> 00:31:58,000
или давайте держать его проста, и просто
выписать нули и единицы в отдельности,

683
00:31:58,000 --> 00:32:00,940
Вот как работает оператор амперсанд.

684
00:32:00,940 --> 00:32:06,400
0 0 амперсанд будет равняться 0.

685
00:32:06,400 --> 00:32:07,210
Теперь, почему это?

686
00:32:07,210 --> 00:32:09,291
>> Это очень похоже на
Логические выражения,

687
00:32:09,291 --> 00:32:10,540
что мы обсуждали до сих пор.

688
00:32:10,540 --> 00:32:15,800
Если вы думаете, после всего, 0
ложь, ложь 0, ложные и ложной

689
00:32:15,800 --> 00:32:18,720
это, как мы уже обсуждали
логически, также ложно.

690
00:32:18,720 --> 00:32:20,270
Итак, мы получаем 0 здесь также.

691
00:32:20,270 --> 00:32:24,390
Если вы берете 0 амперсанд
1, хорошо, что тоже,

692
00:32:24,390 --> 00:32:29,890
будет 0, так как для этого
Выражение левая, чтобы быть правдой или 1,

693
00:32:29,890 --> 00:32:32,360
то ему необходимо будет, чтобы быть правдой, и правда.

694
00:32:32,360 --> 00:32:36,320
Но здесь мы имеем ложное
и правда, или 0 и 1.

695
00:32:36,320 --> 00:32:42,000
Теперь снова, если у нас есть 1 амперсанд
0, что тоже будет 0,

696
00:32:42,000 --> 00:32:47,240
и если у нас есть 1 амперсанд 1,
наконец, у нас есть 1 бит.

697
00:32:47,240 --> 00:32:50,340
Итак, другими словами, мы не делаем
что-нибудь интересное с этим оператором

698
00:32:50,340 --> 00:32:51,850
Пока еще нет, этот оператор амперсанд.

699
00:32:51,850 --> 00:32:53,780
Это побитовое И оператора.

700
00:32:53,780 --> 00:32:57,290
Но эти ингредиенты
через который мы можем сделать

701
00:32:57,290 --> 00:32:59,240
интересные вещи, как мы вскоре увидим.

702
00:32:59,240 --> 00:33:02,790
>> Теперь давайте посмотрим на только один
Вертикальная черта здесь справа.

703
00:33:02,790 --> 00:33:06,710
Если у меня есть 0 немного, и я
Или это с того, что побитовое

704
00:33:06,710 --> 00:33:11,030
Оператор ИЛИ, другой бит 0,
что собирается дать мне 0.

705
00:33:11,030 --> 00:33:17,540
Если я беру немного, и 0 или его с
1 бит, то я иду, чтобы получить 1.

706
00:33:17,540 --> 00:33:19,830
И в самом деле, как раз для
ясность, позвольте мне вернуться,

707
00:33:19,830 --> 00:33:23,380
так что мои вертикальные полосы
не принять за 1-х.

708
00:33:23,380 --> 00:33:26,560
Позвольте мне переписать все
мой 1 немного больше

709
00:33:26,560 --> 00:33:32,700
ясно, так что мы в следующий раз увижу, если я
имеют 1 или 0, что будет 1,

710
00:33:32,700 --> 00:33:39,060
и если у меня есть 1 или 1, что,
тоже будет 1.

711
00:33:39,060 --> 00:33:42,900
Таким образом, вы можете видеть, что логически ИЛИ
Оператор ведет себя очень по-разному.

712
00:33:42,900 --> 00:33:48,070
Это дает мне 0 или 0 дает мне 0, но
каждый другая комбинация дает мне 1.

713
00:33:48,070 --> 00:33:52,480
Пока у меня есть один 1 в
Формула, результат будет 1.

714
00:33:52,480 --> 00:33:55,580
>> В отличие от AND
Оператор, амперсанд,

715
00:33:55,580 --> 00:34:00,940
только если у меня есть два 1-х годов в
Уравнение, я на самом деле выйти на 1.

716
00:34:00,940 --> 00:34:02,850
Теперь есть несколько других
операторы, а также.

717
00:34:02,850 --> 00:34:04,810
Одним из них является немного сложнее.

718
00:34:04,810 --> 00:34:07,980
Итак, позвольте мне идти вперед и стереть
это, чтобы освободить пространство.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
И давайте взглянем на
вставки символов, на мгновение.

721
00:34:16,460 --> 00:34:18,210
Как правило, это
характер можно ввести

722
00:34:18,210 --> 00:34:21,420
На клавиатуре Удержание SHIFT и
то одно из чисел на вершине вашего США

723
00:34:21,420 --> 00:34:22,250
клавиатура.

724
00:34:22,250 --> 00:34:26,190
>> Таким образом, это является эксклюзивным
Оператор ИЛИ, исключающее ИЛИ.

725
00:34:26,190 --> 00:34:27,790
Таким образом, мы только что видели оператор или.

726
00:34:27,790 --> 00:34:29,348
Это исключительное ИЛИ оператор.

727
00:34:29,348 --> 00:34:30,639
Что на самом деле разница?

728
00:34:30,639 --> 00:34:34,570
Ну давайте посмотрим на формулу,
и использовать это в качестве ингредиентов в конечном счете.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Я хочу сказать, всегда 0.

731
00:34:39,650 --> 00:34:41,400
Это определение XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 будет 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 будет 1,
и 1 XOR 1 будет?

734
00:34:58,810 --> 00:34:59,890
Неправильно?

735
00:34:59,890 --> 00:35:00,520
Или вправо?

736
00:35:00,520 --> 00:35:01,860
Я не знаю.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Теперь то, что здесь происходит?

739
00:35:04,700 --> 00:35:06,630
Ну думаю о
наименование этого оператора.

740
00:35:06,630 --> 00:35:09,980
Исключающее ИЛИ, так как
имя, вид, предлагает,

741
00:35:09,980 --> 00:35:13,940
ответ только будет
1, если входы эксклюзивные,

742
00:35:13,940 --> 00:35:15,560
исключительно отличается.

743
00:35:15,560 --> 00:35:18,170
Так вот входы являются
то же самое, поэтому выход равен 0.

744
00:35:18,170 --> 00:35:20,700
Вот входы являются
то же самое, поэтому выход равен 0.

745
00:35:20,700 --> 00:35:25,640
Вот выходы разные, они
являются исключительными, и поэтому выход 1.

746
00:35:25,640 --> 00:35:28,190
Так что это очень похоже на
И, это очень похоже,

747
00:35:28,190 --> 00:35:32,760
или, скорее, это очень похоже на
ИЛИ, но только в эксклюзивном образом.

748
00:35:32,760 --> 00:35:36,210
Не Это один больше не 1,
потому что у нас есть два 1-х,

749
00:35:36,210 --> 00:35:38,621
и не исключительно, только один из них.

750
00:35:38,621 --> 00:35:39,120
Все в порядке.

751
00:35:39,120 --> 00:35:40,080
Что можно сказать о других?

752
00:35:40,080 --> 00:35:44,220
Ну тильды, тем временем,
на самом деле просто и красиво, к счастью.

753
00:35:44,220 --> 00:35:46,410
И это унарный
Оператор, который означает

754
00:35:46,410 --> 00:35:50,400
он применяется только к одному входу,
один операнд, так сказать.

755
00:35:50,400 --> 00:35:51,800
Не левой и правой.

756
00:35:51,800 --> 00:35:56,050
Другими словами, если вы берете тильды из
0, ответ будет наоборот.

757
00:35:56,050 --> 00:35:59,710
А если взять тильды из 1,
Ответ будет наоборот.

758
00:35:59,710 --> 00:36:02,570
Таким образом, оператор тильда
способ отрицания немного,

759
00:36:02,570 --> 00:36:06,000
или листать немного от
От 0 до 1 или от 1 до 0.

760
00:36:06,000 --> 00:36:09,820
>> И, наконец, оставляет нас
только с двумя операторами конечных,

761
00:36:09,820 --> 00:36:13,840
так называемый сдвиг влево, и
так называемый оператор сдвига вправо.

762
00:36:13,840 --> 00:36:16,620
Давайте взглянем на то, как эти работы.

763
00:36:16,620 --> 00:36:20,780
Левый оператор сдвига, написанная
с двумя угловыми скобками, как, что,

764
00:36:20,780 --> 00:36:22,110
работает следующим образом.

765
00:36:22,110 --> 00:36:27,390
Если мой вклад, или мой операнд, слева
Оператор сдвига достаточно просто 1.

766
00:36:27,390 --> 00:36:33,750
И я тогда скажу компьютер в
сдвиг влево, что 1, говорят семь мест,

767
00:36:33,750 --> 00:36:37,150
результат, как если бы я
принять, что 1 и переместить его

768
00:36:37,150 --> 00:36:40,160
семь мест в более
левый, и по умолчанию,

769
00:36:40,160 --> 00:36:42,270
мы будем считать, что
пространство справа

770
00:36:42,270 --> 00:36:44,080
собирается быть нулями.

771
00:36:44,080 --> 00:36:50,316
Другими словами, 1 сдвиг влево 7 будет
чтобы дать мне, что 1, затем 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 нулей.

773
00:36:54,060 --> 00:36:57,380
Таким образом, в некотором смысле, это позволяет
взять небольшое количество, как 1,

774
00:36:57,380 --> 00:37:00,740
и четко сделать это гораздо
намного больше, таким образом

775
00:37:00,740 --> 00:37:06,460
но на самом деле мы увидим
более умные подходы к нему

776
00:37:06,460 --> 00:37:08,080
вместо этого, а также,

777
00:37:08,080 --> 00:37:08,720
>> Все в порядке.

778
00:37:08,720 --> 00:37:10,060
Вот это для трех недели.

779
00:37:10,060 --> 00:37:11,400
Мы увидим вас в следующий раз.

780
00:37:11,400 --> 00:37:12,770
Это было CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [Играет музыка]

783
00:37:22,243 --> 00:37:25,766
>> СПИКЕР 1: Он был на закуску
бар ест горячую выдумки мороженое.

784
00:37:25,766 --> 00:37:28,090
Он был все это на его лице.

785
00:37:28,090 --> 00:37:30,506
Он одет, что шоколад, как бородой

786
00:37:30,506 --> 00:37:31,756
СПИКЕР 2: Что вы делаете?

787
00:37:31,756 --> 00:37:32,422
СПИКЕР 3: Хм?

788
00:37:32,422 --> 00:37:33,500
Что?

789
00:37:33,500 --> 00:37:36,800
>> СПИКЕР 2: Ты только двойное падение?

790
00:37:36,800 --> 00:37:38,585
Вы дважды опустил чип.

791
00:37:38,585 --> 00:37:39,460
СПИКЕР 3: Извините.

792
00:37:39,460 --> 00:37:44,440
СПИКЕР 2: Вы смоченной чип, вы
откусил, и вы снова погружают.

793
00:37:44,440 --> 00:37:44,940
СПИКЕР 3:

794
00:37:44,940 --> 00:37:48,440
СПИКЕР 2: Так вот, как положить
вся ваша рот прямо в провал.

795
00:37:48,440 --> 00:37:52,400
В следующий раз вы берете чип,
просто окунуть его один раз, и конец.

796
00:37:52,400 --> 00:37:53,890
>> СПИКЕР 3: Вы знаете, что, Дэн?

797
00:37:53,890 --> 00:37:58,006
Вы опустите путь, который вы хотите окунуться.

798
00:37:58,006 --> 00:38:01,900
Я опустите так, что я хочу, чтобы окунуться.

799
00:38:01,900 --> 00:38:03,194