1
00:00:00,000 --> 00:00:11,100
>> [Музика свира]

2
00:00:11,100 --> 00:00:11,490
>> Давид Ј. Малан: У реду.

3
00:00:11,490 --> 00:00:12,170
Дакле, добродошли назад.

4
00:00:12,170 --> 00:00:15,180
То је ЦС50, а није
крај три недеље.

5
00:00:15,180 --> 00:00:17,770
>> Тако се сећате у последњих неколико недеља,
смо проводи доста

6
00:00:17,770 --> 00:00:20,820
Време на Ц, на програмирање, на синтакси.

7
00:00:20,820 --> 00:00:24,680
И то је сасвим нормално, ако си и даље
бори са проблемом Сет 2, да буде

8
00:00:24,680 --> 00:00:25,950
лупа главом о зид.

9
00:00:25,950 --> 00:00:28,310
То је криптичан изгледају поруке о грешци
и бубе које

10
00:00:28,310 --> 00:00:29,220
не могу да стигнем.

11
00:00:29,220 --> 00:00:32,310
Зато, будите уверени, да је само у
време неколико недеља ћете осврнем на

12
00:00:32,310 --> 00:00:35,930
ствари као Цезара, и [? В-генаир,]?
можда чак Црацк, и

13
00:00:35,930 --> 00:00:40,050
схватити колико далеко сте дошли
у кратком временском периоду.

14
00:00:40,050 --> 00:00:43,670
Дакле, ако је то нека утеха,
Дрзи се за сада.

15
00:00:43,670 --> 00:00:46,610
>> Данас, међутим, ми смо почели да транзиција
у ствари виши ниво.

16
00:00:46,610 --> 00:00:49,820
И почнемо да узимамо здраво за готово да је
ви знате како да програмирате, или на

17
00:00:49,820 --> 00:00:52,090
Цене су почеци
да ниво удобности.

18
00:00:52,090 --> 00:00:56,520
И ми ћемо почети да се размотри како можемо
се о дизајнирању програма више

19
00:00:56,520 --> 00:00:57,440
ефикасно.

20
00:00:57,440 --> 00:01:01,090
Како можемо да идемо о оптимизацији
Ефикасност наших алгоритама, а

21
00:01:01,090 --> 00:01:03,110
генерално решавање више
интересантне проблеме.

22
00:01:03,110 --> 00:01:06,850
И почиње да се узима здраво за готово да је,
ако бисмо желели да, можемо да се било који кодирају

23
00:01:06,850 --> 00:01:08,350
од примера имамо у виду.

24
00:01:08,350 --> 00:01:11,430
Тако данас, ми не додирнете тастатуру
за било који облик кода.

25
00:01:11,430 --> 00:01:15,150
То ће бити много виши ниво, а
на крају, о решавању проблема.

26
00:01:15,150 --> 00:01:20,490
>> Тако да се у том тренутку, да предложи
да у наредних седам

27
00:01:20,490 --> 00:01:24,290
правоугаоници представљају седам врата, иза
које су гомила

28
00:01:24,290 --> 00:01:26,340
бројева, међу којима је број 50.

29
00:01:26,340 --> 00:01:30,470
Дозволите ми да напустим ово на ово
екран и овде.

30
00:01:30,470 --> 00:01:36,770
И предлажу да ми треба добровољац за
помогну у проналажењу ми броја испред

31
00:01:36,770 --> 00:01:38,140
Интернет овде да видите.

32
00:01:38,140 --> 00:01:40,755
Дођи горе, у розе.

33
00:01:40,755 --> 00:01:43,050
У реду.

34
00:01:43,050 --> 00:01:43,930
Како се зовеш?

35
00:01:43,930 --> 00:01:44,850
>> ЈЕННИФЕР: [ИНАУДИБЛЕ]

36
00:01:44,850 --> 00:01:45,170
>> Давид Ј. Малан: Молим?

37
00:01:45,170 --> 00:01:45,860
>> ЈЕННИФЕР: Џенифер.

38
00:01:45,860 --> 00:01:46,390
>> Давид Ј. Малан: Џенифер.

39
00:01:46,390 --> 00:01:46,980
У реду, Џенифер.

40
00:01:46,980 --> 00:01:47,630
Драго ми је што смо се упознали.

41
00:01:47,630 --> 00:01:48,370
Хајде горе.

42
00:01:48,370 --> 00:01:52,430
Дакле, ово овде су седам врата, а шта
Волео бих да радим за нас овде,

43
00:01:52,430 --> 00:01:56,560
пред свим својим друговима,
се налазимо, број 50.

44
00:01:56,560 --> 00:02:00,860
Да бисте пронашли број, можете да провире
било који од ових врата једноставним додиром

45
00:02:00,860 --> 00:02:03,030
на једној од врата, и
ће открити свој број.

46
00:02:03,030 --> 00:02:06,080
И хајде да видимо колико брзо
да нас нађете број 50,.

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15.

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16.

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50.

53
00:02:16,530 --> 00:02:17,350
Лепо урађено.

54
00:02:17,350 --> 00:02:18,040
У реду.

55
00:02:18,040 --> 00:02:19,906
Аплауз за Џенифер.

56
00:02:19,906 --> 00:02:21,530
>> [Апплаусе]

57
00:02:21,530 --> 00:02:22,320
>> У реду.

58
00:02:22,320 --> 00:02:25,254
Дакле, шта је Ваша стратегија за
проналажење броја, 50?

59
00:02:25,254 --> 00:02:27,222
>> ЈЕННИФЕР: Хм, ако сам мислио -

60
00:02:27,222 --> 00:02:27,714
[ИНАУДИБЛЕ]

61
00:02:27,714 --> 00:02:28,206
>> Давид Ј. Малан: О.

62
00:02:28,206 --> 00:02:29,630
Дајте јој један секунд.

63
00:02:29,630 --> 00:02:32,420
Да ли је твој стратегија
проналажење броја, 50?

64
00:02:32,420 --> 00:02:34,760
>> ЈЕННИФЕР: Тако да сам се крећу од
почиње да се види шта је први број

65
00:02:34,760 --> 00:02:38,590
је, а онда сам помислио, можда ако
они сортирани, ја ћу држати

66
00:02:38,590 --> 00:02:39,970
прислушкивање вишље?

67
00:02:39,970 --> 00:02:40,140
>> Давид Ј. Малан: У реду.

68
00:02:40,140 --> 00:02:42,910
А изгледа да смо нашли
да је то случај.

69
00:02:42,910 --> 00:02:45,670
Мада, хајде да одлепите слојева
само мало, а желите да одете

70
00:02:45,670 --> 00:02:47,640
напред и открије друге врата
могли сте изабрали?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> ЈЕННИФЕР: О, драга.

73
00:02:51,712 --> 00:02:53,128
>> Давид Ј. Малан: Ах.

74
00:02:53,128 --> 00:02:54,280
>> ЈЕННИФЕР: Па управо сам среће.

75
00:02:54,280 --> 00:02:55,270
>> Давид Ј. Малан: Па ти се посрећило.

76
00:02:55,270 --> 00:02:55,710
У реду.

77
00:02:55,710 --> 00:02:56,795
Зато није лоше.

78
00:02:56,795 --> 00:02:58,750
Али, то је занимљиво
увид, зар не?

79
00:02:58,750 --> 00:03:01,870
Ако сте претпоставили, а ви се,
заиста, мало среће тамо.

80
00:03:01,870 --> 00:03:05,350
Али, ако се претпоставља да су цифре
сортирају, могу ли бити прецизнији

81
00:03:05,350 --> 00:03:08,750
како је то утицало
ваше понашање?

82
00:03:08,750 --> 00:03:11,715
>> ЈЕННИФЕР: Дакле, ако су били поредани, ја
Мислио сам најмањег до највећег.

83
00:03:11,715 --> 00:03:11,970
>> Давид Ј. Малан: У реду.

84
00:03:11,970 --> 00:03:15,260
>> ЈЕННИФЕР: Или ако је ово заврсило се
заиста велики, онда највећи до најмањег.

85
00:03:15,260 --> 00:03:15,540
>> Давид Ј. Малан: У реду.

86
00:03:15,540 --> 00:03:18,170
Дакле, највећи до најмањег, или
најмањег до највећег.

87
00:03:18,170 --> 00:03:21,990
Али, дозволите ми да предложи, претпостављам да је
стечен среће, а претпостављам да су они

88
00:03:21,990 --> 00:03:26,840
нису, у ствари, сортирају, колико
та врата можда сте морали да вирим

89
00:03:26,840 --> 00:03:28,590
иза у том најгорем слуцају?

90
00:03:28,590 --> 00:03:29,860
>> ЈЕННИФЕР: Сви они.

91
00:03:29,860 --> 00:03:30,420
>> Давид Ј. Малан: Све њих.

92
00:03:30,420 --> 00:03:31,740
Па хајде да генерализује да је н.

93
00:03:31,740 --> 00:03:34,790
Ту се дешава да буде 7, али хајде да више
обично кажу да постоји н врата на

94
00:03:34,790 --> 00:03:35,650
Екран.

95
00:03:35,650 --> 00:03:40,110
Дакле, у најгорем случају, да би
погледати иза врата, 7 или Н врата.

96
00:03:40,110 --> 00:03:44,140
И то заиста јесте, то је мало
срећа данас, али то је заиста линеарна

97
00:03:44,140 --> 00:03:46,440
алгоритам врста, чак и ако
су врста прескакања око.

98
00:03:46,440 --> 00:03:47,080
Да ли је то фер?

99
00:03:47,080 --> 00:03:47,500
>> ЈЕННИФЕР: Да.

100
00:03:47,500 --> 00:03:50,000
>> Давид Ј. Малан: Па, да видим да ли ваш
Стратегија промене ако пређем на нас

101
00:03:50,000 --> 00:03:52,190
Наш други пример овде са
7 различитих врата.

102
00:03:52,190 --> 00:03:55,240
Исти бројеви, али ово
време они су сортирани.

103
00:03:55,240 --> 00:03:58,350
Која је ваша стратегија овде бити,
покушава да стави ван памети што

104
00:03:58,350 --> 00:03:59,310
остали бројеви су били -

105
00:03:59,310 --> 00:03:59,930
>> ЈЕННИФЕР: У реду.

106
00:03:59,930 --> 00:04:02,290
>> Давид Ј. Малан: - раније?

107
00:04:02,290 --> 00:04:03,180
>> ЈЕННИФЕР: Почнимо
са првом.

108
00:04:03,180 --> 00:04:03,540
>> Давид Ј. Малан: У реду.

109
00:04:03,540 --> 00:04:05,190
Почните са првом.

110
00:04:05,190 --> 00:04:05,960
4..

111
00:04:05,960 --> 00:04:08,810
А где ћеш да идеш, и зашто?

112
00:04:08,810 --> 00:04:10,040
>> ЈЕННИФЕР: 4 заиста мали.

113
00:04:10,040 --> 00:04:12,500
Дакле, ако су врста можда најмањи
до највеће, што би требало

114
00:04:12,500 --> 00:04:13,290
бити два пута већа, и -.

115
00:04:13,290 --> 00:04:13,670
>> Давид Ј. Малан: У реду.

116
00:04:13,670 --> 00:04:15,990
Да видимо, што ти мислиш?

117
00:04:15,990 --> 00:04:19,050
>> ЈЕННИФЕР: Покушајте последњи.

118
00:04:19,050 --> 00:04:19,500
Лепо.

119
00:04:19,500 --> 00:04:20,880
>> Давид Ј. Малан: Веома лепо урађено.

120
00:04:20,880 --> 00:04:21,860
У реду.

121
00:04:21,860 --> 00:04:23,010
>> [Апплаусе]

122
00:04:23,010 --> 00:04:24,310
>> Давид Ј. Малан: У реду.

123
00:04:24,310 --> 00:04:26,790
Дакле, ви у ствари радите ово
страшно, јер си

124
00:04:26,790 --> 00:04:27,700
то раде веома добро.

125
00:04:27,700 --> 00:04:31,150
Што оставља неспособним да
извршити одређене тачке.

126
00:04:31,150 --> 00:04:32,565
Дакле, хајде да покушамо да се врати овде.

127
00:04:32,565 --> 00:04:34,560
>> ЈЕННИФЕР: У реду.

128
00:04:34,560 --> 00:04:35,980
>> Давид Ј. Малан: Веома добро
урађено, ипак.

129
00:04:35,980 --> 00:04:39,060
Тако сте почели на почетку,
видели сте да је 4, онда

130
00:04:39,060 --> 00:04:40,240
помера за крај.

131
00:04:40,240 --> 00:04:42,320
Али, претпостављам да ниси посрећи
тамо, и претпостављам 50

132
00:04:42,320 --> 00:04:42,890
био негде другде.

133
00:04:42,890 --> 00:04:46,190
Шта ваш Трећи корак био?

134
00:04:46,190 --> 00:04:47,680
>> ЈЕННИФЕР: Вратите се на почетак.

135
00:04:47,680 --> 00:04:48,320
>> Давид Ј. Малан: Врати
на почетак.

136
00:04:48,320 --> 00:04:51,320
У реду, тако да би сте дотакли
ова врата, што је 8.

137
00:04:51,320 --> 00:04:51,660
У реду.

138
00:04:51,660 --> 00:04:52,650
Дакле, то није 50.

139
00:04:52,650 --> 00:04:55,380
Где би сте гледали следећи?

140
00:04:55,380 --> 00:04:56,720
>> ЈЕННИФЕР: Да нисам
Знам да сортирају.

141
00:04:56,720 --> 00:04:57,005
>> Давид Ј. Малан: Тачно.

142
00:04:57,005 --> 00:04:58,490
Па, ако си знао
они су сортирани -

