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
можете да уживате во добар разговор
и храна во Fire and Ice

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
е напишано име, преку З И
навистина имиња се толку едноставни, А

14
00:00:47,580 --> 00:00:50,490
преку З И еден од
целите во рака денес

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
од А до Ш

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
Дали прво се движат вашите раце околу
Барате потоа во потрага по Б?

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
>> ЗВУЧНИЦИ: Сите во право, а преку З. Сите
право, алал да му е, си го направила.

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
И тоа е, daresay, друг
техника заедно.

102
00:05:02,650 --> 00:05:06,950
Не сте го третираат како еден голем куп,
ќе се подели на проблемот во четири quads,

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
Или поопшто, ако
имаме n луѓе,

123
00:06:01,290 --> 00:06:04,300
направи N минус 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
Одев од лево кон десно низ
фаза, ме N минус 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
>> Па N минус 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
N минус 2, нели?

146
00:07:10,730 --> 00:07:14,297
Тоа само ќе се трошат моето време, ако јас
задржи споредување осум против некого

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
се случува да бидат плус n минус два чекори,
каде n е бројот на луѓето.

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
>> Сега точка, точка, точка вид на бранови тоа е
раце на некои од juicier детали,

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
она серија summations како
Ова, конечно додаде до.

162
00:07:56,400 --> 00:07:59,600
Во случај, ако имате
променлива како N, и навистина ова,

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
n пати n 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
Значи, да се мултиплицираат ова, па тоа е
N на квадрат, минус n, сите поделено со 2.

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

172
00:08:23,200 --> 00:08:25,010
па тоа е убаво и интересно.

173
00:08:25,010 --> 00:08:27,060
Но, она што се случува ако ние
сега plug-in-вредност?

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
Па 500 милијарди долари, минус 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
може да ме земе 499.999.500.000
чекори или споредби на крајот,

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

188
00:09:14,050 --> 00:09:16,280
вид на се чувствува полошо и
уште полошо, или навистина

189
00:09:16,280 --> 00:09:20,450
почнете да се чувствувате болката на кои
степенување, што n квадрат,

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

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
>> -I'm Жал, 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
>> -We've Добивме шпиони во таму.

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
>> Па јас осветлени во жолто тука
резултат на n квадрат поделен со 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
откако ќе одзема исклучите N поделено со 2.

229
00:11:20,180 --> 00:11:24,850
И тврдењето јас ќе одам да направите сега е,
Кој е грижам се грижи ако одземе исклучување

230
00:11:24,850 --> 00:11:30,060
малку стар n над 2, кога првата
дел од оваа формула е многу поголема?

231
00:11:30,060 --> 00:11:33,910
Доминира со други
рок, n квадрат поделен со 2

232
00:11:33,910 --> 00:11:37,510
толку многу поголеми, јасно, како
N добива големи како еден милион,

233
00:11:37,510 --> 00:11:41,450
тоа е навистина голема разлика на
на крајот на денот помеѓу 500 милијарди

234
00:11:41,450 --> 00:11:45,730
и 499.999.500.000?

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
>> Како N добива поголема, ние сме навистина
ќе се грижат за најголем

242
00:12:07,340 --> 00:12:11,560
термин во секоја таква анализа на
нашите алгоритми перформанси.

243
00:12:11,560 --> 00:12:16,230
И јас одам да се каже, знаеш што,
меур вид е од редот на големите О,

244
00:12:16,230 --> 00:12:18,060
од редот на N на квадрат.

245
00:12:18,060 --> 00:12:20,090
Тоа не е точно n
квадрат, како што видовме,

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

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
Па со нешто како голема О на n
квадрат, тврдам дека О од n квадрат

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

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
би се вели дека се граничи
од n, линеарна функција,

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
отколку како n чекори, или
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
n, нели?

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
Па сигурно, n е горната граница.

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
имаат трчање време, тоа е
граничи со голема О на најавите n, n се најавите?

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
Што е мерка за тоа колку
многу време или колку солзи го

308
00:15:07,754 --> 00:15:10,170
ми требаше да се најде некој како
Мајк Смит во книгата на телефонот?

309
00:15:10,170 --> 00:15:13,212
Ние тврдеше дека најавите n и
дури и ако се запознаени или тоа е

310
00:15:13,212 --> 00:15:15,170
малку маглива што е
логаритам или експонент беше,

311
00:15:15,170 --> 00:15:17,650
само се сеќавам дека најавите n
генерално се однесува на процесот,

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

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
Ако имаше бинарни пребарување, влези n
ќе биде горната граница на тоа колку

318
00:15:37,374 --> 00:15:38,040
времето што е потребно.

319
00:15:38,040 --> 00:15:44,027
Но, оние алгоритми кои трчаа во
најавите n претпоставува што клучните детали?

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
>> Сега што ова може да значи голема О на еден?

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

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
без разлика колку долго
низа е во C код?

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

362
00:17:31,920 --> 00:17:33,350
или 2n чекори, или 3N чекори?

363
00:17:33,350 --> 00:17:36,241
Некои фактор на n чекори,
тоа е нејзината долната граница.

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

365
00:17:36,740 --> 00:17:37,910
>> ПУБЛИКАТА: меур вид?

366
00:17:37,910 --> 00:17:41,610
>> Говорник: меур вид се
ќе минимално n чекори, зошто?

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
Но, тоа се случува да ви n чекори земе.

