1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> СПІКЕР: Гаразд, це CS50.

3
00:00:14,910 --> 00:00:19,020
Це кінець три тижні, і якщо
Ви не скористалися вже,

4
00:00:19,020 --> 00:00:21,790
знаю, що там буде обід
в цю п'ятницю, як завжди, десь

5
00:00:21,790 --> 00:00:25,430
Ви можете насолоджуватися гарною бесідою
і їжа в Вогонь і лід

6
00:00:25,430 --> 00:00:27,980
з деякими з CS50 сайт
персонал і однокласники.

7
00:00:27,980 --> 00:00:30,170
Голова до цього URL тут.

8
00:00:30,170 --> 00:00:33,420
>> Тепер ви, напевно, пам'ятаєте, або ви
найближчим часом може бути знаком с,

9
00:00:33,420 --> 00:00:35,970
ці речі тут, які
наведені в кінці

10
00:00:35,970 --> 00:00:37,850
семестру для багатьох класів.

11
00:00:37,850 --> 00:00:40,870
Так звані екзаменаційні сині книги, в яких
Ви пишете свої відповіді на іспитах.

12
00:00:40,870 --> 00:00:44,240
Тепер у мене є тут 26 таких
блакитні книги, на кожен з них

13
00:00:44,240 --> 00:00:47,580
написано ім'я, до Z. І
дійсно, імена, що просто,

14
00:00:47,580 --> 00:00:50,490
до Z. І один з
цілі під рукою сьогодні

15
00:00:50,490 --> 00:00:53,910
буде продовжувати те, що
ми почали в понеділок, який не є

16
00:00:53,910 --> 00:00:57,830
стільки дивлячись на код, але насправді
дивлячись на ідеї та вирішення проблем.

17
00:00:57,830 --> 00:01:00,170
Одна з цілей і
Обіцянки цього курсу

18
00:01:00,170 --> 00:01:02,985
є навчити вас думати більше
ретельно, більш методично,

19
00:01:02,985 --> 00:01:05,400
і більш ефективно вирішувати проблеми.

20
00:01:05,400 --> 00:01:09,526
І справді, що ми можемо зробити, що дійсно
, Навіть не торкаючись жодного рядка коду.

21
00:01:09,526 --> 00:01:12,150
Тому у мене є пару слонів
тут сьогодні, помаранчевий і синій,

22
00:01:12,150 --> 00:01:15,780
якби ми могли отримати один доброволець,
може бути, від далі назад, ніж зазвичай.

23
00:01:15,780 --> 00:01:18,070
Як щодо прямо там, давай вниз.

24
00:01:18,070 --> 00:01:24,180
Мета, яка буде в
допомогти плюс адмініструвати цей іспит тут.

25
00:01:24,180 --> 00:01:24,935
Як тебе звуть?

26
00:01:24,935 --> 00:01:25,768
>> АУДИТОРІЯ: Мері Бет.

27
00:01:25,768 --> 00:01:27,560
СПІКЕР: Мері Бет, давай до.

28
00:01:27,560 --> 00:01:29,560
Дозвольте мені мікрофон тут для вас.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Приємно познайомитися.

31
00:01:32,880 --> 00:01:34,005
>> АУДИТОРІЯ: Приємно познайомитися.

32
00:01:34,005 --> 00:01:36,790
СПІКЕР: Гаразд, у мене є
тут синій книги через Z,

33
00:01:36,790 --> 00:01:41,680
і я збираюся робити вигляд, що
У мене є один зі студентів,

34
00:01:41,680 --> 00:01:45,770
і вони йдуть в кілька випадковим
Наприкінці тригодинного іспиту блоку,

35
00:01:45,770 --> 00:01:49,400
таким чином, вони в кінцевому підсумку в деяких
полуслучайная порядок, як це.

36
00:01:49,400 --> 00:01:54,510
Тепер ваша задача в мить збирається
щоб be-- це насправді, як вони отримують

37
00:01:54,510 --> 00:01:56,820
Виявилося, в кінці
клас, швидше за все.

38
00:01:56,820 --> 00:02:01,120
Ваше завдання тепер буде, цілком
просто, щоб впорядкувати ці сині книги для нас

39
00:02:01,120 --> 00:02:05,220
від А до Z.

40
00:02:05,220 --> 00:02:08,400
>> АУДИТОРІЯ: О, це
збирається взяти назавжди.

41
00:02:08,400 --> 00:02:13,747
>> СПІКЕР: І ми будемо дивитися
не, як ви робите це, ніякого тиску.

42
00:02:13,747 --> 00:02:15,330
АУДИТОРІЯ: Ні, ніякого тиску або нічого.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> СПІКЕР: І для задоволення,
давайте миритися таймер.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> АУДИТОРІЯ: Так весело, так весело.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> СПІКЕР: я можу тримати мікрофон для вас.

49
00:02:38,574 --> 00:02:40,240
Добре, що ми тільки що подвоїли швидкість.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Таким чином, у той же час, Дозвольте мені задати що
буде питання для Мері Бет

52
00:02:49,060 --> 00:02:51,540
є те, що вона робить, як це
вона збирається про вирішення цього?

53
00:02:51,540 --> 00:02:54,040
І справді, ви не могли б
Замислювалися про що

54
00:02:54,040 --> 00:02:57,440
так просто, як коли ви вибираєте
до 26 книгах, як це,

55
00:02:57,440 --> 00:02:59,350
які мають природне
замовлення до них.

56
00:02:59,350 --> 00:03:01,335
Який процес
що ви насправді використовувати?

57
00:03:01,335 --> 00:03:03,770
Це досить випадковим просто
вибираючи перший, який ви бачите

58
00:03:03,770 --> 00:03:05,250
і покласти її на місце?

59
00:03:05,250 --> 00:03:09,680
Ви спочатку перемістити свої руки навколо
шукаю потім шукаєте B?

60
00:03:09,680 --> 00:03:11,722
Ви погляньте на
Пара з них пліч-о-пліч

61
00:03:11,722 --> 00:03:14,680
і просто сказати, постійте, це
не правий, а потім поміняти порядок?

62
00:03:14,680 --> 00:03:16,960
Ми бачили вже в понеділок
що є кілька способів

63
00:03:16,960 --> 00:03:22,140
, В якому ми можемо зробити це, і
дійсно, як ми наближаємося до кінця тут,

64
00:03:22,140 --> 00:03:26,360
Я б взяти до відома, можливо,
чого Мері Бет робить.

65
00:03:26,360 --> 00:03:30,040
У нас є кілька паль схоже,
більший, три поменше.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> АУДИТОРІЯ: я їх замовленні
коли я знаходжу два листи

68
00:03:36,415 --> 00:03:39,540
що я знаю, разом в послідовності,
Я поклав їх разом так, що я не

69
00:03:39,540 --> 00:03:42,915
доведеться турбуватися про збереження
трек з цілого ряду книг.

70
00:03:42,915 --> 00:03:45,706
Це просто, ну, по-перше,
У мене цей стек тут.

71
00:03:45,706 --> 00:03:47,580
СПІКЕР: Так, майже як
головоломка частин, які

72
00:03:47,580 --> 00:03:49,860
мають правильну форму до
збігаються один з одним.

73
00:03:49,860 --> 00:03:51,026
АУДИТОРІЯ: Досить багато, так.

74
00:03:51,026 --> 00:03:55,320
СПІКЕР: ОК, відмінно.

75
00:03:55,320 --> 00:03:59,850
І тепер кожен з них
палі Імовірно упорядковано?

76
00:03:59,850 --> 00:04:00,990
>> АУДИТОРІЯ: Так.

77
00:04:00,990 --> 00:04:09,900
>> СПІКЕР: Гаразд, до Z. All
Добре, вітаю, ви зробили це.

78
00:04:09,900 --> 00:04:11,461
У вас є вибір.

79
00:04:11,461 --> 00:04:11,960
Синій?

80
00:04:11,960 --> 00:04:13,530
Добре, спасибі вам за це.

81
00:04:13,530 --> 00:04:16,679
Так Мері Бет зробив запропонувати
що її підхід був,

82
00:04:16,679 --> 00:04:19,720
але те, що це ще один підхід, як вам
може йти про сортування ці речі?

83
00:04:19,720 --> 00:04:21,130
Що б ви зробили?

84
00:04:21,130 --> 00:04:24,060
Запис бити було б
одна хвилина і 50 або близько того секунд,

85
00:04:24,060 --> 00:04:26,039
плюс ті, які я забув порахувати.

86
00:04:26,039 --> 00:04:27,080
Що б ви зробили?

87
00:04:27,080 --> 00:04:27,579
Да?

88
00:04:27,579 --> 00:04:28,735
АУДИТОРІЯ: Візьміть стопку.

89
00:04:28,735 --> 00:04:29,776
Почніть з самого початку.

90
00:04:29,776 --> 00:04:32,284
Перевірте ваші документи.

91
00:04:32,284 --> 00:04:36,586
І якщо верхній вище
ніж, може бути, вони,

92
00:04:36,586 --> 00:04:38,980
нижній є
вище, то поміняти їх.

93
00:04:38,980 --> 00:04:41,300
>> СПІКЕР: ОК, так що починати
у верхній і нижній,

94
00:04:41,300 --> 00:04:43,716
а потім працювати ваш шлях
всередину так, помінявши їх місцями?

95
00:04:43,716 --> 00:04:46,580
Отже, трохи схожий
по духу бульбашкового сортування,

96
00:04:46,580 --> 00:04:49,160
але вибір крайності
НЕ сусідні пари.

97
00:04:49,160 --> 00:04:52,080
Але за винятком цього є те, що є
напевно купа різному

98
00:04:52,080 --> 00:04:54,210
ми могли б зробити це, і
чесно кажучи, я думаю, вам вид

99
00:04:54,210 --> 00:04:55,700
прийняв пару підходів, чи не так?

100
00:04:55,700 --> 00:05:00,567
Ви зробили те чотирьох відсортованих паль, і
потім ефективно об'єднали їх разом.

101
00:05:00,567 --> 00:05:02,650
І ось, гадаю, ще один
Техніка в цілому.

102
00:05:02,650 --> 00:05:06,950
Ви не розглядати його як один великий купі,
Ви розділили проблему на чотири каре,

103
00:05:06,950 --> 00:05:09,820
якщо хочете, і тоді так чи інакше
об'єднали їх в кінці.

104
00:05:09,820 --> 00:05:13,410
>> Отже, давайте розглянемо, в кінцевому рахунку ,,
як ще ми могли б зробити це.

105
00:05:13,410 --> 00:05:15,860
Ми оформлено поняття
бульбашкового сортування останній раз,

106
00:05:15,860 --> 00:05:18,780
і бульбашкового сортування нагадаємо було
Алгоритм, який ми візуалізували

107
00:05:18,780 --> 00:05:22,640
з восьми своїх однокласників тут,
здавалося б, випадково упорядковано спочатку.

108
00:05:22,640 --> 00:05:26,110
І ми тоді вирішили попарно, якщо
два елементи з того,

109
00:05:26,110 --> 00:05:26,950
просто поміняти їх місцями.

110
00:05:26,950 --> 00:05:28,930
Так чотири і два
очевидно, з того,

111
00:05:28,930 --> 00:05:31,080
так ці два однокласників
помінялися місцями.

112
00:05:31,080 --> 00:05:35,390
А потім ми повторили з чотирьох до шести років,
потім шість і вісім, на кожній ітерації,

113
00:05:35,390 --> 00:05:36,980
рухатися вправо.

114
00:05:36,980 --> 00:05:42,590
>> Тому, враховуючи, вісім осіб, скільки попарно
порівняння я зробив під час прогулянки з

115
00:05:42,590 --> 00:05:45,220
зліва направо в одній такій ітерації?

116
00:05:45,220 --> 00:05:48,410
Скільки порівняння?

117
00:05:48,410 --> 00:05:49,197
Сім, чи не так?

