1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Музика Відтворення]

3
00:00:10,800 --> 00:00:13,500
DAVID мала: Добре.

4
00:00:13,500 --> 00:00:14,670
Гаразд, з поверненням.

5
00:00:14,670 --> 00:00:18,120
Так що це 4-й тиждень, початок
його, вже.

6
00:00:18,120 --> 00:00:21,320
І ви пам'ятаєте, що минулого тижня, ми ставимо
код відведених для тільки трохи

7
00:00:21,320 --> 00:00:24,240
і ми почали говорити трохи більше
високому рівні, про такі речі

8
00:00:24,240 --> 00:00:28,130
пошук і сортування, яка хоча і
кілька простих ідей, є

9
00:00:28,130 --> 00:00:31,840
представник класу задач
Ви почнете вирішувати особливо

10
00:00:31,840 --> 00:00:34,820
як ви починаєте думати про остаточне
проекти та цікаві рішення, які ви

11
00:00:34,820 --> 00:00:36,760
можливо, доведеться реальних проблем.

12
00:00:36,760 --> 00:00:39,490
Тепер бульбашкового сортування був одним з найпростіших
такі алгоритми, і це

13
00:00:39,490 --> 00:00:42,900
працював за наявності цих невеликих кількостях
у вигляді списку або у вигляді масиву

14
00:00:42,900 --> 00:00:46,530
Пузир їх шлях до вершини, і
великі числа перемістити свій шлях до

15
00:00:46,530 --> 00:00:47,930
До кінця цього списку.

16
00:00:47,930 --> 00:00:50,650
>> І нагадати, що ми могли представляти
бульбашкова сортування трохи

17
00:00:50,650 --> 00:00:52,310
щось на зразок цього.

18
00:00:52,310 --> 00:00:53,640
Отже, дозвольте мені йти вперед і натисніть кнопку Пуск.

19
00:00:53,640 --> 00:00:55,350
Я попередньо бульбашкового сортування.

20
00:00:55,350 --> 00:00:58,920
А якщо згадати, що вище синій
лінії представляють великі номери, невеликі

21
00:00:58,920 --> 00:01:03,300
Сині лінії являють собою невеликі номери, а
ми проходимо через це знову і знову і

22
00:01:03,300 --> 00:01:07,680
знову, порівнюючи два бари поруч один
інші в червоному, ми збираємося, щоб поміняти

23
00:01:07,680 --> 00:01:11,010
великий і мінімальним, якщо
вони вийшли з ладу.

24
00:01:11,010 --> 00:01:14,150
>> Так що це буде тривати і тривати і йти
на, і ви побачите, що чим більше

25
00:01:14,150 --> 00:01:16,700
елементи вносять свій шлях до
вправо, а більш дрібні елементи є

26
00:01:16,700 --> 00:01:17,900
пробираються вліво.

27
00:01:17,900 --> 00:01:21,380
Але ми почали кількісно
ефективністю,

28
00:01:21,380 --> 00:01:22,970
Якість цього алгоритму.

29
00:01:22,970 --> 00:01:25,200
І ми сказали, що в гіршому
випадку, цей алгоритм взяв

30
00:01:25,200 --> 00:01:27,940
приблизно скільки кроків?

31
00:01:27,940 --> 00:01:28,980
>> Таким N квадраті.

32
00:01:28,980 --> 00:01:30,402
І те, що було N?

33
00:01:30,402 --> 00:01:31,650
>> АУДИТОРІЯ: число елементів.

34
00:01:31,650 --> 00:01:32,790
>> DAVID мала: Так було N
число елементів.

35
00:01:32,790 --> 00:01:33,730
І тому ми будемо робити це часто.

36
00:01:33,730 --> 00:01:36,650
Кожен раз, коли ми хочемо говорити про розміри
проблема або розмір

37
00:01:36,650 --> 00:01:39,140
вхід, або кількість часу, необхідне
для отримання вихідних, ми просто

38
00:01:39,140 --> 00:01:41,610
узагальненої всі
вхід як н.

39
00:01:41,610 --> 00:01:45,970
Отже, повернемося до тижня 0, кількість сторінок
У телефонній книзі була N.

40
00:01:45,970 --> 00:01:47,550
Кількість студентів
в кімнаті с.

41
00:01:47,550 --> 00:01:49,630
Так і тут, ми слідуємо
цієї моделі.

42
00:01:49,630 --> 00:01:52,800
>> Тепер н квадрат не є особливо
швидко, так що ми спробували зробити краще.

43
00:01:52,800 --> 00:01:55,970
І так ми дивилися на пару
інші алгоритми, серед яких

44
00:01:55,970 --> 00:01:57,690
були сортування вибором.

45
00:01:57,690 --> 00:01:59,180
Так що вибір був Сортувати
трохи по-іншому.

46
00:01:59,180 --> 00:02:03,130
Це було майже простий, я наважуся сказати,
якого я почав на початку

47
00:02:03,130 --> 00:02:06,740
Список наших волонтерів, і я просто знову
і знову і знову пройшов через

48
00:02:06,740 --> 00:02:10,060
списку, вищипування найменшим
елемента за один раз і покласти його або

49
00:02:10,060 --> 00:02:13,040
її на початку списку.

50
00:02:13,040 --> 00:02:16,410
>> Але і це, як тільки ми почали думати
через математику і більше

51
00:02:16,410 --> 00:02:19,860
картину, думав про те, скільки разів
Я йшов назад і вперед і назад

52
00:02:19,860 --> 00:02:24,090
і вперед, ми сказали, в гіршому випадку,
Вибір роду теж було що?

53
00:02:24,090 --> 00:02:24,960
N у квадрат.

54
00:02:24,960 --> 00:02:27,490
В даний час в реальному світі, вона може
насправді бути швидше.

55
00:02:27,490 --> 00:02:30,620
Бо знову ж, у мене не було тримати
відступає, як тільки я сортував

56
00:02:30,620 --> 00:02:31,880
найдрібніших елементів.

57
00:02:31,880 --> 00:02:35,090
Але якщо ми думаємо про дуже великих N, і
Якщо ви як би зробити з математики як

58
00:02:35,090 --> 00:02:39,170
Я зробив на борту, з N квадрат
мінус щось, все інше

59
00:02:39,170 --> 00:02:41,850
Крім того, N квадратів, як тільки N
стає дійсно великим, що не

60
00:02:41,850 --> 00:02:42,850
має великого значення, як багато.

61
00:02:42,850 --> 00:02:45,470
Так як комп'ютерні вчені, ми ніби як
закривати очі на менші

62
00:02:45,470 --> 00:02:49,220
фактори і фокус тільки на фактор
Вираз, який збирається зробити

63
00:02:49,220 --> 00:02:50,330
Найбільша різниця.

64
00:02:50,330 --> 00:02:52,840
>> Ну, нарешті, ми дивилися
на сортування вставками.

65
00:02:52,840 --> 00:02:56,620
І це було близькі за духом, але
а не проходити через итеративно і

66
00:02:56,620 --> 00:03:01,250
вибрати найменший елемент по одному
час, я замість цього взяв руку, що я

67
00:03:01,250 --> 00:03:04,070
було завдано, і я вирішила, все
Добре, ти тут залишишся.

68
00:03:04,070 --> 00:03:06,160
Потім я перейшов до наступного елементу
і вирішив, що він або

69
00:03:06,160 --> 00:03:07,470
вона належала тут.

70
00:03:07,470 --> 00:03:08,810
А потім я переїхав далі й далі.

71
00:03:08,810 --> 00:03:11,780
І я міг би, щоб, по шляху,
перейти ці хлопці для того, щоб

72
00:03:11,780 --> 00:03:13,030
звільнити місце для них.

73
00:03:13,030 --> 00:03:16,880
Так, щоб був свого роду ментальний розворот
відбору на зразок тих, що ми

74
00:03:16,880 --> 00:03:18,630
називається сортування вставками.

75
00:03:18,630 --> 00:03:20,810
>> Таким чином, ці теми виникають
в реальному світі.

76
00:03:20,810 --> 00:03:23,640
Всього кілька років тому, коли певні
Сенатор був балотуватися на пост президента,

77
00:03:23,640 --> 00:03:27,160
Ерік Шмідт, в той час генеральний директор
Google, насправді мали можливість

78
00:03:27,160 --> 00:03:28,040
взяти у нього інтерв'ю.

79
00:03:28,040 --> 00:03:32,010
І ми подумали, що ми розділимо цю YouTube
Затиск для вас тут, якби ми могли повернути вгору

80
00:03:32,010 --> 00:03:32,950
гучності.

81
00:03:32,950 --> 00:03:39,360
>> [ВІДТВОРЕННЯ ВІДЕО]

82
00:03:39,360 --> 00:03:44,620
>> -Тепер, сенатор, ви тут, в Google,
і мені подобається думати президентства

83
00:03:44,620 --> 00:03:46,042
як співбесіда.

84
00:03:46,042 --> 00:03:47,770
>> [Сміється]

85
00:03:47,770 --> 00:03:50,800
>> -Тепер це важко отримати
робота в якості президента.

86
00:03:50,800 --> 00:03:52,480
І ви проходите
суворості зараз.

87
00:03:52,480 --> 00:03:54,330
Це також важко влаштуватися на роботу в Google.

88
00:03:54,330 --> 00:03:59,610
У нас є питання, і ми просимо
нашим кандидатам питання.

89
00:03:59,610 --> 00:04:02,250
І на цей раз від Ларрі Швіммер.

90
00:04:02,250 --> 00:04:05,325
>> [Сміється]

91
00:04:05,325 --> 00:04:06,400
-Ви, хлопці, думаєте, я жартую?

92
00:04:06,400 --> 00:04:08,750
Це прямо тут.

93
00:04:08,750 --> 00:04:12,110
Що є найбільш ефективним способом
сортувати мільйон двісті-розрядних цілих чисел?

94
00:04:12,110 --> 00:04:15,810
>> [Сміється]

95
00:04:15,810 --> 00:04:18,260
>> -Ну, ну -

96
00:04:18,260 --> 00:04:19,029
>> -Пробач.

97
00:04:19,029 --> 00:04:19,745
Може бути, ми повинні -

98
00:04:19,745 --> 00:04:21,000
>> -Ні, ні, ні, ні, ні.

99
00:04:21,000 --> 00:04:21,470
>> -Це не -

100
00:04:21,470 --> 00:04:22,185
ОК.

101
00:04:22,185 --> 00:04:25,328
>> -Я думаю, що бульбашкова сортування б
бути неправильний шлях.

102
00:04:25,328 --> 00:04:26,792
>> [Сміється]

103
00:04:26,792 --> 00:04:28,510
>> [ВІТАННЯ І оплески]

104
00:04:28,510 --> 00:04:31,211
>> -Давай, який сказав йому це?

105
00:04:31,211 --> 00:04:32,155
ОК.

106
00:04:32,155 --> 00:04:33,350
>> [КІНЕЦЬ відеовідтворення]

107
00:04:33,350 --> 00:04:35,070
>> DAVID мала: Так що у вас є.

108
00:04:35,070 --> 00:04:39,600
Таким чином, ми почали дати кількісну оцінку цим працює
раз, так би мовити, з чимось

109
00:04:39,600 --> 00:04:43,480
називається асимптотичним позначення, яке
просто посилаючись на наш вид повороту

110
00:04:43,480 --> 00:04:47,420
закривати очі на ці фактори і менше
Тільки дивлячись на час роботи,

111
00:04:47,420 --> 00:04:51,250
продуктивність цих алгоритмів,
як н стає дійсно великим з плином часу.

112
00:04:51,250 --> 00:04:55,110
І тому ми ввели велику О. І Big O
представлене те, що ми думали,

113
00:04:55,110 --> 00:04:57,000
як верхню межу.

114
00:04:57,000 --> 00:04:59,570
А насправді, Баррі, ми можемо знизити
, Ніж мікрофон трохи?

115
00:04:59,570 --> 00:05:01,040
>> Ми думали про це є верхньою межею.

116
00:05:01,040 --> 00:05:04,710
Так Big O п квадрат означає, що в
гіршому випадку, щось на зразок

117
00:05:04,710 --> 00:05:07,780
Вибір роду візьме
п квадрат кроків.

118
00:05:07,780 --> 00:05:10,310
Або щось на кшталт сортування вставками
б квадрат N кроків.

119
00:05:10,310 --> 00:05:15,150
Тепер за те, як вставки
, Дивіться, яке було в гіршому випадку?

120
00:05:15,150 --> 00:05:18,200
Дано масив, що найгірше
можливі сценарії, які можуть виявитися

121
00:05:18,200 --> 00:05:20,650
опинитеся перед?

122
00:05:20,650 --> 00:05:21,860
>> Це абсолютно у зворотному напрямку, чи не так?

123
00:05:21,860 --> 00:05:24,530
Тому що, якщо це абсолютно у зворотному напрямку,
що вам потрібно зробити багато роботи.

124
00:05:24,530 --> 00:05:26,420
Тому що, якщо ви абсолютно у зворотному напрямку,
Ви збираєтеся знайти

125
00:05:26,420 --> 00:05:28,840
найбільшим елементом тут, хоча
він належить там.

126
00:05:28,840 --> 00:05:31,140
Так що ви збираєтеся сказати, все правильно, по
даний момент часу, ти тут залишишся,

127
00:05:31,140 --> 00:05:32,310
так що ви залишити його в спокої.

128
00:05:32,310 --> 00:05:35,425
>> Тоді ви розумієте, чорт забирай, я повинен
перемістити цей трохи менший елемент

129
00:05:35,425 --> 00:05:36,470
Зліва від вас.

130
00:05:36,470 --> 00:05:38,770
Тоді я повинен зробити це знову
і знову і знову.

131
00:05:38,770 --> 00:05:41,410
І якби я ходив взад і вперед, ви
владнає відчуваю продуктивність

132
00:05:41,410 --> 00:05:45,540
, Що алгоритм, тому що я постійно
перетасовування всі інші вниз у

133
00:05:45,540 --> 00:05:46,510
масив, щоб звільнити місце для нього.

134
00:05:46,510 --> 00:05:47,750
Так що це в гіршому випадку.

135
00:05:47,750 --> 00:05:48,570
>> На відміну від цього -

136
00:05:48,570 --> 00:05:50,320
і це було захоплюючим востаннє -

137
00:05:50,320 --> 00:05:54,065
ми говорили, що сортування вставками
був омега чого?

138
00:05:54,065 --> 00:05:57,530
Який найкращий випадок хід
час сортування вставками?

139
00:05:57,530 --> 00:05:58,520
Так це насправді п.

140
00:05:58,520 --> 00:06:00,980
Це був порожній, що ми залишили
на дошці востаннє.

141
00:06:00,980 --> 00:06:03,160
>> І це омега п, так чому?

142
00:06:03,160 --> 00:06:06,630
Ну, в найкращому випадку, що
сортування вставками буде переданий?

143
00:06:06,630 --> 00:06:09,830
Ну, список, який все повністю відсортований
вже, мінімальна робота.

144
00:06:09,830 --> 00:06:12,460
Але те, що чарівне в тому, сортування вставкою
є те, що, оскільки він починається тут і

145
00:06:12,460 --> 00:06:15,340
вирішує, О, ти числа
Один з них, ти тут залишишся.

