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
Малан ДАВИД: У реду.

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
>> Дакле, н на квадрат.

32
00:01:28,980 --> 00:01:30,402
А шта је н?

33
00:01:30,402 --> 00:01:31,650
>> ПУБЛИКА: Број елемената.

34
00:01:31,650 --> 00:01:32,790
>> Малан ДАВИД: Тако је н
број елемената.

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, број страница
у телефонском именику је н.

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
н на квадрат.

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
Али, ако размишљамо о веома великим Н, и
ако некако раде из математику као

58
00:02:35,090 --> 00:02:39,170
Ја сам на табли, са н квадрата
минус нешто, све остало

59
00:02:39,170 --> 00:02:41,850
поред н на квадрат, једном н
постаје заиста велики, не

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
Ерик Шмит, у то време директор
Гоогле, заправо имао прилику

78
00:03:27,160 --> 00:03:28,040
да га интервјуише.

79
00:03:28,040 --> 00:03:32,010
А мислили смо да деле овај ИоуТубе
цлип за вас овде, ако би могли искрснути

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
>> -Сада, сенатор, овде си на Гоогле-у,
и ја волим да мислим председништва

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
Такође је тешко добити посао у Гоогле-у.

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
>> Малан ДАВИД: Па то је то.

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
И тако смо увели велики О. и Биг О
представља нешто што смо мислили

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
Дакле, велика О од н квадрата значи да у
најгорем случају, нешто као

117
00:05:04,710 --> 00:05:07,780
Избор врста би потребно
н на квадрат кораке.

118
00:05:07,780 --> 00:05:10,310
Или нешто попут убацивања врсте
би н на квадрат корака.

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
>> Само да подсетимо, тада, Биг О од н
квадрат, видели смо неколико таквих

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

161
00:06:58,350 --> 00:06:59,580
Велико О од н?

162
00:06:59,580 --> 00:07:02,870
Шта је алгоритам који би могли
се рећи да је Биг О од н?

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
Велико О од н би било линеарно претрагу,
јер у најгорем случају,

172
00:07:23,910 --> 00:07:26,610
елеменат чак и није тамо, или је то
све на крају.

173
00:07:26,610 --> 00:07:29,370
>> Па, велики о лог н.

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
>> Велико О 1.

186
00:08:01,400 --> 00:08:03,540
Тако смо могли Биг О од 2, Биг О од 3..

187
00:08:03,540 --> 00:08:06,260
Кад год желите само константан број,
Само некако ми само поједностављују

188
00:08:06,260 --> 00:08:07,280
да што већи од 1 О.

189
00:08:07,280 --> 00:08:10,440
Иако реално ако је потребно
2 или чак 100 корака, ако је то

190
00:08:10,440 --> 00:08:13,680
константан број корака,
Ми само кажемо Биг О 1.

191
00:08:13,680 --> 00:08:15,930
Шта је алгоритам који је
у великој О од 1?

192
00:08:15,930 --> 00:08:18,350
>> ПУБЛИКА: Проналажење дужину
променљиве.

193
00:08:18,350 --> 00:08:21,090
>> ДАВИД Малан: Финдинг
дужина променљиве?

194
00:08:21,090 --> 00:08:23,870
>> ПУБЛИКА: Не, дужина
ако је већ сортирају.

195
00:08:23,870 --> 00:08:24,160
>> ДАВИД Малан: Добро.

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
Сетите се прве недеље Ц,
позивање само принтф и штампање

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
>> Малан ДАВИД: Да.

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
које дужине н, као и -

216
00:09:17,780 --> 00:09:21,990
вероватно, иф сама Биг О од н
јер то ће вас одвести н корака

217
00:09:21,990 --> 00:09:24,750
одштампати сваку од тих н
карактера, највероватније.

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
овде или овде имам угњеждене петље,
који ће радити ствари н н пута,

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
>> Дакле, шта је омега н на квадрат?

228
00:09:49,730 --> 00:09:53,582
Шта је алгоритам који на најбољи
случај, још увек је н квадрат кораци?

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
>> Малан ДАВИД: Па избор врста.

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
>> Ова, на крају, омега н лог н.