118
00:05:49,197 --> 00:05:51,405
Тому що, якщо є вісім
люди, але у вас є пару

119
00:05:51,405 --> 00:05:53,880
їм і ви продовжувати рухатися
один хоп вправо,

120
00:05:53,880 --> 00:05:56,060
ви не будете мати вісім
порівняння, тому що ви не можете порівняти

121
00:05:56,060 --> 00:05:59,226
елемент сам в собі, або це буде
просто безглуздо, так що ви повинні сім.

122
00:05:59,226 --> 00:06:01,290
Або в більш загальному, якщо
у нас є російських людей, ми

123
00:06:01,290 --> 00:06:04,300
зробити п мінус 1 порівнянь
з бульбашкового сортування.

124
00:06:04,300 --> 00:06:08,150
>> Отже, давайте розглянемо тепер, наскільки добре чи
погано міхур був сам, і спробуйте

125
00:06:08,150 --> 00:06:13,570
дати собі словник з
для критики алгоритмів, як це,

126
00:06:13,570 --> 00:06:14,430
і незабаром самостійно.

127
00:06:14,430 --> 00:06:16,970
Так при першому проходженні через
бульбашкового сортування, перший раз

128
00:06:16,970 --> 00:06:20,909
Я йшов зліва направо по
етап, взяв мене н мінус 1 порівнянь.

129
00:06:20,909 --> 00:06:22,950
І це буде мій
одиниця виміру, чи не так?

130
00:06:22,950 --> 00:06:26,170
Я був почасти говорити і прогулюючись,
кілька швидко, наскільки повільно,

131
00:06:26,170 --> 00:06:29,300
так вважаю своїх секундах
не дуже показово,

132
00:06:29,300 --> 00:06:32,260
але підрахунку кількості
операції, які я зробив у понеділок,

133
00:06:32,260 --> 00:06:35,900
порівняння двох людей, що відчуває себе
як хороший одиниці виміру.

134
00:06:35,900 --> 00:06:40,980
>> Так н мінус 1 кроки в перший раз,
але те що сталося після цього?

135
00:06:40,980 --> 00:06:46,610
Що один Верх один прохід
через іншому випадку несортоване список?

136
00:06:46,610 --> 00:06:49,840
Що ви можете сказати мені про елемент
який був повністю там?

137
00:06:49,840 --> 00:06:51,300
Да?

138
00:06:51,300 --> 00:06:52,870
Це був найбільший елемент, чи не так?

139
00:06:52,870 --> 00:06:55,710
Номер вісім, хоча вона
почалося тут, кожен раз, коли я

140
00:06:55,710 --> 00:06:57,860
в порівнянні з нею проти
сусід, вона продовжувала

141
00:06:57,860 --> 00:07:00,480
б'ється праворуч
Права частина списку.

142
00:07:00,480 --> 00:07:02,710
І справді, ось де
Алгоритм отримав свою назву.

143
00:07:02,710 --> 00:07:07,630
>> Тепер за цією логікою, скільки порівняння
чи потрібно робити на другий раз

144
00:07:07,630 --> 00:07:09,800
Я роблю, що прохід зліва направо?

145
00:07:09,800 --> 00:07:10,730
н мінус 2, чи не так?

146
00:07:10,730 --> 00:07:14,297
Було б просто витрачати свій час, якщо I
тримати порівнюючи вісім проти кого

147
00:07:14,297 --> 00:07:16,630
ще, бо ми вже знаємо
вона була в потрібному місці.

148
00:07:16,630 --> 00:07:19,760
Так що це трохи
оптимізація, тому наступного прохід

149
00:07:19,760 --> 00:07:23,899
буде плюс н мінус два кроки,
де п число людей.

150
00:07:23,899 --> 00:07:26,940
Тепер ви можете роду екстраполяції, навіть
якщо ви не фахівець з комп'ютерів,

151
00:07:26,940 --> 00:07:27,680
як це закінчується.

152
00:07:27,680 --> 00:07:31,259
В кінці цього алгоритму, мабуть
у вас є тільки одне порівняння залишили.

153
00:07:31,259 --> 00:07:33,800
Ви повинні роду виправити
початку списку в разі двох

154
00:07:33,800 --> 00:07:36,540
і один вийшли з ладу
і повинен бути один і два,

155
00:07:36,540 --> 00:07:40,330
так що це упору на
плюс 1 Остаточне порівняння.

156
00:07:40,330 --> 00:07:44,500
>> Тепер точка, точка, точка вид хвиль це
руки у деяких з соковитіше деталей,

157
00:07:44,500 --> 00:07:46,452
але давайте просто йти вперед і спрощення.

158
00:07:46,452 --> 00:07:48,660
Якщо ви пам'ятаєте з високого
школа, чесно кажучи, багато хто з вас

159
00:07:48,660 --> 00:07:50,340
була математичні книги, які мали
трохи шпаргалка

160
00:07:50,340 --> 00:07:52,550
на обкладинці або
задня кришка, що показав вам,

161
00:07:52,550 --> 00:07:56,400
Підсумовування що серія, як
це, зрештою складаються в.

162
00:07:56,400 --> 00:07:59,600
У загальному випадку, якщо у вас є
змінна, як п, і справді це одне,

163
00:07:59,600 --> 00:08:01,634
якщо ви подивіться на ваш
стара школа математика книга,

164
00:08:01,634 --> 00:08:04,050
ви побачите, що це насправді
додає до цієї суми тут,

165
00:08:04,050 --> 00:08:07,970
п раз п мінус 1 все поділене на число 2.

166
00:08:07,970 --> 00:08:11,172
Так що на даний дозвольте мені просто передбачають
це вірно, так на стрибок віри,

167
00:08:11,172 --> 00:08:12,880
це те, що це підводить
до, і ми могли

168
00:08:12,880 --> 00:08:14,341
довести, що в більш загальному випадку.

169
00:08:14,341 --> 00:08:15,590
Але тепер давайте розширимо це.

170
00:08:15,590 --> 00:08:19,920
Так що давайте помножимо це, так от
н квадрат, мінус п, все розділити на 2.

171
00:08:19,920 --> 00:08:23,200
Це дійсно п квадрат,
поділене на 2, мінус п над 2,

172
00:08:23,200 --> 00:08:25,010
так що все добре і цікаво.

173
00:08:25,010 --> 00:08:27,060
Але що станеться, якщо ми
Плагін значення?

174
00:08:27,060 --> 00:08:29,724
Припустимо, у мене не було вісім
люди, але сказати, мільйон.

175
00:08:29,724 --> 00:08:31,890
І млн тільки тому, що
це досить велика сума,

176
00:08:31,890 --> 00:08:34,039
давайте підключити, що в і подивитися, що відбувається.

177
00:08:34,039 --> 00:08:39,039
Так що, якщо я підключу млн в цій формулі
Я йду, щоб отримати мільйон квадрат,

178
00:08:39,039 --> 00:08:42,868
поділене на 2, мінус
млн, поділене на 2.

179
00:08:42,868 --> 00:08:44,159
Тепер те, що, що збирається рівнятися?

180
00:08:44,159 --> 00:08:47,354
Так 500000000000, мінус 500 000.

181
00:08:47,354 --> 00:08:49,270
А якщо я насправді
що математика, це означає,

182
00:08:49,270 --> 00:08:53,920
що сортування мільйон
люди з бульбашкового сортування

183
00:08:53,920 --> 00:09:01,800
може зайняти мені +499999500000
кроки чи порівняння зрештою,

184
00:09:01,800 --> 00:09:02,900
ми просто екстраполяції.

185
00:09:02,900 --> 00:09:06,860
>> Це відчуває себе досить повільно, але, чесно кажучи
вимірювання один певний вхід

186
00:09:06,860 --> 00:09:09,160
як це, не все, що говорить багато про що.

187
00:09:09,160 --> 00:09:14,050
Але насправді це означає, що до як п
отримує більше і більше, цей алгоритм

188
00:09:14,050 --> 00:09:16,280
вид почуває себе гірше і
гірше, або ви дійсно

189
00:09:16,280 --> 00:09:20,450
починають відчувати біль, що
спорудження до рівня, що п квадрат,

190
00:09:20,450 --> 00:09:21,770
який додає досить швидко.

191
00:09:21,770 --> 00:09:25,340
І ця деталь не
втратив на людей, насправді

192
00:09:25,340 --> 00:09:29,640
Кілька років тому якийсь сенатор, який був
агітація, сів на співбесіду

193
00:09:29,640 --> 00:09:32,180
з Еріком компанії Google
Шмідт, генеральний директор в той час,

194
00:09:32,180 --> 00:09:36,380
і був кинутий виклик з питанням
так само, як ми досліджуємо сьогодні.

195
00:09:36,380 --> 00:09:38,468
Давайте поглянемо.

196
00:09:38,468 --> 00:09:45,280
>> [Відеовідтворення]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Що ти тут
в Google, і мені подобається

198
00:09:48,560 --> 00:09:53,382
думати про президентство
як співбесіда.

199
00:09:53,382 --> 00:09:56,434
Тепер, це важко отримати
робота в якості президента,

200
00:09:56,434 --> 00:09:58,100
і ви збираєтеся через суворі зараз.

201
00:09:58,100 --> 00:10:01,860
Це також важко отримати роботу в Google.

202
00:10:01,860 --> 00:10:05,490
У нас є питання, і ми
просимо наших кандидатів питання,

203
00:10:05,490 --> 00:10:09,770
і цей від Ларрі Швіммер.

204
00:10:09,770 --> 00:10:14,760
Подав що ви, хлопці, думаєте, що я
жартую, це прямо тут.

205
00:10:14,760 --> 00:10:17,930
Що є найбільш ефективним способом
сортувати мільйон 32-розрядних цілих чисел?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -Пробач, Maybe--

209
00:10:25,200 --> 00:10:27,400
>> Ні, ні, ні.

210
00:10:27,400 --> 00:10:30,700
Я думаю, що міхур то
буде неправильний шлях.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -Давай, Який сказав йому, цей?

213
00:10:38,180 --> 00:10:40,590
Я не бачив комп'ютер
наука в фоні.

214
00:10:40,590 --> 00:10:42,130
>> -Ми Отримали наші шпигуни там.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK, Давайте запитаємо відрізняється
питання інтерв'ю.

217
00:10:48,444 --> 00:10:49,300
>> [END відеовідтворення]

218
00:10:49,300 --> 00:10:52,290
>> СПІКЕР: Так говорити про
конкретні цифри, хоча,

219
00:10:52,290 --> 00:10:53,890
не збирається бути все, що корисно.

220
00:10:53,890 --> 00:10:56,810
Це не урок життя, що міхур
сортувати, враховуючи мільйон входів,

221
00:10:56,810 --> 00:10:58,590
може зайняти цілих 500 мільярдів кроків.

222
00:10:58,590 --> 00:11:01,120
Ви не можете дійсно узагальнити
надто ефективно від

223
00:11:01,120 --> 00:11:03,560
і приймати правильні рішення дизайну
при написанні програм.

224
00:11:03,560 --> 00:11:07,070
Так що давайте хоча зосередитися на тому,
ми могли б спростити цей результат.

225
00:11:07,070 --> 00:11:11,780
>> Так що я виділені жовтим кольором тут
Результатом п поділене на квадрат 2,

226
00:11:11,780 --> 00:11:14,330
так млн квадрат
поділене на 2, а потім

227
00:11:14,330 --> 00:11:16,710
Я виділив те, що
Остаточний відповідь була

228
00:11:16,710 --> 00:11:20,180
як тільки ми віднімається від п поділене на число 2.

229
00:11:20,180 --> 00:11:24,850
І претензії я збираюся зробити зараз,
хто, чорт візьми піклується якщо відняти від

230
00:11:24,850 --> 00:11:30,060
трохи старий п над 2, коли перший
частина цієї формули є набагато більше?