381
00:18:09,700 --> 00:18:12,033
>> И обратно, што е уште еден
начин на размислување за тоа?

382
00:18:12,033 --> 00:18:15,240
Меур вид е омега,
така да се каже, на n,

383
00:18:15,240 --> 00:18:19,050
затоа што ако се погледне на
помалку од n елементи, што

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
тоа не ме n чекори ги преземе, но го направив тоа.

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 чекори, но
константна, независно од n,

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
Затоа што printf ги зема
влез, тоа е стринг,

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

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

435
00:20:18,270 --> 00:20:20,661
Тоа само значи дека кога голем
O и омега се исти.

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
N минус 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
само да се спарите елементи
заедно n минус 1 пати.

448
00:20:52,010 --> 00:20:55,630
Па селекција вид на сличен начин се
N минус 1 чекорите прв пат.

449
00:20:55,630 --> 00:20:59,540
>> Колку чекори не ме однесе до
најдете вториот најмал елемент?

450
00:20:59,540 --> 00:21:02,920
N минус 2, затоа што јас сум се неми
ако Продолжувам да гледа во истите луѓе

451
00:21:02,920 --> 00:21:06,280
повторно ако јас сум веќе го одбрани
или неа и ги стави во нивното место.

452
00:21:06,280 --> 00:21:09,270
А третиот чекор, н
минус 3, тогаш n минус 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
од n квадрат ако правиме се што збир.

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
Можеби тоа е n, како порано.

461
00:21:32,360 --> 00:21:35,040
Можеби тоа е n квадрат, како што
е сега како горна граница.

462
00:21:35,040 --> 00:21:35,874
>> ПУБЛИКАТА: N квадрат.

463
00:21:35,874 --> 00:21:36,664
ЗВУЧНИЦИ: N квадрат.

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
може да ме прекине по
само n или така чекори.

473
00:21:54,350 --> 00:21:57,080
Па навистина, избор
вид, омега на n квадрат.

474
00:21:57,080 --> 00:22:00,667
>> Што е со вметнување вид, каде што се
кои ми беше дадена, а потоа го plopped

475
00:22:00,667 --> 00:22:01,750
или неа во право место?

476
00:22:01,750 --> 00:22:04,958
Тогаш ќе се продолжи со второ лице,
plopped него или неа на вистинското место.

477
00:22:04,958 --> 00:22:07,910
Тогаш следниот лице, plopped
него или неа на вистинското место.

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
И така што n минус 1 shufflings,
n минус 2 shufflings, n

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
Elena исполнуваат Петар.

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

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

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

596
00:27:19,060 --> 00:27:22,080
и тоа беше pseudocode за
решавање на телефон книга проблем.

597
00:27:22,080 --> 00:27:25,150
При што во pseudocode јас
набројани повеќе методичен начин

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
Тие се доказ за итеративен
пристап, looping пристап,

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
Тоа не е фундаментално скратување
на pseudocode многу,

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
Тука е pseudocode за спојување вид.

643
00:29:54,810 --> 00:30:00,170
Кога на влез на n елементи, па со оглед на
низа на големина 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
Што е импликација ако те предаде
низа чија должина n е помалку од 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
Сум те праша да се најде решение
n елементи, и јас сум

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

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
Прво проверете е n помалку од две, не,
па јас продолжи кон друг блок повторно.

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
Добро, па сега јас го нарекувам мојот истата спојување
сортирање алгоритам, е N помалку од два?

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
Па десната половина, па ајде да се движат Лука во текот
тука во првобитната положба на Darren.

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
но ако се направи тоа во реално време, ние ќе
да видиме што takeaways и ќе биде.

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
Имаме Лука со број два
или Chris со бројот три.

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
и сега денес се спојат вид, која
ќе биде нашиот climactic крај.

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
не е особено climactic,
тие само се заокружи подредени.

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
>> ПУБЛИКАТА: Логирај n.

878
00:39:41,890 --> 00:39:42,760
>> ЗВУЧНИЦИ: Логирај n.

879
00:39:42,760 --> 00:39:46,300
Но тогаш има еден друг клучен чекор,
овој алгоритам не е да се најавите n чекори.

880
00:39:46,300 --> 00:39:48,992
Ако тоа беа само се најавите n чекори,
ние ќе бидеме во истиот проблем

881
00:39:48,992 --> 00:39:51,200
како порано, каде што не може да биде
сигурни сè е подредени.

882
00:39:51,200 --> 00:39:54,480
Мора да се погледне во минимално n елементи
за да бидете сигурни n елементи се подредени,

883
00:39:54,480 --> 00:39:55,950
инаку тоа е скок на верата.

884
00:39:55,950 --> 00:39:59,810
>> Така, тоа е минимално најавите n чекори, но
она што за овој клучен спојување чекор

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
Тоа е n, но јас не само што
се спојат финалето време.

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
Значи, ако поделба на листа
може да се направи најавите n пати,

895
00:40:28,570 --> 00:40:33,880
и спојување на крајот се n
чекори, што може да биде сега горниот

896
00:40:33,880 --> 00:40:37,000
обврзани на водење
време на нашиот алгоритам?

897
00:40:37,000 --> 00:40:37,980
n најавите n.

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
е N на квадрат против n
квадрат против n најавите n.

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