250
00:10:49,190 --> 00:10:52,573
Дакле н лог н, нисмо баш
говори о још, али -

251
00:10:52,573 --> 00:10:53,300
>> ПУБЛИКА: Мерге сорт?

252
00:10:53,300 --> 00:10:53,960
>> ДАВИД Малан: Мерге сорт.

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
У ствари, кратко споји не само у
Најбољи случај н лог н, у најгорем

258
00:11:07,800 --> 00:11:09,460
случај н лог н.

259
00:11:09,460 --> 00:11:14,540
А када имате ову подударност
Омега и велика о што је то исто?

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
Хеап сорт, сорт брзо, Схелл -

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
А можда за П сет 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
Има н ствари у њему.

302
00:13:04,000 --> 00:13:05,370
То је све што ми је рекао.

303
00:13:05,370 --> 00:13:07,560
>> Ако је н мање од 2, вратити.

304
00:13:07,560 --> 00:13:08,640
Дакле, то је само безначајна ствар.

305
00:13:08,640 --> 00:13:12,580
Ако је н мање од 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
>> Малан ДАВИД: Да, мој алгоритам за сортирање,
двојица његових корака су "врста

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
Гоогле стакла -

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
>> Малан ДАВИД: Ако бисмо могли да осам
волонтера, и хајде да видимо да ли можемо

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
>> Малан ДАВИД: Ја сам у ствари
не знам шта је то.

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
У реду, тако да сви седите,
али не и на Гоогле стакла.

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
>> ДАВИД Малан: Мишел?

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
Ми смо покушавали да дођу до
случај коришћења за Гоогле стакла, а ми

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
Није вероватно оно што Гоогле намењена.

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
>> Малан ДАВИД: То је прилично насумично.

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
>> Малан ДАВИД: Тако да сада морам да сортирате
Лева половина ових момака.

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
>> ДАВИД Малан: Сортирај левој половини.

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
>> ДАИСИ ПРИНЦЕЗА: Принцеза Дејзи.

440
00:18:02,390 --> 00:18:03,690
>> ДАВИД Малан: Принцеза Дејзи се овде.

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
У реду, врати, јер је списак од
величина 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
>> ДАВИД Малан: Линда.

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
>> ДАВИД Малан: Пажљиво.

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
>> ДАВИД Малан: Сортирај десној половини.

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
>> ДАВИД Малан: Јесс.

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
>> ДАВИД Малан: Мишел је очигледно
листа величине 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
>> ПУБЛИКА: Мерге.

499
00:20:03,030 --> 00:20:04,160
>> Малан ДАВИД: Тако да сада имамо да се споје.

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
>> ДАВИД Малан: И сад смо
у прилично добром стању.

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
>> ДАВИД Малан: Добро.

528
00:21:09,250 --> 00:21:10,350
>> СПИКЕР 1: И онда -

529
00:21:10,350 --> 00:21:11,800
>> ДАВИД Малан: Ко ради
микрофон иде даље?

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
>> ДАВИД Малан: Добро.

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
>> ДАВИД Малан: Управо тако.

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: Ја сам десна половина
Лева половина, а мој је н мање од

545
00:21:43,590 --> 00:21:45,048
1, па ћу само да прође -

546
00:21:45,048 --> 00:21:46,380
>> ДАВИД Малан: Добро.

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
>> Малан ДАВИД: Па ти иди у ледја.

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
>> ПУБЛИКА: Мерге.

557
00:22:02,940 --> 00:22:07,270
>> ДАВИД Малан: Спајање лево и десно пола
половина некадашњег левој половини.

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
>> Малан ДАВИД: Није готово, јер
очигледно, постоји један преостали корак.

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
алгоритам основи, нарочито као
н постаје заиста велики, као што смо видели

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
је велика О од н лог н пута.

594
00:23:36,160 --> 00:23:39,160
То јест, постоји неки аспект овог
алгоритам је потребно н корака, али

595
00:23:39,160 --> 00:23:43,110
постоји још један аспект негде у
да итерација, то петље, која

596
00:23:43,110 --> 00:23:44,410
Потребно лог н корака.

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
>> ДАВИД Малан: Управо тако.

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
>> Тако сам стапање узимање
не више од н корака.