231
00:11:30,060 --> 00:11:33,910
Це домінує над іншим
Термін, н квадрат розділений на 2

232
00:11:33,910 --> 00:11:37,510
так набагато більше, ясно, як
н стає великим, як мільйон,

233
00:11:37,510 --> 00:11:41,450
що є насправді велика різниця в
кінець дня між 500000000000

234
00:11:41,450 --> 00:11:45,730
і +499999500000?

235
00:11:45,730 --> 00:11:46,349
Не зовсім.

236
00:11:46,349 --> 00:11:48,640
І так, що ми збираємося
робити, як комп'ютерники є

237
00:11:48,640 --> 00:11:53,270
ігнорувати ці молодші члени та
прийняти те, як це і дійсно

238
00:11:53,270 --> 00:11:56,050
тільки спростити його, щоб
термін, який походить з матерією.

239
00:11:56,050 --> 00:12:00,315
Чим більше наші набори даних отримати, тим більше
наші бази даних отримати, тим більше веб-сторінок

240
00:12:00,315 --> 00:12:02,690
ми повинні шукати, тим більше
Друзі у вас є на Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Як н стає більше, ми дійсно
дбатиме про величину

242
00:12:07,340 --> 00:12:11,560
Термін в будь-якому такому аналізі
наш виступ алгоритми.

243
00:12:11,560 --> 00:12:16,230
І я збираюся сказати, ви знаєте, що,
бульбашкового сортування порядку великого O,

244
00:12:16,230 --> 00:12:18,060
порядку п квадрат.

245
00:12:18,060 --> 00:12:20,090
Це не зовсім н
квадрат, як ми бачили,

246
00:12:20,090 --> 00:12:22,060
але хто дійсно піклується
про тих невеликих точки,

247
00:12:22,060 --> 00:12:24,390
і, чесно кажучи, хто насправді
різниця, якщо ми ділимо на 2?

248
00:12:24,390 --> 00:12:25,870
Ось тільки постійним фактором.

249
00:12:25,870 --> 00:12:29,480
І це 500 мільярдів проти 250
млрд дійсно, що велика справа?

250
00:12:29,480 --> 00:12:32,190
Я міг би просто чекати один рік,
нехай мій ноутбук буквально

251
00:12:32,190 --> 00:12:34,810
отримати в два рази швидше в апаратних засобах,
і такого роду відмінності

252
00:12:34,810 --> 00:12:36,650
просто йде природним плином часу.

253
00:12:36,650 --> 00:12:39,300
>> Те, що ми дбаємо про те,
вираз, частина

254
00:12:39,300 --> 00:12:42,489
вирази, що буде мінятися в залежності
як наш вклад стає більше і більше.

255
00:12:42,489 --> 00:12:45,280
І справді, в реальному світі,
це те, що все більше відбувається

256
00:12:45,280 --> 00:12:48,330
є внеском у наші проблеми і
алгоритми стають все більше.

257
00:12:48,330 --> 00:12:53,470
Настільки великий O буде позначення,
асимптотическое позначення, що ми просто

258
00:12:53,470 --> 00:12:57,160
використовувати як комп'ютерні фахівці, щоб описати
продуктивність, або час роботи,

259
00:12:57,160 --> 00:12:58,130
алгоритму.

260
00:12:58,130 --> 00:13:00,800
Так що ми можемо порівняти алгоритми
на різних комп'ютерах, написаних

261
00:13:00,800 --> 00:13:04,170
різними людьми, за допомогою
деякі принципово схожі метрика

262
00:13:04,170 --> 00:13:07,557
як числа порівнянь ви
рішень, або, може бути, кількість свопів

263
00:13:07,557 --> 00:13:08,140
ви робите.

264
00:13:08,140 --> 00:13:11,910
>> Те, що ми не збираємося
кількість являє собою кількість часу

265
00:13:11,910 --> 00:13:13,981
, Який проходить по годинах
на стіні зазвичай.

266
00:13:13,981 --> 00:13:16,230
Те, що ми не збираємося турбуватися
про те, скільки пам'яті

267
00:13:16,230 --> 00:13:17,820
ви використовуєте сьогодні на
міру, хоча це

268
00:13:17,820 --> 00:13:19,370
ще один ресурс, ми могли б виміряти.

269
00:13:19,370 --> 00:13:23,610
Ми збираємося, щоб спробувати засновувати наші аналізи
на лише основні операції, ті,

270
00:13:23,610 --> 00:13:25,930
чесно кажучи, що ви можете бачити найбільш візуально.

271
00:13:25,930 --> 00:13:30,700
Так щось на зразок великої O п
квадрат, я стверджую, що O н квадрат

272
00:13:30,700 --> 00:13:35,820
є верхньою межею на так званий
час роботи в бульбашкового сортування.

273
00:13:35,820 --> 00:13:38,820
Іншими словами, якщо вас
хотів стверджувати, що є

274
00:13:38,820 --> 00:13:41,370
це верхня межа того, скільки
кроки алгоритму може зайняти,

275
00:13:41,370 --> 00:13:46,240
це буде у великій O п
квадрат в цьому випадку верхня межа.

276
00:13:46,240 --> 00:13:49,710
>> Що робити, якщо я замість змінити
історія була нема про бульбашкового сортування,

277
00:13:49,710 --> 00:13:50,910
але про це верхня межа.

278
00:13:50,910 --> 00:13:54,030
Чи можете ви назвати алгоритмом
що ми дивилися на вже

279
00:13:54,030 --> 00:13:59,530
чия верхня межа, максимум
вимірювання часу або операцій,

280
00:13:59,530 --> 00:14:04,300
буде називається обмеженим,
по п, лінійною функцією,

281
00:14:04,300 --> 00:14:07,260
не квадратичного, ось вигнуті?

282
00:14:07,260 --> 00:14:10,780
Що собою алгоритм, який
завжди займає не більше

283
00:14:10,780 --> 00:14:12,860
ніж як п кроків, або
2n кроків, або кроки 3n?

284
00:14:12,860 --> 00:14:13,360
Да?

285
00:14:13,360 --> 00:14:15,030
>> АУДИТОРІЯ: Пошук
Найбільша кількість у списку?

286
00:14:15,030 --> 00:14:16,930
>> СПІКЕР: Абсолютно, знаходячи
Найбільша кількість у списку.

287
00:14:16,930 --> 00:14:18,940
Якщо мені дадуть список
люди наприклад,

288
00:14:18,940 --> 00:14:21,440
кожен з який тримає ряд,
що це максимальне число

289
00:14:21,440 --> 00:14:23,770
кроків він повинен взяти мене,
розумно розумна людина,

290
00:14:23,770 --> 00:14:27,530
знайти найбільше людини в цьому списку?

291
00:14:27,530 --> 00:14:28,100
п, чи не так?

292
00:14:28,100 --> 00:14:31,320
Тому що в гіршому випадку, де
може найбільша цінність бути?

293
00:14:31,320 --> 00:14:32,700
Право, всю дорогу в кінці.

294
00:14:32,700 --> 00:14:34,575
Таким чином, в гіршому випадку
Верхня межа, я міг би

295
00:14:34,575 --> 00:14:36,450
повинні пройти весь шлях
тут і сказати:

296
00:14:36,450 --> 00:14:39,170
ой, ось номер вісім,
або що це значення.

297
00:14:39,170 --> 00:14:41,330
Тепер було б просто нерозумно
якщо я продовжував йти, чи не так?

298
00:14:41,330 --> 00:14:43,840
Дивлячись на все більше і більше елементів
якщо останній з них знаходиться там?

299
00:14:43,840 --> 00:14:45,340
Так, звичайно ,, п є верхньою межею.

300
00:14:45,340 --> 00:14:47,420
Мені не потрібно, щоб взяти
більше кроків, ніж це.

301
00:14:47,420 --> 00:14:51,580
>> Так що, якщо замість цього я запропонував, щоб
Є алгоритми в цьому світі, що

302
00:14:51,580 --> 00:14:57,750
є час, бігаючи Це
обмежена великим O із журналу п, увійдіть н?

303
00:14:57,750 --> 00:15:00,390
Де ми бачили цього раніше?

304
00:15:00,390 --> 00:15:00,890
Да?

305
00:15:00,890 --> 00:15:03,309
>> АУДИТОРІЯ: У задачі телефонної книги?

306
00:15:03,309 --> 00:15:04,850
СПІКЕР: Як проблеми телефонної книги.

307
00:15:04,850 --> 00:15:07,754
Те, що було показником того, наскільки
скільки часу або скільки сліз IT

308
00:15:07,754 --> 00:15:10,170
взяв мене, щоб знайти таку людину, як
Майк Сміт в телефонній книзі?

309
00:15:10,170 --> 00:15:13,212
Ми стверджували, що це був журнал п, і
навіть якщо не знайомі або це

310
00:15:13,212 --> 00:15:15,170
трохи туманно, що
логарифм або показник був,

311
00:15:15,170 --> 00:15:17,650
тільки пам'ятайте, що § п
як правило, відноситься до процесу,

312
00:15:17,650 --> 00:15:20,790
В цьому випадку ділення
то в половині знову, і знову,

313
00:15:20,790 --> 00:15:25,790
і знову, і знову, так що він
отримує все менше і менше, як і ви, що.

314
00:15:25,790 --> 00:15:28,470
>> Так увійти н стосується, звичайно,
наприклад телефонної книги,

315
00:15:28,470 --> 00:15:32,662
щоб бінарного пошуку в теорії, коли ми
були віртуальні двері на борту,

316
00:15:32,662 --> 00:15:34,370
або коли Шон був
пошуках чогось.

317
00:15:34,370 --> 00:15:37,374
Якщо він використовується бінарний пошук, увійдіть н
буде верхня межа, скільки

318
00:15:37,374 --> 00:15:38,040
час, що потрібно.

319
00:15:38,040 --> 00:15:44,027
Але ці алгоритми, які бігли в
§ п передбачається, які ключові деталі?

320
00:15:44,027 --> 00:15:45,360
Це список був відсортований, чи не так?

321
00:15:45,360 --> 00:15:47,789
Ваш алгоритм помиляється, якщо
ваш вклад не сортується,

322
00:15:47,789 --> 00:15:49,830
і ще ви використовуєте
щось на зразок бінарного пошуку

323
00:15:49,830 --> 00:15:51,704
тому що ви можете стрибати
прямо над елементом

324
00:15:51,704 --> 00:15:53,600
, Не розуміючи, що це дійсно є.

325
00:15:53,600 --> 00:15:55,600
>> Тепер, що це може означати, Big O одного?

326
00:15:55,600 --> 00:15:59,117
Це не означає, що ваш алгоритм
займає один і тільки один крок,

327
00:15:59,117 --> 00:16:01,200
це просто означає, що вимагається
постійне число кроків.

328
00:16:01,200 --> 00:16:04,060
Може бути, це 1, може бути, це
10, може бути, це 1000,

329
00:16:04,060 --> 00:16:07,750
але це залежить від
розмір проблеми.

330
00:16:07,750 --> 00:16:10,850
Незалежно від того, наскільки великий п,
постійна алгоритм час

331
00:16:10,850 --> 00:16:12,747
завжди має те ж саме число кроків.

332
00:16:12,747 --> 00:16:15,080
Так що може бути алгоритм
ми говорили про або просто

333
00:16:15,080 --> 00:16:20,418
інтуїтивно, що приходить до вас, що
завжди працює в так званій постійної часу?

334
00:16:20,418 --> 00:16:20,918
Да?

335
00:16:20,918 --> 00:16:22,001
>> АУДИТОРІЯ: Додати два числа.

336
00:16:22,001 --> 00:16:25,320
СПІКЕР: Додати два числа,
2 плюс 2 дорівнює 4, зроблено.

337
00:16:25,320 --> 00:16:27,227
Так що може працювати, що ще?

338
00:16:27,227 --> 00:16:28,560
Як щодо більш реальному світі, так?