143
00:04:58,490 --> 00:04:58,700
>> ЈЕННИФЕР: О, нисам знао, да.

144
00:04:58,700 --> 00:05:00,910
>> Давид Ј. Малан: - али ви не
Знам где је 50 било још?

145
00:05:00,910 --> 00:05:01,785
>> ЈЕННИФЕР: Само настави.

146
00:05:01,785 --> 00:05:02,130
>> Давид Ј. Малан: У реду.

147
00:05:02,130 --> 00:05:02,520
ОК.

148
00:05:02,520 --> 00:05:03,800
Настави.

149
00:05:03,800 --> 00:05:05,270
У реду, да ја могу да радим са.

150
00:05:05,270 --> 00:05:05,610
>> ЈЕННИФЕР: У реду.

151
00:05:05,610 --> 00:05:07,210
>> Давид Ј. Малан: Сада, ако сте само
ће да иде, шта је твој

152
00:05:07,210 --> 00:05:09,680
алгоритам подршку у преношењу.

153
00:05:09,680 --> 00:05:10,740
>> ЈЕННИФЕР: линеарна -.

154
00:05:10,740 --> 00:05:11,820
>> Давид Ј. Малан: То је некако линеарно.

155
00:05:11,820 --> 00:05:13,480
Али, дозволите ми да предложи, да
ме на лицу места.

156
00:05:13,480 --> 00:05:14,900
Дозволите ми да освежите страницу.

157
00:05:14,900 --> 00:05:17,120
исти број, исти аранжман,
Исти врата.

158
00:05:17,120 --> 00:05:21,350
Али сетите се да тог првог дана у
класа када поцепао телефонски именик у

159
00:05:21,350 --> 00:05:25,480
пола, некако, и оно што је било
Наша стратегија тамо?

160
00:05:25,480 --> 00:05:26,450
>> ЈЕННИФЕР: Почните у средини.

161
00:05:26,450 --> 00:05:26,690
>> Давид Ј. Малан: У реду.

162
00:05:26,690 --> 00:05:27,610
Дакле, почните на средини.

163
00:05:27,610 --> 00:05:28,790
Дакле, идемо напред и да симулира.

164
00:05:28,790 --> 00:05:30,720
Почните у средини
откривајући та врата.

165
00:05:30,720 --> 00:05:31,660
Дакле, број 16.

166
00:05:31,660 --> 00:05:35,290
Дакле, шта би јак момак урадио,
који је поцепао телефонског именика на пола,

167
00:05:35,290 --> 00:05:38,450
да се до следећег нагађања?

168
00:05:38,450 --> 00:05:39,400
>> ЈЕННИФЕР: Идите у овој половини.

169
00:05:39,400 --> 00:05:41,700
>> Давид Ј. Малан: А зашто у десно?

170
00:05:41,700 --> 00:05:43,900
>> ЈЕННИФЕР: Ако су некако најмање
до највеће, онда би требало да буде 50

171
00:05:43,900 --> 00:05:44,720
у том крају.

172
00:05:44,720 --> 00:05:44,920
>> Давид Ј. Малан: Добро.

173
00:05:44,920 --> 00:05:45,390
Потпуно разумно.

174
00:05:45,390 --> 00:05:48,380
Дакле, као телефонски именик, идете на
право за разлику од леве стране, али овде

175
00:05:48,380 --> 00:05:49,500
је кључ за понети.

176
00:05:49,500 --> 00:05:53,930
Сада можете бацити, или отцепи,
половина овог проблема, те не оставља

177
00:05:53,930 --> 00:05:55,970
са 7 врата, али стварно са само 3.

178
00:05:55,970 --> 00:05:57,870
Што је отприлике половина
Величина проблема.

179
00:05:57,870 --> 00:05:58,350
У реду.

180
00:05:58,350 --> 00:06:01,890
Дакле, сада оно што би
урадити након десно?

181
00:06:01,890 --> 00:06:05,870
>> ЈЕННИФЕР: Дакле, 16 је и даље веома мали,
у односу на 50, па можда ћу пробати,

182
00:06:05,870 --> 00:06:06,700
као што је, овај.

183
00:06:06,700 --> 00:06:07,890
>> Давид Ј. Малан: У реду.

184
00:06:07,890 --> 00:06:08,720
42.

185
00:06:08,720 --> 00:06:10,830
У реду, па сад шта је твој
инстинкт ти?

186
00:06:10,830 --> 00:06:12,100
>> ЈЕННИФЕР: Ја могу да бацим
то и онда само -

187
00:06:12,100 --> 00:06:12,360
>> Давид Ј. Малан: У реду.

188
00:06:12,360 --> 00:06:14,212
Добро, можете да баците
Лева половина тамо.

189
00:06:14,212 --> 00:06:14,890
>> ЈЕННИФЕР: - изаберите ово.

190
00:06:14,890 --> 00:06:15,530
>> Давид Ј. Малан: И у праву.

191
00:06:15,530 --> 00:06:15,760
>> ЈЕННИФЕР: Да.

192
00:06:15,760 --> 00:06:17,820
>> Давид Ј. Малан: Дакле, иако је то тешко
можда да види, само кад постоји

193
00:06:17,820 --> 00:06:21,320
7 врата, размислите, сада,
конзистентност

194
00:06:21,320 --> 00:06:22,620
алгоритам само применити.

195
00:06:22,620 --> 00:06:24,510
У претходном случају, јеси
посрећи, што је сјајно.

196
00:06:24,510 --> 00:06:26,540
Али сте користили хеуристички,
Ја бих рекао.

197
00:06:26,540 --> 00:06:29,150
Можете користити врсту своје инстинкте, и
знајући то сам средио, ако је лепа

198
00:06:29,150 --> 00:06:31,600
мала у почетку, наравно, ми смо
Морам да идем више у десно.

199
00:06:31,600 --> 00:06:34,990
Али, у извесном смислу, имаш среће,
Можда је то зато што је број 100,

200
00:06:34,990 --> 00:06:36,220
а можда и 50 био више у средини.

201
00:06:36,220 --> 00:06:37,910
50 Можда је чак овамо.

202
00:06:37,910 --> 00:06:40,960
>> Али, оно што си урадио мало другачије
овај пут је било, ти урадио исту ствар

203
00:06:40,960 --> 00:06:42,150
изнова и изнова.

204
00:06:42,150 --> 00:06:45,310
И ја бих рекла да је оно што сте управо
је, иако под утицајем телефона

205
00:06:45,310 --> 00:06:48,100
Књига пример, нешто много
више алгоритамски, и много

206
00:06:48,100 --> 00:06:49,930
мање посебан покриваннуу.

207
00:06:49,930 --> 00:06:51,620
Много мање инстинктивна.

208
00:06:51,620 --> 00:06:57,160
Дакле, на крају дана, како би
описујете ефикасност

209
00:06:57,160 --> 00:07:00,530
Први алгоритам, где сте отишли
лева на десно, у односу

210
00:07:00,530 --> 00:07:03,430
Други алгоритам овде?

211
00:07:03,430 --> 00:07:06,460
>> ЈЕННИФЕР: ово би требало, као, можда
преполовити време, или чак и више, да.

212
00:07:06,460 --> 00:07:07,320
>> Давид Ј. Малан: У реду, можда чак и више.

213
00:07:07,320 --> 00:07:10,150
Хајде да се мало јаче притиснути на то.

214
00:07:10,150 --> 00:07:13,030
Шта заиста, ако наставимо ово
логика, ми смо дефинитивно преполовљен

215
00:07:13,030 --> 00:07:15,830
трчање време са овом другом алгоритма
бацањем даље половину

216
00:07:15,830 --> 00:07:18,470
бројеве, али шта смо радили на следећи
итерација, када је Џенифер открио

217
00:07:18,470 --> 00:07:20,615
други број?

218
00:07:20,615 --> 00:07:22,830
>> Ми преполовио поново бројеве врата.

219
00:07:22,830 --> 00:07:25,270
И шта смо урадили после тога, ако
било више врата да се игра са?

220
00:07:25,270 --> 00:07:27,520
Ми би их преполовити, и опет,
и опет, и опет.

221
00:07:27,520 --> 00:07:30,420
А то је било баш као и ви сви
стоји горе у првој недељи

222
00:07:30,420 --> 00:07:33,000
класа, половина ли седиш, половина
од ви седите, половина вас

223
00:07:33,000 --> 00:07:35,440
седе, док један усамљени
душа је стајао.

224
00:07:35,440 --> 00:07:39,050
А ми смо рекли да време ради
да, број корака Било је потребно

225
00:07:39,050 --> 00:07:40,430
по налогу чега?

226
00:07:40,430 --> 00:07:41,230
>> СПИКЕР 1: [ИНАУДИБЛЕ]

227
00:07:41,230 --> 00:07:43,970
>> Давид Ј. Малан: Па дневник база од 2 н,
или једноставно само више, пријавите се за н.

228
00:07:43,970 --> 00:07:45,060
Тако нешто логаритамске.

229
00:07:45,060 --> 00:07:48,380
И граф није права линија
да управо сам горе и горе, било је

230
00:07:48,380 --> 00:07:52,490
ово интересантно да није крива
толико лоше током времена.

231
00:07:52,490 --> 00:07:53,910
Па хајде да држите на ову идеју.

232
00:07:53,910 --> 00:07:54,690
Хајде да се захвалим Џенифер.

233
00:07:54,690 --> 00:07:56,150
Хвала много за долазак на горе.

234
00:07:56,150 --> 00:07:57,400
И, један сек.

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
Нема лампе деск данас, али ми
немате ЦС50 стрес лоптице.

237
00:08:02,925 --> 00:08:03,420
>> ЈЕННИФЕР: Ура.

238
00:08:03,420 --> 00:08:04,410
>> Давид Ј. Малан: У реду, овде.

239
00:08:04,410 --> 00:08:06,545
Хвала вам за настајање
стрес овде.

240
00:08:06,545 --> 00:08:07,350
У реду.

241
00:08:07,350 --> 00:08:10,620
Па да видимо да ли можемо сада не
формализовати то мало.

242
00:08:10,620 --> 00:08:14,820
Па опет, шта смо урадили је
у суштини иста ствар као и ми

243
00:08:14,820 --> 00:08:16,660
у првој недељи.

244
00:08:16,660 --> 00:08:23,780
Али, уместо да крај са само линеарно
алгоритам, који се приказао

245
00:08:23,780 --> 00:08:27,210
као раније ове правој линији,
при чему, ако ставимо једну на врата

246
00:08:27,210 --> 00:08:29,610
екран, онда би Џенифер
су морали да изгледају, потенцијално,

247
00:08:29,610 --> 00:08:30,600
иза врата још једном.

248
00:08:30,600 --> 00:08:33,490
Ако ставимо још два врата, она може имати
погледати иза два врата.

249
00:08:33,490 --> 00:08:35,990
>> И тако, било је то линеарно
однос између величине

250
00:08:35,990 --> 00:08:39,059
проблем на, рецимо, к-осе, и
количина времена које је потребно да

251
00:08:39,059 --> 00:08:40,440
решити на и.

252
00:08:40,440 --> 00:08:43,330
Али слика коју је алудирајући
раније је то зелена линија.

253
00:08:43,330 --> 00:08:45,970
Зелена намерно, јер
то је само осећао боље.

254
00:08:45,970 --> 00:08:49,790
У теорији, алгоритам, када смо то урадили
у телефонском именику, када смо то урадили

255
00:08:49,790 --> 00:08:52,420
са бројањем ви једни друге, и
у другом случају, када је Џенифер само

256
00:08:52,420 --> 00:08:55,250
да ли је овде, то је на неки
фундаментално боље.

257
00:08:55,250 --> 00:08:57,180
Зато што то није био само два пута брже.

258
00:08:57,180 --> 00:08:58,870
Није било чак четири пута брже.

259
00:08:58,870 --> 00:09:03,290
То је у потпуности зависи од тога шта
величина улаза је, о томе колико је

260
00:09:03,290 --> 00:09:05,220
кораке које је на крају узео.

261
00:09:05,220 --> 00:09:08,040
>> И тако ова једноставна идеја да смо сви узели
за готово у телефонском именику,

262
00:09:08,040 --> 00:09:10,200
Слично се може применити
на овако нешто.

263
00:09:10,200 --> 00:09:12,380
И ово може да буде више узгред
познат као, као што сте могли

264
00:09:12,380 --> 00:09:13,940
замислите, завади па владај.

265
00:09:13,940 --> 00:09:16,390
Не личи на оно што смо урадили, наравно,
у телефонском именику.

266
00:09:16,390 --> 00:09:18,300
>> Али Псеудокод, подсетимо, био је то.

267
00:09:18,300 --> 00:09:21,800
Дакле, нећемо учинити поново, али сећам
те прве недеље, све нас је устао

268
00:09:21,800 --> 00:09:25,140
а затим половина вас седе, половина
сте сели, половина вас сео.

269
00:09:25,140 --> 00:09:29,280
Тај алгоритам је реализован у
мало варање начин, у томе, што

270
00:09:29,280 --> 00:09:32,870
није био само један од мене бројања,
фундаментално, ефикасније.

271
00:09:32,870 --> 00:09:35,830
У том случају, ја сам усклађивање
секундарни извор.

272
00:09:35,830 --> 00:09:39,470
На неки начин, више процесора, више мозак,
више паметних људи у

273
00:09:39,470 --> 00:09:42,740
собе су помагали ми да од нечега
линеарна нешто

274
00:09:42,740 --> 00:09:45,190
логаритамске, од нечега
црвено да нешто зелено.

275
00:09:45,190 --> 00:09:48,650
>> Али у овом случају, Џенифер сами могу
фундаментално побољшање на