146
00:06:15,340 --> 00:06:16,970
Ой, яке щастя.

147
00:06:16,970 --> 00:06:17,740
>> Ти номер два.

148
00:06:17,740 --> 00:06:19,030
Ви також належать тут.

149
00:06:19,030 --> 00:06:21,010
Номер три, ще краще,
Вам варто до нас.

150
00:06:21,010 --> 00:06:25,210
Як тільки він потрапляє в кінці
Список, на сортування вставками у псевдокоді

151
00:06:25,210 --> 00:06:28,010
, Що ми йшли у вербально
Останній раз, це робиться.

152
00:06:28,010 --> 00:06:32,790
Однак вибір виду, навпаки,
продовжував робити те, що?

153
00:06:32,790 --> 00:06:35,260
>> Продовжував йти за списком
знову і знову і знову.

154
00:06:35,260 --> 00:06:39,160
Оскільки ключове розуміння було тільки
Як тільки ви дивилися всі шляхи до

155
00:06:39,160 --> 00:06:42,500
кінці списку ви можете бути впевнені
що елемент був обраний

156
00:06:42,500 --> 00:06:45,560
Дійсно в даний час найменший елемент.

157
00:06:45,560 --> 00:06:48,920
Таким чином, ці різні психічні моделях
до отримання деяких дуже реальним

158
00:06:48,920 --> 00:06:53,130
відмінності для нас, а також ці
теоретичні асимптотичної відмінності.

159
00:06:53,130 --> 00:06:56,910
>> Так просто, щоб резюмувати, то, Big O п
квадрат, ми бачили кілька таких

160
00:06:56,910 --> 00:06:58,350
алгоритмів досі.

161
00:06:58,350 --> 00:06:59,580
Big O п?

162
00:06:59,580 --> 00:07:02,870
Що алгоритм, здатний
назвати Big O п?

163
00:07:02,870 --> 00:07:06,930
У гіршому випадку, вона займає
лінійний число кроків.

164
00:07:06,930 --> 00:07:07,810
>> Добре, лінійний пошук.

165
00:07:07,810 --> 00:07:10,470
А в гіршому випадку, коли це
елемент, який ви шукаєте, коли

166
00:07:10,470 --> 00:07:12,950
застосуванні лінійного пошуку?

167
00:07:12,950 --> 00:07:14,680
>> Добре, в гіршому випадку,
це навіть не там.

168
00:07:14,680 --> 00:07:17,000
Або в другому гіршому випадку, це
всі шляхи зрештою, який

169
00:07:17,000 --> 00:07:18,880
плюс-мінус один крок різниці.

170
00:07:18,880 --> 00:07:21,180
Отже, врешті-решт,
ми можемо сказати, що це лінійна.

171
00:07:21,180 --> 00:07:23,910
Big O п буде лінійний пошук,
тому що в гіршому випадку,

172
00:07:23,910 --> 00:07:26,610
Елемент навіть не там, або це
всі шляхи в кінці.

173
00:07:26,610 --> 00:07:29,370
>> Ну, Big O журналу н.

174
00:07:29,370 --> 00:07:32,760
Ми не говорили дуже докладно про
це, але ми бачили це раніше.

175
00:07:32,760 --> 00:07:36,840
Що працює в так званий логарифмічний
часу, в гіршому випадку?

176
00:07:36,840 --> 00:07:38,500
>> Так, так що бінарний пошук.

177
00:07:38,500 --> 00:07:42,930
І бінарного пошуку в гіршому випадку
може мати елемент десь

178
00:07:42,930 --> 00:07:45,640
середині, або в іншому
в масиві.

179
00:07:45,640 --> 00:07:48,040
Але ви тільки знайти його, як тільки ви
розділити список в два рази, в

180
00:07:48,040 --> 00:07:48,940
половина, навпіл, навпіл.

181
00:07:48,940 --> 00:07:50,200
А потім вуаля, що вона є.

182
00:07:50,200 --> 00:07:52,500
Або, знову ж, гіршому випадку,
це навіть не там.

183
00:07:52,500 --> 00:07:56,770
Але ви не знаєте, що це не є
поки ніби не досягнете, що минулого

184
00:07:56,770 --> 00:08:00,470
самий нижній елементів вдвічі
і скорочення вдвічі і вдвічі.

185
00:08:00,470 --> 00:08:01,400
>> Big O 1.

186
00:08:01,400 --> 00:08:03,540
Можливо, ми можемо Big O 2, Big O 3.

187
00:08:03,540 --> 00:08:06,260
У будь-який час ви хочете просто постійне число,
ми просто начебто просто спростити

188
00:08:06,260 --> 00:08:07,280
що Big O 1.

189
00:08:07,280 --> 00:08:10,440
Хоча, якщо реально, вона займає
2 або навіть 100 кроків, якщо це

190
00:08:10,440 --> 00:08:13,680
постійне число кроків
ми просто скажемо Big O 1.

191
00:08:13,680 --> 00:08:15,930
Що це алгоритм
У Big O 1?

192
00:08:15,930 --> 00:08:18,350
>> АУДИТОРІЯ: Визначення довжини
змінної.

193
00:08:18,350 --> 00:08:21,090
>> DAVID мала: Пошук
Довжина змінної?

194
00:08:21,090 --> 00:08:23,870
>> АУДИТОРІЯ: Ні, довжина
якщо він вже відсортований.

195
00:08:23,870 --> 00:08:24,160
>> DAVID мала: Добре.

196
00:08:24,160 --> 00:08:27,850
ОК, так що знайти щось довжину
якщо довжина що щось подібне

197
00:08:27,850 --> 00:08:30,020
масив, зберігається в деякої змінної.

198
00:08:30,020 --> 00:08:33,380
Тому що ви можете просто прочитати змінну,
або роздрукувати змінної або

199
00:08:33,380 --> 00:08:34,960
просто взагалі доступ до цієї змінної.

200
00:08:34,960 --> 00:08:37,299
І вуаля, що вимагає постійного часу.

201
00:08:37,299 --> 00:08:38,909
>> На відміну від цього, думаю, назад в хорошому стані.

202
00:08:38,909 --> 00:08:42,460
Згадайте перший тиждень C,
виклику просто Е і друку

203
00:08:42,460 --> 00:08:46,240
щось на екрані, можливо,
постійний час, так він просто приймає

204
00:08:46,240 --> 00:08:50,880
деяке число циклів процесора, щоб показати
, Що текст на екрані.

205
00:08:50,880 --> 00:08:52,720
Або чекати - чи не так?

206
00:08:52,720 --> 00:08:56,430
Як ще ми можемо моделювати
продуктивність Е?

207
00:08:56,430 --> 00:09:00,420
Хто-небудь хотів би не погодитися, що
Може бути, це не зовсім постійний час?

208
00:09:00,420 --> 00:09:03,600
У якому сенсі може Е біжить
Час, фактично виводячи рядок на

209
00:09:03,600 --> 00:09:05,580
екрані, будь то
крім постійною.

210
00:09:05,580 --> 00:09:07,860
>> АУДИТОРІЯ: [нерозбірливо].

211
00:09:07,860 --> 00:09:08,230
>> DAVID мала: Так.

212
00:09:08,230 --> 00:09:09,300
Так що це залежить від нашої точки зору.

213
00:09:09,300 --> 00:09:13,390
Якщо ми насправді думаємо про вхід
Е як рядки, а

214
00:09:13,390 --> 00:09:16,380
Тому ми вимірюємо розмір цього
Введення його довжина - тому назвемо

215
00:09:16,380 --> 00:09:17,780
що довжини N, а також -

216
00:09:17,780 --> 00:09:21,990
Можна стверджувати, що Е є найбільшою O п
тому що він збирається зробити кроки ви н

217
00:09:21,990 --> 00:09:24,750
роздрукувати кожну з цих N
символів, швидше за все.

218
00:09:24,750 --> 00:09:27,730
Принаймні, в тій мірі, що ми припускаємо
що, можливо, він використовує для петлі

219
00:09:27,730 --> 00:09:28,560
під капотом.

220
00:09:28,560 --> 00:09:30,860
>> Але ми повинні були б дивитися на це
код краще зрозуміти його.

221
00:09:30,860 --> 00:09:33,650
І дійсно, як тільки ви хлопці починають
Аналізуючи власні алгоритми, ви будете

222
00:09:33,650 --> 00:09:34,900
буквально зробити саме це.

223
00:09:34,900 --> 00:09:37,765
Сортувати очного яблука код і думати
Про нас - все в порядку, у мене є ця петля

224
00:09:37,765 --> 00:09:41,870
Тут або у мене є вкладені цикли тут,
що буде робити речі N N раз,

225
00:09:41,870 --> 00:09:46,050
і ви можете сортувати розуму свій шлях
через код, навіть якщо це

226
00:09:46,050 --> 00:09:47,980
псевдокод, а не реальний код.

227
00:09:47,980 --> 00:09:49,730
>> Так що про омега N квадратів?

228
00:09:49,730 --> 00:09:53,582
Те, що було алгоритм, в кращому
випадку, все ще взяв квадрат N кроків?

229
00:09:53,582 --> 00:09:54,014
Так?

230
00:09:54,014 --> 00:09:54,880
>> АУДИТОРІЯ: [нерозбірливо].

231
00:09:54,880 --> 00:09:55,900
>> DAVID мала: Так Сортувати вибору.

232
00:09:55,900 --> 00:09:59,150
Тому що в цьому проблема дійсно зменшений
до того, що знову ж, я не знаю,

233
00:09:59,150 --> 00:10:02,600
Я знайшов поточного меншому, поки
Я перевірив всі прокляті елементів.

234
00:10:02,600 --> 00:10:08,050
Так омега, скажімо, п
тільки що прийшов з одним.

235
00:10:08,050 --> 00:10:09,300
Сортування вставками.

236
00:10:09,300 --> 00:10:12,370
Якщо список трапляється бути відсортовані
вже, в кращому випадку ми просто повинні

237
00:10:12,370 --> 00:10:15,090
щоб зробити один прохід через нього,
і в цей момент ми впевнені.

238
00:10:15,090 --> 00:10:17,890
І потім, що можна сказати
лінійні, напевно.

239
00:10:17,890 --> 00:10:20,570
>> Як щодо омега 1?

240
00:10:20,570 --> 00:10:23,790
Що, в кращому випадку, може зайняти
постійне число кроків?

241
00:10:23,790 --> 00:10:27,220
Так лінійний пошук, якщо ви просто щастить
і елемент, який ви шукаєте

242
00:10:27,220 --> 00:10:31,000
знаходиться на самому початку списку,
якщо це те, де ви починаєте вашу

243
00:10:31,000 --> 00:10:33,070
лінійного обходу цього списку.

244
00:10:33,070 --> 00:10:35,180
>> І це вірно для
кілька речей.

245
00:10:35,180 --> 00:10:37,660
Наприклад, навіть двійковий
пошук омега 1.

246
00:10:37,660 --> 00:10:40,310
Тому що, якщо ви отримуєте дійсно прокляте
пощастило, і дотик смаку в середині

247
00:10:40,310 --> 00:10:42,950
вашого масиву є число
Ви шукаєте?

248
00:10:42,950 --> 00:10:45,730
Таким чином, ви можете отримати пощастило там, а також.

249
00:10:45,730 --> 00:10:49,190
>> Цей, нарешті, омега N § п.

250
00:10:49,190 --> 00:10:52,573
Таким N журнал N, нам справді не
говорити про поки немає, але -

251
00:10:52,573 --> 00:10:53,300
>> АУДИТОРІЯ: Сортування злиттям?

252
00:10:53,300 --> 00:10:53,960
>> DAVID мала: сортування злиттям.

253
00:10:53,960 --> 00:10:56,920
Це було захоплюючим останнього часу,
де ми запропонували, і ми показали

254
00:10:56,920 --> 00:10:58,600
візуально, тобто алгоритми.

255
00:10:58,600 --> 00:11:02,470
І сортування злиттям тільки одного такого
Алгоритм, який принципово швидше

256
00:11:02,470 --> 00:11:03,450
ніж деякі з цих інших хлопців.

257
00:11:03,450 --> 00:11:07,800
Справді, злиття короткий не тільки в
кращому випадку N журнал N, в гіршому

258
00:11:07,800 --> 00:11:09,460
Випадок п § п.

259
00:11:09,460 --> 00:11:14,540
І коли у вас є це збіг
Омега і Big O є одне і те ж?

260
00:11:14,540 --> 00:11:17,310
Ми можемо реально описати це як те, що
називаються тета, хоча це

261
00:11:17,310 --> 00:11:18,220
трохи рідше.

262
00:11:18,220 --> 00:11:21,730
Але це просто означає, що два стрибки
У цьому випадку ті ж самі.

263
00:11:21,730 --> 00:11:25,770
>> Так сортування злиттям, що ж це
дійсно зводяться до для нас?

264
00:11:25,770 --> 00:11:27,000
Ну, згадайте мотивації.

265
00:11:27,000 --> 00:11:30,340
Дозвольте мені підтягнути анімацію, яке
Ми не дивилися на останній раз.

266
00:11:30,340 --> 00:11:33,390
Це одне, та ж ідея, але
це трохи більше.

267
00:11:33,390 --> 00:11:36,160
І я збираюся йти вперед і відзначити,
перше - у нас є на сортування вставками

268
00:11:36,160 --> 00:11:39,410
лівому верхньому куті, а потім вибір роду,
бульбашкова сортування, кілька інших видів -

269
00:11:39,410 --> 00:11:42,670
оболонки і швидко, - що ми ще не говорили
о, і купу і сортування злиттям.

270
00:11:42,670 --> 00:11:47,090
>> Так принаймні спробувати зосередитися на ваших очах
трійку на лівій, а потім

271
00:11:47,090 --> 00:11:49,120
сортування злиттям, коли я натискаю
цієї зеленою стрілкою.

272
00:11:49,120 --> 00:11:51,900
Але я дозволю всі вони запускаються, просто щоб
дати вам відчуття різноманітності

273
00:11:51,900 --> 00:11:53,980
Алгоритми, які існують у світі.

274
00:11:53,980 --> 00:11:56,180
Я збираюся дозволити цій перспективі
всього за кілька секунд.

275
00:11:56,180 --> 00:11:59,640
І якщо ви зосередитеся очі - вибрати
Алгоритм, зосередитися на ньому протягом всього

276
00:11:59,640 --> 00:12:02,970
секунд - ви починаєте бачити
картина, що це здійснення.

277
00:12:02,970 --> 00:12:04,530
>> Сортування злиттям, зауважте, робиться.

278
00:12:04,530 --> 00:12:06,430
Купи сортування, швидкого сортування, Shell -

279
00:12:06,430 --> 00:12:09,480
так що здається, ми ввели три
найгірших алгоритмів минулого тижня.

280
00:12:09,480 --> 00:12:12,960
Але це добре, що ми сьогодні тут, щоб
подивитися на сортування злиттям, яке є одним з

281
00:12:12,960 --> 00:12:16,500
більш легкі, щоб дивитися на, навіть
хоча вона, ймовірно, буде згинатися ваш розум

282
00:12:16,500 --> 00:12:17,490
тільки трохи.

283
00:12:17,490 --> 00:12:21,130
Тут ми можемо бачити, як багато
Вибір роду смокче.