339
00:16:28,560 --> 00:16:30,686
>> АУДИТОРІЯ: Пошук
Перше, що в списку.

340
00:16:30,686 --> 00:16:32,810
СПІКЕР: Пошук першим
елемент у списку, звичайно.

341
00:16:32,810 --> 00:16:34,540
Ми насправді говорив
про масивах вже,

342
00:16:34,540 --> 00:16:36,540
як ви отримаєте на
Перший елемент в масиві,

343
00:16:36,540 --> 00:16:40,465
незалежно від того, як довго
масив на С?

344
00:16:40,465 --> 00:16:43,090
Ви просто використовувати як кронштейн
нульовий позначення, бац, ти там.

345
00:16:43,090 --> 00:16:46,120
І дійсно масиви, як в сторону,
підтримка щось відомо

346
00:16:46,120 --> 00:16:49,240
як випадкового доступу, випадкового доступу
пам'яті, тому що ви можете буквально

347
00:16:49,240 --> 00:16:50,284
перейти в будь одному місці.

348
00:16:50,284 --> 00:16:52,700
Ми можемо зробити це ще простіше
ми можемо переміститися до нульової тижня

349
00:16:52,700 --> 00:16:53,900
коли ми зробили нуля.

350
00:16:53,900 --> 00:16:59,707
Скільки часу буде потрібно для
кажуть блок в порожньому виконати?

351
00:16:59,707 --> 00:17:00,790
Просто постійна часу, чи не так?

352
00:17:00,790 --> 00:17:03,960
Скажи що-небудь, скажімо
то, це не має значення

353
00:17:03,960 --> 00:17:07,359
як великі подряпини світ, це завжди
збирається взяти таку ж кількість часу

354
00:17:07,359 --> 00:17:08,490
просто сказати щось.

355
00:17:08,490 --> 00:17:11,089
>> Так ось постійна часу,
але те, що зворотна сторона?

356
00:17:11,089 --> 00:17:13,030
Якби це було верхня
кордону, що, якщо ми хочемо

357
00:17:13,030 --> 00:17:17,089
для опису нижні межі
наших алгоритмів час роботи?

358
00:17:17,089 --> 00:17:19,852
Майже кращому випадку
потенційно, якщо хочете,

359
00:17:19,852 --> 00:17:23,060
хоча ці терміни можна застосувати до кращих
Випадки, гірших випадках середні випадки більше

360
00:17:23,060 --> 00:17:26,359
взагалі, але давайте просто зосередитися
на нижніх меж в цілому.

361
00:17:26,359 --> 00:17:31,920
Що собою алгоритм, який має
нижня межа п кроків,

362
00:17:31,920 --> 00:17:33,350
або 2n кроків, або кроки 3n?

363
00:17:33,350 --> 00:17:36,241
Деякі фактор п кроків,
ось його нижньої межі.

364
00:17:36,241 --> 00:17:36,740
Да?

365
00:17:36,740 --> 00:17:37,910
>> АУДИТОРІЯ: Bubble роду?

366
00:17:37,910 --> 00:17:41,610
>> СПІКЕР: Bubble роду бере
Ви мінімально п кроків, то чому?

367
00:17:41,610 --> 00:17:42,279
Чому це?

368
00:17:42,279 --> 00:17:45,320
Чому, що почало приходити до вас
інтуїтивно, навіть якщо це не так просто

369
00:17:45,320 --> 00:17:46,530
ще?

370
00:17:46,530 --> 00:17:47,030
Да?

371
00:17:47,030 --> 00:17:47,990
>> АУДИТОРІЯ: [нерозбірливо].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
СПІКЕР: Точно.

374
00:17:52,360 --> 00:17:55,810
В кращому сценарії
бульбашкового сортування, і багато алгоритмів

375
00:17:55,810 --> 00:17:58,769
якщо я вручаю вам вісім осіб
які вже відсортовані,

376
00:17:58,769 --> 00:18:00,560
було б нерозумно
для вас, алгоритм,

377
00:18:00,560 --> 00:18:02,202
щоб йти вперед і назад
більш ніж один раз, чи не так?

378
00:18:02,202 --> 00:18:04,285
Тому що як тільки ви
ходити по списку один раз,

379
00:18:04,285 --> 00:18:08,090
ви повинні розуміти, о, я зробив немає
свопи, цей список сортується, вихід.

380
00:18:08,090 --> 00:18:09,700
Але що відбувається, щоб у вас н кроки.

381
00:18:09,700 --> 00:18:12,033
>> І навпаки, те, що ще один
спосіб думати про це?

382
00:18:12,033 --> 00:18:15,240
Bubble роду є омега,
так би мовити, з п,

383
00:18:15,240 --> 00:18:19,050
бо якщо ви подивіться на
менше, ніж п елементів, то, що

384
00:18:19,050 --> 00:18:23,009
фундаментальне питання є?

385
00:18:23,009 --> 00:18:24,550
Ви не знаєте, якщо це сортуються, право.

386
00:18:24,550 --> 00:18:26,800
Ми люди могли погляд на восьми
люди і бути як, о, це сортується,

387
00:18:26,800 --> 00:18:28,430
що мене не взяли н кроки, але це зробив.

388
00:18:28,430 --> 00:18:30,810
Твої очі, хоча вас вид
від того, мають велике поле зору,

389
00:18:30,810 --> 00:18:33,184
Ви дивилися на восьми елементів,
Ви дивилися на вісім чоловік,

390
00:18:33,184 --> 00:18:34,610
ось вісім кроків ефективно.

391
00:18:34,610 --> 00:18:38,612
І тільки тоді, коли я йду через весь
Список я розумію, так, відсортовано.

392
00:18:38,612 --> 00:18:41,320
Якщо я зупинятися на півдорозі думати, все
Право, це досить упорядковано досі,

393
00:18:41,320 --> 00:18:42,520
які шанси, що це не Починаючи?

394
00:18:42,520 --> 00:18:44,186
Що алгоритми НЕ буде правильним.

395
00:18:44,186 --> 00:18:46,250
Може бути швидше, але неправильно.

396
00:18:46,250 --> 00:18:48,500
>> Так що тепер у нас є спосіб
описи нижні межі,

397
00:18:48,500 --> 00:18:49,710
і те, що про постійне часу?

398
00:18:49,710 --> 00:18:54,565
Що собою алгоритм, який має нижчий
обмеження на час його роботи одного?

399
00:18:54,565 --> 00:18:58,350
1 крок, 2 кроки, 10 кроків, але
постійним, залежить від п,

400
00:18:58,350 --> 00:18:59,310
розмір входу?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Так, в спину.

403
00:19:04,600 --> 00:19:05,309
>> АУДИТОРІЯ: Printf?

404
00:19:05,309 --> 00:19:06,183
СПІКЕР: Що це?

405
00:19:06,183 --> 00:19:07,184
АУДИТОРІЯ: Printf?

406
00:19:07,184 --> 00:19:07,850
СПІКЕР: Printf.

407
00:19:07,850 --> 00:19:08,400
ОК, впевнений.

408
00:19:08,400 --> 00:19:10,720
Таким чином, це займає фіксоване число кроків.

409
00:19:10,720 --> 00:19:13,170
І я повинен now-- тепер,
ми говоримо про C коду

410
00:19:13,170 --> 00:19:16,040
а не до подряпин, то
як скажімо, з Printf,

411
00:19:16,040 --> 00:19:17,710
ми повинні почати, щоб отримати обережним.

412
00:19:17,710 --> 00:19:21,090
Оскільки Е дійсно бере
вхід, це рядок,

413
00:19:21,090 --> 00:19:23,220
і струни у технічно мають довжину.

414
00:19:23,220 --> 00:19:25,530
Так що, якщо ми зараз хочемо, щоб забрати
на вас, якщо ви не заперечуєте,

415
00:19:25,530 --> 00:19:29,430
технічно ми могли стверджувати, що Printf
дійсно бере змінну довжину вхідний,

416
00:19:29,430 --> 00:19:32,270
і, звичайно, це може зайняти більше
Час надрукувати рядок так довго,

417
00:19:32,270 --> 00:19:33,560
що так довго.

418
00:19:33,560 --> 00:19:36,570
>> Так що, якщо ми розглядаємо тільки
сортування та пошук прикладів?

419
00:19:36,570 --> 00:19:40,450
Як щодо Майка Сміта в телефоні
Книга, або бінарний пошук в більш загальному?

420
00:19:40,450 --> 00:19:42,220
В кращому випадку, що може трапитися?

421
00:19:42,220 --> 00:19:45,577
Я відкриваю телефонну книгу і, бац,
є число Майка Сміта.

422
00:19:45,577 --> 00:19:46,660
Я можу зателефонувати йому прямо зараз.

423
00:19:46,660 --> 00:19:49,390
>> Взяв один крок, може бути, два кроки,
але постійне число кроків

424
00:19:49,390 --> 00:19:50,230
якщо мені пощастило.

425
00:19:50,230 --> 00:19:52,570
І, чесно кажучи, ми бачили на
Понеділок ваш однокласник

426
00:19:52,570 --> 00:19:54,710
отримати дуже пощастило два рази поспіль.

427
00:19:54,710 --> 00:19:57,050
І це було дійсно постійної
час в нижніх меж

428
00:19:57,050 --> 00:20:01,280
від алгоритму в питанні знаходження
число 50 за тих, закрито

429
00:20:01,280 --> 00:20:01,830
двері.

430
00:20:01,830 --> 00:20:06,400
>> Тепер, як в сторону, якщо ви виявите,
що і велика O, верхня межа,

431
00:20:06,400 --> 00:20:09,310
і омега, нижня межа,
один в тому ж, що

432
00:20:09,310 --> 00:20:11,830
є та ж формула в
дужки, ви також можете

433
00:20:11,830 --> 00:20:15,170
сказати, просто бути незвичайним,
щось не в тета

434
00:20:15,170 --> 00:20:18,270
н або тета деякого іншого значення.

435
00:20:18,270 --> 00:20:20,661
Це просто означає, коли більша
Виводу і омега однакові.

436
00:20:20,661 --> 00:20:21,910
Тепер щодо вибору роду?

437
00:20:21,910 --> 00:20:23,400
Давайте використовувати цей новий словник.

438
00:20:23,400 --> 00:20:27,407
У селекції роду, то, що ми були
робити знову, і знову, і знову?

439
00:20:27,407 --> 00:20:29,990
Я збирався туди і назад через
список, шукає кого?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Найменше число.

442
00:20:34,730 --> 00:20:37,560
>> Так як багато кроків, як
багато порівнянь я теж

443
00:20:37,560 --> 00:20:43,250
повинні зробити для того, щоб з'ясувати, хто
найменший елемент у списку був?

444
00:20:43,250 --> 00:20:44,437
н мінус 1, чи не так?

445
00:20:44,437 --> 00:20:47,770
Тому що, якщо я просто почати з того, що я перебуваю
враховуючи і я починаю порівнювати його або її,

446
00:20:47,770 --> 00:20:49,519
то йому або їй, як він
або їй, йому або їй, я

447
00:20:49,519 --> 00:20:52,010
може тільки пару елементів
разом н мінус 1 раз.

448
00:20:52,010 --> 00:20:55,630
Так вибір роду ж бере
н мінус 1 кроки в перший раз.

449
00:20:55,630 --> 00:20:59,540
>> Скільки кроків потрібно, щоб я
знайти другий найменший елемент?

450
00:20:59,540 --> 00:21:02,920
н мінус 2, тому що я німий
якщо я продовжую дивитися на ті ж люди,

451
00:21:02,920 --> 00:21:06,280
знову, якщо я вже вибрали його
або її і покласти їх на місце.

452
00:21:06,280 --> 00:21:09,270
І третій крок, н
мінус 3, то п мінус 4.

453
00:21:09,270 --> 00:21:11,020
Ми бачили цю модель
раніше, і насправді