276
00:09:48,650 --> 00:09:52,370
извођење њеног првог алгоритма по,
опет, само мислим мало теже.

277
00:09:52,370 --> 00:09:56,650
И сада, када дође време за спровођење
ове ствари, фигуринг

278
00:09:56,650 --> 00:10:00,670
шта линија кода можете да напишете што су
да можете да их поновите, и

279
00:10:00,670 --> 00:10:03,350
опет, и опет, на неки начин
у лоопинг начин.

280
00:10:03,350 --> 00:10:06,370
Зато што нећеш имати
луксуз, као што је Џенифер је у почетку, да се

281
00:10:06,370 --> 00:10:10,460
Само имам гомилу ИФС и рећи,
Хмм, ако је ово први број је 4,

282
00:10:10,460 --> 00:10:11,800
дозволите ми да скочи све до краја.

283
00:10:11,800 --> 00:10:14,180
Оох, ако тај број је превелика,
да пређемо произвољно назад

284
00:10:14,180 --> 00:10:15,220
до другог елемента.

285
00:10:15,220 --> 00:10:18,210
Видећете да ће то бити много
теже да се формализује оно што ми људи

286
00:10:18,210 --> 00:10:21,270
узимају здраво за готово, као врло разумна
хеуристике, али компјутер је само

287
00:10:21,270 --> 00:10:23,260
урадити оно што не кажете да уради.

288
00:10:23,260 --> 00:10:25,280
>> Сада ово је веома интересантно
импликације.

289
00:10:25,280 --> 00:10:29,950
Овај граф је врста значило да некако
затрпати визуелно, али обавештење, где

290
00:10:29,950 --> 00:10:32,230
је права линија у овом графикону?

291
00:10:32,230 --> 00:10:35,330
Где је линеарни граф
да зовемо н?

292
00:10:35,330 --> 00:10:37,580
Па, то је нека врста према дну
ове слике, зар не?

293
00:10:37,580 --> 00:10:40,500
Дакле, све што смо урадили јесте да смо на неки начин
умањен за к-осе и

294
00:10:40,500 --> 00:10:44,780
И-оса да покуша да добије осећај шта
друге врсте кривих изгледа.

295
00:10:44,780 --> 00:10:47,760
>> И специфичности математички
изрази данас неће бити толико битно

296
00:10:47,760 --> 00:10:52,440
много, али је приметио да постоји много
алгоритми који су далеко горе од

297
00:10:52,440 --> 00:10:53,470
нешто што је линеарна.

298
00:10:53,470 --> 00:10:55,410
Заиста, н на куб изгледа прилично лоше.

299
00:10:55,410 --> 00:10:58,400
2. до н изгледа прилично лоше.
н на квадрат изгледа прилично лоше.

300
00:10:58,400 --> 00:11:01,630
А ми ћемо видети шта су неки од оних који
може бити у стварности данас.

301
00:11:01,630 --> 00:11:05,430
И лог н не осећа тако лоше, али
боље од н је дневник база 2 од н.

302
00:11:05,430 --> 00:11:08,080
Али, знате, то би био ни
више невероватно ако је Џенифер, или ако ми,

303
00:11:08,080 --> 00:11:12,910
те прве недеље, дошао до
нешто што је лог лог н.

304
00:11:12,910 --> 00:11:15,880
>> Дакле, другим речима, ту је цео овај
опсег могућих решења

305
00:11:15,880 --> 00:11:18,570
проблема, али чак и овде, обавештење
шта ће се догодити.

306
00:11:18,570 --> 00:11:22,910
Када сам умањите, који ове криве
ће се показати као апсолутни

307
00:11:22,910 --> 00:11:26,630
најгори од оних на екрану?

308
00:11:26,630 --> 00:11:28,680
Дакле н кубу изгледа прилично
лоше у овом тренутку.

309
00:11:28,680 --> 00:11:32,470
Али, ако се зумира и види више
к и и-оса, ко ће

310
00:11:32,470 --> 00:11:34,550
доминирају на крају?

311
00:11:34,550 --> 00:11:37,120
Тако да заправо испада да је 2 до
н, а можете да схватите ово само

312
00:11:37,120 --> 00:11:39,990
укључивања у неким све већи
бројеве, а ви ћете видети да се 2

313
00:11:39,990 --> 00:11:42,070
н, заиста, постаје све већи много брже.

314
00:11:42,070 --> 00:11:45,530
Ако заиста умањите, а 2 за
н алгоритам апсолутно срање.

315
00:11:45,530 --> 00:11:48,170
Мислим да ће ово узети
сасвим мало времена за

316
00:11:48,170 --> 00:11:49,460
рачунар да узбуркају кроз.

317
00:11:49,460 --> 00:11:52,500
>> Али, ви ћете видети током времена, посебно
са будућим проблем поставе чак и

318
00:11:52,500 --> 00:11:55,600
завршних пројеката, јесте ваши подаци
Сет добија велики, у реду?

319
00:11:55,600 --> 00:11:58,300
Чак иу првој верзији Фацебоока,
као број пријатеља, и

320
00:11:58,300 --> 00:12:01,840
број регистрованих корисника добила велики,
можете да сортирате у телефон га у и

321
00:12:01,840 --> 00:12:05,530
спроведе нешто са линеарном претрагу,
или веома једноставно сортирање

322
00:12:05,530 --> 00:12:07,030
алгоритам, као што ћемо видети данас.

323
00:12:07,030 --> 00:12:09,280
Морате да почнете да размишљате теже
и теже о овим проблемима.

324
00:12:09,280 --> 00:12:12,070
И врсте проблема местима као што су
Фацебоок и Гоогле и Мицрософт,

325
00:12:12,070 --> 00:12:16,350
и други раде на управо овим
врста великог података врсте питања

326
00:12:16,350 --> 00:12:18,530
све више ових дана.

327
00:12:18,530 --> 00:12:18,900
>> У реду.

328
00:12:18,900 --> 00:12:23,800
Дакле Јенниферин успех у тој секунди
алгоритам, искрено, она је невероватно

329
00:12:23,800 --> 00:12:26,110
и први пут, али да
пише како је среће да смо

330
00:12:26,110 --> 00:12:27,000
може да ову тачку.

331
00:12:27,000 --> 00:12:30,970
У другом случају, она је искористио
алгоритам који понавља опет и

332
00:12:30,970 --> 00:12:34,670
поново, али она је за готово
сигурно претпоставка да смо дозволили

333
00:12:34,670 --> 00:12:39,370
њу, али она је експлоатисана неке детаље
други пут да она није имала

334
00:12:39,370 --> 00:12:39,840
први пут.

335
00:12:39,840 --> 00:12:41,800
А то је?

336
00:12:41,800 --> 00:12:43,050
>> Тај списак је сортиран.

337
00:12:43,050 --> 00:12:46,350
Дакле, чим је листа сортирана, ми смо
тврде да је Џенифер била у стању да уради

338
00:12:46,350 --> 00:12:47,480
фундаментално боље.

339
00:12:47,480 --> 00:12:51,450
7 врата, да, није то интересантно,
али претпостављам да смо 7 милиона врата.

340
00:12:51,450 --> 00:12:54,080
Пријава за н је дефинитивно иде
да обавља много, много

341
00:12:54,080 --> 00:12:55,610
брже на дуге стазе.

342
00:12:55,610 --> 00:12:58,880
Али, она је морала да има
врата поредани за њу.

343
00:12:58,880 --> 00:13:02,320
Сада сам узео слободу да ради
унапред на екрану рачунара

344
00:13:02,320 --> 00:13:05,160
овде, али претпостављам да је Џенифер
морао да урадим сама?

345
00:13:05,160 --> 00:13:10,120
Претпоставимо да су врата у питању
представљени подаци у бази података, или

346
00:13:10,120 --> 00:13:14,260
пријатељи који су регистровани за Фацебоок, или
и веб странице на интернету који

347
00:13:14,260 --> 00:13:16,880
разним сајтовима можда ће бити потребно
у индексу или претражују.

348
00:13:16,880 --> 00:13:20,940
>> Претпоставимо да си имала сирове податке
сет и да је остало да се вама, или да

349
00:13:20,940 --> 00:13:23,010
Џенифер да то сређивање?

350
00:13:23,010 --> 00:13:26,950
То је, уместо тога, захтева да ми одговорите
питање, па, колико времена

351
00:13:26,950 --> 00:13:31,080
би узели Џенифер, или чак да,
за сортирање те бројеве унапред тако

352
00:13:31,080 --> 00:13:32,680
да је она могла искористити то?

353
00:13:32,680 --> 00:13:32,880
Зар не?

354
00:13:32,880 --> 00:13:36,620
Јер импликација, наравно, није
ако ми треба доста времена да сортирате

355
00:13:36,620 --> 00:13:40,800
бројеви, који се сад стало да вас
можете наћи број као 50 тако брзо,

356
00:13:40,800 --> 00:13:44,850
као у Јенниферин случају, ако се више од
преплављени количину укупног времена

357
00:13:44,850 --> 00:13:46,920
то је тако сортирање ствари унапред?

358
00:13:46,920 --> 00:13:49,320
>> Па да видимо, ако не можемо
бојите овде слику.

359
00:13:49,320 --> 00:13:51,370
Имам гомилу више стреса
кугле, ако то помаже

360
00:13:51,370 --> 00:13:52,270
пробије лед овде.

361
00:13:52,270 --> 00:13:55,690
А ако немате ништа против, ми смо
Треба седам добровољац -

362
00:13:55,690 --> 00:13:57,060
, ОК.

363
00:13:57,060 --> 00:13:57,240
Вау.

364
00:13:57,240 --> 00:13:59,250
Тако да не морате да потрошите
на стоне лампе, изгледа.

365
00:13:59,250 --> 00:13:59,690
У реду.

366
00:13:59,690 --> 00:14:01,530
Па како ти двоје испред.

367
00:14:01,530 --> 00:14:04,160
Како би било да двојица позади.

368
00:14:04,160 --> 00:14:04,870
Дакле, то је четири.

369
00:14:04,870 --> 00:14:09,890
Како би било да пред
пет, шест и седам.

370
00:14:09,890 --> 00:14:10,320
Тамо.

371
00:14:10,320 --> 00:14:13,260
Ваш пријатељ те истичући,
тако да добијете награду.

372
00:14:13,260 --> 00:14:13,700
>> У реду.

373
00:14:13,700 --> 00:14:14,410
Хајде горе.

374
00:14:14,410 --> 00:14:17,120
И зашто не бисмо ли
Додјите овамо.

375
00:14:17,120 --> 00:14:18,960
Ја ћу да вам дам сваки број.

376
00:14:18,960 --> 00:14:22,150
И само напред и организује себе
идентично ономе што је

377
00:14:22,150 --> 00:14:25,180
приказан на екрану.

378
00:14:25,180 --> 00:14:26,530
>> [Изнео ВОИЦЕС]

379
00:14:26,530 --> 00:14:28,160
>> Давид Ј. Малан: ООП, извини.

380
00:14:28,160 --> 00:14:30,210
Буг.

381
00:14:30,210 --> 00:14:32,180
У реду.

382
00:14:32,180 --> 00:14:32,750
Па, идемо.

383
00:14:32,750 --> 00:14:34,180
Број пет.

384
00:14:34,180 --> 00:14:35,136
Број шест.

385
00:14:35,136 --> 00:14:37,770
Један, два, три, четири,
пет, шест, седам.

386
00:14:37,770 --> 00:14:39,410
Ох, ово је непријатно.

387
00:14:39,410 --> 00:14:41,210
>> СПИКЕР 2: Само да узмем -.

388
00:14:41,210 --> 00:14:41,900
>> Давид Ј. Малан: Добар посао.

389
00:14:41,900 --> 00:14:43,130
У реду.

390
00:14:43,130 --> 00:14:44,611
Хвала вам на учешћу.

391
00:14:44,611 --> 00:14:47,200
>> [Апплаусе]

392
00:14:47,200 --> 00:14:48,580
>> ОК.

393
00:14:48,580 --> 00:14:48,860
У реду.

394
00:14:48,860 --> 00:14:51,970
Дакле, имамо четири, два, шест,
један, три, седам, пет.

395
00:14:51,970 --> 00:14:56,010
Савршена тако да имамо седам волонтера
овде који су једнаки у ширини до

396
00:14:56,010 --> 00:14:57,430
низа да играмо
са раније.

397
00:14:57,430 --> 00:14:59,470
И ја сам изабрао седам разлога
то ће бити само

398
00:14:59,470 --> 00:15:00,840
погодан за мало.

399
00:15:00,840 --> 00:15:04,400
И ја ћу предложити да прво
можемо сложити седам волонтера.

400
00:15:04,400 --> 00:15:06,786
Ако желите, прво,
да те поздравим ипак.

401
00:15:06,786 --> 00:15:08,970
Пошто ће ово бити
незгодна неколико минута.

402
00:15:08,970 --> 00:15:10,370
Представите се.

403
00:15:10,370 --> 00:15:10,980
>> ГРАЦЕ: Здраво, ја сам Грејс.

404
00:15:10,980 --> 00:15:14,190
Ја сам студент друге године у Дому Леверетт.

405
00:15:14,190 --> 00:15:14,620
>> Брансон: Здраво.

406
00:15:14,620 --> 00:15:15,620
Ја сам Брансон.

407
00:15:15,620 --> 00:15:16,920
Ја сам бруцош у вара.

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> Габе: Здраво.

410
00:15:20,230 --> 00:15:21,040
Ја сам Гејб.

411
00:15:21,040 --> 00:15:22,300
Ја сам млађи у Кабот.

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> СКАНДАЛ: Ја сам Нил.

414
00:15:25,980 --> 00:15:29,090
Ја сам бруцош у Маттхевс.