284
00:12:21,130 --> 00:12:24,600
>> Але, з іншого боку, це
дійсно легко здійснити.

285
00:12:24,600 --> 00:12:28,160
І може бути, для P набір 3, це одна з
Алгоритми ви вирішили реалізувати

286
00:12:28,160 --> 00:12:28,960
для стандартного видання.

287
00:12:28,960 --> 00:12:30,970
Чудово підходить, абсолютно правильно.

288
00:12:30,970 --> 00:12:35,210
>> Але знову ж, як н стає великим, якщо ви
вибрати для реалізації більш швидкий алгоритм

289
00:12:35,210 --> 00:12:39,020
подобається сортування злиттям, шанси у великих і
більше входів, код є просто

290
00:12:39,020 --> 00:12:39,800
збирається працювати швидше.

291
00:12:39,800 --> 00:12:41,090
Ваш сайт буде працювати краще.

292
00:12:41,090 --> 00:12:42,650
Ваші користувачі будуть щасливішими.

293
00:12:42,650 --> 00:12:45,280
І так є ці ефекти
фактично даючи

294
00:12:45,280 --> 00:12:47,350
нам деякі глибокі думки.

295
00:12:47,350 --> 00:12:49,990
>> Отже, давайте подивимося, що злиття
Сортувати насправді все о.

296
00:12:49,990 --> 00:12:52,992
Саме чудове в тому, що злиття
роду є саме це.

297
00:12:52,992 --> 00:12:56,300
Це, знову ж таки, те, що ми назвали
псевдокод, псевдокод істота

298
00:12:56,300 --> 00:12:57,720
Англійська-подібний синтаксис.

299
00:12:57,720 --> 00:12:59,890
І простота
роду захоплюючим.

300
00:12:59,890 --> 00:13:02,840
>> Так на вході з п елементів - так, щоб
просто означає, ось масив.

301
00:13:02,840 --> 00:13:04,000
У цього є N речі в ньому.

302
00:13:04,000 --> 00:13:05,370
Це все, що ми говоримо, що там.

303
00:13:05,370 --> 00:13:07,560
>> Якщо N менше 2, повернутися.

304
00:13:07,560 --> 00:13:08,640
Так що це просто тривіальний випадок.

305
00:13:08,640 --> 00:13:12,580
Якщо N менше 2, то, очевидно, це
1 або 0, в цьому випадку річ

306
00:13:12,580 --> 00:13:14,780
вже відсортований або неіснуючі,
так що просто повернутися.

307
00:13:14,780 --> 00:13:15,900
Там немає нічого, щоб зробити.

308
00:13:15,900 --> 00:13:18,360
Так що це простий випадок, щоб обривати.

309
00:13:18,360 --> 00:13:20,110
>> В іншому випадку, у нас є три етапи.

310
00:13:20,110 --> 00:13:23,650
Сортувати ліву половину елементів, отсортируйте
Права половина елементів

311
00:13:23,650 --> 00:13:26,650
, А потім об'єднати відсортований половини.

312
00:13:26,650 --> 00:13:29,400
Що цікаво тут те, що
Я начебто понтіровавшего, вірно?

313
00:13:29,400 --> 00:13:32,300
Там начебто кругової визначенню
для цього алгоритму.

314
00:13:32,300 --> 00:13:35,986
У якому сенсі цього алгоритму
Визначення кругової?

315
00:13:35,986 --> 00:13:37,850
>> АУДИТОРІЯ: [нерозбірливо].

316
00:13:37,850 --> 00:13:41,670
>> DAVID мала: Так, мій алгоритм сортування,
двох своїх кроків "вид

317
00:13:41,670 --> 00:13:44,640
щось. "І так, що виникає
Питання, ну, що я збираюся використовувати

318
00:13:44,640 --> 00:13:46,460
для сортування лівої половини
а права половина?

319
00:13:46,460 --> 00:13:49,600
І краса в тому, що навіть при тому,
знову ж, це галюциногенний

320
00:13:49,600 --> 00:13:54,030
частина потенційно, ви можете використовувати той же
Алгоритм для сортування лівій половині.

321
00:13:54,030 --> 00:13:54,700
>> Але почекайте хвилину.

322
00:13:54,700 --> 00:13:57,070
Коли ви сказали, щоб відсортувати
Ліва половина, які дві

323
00:13:57,070 --> 00:13:58,240
кроків буде далі?

324
00:13:58,240 --> 00:14:00,550
Ми розберемося з лівої половини
Ліва половина і право

325
00:14:00,550 --> 00:14:01,420
половина лівої половини.

326
00:14:01,420 --> 00:14:04,430
Блін, як мені впорядкувати ці два
половини і чверті, в даний час?

327
00:14:04,430 --> 00:14:05,260
>> Але це не страшно.

328
00:14:05,260 --> 00:14:07,830
У нас є алгоритм сортування тут.

329
00:14:07,830 --> 00:14:10,660
І хоча ви можете турбуватися
Перше це начебто нескінченного

330
00:14:10,660 --> 00:14:12,780
петлі, це цикл, який ніколи не
скінчиться - він збирається

331
00:14:12,780 --> 00:14:15,770
припиниться, як тільки те, що відбувається?

332
00:14:15,770 --> 00:14:16,970
Після п менше 2.

333
00:14:16,970 --> 00:14:19,180
Які в кінцевому підсумку відбудеться,
тому що якщо ви продовжуйте ділити на два і

334
00:14:19,180 --> 00:14:23,020
зниження в два рази скоротити вдвічі ці половини, безумовно,
в кінці кінців ви будете в кінцевому

335
00:14:23,020 --> 00:14:25,350
тільки з 1 або 0 елементів.

336
00:14:25,350 --> 00:14:28,500
У цей момент, цей алгоритм
говорить, що ви зробили.

337
00:14:28,500 --> 00:14:31,020
>> Таким чином, справжня магія в цьому
Алгоритм, здається, в

338
00:14:31,020 --> 00:14:33,470
цей останній крок, зливаючись.

339
00:14:33,470 --> 00:14:37,190
Це проста ідея просто злиття двох
речі, це те, що в кінцевому рахунку буде

340
00:14:37,190 --> 00:14:40,920
, Щоб дозволити нам відсортувати масив,
скажімо, вісім елементів.

341
00:14:40,920 --> 00:14:44,410
Так що у мене ще вісім куль до стресу
Тут, вісім папірці, і один

342
00:14:44,410 --> 00:14:45,500
Google скла -

343
00:14:45,500 --> 00:14:46,140
які я отримую, щоб зберегти.

344
00:14:46,140 --> 00:14:46,960
>> [Сміється]

345
00:14:46,960 --> 00:14:48,970
>> DAVID мала: Якби ми могли прийняти вісім
добровольців, і давайте подивимося, якщо ми можемо

346
00:14:48,970 --> 00:14:51,430
грати в цю, таким чином.

347
00:14:51,430 --> 00:14:52,500
Нічого собі, ОК.

348
00:14:52,500 --> 00:14:53,565
Інформатика стає весело.

349
00:14:53,565 --> 00:14:54,320
Добре.

350
00:14:54,320 --> 00:14:57,770
Так, як ви троє
найбільших руку там.

351
00:14:57,770 --> 00:14:58,580
Чотири в спину.

352
00:14:58,580 --> 00:15:02,220
А як щодо зробимо Вам
три в цьому ряду?

353
00:15:02,220 --> 00:15:03,390
І чотири в передній частині.

354
00:15:03,390 --> 00:15:04,920
Таким чином, ви вісім, піднімайся.

355
00:15:04,920 --> 00:15:12,060
>> [Сміється]

356
00:15:12,060 --> 00:15:13,450
>> DAVID мала: Я насправді
не впевнений, що це таке.

357
00:15:13,450 --> 00:15:14,810
Це стрес куль?

358
00:15:14,810 --> 00:15:16,510
Настільні лампи?

359
00:15:16,510 --> 00:15:18,650
Матеріал?

360
00:15:18,650 --> 00:15:19,680
В інтернеті?

361
00:15:19,680 --> 00:15:20,160
>> ОК.

362
00:15:20,160 --> 00:15:21,310
Так що приїжджайте і вище.

363
00:15:21,310 --> 00:15:22,310
Хто хотів -

364
00:15:22,310 --> 00:15:23,570
продовжують надходити.

365
00:15:23,570 --> 00:15:24,240
Давайте подивимося.

366
00:15:24,240 --> 00:15:26,460
І це ставить вас в місці -

367
00:15:26,460 --> 00:15:27,940
Ви знаходитесь в одному розташування.

368
00:15:27,940 --> 00:15:28,670
Ой, почекай хвилинку.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - о, добре.

370
00:15:30,760 --> 00:15:31,310
Добре, що ми хороші.

371
00:15:31,310 --> 00:15:35,130
Гаразд, у всіх є місце,
але не на склі Google.

372
00:15:35,130 --> 00:15:36,475
Дозвольте мені в чергу ці вгору.

373
00:15:36,475 --> 00:15:37,115
Як тебе звуть?

374
00:15:37,115 --> 00:15:37,440
>> МІШЕЛЬ: Мішель.

375
00:15:37,440 --> 00:15:38,090
>> DAVID мала: Мішель?

376
00:15:38,090 --> 00:15:42,000
Гаразд, ви отримуєте можливість виглядати
Грайте і вигравайте, якщо це нормально.

377
00:15:42,000 --> 00:15:44,625
Ну, я теж, я вважаю,
на мить.

378
00:15:44,625 --> 00:15:45,875
Всі права, в режимі очікування.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Ми намагаємося, щоб придумати
випадки використання Google скла, і ми

381
00:15:50,950 --> 00:15:53,750
думав, що це було б цікаво, щоб просто робити
це коли люди на сцені.

382
00:15:53,750 --> 00:15:57,120
Ми запишемо світі
з їхньої точки зору.

383
00:15:57,120 --> 00:15:58,410
Добре.

384
00:15:58,410 --> 00:15:59,830
Не можливо, що Google призначене.

385
00:15:59,830 --> 00:16:02,260
Гаразд, якщо ви не проти носити
цьому протягом наступного незручний хвилин

386
00:16:02,260 --> 00:16:03,150
це було б чудово.

387
00:16:03,150 --> 00:16:08,620
>> Гаразд, так що ми маємо тут справу з масивом
елементами і масиву, згідно

388
00:16:08,620 --> 00:16:11,480
папірці в цих людей "
руки, в даний час відсортовані.

389
00:16:11,480 --> 00:16:12,050
>> МІШЕЛЬ: О, це так дивно.

390
00:16:12,050 --> 00:16:12,810
>> DAVID мала: Це значною мірою випадковим.

391
00:16:12,810 --> 00:16:15,760
І через хвилину, ми збираємося, щоб спробувати
для реалізації сортування злиттям разом

392
00:16:15,760 --> 00:16:17,950
і подивитися, де, що ключове розуміння є.

393
00:16:17,950 --> 00:16:21,970
І трюк тут з сортування злиттям є
те, що ми поки не передбачається.

394
00:16:21,970 --> 00:16:24,030
Ми насправді потрібна
додатковий простір.

395
00:16:24,030 --> 00:16:26,650
Так що ж відбувається, що особливо
цікаве в цьому те, що ці

396
00:16:26,650 --> 00:16:29,270
хлопці, збираєтеся пересуватися трохи
небагато, тому що я буду вважати, що

397
00:16:29,270 --> 00:16:31,880
є додаткова масив просторі,
скажімо, відразу за ними.

398
00:16:31,880 --> 00:16:34,570
>> Так що якщо вони за свої крісла,
це вторинне масиву.

399
00:16:34,570 --> 00:16:36,960
Якщо вони сидять тут, це
первинного масиву.

400
00:16:36,960 --> 00:16:40,170
Але це ресурс, який ми маємо
не використала досі з бульбашкою

401
00:16:40,170 --> 00:16:42,040
сортування, з вибором виду,
з сортування вставками.

402
00:16:42,040 --> 00:16:44,600
Нагадаємо, минулого тижня, все просто
вид перемішуються на місці.

403
00:16:44,600 --> 00:16:46,840
Вони не використовували будь-якої додаткової пам'яті.

404
00:16:46,840 --> 00:16:49,310
Ми створили місце для людей
переміщення людей навколо.

405
00:16:49,310 --> 00:16:50,580
>> Так що це ключове розуміння, теж.

406
00:16:50,580 --> 00:16:53,410
Там є компроміс, в цілому в
комп'ютерні науки, ресурсів.

407
00:16:53,410 --> 00:16:55,800
Якщо ви хочете прискорити щось
як час, ви збираєтеся

408
00:16:55,800 --> 00:16:56,900
доведеться заплатити ціну.

409
00:16:56,900 --> 00:17:00,750
І одна з цих цін дуже часто
просторі, обсяг пам'яті або жорсткого

410
00:17:00,750 --> 00:17:01,700
дискового простору, який ви використовуєте.

411
00:17:01,700 --> 00:17:03,640
Або, якщо чесно, кількість
програміст часу.

412
00:17:03,640 --> 00:17:06,700
Скільки часу це займе у вас, людини,
в цілях практичного здійснення ще кілька

413
00:17:06,700 --> 00:17:07,829
складний алгоритм.

414
00:17:07,829 --> 00:17:09,760
Але на сьогоднішній день, компроміс
час і простір.

415
00:17:09,760 --> 00:17:11,930
>> Так що, якщо ви, хлопці, могли б просто підніміть
номери, щоб ми могли бачити, що Ви

416
00:17:11,930 --> 00:17:15,839
Дійсно відповідний 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Відмінно.

418
00:17:16,599 --> 00:17:19,520
Так що я збираюся спробувати, щоб організувати
речі, якщо ви, хлопці, можете просто

419
00:17:19,520 --> 00:17:21,800
Іди за мною тут.

420
00:17:21,800 --> 00:17:26,650
>> Так що я збираюся здійснити, по-перше,
Перший етап псевдокоду, який

421
00:17:26,650 --> 00:17:29,440
на вході елементів п, якщо п
менше 2, то повертається.

422
00:17:29,440 --> 00:17:31,370
Очевидно, що ні
застосовуються, тому ми рухатися далі.

423
00:17:31,370 --> 00:17:33,340
Так відсортувати ліву половину елементів.

424
00:17:33,340 --> 00:17:36,220
Значить, я збираюся зосередити свою
увагу на мить на цих

425
00:17:36,220 --> 00:17:37,310
четверо хлопців тут.

426
00:17:37,310 --> 00:17:39,774
Добре, що я наступний робити?

427
00:17:39,774 --> 00:17:40,570
>> АУДИТОРІЯ: Сортувати ліву половину.

428
00:17:40,570 --> 00:17:42,780
>> DAVID мала: Так що тепер у мене є, щоб розібратися
Ліва половина цих хлопців.

429
00:17:42,780 --> 00:17:45,580
Бо знову ж, припустимо, до себе
Мета полягає в сортуванні ліву половину.

430
00:17:45,580 --> 00:17:46,440
Як ви це зробили?

431
00:17:46,440 --> 00:17:49,140
Просто дотримуйтесь інструкцій, навіть
хоча ми робимо це знову.

432
00:17:49,140 --> 00:17:50,160
Так відсортувати ліву половину.

433
00:17:50,160 --> 00:17:52,030
Тепер я сортування цих двох хлопців.