454
00:21:11,020 --> 00:21:13,460
Вибір роду аналогічно
має верхню межу

455
00:21:13,460 --> 00:21:16,210
н квадрат, якщо ми робимо до, що підсумовування.

456
00:21:16,210 --> 00:21:19,790
Яка його нижньої межі, вибір роду?

457
00:21:19,790 --> 00:21:25,350
Мінімально, скільки часу відбору повинні
Сортувати прийняти, як ми визначили його в понеділок?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Пропоную два варіанти.

460
00:21:30,490 --> 00:21:32,360
Може бути, це п, як і раніше.

461
00:21:32,360 --> 00:21:35,040
Може бути, це н квадрат, як це
Зараз як верхня грань.

462
00:21:35,040 --> 00:21:35,874
>> АУДИТОРІЯ: н квадрат.

463
00:21:35,874 --> 00:21:36,664
СПІКЕР: н квадрат.

464
00:21:36,664 --> 00:21:37,368
Чому?

465
00:21:37,368 --> 00:21:40,060
>> АУДИТОРІЯ: Тому що у вас є
визначити [нерозбірливо].

466
00:21:40,060 --> 00:21:41,510
>> СПІКЕР: Точно.

467
00:21:41,510 --> 00:21:45,077
Принаймні, як я визначив вибір роду
це було досить наївно, продовжувати йти,

468
00:21:45,077 --> 00:21:46,160
знайти найменший елемент.

469
00:21:46,160 --> 00:21:47,770
Верніться, знайти найменший елемент.

470
00:21:47,770 --> 00:21:49,490
Верніться, знайти найменший елемент.

471
00:21:49,490 --> 00:21:51,700
Там немає роду
оптимізація в там, що

472
00:21:51,700 --> 00:21:54,350
може дозвольте мені перервати після
всього п або близько кроки.

473
00:21:54,350 --> 00:21:57,080
Так дійсно, вибір
сортувати, омега п квадрат.

474
00:21:57,080 --> 00:22:00,667
>> Як щодо сортування вставками, де я взяв
які мені дали, і тоді я гепнувся його

475
00:22:00,667 --> 00:22:01,750
або її в потрібному місці?

476
00:22:01,750 --> 00:22:04,958
Тоді я продовжив другої людини,
шльопнувся його або її в потрібному місці.

477
00:22:04,958 --> 00:22:07,910
Тоді наступна людина, гепнувся
йому або їй в потрібному місці.

478
00:22:07,910 --> 00:22:10,537
Зверніть увагу, що це дуже
лінійний, так би мовити.

479
00:22:10,537 --> 00:22:12,620
Я прямий, я
не ходить взад і вперед,

480
00:22:12,620 --> 00:22:16,080
Я ніколи не озираючись назад дійсно, але
що відбувається, коли я вставляю його

481
00:22:16,080 --> 00:22:20,302
або їй на початку
Список, як ми зробили в понеділок?

482
00:22:20,302 --> 00:22:21,010
Що відбувається?

483
00:22:21,010 --> 00:22:21,510
Да?

484
00:22:21,510 --> 00:22:23,122
АУДИТОРІЯ: [нерозбірливо].

485
00:22:23,122 --> 00:22:24,830
СПІКЕР: Так,
була заковика, чи не так?

486
00:22:24,830 --> 00:22:26,746
Ви можете пригадати з
Ваші однокласники, якщо вони

487
00:22:26,746 --> 00:22:29,670
робили будь-який рух з
їх ноги, що була операція.

488
00:22:29,670 --> 00:22:33,610
Так що, якщо було три людини, тут і
нова людина належав спосіб там,

489
00:22:33,610 --> 00:22:37,360
на довгий етап, як це, впевнений, він
або вона може просто піти до самого кінця.

490
00:22:37,360 --> 00:22:40,074
Але якщо ми думаємо про
Комп'ютер і масив пам'яті,

491
00:22:40,074 --> 00:22:41,990
ці люди збираються
доведеться перетасувати над

492
00:22:41,990 --> 00:22:43,260
щоб звільнити місце для цієї людини.

493
00:22:43,260 --> 00:22:46,930
І так, що п мінус 1 shufflings,
н мінус 2 shufflings, п

494
00:22:46,930 --> 00:22:50,660
мінус 3 shufflings є тільки почасти
відбувається позаду мене, чи не переді мною

495
00:22:50,660 --> 00:22:52,710
як і раніше, в деякому сенсі.

499
00:22:52,557 --> 00:22:54,640
Тепер, як в сторону, і, як
Ви, можливо, бачили онлайн

500
00:22:54,640 --> 00:22:57,699
якщо ви починаєте колупатися про
види, є так багато різних ті,

501
00:22:57,699 --> 00:22:59,490
там, деякі з них
краще, ніж інші.

502
00:22:59,490 --> 00:23:02,200
Дійсно, bogosort є одним
що забавно дивитися вгору.

503
00:23:02,200 --> 00:23:06,650
Bogosort приймає набір
цифри або сказати колоду карт,

504
00:23:06,650 --> 00:23:09,870
змішає випадковим їх, і
перевіряє, якщо вони відсортовані.

505
00:23:09,870 --> 00:23:12,130
А якщо ні, робить це знову.

506
00:23:12,130 --> 00:23:14,140
А якщо ні, робить це знову.

507
00:23:14,140 --> 00:23:15,440
Якщо ні, робить це знову.

508
00:23:15,440 --> 00:23:17,060
Неймовірно нерозумно.

509
00:23:17,060 --> 00:23:19,520
>> І справді, якщо ви читаєте
як статті Вікіпедії,

510
00:23:19,520 --> 00:23:21,200
його прізвисько нерозумно роду.

511
00:23:21,200 --> 00:23:25,180
Це в кінцевому рахунку спрацює,
сподіваюся, достатньо часу,

512
00:23:25,180 --> 00:23:28,240
але це кількість часу
може зайняти досить багато часу.

513
00:23:28,240 --> 00:23:31,650
Так що, якщо я міг, давайте прискорити речей
в порівнянні з, наприклад Мері Бет раніше,

514
00:23:31,650 --> 00:23:35,150
маючи ще кілька елементів,
але більше двох процесорів.

515
00:23:35,150 --> 00:23:37,100
Дві людини, якщо вам
був би не проти приєднатися до мене.

516
00:23:37,100 --> 00:23:40,972
Як щодо 1 тут, і
давайте НЕ go-- нікого, он там?

517
00:23:40,972 --> 00:23:41,722
Ніхто не там?

518
00:23:41,722 --> 00:23:42,221
Добре.

519
00:23:42,221 --> 00:23:44,190
Ви з чорними
сорочка, да, давай вниз.

520
00:23:44,190 --> 00:23:45,000
Гаразд, як тебе звуть?

521
00:23:45,000 --> 00:23:45,720
>> АУДИТОРІЯ: Пітер.

522
00:23:45,720 --> 00:23:46,100
>> СПІКЕР: Що це?

523
00:23:46,100 --> 00:23:46,766
>> АУДИТОРІЯ: Пітер.

524
00:23:46,766 --> 00:23:49,450
СПІКЕР: Питер, Девід, приємно познайомитися.

525
00:23:49,450 --> 00:23:53,670
Добре, у нас є Петро тут, якщо вам
хочу приїхати на стіл тут.

526
00:23:53,670 --> 00:23:54,550
І як тебе звуть?

527
00:23:54,550 --> 00:23:55,216
>> АУДИТОРІЯ: Олена.

528
00:23:55,216 --> 00:23:55,970
СПІКЕР: Олена.

529
00:23:55,970 --> 00:23:57,030
ОК, приємно познайомитися.

530
00:23:57,030 --> 00:23:58,060
Олена зустрінете Пітера.

531
00:23:58,060 --> 00:23:59,170
Пітер, Олена.

532
00:23:59,170 --> 00:24:02,290
І ми повинні Ендрю
тут також, будь ласка.

533
00:24:02,290 --> 00:24:06,107
І ваше завдання буде
бути впорядкувати колоду карт.

534
00:24:06,107 --> 00:24:08,190
І якщо не знайомі, палуба
карт повинні в кінцевому рахунку,

535
00:24:08,190 --> 00:24:11,064
бути відсортовані дещо як
це де ми зробимо клуби, то

536
00:24:11,064 --> 00:24:13,660
лопати, то серця і
діаманти, від туза як один,

537
00:24:13,660 --> 00:24:15,570
все, аж до короля.

538
00:24:15,570 --> 00:24:20,890
>> Карти я збираюся дати вам
збираються бути 52 в кількості.

539
00:24:20,890 --> 00:24:23,160
Ми збираємося аналогічним
Час у вас, через хвилину.

540
00:24:23,160 --> 00:24:26,410
Ми збираємося кинути Ендрю
на екрані тут,

541
00:24:26,410 --> 00:24:28,170
таким чином, щоб дивитися, як ви робите це.

542
00:24:28,170 --> 00:24:31,070
І таким чином, що все це
тим більше видно,

543
00:24:31,070 --> 00:24:33,490
це карти, які я отримав на Амазонці.

544
00:24:33,490 --> 00:24:42,861
Так вони вже випадково
сортуються, і ми збираємося раз, коли ви.

545
00:24:42,861 --> 00:24:44,610
І ми збираємося
тримати його реальної на цей раз,

546
00:24:44,610 --> 00:24:47,820
так що ми збираємося спробувати чинити тиск на вас
бо інакше це буде отримати утомливо

547
00:24:47,820 --> 00:24:48,460
швидко.

548
00:24:48,460 --> 00:24:53,860
Якби ви могли приступити до впорядкувати 52
елементи разом через деякі засоби, зараз.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> І знову, як ми дивимося ці
хлопці роблять те, що, врешті-решт,

551
00:25:07,180 --> 00:25:10,200
вироблятиме очевидно
Результат, думаю, про дійсно

552
00:25:10,200 --> 00:25:12,962
як вони кожен робить це,
як Ви могли б описати його.

553
00:25:12,962 --> 00:25:15,045
Бо знову ж таки, це
всі процеси, алгоритми

554
00:25:15,045 --> 00:25:17,090
що ми вважаємо само собою зрозумілим, як людина.

555
00:25:17,090 --> 00:25:22,349
Але ви, напевно, давно
інтуїція, задовго до вас, навіть

556
00:25:22,349 --> 00:25:24,390
думав про взяття
інформатика клас вам

557
00:25:24,390 --> 00:25:27,223
можливо, мали інтуїцію з
які вирішити подібні проблеми.

558
00:25:27,223 --> 00:25:29,560
Але як тільки ви визнаєте
патерни і почати

559
00:25:29,560 --> 00:25:32,407
формалізувати дії, за допомогою яких
ви вирішуєте ці проблеми,

560
00:25:32,407 --> 00:25:35,490
Ви знайдете, що ви можете вирішити багато
цікавішим і набагато складніше

561
00:25:35,490 --> 00:25:39,190
проблеми швидко.

562
00:25:39,190 --> 00:25:42,351
Так хто з глядачів, що є
щонайменше, один елемент алгоритму

563
00:25:42,351 --> 00:25:43,350
що вони використовують тут?

564
00:25:43,350 --> 00:25:44,275
>> АУДИТОРІЯ: [нерозбірливо]

565
00:25:44,275 --> 00:25:45,150
СПІКЕР: Що це?

566
00:25:45,150 --> 00:25:47,062
АУДИТОРІЯ: По костюмі.

567
00:25:47,062 --> 00:25:47,770
СПІКЕР: По костюмі.

568
00:25:47,770 --> 00:25:50,630
Отже, спочатку вони кластеризації
всі алмази разом

569
00:25:50,630 --> 00:25:52,560
мабуть, все
серця разом схоже,

570
00:25:52,560 --> 00:25:56,520
і так далі, без дотримання
для чисел на картах.

571
00:25:56,520 --> 00:26:00,900
І тепер вони з'являються, наприклад,
щоб бути їх сортування за номером.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Дуже добре.