627
00:25:00,570 --> 00:25:03,250
И колико пута сам имао
за то спајање?

628
00:25:03,250 --> 00:25:07,150
Па, не више од н, а ми смо управо
Видео сам да је са коначном стапања.

629
00:25:07,150 --> 00:25:13,120
И ако урадите нешто што траје
лог н корака н пута, или обрнуто,

630
00:25:13,120 --> 00:25:15,210
то ће нам дати н лог н пута.

631
00:25:15,210 --> 00:25:16,310
>> А зашто је то боље?

632
00:25:16,310 --> 00:25:19,600
Па, ако већ знамо тај дневник
н је бољи од н - зар не?

633
00:25:19,600 --> 00:25:22,590
Видели смо у бинарном претрагом, телефонског именика
пример, лог н је дефинитивно

634
00:25:22,590 --> 00:25:23,760
боље него линеарно.

635
00:25:23,760 --> 00:25:28,420
Значи н пута лог н
дефинитивно боље од н пута други

636
00:25:28,420 --> 00:25:30,390
н, ака Н на квадрат.

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
>> Малан ДАВИД: А твоји поклонима -
Можете сачувати бројеве,

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
Тако сте пропустили део где је он
заправо учинио лог н, лог н лог н,

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
>> ДАВИД Малан: Хм.

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
>> Малан ДАВИД: Тако је.

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
>> ДАВИД Малан: Опет, обавештење, никада
дотакао дати чашу више пута

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
Дакле, у овом тренутку, ја ћу хит представу.

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
>> [ТОНЕС ПЛАИИНГ]

718
00:29:50,400 --> 00:29:52,400
>> ДАВИД Малан: Опет се покушава
да убаците сваки елемент

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
>> [ТОНЕС ПЛАИИНГ]

722
00:30:10,097 --> 00:30:13,630
>> Малан ДАВИД: А можете некако осећају
релативно мало раде како се то ради

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
>> [ТОНЕС ПЛАИИНГ]

726
00:30:21,472 --> 00:30:25,222
>> ДАВИД Малан: Ово је избор врста,
где смо изабрали елемент желимо од

727
00:30:25,222 --> 00:30:28,845
пролази кроз изнова и изнова и изнова
и стављајући га на почетку.

728
00:30:28,845 --> 00:30:37,674
>> [ТОНЕС ПЛАИИНГ]

729
00:30:37,674 --> 00:30:43,970
>> ДАВИД Малан: Ово је обједињавање врста, које
заиста можете почети да се осећају.

730
00:30:43,970 --> 00:30:51,810
>> [ТОНЕС ПЛАИИНГ]

731
00:30:51,810 --> 00:30:54,770
>> [Смех]

732
00:30:54,770 --> 00:30:58,395
>> ДАВИД Малан: Нешто што се зове ГНОМЕ
врста, које нисмо гледали.

733
00:30:58,395 --> 00:31:13,630
>> [ТОНЕС ПЛАИИНГ]

734
00:31:13,630 --> 00:31:17,910
>> Малан ДАВИД: Па да видимо, сада,
растројен јер сте надам се до

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
Ако је н мање од 2, време укључени
за сортирање н елемената,

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
Па, Т од н само значи
Време за сортирање н елемената.

768
00:32:58,690 --> 00:33:03,070
И онда на десној страни
знак једнакости тамо, Т од н подељено

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
Други Т од н подељено са 2 је
вероватно се односи на трошкове за

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

773
00:33:12,390 --> 00:33:14,590
>> А онда плус н?

774
00:33:14,590 --> 00:33:15,420
Да ли је спајање.

775
00:33:15,420 --> 00:33:19,120
Јер, ако имате два листа, један од
величина н преко 2 и још један од величине н

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
Т пута од 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 за т 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, прикључите га у средњој линији, Т

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
>> Сада је сама по себи врста говори
ништа се н нотацији,

816
00:35:18,480 --> 00:35:20,700
Велико О, Омега које смо
говорили.

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
да приказују време стапања
врста је заиста н лог н.

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
Али, ако ја идем на гоогле.цом и ако
Желим да научим нешто о