434
00:17:52,030 --> 00:17:53,563
Що буде далі?

435
00:17:53,563 --> 00:17:54,510
>> АУДИТОРІЯ: Сортувати ліву половину.

436
00:17:54,510 --> 00:17:55,460
>> DAVID мала: Сортувати ліву половину.

437
00:17:55,460 --> 00:18:00,680
Так що тепер це, це місце тут,
наведено список розмір 1.

438
00:18:00,680 --> 00:18:01,365
І те, що тебе звуть?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Принцеса Дейзі.

440
00:18:02,390 --> 00:18:03,690
>> DAVID мала: Принцеса Дейзі тут.

441
00:18:03,690 --> 00:18:07,470
І ось вона вже відсортований, так як
Список має розмір 1.

442
00:18:07,470 --> 00:18:09,490
Що мені робити наступний?

443
00:18:09,490 --> 00:18:13,680
OK, повернутися, тому що список з
розмір 1, який складає менше 2.

444
00:18:13,680 --> 00:18:14,320
Тоді в чому ж наступний крок?

445
00:18:14,320 --> 00:18:17,490
І тепер ви повинні вид
повернутися у вашому розумі.

446
00:18:17,490 --> 00:18:19,340
>> Сортувати права половина, яка -

447
00:18:19,340 --> 00:18:19,570
Як тебе звуть?

448
00:18:19,570 --> 00:18:20,220
>> Лінда: Лінда.

449
00:18:20,220 --> 00:18:20,980
>> DAVID мала: Лінда.

450
00:18:20,980 --> 00:18:23,210
І так, що ж нам тепер робити, що
у нас є список розміром 1?

451
00:18:23,210 --> 00:18:24,440
>> АУДИТОРІЯ: Повернення.

452
00:18:24,440 --> 00:18:24,760
>> DAVID мала: Обережно.

453
00:18:24,760 --> 00:18:29,540
Повернемося першої, і тепер третій
Крок - і якщо я ніби зобразити його

454
00:18:29,540 --> 00:18:33,490
охоплює два місця, тепер я
необхідно об'єднати ці два елементи.

455
00:18:33,490 --> 00:18:35,530
Так що тепер, на жаль, елементи
вийшли з ладу.

456
00:18:35,530 --> 00:18:39,920
Але на цьому процес об'єднання
починає ставати переконливими.

457
00:18:39,920 --> 00:18:42,410
>> Так що, якщо ви, хлопці, могли постояти за просто
момент, я буду мати потребу в вас, в

458
00:18:42,410 --> 00:18:44,170
момент, щоб крок позаду стільця.

459
00:18:44,170 --> 00:18:46,480
І якщо Лінда, оскільки 2 знаходиться
менше, ніж 4, чому не

460
00:18:46,480 --> 00:18:48,130
Вас приходять в першу чергу?

461
00:18:48,130 --> 00:18:48,690
Залишайтеся там.

462
00:18:48,690 --> 00:18:50,520
Так Лінда, ви приходите навколо першої.

463
00:18:50,520 --> 00:18:53,820
>> Зараз насправді, якщо це просто масив
ми могли б просто перемістити її в режимі реального часу

464
00:18:53,820 --> 00:18:55,360
цієї кафедри в це місце.

465
00:18:55,360 --> 00:18:57,770
Отже, уявіть, що було потрібно якийсь постійне
число кроків 1.

466
00:18:57,770 --> 00:18:58,480
А тепер -

467
00:18:58,480 --> 00:19:01,490
але ми повинні поставити вас в
першого місця тут.

468
00:19:01,490 --> 00:19:03,930
>> І тепер, якщо ви могли б приходити,
також, ми збираємося

469
00:19:03,930 --> 00:19:06,300
Розміщення знаходиться в два.

470
00:19:06,300 --> 00:19:09,120
І навіть якщо це відчуває, що це
зайняти деякий час, те, що приємно зараз

471
00:19:09,120 --> 00:19:14,710
що ліва половина
Ліва половина тепер сортується.

472
00:19:14,710 --> 00:19:18,010
Так що був наступний крок, якщо ми зараз
перемотати далі в історію?

473
00:19:18,010 --> 00:19:18,980
>> АУДИТОРІЯ: Права половина.

474
00:19:18,980 --> 00:19:19,900
>> DAVID мала: Сортувати праву половину.

475
00:19:19,900 --> 00:19:21,320
Таким чином, ви, хлопці, повинні зробити це, а також.

476
00:19:21,320 --> 00:19:23,510
Так що якщо ви могли встати
на мить?

477
00:19:23,510 --> 00:19:25,192
А як тебе звати?

478
00:19:25,192 --> 00:19:25,540
>> Джессі: Джесс.

479
00:19:25,540 --> 00:19:25,870
>> DAVID мала: Джесс.

480
00:19:25,870 --> 00:19:29,720
Отже, Джесс Тепер ліва
половину правої половини.

481
00:19:29,720 --> 00:19:31,400
І так вона список Розмір 1.

482
00:19:31,400 --> 00:19:32,380
Вона, очевидно, сортують.

483
00:19:32,380 --> 00:19:33,070
І ваше ім'я?

484
00:19:33,070 --> 00:19:33,630
>> МІШЕЛЬ: Мішель.

485
00:19:33,630 --> 00:19:35,340
>> DAVID мала: Мішель, очевидно,
Перелік розмір 1.

486
00:19:35,340 --> 00:19:36,050
Вона вже відсортований.

487
00:19:36,050 --> 00:19:38,690
Так що тепер відбувається чарівництво,
Процес злиття.

488
00:19:38,690 --> 00:19:39,790
Так що, хто збирається прийти?

489
00:19:39,790 --> 00:19:41,560
Очевидно Мішель.

490
00:19:41,560 --> 00:19:43,280
Так що, якщо ви могли б приходити назад.

491
00:19:43,280 --> 00:19:47,090
Просторі ми маємо в наявності для неї тепер
Прямо за це крісло тут.

492
00:19:47,090 --> 00:19:51,580
І тепер, якщо ви могли б повернутися, а також,
у нас тепер є, щоб бути ясним, два

493
00:19:51,580 --> 00:19:53,810
половин, кожна з розмір 2 -

494
00:19:53,810 --> 00:19:57,090
і просто заради зображенням учасника, якщо Ви
могли б зробити трохи простору -

495
00:19:57,090 --> 00:19:59,780
однією лівою половині, по одному
Права половина тут.

496
00:19:59,780 --> 00:20:01,160
>> Перемотка далі в історію.

497
00:20:01,160 --> 00:20:02,270
Який крок буде наступним?

498
00:20:02,270 --> 00:20:03,030
>> АУДИТОРІЯ: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID мала: Так що тепер у нас є для злиття.

500
00:20:04,160 --> 00:20:07,490
Так добре, так що тепер, на щастя, ми
просто звільнив чотирма стільцями.

501
00:20:07,490 --> 00:20:11,480
Таким чином, ми використовували два рази більше пам'яті, але
ми можемо дати фліп-флоп між

502
00:20:11,480 --> 00:20:12,330
два масиви.

503
00:20:12,330 --> 00:20:14,190
Так, число яких на першому місці?

504
00:20:14,190 --> 00:20:14,850
Так Мішель, це очевидно.

505
00:20:14,850 --> 00:20:16,680
Так приходять і беруть
ваше місце тут.

506
00:20:16,680 --> 00:20:19,120
А потім номер 2, очевидно,
Далі, так що ви прийшли сюди.

507
00:20:19,120 --> 00:20:21,520
Номер 4, номер 6.

508
00:20:21,520 --> 00:20:23,390
І знову, незважаючи на те, що є
трохи пішохідних прогулянок залученого,

509
00:20:23,390 --> 00:20:26,010
дійсно, це може відбутися миттєво,
шляхом переміщення одного -

510
00:20:26,010 --> 00:20:26,880
Добре, добре грав.

511
00:20:26,880 --> 00:20:28,350
>> [Сміється]

512
00:20:28,350 --> 00:20:29,680
>> DAVID мала: А тепер ми
в досить хорошій формі.

513
00:20:29,680 --> 00:20:34,910
Ліва половина всього
вхідного тепер сортуються.

514
00:20:34,910 --> 00:20:37,370
Гаразд, ці хлопці були
Перевага моєї -

515
00:20:37,370 --> 00:20:40,340
як вона в кінцевому підсумку всі дівчата на
наліво і всі хлопчики праворуч?

516
00:20:40,340 --> 00:20:42,450
>> Добре, таким чином хлопців чергу.

517
00:20:42,450 --> 00:20:44,680
Тому я не буду йти Ви через
ці кроки.

518
00:20:44,680 --> 00:20:46,550
Ми побачимо, якщо ми можемо повторно
ж псевдокод.

519
00:20:46,550 --> 00:20:50,050
Якщо ви хочете йти вперед і встати,
і ви, хлопці, дозвольте мені дати вам мікрофон.

520
00:20:50,050 --> 00:20:52,990
Дивіться, якщо ви не можете повторити те, що
ми тільки що зробили тут, на

521
00:20:52,990 --> 00:20:53,880
Інший кінець списку.

522
00:20:53,880 --> 00:20:59,530
Хто повинен говорити першим,
заснований на алгоритмі?

523
00:20:59,530 --> 00:21:03,210
То поясніть, що ви робите, перш
Ви робите будь нозі рухів.

524
00:21:03,210 --> 00:21:05,930
>> Виступаючий 1: Ну, добре, так як
Я лівої половини

525
00:21:05,930 --> 00:21:07,790
Ліва половина, я повернуся.

526
00:21:07,790 --> 00:21:08,730
Вірно?

527
00:21:08,730 --> 00:21:09,250
>> DAVID мала: Добре.

528
00:21:09,250 --> 00:21:10,350
>> Виступаючий 1: А потім -

529
00:21:10,350 --> 00:21:11,800
>> DAVID мала: хто
MIC перейти до наступного?

530
00:21:11,800 --> 00:21:12,920
>> Виступаючий 1: Наступний номер.

531
00:21:12,920 --> 00:21:14,720
>> Доповідач 2: Так що я права половина
лівої половини

532
00:21:14,720 --> 00:21:17,830
ліва половина, і я повернуся.

533
00:21:17,830 --> 00:21:18,050
>> DAVID мала: Добре.

534
00:21:18,050 --> 00:21:18,550
Ви повернетеся.

535
00:21:18,550 --> 00:21:21,855
Так що тепер який наступний за вами двома?

536
00:21:21,855 --> 00:21:23,740
>> Доповідач 2: Ми хочемо бачити, хто менше.

537
00:21:23,740 --> 00:21:24,200
>> DAVID мала: Абсолютно вірно.

538
00:21:24,200 --> 00:21:24,940
Ми хочемо об'єднати.

539
00:21:24,940 --> 00:21:27,590
Простір ми збираємося використовувати для злиття
Вас у, навіть якщо вони

540
00:21:27,590 --> 00:21:30,250
Очевидно, вже відсортовані, ми збираємося
піти по тому ж алгоритму.

541
00:21:30,250 --> 00:21:31,560
Так хто йде в спині в першу чергу?

542
00:21:31,560 --> 00:21:35,720
Таким 3, а потім 7.

543
00:21:35,720 --> 00:21:38,570
А тепер йде мікрофон
з цими хлопцями, добре?

544
00:21:38,570 --> 00:21:43,590
>> Виступаючий 3: Так що я праву половину
ліву половину, і мій N менше

545
00:21:43,590 --> 00:21:45,048
1, так що я просто хочу, щоб пройти -

546
00:21:45,048 --> 00:21:46,380
>> DAVID мала: Добре.

547
00:21:46,380 --> 00:21:49,450
>> Виступаючий 4: Я права половина
Права половина права половина, і я

548
00:21:49,450 --> 00:21:51,740
Також одна людина, так що я
збирається повернутися.

549
00:21:51,740 --> 00:21:52,990
Так що тепер ми зливаємося.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> Виступаючий 3: Отже, ми повертаємося.

552
00:21:56,150 --> 00:21:57,160
>> DAVID мала: Так ви йдете в задню частину.

553
00:21:57,160 --> 00:21:59,200
Так 5 йде в першу чергу, то 8.

554
00:21:59,200 --> 00:22:01,240
А тепер аудиторії, який є
кроку нам потрібно тепер перемотати

555
00:22:01,240 --> 00:22:02,200
повернутися до в нашій свідомості?

556
00:22:02,200 --> 00:22:02,940
>> АУДИТОРІЯ: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID мала: об'єднання лівої і правої половини
половину початкової ліву половину.

558
00:22:07,270 --> 00:22:08,840
Так що тепер -

559
00:22:08,840 --> 00:22:10,520
і просто, щоб було зрозуміліше,
зробити трохи простору

560
00:22:10,520 --> 00:22:11,690
між вами двома хлопцями.

561
00:22:11,690 --> 00:22:13,800
Так що тепер це два списки,
зліва і справа.

562
00:22:13,800 --> 00:22:18,320
Так як же нам тепер злиття, ви хлопці в
перший ряд місць знову?

563
00:22:18,320 --> 00:22:19,600
>> 3 йде в першу чергу.

564
00:22:19,600 --> 00:22:20,850
5 Тоді, очевидно.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Потім 7, і тепер 8.

567
00:22:27,330 --> 00:22:28,710
ОК, а тепер ми?

568
00:22:28,710 --> 00:22:29,650
>> АУДИТОРІЯ: не робиться.

569
00:22:29,650 --> 00:22:32,440
>> DAVID мала: Не за те, що
Очевидно, що тут один крок залишилося.

570
00:22:32,440 --> 00:22:35,720
Але, знову ж, причина я використовую це
жаргону, як "перемотування в своєму розумі,"

571
00:22:35,720 --> 00:22:37,160
це тому, що насправді
що відбувається.

572
00:22:37,160 --> 00:22:39,610
Ми проходимо через всі ці кроки,
але ми ж начебто зупиняючись на

573
00:22:39,610 --> 00:22:42,480
момент, дайвінг глибше в
Алгоритм, затримавшись на мить,

574
00:22:42,480 --> 00:22:45,840
занурюватися глибше і глибше в алгоритм, і
Тепер ми повинні розібратися перемотування в нашій

575
00:22:45,840 --> 00:22:49,430
уми і скасувати всі ці шари
що ми начебто припинене.

576
00:22:49,430 --> 00:22:51,790
>> Так що тепер у нас є два списки розміру 4.

577
00:22:51,790 --> 00:22:54,790
Якщо ви, хлопці, могли встати в останній раз
і зробити трохи місця тут, щоб

578
00:22:54,790 --> 00:22:57,230
дати зрозуміти, що це лівий
половину початкової,

579
00:22:57,230 --> 00:22:58,620
Права половина оригіналу.

580
00:22:58,620 --> 00:23:01,060
Хто першим номером, що ми
потрібно тягнути в спину?

581
00:23:01,060 --> 00:23:01,870
Мішель, звичайно.

582
00:23:01,870 --> 00:23:03,230
>> Так ми одягли Мішель тут.

583
00:23:03,230 --> 00:23:05,080
І хто має номер 2?

584
00:23:05,080 --> 00:23:06,440
Номер 2 приходить на спині, а також.

585
00:23:06,440 --> 00:23:07,800
Номер 3?

586
00:23:07,800 --> 00:23:08,510
Відмінно.