574
00:26:08,910 --> 00:26:12,370
>> Гаразд, так що буде
бути останнім кроком, то тут?

575
00:26:12,370 --> 00:26:16,950
Після того, як у нас є чотири відсортовані костюми, що
нам потрібно зробити, щоб чотирьох паль

576
00:26:16,950 --> 00:26:20,059
для досягнення однієї
упорядковано палубу, досить просто?

577
00:26:20,059 --> 00:26:21,350
Так що ми повинні об'єднати їх знову.

578
00:26:21,350 --> 00:26:25,160
>> Таким чином, є цікава ідея, що
знову, гадаю, дуже зрозумілий навіть

579
00:26:25,160 --> 00:26:28,140
якщо ви ніколи б не вдарив
що вид етикетки на ньому.

580
00:26:28,140 --> 00:26:31,900
Це фундаментальне поняття ділення
проблема не в половину цього часу,

581
00:26:31,900 --> 00:26:33,410
але принаймні на чотири частини.

582
00:26:33,410 --> 00:26:36,810
Рішення в значній мірі
принципово ідентичні проблеми

583
00:26:36,810 --> 00:26:40,480
ізольовано один від одного,
, А потім об'єднати результати.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
І, відмінно, зроблено.

586
00:26:50,140 --> 00:26:52,140
Добре, велика кругла
оплесків, якщо ми могли.

587
00:26:52,140 --> 00:26:56,480
>> [Оплески]

588
00:26:56,480 --> 00:26:59,740
>> СПІКЕР: Я поняття не маю, що ви будете
робити з ними, але тут ви йдете.

589
00:26:59,740 --> 00:27:01,690
Спасибо большое.

590
00:27:01,690 --> 00:27:04,660
Отже, давайте подивимося, дві хвилини
і вісім секунд,

591
00:27:04,660 --> 00:27:07,490
якщо ви хочете, щоб битися зі своїми друзями.

592
00:27:07,490 --> 00:27:12,160
Що ж тоді буде
бути відняти від цього

593
00:27:12,160 --> 00:27:13,830
що ми можемо використовувати більш загальному?

594
00:27:13,830 --> 00:27:16,080
Ну, думаю, назад в
Цей масив чисел,

595
00:27:16,080 --> 00:27:19,060
і згадую зараз, щоб деякі з
псевдокод ми написали в минулому,

596
00:27:19,060 --> 00:27:22,080
і це було команд для
вирішенні проблеми телефонної книги.

597
00:27:22,080 --> 00:27:25,150
Причому в псевдокода I
перерахував більш методичну шлях

598
00:27:25,150 --> 00:27:28,400
описи того, як я зробив дуже інтуїтивний
людина алгоритм ділення телефон

599
00:27:28,400 --> 00:27:31,650
Книга в половині, повторіть, повторюю, повторюю,
поки я не знайду така людина, як Майк Сміт,

600
00:27:31,650 --> 00:27:33,790
якщо він дійсно перебуває в телефонній книзі.

601
00:27:33,790 --> 00:27:37,610
>> Але я почасти звик, що я називаю
дуже ітеративний підхід тут,

602
00:27:37,610 --> 00:27:42,160
зокрема повідомлення лінія 8 і рядок 11.

603
00:27:42,160 --> 00:27:46,750
Ті, є свідченням ітеративний
підхід, перекручування підхід,

604
00:27:46,750 --> 00:27:49,040
бо це саме
поведінку вони викликають.

605
00:27:49,040 --> 00:27:52,910
Ці лінії як би, йдуть в
Лінія три, і ви можете роду

606
00:27:52,910 --> 00:27:55,140
думати про те, що у вашому
уявним поглядом як петля.

607
00:27:55,140 --> 00:27:59,080
Це говорю вам, щоб повернутися до кроку
три і повторюю, знову, і знову,

608
00:27:59,080 --> 00:28:00,010
і знову.

609
00:28:00,010 --> 00:28:04,410
>> Але що, якщо ми використовувати ключову ідею
тут, що ми зробили не востаннє,

610
00:28:04,410 --> 00:28:10,280
і спростити лінії 8 і
рядок 11 і їхні сусіди

611
00:28:10,280 --> 00:28:12,840
як тільки це, в жовтий колір.

612
00:28:12,840 --> 00:28:16,480
Це не принципово скорочення
псевдокод дуже багато,

613
00:28:16,480 --> 00:28:20,530
але це в корені міняє
природа мого алгоритму.

614
00:28:20,530 --> 00:28:24,220
Те, що я зараз говорю
в пункті 7, на етапі 10,

615
00:28:24,220 --> 00:28:29,140
є пошук Mike
в тому ж чином,

616
00:28:29,140 --> 00:28:31,580
але тільки в лівій
половина або права половина.

617
00:28:31,580 --> 00:28:33,420
>> Таким чином, іншими словами, якщо
Я починаю з кроком один,

618
00:28:33,420 --> 00:28:36,150
підібрати телефонну книгу, відкритий до середини
з телефонної книги, подивитися на імена,

619
00:28:36,150 --> 00:28:39,010
якщо Сміт є одним
звуть, телефонуйте Майк, ще

620
00:28:39,010 --> 00:28:44,340
якщо Сміт раніше в книзі, крок сім
шукати Майка в лівій половині книги.

621
00:28:44,340 --> 00:28:47,130
Але що це за відчуття,
це залишивши мене висить, чи не так?

622
00:28:47,130 --> 00:28:49,240
В жовтий, є
інструкція, але як я можу

623
00:28:49,240 --> 00:28:51,870
шукати Майка в лівій
половина телефонній книзі?

624
00:28:51,870 --> 00:28:54,210
Де я повинен
Алгоритм, з якою я

625
00:28:54,210 --> 00:28:57,100
може шукати таку людину, як Майк Сміт?

626
00:28:57,100 --> 00:28:58,980
Ну, це дивлячись нам в очі.

627
00:28:58,980 --> 00:29:03,090
Я можу буквально використовувати точно такий же
Програма ефективно, підійшовши до верхньої

628
00:29:03,090 --> 00:29:06,490
знову і знову працює
ті ж рядки коду.

629
00:29:06,490 --> 00:29:10,610
>> Таким чином, навіть при тому, що це має почуватися
як трохи циклічного визначення

630
00:29:10,610 --> 00:29:13,480
де ви відповідаючи хто-
Питання по тільки вид з проханням

631
00:29:13,480 --> 00:29:15,990
те ж питання знову,
як, чому, чому, чому?

632
00:29:15,990 --> 00:29:21,580
Реальність така, тому що ми жорстко
пару спеціальних ліній, крок 4,

633
00:29:21,580 --> 00:29:25,320
що, якщо, і крок 12, які
ефективно інша гілка,

634
00:29:25,320 --> 00:29:30,120
тому що у нас ці заходи по усуненню вузьких,
цей алгоритм буде припинена, якщо ми

635
00:29:30,120 --> 00:29:32,050
знайти Майка, або якщо ми не робимо.

636
00:29:32,050 --> 00:29:36,810
Але в кроці 7 і 10 тепер, у нас є
що ми будемо називати рекурсивний алгоритм.

637
00:29:36,810 --> 00:29:40,420
І рекурсія дійсно потужна ідея
це трохи запаморочливим спочатку,

638
00:29:40,420 --> 00:29:42,500
що тепер ми можемо застосувати такий спосіб.

639
00:29:42,500 --> 00:29:46,600
>> Злиття роду буде останнім видом, який
ми дивимося на, принаймні, в класі формально.

640
00:29:46,600 --> 00:29:50,040
І це в корені відрізняється
від тих трьох останніх, і, звичайно,

641
00:29:50,040 --> 00:29:52,140
Останні чотири, якщо ми включимо bogosort.

642
00:29:52,140 --> 00:29:54,810
Ось псевдокод для сортування злиттям.

643
00:29:54,810 --> 00:30:00,170
Коли на вході п елементів, тому, враховуючи,
масив розміру N, якщо N менше 2,

644
00:30:00,170 --> 00:30:01,040
повернутися.

645
00:30:01,040 --> 00:30:03,610
Так чому ж я, що
розсудливість перевірити в першу чергу?

646
00:30:03,610 --> 00:30:09,477
Що мається на увазі якщо зраджу тебе
масив, довжина якого н менше 2?

647
00:30:09,477 --> 00:30:11,060
Це вже відсортовані, очевидно, не так?

648
00:30:11,060 --> 00:30:13,640
Оскільки список або має
один елемент, який є тривіальним

649
00:30:13,640 --> 00:30:15,180
сортуються, тому що це
Єдине, що є.

650
00:30:15,180 --> 00:30:18,138
Або, це через нульового розміру, що означає
немає нічого, щоб розібратися, так за своєю природою

651
00:30:18,138 --> 00:30:18,720
сортується.

652
00:30:18,720 --> 00:30:20,410
Там просто нічого поганого там.

653
00:30:20,410 --> 00:30:22,310
Так ось наша так звана базовий варіант.

654
00:30:22,310 --> 00:30:24,440
>> Тобто близький по духу
до того, що ми зробили з Майком.

655
00:30:24,440 --> 00:30:26,023
Якщо Майк в телефонній книзі, зателефонуйте йому.

656
00:30:26,023 --> 00:30:27,740
Якщо його там немає, здаватися.

657
00:30:27,740 --> 00:30:31,240
Це так званий базовий варіант, щоб переконатися
Цей алгоритм в кінці дня

658
00:30:31,240 --> 00:30:33,540
зупиниться в певних обставинах.

659
00:30:33,540 --> 00:30:37,890
>> Але ось стрибок віри зараз, інакше,
сортувати ліву половину елементів,

660
00:30:37,890 --> 00:30:39,740
потім відсортувати право
половина елементів,

661
00:30:39,740 --> 00:30:41,189
а потім об'єднати відсортовані половинки.

662
00:30:41,189 --> 00:30:43,230
І ось, коли він відчуває себе
як ми Copping з.

663
00:30:43,230 --> 00:30:46,900
Я попросив вас розібратися
п елементів, і я

664
00:30:46,900 --> 00:30:50,712
кажучи, добре, зробіть це за допомогою сортування
вліво і сортування право.

665
00:30:50,712 --> 00:30:52,420
Але я говорю одне
Інша справа, і це

666
00:30:52,420 --> 00:30:55,530
є ключовою темою здається
в інтуїції досі,

667
00:30:55,530 --> 00:30:57,380
Тобто цей третій етап злиття.

668
00:30:57,380 --> 00:31:00,430
Який хоча його
здається настільки дурний в дусі,

669
00:31:00,430 --> 00:31:02,320
як тільки об'єднати речі
разом, здається,

670
00:31:02,320 --> 00:31:05,380
є ключовим кроком на шляху
збірка з двох проблем, які

671
00:31:05,380 --> 00:31:07,330
в кінцевому рахунку, були розділені на дві частини.

672
00:31:07,330 --> 00:31:12,090
>> Так сортування злиттям, давайте зробимо це, якщо ви будете
гумор мене, ще одним демонстрації,

673
00:31:12,090 --> 00:31:14,730
просто так, що у нас є деякі
Номери працювати.

674
00:31:14,730 --> 00:31:19,470
Чи можу я обміняти вісім стрес
м'ячі для восьми осіб?

675
00:31:19,470 --> 00:31:29,320
Гаразд, а як щодо вас три, ви чотири
в цьому розділі, п'ять, шість, і давайте

676
00:31:29,320 --> 00:31:30,720
у 7, 8, давай до.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
ОК, да ОК.

679
00:31:36,520 --> 00:31:38,640
Мінус 8, там ми йдемо, плюс 1.

680
00:31:38,640 --> 00:31:39,150
Відмінно.

681
00:31:39,150 --> 00:31:42,000
Гаразд давай, давайте
швидко дати вам цифри.

682
00:31:42,000 --> 00:31:50,800
Номер два, номер три, номер чотири,
номер п'ять, шість, сім, вісім.