415
00:15:29,090 --> 00:15:29,550
>> Јасон: Ја сам Јасон.

416
00:15:29,550 --> 00:15:32,816
Ја сам бруцош у Грееноугх.

417
00:15:32,816 --> 00:15:33,700
>> МИКЕ: Ја сам Мике.

418
00:15:33,700 --> 00:15:37,360
Ја сам бруцош у Граис.

419
00:15:37,360 --> 00:15:37,990
>> Јесс: Ја сам Џес.

420
00:15:37,990 --> 00:15:40,313
Ја сам студент друге у Леверетт.

421
00:15:40,313 --> 00:15:41,300
>> Давид Ј. Малан: Одлично.

422
00:15:41,300 --> 00:15:41,850
У реду.

423
00:15:41,850 --> 00:15:44,190
Па, хвала вам на свим нашим
волонтери овде до сада.

424
00:15:44,190 --> 00:15:47,110
А изазов при руци сада иде
да се на неки начин ове момке, али онда

425
00:15:47,110 --> 00:15:50,250
ћемо морати да мало
тешко о томе како ефикасно заправо

426
00:15:50,250 --> 00:15:51,110
сортирају их.

427
00:15:51,110 --> 00:15:52,580
Па хајде да прво пробамо ово.

428
00:15:52,580 --> 00:15:55,970
Момци могу да виде једни друге бројеве
само постављањем око углова.

429
00:15:55,970 --> 00:15:59,380
Само напред и да потраје неколико секунди, а
Сортирај себе од најмањих на

430
00:15:59,380 --> 00:16:01,240
препуштен највећи десно.

431
00:16:01,240 --> 00:16:02,490
Го.

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> ОК.

434
00:16:07,530 --> 00:16:08,030
Добро.

435
00:16:08,030 --> 00:16:09,370
То је заиста проклето брзо.

436
00:16:09,370 --> 00:16:14,040
Сада је неко овде, шта је алгоритам
да ови момци примењује?

437
00:16:14,040 --> 00:16:14,900
>> СПИКЕР 1: најмање до највеће.

438
00:16:14,900 --> 00:16:15,000
>> Давид Ј. Малан: У реду.

439
00:16:15,000 --> 00:16:18,070
Најмање да је највећи заиста некако
објективан, али нисам сигуран да је то

440
00:16:18,070 --> 00:16:18,890
Стварно алгоритам.

441
00:16:18,890 --> 00:16:21,810
Најмање се највећи не говори
ми корак по корак шта да радим.

442
00:16:21,810 --> 00:16:22,833
Да?

443
00:16:22,833 --> 00:16:24,083
>> СПИКЕР 1: [ИНАУДИБЛЕ]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> Давид Ј. Малан: У реду.

446
00:16:26,280 --> 00:16:28,920
Дакле, ако видите лице мањи од
ваш број, а затим прећи на

447
00:16:28,920 --> 00:16:29,680
право на њих.

448
00:16:29,680 --> 00:16:32,800
Тако да је сада све израженије,
више као алгоритма, јер сте

449
00:16:32,800 --> 00:16:35,410
могу да кажем, ако је то, онда да.

450
00:16:35,410 --> 00:16:37,050
Дакле, имамо неку врсту
условни конструкт.

451
00:16:37,050 --> 00:16:39,700
А ови момци изгледа да се то уради неколико
времена, јер неки од вас преселили мало

452
00:16:39,700 --> 00:16:40,420
из даљине.

453
00:16:40,420 --> 00:16:43,410
Тако да је вероватно нека врста
лоопинг дешава у њиховим главама.

454
00:16:43,410 --> 00:16:44,610
>> Али, хајде да покушамо да то формализује.

455
00:16:44,610 --> 00:16:47,540
Ако сте могли поново вратити
на овај аранжман.

456
00:16:47,540 --> 00:16:50,650
Да видимо да не можемо да формализују
битни, а онда постави питање, само

457
00:16:50,650 --> 00:16:51,580
колико је ефикасан је ово?

458
00:16:51,580 --> 00:16:54,220
Наравно, када смо то урадили спорије,
то ће да се осећају као добра од

459
00:16:54,220 --> 00:16:57,210
алгоритам, али хајде да видимо да ли можемо
стави прсте на прецизним корацима.

460
00:16:57,210 --> 00:16:58,670
>> Дакле, вас двојица су и два четири.

461
00:16:58,670 --> 00:17:01,020
Или сте тачно или нетачно како?

462
00:17:01,020 --> 00:17:01,900
Очигледно нетачна.

463
00:17:01,900 --> 00:17:02,710
Тако смо се заменили.

464
00:17:02,710 --> 00:17:05,170
Сада ћу да се креће у страну
овде и кажем, четири до шест.

465
00:17:05,170 --> 00:17:06,240
Да ли сте тачно или нетачно?

466
00:17:06,240 --> 00:17:06,599
>> Габе: Тачно.

467
00:17:06,599 --> 00:17:07,180
>> Давид Ј. Малан: Тачно.

468
00:17:07,180 --> 00:17:08,300
Шест и један?

469
00:17:08,300 --> 00:17:08,609
Јок.

470
00:17:08,609 --> 00:17:09,630
Свап.

471
00:17:09,630 --> 00:17:10,490
Дакле, то су два свопови.

472
00:17:10,490 --> 00:17:11,710
Шест и три?

473
00:17:11,710 --> 00:17:11,980
Јок.

474
00:17:11,980 --> 00:17:13,000
Свап.

475
00:17:13,000 --> 00:17:13,930
Шест и седам?

476
00:17:13,930 --> 00:17:14,630
Изгледа добро.

477
00:17:14,630 --> 00:17:15,396
Седам и пет?

478
00:17:15,396 --> 00:17:16,150
>> Јесс: [ИНАУДИБЛЕ]

479
00:17:16,150 --> 00:17:17,089
>> Давид Ј. Малан: У реду, замените.

480
00:17:17,089 --> 00:17:19,770
И сортирају.

481
00:17:19,770 --> 00:17:19,980
У реду.

482
00:17:19,980 --> 00:17:21,440
Очигледно не, зар не?

483
00:17:21,440 --> 00:17:22,470
Дакле, било је више дешава.

484
00:17:22,470 --> 00:17:24,920
Али, заиста, ови момци, чак
баш инстинктивно.

485
00:17:24,920 --> 00:17:25,450
стално креће.

486
00:17:25,450 --> 00:17:27,710
Нису само зауставити, када су
исправио један проблем.

487
00:17:27,710 --> 00:17:27,839
Тако.

488
00:17:27,839 --> 00:17:29,390
Заиста, ја ћу имати
да уради исту ствар.

489
00:17:29,390 --> 00:17:32,720
Ја ћу морати да некако премотавање леђа
до почетка овог проблема,

490
00:17:32,720 --> 00:17:35,630
или почетак овог низа
људи, хајде да почнемо да их зове.

491
00:17:35,630 --> 00:17:38,366
>> И шта сада треба мој алгоритам
на другом пролазу бити?

492
00:17:38,366 --> 00:17:39,220
>> СПИКЕР 1: Иста ствар.

493
00:17:39,220 --> 00:17:39,940
>> Давид Ј. Малан: Иста ствар.

494
00:17:39,940 --> 00:17:41,460
И ово, ја почињем да се свиђа, зар не?

495
00:17:41,460 --> 00:17:44,720
Чим можете да нађете раде
иста ствар изнова и изнова, то је

496
00:17:44,720 --> 00:17:47,890
све више као алгоритма,
а мање људски инстинкт.

497
00:17:47,890 --> 00:17:48,680
>> Дакле, сада, ево нас опет.

498
00:17:48,680 --> 00:17:49,870
Два и четири?

499
00:17:49,870 --> 00:17:50,220
Не.

500
00:17:50,220 --> 00:17:51,050
Четири и један?

501
00:17:51,050 --> 00:17:53,380
Ах, заиста је било неких
ради тога да се уради.

502
00:17:53,380 --> 00:17:53,620
За и три?

503
00:17:53,620 --> 00:17:54,572
Добро.

504
00:17:54,572 --> 00:17:56,000
Четири и шест?

505
00:17:56,000 --> 00:17:58,380
Шест и пет?

506
00:17:58,380 --> 00:17:59,470
Шест и седам?

507
00:17:59,470 --> 00:18:00,970
У реду, сада, урађено.

508
00:18:00,970 --> 00:18:01,550
ОК, нема.

509
00:18:01,550 --> 00:18:02,710
Морам да се вратим.

510
00:18:02,710 --> 00:18:05,130
>> Тако да сада, опет, ово радимо
мало намерно.

511
00:18:05,130 --> 00:18:08,700
А сада, постоји само један мозак
реализацији овог алгоритма.

512
00:18:08,700 --> 00:18:10,290
Један процесор, ако хоћете.

513
00:18:10,290 --> 00:18:13,090
И искрено, то је једини ресурс
ћемо имати приступ.

514
00:18:13,090 --> 00:18:16,280
А када се вратимо на тастатури
и имају нешто као Ц на нашем

515
00:18:16,280 --> 00:18:19,600
одлагање, ми само писање програма
то може да уради само једну ствар у исто време.

516
00:18:19,600 --> 00:18:22,900
Док, ови момци малопре, ми
искористио њихов колективни памет

517
00:18:22,900 --> 00:18:24,180
као што сте урадили у недељу нуле.

518
00:18:24,180 --> 00:18:24,980
Па хајде да наставим да радим ово.

519
00:18:24,980 --> 00:18:26,260
>> Два и један.

520
00:18:26,260 --> 00:18:26,945
Два и три.

521
00:18:26,945 --> 00:18:27,460
Три и четири.

522
00:18:27,460 --> 00:18:28,310
Четири и пет.

523
00:18:28,310 --> 00:18:28,620
Пет и шест.

524
00:18:28,620 --> 00:18:30,510
Шест и седам.

525
00:18:30,510 --> 00:18:31,880
Готово?

526
00:18:31,880 --> 00:18:34,560
И ја сам, али дозволите ми да играм
ђавољег адвоката.

527
00:18:34,560 --> 00:18:37,950
Да ли ми, врста рачунара који само
направио пролаз кроз овај низ

528
00:18:37,950 --> 00:18:40,225
људи, знам да сам урадио?

529
00:18:40,225 --> 00:18:40,670
>> СПИКЕР 1: Не.

530
00:18:40,670 --> 00:18:41,050
>> Давид Ј. Малан: Зашто?

531
00:18:41,050 --> 00:18:46,900
Оно што бих ја морао да урадим да би
децидно закључити да сам урадио?

532
00:18:46,900 --> 00:18:48,230
Вероватно још један пролаз.

533
00:18:48,230 --> 00:18:48,430
Зар не?

534
00:18:48,430 --> 00:18:51,760
Јер ја знам да од претходна
центаршут је да сам исправио грешку.

535
00:18:51,760 --> 00:18:53,920
А то значи, можда постоји
још један грешка

536
00:18:53,920 --> 00:18:54,840
да треба да се исправи.

537
00:18:54,840 --> 00:18:58,680
Тако да можете бити сигурни само по премотавања, и
онда проверу, један до два, два и

538
00:18:58,680 --> 00:19:00,940
три, три и четири, четири и пет,
пет и шест, шест и седам.

539
00:19:00,940 --> 00:19:02,510
У реду, сада сам без посла.

540
00:19:02,510 --> 00:19:05,990
>> Свакако могу да се сетим да сам не
ради са нечим као променљиве,

541
00:19:05,990 --> 00:19:06,975
као инт.

542
00:19:06,975 --> 00:19:12,490
Назовите то свопови, а ако је свопови 0 Једном сам
Овде се, а она је почела на 0, онда

543
00:19:12,490 --> 00:19:15,520
Само би било глупо да наставим
и назад, проверу поново, и

544
00:19:15,520 --> 00:19:16,450
опет, и опет, зар не?

545
00:19:16,450 --> 00:19:18,450
Зато што се заглави у неким
врсту бесконачне петље.

546
00:19:18,450 --> 00:19:21,250
Дакле, чим има 0 свопови,
можемо тврдити да је ово

547
00:19:21,250 --> 00:19:23,810
алгоритам је заиста потпун.

548
00:19:23,810 --> 00:19:25,400
>> Сада, хајде да стави име на то.

549
00:19:25,400 --> 00:19:28,930
Алгоритам који сам предлажемо управо
спроводи се нешто што се зове Буббле

550
00:19:28,930 --> 00:19:32,800
врста, као што је познато, у смислу да
бројеви који су већи врста

551
00:19:32,800 --> 00:19:37,990
Буббле свој пут до врха, или се
до краја низа бројева.

552
00:19:37,990 --> 00:19:40,270
Али како је ово ефикасан алгоритам?

553
00:19:40,270 --> 00:19:44,600
Колико корака сам физички да
Узмимо, на пример, да се сложити

554
00:19:44,600 --> 00:19:45,850
седам људи?

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> Четири до пет?

557
00:19:49,550 --> 00:19:51,420
Ок, превише је на крају
ће бити одговор.

558
00:19:51,420 --> 00:19:54,960
Али чак и тада, одређени број
није толико интересантно.

559
00:19:54,960 --> 00:19:56,670
Хајде да се генерализује као Н.

560
00:19:56,670 --> 00:20:00,520
Дакле, ако сам н људи овде, и они су
били су, на неки начин, случајним редоследом на

561
00:20:00,520 --> 00:20:02,180
почетак, у том оригиналном редоследу.

562
00:20:02,180 --> 00:20:04,910
Па, колико сам ја имао корака
да се на првом пролазу?

563
00:20:04,910 --> 00:20:09,810
То је био један, два, три, четири, пет,
шест, седам и они су људи, па