587
00:23:08,510 --> 00:23:16,570
Номер 4, № 5, № 6,
№ 7, і № 8.

588
00:23:16,570 --> 00:23:18,850
>> Добре, таким чином, було схоже на багато
кроків, це точно.

589
00:23:18,850 --> 00:23:22,390
Але тепер давайте подивимося, якщо ми не можемо підтвердити
роду інтуїтивно, що це

590
00:23:22,390 --> 00:23:26,190
Алгоритм принципово, зокрема,
N стає дійсно великим, як ми бачили

591
00:23:26,190 --> 00:23:29,170
з анімацією, є
принципово швидше.

592
00:23:29,170 --> 00:23:33,400
Тому я стверджую, цей алгоритм, в гіршому
випадок і навіть у кращому випадку,

593
00:23:33,400 --> 00:23:36,160
велика O п § п раз.

594
00:23:36,160 --> 00:23:39,160
Тобто, є деякі аспекти цього
алгоритм, який користується N кроків, але

595
00:23:39,160 --> 00:23:43,110
є ще один аспект десь в
що ітерації циклу, що, що

596
00:23:43,110 --> 00:23:44,410
бере журнал N кроків.

597
00:23:44,410 --> 00:23:49,154
Чи можемо ми вказати на те, що ці
два числа мають на увазі?

598
00:23:49,154 --> 00:23:51,320
Ну, і де -

599
00:23:51,320 --> 00:23:54,160
Де мікрофон йти?

600
00:23:54,160 --> 00:23:58,660
>> Виступаючий 1: Чи буде увійти п
порушення нас на дві частини -

601
00:23:58,660 --> 00:23:59,630
ділення на два, по суті.

602
00:23:59,630 --> 00:24:00,120
>> DAVID мала: Абсолютно вірно.

603
00:24:00,120 --> 00:24:03,000
Кожен раз, коли ми бачимо в будь-який алгоритм таким чином,
далеко, там був цей зразок

604
00:24:03,000 --> 00:24:04,200
поділ, ділення, ділення.

605
00:24:04,200 --> 00:24:05,700
І це зазвичай відновлюють
на те, що це

606
00:24:05,700 --> 00:24:07,100
логарифмічні, логарифм за основою 2.

607
00:24:07,100 --> 00:24:10,180
Але це дійсно може бути що завгодно,
але ввійти основою 2.

608
00:24:10,180 --> 00:24:11,330
>> Тепер те, що про росіян?

609
00:24:11,330 --> 00:24:14,550
Я бачу, що ми як би розділило вас
Хлопці - розділило вас, розділило вас,

610
00:24:14,550 --> 00:24:15,910
розділило вас, розділений вас.

611
00:24:15,910 --> 00:24:18,760
Де врешті-решт прийшли?

612
00:24:18,760 --> 00:24:19,810
>> Так що це злиття.

613
00:24:19,810 --> 00:24:20,610
Тому що думати про це.

614
00:24:20,610 --> 00:24:25,420
При об'єднанні вісім осіб разом,
за допомогою чого половина з них представляють собою набір з чотирьох

615
00:24:25,420 --> 00:24:27,770
і інша половина інший
набір з чотирьох, як ви йдете

616
00:24:27,770 --> 00:24:28,820
про виконання злиття?

617
00:24:28,820 --> 00:24:30,830
Ну, ви, хлопці, зробили це
досить інтуїтивно.

618
00:24:30,830 --> 00:24:34,140
>> Але якби я зробив це, а трохи більше
методично, я б вказав на

619
00:24:34,140 --> 00:24:38,090
лівий людина спочатку з моєю лівою
боку, вказав на крайню ліву людини

620
00:24:38,090 --> 00:24:42,080
що половина з своєю правою рукою, і
тільки згодом йшли через

621
00:24:42,080 --> 00:24:46,990
список, вказуючи на найменший елемент
кожен раз, рухаючи пальцем по і

622
00:24:46,990 --> 00:24:48,970
за які необхідні для створення списку.

623
00:24:48,970 --> 00:24:51,890
Але те, що про цю ключовою злиття
процес я порівнюю ці пари

624
00:24:51,890 --> 00:24:53,460
елементів.

625
00:24:53,460 --> 00:24:57,270
З правій половині і з лівого
половину, я ніколи не відступає один раз.

626
00:24:57,270 --> 00:25:00,570
>> Так злитися приймає
не більше N кроків.

627
00:25:00,570 --> 00:25:03,250
І скільки разів у мене є
зробити це злиття?

628
00:25:03,250 --> 00:25:07,150
Ну, не більше, ніж N, і ми просто
побачив, що з остаточним злиттям.

629
00:25:07,150 --> 00:25:13,120
І так, якщо ви робите те, що займає
увійти N п кроків рази, або навпаки,

630
00:25:13,120 --> 00:25:15,210
він збирається дати нам п раз журнал N.

631
00:25:15,210 --> 00:25:16,310
>> І чому це краще?

632
00:25:16,310 --> 00:25:19,600
Ну, якщо ми вже знаємо, що журнал
N краще, ніж N - чи не так?

633
00:25:19,600 --> 00:25:22,590
Ми бачили в бінарний пошук, телефонна книга
Наприклад, журнал N був безперечно

634
00:25:22,590 --> 00:25:23,760
краще, ніж лінійні.

635
00:25:23,760 --> 00:25:28,420
Значить, раз журнал N п
безперечно краще, ніж N раз інше

636
00:25:28,420 --> 00:25:30,390
N, N AKA квадраті.

637
00:25:30,390 --> 00:25:32,400
І це те, що ми в кінцевому підсумку відчувають.

638
00:25:32,400 --> 00:25:34,928
>> Настільки великі оплески, якщо
Ми могли б, цих хлопців.

639
00:25:34,928 --> 00:25:38,920
>> [Оплески]

640
00:25:38,920 --> 00:25:41,550
>> DAVID мала: І ваші подарунки Розставання -
Ви можете зберегти номери,

641
00:25:41,550 --> 00:25:44,010
Якщо ви хотіли б.

642
00:25:44,010 --> 00:25:45,620
І ваш прощальний подарунок, як звичайно.

643
00:25:45,620 --> 00:25:47,290
О, і ми надішлемо Вам
кадри, Мішель.

644
00:25:47,290 --> 00:25:48,343
Спасибо.

645
00:25:48,343 --> 00:25:49,250
Добре.

646
00:25:49,250 --> 00:25:50,400
Допомогти собі стрес м'яч.

647
00:25:50,400 --> 00:25:54,110
>> І дозвольте мені підтягнути, в той же час,
наш друг Роб Боуден запропонувати

648
00:25:54,110 --> 00:25:59,520
Дещо інший погляд на це,
так як ви можете думати про ці

649
00:25:59,520 --> 00:26:01,280
кроків відбувається в кілька
іншому.

650
00:26:01,280 --> 00:26:04,750
Насправді, установка за те, що Роб про
щоб показати нам, припускає, що ми

651
00:26:04,750 --> 00:26:09,030
вже зробили поділ
великий список на вісім невеликих списків,

652
00:26:09,030 --> 00:26:10,570
кожна розміром 1.

653
00:26:10,570 --> 00:26:13,350
>> Таким чином, ми міняємо псевдокод
трохи тільки до виду отримати в

654
00:26:13,350 --> 00:26:15,320
Основна ідея, як злиття робіт.

655
00:26:15,320 --> 00:26:17,600
Але час роботи, що
він збирається зробити, це як і раніше

656
00:26:17,600 --> 00:26:19,110
буде тим же самим.

657
00:26:19,110 --> 00:26:23,540
І знову, налаштування тут є те, що він
почалося з вісьмома списки розміру 1.

658
00:26:23,540 --> 00:26:27,730
Отже, ви пропустили частину, де він
насправді зробили журнал N, N журнал, журнал N

659
00:26:27,730 --> 00:26:31,205
поділ вхідного сигналу.

660
00:26:31,205 --> 00:26:32,120
>> [ВІДТВОРЕННЯ ВІДЕО]

661
00:26:32,120 --> 00:26:33,615
>> -Ось і все на першому кроці.

662
00:26:33,615 --> 00:26:38,270
Для другого кроку, неодноразово
об'єднує пару списків.

663
00:26:38,270 --> 00:26:39,210
>> DAVID мала: Хм.

664
00:26:39,210 --> 00:26:41,270
Тільки звук йде
з мого комп'ютера.

665
00:26:41,270 --> 00:26:42,520
Давайте спробуємо ще раз.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Просто довільно вибрати, який -
тепер у нас є чотири списку.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Дізнатися раніше.

670
00:26:52,120 --> 00:26:53,040
>> DAVID мала: Там ми йдемо.

671
00:26:53,040 --> 00:27:00,510
>> Злиття-108 і 15, ми врешті
з списку 15, 108.

672
00:27:00,510 --> 00:27:07,170
Злиття 50 і 4, ми
в кінцевому підсумку з 4, 50.

673
00:27:07,170 --> 00:27:12,990
Злиття 8 і 42, ми
в кінцевому підсумку з 8, 42.

674
00:27:12,990 --> 00:27:19,970
І злиття 23 і 16, ми
в кінцевому підсумку з 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Тепер всі наші списки розміру 2.

676
00:27:23,270 --> 00:27:26,690
Слід зазначити, що кожен з
чотири списки відсортовані.

677
00:27:26,690 --> 00:27:29,450
Так ми можемо почати злиття
пар списки.

678
00:27:29,450 --> 00:27:38,420
Злиття 15 і 108, 4 і 50, ми
спочатку взяти 4, то 15, то

679
00:27:38,420 --> 00:27:41,500
50, то 108.

680
00:27:41,500 --> 00:27:50,610
Злиття 8, 42 і 16, 23, ми спочатку
8, то 16, то 23,

681
00:27:50,610 --> 00:27:52,700
то 42.

682
00:27:52,700 --> 00:27:57,600
>> Так що тепер у нас є тільки два списки розмір
4, кожен з яких сортують.

683
00:27:57,600 --> 00:28:01,170
Так що тепер ми об'єднати ці два списки.

684
00:28:01,170 --> 00:28:11,835
По-перше, ми беремо 4, то візьмемо
8, то ми беремо 15, то 16, то

685
00:28:11,835 --> 00:28:19,456
23, то 42, то 50, то 108.

686
00:28:19,456 --> 00:28:19,872
>> [КІНЕЦЬ відеовідтворення]

687
00:28:19,872 --> 00:28:23,430
>> DAVID НЕ мала: Знову ж, зауважте, він ніколи
торкнувся даної чашки більше одного разу

688
00:28:23,430 --> 00:28:24,860
після зростання за його межами.

689
00:28:24,860 --> 00:28:26,200
Так він ніколи не повторюється.

690
00:28:26,200 --> 00:28:29,850
Значить, він завжди рухається в бік,
а от де ми отримали нашу н.

691
00:28:29,850 --> 00:28:33,290
>> Чому б не дозволити мені підтягнути одну анімацію
, Що ми бачили раніше, але на цей раз

692
00:28:33,290 --> 00:28:35,110
орієнтуючись тільки на сортування злиттям.

693
00:28:35,110 --> 00:28:38,030
Дозвольте мені йти вперед і збільшення
на це тут.

694
00:28:38,030 --> 00:28:42,530
Перш за все дозвольте мені вибрати випадковий введення,
збільшити це, і ви можете сортувати, см.

695
00:28:42,530 --> 00:28:46,600
те, що ми вважали само собою зрозумілим, раніше,
сортування злиттям насправді робить.

696
00:28:46,600 --> 00:28:50,330
>> Так помітите, що ви отримаєте ці половинки або
цих кварталів або ці восьмих

697
00:28:50,330 --> 00:28:53,140
проблема, яка раптом
почати приймати хорошій формі.

698
00:28:53,140 --> 00:28:57,070
І, нарешті, ви побачите в
У самому кінці, що БАМ,

699
00:28:57,070 --> 00:28:58,860
всі об'єднані разом.

700
00:28:58,860 --> 00:29:01,690
>> Так що це просто три різних
бере на себе ту ж ідею.

701
00:29:01,690 --> 00:29:05,980
Але ключове розуміння, як і розриву
і перемогти в першому класі,

702
00:29:05,980 --> 00:29:10,640
було те, що ми вирішили якось розділити
Проблема в щось більше, в

703
00:29:10,640 --> 00:29:14,760
щось на зразок ідентичні за духом,
але менше і менше

704
00:29:14,760 --> 00:29:15,660
і менше.

705
00:29:15,660 --> 00:29:18,420
>> Тепер інший цікавий спосіб сортувати думаю
про це, хоча це не

706
00:29:18,420 --> 00:29:20,520
збираюся дати вам те ж інтуїтивне
розумінні,

707
00:29:20,520 --> 00:29:21,640
Наступні анімації.

708
00:29:21,640 --> 00:29:25,400
Так що це відео хтось поклав разом
, Що пов'язано різних

709
00:29:25,400 --> 00:29:29,970
звуків з різних операцій для
сортування вставками, для сортування злиттям, і

710
00:29:29,970 --> 00:29:31,150
на пару інших.

711
00:29:31,150 --> 00:29:32,330
Таким чином, в даний момент, я вдарю Play.

712
00:29:32,330 --> 00:29:33,600
Це близько хвилини завдовжки.

713
00:29:33,600 --> 00:29:37,410
І навіть якщо ви все ще можете побачити
моделі відбувається, цей час ви можете

714
00:29:37,410 --> 00:29:41,420
також почути, як ці алгоритми
виконання по-різному і з

715
00:29:41,420 --> 00:29:43,950
кілька різних моделей.

716
00:29:43,950 --> 00:29:45,830
>> Це сортування вставками.

717
00:29:45,830 --> 00:29:50,400
>> [TONES композиція]

718
00:29:50,400 --> 00:29:52,400
>> DAVID мала: Це знову намагається
вставити кожен елемент

719
00:29:52,400 --> 00:29:52,900
в якій вона належить.

720
00:29:52,900 --> 00:29:54,628
Це бульбашкового сортування.

721
00:29:54,628 --> 00:30:10,097
>> [TONES композиція]

722
00:30:10,097 --> 00:30:13,630
>> DAVID мала: І ви можете сортувати, почуття
як відносно мало працювати, що він робить

723
00:30:13,630 --> 00:30:15,834
на кожному кроці.

724
00:30:15,834 --> 00:30:20,470
Це те, що звучить як занудство.

725
00:30:20,470 --> 00:30:21,472
>> [TONES композиція]

726
00:30:21,472 --> 00:30:25,222
>> DAVID мала: Це вибір роду,
де ми вибираємо елемент, який ми формуємо

727
00:30:25,222 --> 00:30:28,845
проходячи знову і знову і знову
і покласти його на самому початку.

728
00:30:28,845 --> 00:30:37,674
>> [TONES композиція]

729
00:30:37,674 --> 00:30:43,970
>> DAVID мала: Це сортування злиттям, яке
Ви можете дійсно починаєш відчувати.

730
00:30:43,970 --> 00:30:51,810
>> [TONES композиція]

731
00:30:51,810 --> 00:30:54,770
>> [Сміється]

732
00:30:54,770 --> 00:30:58,395
>> DAVID мала: Те, що називається GNOME
сортування, яку ми не дивилися.