683
00:31:50,800 --> 00:31:52,140
Я правильно зробив вісім на цей раз.

684
00:31:52,140 --> 00:31:56,390
>> ОК, так що йти вперед, якби міг, і
давайте сортувати в первісному порядку

685
00:31:56,390 --> 00:31:59,810
що ми повинні були вчора який виглядав
як це, якщо ви не заперечуєте.

686
00:31:59,810 --> 00:32:03,620
І давайте зробимо це перед столом.

687
00:32:03,620 --> 00:32:06,510
Гаразд, так сортування злиттям.

688
00:32:06,510 --> 00:32:08,820
Це де це відбувається
щоб отримати вид цікавого,

689
00:32:08,820 --> 00:32:12,800
бо я, здається, даючи себе
стільки менше інформації сьогодні.

690
00:32:12,800 --> 00:32:15,149
>> Так сортування злиттям в першу чергу
на вході п елементів,

691
00:32:15,149 --> 00:32:18,440
і, очевидно, не менше двох, це
вісім, так що я ще трохи попрацювати.

692
00:32:18,440 --> 00:32:21,140
Так що тепер подумки ми як клас
тепер в ще галузі,

693
00:32:21,140 --> 00:32:22,540
що означає три кроки.

694
00:32:22,540 --> 00:32:25,017
По-перше, у мене є для сортування
Ліва половина елементів.

695
00:32:25,017 --> 00:32:26,350
Так як же я йти про це?

696
00:32:26,350 --> 00:32:28,950
Ну, я збираюся вид
подумки розділити список тут,

697
00:32:28,950 --> 00:32:30,700
Ви не повинні
фізично рухатися, і я

698
00:32:30,700 --> 00:32:33,180
збираюся зосередитися тільки на
Ліва половина елементів тут.

699
00:32:33,180 --> 00:32:36,770
Так як я можу йти про сортування
Список тепер розміру чотири?

700
00:32:36,770 --> 00:32:38,730
Що мій алгоритм?

701
00:32:38,730 --> 00:32:42,580
Спочатку я перевірити це н менше двох, ні,
так що я приступити до ще блок знову.

702
00:32:42,580 --> 00:32:43,900
Сортувати залишив половину елементів.

703
00:32:43,900 --> 00:32:45,608
>> Так що тепер знову, подумки,
і це, коли

704
00:32:45,608 --> 00:32:49,550
Ви повинні нараховуватися багато
психічне історія, якщо ви будете.

705
00:32:49,550 --> 00:32:51,940
Тепер я сортуванні ліву
половина лівій половині.

706
00:32:51,940 --> 00:32:57,000
Гаразд, так що тепер я називаю ж злиття
алгоритм сортування, є н менше двох?

707
00:32:57,000 --> 00:33:00,590
Ні, це два, так що я повинен розібратися
ліва половина, а права половина.

708
00:33:00,590 --> 00:33:02,042
Тому тут ми йдемо, сортувати ліву половину.

709
00:33:02,042 --> 00:33:03,750
Чому б вам просто не
зробіть один крок вперед.

710
00:33:03,750 --> 00:33:04,415
Як тебе звуть?

711
00:33:04,415 --> 00:33:04,860
>> АУДИТОРІЯ: Даррен.

712
00:33:04,860 --> 00:33:05,260
>> СПІКЕР: Ден.

713
00:33:05,260 --> 00:33:06,040
Ден вийшов вперед.

714
00:33:06,040 --> 00:33:06,748
>> АУДИТОРІЯ: Даррен.

715
00:33:06,748 --> 00:33:09,000
, Зроблено Даррен: СПІКЕР.

716
00:33:09,000 --> 00:33:10,090
Ви сказали Даррен або Ден?

717
00:33:10,090 --> 00:33:10,550
>> АУДИТОРІЯ: Даррен.

718
00:33:10,550 --> 00:33:11,216
>> СПІКЕР: Даррен.

719
00:33:11,216 --> 00:33:14,422
ОК, Даррен активізував
вперед, і він тепер сортується.

720
00:33:14,422 --> 00:33:16,130
І це майже
безглуздим вимога, чи не так?

721
00:33:16,130 --> 00:33:18,862
Я дійсно не здається, досягнення
нічого, але давайте перейдемо.

722
00:33:18,862 --> 00:33:20,820
Тепер дозвольте мені розібратися право
половина елементів.

723
00:33:20,820 --> 00:33:21,200
Як тебе звуть?

724
00:33:21,200 --> 00:33:21,690
>> АУДИТОРІЯ: Люк.

725
00:33:21,690 --> 00:33:22,273
>> СПІКЕР: Люк.

726
00:33:22,273 --> 00:33:23,400
Давай, крок вперед.

727
00:33:23,400 --> 00:33:25,640
Утрату, я упорядковано Луки.

728
00:33:25,640 --> 00:33:28,570
Ліва половина тепер сортується та
права половина тепер сортується,

729
00:33:28,570 --> 00:33:30,770
але знову ж таки, є ключовий крок тут.

730
00:33:30,770 --> 00:33:32,940
Що мені в наступному потрібно зробити?

731
00:33:32,940 --> 00:33:33,941
Злиття відсортовані половинки.

732
00:33:33,941 --> 00:33:36,648
Тепер ми збираємося просто
все назад і вперед на цьому шляху,

733
00:33:36,648 --> 00:33:38,620
бо я начебто потрібно
деякі робочий простір.

734
00:33:38,620 --> 00:33:40,411
Це майже як вони
хлопці на столі,

735
00:33:40,411 --> 00:33:42,460
і мені потрібна кімната
переміщати їх на.

736
00:33:42,460 --> 00:33:44,170
Так що я збираюся об'єднати
ви, хлопці, подивившись

737
00:33:44,170 --> 00:33:45,960
на лівій половині і в правій половині.

738
00:33:45,960 --> 00:33:48,740
І який, очевидно, стоїть на першому місці,
ліва половина або права половина?

739
00:33:48,740 --> 00:33:52,710
Так права половина, так що давайте рухатися Луки над
тут у вихідне положення Даррена.

740
00:33:52,710 --> 00:33:57,640
І тепер, щоб об'єднати їх ліву половину в,
Даррен збирається рухатися прямо там.

741
00:33:57,640 --> 00:33:59,750
>> Так почувається майже
бульбашкового сортування ефект,

742
00:33:59,750 --> 00:34:02,482
але моє фундаментальне алгоритм,
дуже різні на цей раз.

743
00:34:02,482 --> 00:34:04,815
Але тепер, де речі стають
трохи дратує, бо вас

744
00:34:04,815 --> 00:34:06,810
повинні перемотати розумово
звідки я зупинився.

745
00:34:06,810 --> 00:34:09,893
Я щойно злив відсортовані половинки,
який означає, що я, де в моєму алгоритмі?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Я повинен розібратися праву половину, чи не так?

748
00:34:13,770 --> 00:34:15,910
>> Якщо ви перемотати, буквально
на відео, ви будете

749
00:34:15,910 --> 00:34:18,339
бачити, що ми дісталися до цього
точка Луки і Дарреном

750
00:34:18,339 --> 00:34:21,370
шляхом сортування лівий
половина лівій половині.

751
00:34:21,370 --> 00:34:23,430
Тоді ми об'єднали ті,
відсортовані половинки, які

752
00:34:23,430 --> 00:34:27,941
означає наступний крок є свого роду
Права половина лівій половині.

753
00:34:27,941 --> 00:34:29,649
Гаразд, так що давайте
зробити це швидше.

754
00:34:29,649 --> 00:34:33,282
Гаразд, шість, я збираюся стверджувати,
Ви тепер сортуються, давай вперед.

755
00:34:33,282 --> 00:34:33,990
Як тебе звуть?

756
00:34:33,990 --> 00:34:34,589
>> АУДИТОРІЯ: Адріано.

757
00:34:34,589 --> 00:34:35,200
>> СПІКЕР: Адріано.

758
00:34:35,200 --> 00:34:36,010
Адріано тепер сортується.

759
00:34:36,010 --> 00:34:36,450
І як тебе звуть?

760
00:34:36,450 --> 00:34:37,080
>> АУДИТОРІЯ: Алекс.

761
00:34:37,080 --> 00:34:38,379
>> СПІКЕР: Алекс тепер сортується.

762
00:34:38,379 --> 00:34:40,750
Ліва половина, права половина,
що останній крок?

763
00:34:40,750 --> 00:34:41,250
Злиття.

764
00:34:41,250 --> 00:34:44,310
Досить тривіально, так що я
збирається об'єднати в шість,

765
00:34:44,310 --> 00:34:46,930
зробити крок назад,
вісім, зробити крок назад.

766
00:34:46,930 --> 00:34:49,530
А тепер зверніть увагу, це
корисно винос, що

767
00:34:49,530 --> 00:34:53,930
Зараз правда про лівій половині
Список, незалежно від того, як ми почали?

768
00:34:53,930 --> 00:34:55,090
Це сортується.

769
00:34:55,090 --> 00:34:57,750
>> Тепер це не відсортовані в
великій схемі речей,

770
00:34:57,750 --> 00:35:00,250
але це сортується незалежно один від одного
з іншої половини.

771
00:35:00,250 --> 00:35:04,100
Тепер те, що крок я на, якщо я продовжу
перемотування, як історія почалася?

772
00:35:04,100 --> 00:35:05,680
Тепер у мене є для сортування праву половину.

773
00:35:05,680 --> 00:35:07,630
Так що тепер ми шлях назад в
початок історії,

774
00:35:07,630 --> 00:35:08,921
і давайте зробимо це швидше.

775
00:35:08,921 --> 00:35:11,320
Так що я збираюся розібратися
Права половина усього списку.

776
00:35:11,320 --> 00:35:13,060
Який наступний крок?

777
00:35:13,060 --> 00:35:15,840
Сортувати ліву половину правій половині.

778
00:35:15,840 --> 00:35:18,715
Сортувати ліву половину
Ліва половина правій половині.

779
00:35:18,715 --> 00:35:19,590
І як тебе звуть?

780
00:35:19,590 --> 00:35:20,230
>> АУДИТОРІЯ: Омар.

781
00:35:20,230 --> 00:35:21,970
>> СПІКЕР: Омар, крок вперед, зробити.

782
00:35:21,970 --> 00:35:22,860
Ліва половина сортується.

783
00:35:22,860 --> 00:35:23,330
І як тебе звуть?

784
00:35:23,330 --> 00:35:23,820
>> АУДИТОРІЯ: Кріс.

785
00:35:23,820 --> 00:35:25,620
>> СПІКЕР: Кріс, зробити крок
вперед, ви тепер сортуються.

786
00:35:25,620 --> 00:35:27,010
Що ключовий крок зараз?

787
00:35:27,010 --> 00:35:27,510
Злиття.

788
00:35:27,510 --> 00:35:30,509
Так ніхто не збирається зливатися в місці
тут, якби ви могли зробити крок назад,

789
00:35:30,509 --> 00:35:32,930
і три збирається
зробити крок назад, зливаються.

790
00:35:32,930 --> 00:35:38,080
Так ліва половина
Права половина, тепер сортується.

791
00:35:38,080 --> 00:35:41,747
Чесно кажучи, цей алгоритм відчуває, як ми
витрачаєте набагато більше часу, ніж раніше,

792
00:35:41,747 --> 00:35:44,830
але якби ми зробили це в режимі реального часу, ми будемо
бачити те, що їжі додому буде.

793
00:35:44,830 --> 00:35:47,970
Отже, я тут, прямо
половина правій половині,

794
00:35:47,970 --> 00:35:50,170
дозвольте мені йти вперед і відсортувати ліву половину.

795
00:35:50,170 --> 00:35:51,482
Крок вперед, як тебе звуть?

796
00:35:51,482 --> 00:35:52,190
АУДИТОРІЯ: Ремсі.