564
00:20:09,810 --> 00:20:13,670
То је седам, шест -, тако да је н
минус један кораке први пут.

565
00:20:13,670 --> 00:20:16,280
>> Сада, колико корака сам морао
да се, када сам поново ранити?

566
00:20:16,280 --> 00:20:19,310
Па, ми смо у ствари могао да се удвостручи уколико то
ми смо заиста желели да, али за сада, ја сам

567
00:20:19,310 --> 00:20:22,300
Само ћу рећи, у реду,
још један минус 1 н.

568
00:20:22,300 --> 00:20:25,240
Тако Н минус 1 ће добити
непријатно да пратите, па хајде да

569
00:20:25,240 --> 00:20:26,400
само око навише.

570
00:20:26,400 --> 00:20:27,770
Дакле 2н корака.

571
00:20:27,770 --> 00:20:29,310
Дакле 14 корака, узми или остави.

572
00:20:29,310 --> 00:20:31,930
>> Колико пута сам узети
корак следећи пут?

573
00:20:31,930 --> 00:20:33,740
Па, то је 3н.

574
00:20:33,740 --> 00:20:34,510
стварно.

575
00:20:34,510 --> 00:20:37,920
А сада, у најгорем случају, за
пример, колико пута ћу морати

576
00:20:37,920 --> 00:20:41,730
отишао напред и назад, напред и назад,
реализацији овог алгоритма, замене

577
00:20:41,730 --> 00:20:44,620
људи на сваком пролазу, отприлике?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
То је у ствари н на квадрат, зар не?

580
00:20:50,010 --> 00:20:53,000
>> Зато што у најгорем случају, можете да некако
од мисли о овоме интуитивно,

581
00:20:53,000 --> 00:20:54,800
иако можда ће бити потребно мало
мало времена да тоне унутра

582
00:20:54,800 --> 00:20:57,590
У најгорем случају, шта би ови
седам људи је изгледало, у

583
00:20:57,590 --> 00:21:00,230
услови споразума
њиховог броја?

584
00:21:00,230 --> 00:21:01,460
Потпуно уназад, зар не?

585
00:21:01,460 --> 00:21:02,815
И само да симулира да је,
Како се оно зовеш?

586
00:21:02,815 --> 00:21:03,360
>> МИКЕ: Мајк.

587
00:21:03,360 --> 00:21:03,640
>> Давид Ј. Малан: Мајк?

588
00:21:03,640 --> 00:21:08,100
ОК, Мајк, да ли можете да ми се придружите у
овде на секунд?

589
00:21:08,100 --> 00:21:08,880
Заправо, не.

590
00:21:08,880 --> 00:21:10,150
Жао нам је Мајк, хајде да уназад.

591
00:21:10,150 --> 00:21:10,910
Како се зовеш?

592
00:21:10,910 --> 00:21:11,180
>> СКАНДАЛ: Неил.

593
00:21:11,180 --> 00:21:11,640
>> Давид Ј. Малан: Нил.

594
00:21:11,640 --> 00:21:13,750
Ок, Нил, идеш са
ми, ако ти не смета.

595
00:21:13,750 --> 00:21:17,150
Зато ћу предложити, само за
једноставност, да је Нил је сада у његовом

596
00:21:17,150 --> 00:21:18,510
најгори могући случај.

597
00:21:18,510 --> 00:21:20,720
Али, сећам се како сам се спроводи
мој алгоритам.

598
00:21:20,720 --> 00:21:24,530
Ја сам у односу, у односу, у односу,
поређења, поређења, ох.

599
00:21:24,530 --> 00:21:26,640
Сада ови момци су ван
реда, па сам поправити.

600
00:21:26,640 --> 00:21:27,980
Дакле, ви мењате.

601
00:21:27,980 --> 00:21:31,630
Али сада размислите, колико даље
нема Неил да идем?

602
00:21:31,630 --> 00:21:32,690
То је отприлике н.

603
00:21:32,690 --> 00:21:33,570
Знате, то није стварно н.

604
00:21:33,570 --> 00:21:36,040
То је као, Н минус 1, али ја сам све
изнервиран праћење мало

605
00:21:36,040 --> 00:21:37,550
број, па назовимо га н.

606
00:21:37,550 --> 00:21:42,860
>> Дакле, ако Нил помера један корак максимално сваки
време, и да се крећу Неил један корак,

607
00:21:42,860 --> 00:21:46,580
Морам да ово стварно досадан пас
и назад, то је отприлике

608
00:21:46,580 --> 00:21:52,080
При томе, н корака, укупно н пута,
јер ће ме одвести

609
00:21:52,080 --> 00:21:55,820
да су многи кораци да се Нил све
начин да се тамо где припада.

610
00:21:55,820 --> 00:21:58,620
А камоли сви остали, ако сте
Сви су погрешно наредио као добро.

611
00:21:58,620 --> 00:22:01,100
>> Дакле, назовимо врсту балон н квадрат.

612
00:22:01,100 --> 00:22:04,860
Време извршавања овог алгоритма,
Перформансе овог алгоритма,

613
00:22:04,860 --> 00:22:07,120
Ефикасност овог алгоритма,
овде ћемо описати више

614
00:22:07,120 --> 00:22:08,800
углавном као н на квадрат.

615
00:22:08,800 --> 00:22:11,650
Што је лепо, јер сам могао да урадим
исти пример са осам, девет људи

616
00:22:11,650 --> 00:22:15,450
људи, а милион људи и да
Одговор се неће променити.

617
00:22:15,450 --> 00:22:18,870
>> Дакле, ако ви немате ништа против, хајде да
ресет вас тамо где сте почели.

618
00:22:18,870 --> 00:22:22,510
А да пробамо два приступа и
видим да ми не можемо учинити суштински

619
00:22:22,510 --> 00:22:23,820
боље од овога.

620
00:22:23,820 --> 00:22:27,130
Дакле ово време, ја ћу предложити
различитих врста алгоритма.

621
00:22:27,130 --> 00:22:29,950
То је било веома паметно од нас последњи пут,
и да сте били у праву да

622
00:22:29,950 --> 00:22:32,470
право инстинкти некако
од замене Паирвисе.

623
00:22:32,470 --> 00:22:36,500
Али, ако сам стварно желео да се обрате ово
једноставно, а мој циљ је да се

624
00:22:36,500 --> 00:22:39,800
све мале бројеве на овај начин, и
гурните све од великих бројева који

625
00:22:39,800 --> 00:22:43,030
начин, зашто не бих то да урадим у
најнаивнији начин је могуће и видети да ли

626
00:22:43,030 --> 00:22:45,730
може да уради боље него што је било
прилично сложен алгоритам?

627
00:22:45,730 --> 00:22:46,620
>> Па да видимо.

628
00:22:46,620 --> 00:22:48,940
Четири је прилично мали број, тако да сам
ће вас оставити тамо тренутак.

629
00:22:48,940 --> 00:22:50,610
Оох, број два је још боље.

630
00:22:50,610 --> 00:22:52,230
Дакле, можете ли само корак напред
за тренутак?

631
00:22:52,230 --> 00:22:55,670
Ово је сада моја најмања нумерисана
кандидат, а ја ћу да се сетим

632
00:22:55,670 --> 00:22:57,000
да са, рецимо, променљиву.

633
00:22:57,000 --> 00:22:57,930
Али, ја ћу да провере.

634
00:22:57,930 --> 00:22:59,890
Да ли постоји неко ко је
број је мањи?

635
00:22:59,890 --> 00:23:00,460
Шест, бр.

636
00:23:00,460 --> 00:23:01,390
Ох, има Нил поново.

637
00:23:01,390 --> 00:23:04,050
>> Дакле, ја ћу да вас одгурне
врста концептуално.

638
00:23:04,050 --> 00:23:05,120
Нил ће напред доћи.

639
00:23:05,120 --> 00:23:08,440
А сада, променљиве које ја користим да
пратити ко има најмањи

640
00:23:08,440 --> 00:23:11,390
број се ажурира да садржи
Неил је локација.

641
00:23:11,390 --> 00:23:12,110
Па, хајде да видимо.

642
00:23:12,110 --> 00:23:13,960
Три, седам, пет.

643
00:23:13,960 --> 00:23:15,590
ОК, знам Нил био најмањи.

644
00:23:15,590 --> 00:23:18,110
Шта је најједноставније
ми сада да радимо?

645
00:23:18,110 --> 00:23:21,410
Нећу да трошим време само
бистрим Нил за једно место улево.

646
00:23:21,410 --> 00:23:25,350
Зашто не бих ставио Нила, где је
припада, што је, наравно, где?

647
00:23:25,350 --> 00:23:26,160
>> Скроз на почетку.

648
00:23:26,160 --> 00:23:27,720
Дакле Неил, пођи са мном.

649
00:23:27,720 --> 00:23:28,910
А шта је зовеш?

650
00:23:28,910 --> 00:23:29,310
>> МИЛОСТ: Грејс.

651
00:23:29,310 --> 00:23:29,710
>> Давид Ј. Малан: Грејс.

652
00:23:29,710 --> 00:23:29,920
ОК.

653
00:23:29,920 --> 00:23:32,490
Дакле Грејс, нажалост, ти си
врста на путу.

654
00:23:32,490 --> 00:23:34,290
Дакле, како да решим овај проблем?

655
00:23:34,290 --> 00:23:34,490
Зар не?

656
00:23:34,490 --> 00:23:37,500
Ако је низ, ту је
Само седам локација.

657
00:23:37,500 --> 00:23:40,830
Подсетимо се да је, са Робом, разговарали смо о
декларисање доба, а ми смо имали само

658
00:23:40,830 --> 00:23:41,740
коначан број векова?

659
00:23:41,740 --> 00:23:42,535
Иста идеја овде.

660
00:23:42,535 --> 00:23:44,300
Имамо само коначан број интс.

661
00:23:44,300 --> 00:23:47,590
Милост је врста у нашој
начин, па како да поправим?

662
00:23:47,590 --> 00:23:49,555
>> Најједноставнији начин је да,
Грејс, извини.

663
00:23:49,555 --> 00:23:51,870
Ти ћеш морати да иде преко
тамо тако да можемо направити собу.

664
00:23:51,870 --> 00:23:55,290
Сада, ако мислите о томе, можда
ми смо само направили проблем још горим.

665
00:23:55,290 --> 00:23:58,510
А можда смо, јер шта ако
Грејс су били на правом месту?

666
00:23:58,510 --> 00:24:01,730
Али ми знамо да није, јер
у супротном, она би била

667
00:24:01,730 --> 00:24:03,980
напред стоји уместо
Нил у то време, зар не?

668
00:24:03,980 --> 00:24:05,550
Већ смо проверили њен број напоље.

669
00:24:05,550 --> 00:24:05,770
>> У реду.

670
00:24:05,770 --> 00:24:09,110
Тако да сада, Нил је на правом месту, и
Ја могу да урадим благи оптимизацију.

671
00:24:09,110 --> 00:24:11,740
У следећем минуту, ја ћу игнорисати
Нил сви заједно, тако да не

672
00:24:11,740 --> 00:24:15,280
губи време, или случајно
свап га на погрешно место.

673
00:24:15,280 --> 00:24:17,805
Па сад, како да надјем следећи
елемент који је најмањи?

674
00:24:17,805 --> 00:24:18,480
Два.

675
00:24:18,480 --> 00:24:20,225
То је прилично добар број, ако
желите да иступи и

676
00:24:20,225 --> 00:24:21,100
Ја ћу те се.

677
00:24:21,100 --> 00:24:21,980
Шест, није добро.

678
00:24:21,980 --> 00:24:24,820
Четири, три, седам, пет, није добро.

679
00:24:24,820 --> 00:24:26,800
Дакле, да пређемо на ти
Ваше право место.

680
00:24:26,800 --> 00:24:28,470
И управо смо среће овај пут.

681
00:24:28,470 --> 00:24:31,350
>> Сада, ја ћу игнорисати ово
два момка, а сада још један

682
00:24:31,350 --> 00:24:32,260
пролазе кроз ово.

683
00:24:32,260 --> 00:24:33,490
Шест, то прилично мали број.

684
00:24:33,490 --> 00:24:34,300
Идемо напред.

685
00:24:34,300 --> 00:24:35,220
Ох, извините.

686
00:24:35,220 --> 00:24:37,640
Граце број је боље,
тако корак даље напред.

687
00:24:37,640 --> 00:24:38,260
Четири.

688
00:24:38,260 --> 00:24:39,120
Извини, Грејс.

689
00:24:39,120 --> 00:24:39,950
Врати се поново.

690
00:24:39,950 --> 00:24:41,550
Број три је боље.

691
00:24:41,550 --> 00:24:42,290
Седам.

692
00:24:42,290 --> 00:24:42,720
Пет.

693
00:24:42,720 --> 00:24:43,550
И шта сада зовеш?

694
00:24:43,550 --> 00:24:44,000
>> Јасон: Јасон.

695
00:24:44,000 --> 00:24:44,420
>> Давид Ј. Малан: Јасон.

696
00:24:44,420 --> 00:24:47,050
Дакле, Џејсон је сада најмањи
Елемент сам изабрао.

697
00:24:47,050 --> 00:24:49,160
Где ли он да иде?

698
00:24:49,160 --> 00:24:50,380
Дакле, где је шест.

699
00:24:50,380 --> 00:24:51,210
И твоје име је опет?

700
00:24:51,210 --> 00:24:51,710
>> Габе: Гејб.

701
00:24:51,710 --> 00:24:52,340
>> Давид Ј. Малан: Гејб.

702
00:24:52,340 --> 00:24:53,220
Гејб је на путу.

703
00:24:53,220 --> 00:24:54,640
Шта је најлакше да уради?

704
00:24:54,640 --> 00:24:58,390
Свап ова два момка и даље.