733
00:30:58,395 --> 00:31:13,630
>> [TONES композиція]

734
00:31:13,630 --> 00:31:17,910
>> DAVID мала: Так покажіть, в даний час,
відволікатися, як ви, сподіваємося, по

735
00:31:17,910 --> 00:31:21,110
музику, якщо я можу ковзати трохи
трохи математики тут.

736
00:31:21,110 --> 00:31:24,850
Так що є і четвертий шлях, що ми можемо
думати про те, що це означає, що ці

737
00:31:24,850 --> 00:31:29,210
функцій, які будуть швидше, ніж ті,
що ми бачили раніше.

738
00:31:29,210 --> 00:31:32,470
І, якщо ви приїжджаєте на курс від
математика фоном, ви

739
00:31:32,470 --> 00:31:36,030
насправді може бути, вже знаєте, що ви
може ляпас строком на цій техніці -

740
00:31:36,030 --> 00:31:40,400
а саме рекурсію, функції
що так чи інакше викликає сам себе.

741
00:31:40,400 --> 00:31:44,780
>> І знову ж, нагадати, що сортування злиттям
псевдокод рекурсивної в тому сенсі,

742
00:31:44,780 --> 00:31:48,460
що один із кроків сортування злиттям у
було закликати роду -

743
00:31:48,460 --> 00:31:49,740
тобто безпосередньо.

744
00:31:49,740 --> 00:31:52,480
Але, на щастя, бо ми продовжували
виклику сортування або сортування злиттям,

745
00:31:52,480 --> 00:31:55,880
Зокрема, на менші і менші
і менше список, ми в кінцевому рахунку

746
00:31:55,880 --> 00:32:00,005
дна, завдяки чому ми будемо називати
базовий варіант, жорстко випадку,

747
00:32:00,005 --> 00:32:04,270
сказав, що якщо список невеликий, менше 2
У цьому випадку, просто негайно повернутися.

748
00:32:04,270 --> 00:32:07,550
Якщо у нас не було, що особливий випадок,
Алгоритм ніколи не буде нижньої межі,

749
00:32:07,550 --> 00:32:11,010
і ви б дійсно потрапити в
нескінченний цикл дійсно назавжди.

750
00:32:11,010 --> 00:32:14,330
>> Але припустимо, що ми хотіли зараз поставлю
деякі номери на цьому, знову ж таки, з використанням н

751
00:32:14,330 --> 00:32:15,660
як розмір вхідних даних.

752
00:32:15,660 --> 00:32:18,680
І я хотів би запитати вас, що
загальний час, що витрачається на

753
00:32:18,680 --> 00:32:19,800
працює сортування злиттям?

754
00:32:19,800 --> 00:32:22,960
Або більш загальному сенсі, що
вартість його в часі?

755
00:32:22,960 --> 00:32:24,730
>> Ну, це досить легко виміряти це.

756
00:32:24,730 --> 00:32:29,010
Якщо N менше 2, час, що витрачається
У сортування N елементів,

757
00:32:29,010 --> 00:32:30,480
де п дорівнює 2, 0.

758
00:32:30,480 --> 00:32:31,410
Тому що ми просто повертаємо.

759
00:32:31,410 --> 00:32:32,510
Там немає роботи, яку належить зробити.

760
00:32:32,510 --> 00:32:35,660
Тепер, можливо, може бути, це один крок чи два
кроки, щоб з'ясувати кількість

761
00:32:35,660 --> 00:32:38,420
працювати, але це досить близько до 0, що
Я просто хочу сказати, немає роботи

762
00:32:38,420 --> 00:32:40,940
вимагається, якщо список настільки мала
бути нецікавим.

763
00:32:40,940 --> 00:32:42,580
>> Але цей випадок цікавий.

764
00:32:42,580 --> 00:32:47,320
Рекурсивні випадок був філія
псевдокод, сказав ще, отсортируйте

765
00:32:47,320 --> 00:32:52,000
ліва половина, сортувати право
половину, об'єднати дві половини.

766
00:32:52,000 --> 00:32:55,530
Тепер чому це вираз
заявляєте, що рахунок?

767
00:32:55,530 --> 00:32:58,690
Ну, T п просто означає, що
час, щоб розібратися N елементів.

768
00:32:58,690 --> 00:33:03,070
А потім на правій стороні
Знак рівності там, T п розділений

769
00:33:03,070 --> 00:33:06,600
2 Мається на увазі вартість того, що?

770
00:33:06,600 --> 00:33:07,570
Сортування ліву половину.

771
00:33:07,570 --> 00:33:10,990
Інший T п поділене на 2
імовірно з посиланням на вартість

772
00:33:10,990 --> 00:33:12,390
сортувати праву половину.

773
00:33:12,390 --> 00:33:14,590
>> І тоді N Plus?

774
00:33:14,590 --> 00:33:15,420
Це злиття.

775
00:33:15,420 --> 00:33:19,120
Тому що, якщо у вас є два списки, один з
Розмір п над 2 і іншим розміром N

776
00:33:19,120 --> 00:33:22,580
більше 2, ви повинні торкнутися по суті
кожного з цих елементів, як і Роб

777
00:33:22,580 --> 00:33:24,990
торкнулася кожної з чашок, і тільки
як вказувалося в кожному з

778
00:33:24,990 --> 00:33:26,310
добровольців на сцені.

779
00:33:26,310 --> 00:33:28,790
Так п за рахунок злиття.

780
00:33:28,790 --> 00:33:31,780
>> Зараз, на жаль, ця формула
Також сама рекурсивної.

781
00:33:31,780 --> 00:33:36,390
Таким чином, якщо задано питання, якщо п, скажімо,
16, якщо є 16 осіб на сцені

782
00:33:36,390 --> 00:33:40,670
або 16 чашок на відео, скільки всього
кроки потрібно для того, щоб впорядкувати їх

783
00:33:40,670 --> 00:33:41,550
з сортування злиттям?

784
00:33:41,550 --> 00:33:45,790
Це насправді не очевидну відповідь,
тому що тепер у вас є до виду

785
00:33:45,790 --> 00:33:48,500
рекурсивно відповісти на це формулою.

786
00:33:48,500 --> 00:33:51,190
>> Але це нормально, тому що то дозвольте мені висунути
що ми робимо наступне.

787
00:33:51,190 --> 00:33:56,670
Часу, необхідного для сортування або 16 осіб
16 чашок, які будуть представлені

788
00:33:56,670 --> 00:33:58,020
взагалі як Т 16.

789
00:33:58,020 --> 00:34:01,400
Але, рівний, за нашими
попередній формулі, 2 рази кількість

790
00:34:01,400 --> 00:34:04,780
Час, необхідний для сортування
8 чашок плюс 16.

791
00:34:04,780 --> 00:34:08,590
І знову ж, плюс 16 самий час об'єднуватися,
і два рази Т 8

792
00:34:08,590 --> 00:34:10,790
час, щоб розібратися ліва половина і права половина.

793
00:34:10,790 --> 00:34:11,989
>> Але знову ж, цього недостатньо.

794
00:34:11,989 --> 00:34:13,210
Ми повинні зануритися в більш глибоких.

795
00:34:13,210 --> 00:34:16,409
Це означає, що ми повинні відповісти
питання, що таке Т 8?

796
00:34:16,409 --> 00:34:19,610
Ну Т 8 знаходиться всього в 2
раз T 4 плюс 8.

797
00:34:19,610 --> 00:34:20,520
Ну, що Т 4?

798
00:34:20,520 --> 00:34:23,780
Т 4 знаходиться всього в 2 рази Т 2 плюс 4.

799
00:34:23,780 --> 00:34:25,489
Ну, що Т 2?

800
00:34:25,489 --> 00:34:29,030
Т 2 знаходиться всього в 2 рази Т 1 плюс 2.

801
00:34:29,030 --> 00:34:31,940
>> І знову ж, ми начебто отримання
застряг в цьому циклі.

802
00:34:31,940 --> 00:34:34,790
Але мова йде про вдарити, що
так званий базовий варіант.

803
00:34:34,790 --> 00:34:37,310
Тому що те, Т 1, хіба ми стверджуємо?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Так що тепер, нарешті, ми можемо працювати у зворотному напрямку.

806
00:34:39,730 --> 00:34:44,290
>> Якщо Т 1 0, тепер я можу повернутися до одного
лінії Ось цей хлопець, і я можу

807
00:34:44,290 --> 00:34:46,330
підключіть 0 для T 1.

808
00:34:46,330 --> 00:34:51,770
Значить, вона дорівнює нулю 2 рази,
інакше відомий як 0, а також 2.

809
00:34:51,770 --> 00:34:53,739
І так, щоб всі вираз 2.

810
00:34:53,739 --> 00:34:58,740
>> Тепер, якщо я беру Т 2, відповідь на
2, підключити його до середньої лінії, T

811
00:34:58,740 --> 00:35:02,740
4, то це дає мені 2 рази
2 плюс 4, тому 8.

812
00:35:02,740 --> 00:35:07,080
Якщо я після цього підключити 8 до попереднього
лінії, що дає мені 2 рази 8, 16.

813
00:35:07,080 --> 00:35:12,470
І якщо ми будемо продовжувати те, що з
24, додавши в 16, ми, нарешті, отримати

814
00:35:12,470 --> 00:35:13,820
значення 64.

815
00:35:13,820 --> 00:35:18,480
>> Тепер, коли саме по собі говорить роду
Нічого позначення N,

816
00:35:18,480 --> 00:35:20,700
Big O, омега, які ми
говорили.

817
00:35:20,700 --> 00:35:24,890
Але виявляється, що насправді 64
16, розмір вхідного

818
00:35:24,890 --> 00:35:27,110
логарифм за основою 2 з 16.

819
00:35:27,110 --> 00:35:30,200
І якщо це трохи незнайомим, просто
згадую, і повернуся

820
00:35:30,200 --> 00:35:30,700
Вам зрештою.

821
00:35:30,700 --> 00:35:33,775
Якщо це логарифм за основою 2, це як 2
зведене в те, що дає вам 16?

822
00:35:33,775 --> 00:35:36,380
О, це 4, так що це 16 разів 4.

823
00:35:36,380 --> 00:35:39,380
>> І знову ж, це не має великого значення, якщо це
є свого роду туманний пам'яті зараз.

824
00:35:39,380 --> 00:35:43,720
Але зараз, приймати на віру
що 16 журнал 16 одно 64.

825
00:35:43,720 --> 00:35:46,590
І так дійсно, за допомогою цього простого розсудливості
перевірити, ми підтвердили -

826
00:35:46,590 --> 00:35:48,250
але формально не доведена -

827
00:35:48,250 --> 00:35:52,800
що час злиття
Сортувати дійсно N N увійти.

828
00:35:52,800 --> 00:35:53,790
>> Так не погано.

829
00:35:53,790 --> 00:35:57,260
Це безперечно краще, ніж
алгоритми, які ми бачили дотепер, і

830
00:35:57,260 --> 00:36:00,710
це тому, що ми використовувала, один,
методику, яка називається рекурсією.

831
00:36:00,710 --> 00:36:03,880
Але що ще більш цікаво, ніж та, що
Поняття поділу і завоювання.

832
00:36:03,880 --> 00:36:07,460
Знову ж, по-справжньому тиждень 0 речі, які
навіть зараз повторюється в

833
00:36:07,460 --> 00:36:08,740
більш переконливим способом.

834
00:36:08,740 --> 00:36:11,750
>> Тепер задоволення мало вправ, якщо у Вас є
ніколи не робив цього, - і ви, ймовірно,

835
00:36:11,750 --> 00:36:14,660
не буде, так як вид нормального
люди не думають, щоб зробити це.

836
00:36:14,660 --> 00:36:20,650
Але якщо я йду на google.com і якщо
Я хочу дізнатися що-небудь про

837
00:36:20,650 --> 00:36:22,356
рекурсію, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Сміється]

840
00:36:29,058 --> 00:36:32,030
[Сміх]

841
00:36:32,030 --> 00:36:33,385
DAVID мала: поганий жарт поступово поширюється.

842
00:36:33,385 --> 00:36:34,450
[Сміється]

843
00:36:34,450 --> 00:36:36,970
DAVID мала: Про всяк випадок, що вона є.

844
00:36:36,970 --> 00:36:38,710
Я не записати це неправильно,
і є жарт.

845
00:36:38,710 --> 00:36:40,810
Добре.

846
00:36:40,810 --> 00:36:42,950
Поясніть це люди поруч з вами, якщо
Це не зовсім натиснута тільки поки.

847
00:36:42,950 --> 00:36:47,650
Але рекурсії, в цілому, відноситься
в процесі виклику функції

848
00:36:47,650 --> 00:36:51,430
собі, або в більш загальному, розділивши
Проблема в те, що може бути

849
00:36:51,430 --> 00:36:56,220
вирішити по частинах рішення ідентичних
Представник проблем.

850
00:36:56,220 --> 00:36:58,400
>> Ну, давайте передач зміни
на мить.

851
00:36:58,400 --> 00:37:00,840
Ми б закінчити на певних кульмінацій,
так що давайте почнемо встановлювати

852
00:37:00,840 --> 00:37:05,870
етап, протягом декількох хвилин
на дуже простій ідеї -

853
00:37:05,870 --> 00:37:07,620
перекачування, що два елементи, чи не так?

854
00:37:07,620 --> 00:37:10,040
Всі ці алгоритми ми були
Говорячи про останні декілька

855
00:37:10,040 --> 00:37:12,420
Лекції включають деякі
роду заміни.

856
00:37:12,420 --> 00:37:14,630
Сьогодні було візуалізували їх отримання
вгору зі свого стільця і

857
00:37:14,630 --> 00:37:18,570
ходять, але в коді, ми б
просто взяти елемент з одного масиву

858
00:37:18,570 --> 00:37:20,370
і вставити його в інший.

859
00:37:20,370 --> 00:37:21,880
>> Так як же нам йти про це?

860
00:37:21,880 --> 00:37:24,850
Ну, дозвольте мені йти вперед і написати
швидкий програму тут.

861
00:37:24,850 --> 00:37:31,600
Я збираюся йти вперед і робити
це як таке.

862
00:37:31,600 --> 00:37:33,910
Давайте назвемо це -

863
00:37:33,910 --> 00:37:38,070
Чого ми хочемо назвати це одна?

864
00:37:38,070 --> 00:37:38,650
>> Взагалі-то, немає.

865
00:37:38,650 --> 00:37:39,420
Дозвольте мені перемотування назад.

866
00:37:39,420 --> 00:37:41,220
Я не хочу, щоб зробити це
ще захоплюючим.

867
00:37:41,220 --> 00:37:42,270
Це зіпсує задоволення.

868
00:37:42,270 --> 00:37:43,600
Давайте зробимо це замість цього.

869
00:37:43,600 --> 00:37:47,430
>> Припустимо, що я хочу написати трохи
програма і що в даний час використовує цю

870
00:37:47,430 --> 00:37:48,700
Ідея рекурсії.

871
00:37:48,700 --> 00:37:50,370
Я б отримав попереду себе там.

872
00:37:50,370 --> 00:37:51,420
Я збираюся зробити наступне.

873
00:37:51,420 --> 00:38:00,220
>> По-перше, швидко включати стандартні io.h,
а також включати в себе, cs50.h.