797
00:35:52,190 --> 00:35:53,210
СПІКЕР: Ремсі тепер сортується.

798
00:35:53,210 --> 00:35:53,570
Як тебе звуть?

799
00:35:53,570 --> 00:35:54,200
>> АУДИТОРІЯ: Марина.

800
00:35:54,200 --> 00:35:57,033
>> СПІКЕР: Марина тепер сортується як
добре, якщо ви берете один крок вперед.

801
00:35:57,033 --> 00:36:00,690
Ключ крок тут тепер зливаються, я
збирається зривати з моїх двох списків,

802
00:36:00,690 --> 00:36:01,720
зліва і справа.

803
00:36:01,720 --> 00:36:05,150
П'ять прийде першим,
і сім прийде наступний.

804
00:36:05,150 --> 00:36:06,410
І знову ж таки, це не випадково.

805
00:36:06,410 --> 00:36:08,535
Той факт, що вони беруть
кроки вперед і назад

806
00:36:08,535 --> 00:36:12,997
призначена для представлення, що ми не можемо
зробити цей алгоритм на місці, як легко

807
00:36:12,997 --> 00:36:15,830
як бульбашкового сортування та відбору роду,
і сортування вставками, де ми просто

808
00:36:15,830 --> 00:36:16,960
зберігається заміни людей.

809
00:36:16,960 --> 00:36:19,940
Я буквально потрібно свого роду
з паперу для заміток, в яких

810
00:36:19,940 --> 00:36:21,827
поставити цих людей
в той час як я роблю злиття,

811
00:36:21,827 --> 00:36:23,410
і тоді я можу покласти їх на місце.

812
00:36:23,410 --> 00:36:27,260
І це ключовий момент, тому я використовую
Новий ресурс, простір, не тільки час.

813
00:36:27,260 --> 00:36:28,270
>> ОК, це дивно.

814
00:36:28,270 --> 00:36:32,050
Ліва половина сортується, правій половині
відсортоване, тепер, коли ключ злиття крок.

815
00:36:32,050 --> 00:36:33,450
Як я буду об'єднати це?

816
00:36:33,450 --> 00:36:35,470
Так що якщо ви будете слідувати моїм
ліва рука і права рука,

817
00:36:35,470 --> 00:36:38,930
Я збираюся вказати ліву руку
в лівій половині, моя права рука

818
00:36:38,930 --> 00:36:42,680
в правій половині, і тепер я повинен
вирішити, крок за кроком, якого до злиття в.

819
00:36:42,680 --> 00:36:44,650
Хто очевидно на першому місці?

820
00:36:44,650 --> 00:36:45,150
Номер один.

821
00:36:45,150 --> 00:36:47,327
Так йди сюди,
ось наш сверхоперативной.

822
00:36:47,327 --> 00:36:49,910
Так що тепер номер один, і повідомлення
що я буду робити зі своєю правою рукою,

823
00:36:49,910 --> 00:36:54,152
Я збираюся рухати правою рукою один
переступити вказати номер три,

824
00:36:54,152 --> 00:36:55,860
і тепер я повинен зробити
те ж саме рішення.

825
00:36:55,860 --> 00:36:58,387
А насправді коштують права в
Фронт Луки тут, якби ви могли,

826
00:36:58,387 --> 00:36:59,720
бо це наш сверхоперативной.

827
00:36:59,720 --> 00:37:00,610
Так хто ж далі?

828
00:37:00,610 --> 00:37:05,000
У нас є Луки з номер два
або Кріс з номером три.

829
00:37:05,000 --> 00:37:07,460
Очевидно Луки, число
два, так що ви прийшли сюди.

830
00:37:07,460 --> 00:37:11,270
>> Але моя ліва рука тепер збирається
бути збільшено, щоб вказати на Даррена,

831
00:37:11,270 --> 00:37:15,160
і ось ключ забрати з
злиття, я збираюся продовжувати це робити,

832
00:37:15,160 --> 00:37:17,340
очевидно, якщо вас вид
з слідувати логіці.

833
00:37:17,340 --> 00:37:19,670
Але мої руки ніколи не
збирається йти у зворотному напрямку,

834
00:37:19,670 --> 00:37:23,861
який означає, що я тільки коли перехід до
зліва, з моєї процесу злиття,

835
00:37:23,861 --> 00:37:26,360
і що буде ключем до
наш аналіз через хвилину.

836
00:37:26,360 --> 00:37:27,859
>> А тепер давайте закінчити це швидко.

837
00:37:27,859 --> 00:37:31,650
Так три буде далі,
потім чотири буде далі,

838
00:37:31,650 --> 00:37:38,750
і тепер п'ять буде далі, то шість,
і сім, і, нарешті, вісім.

839
00:37:38,750 --> 00:37:42,960
За відчуттями самого повільного алгоритму
поки немає, але не, якщо ми насправді

840
00:37:42,960 --> 00:37:45,510
запустити його на такий же
тактової частоти, таким чином, щоб

841
00:37:45,510 --> 00:37:48,106
кажуть, з тим же
цокає годинник, як і раніше.

842
00:37:48,106 --> 00:37:48,605
Чому?

843
00:37:48,605 --> 00:37:51,100
Ну, давайте
подивитися на кінцевий результат.

844
00:37:51,100 --> 00:37:56,990
>> Давайте повернемося сюди, хай мене
підтягнути демонстрацію візуально

845
00:37:56,990 --> 00:37:59,030
про те, що ми тільки що зробили.

846
00:37:59,030 --> 00:38:06,110
Масштабування тут, на цьому
сторінка тут, розповідаючи Firefox

847
00:38:06,110 --> 00:38:08,200
що ми хочемо стояти в черзі
в цій рамки, давайте

848
00:38:08,200 --> 00:38:11,260
сказати бульбашкового сортування, з якою
ми тепер добре знайомі,

849
00:38:11,260 --> 00:38:14,130
Вибір роду, що є ще одним
досить просто один,

850
00:38:14,130 --> 00:38:18,250
і тепер сьогоднішня сортування злиттям, яка
буде нашим кліматичні закінчення.

851
00:38:18,250 --> 00:38:21,530
Причина це зайняло так багато більше
тут з людьми і мені усно це,

852
00:38:21,530 --> 00:38:23,480
Очевидно, я пояснюю кожен крок.

853
00:38:23,480 --> 00:38:26,920
Але якщо ви просто виконати це, набагато
як ми робили бульбашкового сортування та вибору

854
00:38:26,920 --> 00:38:30,890
сортування не тільки візуально, годинники
наскільки більш ефективно

855
00:38:30,890 --> 00:38:33,330
це залучення в роботу
поділ і завоювання

856
00:38:33,330 --> 00:38:39,150
може бути при застосуванні до набору даних, це
навіть не розмір вісім, але навіть багато,

857
00:38:39,150 --> 00:38:39,970
набагато більше.

858
00:38:39,970 --> 00:38:44,585
Я даю вам сортування злиттям, пліч-о
стороні з цими іншими алгоритмами.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Це буде отримати боляче
швидко, і кінцівка

861
00:38:58,530 --> 00:39:00,890
не дуже кліматичні,
вони просто в кінцевому підсумку сортуються.

862
00:39:00,890 --> 00:39:05,280
Але ключ відняти те, що
Подивіться, наскільки швидше сортування злиттям

863
00:39:05,280 --> 00:39:08,110
було, якщо ви не думаєте, що я
тільки почасти возитися з вами.

864
00:39:08,110 --> 00:39:13,100
Якщо ми робимо це в останній раз,
давайте Перезавантажити, давайте повернемося

865
00:39:13,100 --> 00:39:14,960
і вибрати бульбашкового сортування,
і тільки для ударів,

866
00:39:14,960 --> 00:39:17,330
давайте виберемо вставку
сортувати, для рівного рахунку.

867
00:39:17,330 --> 00:39:20,020
І на цей раз знову, давайте
вибрати сортування злиттям і давайте

868
00:39:20,020 --> 00:39:21,595
реально працювати ці пліч-о-пліч.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> І це не так, насправді, щаслива випадковість.

871
00:39:26,930 --> 00:39:31,140
Те, що я ефективно зробити це у мене є
розділив свій вклад в половині, знову,

872
00:39:31,140 --> 00:39:32,240
і знову, і знову.

873
00:39:32,240 --> 00:39:35,590
І є тільки так багато раз, ви можете
розділити вхід навпіл, зліва

874
00:39:35,590 --> 00:39:36,240
і право.

875
00:39:36,240 --> 00:39:39,425
Що формула, що ми весь час бачу
, Який описує поділ навпіл

876
00:39:39,425 --> 00:39:41,050
знову, і знову, і знову, і знову?

877
00:39:41,050 --> 00:39:41,890
>> АУДИТОРІЯ: Увійти н.

878
00:39:41,890 --> 00:39:42,760
>> СПІКЕР: Увійти н.

879
00:39:42,760 --> 00:39:46,300
Але тоді є ще один ключовий крок,
цей алгоритм не ввійти п кроків.

880
00:39:46,300 --> 00:39:48,992
Якби це було тільки увійти п кроків,
ми були б у тій же проблеми

881
00:39:48,992 --> 00:39:51,200
як і раніше, де ми не можемо бути
що все в сортуються.

882
00:39:51,200 --> 00:39:54,480
Ви повинні мінімально подивитися на п елементів
щоб переконатися, що п елементів сортуються,

883
00:39:54,480 --> 00:39:55,950
в іншому випадку це стрибок віри.

884
00:39:55,950 --> 00:39:59,810
>> Так що це мінімально журнал п кроків, але
що з цього приводу ключовою стадії злиття

885
00:39:59,810 --> 00:40:04,370
де я злилися моя ліва половина і право
половина і пройшовся по сцені?

886
00:40:04,370 --> 00:40:06,980
Скільки кроків у тому, що для злиття?

887
00:40:06,980 --> 00:40:10,150
Це п, але я не зробив усього
об'єднати в останній раз.

888
00:40:10,150 --> 00:40:15,089
На кожній з цих вкладених викликів, на кожному
з тих, вкладених злиттів, я до сих пір сортуються.

889
00:40:15,089 --> 00:40:18,380
Я об'єднані ці два хлопця, то ці два
хлопці, то ці два хлопця і так далі.

890
00:40:18,380 --> 00:40:19,955
>> Так що я злиття знову, і знову.

891
00:40:19,955 --> 00:40:20,580
Скільки разів?

892
00:40:20,580 --> 00:40:23,510
Так що кожен раз я розділив
Список навпіл, я зробив злиття.

893
00:40:23,510 --> 00:40:25,460
Розбийте список навпіл, зробити злиття.

894
00:40:25,460 --> 00:40:28,570
Так що, якщо розділяє список
можна зробити журнал п раз,

895
00:40:28,570 --> 00:40:33,880
і злиття в кінцевому рахунку, приймає п
кроки, що може бути зараз верхня

896
00:40:33,880 --> 00:40:37,000
обмеження на працюючому
Час нашого алгоритму?

897
00:40:37,000 --> 00:40:37,980
н увійти н.

898
00:40:37,980 --> 00:40:40,560
>> І справді, ось що
ми досягли тут.

899
00:40:40,560 --> 00:40:44,650
Так почуття, що ви бачите візуально, коли
ці три речі працювати пліч-о-пліч

900
00:40:44,650 --> 00:40:47,930
є н квадрат проти п
квадрат проти н журналу п.

901
00:40:47,930 --> 00:40:51,010
Які принципово ми побачимо,
не тільки сьогодні, але в майбутньому,

902
00:40:51,010 --> 00:40:52,760
набагато, набагато швидше.

903
00:40:52,760 --> 00:40:56,010
Оплески для цих хлопців,
Я винагородить їх зі стресом куль.

904
00:40:56,010 --> 00:41:00,260
Давайте перервати тут сьогодні, і
ми будемо бачити вас в понеділок.

905
00:41:00,260 --> 00:41:02,255