705
00:24:58,390 --> 00:24:59,020
Сада да видимо.

706
00:24:59,020 --> 00:25:00,170
Ко је најмањи?

707
00:25:00,170 --> 00:25:01,030
Четири.

708
00:25:01,030 --> 00:25:01,990
Само да некако варају.

709
00:25:01,990 --> 00:25:03,090
Пет ће бити најмањи.

710
00:25:03,090 --> 00:25:05,220
Мислим да следећи, ако, желите да корак
напред, шта ја треба да урадим са

711
00:25:05,220 --> 00:25:06,820
ови момци, са Габе?

712
00:25:06,820 --> 00:25:08,450
Свап поново.

713
00:25:08,450 --> 00:25:10,740
Тако да сада, још увек мало у квару.

714
00:25:10,740 --> 00:25:14,140
Нашао сам Гејб да буде најмања, тако
Ја га поп, померите се момци изнад.

715
00:25:14,140 --> 00:25:15,190
И урадио.

716
00:25:15,190 --> 00:25:17,200
>> Дакле, одговор је исти.

717
00:25:17,200 --> 00:25:18,600
Крајњи резултат је исти.

718
00:25:18,600 --> 00:25:22,730
Који од ова два алгоритма
је бољи?

719
00:25:22,730 --> 00:25:23,500
Други, чуо сам.

720
00:25:23,500 --> 00:25:24,252
Зашто?

721
00:25:24,252 --> 00:25:25,900
>> ПРЕДСЕДНИК 3: То је н корака [ИНАУДИБЛЕ].

722
00:25:25,900 --> 00:25:27,600
>> Давид Ј. Малан: То је н корака највише.

723
00:25:27,600 --> 00:25:28,490
Занимљиво.

724
00:25:28,490 --> 00:25:30,610
Тако да је, иако?

725
00:25:30,610 --> 00:25:33,630
Па како да нађем
Најмањи елемент?

726
00:25:33,630 --> 00:25:37,060
Колико корака сам морао да се
наћи најмањи елемент?

727
00:25:37,060 --> 00:25:39,220
Ја сам изгледа скроз
на крају, зар не?

728
00:25:39,220 --> 00:25:41,530
Јер у том најгорем случају, шта
ако је Нил био овде?

729
00:25:41,530 --> 00:25:45,700
Дакле, само налаз најмањи елемент
Потребно ми н корака, или Н минус 1.

730
00:25:45,700 --> 00:25:46,100
Али, у реду.

731
00:25:46,100 --> 00:25:46,980
Тако поправити Нила.

732
00:25:46,980 --> 00:25:48,740
Не заборавите да, минут или тако.

733
00:25:48,740 --> 00:25:51,680
>> Али, како сам наћи следећи
Најмањи елемент?

734
00:25:51,680 --> 00:25:54,830
То је минус н 1, н или минус 2 заиста,
од броја корака.

735
00:25:54,830 --> 00:25:55,440
Дакле, у реду.

736
00:25:55,440 --> 00:25:57,390
Тако сам и урадио н минус 2.

737
00:25:57,390 --> 00:25:57,600
У реду.

738
00:25:57,600 --> 00:25:59,130
Дакле, да се осећа мало боље.

739
00:25:59,130 --> 00:25:59,730
У реду.

740
00:25:59,730 --> 00:26:03,270
Колико корака следећи пут
да пронађе број три?

741
00:26:03,270 --> 00:26:04,420
Дакле н минус 4.

742
00:26:04,420 --> 00:26:07,670
Тако да је смањује, један мање
корак на свакој итерацији.

743
00:26:07,670 --> 00:26:08,740
Дакле, то не осећа боље, зар не?

744
00:26:08,740 --> 00:26:13,450
Ако последњи пут је то било отприлике н пута Н,
овај пут је н минус 1, плус Н минус

745
00:26:13,450 --> 00:26:16,500
2, Н плус минус 3, плус н
минус 4, тачка, тачка, тачка.

746
00:26:16,500 --> 00:26:18,750
Али, ако се сећате из средње школе
уџбеници, мало подвалити

747
00:26:18,750 --> 00:26:24,380
лист на леђима који има формуле, ако
додате ову серију бројева,

748
00:26:24,380 --> 00:26:31,280
што је укупан број корака
Биће да сам овде узети?

749
00:26:31,280 --> 00:26:36,580
>> Ово је један од оних који, као, н минус
1, н пута, подељено са 2.

750
00:26:36,580 --> 00:26:39,040
Па да видим да ли могу да се повуче
ово за тренутак.

751
00:26:39,040 --> 00:26:42,230
А опет, некако сам заокруживања неке
Бројеви само да би наш живот једноставан,

752
00:26:42,230 --> 00:26:47,830
али колико се сећам, то је нешто као кад
Ја н минус 1 ствари, онда н минус

753
00:26:47,830 --> 00:26:53,570
2, затим н минус 3, она има
овако нешто више од 2, а ако ја

754
00:26:53,570 --> 00:26:55,510
помножите ово, то је
заправо н квадрат.

755
00:26:55,510 --> 00:26:58,940
То се не осећа добро.
н н минус преко 2.

756
00:26:58,940 --> 00:27:00,350
>> Али овде је ствар.

757
00:27:00,350 --> 00:27:03,720
У рачунарству, кад су проблеми
почети да се интересантно је кад н

758
00:27:03,720 --> 00:27:04,700
постаје заиста велики.

759
00:27:04,700 --> 00:27:08,110
А када н постаје заиста велики, који од
ове вредности ће доминирати све

760
00:27:08,110 --> 00:27:09,750
од осталих?

761
00:27:09,750 --> 00:27:10,990
То је нешто о н квадрата, зар не?

762
00:27:10,990 --> 00:27:13,340
Да, дељењем са 2 је прилично добар.

763
00:27:13,340 --> 00:27:16,740
Али ако говоримо о милијардама
комада података или трилионе

764
00:27:16,740 --> 00:27:18,700
делови података, ОК, дакле
ти си дупло брже.

765
00:27:18,700 --> 00:27:22,440
Али кога је брига да ли стварно тај велики број,
ако је овај фактор је што добија

766
00:27:22,440 --> 00:27:23,040
све веће и веће.

767
00:27:23,040 --> 00:27:25,990
И сигурно, то је више од
разлика од овог типа.

768
00:27:25,990 --> 00:27:29,120
Дакле, иако сте у праву,
Други алгоритам, ми ћемо га назвати

769
00:27:29,120 --> 00:27:32,970
Избор врста, је, у стварном свету,
мало брже потенцијално, јер сам

770
00:27:32,970 --> 00:27:35,360
узимање мање и мање
кораке сваки пут.

771
00:27:35,360 --> 00:27:37,340
>> То није баш фундаментално брже.

772
00:27:37,340 --> 00:27:41,430
Јер ако ми у ствари игра се за ово
велике вредности н, на крају

773
00:27:41,430 --> 00:27:44,750
дан, за довољно велику н, то је још увек
ће се осећати прилично споро.

774
00:27:44,750 --> 00:27:46,770
Па, дозволите ми да једну
последњи пролаз у то.

775
00:27:46,770 --> 00:27:48,920
То је оно што бих ја назвао
Избор врста.

776
00:27:48,920 --> 00:27:51,040
Можете ли себе поново
последњи пут?

777
00:27:51,040 --> 00:27:53,550
И у овом последњем случају, ја ћу
да предложи нешто

778
00:27:53,550 --> 00:27:54,970
зове уметања сорт.

779
00:27:54,970 --> 00:27:57,470
Уношење врста бића, концептуално,
мало другачије.

780
00:27:57,470 --> 00:28:00,980
>> Уместо да иде напред и назад и
изабрати најмањи елемент, ја сам

781
00:28:00,980 --> 00:28:05,030
само да се осврнем на сваки од њих
момци као што сам их срести, и убаците

782
00:28:05,030 --> 00:28:06,850
их у своје одговарајуће место.

783
00:28:06,850 --> 00:28:10,160
Дакле, ја ћу само да се почне са Граце,
и ја видим да је она број четири.

784
00:28:10,160 --> 00:28:11,720
Где се број четири припада?

785
00:28:11,720 --> 00:28:14,940
Нисам почео сортирање ништа,
Грејс добија тако да остане тамо.

786
00:28:14,940 --> 00:28:18,355
А сада ћу да тврдим, ако би могао
предузме неки корак у десно, ово

787
00:28:18,355 --> 00:28:21,650
мој сортирана листа, ово је мој
некласификовани остатак листе.

788
00:28:21,650 --> 00:28:23,260
Сада ћу наставити следећи,
и како ти је име?

789
00:28:23,260 --> 00:28:23,700
>> Брансон: Бренсон.

790
00:28:23,700 --> 00:28:24,150
>> Давид Ј. Малан: Бренсон.

791
00:28:24,150 --> 00:28:25,375
Дакле, Бренсон је број два.

792
00:28:25,375 --> 00:28:27,490
Дакле, ја ћу вас одвести
се за тренутак.

793
00:28:27,490 --> 00:28:30,940
А сада, где припадате
у овом низу?

794
00:28:30,940 --> 00:28:32,360
Дакле, десно од благодати.

795
00:28:32,360 --> 00:28:35,670
Па опет, ми смо некако доношења
Грејс до овде много посла.

796
00:28:35,670 --> 00:28:37,290
Где да те ставим?

797
00:28:37,290 --> 00:28:40,120
Дакле, ми ћемо да вам да померите
лево, и ту убаците Брансон.

798
00:28:40,120 --> 00:28:41,680
Али сада ја тврдим да
момци су урадили.

799
00:28:41,680 --> 00:28:43,240
Али, погледајте, ја не користим додатни простор.

800
00:28:43,240 --> 00:28:45,130
Још увек је 2 елемента
овде, 5. овамо.

801
00:28:45,130 --> 00:28:47,910
Укупно је ред величине 7, тако да сам
не варају, у реду?

802
00:28:47,910 --> 00:28:51,950
>> Тако да сада имамо, са Габе овде,
број шест, где си ти?

803
00:28:51,950 --> 00:28:52,650
Имаш среће поново.

804
00:28:52,650 --> 00:28:53,820
Тако добијате да остану тамо.

805
00:28:53,820 --> 00:28:57,210
Само се благо корак десно
Само да буде јасно да сте сортирају.

806
00:28:57,210 --> 00:29:00,520
А сада имамо опет Нила, број
један, где идете?

807
00:29:00,520 --> 00:29:03,540
А сада је место где ћемо почети да видимо да
Овај алгоритам, иако на први

808
00:29:03,540 --> 00:29:05,950
поглед, осећа прилично паметан, гледати
шта ће се десити.

809
00:29:05,950 --> 00:29:07,370
Ако можете да иступи.

810
00:29:07,370 --> 00:29:09,260
>> Где желимо да стави Нила?

811
00:29:09,260 --> 00:29:11,830
Дакле, очигледно овде, па како
да стигнемо тамо Нила?

812
00:29:11,830 --> 00:29:12,970
Хајде да урадимо ово корак по корак.

813
00:29:12,970 --> 00:29:15,620
Гејб, где треба да идете?

814
00:29:15,620 --> 00:29:19,590
Да, тако се један велики корак,
или два пола-корака да направи

815
00:29:19,590 --> 00:29:20,820
један корак тамо.

816
00:29:20,820 --> 00:29:21,750
Грејс, где идете?

817
00:29:21,750 --> 00:29:22,510
Добро.

818
00:29:22,510 --> 00:29:23,500
Дакле, још један корак.

819
00:29:23,500 --> 00:29:24,960
И на крају, Бренсон?

820
00:29:24,960 --> 00:29:25,460
Још један корак.

821
00:29:25,460 --> 00:29:27,190
И сада можемо да ставимо Неил на своје место.

822
00:29:27,190 --> 00:29:28,440
>> Дакле, сада, и даље ту логику.

823
00:29:28,440 --> 00:29:32,420
Иако ми се не мења Нила
више, и више, и више, да га стави

824
00:29:32,420 --> 00:29:36,420
где он иде, у најгорем случају,
Следећи број можемо наићи могли

825
00:29:36,420 --> 00:29:42,220
бити број, кажу, било је више
нула, онда ћемо да смени све

826
00:29:42,220 --> 00:29:42,730
ови момци.

827
00:29:42,730 --> 00:29:44,950
Претпоставимо да постоји број, негативан
један, онда морамо да се пребаци

828
00:29:44,950 --> 00:29:46,080
све ове момке.

829
00:29:46,080 --> 00:29:48,500
Дакле, стварно смо некако превртања
Проблем око, тако да смо

830
00:29:48,500 --> 00:29:52,620
преноса трошак од
селекције тако уметање

831
00:29:52,620 --> 00:29:56,930
процес, тако да сте управо имали
да се креће отприлике н минус нешто

832
00:29:56,930 --> 00:29:57,940
број корака.

833
00:29:57,940 --> 00:30:01,200
И тај број корака је само иде
да се повећа како да изаберем више бројева,

834
00:30:01,200 --> 00:30:04,730
ако морам да гура момци
назад, и поново, и поново.

835
00:30:04,730 --> 00:30:08,320
>> Тако тужна ствар сада је све ово
алгоритми су н на квадрат.

836
00:30:08,320 --> 00:30:10,570
Идемо напред и захваљујући оваквим
момци, а замислите ове мало

837
00:30:10,570 --> 00:30:11,090
другачије.

838
00:30:11,090 --> 00:30:12,312
Врло добро урађено.

839
00:30:12,312 --> 00:30:14,120
>> [Апплаусе]

840
00:30:14,120 --> 00:30:15,030
>> У реду.

841
00:30:15,030 --> 00:30:16,280
Изволи.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Хвала за -