837
00:36:20,650 --> 00:36:22,356
рекурзије, Ентер.

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
ДАВИД Малан: Лош виц полако шири.

842
00:36:33,385 --> 00:36:34,450
[Смех]

843
00:36:34,450 --> 00:36:36,970
ДАВИД Малан: За сваки случај, ту је.

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
>> Прво, брзо укључују стандардне ио.х,
као и спадају у цс50.х.

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
Схватио сам миснамед датотеку, па
дозволите ми да додате ц продужења. овде тако

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
Дакле, прво ћу да наставим
и прогласи инт н.

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
А онда ћу да
кажу н добија се инт.

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 и н и, или 0 и н,

894
00:38:51,020 --> 00:38:52,570
еквивалентно, да се укупан збир.

895
00:38:52,570 --> 00:38:55,100
Дакле, велики симбол Сигма
Можда се сећате да сте.

896
00:38:55,100 --> 00:38:59,050
Дакле, ја ћу да урадим ово први позивом
функција се зове сигма,

897
00:38:59,050 --> 00:39:06,030
пролази га у Н, а онда ћу да
принтф кажу, одговор је ту.

898
00:39:06,030 --> 00:39:08,180
>> Дакле укратко, ја се и
инт од корисника.

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
Вредност СИГМА, пролази у н као улаз.

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
матх.х фајл, његова изјава,
заправо није.

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
Идем да се имплементира функцију која се зове
сигма, а то ће да се

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
Онда ћу имати
за петљи инт -

919
00:39:59,630 --> 00:40:02,820
и пусти ме да радим да поклапају са нашом
код дистрибуција, тако да имате копију

920
00:40:02,820 --> 00:40:07,500
код куће. инт добија на 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
Користи двоструку петљу да се позитивна
инт од корисника.

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
>> Малан ДАВИД: Да, ја нисам изјављујем
функција до врха, зар не?

955
00:41:37,800 --> 00:41:40,590
Ц је мало глупо, по томе што је
ради оно што ви кажете да урадите, а ви

956
00:41:40,590 --> 00:41:41,880
морате да урадите у том циљу.

957
00:41:41,880 --> 00:41:45,910
И ако сам погодио Унесите овде, ја ћу да
добили упозорење о сигма имплицитно

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
Сигма је функција која враћа
инт и очекује

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
плус 2 плус 1, 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, или обрнуто
између 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
изазивања, при чему сам имплементацији
сигма позивањем СИГМА.

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, сигма није
ће да се зовем.

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
Овај овде, носвап.

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
У главни, то прво изјављује
инт к позвао и додељује га

1078
00:47:10,140 --> 00:47:11,100
вредност 1.

1079
00:47:11,100 --> 00:47:13,520
Онда искаже инт и и
додељује му вредност 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
>> Затим тврди да се позивање функција
зове замену, пролази у к и

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
средње-човек звао темп осећа
савршено разумно.

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
Зваћу ову носвап.ц.

1099
00:48:01,995 --> 00:48:05,630
И као што име сугерише, ово није
ће бити одговарајући програми.

1100
00:48:05,630 --> 00:48:09,460
Направите носвап / бр свап..

1101
00:48:09,460 --> 00:48:12,110
к је 1, и 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
АМ, део који се односи на купон
код, идеја је да можете продужити

1122
00:49:05,170 --> 00:49:07,710
Ваша рок за
П сет до петка.

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
>> Дакле, имамо среће да има један од
ЦС50 је бивши шеф наставних момци на

1134
00:49:37,050 --> 00:49:39,302
фирма се зове дропбок.цом.

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
много више простора за своје Дропбок
апарата и за ваше личне датотеке.

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
>> ДАВИД Малан: Видећемо
ти у среду.

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
>> ДАВИД Малан: Балкон људи, долазе
доле на фронт,

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
>> НАРАТОР: На следећем ЦС50 -

1166
00:50:54,590 --> 00:51:00,374
>> ПРЕДСЕДНИК 5: О боже боже боже боже
бозе бозе бозе бозе бозе бозе -

1167
00:51:00,374 --> 00:51:02,106
>> [Укелеле плаис]