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
від вартості 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