844
00:30:18,470 --> 00:30:19,190
>> Брансон: [ИНАУДИБЛЕ] задржати бројеве.

845
00:30:19,190 --> 00:30:21,990
>> Давид Ј. Малан: Не, можете
задржати бројеве као добро.

846
00:30:21,990 --> 00:30:23,440
У реду.

847
00:30:23,440 --> 00:30:24,100
Лепо урађено.

848
00:30:24,100 --> 00:30:25,300
У реду.

849
00:30:25,300 --> 00:30:30,510
Па да видимо да ли можемо сада резимирам
брже, и више визуелно,

850
00:30:30,510 --> 00:30:33,410
управо оно што се догодило
овде на следећи начин.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Ја ћу да наставим
и попните се Фирефок.

853
00:30:38,770 --> 00:30:41,310
Ми ћемо повезати ову демонстрацију
на интернет страници курса.

854
00:30:41,310 --> 00:30:43,870
Јава је мало непријатно да се ради
у неким прегледачима ових дана.

855
00:30:43,870 --> 00:30:46,760
Дакле, ако се играте са овим код куће,
схватите да ћете морати да користите Фирефок

856
00:30:46,760 --> 00:30:47,990
да се то ради.

857
00:30:47,990 --> 00:30:50,440
И шта ћу да урадим са овим
демонстрација је следећи.

858
00:30:50,440 --> 00:30:54,875
>> На дну, имам гомилу
опција менија, укључујући почетак и

859
00:30:54,875 --> 00:30:55,840
стоп дугме.

860
00:30:55,840 --> 00:30:59,450
Такође, као страну, чини се да
буг у овим програмима, при чему ти

861
00:30:59,450 --> 00:31:03,720
Не могу стварно видети почетак или зауставити
дугме, осим ако држите Цомманд или Алт

862
00:31:03,720 --> 00:31:06,560
плус и увећај, који радознало
показује да вам више дугмади.

863
00:31:06,560 --> 00:31:09,090
Дакле, само за вашу информацију, ако играте
уз то код куће.

864
00:31:09,090 --> 00:31:12,870
Сада ћу да кликнете на Старт само
тренутак, после навођења одлагање,

865
00:31:12,870 --> 00:31:16,810
као, 200 милисекунди, овде, само
тако да можемо да видимо шта се дешава.

866
00:31:16,810 --> 00:31:20,180
>> Дакле, ја тврдим да је ово визуелизација
првог алгоритма

867
00:31:20,180 --> 00:31:23,730
ови момци урадили, Буббле сорт, при чему
смо се заменили људе пар-мудре.

868
00:31:23,730 --> 00:31:27,490
Кључни увид у ову визуелизацију
је да висина пруга

869
00:31:27,490 --> 00:31:30,510
представља величину броја.

870
00:31:30,510 --> 00:31:32,210
Дакле, виша трака,
већи број.

871
00:31:32,210 --> 00:31:33,680
Краћи бар, мањи број.

872
00:31:33,680 --> 00:31:38,630
И ако сте приметили, ми идемо кроз
првој итерацији овог алгоритма,

873
00:31:38,630 --> 00:31:42,620
замене велике и мале бројеве, тако да се
мали број првом и

874
00:31:42,620 --> 00:31:44,280
велики број одлази у десно.

875
00:31:44,280 --> 00:31:48,770
>> И чим смо добили крај низа
многих више од седам бројева, ми смо

876
00:31:48,770 --> 00:31:49,900
ће се вратити на почетак.

877
00:31:49,900 --> 00:31:51,140
И то предвиди.

878
00:31:51,140 --> 00:31:54,860
На далеко лево, да малиша ће
да мењате у страну, и то

879
00:31:54,860 --> 00:31:56,010
процес се понавља.

880
00:31:56,010 --> 00:31:59,450
Сада ова визуализација брзо постаје
досадно, па ћу ићи напред и заустави

881
00:31:59,450 --> 00:32:04,170
то, много променио у нешто кашњења
брже само да се сада, осећај за

882
00:32:04,170 --> 00:32:05,060
Овај алгоритам.

883
00:32:05,060 --> 00:32:07,840
>> Тако да, иако сам га убрзао, ово је
као надоградња мој процесор, куповина

884
00:32:07,840 --> 00:32:08,580
нови рачунар.

885
00:32:08,580 --> 00:32:12,980
Нисам фундаментално променио мој
алгоритам, али ви заиста можете видети више

886
00:32:12,980 --> 00:32:16,800
јасније него са људима, да велики
бројеви се пенуша до врха,

887
00:32:16,800 --> 00:32:20,900
и мали бројеви су бистрим
до дна.

888
00:32:20,900 --> 00:32:22,390
И сада ово овде сортирају.

889
00:32:22,390 --> 00:32:25,260
И као по страни, на трговима, ту је
само нека књиговодство ту да

890
00:32:25,260 --> 00:32:28,010
да вам помогне да рачунају колико поређења,
или колико су свопови

891
00:32:28,010 --> 00:32:28,950
заправо урађено.

892
00:32:28,950 --> 00:32:30,750
>> Па, хајде да покушамо један од
остали смо видели.

893
00:32:30,750 --> 00:32:37,116
Дозволите ми да кликнете на мехурићима врсте овде, и
дозволите ми да бирају, а цела ова веб страница

894
00:32:37,116 --> 00:32:38,936
је мало луд.

895
00:32:38,936 --> 00:32:41,155
Хајде да прихватимо ризик
и покрените га поново.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Ту смо.

898
00:32:45,030 --> 00:32:47,180
Урадимо избор сорт.

899
00:32:47,180 --> 00:32:49,140
Не знам зашто мени
појављује се тамо.

900
00:32:49,140 --> 00:32:54,070
Хајде да увеличате да то поправимо
Буг, промените то до 50 година.

901
00:32:54,070 --> 00:32:56,020
Ах, да заправо
то много брже.

902
00:32:56,020 --> 00:32:59,160
Пет милисекунди или тако, и почети.

903
00:32:59,160 --> 00:33:00,470
>> Дакле, ово је избор врста.

904
00:33:00,470 --> 00:33:03,070
Дакле, опет, мисле о ономе што смо
урадио са људима овде.

905
00:33:03,070 --> 00:33:08,490
Ишли смо кроз низ и изабраних
Најмањи елемент поново,

906
00:33:08,490 --> 00:33:09,250
и опет, и опет.

907
00:33:09,250 --> 00:33:11,110
Сада тврде да је и даље прилично лоше.

908
00:33:11,110 --> 00:33:15,010
Она је и даље н на квадрат, узми или остави,
али је, у стварном свету, мало

909
00:33:15,010 --> 00:33:18,280
брже, јер сам заиста узимао
нешто мање корака сваки пут.

910
00:33:18,280 --> 00:33:19,800
Али, ми само говоримо шта?

911
00:33:19,800 --> 00:33:21,830
Можда 40-ак бара овде?

912
00:33:21,830 --> 00:33:23,200
Ми не говоримо 40 милиона.

913
00:33:23,200 --> 00:33:27,430
Дакле, то није потпуно јасно ми је да
је заиста значајан добитак.

914
00:33:27,430 --> 00:33:32,530
>> Дозволите ми да се вратимо и промените на наше
Трећи алгоритам, који је био изаберите

915
00:33:32,530 --> 00:33:33,180
уметање врста.

916
00:33:33,180 --> 00:33:36,380
А сада је стварно луд, јер
Мени заиста не би требало да буде тамо.

917
00:33:36,380 --> 00:33:40,840
Дакле, сада се враћамо помицати горе
и почети овај алгоритам.

918
00:33:40,840 --> 00:33:43,270
Вхооп, старт и стоп.

919
00:33:43,270 --> 00:33:47,160
Према томе, ова врста има лепу образац
на њега, чиме смо опет смо

920
00:33:47,160 --> 00:33:50,240
убацивањем људе, или у
том случају, барови у

921
00:33:50,240 --> 00:33:52,620
њихова адекватна локација.

922
00:33:52,620 --> 00:33:55,430
И то је већ учињено пре
Окренула сам се.

923
00:33:55,430 --> 00:33:58,940
Али овај је, такође, у теорији,
још увек н на квадрат.

924
00:33:58,940 --> 00:34:01,430
>> Па да видимо, ако не можемо да резимирамо
ово на следећи начин.

925
00:34:01,430 --> 00:34:04,750
Ја ћу ићи напред и само да дају
нас нека врста заједничког начин да се говори

926
00:34:04,750 --> 00:34:08,489
о тим стварима, дозволите ми да представим
само мало нотацији овде.

927
00:34:08,489 --> 00:34:12,480
Ви ћете видети нешто што се зове велико
О, јер буквално је велика

928
00:34:12,480 --> 00:34:16,320
О. И то је начин на који рачунар
научник или математичар чак користи

929
00:34:16,320 --> 00:34:19,230
да опише време рада
неког алгоритма.

930
00:34:19,230 --> 00:34:21,400
Колико корака то заправо траје?

931
00:34:21,400 --> 00:34:25,080
>> Сада ћу да се осрамотити са
мој рукопис овде за који тренутак.

932
00:34:25,080 --> 00:34:29,020
Али, дозволите ми да иде напред и рећи да
Ово ће бити велики О овде.

933
00:34:29,020 --> 00:34:33,610
И дозволите ми да представим један други
симбол, главни Омега.

934
00:34:33,610 --> 00:34:37,080
Омега ће бити супротно,
у суштини, од великог О. док је Биг О

935
00:34:37,080 --> 00:34:40,790
значи, у најгорем случају, колико времена
Можда неки алгоритам узети у

936
00:34:40,790 --> 00:34:43,480
Услови н, омега ће
бити колико времена да би могло

937
00:34:43,480 --> 00:34:45,409
узети у најбољем случају.

938
00:34:45,409 --> 00:34:48,090
Па да видимо шта се подразумева под
Најбољи случај за који тренутак.

939
00:34:48,090 --> 00:34:49,940
>> Дакле, хајде да почнемо нешто једноставно.

940
00:34:49,940 --> 00:34:54,719
Дозволите ми да почнем са линеарном претраге.

941
00:34:54,719 --> 00:34:55,679
Дакле, не сортирање.

942
00:34:55,679 --> 00:34:58,000
Ми ћемо назвати овај линеарни претрагу.

943
00:34:58,000 --> 00:35:01,140
А сада, да мало
сто се у ово.

944
00:35:01,140 --> 00:35:06,600
А сада, у случају линеарне претраге,
у најгорем случају, колико корака је

945
00:35:06,600 --> 00:35:11,770
Да ли ће ме наћи
број произвољне избора?

946
00:35:11,770 --> 00:35:14,540
И ту је н укупна врата
или н укупне бројеве.

947
00:35:14,540 --> 00:35:15,940
Најгори случај.

948
00:35:15,940 --> 00:35:18,800
Колико корака ћу морати да
предузети да пронађе број 50 у низу

949
00:35:18,800 --> 00:35:20,830
од н врата?

950
00:35:20,830 --> 00:35:21,410
А зашто?

951
00:35:21,410 --> 00:35:23,680
Јер то може бити све
пут преко на крају.

952
00:35:23,680 --> 00:35:27,120
Толико попут Џенифер наишао,
Број 50 је скроз, тако да у

953
00:35:27,120 --> 00:35:30,760
најгорем случају линеарна претрагу
је велика О од н, рећи ћемо.

954
00:35:30,760 --> 00:35:33,430
>> Шта је у најбољем случају,
ако се заиста срећан?

955
00:35:33,430 --> 00:35:36,200
Само ће један корак,
или исти број корака.

956
00:35:36,200 --> 00:35:37,830
Тако ћемо описати то као 1.

957
00:35:37,830 --> 00:35:39,010
Дакле, ово је прилично добар.

958
00:35:39,010 --> 00:35:41,210
Сада, шта ако смо негде
као бинарну претрагу?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
Дакле бинарно претраживање, у најгорем
случај, узео колико времена?

961
00:35:47,846 --> 00:35:49,250
>> [Изнео ВОИЦЕС]

962
00:35:49,250 --> 00:35:51,310
>> Давид Ј. Малан: Па у ствари, ја
Чуо је за неколико места.

963
00:35:51,310 --> 00:35:56,390
Дакле, то је заправо лог н, узми или остави,
зато што делимо листу на пола

964
00:35:56,390 --> 00:36:00,730
опет, и опет, и опет, ми смо у стању
да пронађе, на крају, вредност,

965
00:36:00,730 --> 00:36:04,750
ако постоји, али постоји цака.

966
00:36:04,750 --> 00:36:08,590
Шта је претпоставка да морамо да
узети здраво за готово за бинарну претрагу?

967
00:36:08,590 --> 00:36:09,700
Она мора да се сортирају.

968
00:36:09,700 --> 00:36:12,770
То се не сортира, можете поделити ствар
у пола поново и поново, и ви

969
00:36:12,770 --> 00:36:15,490
може да иде лево, а можете ићи десно, и
можете ићи лево и десно, али ти си

970
00:36:15,490 --> 00:36:18,070
неће пронаћи елеменат ако
листа се не сортира, јер

971
00:36:18,070 --> 00:36:18,790
можда га пропустити.

972
00:36:18,790 --> 00:36:22,120
Зато што ваш хеуристике, за одлазак лево
или право ће бити погрешна ако је то

973
00:36:22,120 --> 00:36:23,420
заиста не сортира.

974
00:36:23,420 --> 00:36:26,110
Дакле, постоји нека врста скривених трошкова
да користи овако нешто.

975
00:36:26,110 --> 00:36:29,250
>> Сада, хајде да идемо у наш сортирање
алгоритми не тражи -

976
00:36:29,250 --> 00:36:31,140
Ох, у ствари идемо у празно.