874
00:38:00,220 --> 00:38:03,200
А потім я збираюся йти вперед
і оголосити недійсним тап_п

875
00:38:03,200 --> 00:38:04,360
у звичайному порядку.

876
00:38:04,360 --> 00:38:07,920
Я зрозумів, я невірно названі файл, так що
дозвольте мені додати. C розширенням ось так

877
00:38:07,920 --> 00:38:09,510
що ми можемо скомпілювати його належним чином.

878
00:38:09,510 --> 00:38:10,970
Почати цю функцію.

879
00:38:10,970 --> 00:38:13,290
>> А функція Я хочу написати, досить
Простіше кажучи, це той, який запитує

880
00:38:13,290 --> 00:38:16,210
користувача число, а потім складає
всі числа між цим

881
00:38:16,210 --> 00:38:19,920
числа і, скажімо, 0.

882
00:38:19,920 --> 00:38:22,510
Отже, спочатку я збираюся йти вперед
і оголосити Int N.

883
00:38:22,510 --> 00:38:24,760
Потім я копіюю код, який
ми використовували на деякий час.

884
00:38:24,760 --> 00:38:26,660
Хоча дещо вірно.

885
00:38:26,660 --> 00:38:28,000
Я повернуся до цього трохи пізніше.

886
00:38:28,000 --> 00:38:29,010
>> Що я хочу зробити?

887
00:38:29,010 --> 00:38:33,460
Я хочу сказати, Е позитивної
ціле будь ласка.

888
00:38:33,460 --> 00:38:36,130
А потім я збираюся
кажуть N отримує отримати Int.

889
00:38:36,130 --> 00:38:38,800
Отже, ще раз, деякі шаблонний код
що ми використовували раніше.

890
00:38:38,800 --> 00:38:40,810
І я збираюся це зробити
а п менше 1.

891
00:38:40,810 --> 00:38:44,120
Так що це буде гарантувати, що користувач
дає мені позитивне ціле число.

892
00:38:44,120 --> 00:38:45,490
>> А тепер я збираюся зробити наступне.

893
00:38:45,490 --> 00:38:51,020
Я хочу скласти всі числа
від 1 і N, або від 0 до N,

894
00:38:51,020 --> 00:38:52,570
те ж саме, щоб отримати загальну суму.

895
00:38:52,570 --> 00:38:55,100
Так що найбільший символ Sigma
що ви могли б згадати.

896
00:38:55,100 --> 00:38:59,050
Так що я збираюся зробити це, першого скликання
функція під назвою Sigma,

897
00:38:59,050 --> 00:39:06,030
передаючи його по-російськи, а потім я збираюся
Е сказати, відповідь тут же.

898
00:39:06,030 --> 00:39:08,180
>> Коротше кажучи, я отримую і
Int від користувача.

899
00:39:08,180 --> 00:39:09,280
Я можу гарантувати, що це позитивно.

900
00:39:09,280 --> 00:39:12,700
Я оголошую змінну відповідь
цілого типу і зберігати в його повернення

901
00:39:12,700 --> 00:39:15,610
Значення сигма, передаючи N якості вхідних даних.

902
00:39:15,610 --> 00:39:17,060
І тоді я роздрукувати, що відповісти.

903
00:39:17,060 --> 00:39:19,550
>> На жаль, хоча сигма звучить
як щось, що може бути в

904
00:39:19,550 --> 00:39:24,040
math.h файлу, його декларації,
це насправді немає.

905
00:39:24,040 --> 00:39:24,690
Так що це нормально.

906
00:39:24,690 --> 00:39:26,170
Можна реалізувати це сам.

907
00:39:26,170 --> 00:39:29,160
Я збираюся реалізувати функцію називають
Sigma, і він збирається взяти

908
00:39:29,160 --> 00:39:29,900
параметра -

909
00:39:29,900 --> 00:39:32,100
Давайте просто називати це м, всього
так все по-іншому.

910
00:39:32,100 --> 00:39:35,910
А потім тут, я збираюся сказати,
Ну, якщо м менше 1 - це

911
00:39:35,910 --> 00:39:38,180
дуже нецікаві програми.

912
00:39:38,180 --> 00:39:41,700
Так що я збираюся йти вперед і
негайно повернути 0.

913
00:39:41,700 --> 00:39:45,920
Це просто не має сенсу скласти всі
числа від 1 м, якщо м

914
00:39:45,920 --> 00:39:48,470
саме 0 або негативним.

915
00:39:48,470 --> 00:39:50,900
>> А потім я збираюся йти вперед
і робити це дуже итеративно.

916
00:39:50,900 --> 00:39:53,090
Я збираюся робити такого роду старої школи,
і я збираюся йти вперед

917
00:39:53,090 --> 00:39:57,150
і сказати, що я збираюся
оголосити суму рівним 0.

918
00:39:57,150 --> 00:39:59,630
Тоді я буду мати
для петлі Int -

919
00:39:59,630 --> 00:40:02,820
і дозвольте мені зробити це у відповідності з нашими
Розподіл коду, тому у вас є копія

920
00:40:02,820 --> 00:40:07,500
будинку. INT I отримує 1 на до
я менше або дорівнює м.

921
00:40:07,500 --> 00:40:09,430
Я плюс плюс.

922
00:40:09,430 --> 00:40:11,430
І тоді всередині цього циклу -

923
00:40:11,430 --> 00:40:12,440
ми майже на місці -

924
00:40:12,440 --> 00:40:15,810
сума потрапляє сума плюс 1.

925
00:40:15,810 --> 00:40:17,670
А потім я збираюся повернути суму.

926
00:40:17,670 --> 00:40:19,420
>> Так що я зробив це швидко,
зовсім правда.

927
00:40:19,420 --> 00:40:22,775
Але, знову ж, основна функція досить
просто на основі коду, який ми

928
00:40:22,775 --> 00:40:23,190
написано до цих пір.

929
00:40:23,190 --> 00:40:25,610
Використовує подвійну петлю, щоб отримати позитивний
Int від користувача.

930
00:40:25,610 --> 00:40:29,870
Я потім передати десяткового до нової функції
називається сигма, назвавши його, знову ж таки, з.

931
00:40:29,870 --> 00:40:33,100
І я зберігання значення, що повертається, відповідь
від чорного ящика даний час

932
00:40:33,100 --> 00:40:35,460
відомий як сигма, в змінну
називають відповіддю.

933
00:40:35,460 --> 00:40:36,580
Тоді я роздрукувати його.

934
00:40:36,580 --> 00:40:39,090
>> Якщо ми тепер продовжимо розповідь,
яким сигма реалізовані?

935
00:40:39,090 --> 00:40:40,840
Я пропоную реалізувати наступним чином.

936
00:40:40,840 --> 00:40:43,560
По-перше, трохи перевірки помилок
щоб переконатися, що користувач не

937
00:40:43,560 --> 00:40:46,480
возитися зі мною і передавши
деякі негативні або значення 0.

938
00:40:46,480 --> 00:40:49,710
Тоді я оголошую змінну
суму і встановити його в 0.

939
00:40:49,710 --> 00:40:55,910
>> І тепер я починаю переходити від Я одно
1 все, аж до і включаючи м,

940
00:40:55,910 --> 00:41:00,130
тому що я хочу, щоб включити всі
числа від одного до М включно.

941
00:41:00,130 --> 00:41:04,350
А всередині цього циклу, я просто
Сума отримує те, що він є зараз, плюс

942
00:41:04,350 --> 00:41:08,900
Значення я.

943
00:41:08,900 --> 00:41:10,370
Крім того значення я.

944
00:41:10,370 --> 00:41:14,090
>> Як осторонь, якщо ви не бачили цього
і колись, є деякі синтаксичний цукор

945
00:41:14,090 --> 00:41:14,870
для цієї лінії.

946
00:41:14,870 --> 00:41:21,120
Я можу переписати це як плюс Я одно,
просто щоб врятувати себе кілька натискань клавіш

947
00:41:21,120 --> 00:41:22,570
і виглядати трохи прохолодніше.

948
00:41:22,570 --> 00:41:23,140
Але от і все.

949
00:41:23,140 --> 00:41:24,660
Це функціонально те ж саме.

950
00:41:24,660 --> 00:41:26,710
>> На жаль, ця коду
Чи не збираєтеся компілювати ще.

951
00:41:26,710 --> 00:41:31,600
Якщо я запускаю зробити сигма 0, як же я
Я збираюся отримати кричав на?

952
00:41:31,600 --> 00:41:33,473
Як це буде, не подобається?

953
00:41:33,473 --> 00:41:35,740
>> АУДИТОРІЯ: [нерозбірливо].

954
00:41:35,740 --> 00:41:37,800
>> DAVID мала: Так, я не оголошував
Функція нагорі, чи не так?

955
00:41:37,800 --> 00:41:40,590
C почасти нерозумно, тим, що він тільки
робить те, що ви скажете їй зробити, і ви

956
00:41:40,590 --> 00:41:41,880
повинні зробити це в такому порядку.

957
00:41:41,880 --> 00:41:45,910
І тому, якщо я вдарив Введіть тут, я збираюся
отримати попередження про Sigma неявній

958
00:41:45,910 --> 00:41:46,860
декларації.

959
00:41:46,860 --> 00:41:48,120
>> О, не проблема.

960
00:41:48,120 --> 00:41:50,370
Я можу піднятися на самий верх, і я можу
кажуть, все в порядку, почекай хвилинку.

961
00:41:50,370 --> 00:41:54,240
Sigma є функцією, яка повертає
Цілочисельне і він очікує

962
00:41:54,240 --> 00:41:56,620
ІНТАС входу, крапка з комою.

963
00:41:56,620 --> 00:41:59,550
Або я міг би поставити весь функції
над головною, але в цілому, я б

964
00:41:59,550 --> 00:42:02,260
рекомендую проти цього, тому що це
добре, щоб завжди мати основні нагорі, таким чином

965
00:42:02,260 --> 00:42:06,310
Ви зможете зануритися в них і знаю, що
Програма робить, читаючи основні першим.

966
00:42:06,310 --> 00:42:07,930
>> Так що тепер дозвольте мені очистити екран.

967
00:42:07,930 --> 00:42:09,330
Рімейк сигма 0.

968
00:42:09,330 --> 00:42:10,340
Все, здається, щоб перевірити.

969
00:42:10,340 --> 00:42:11,970
Дозвольте мені запустити сигма 0.

970
00:42:11,970 --> 00:42:12,770
Позитивне в тому.

971
00:42:12,770 --> 00:42:15,580
Я дам йому кількість
3 зберегти його простим.

972
00:42:15,580 --> 00:42:18,710
Отже, що повинен дати мені 3
плюс два плюс один, так 6.

973
00:42:18,710 --> 00:42:20,750
Введіть, та й взагалі я отримую 6.

974
00:42:20,750 --> 00:42:21,820
>> Я можу зробити щось більше -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Так само, як дотичній, я збираюся зробити
щось смішне, як дійсно великий

977
00:42:27,690 --> 00:42:30,375
число, О, це фактично вдалося -

978
00:42:30,375 --> 00:42:31,600
Ех, я не думаю, що це правильно.

979
00:42:31,600 --> 00:42:32,810
Давайте подивимося.

980
00:42:32,810 --> 00:42:34,060
Давайте вже возитися з ним.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Це проблема.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Що відбувається?

985
00:42:44,970 --> 00:42:46,050
Коду не так уже й погано.

986
00:42:46,050 --> 00:42:48,470
Він як і раніше лінійно.

987
00:42:48,470 --> 00:42:50,810
Свист є хорошим ефектом, однак.

988
00:42:50,810 --> 00:42:52,060
Що відбувається?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Не впевнений, що я почув його.

991
00:42:55,620 --> 00:42:57,620
Ось і виходить, - і
це як в сторону.

992
00:42:57,620 --> 00:42:59,400
Це не сердечника
Ідея рекурсії.

993
00:42:59,400 --> 00:43:02,480
Виявляється, тому, що я намагаюся
представляють таку велику кількість, більшість

994
00:43:02,480 --> 00:43:06,980
ймовірно, це неправильної інтерпретації
на С, не позитивне число,

995
00:43:06,980 --> 00:43:09,980
але негативне число.

996
00:43:09,980 --> 00:43:12,690
>> Ми не говорили про це, але це
Виявляється, є негативні числа

997
00:43:12,690 --> 00:43:14,210
у світі на додаток
на позитивні числа.

998
00:43:14,210 --> 00:43:16,290
І кошти, за допомогою яких ви можете
являють собою негативне число

999
00:43:16,290 --> 00:43:19,530
по суті є, використовується один
спеціальний біт, щоб вказати,

1000
00:43:19,530 --> 00:43:20,400
позитивні над негативними.

1001
00:43:20,400 --> 00:43:22,950
Це трохи складніше, ніж,
але це основна ідея.

1002
00:43:22,950 --> 00:43:26,740
>> Тому, на жаль, тоді, коли З заплутаною один
з тих бітів, насправді це означає,

1003
00:43:26,740 --> 00:43:30,790
о, це негативне число, мій цикл
Тут, наприклад, немає фактично ніколи

1004
00:43:30,790 --> 00:43:31,740
збирається припинити.

1005
00:43:31,740 --> 00:43:33,850
Так що якщо я насправді були надрукувавши небудь
знову і знову, ми,

1006
00:43:33,850 --> 00:43:34,650
см. багато.

1007
00:43:34,650 --> 00:43:36,220
Але знову ж, це, крім точки.

1008
00:43:36,220 --> 00:43:38,590
Це дійсно так, начебто
інтелектуальне цікавість, що ми приїдемо

1009
00:43:38,590 --> 00:43:39,550
повернутися до зрештою.

1010
00:43:39,550 --> 00:43:43,400
Але зараз, це правильне
реалізацію, якщо ми припускаємо, що

1011
00:43:43,400 --> 00:43:45,970
Користувач забезпечить цілих
, Які вписуються в цілі.

1012
00:43:45,970 --> 00:43:49,370
>> Але я стверджую, що цей код, чесно кажучи,
можна було б зробити набагато більше, просто.

1013
00:43:49,370 --> 00:43:54,060
Якщо мета під рукою прийняти ряд
м, як і складіть всі

1014
00:43:54,060 --> 00:43:59,510
номери між ним і один або, навпаки
між 1 і це, я стверджую,

1015
00:43:59,510 --> 00:44:03,380
що я можу зайняти цю ідею, які зливаються
Сортувати мав, який брав проблеми

1016
00:44:03,380 --> 00:44:05,660
такого розміру і розділивши її
в щось менше.

1017
00:44:05,660 --> 00:44:09,875
Може бути, не половина, але менше, але
представницьки те ж саме.

1018
00:44:09,875 --> 00:44:12,130
Та ж сама ідея, але менші проблеми.

1019
00:44:12,130 --> 00:44:15,470
>> Так що я насправді - дозвольте мені зберегти цей файл
з іншого номер версії.

1020
00:44:15,470 --> 00:44:17,670
Ми назвемо цю версію
1 замість 0.

1021
00:44:17,670 --> 00:44:20,790
І я стверджую, що я можу реально
перевизначити цю в такого роду

1022
00:44:20,790 --> 00:44:22,160
галюциногенний шляху.

1023
00:44:22,160 --> 00:44:23,710
>> Я збираюся залишити частину його в спокої.