977
00:36:31,140 --> 00:36:33,190
Бинарни тражи у најбољем случају?

978
00:36:33,190 --> 00:36:36,290
Такође је 1 само ако се деси да буде
у самом центру низа, или

979
00:36:36,290 --> 00:36:37,810
средина именика.

980
00:36:37,810 --> 00:36:39,710
Хајде да урадимо Буббле сорт.

981
00:36:39,710 --> 00:36:42,570
Дакле, опет, сад улазимо
врсте, а не претраге.

982
00:36:42,570 --> 00:36:47,220
>> У најгорем случају, колико корака смо урадили
Буббле сорт тврде да ће трајати?

983
00:36:47,220 --> 00:36:48,410
н на квадрат.

984
00:36:48,410 --> 00:36:49,200
Зато ћу извући то.

985
00:36:49,200 --> 00:36:51,710
Оох, мој рукопис изгледа још горе
када је пројектован тако велика.

986
00:36:51,710 --> 00:36:52,510
У реду.

987
00:36:52,510 --> 00:36:53,570
Дакле, то је н квадрат.

988
00:36:53,570 --> 00:36:59,460
И у најбољем случају буббле врсте,
колико корака ће то трајати?

989
00:36:59,460 --> 00:37:00,980
1, чуо сам.

990
00:37:00,980 --> 00:37:01,760
>> СПИКЕР 1: н.

991
00:37:01,760 --> 00:37:03,286
>> Давид Ј. Малан: н, чуо сам.

992
00:37:03,286 --> 00:37:04,200
>> СПИКЕР 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> Давид Ј. Малан: 2, чуо сам.

994
00:37:05,010 --> 00:37:06,670
Чујем 3?

995
00:37:06,670 --> 00:37:07,080
У реду.

996
00:37:07,080 --> 00:37:11,390
Чуо сам 1, н, 2, али хајде да изаберемо
размаку од најмање први од оних

997
00:37:11,390 --> 00:37:12,330
сугестије, 1.

998
00:37:12,330 --> 00:37:15,370
То није лоша инстинкт, јер је
врста следи образац овде.

999
00:37:15,370 --> 00:37:19,670
Али, ако је потребно само 1 корак, како у
свет би могао да тврдим да је списак

1000
00:37:19,670 --> 00:37:22,900
је сортиран, јер ако ми је дозвољено
да се 1 корак, колико елемената

1001
00:37:22,900 --> 00:37:25,230
могао сам стварно проверите да ли?

1002
00:37:25,230 --> 00:37:28,270
Па, само 1, што значи да је н
минус 1 елемената који би могли бити од

1003
00:37:28,270 --> 00:37:31,310
поредак, а ја ћу само на вери након
гледајући 1 елемент који

1004
00:37:31,310 --> 00:37:31,850
ствар је сортиран.

1005
00:37:31,850 --> 00:37:33,930
Дакле, 1 није тачно овде.

1006
00:37:33,930 --> 00:37:35,710
Па минимално, колико
морам да погледам?

1007
00:37:35,710 --> 00:37:36,680
>> [Изнео ВОИЦЕС]

1008
00:37:36,680 --> 00:37:40,160
>> Давид Ј. Малан: Н минус 1, или стварно,
н, јер морам да погледам сваки

1009
00:37:40,160 --> 00:37:42,190
елеменат да се уверите да
то није у квару.

1010
00:37:42,190 --> 00:37:44,750
Али опет, средицемо таласа нашег
руке у мањем броју и

1011
00:37:44,750 --> 00:37:47,100
Претпостављам да, као н добија велики, они су
ионако незанимљива.

1012
00:37:47,100 --> 00:37:48,380
Дакле, то је балон врста.

1013
00:37:48,380 --> 00:37:49,830
А сада, хајде да ове последње две.

1014
00:37:49,830 --> 00:37:53,520
Избор врста, а онда ћемо
до сорт уметања.

1015
00:37:53,520 --> 00:37:57,160
А онда ћемо разнети
умове у нешто много

1016
00:37:57,160 --> 00:37:58,926
бољи од свих њих.

1017
00:37:58,926 --> 00:38:00,410
У реду.

1018
00:38:00,410 --> 00:38:04,700
>> Који је најгори случај покренут
време избора врсте?

1019
00:38:04,700 --> 00:38:05,680
>> ПРЕДСЕДНИК 4: н на квадрат.

1020
00:38:05,680 --> 00:38:06,710
>> Давид Ј. Малан: н квадрат, чујем.

1021
00:38:06,710 --> 00:38:09,790
Али зашто н на квадрат, интуитивно?

1022
00:38:09,790 --> 00:38:11,170
>> ПРЕДСЕДНИК 4: Зато што смо управо то урадили.

1023
00:38:11,170 --> 00:38:12,260
>> Давид Ј. Малан: Зато што смо управо то урадили.

1024
00:38:12,260 --> 00:38:12,550
ОК.

1025
00:38:12,550 --> 00:38:13,380
Добар одговор.

1026
00:38:13,380 --> 00:38:16,660
Али интуитивно, због чега је избор
Сортирај н на квадрат?

1027
00:38:16,660 --> 00:38:18,980
Шта морамо да урадимо
опет и опет?

1028
00:38:18,980 --> 00:38:22,570
Морали смо да кроз скенирање, су
ти најмањи, ти си

1029
00:38:22,570 --> 00:38:24,020
Најмањи, ти си најмањи.

1030
00:38:24,020 --> 00:38:27,480
И готово, ми смо били у стању да се н
кораци, а затим н минус 1, а затим н минус 2.

1031
00:38:27,480 --> 00:38:30,700
Али, ако се некако додати оне све горе,
или да га на основу обећања које сам додао

1032
00:38:30,700 --> 00:38:34,810
их унапред, ми смо отприлике се н
квадрат минус неким мањим бројевима.

1033
00:38:34,810 --> 00:38:36,730
Дакле, ја ћу да позовем овај број на квадрат.

1034
00:38:36,730 --> 00:38:39,530
Али са врстом селекције у најбољи
случај, колико корака је

1035
00:38:39,530 --> 00:38:40,632
ће да ме води?

1036
00:38:40,632 --> 00:38:41,840
>> ПРЕДСЕДНИК 5: [ИНАУДИБЛЕ]

1037
00:38:41,840 --> 00:38:44,350
>> Давид Ј. Малан: То је, нажалост,
још н на квадрат, зар не?

1038
00:38:44,350 --> 00:38:49,590
Јер ако сам изабрати најмањи
елеменат, а ми смо имали овде седам особа,

1039
00:38:49,590 --> 00:38:53,280
Ја само знам, једном сам се да сам
крај, то сам пронашао најмањи

1040
00:38:53,280 --> 00:38:55,670
број, где год он или
можда је она била.

1041
00:38:55,670 --> 00:38:58,820
Али, како да надјем следећи
Најмањи број?

1042
00:38:58,820 --> 00:39:00,160
Морам да урадим још једну пропусницу.

1043
00:39:00,160 --> 00:39:04,810
Дакле, у најбољем случају, оно што је
улаз у избор врсте?

1044
00:39:04,810 --> 00:39:07,830
То је већ врста листа, број један,
број два, број три, број четири.

1045
00:39:07,830 --> 00:39:08,600
Али, ја сам компјутер.

1046
00:39:08,600 --> 00:39:10,190
Ја могу само да погледате један
по једно.

1047
00:39:10,190 --> 00:39:12,465
Ја не могу некако направити корак
назад као човек и каже,

1048
00:39:12,465 --> 00:39:14,030
ох, ово изгледа тачно.

1049
00:39:14,030 --> 00:39:17,580
>> Ја само могу да суде коректност у
Избор врста избором

1050
00:39:17,580 --> 00:39:18,370
Најмањи број.

1051
00:39:18,370 --> 00:39:21,390
Али, чак и ако је број један прво,
ако ја не знам ништа више о томе

1052
00:39:21,390 --> 00:39:24,460
други бројеви, што ја не, све сам
Знам да сам дао низ

1053
00:39:24,460 --> 00:39:27,930
или скуп врата иза којих су
бројеви, једини начин који знам да је један

1054
00:39:27,930 --> 00:39:28,680
била најмања?

1055
00:39:28,680 --> 00:39:32,440
Ако добијем скроз овде и остваре,
Проклетство, један заиста био најмањи.

1056
00:39:32,440 --> 00:39:34,870
>> Али како да ја онда утврдити да
два је следећи најмањи?

1057
00:39:34,870 --> 00:39:38,350
На исти начин неефикасност
изнова и изнова.

1058
00:39:38,350 --> 00:39:42,210
Дакле, коначно, са врстом уметања,
како се, у најгорем случају,

1059
00:39:42,210 --> 00:39:44,990
смо рекли да обавља?

1060
00:39:44,990 --> 00:39:49,100
То је сувише н на квадрат.

1061
00:39:49,100 --> 00:39:53,020
А шта је са најбољем случају?

1062
00:39:53,020 --> 00:39:56,282
Оставићемо то као Цлиффхангер.

1063
00:39:56,282 --> 00:40:00,090
Ми ћемо испунити у том празном следећи пут,
али прво да ми предложи да

1064
00:40:00,090 --> 00:40:02,620
фундаментално боље него
све то, у реду?

1065
00:40:02,620 --> 00:40:05,220
>> Зато мислим да за себе оно што уметање
Сортирај ће бити.

1066
00:40:05,220 --> 00:40:06,910
Па, то није драматично,
јер ја сам једини

1067
00:40:06,910 --> 00:40:08,970
који је видео промену.

1068
00:40:08,970 --> 00:40:09,620
Вау.

1069
00:40:09,620 --> 00:40:10,420
ОК.

1070
00:40:10,420 --> 00:40:12,615
Дакле, овде имамо нешто
Различити демонстрациони.

1071
00:40:12,615 --> 00:40:16,580
Ако сам зумирати овде, видећете да на
Са леве стране имамо буббле сорт, у

1072
00:40:16,580 --> 00:40:20,740
средњи имамо избор врсту, а на
крајње деснице, имамо нешто што

1073
00:40:20,740 --> 00:40:23,380
није погледао још
назвао обједињавање сорт.

1074
00:40:23,380 --> 00:40:26,080
Али размислите шта смо
овде до сада данас.

1075
00:40:26,080 --> 00:40:29,200
Када је Џенифер први пут дошао на сцену,
смо прошли кроз низ бројева

1076
00:40:29,200 --> 00:40:33,750
опет, и опет, са линеарним претрагу,
и имамо линеарно време рада, Биг О

1077
00:40:33,750 --> 00:40:35,100
од н, да тако кажем.

1078
00:40:35,100 --> 00:40:41,000
>> Када сада размотрити прву недељу
класа, када смо завади па владај,

1079
00:40:41,000 --> 00:40:43,740
па смо именик цепање,
и Џенифер, и ми смо колективно

1080
00:40:43,740 --> 00:40:47,500
искористио да кључни увид, који је требало да
понављам себе опет и опет од

1081
00:40:47,500 --> 00:40:50,930
некако баците, баците,
бацања, половина проблема, или

1082
00:40:50,930 --> 00:40:55,320
генерално, проблем поделе на пола,
а затим третира мањи комад

1083
00:40:55,320 --> 00:40:59,630
проблем као и концептуално еквивалент
на другом, ми смо некако урадили

1084
00:40:59,630 --> 00:41:00,910
фундаментално боље.

1085
00:41:00,910 --> 00:41:04,720
Али са мехурићима врстом, уз избор
врста, са убацивања врсте, ми смо можда

1086
00:41:04,720 --> 00:41:06,560
такви увиди да је Џенифер урадио.

1087
00:41:06,560 --> 00:41:10,220
Управо смо прилично се врати и
даље гомила времена, и ми смо

1088
00:41:10,220 --> 00:41:12,650
намештена ствари мало, замене
у том циљу, можда

1089
00:41:12,650 --> 00:41:13,730
уметања или избором.

1090
00:41:13,730 --> 00:41:16,950
Али на крају дана, ја сам много
непријатно ходању и назад.

1091
00:41:16,950 --> 00:41:21,160
Нисмо баш нешто полуга
паметан попут Џенифер допала дељењем

1092
00:41:21,160 --> 00:41:22,040
и освајање.

1093
00:41:22,040 --> 00:41:25,620
>> Дакле обједињавање врсту, насупрот томе, ми који
неће видети до следеће недеље, то ће

1094
00:41:25,620 --> 00:41:29,540
да искористи кључна идеја да се дељењем
унос, а затим преполовити, а затим

1095
00:41:29,540 --> 00:41:30,580
преполови, а затим преполовити.

1096
00:41:30,580 --> 00:41:34,590
И на свакој итерацији те петље,
сортирање леву половину, као и право

1097
00:41:34,590 --> 00:41:38,200
пола, онда Лева половина левој половини,
и десна половина леве стране, а затим

1098
00:41:38,200 --> 00:41:40,990
Лева половина десној половини, а
десна половина десној половини.

1099
00:41:40,990 --> 00:41:42,840
И понавља изнова и изнова.

1100
00:41:42,840 --> 00:41:46,170
>> Тако ћете видети визуелно овај, али овај
је оно што нас чека следеће недеље.

1101
00:41:46,170 --> 00:41:49,760
И уопште, кад мислимо мало
мало теже у сваком таквом проблему.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Ми смо н квадрат са леве стране, н
квадрат у средини, и н

1104
00:41:57,970 --> 00:41:59,400
лог н са десне стране.

1105
00:41:59,400 --> 00:42:00,590
Тако да ти је право Цлиффхангер.

1106
00:42:00,590 --> 00:42:02,040
Видимо се у понедељак.

1107
00:42:02,040 --> 00:42:05,163
>> [Апплаусе]