1024
00:44:23,710 --> 00:44:27,710
Я збирався сказати, якщо т менше
ніж або дорівнює 0 -

1025
00:44:27,710 --> 00:44:29,280
Я просто хочу бути трохи
Ще Анальний цей раз

1026
00:44:29,280 --> 00:44:30,520
з моєю перевірки помилок -

1027
00:44:30,520 --> 00:44:33,190
Я збираюся йти вперед і повертає 0.

1028
00:44:33,190 --> 00:44:34,490
Це довільне.

1029
00:44:34,490 --> 00:44:37,500
Я просто Просто вирішити, якщо користувач
дає мені негативним числом, я

1030
00:44:37,500 --> 00:44:41,490
повертаємо 0, і вони повинні були прочитати
документації більш уважно.

1031
00:44:41,490 --> 00:44:42,170
>> Решта -

1032
00:44:42,170 --> 00:44:44,070
помітити, що я збираюся робити.

1033
00:44:44,070 --> 00:44:49,260
Останнє я збираюся повернутися м плюс -

1034
00:44:49,260 --> 00:44:51,010
що сигма-му?

1035
00:44:51,010 --> 00:44:56,710
Ну, сигма-м плюс мінус 1 м,
м плюс мінус 2, плюс мінус 3 м.

1036
00:44:56,710 --> 00:44:58,030
Я не хочу писати все це.

1037
00:44:58,030 --> 00:44:59,120
Чому б мені просто не плоскодонки?

1038
00:44:59,120 --> 00:45:05,080
Рекурсивний називаю себе зі злегка
менша проблема, крапку з комою

1039
00:45:05,080 --> 00:45:06,840
і назвіть його день?

1040
00:45:06,840 --> 00:45:07,040
>> Вірно?

1041
00:45:07,040 --> 00:45:10,980
Тепер і тут, ви можете відчути або турбуватися
що це нескінченний цикл, який я

1042
00:45:10,980 --> 00:45:15,450
викликають, в результаті чого я реалізую
Sigma Sigma по телефону.

1043
00:45:15,450 --> 00:45:20,342
Але це абсолютно нормально, тому що я
думав, попереду якої додані лінії?

1044
00:45:20,342 --> 00:45:22,600
>> АУДИТОРІЯ: [нерозбірливо].

1045
00:45:22,600 --> 00:45:25,430
>> Девід мала: від 23 до 26, які
Якщо мій стан.

1046
00:45:25,430 --> 00:45:28,390
Тому що приємно про
віднімання тут, тому що я тримаю

1047
00:45:28,390 --> 00:45:31,180
вручати сигма менше проблем менше
проблеми, менше - це не

1048
00:45:31,180 --> 00:45:31,870
в два рази менше.

1049
00:45:31,870 --> 00:45:34,380
Це всього лише крок дитини менше,
але це нормально.

1050
00:45:34,380 --> 00:45:38,050
Тому що в кінцевому підсумку, ми будемо працювати
наш шлях вниз до 1 або 0.

1051
00:45:38,050 --> 00:45:41,630
І як тільки ми вразили 0, Sigma НЕ
збираюся називати себе більше.

1052
00:45:41,630 --> 00:45:43,590
Це збирається негайно повернути 0.

1053
00:45:43,590 --> 00:45:47,960
>> Таким чином, ефект, якщо ви роду Вітер цьому
в своєму розумі, є додавання м плюс

1054
00:45:47,960 --> 00:45:52,740
м мінус 1, плюс мінус 2 м, м плюс мінус
3, а також точка, точка, точка, М мінус

1055
00:45:52,740 --> 00:45:57,820
м, в кінцевому підсумку дає вам 0, а
ефект в кінцевому рахунку, щоб додати всі

1056
00:45:57,820 --> 00:45:59,070
ці речі разом.

1057
00:45:59,070 --> 00:46:02,380
Так що ми не маємо з рекурсією,
вирішена проблема, яку ми

1058
00:46:02,380 --> 00:46:03,470
не могли вирішити раніше.

1059
00:46:03,470 --> 00:46:06,840
Дійсно, версія 0 про це, і кожен
Проблема на сьогоднішній день, були вирішувані

1060
00:46:06,840 --> 00:46:09,980
тільки з використанням для петлі або в той час як
петлі або аналогічних конструкцій.

1061
00:46:09,980 --> 00:46:13,150
>> Але рекурсію, я вважаю, дає нам
інший спосіб мислення про

1062
00:46:13,150 --> 00:46:17,010
проблеми, згідно з яким, якщо ми можемо взяти
Проблема, розділіть його від чогось

1063
00:46:17,010 --> 00:46:22,340
дещо більшим в щось кілька
менше, я стверджую, що ми можемо дозволити його

1064
00:46:22,340 --> 00:46:26,040
можливо, трохи більш елегантно, з точки
конструкції, з меншою кількістю коду,

1065
00:46:26,040 --> 00:46:30,980
і може бути, навіть вирішити проблеми, які
буде складніше, так як ми в кінцевому рахунку

1066
00:46:30,980 --> 00:46:33,280
см., вирішуючи чисто итеративно.

1067
00:46:33,280 --> 00:46:35,980
>> Але захоплюючим, що я зробив
хочете, щоб залишити нас було на це.

1068
00:46:35,980 --> 00:46:40,720
Дозвольте мені йти вперед і відкрити
до файлу з -

1069
00:46:40,720 --> 00:46:44,300
Насправді, мене відпустили і
зробити це дуже швидко.

1070
00:46:44,300 --> 00:46:46,875
Дозвольте мені піти далі і запропонувати
наступному.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Серед код сьогоднішня цей файл тут.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Ось ця ось, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Так що це дурна маленька програма, яка
Я нашвидкуруч, що стверджує, що робити

1076
00:47:06,260 --> 00:47:06,940
наступному.

1077
00:47:06,940 --> 00:47:10,140
В основному, це спочатку заявляє
десяткового називаються X і привласнює його

1078
00:47:10,140 --> 00:47:11,100
значення 1.

1079
00:47:11,100 --> 00:47:13,520
Тоді він оголошує Цілочисельне Y та
присвоює їй значення 2.

1080
00:47:13,520 --> 00:47:15,310
Потім він видає які х і у.

1081
00:47:15,310 --> 00:47:17,781
Тоді він каже, заміна, точка точка точка.

1082
00:47:17,781 --> 00:47:21,670
>> Потім він стверджує, що виклик функції
називається своп, переходячи в X і

1083
00:47:21,670 --> 00:47:24,290
у, ідея якого в тому, що, ми сподіваємося,
х і у повернеться

1084
00:47:24,290 --> 00:47:25,620
інший, протилежний.

1085
00:47:25,620 --> 00:47:27,110
Тоді стверджують помінялися місцями!

1086
00:47:27,110 --> 00:47:28,420
зі знаком оклику.

1087
00:47:28,420 --> 00:47:30,190
Тоді вона виводить х і у.

1088
00:47:30,190 --> 00:47:33,480
>> Але виявляється, що це дуже
Проста демонстрація вниз

1089
00:47:33,480 --> 00:47:35,570
Тут насправді дитяча коляска.

1090
00:47:35,570 --> 00:47:38,870
Навіть якщо я оголошую тимчасовий
змінної і тимчасово покласти в

1091
00:47:38,870 --> 00:47:42,010
його, то я перепризначення
значення б -

1092
00:47:42,010 --> 00:47:45,080
яка відчуває себе розумно, тому, що я
збережені копії при темп.

1093
00:47:45,080 --> 00:47:48,410
Тоді я б поновлення на рівну
все, що було при темп.

1094
00:47:48,410 --> 00:47:51,610
Така оболонка гра переміщення
в В і В у За допомогою цієї

1095
00:47:51,610 --> 00:47:54,360
середньої людини по імені Temp відчуває
цілком розумно.

1096
00:47:54,360 --> 00:47:57,270
>> Але я стверджую, що коли я запускаю цю
коду, як я зроблю зараз -

1097
00:47:57,270 --> 00:47:59,490
Дозвольте мені йти вперед і вставте його тут.

1098
00:47:59,490 --> 00:48:01,995
Я буду називати цю noswap.c.

1099
00:48:01,995 --> 00:48:05,630
І як випливає з назви, це не
буде правильною програмою.

1100
00:48:05,630 --> 00:48:09,460
Не робіть noswap. / Ні підкачки.

1101
00:48:09,460 --> 00:48:12,110
X = 1, Y = 2, заміна, помінятися місцями.

1102
00:48:12,110 --> 00:48:14,220
х дорівнює 1, у дорівнює 2.

1103
00:48:14,220 --> 00:48:16,920
Це в корені неправильно, навіть
хоча це здається абсолютно

1104
00:48:16,920 --> 00:48:17,730
розумним мені.

1105
00:48:17,730 --> 00:48:21,330
І є причини, але ми не
збираємося виявити причину тільки поки.

1106
00:48:21,330 --> 00:48:24,610
>> Поки другий захоплюючим я хотів
залишить у вас є те,

1107
00:48:24,610 --> 00:48:27,120
Оголошення види на знижкових купонів.

1108
00:48:27,120 --> 00:48:31,590
Наші інновації з кінця днів у цьому році
спровокував нетривіальне кількість

1109
00:48:31,590 --> 00:48:33,830
питань, який був
У наші наміри не.

1110
00:48:33,830 --> 00:48:36,590
Метою цих купонів,
згідно з яким, якщо ви частина проблеми

1111
00:48:36,590 --> 00:48:39,850
встановити рано, таким чином отримуючи додатковий день,
було дійсно, щоб допомогти вам, хлопці, допоможіть

1112
00:48:39,850 --> 00:48:42,420
самі починають рано, отсортируйте
побічних стимулювання вас.

1113
00:48:42,420 --> 00:48:44,880
Допомагає нам розподілити навантаження між
Години роботи краще, щоб

1114
00:48:44,880 --> 00:48:45,740
це свого роду безпрограшна.

1115
00:48:45,740 --> 00:48:48,860
>> На жаль, я думаю, що мої інструкції
не було, на сьогоднішній день, дуже ясно, так що

1116
00:48:48,860 --> 00:48:52,230
Я повернувся в ці вихідні і оновлюється
У специфікації більше, сміливіше текст

1117
00:48:52,230 --> 00:48:53,600
поясніть кулі, як ці.

1118
00:48:53,600 --> 00:48:56,900
І просто сказати, що це більш відкрито, шляхом
Типово, набори проблеми обумовлені четвер

1119
00:48:56,900 --> 00:48:58,400
опівдні, в навчальну програму.

1120
00:48:58,400 --> 00:49:02,030
Якщо ви починаєте рано, завершальна частина
питання, поставлене середу о 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, частина, яка відноситься до купон
код, ідея в тому, що ви можете розширити

1122
00:49:05,170 --> 00:49:07,710
Вашої термін
P не встановлена ​​до п'ятниці.

1123
00:49:07,710 --> 00:49:10,890
Тобто, відкусила крихітний частина р.
встановлено щодо того, що зазвичай є

1124
00:49:10,890 --> 00:49:13,200
серйозніша проблема, і ви купуєте
собі додатковий день.

1125
00:49:13,200 --> 00:49:15,190
Знову ж, він отримує вас думати про
Поставлена ​​задача, отримує вас до

1126
00:49:15,190 --> 00:49:16,380
Години роботи раніше.

1127
00:49:16,380 --> 00:49:20,670
Але проблема купон на знижку і раніше
потрібно, навіть якщо ви нічого не пишіть.

1128
00:49:20,670 --> 00:49:23,340
>> Але ще більш переконливо це.

1129
00:49:23,340 --> 00:49:26,520
(Пошепки) А тих людей, залишаючи
рано збираються пошкодуєте.

1130
00:49:26,520 --> 00:49:28,620
Як ті люди, на балконі.

1131
00:49:28,620 --> 00:49:32,510
Прошу вибачення заздалегідь, щоб люди на
балкон з причин, які будуть

1132
00:49:32,510 --> 00:49:33,920
очистити через хвилину.

1133
00:49:33,920 --> 00:49:37,050
>> Так що нам пощастило мати один з
CS50 колишній глава навчання стипендіатів

1134
00:49:37,050 --> 00:49:39,302
Компанія під назвою dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Вони дуже щедро пожертвував
купон на знижку тут для цього багато місця,

1136
00:49:45,500 --> 00:49:48,180
який в порівнянні з
звичайна 2 гігабайти.

1137
00:49:48,180 --> 00:49:51,740
Так що те, що я думав, що ми могли б зробити на цьому
Останнє зауваження зробити трохи піддавки,

1138
00:49:51,740 --> 00:49:55,380
при цьому в якусь мить ми розкриємо
переможець і хто має купон

1139
00:49:55,380 --> 00:49:57,980
кодів, які можна потім перейти до їх
Веб-сайт, введіть його в, і вуаля, отримати

1140
00:49:57,980 --> 00:50:01,370
набагато більше простору Dropbox для вашого
прилад і для ваших особистих файлів.

1141
00:50:01,370 --> 00:50:05,690
>> І перший, хто хотів би взяти участь
на цьому малюнку?

1142
00:50:05,690 --> 00:50:09,630
Добре, тепер, що робить його ще більш захоплюючим.

1143
00:50:09,630 --> 00:50:14,010
Людина, яка отримує цю 25-гігабайтний
код купона - який далеко

1144
00:50:14,010 --> 00:50:16,150
більш переконливими, ніж пізно
днів в даний час, можливо -

1145
00:50:16,150 --> 00:50:20,620
це той, хто сидить на вершині
подушка сидіння під якою мається

1146
00:50:20,620 --> 00:50:21,620
що код купона.

1147
00:50:21,620 --> 00:50:23,480
Тепер ви можете дивитися під
ваша подушка сидіння.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [ВІДТВОРЕННЯ ВІДЕО]

1150
00:50:29,680 --> 00:50:31,620
>> -Раз, два, три.

1151
00:50:31,620 --> 00:50:35,015
>> [Крики]

1152
00:50:35,015 --> 00:50:35,985
>> -Ви отримуєте автомобіль!

1153
00:50:35,985 --> 00:50:36,670
Ви отримуєте автомобіль!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID мала: Ми побачимо
Ви в середу.

1155
00:50:37,970 --> 00:50:38,904
>> -Ви отримуєте автомобіль!

1156
00:50:38,904 --> 00:50:39,371
Ви отримуєте автомобіль!

1157
00:50:39,371 --> 00:50:40,305
Ви отримуєте автомобіль!

1158
00:50:40,305 --> 00:50:41,706
Ви отримуєте автомобіль!

1159
00:50:41,706 --> 00:50:43,107
Ви отримуєте автомобіль!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID мала: Балкон люди, приходьте
тут на передній план,

1161
00:50:45,530 --> 00:50:46,866
де у нас є додаткові послуги.

1162
00:50:46,866 --> 00:50:50,282
>> -Кожен отримує автомобіль!

1163
00:50:50,282 --> 00:50:52,234
Кожен отримує автомобіль!

1164
00:50:52,234 --> 00:50:52,722
>> [КІНЕЦЬ відеовідтворення]

1165
00:50:52,722 --> 00:50:54,590
>> Оповідач: Наступного CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: О боже мій Гоша Гоша Гоша
Гоша Гоша Гоша Гоша Гоша Гоша -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukelele ІГРИ]