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

2
00:00:11,270 --> 00:00:14,910
>> Лектор: Добре, това е CS50.

3
00:00:14,910 --> 00:00:19,020
Това е краят на три седмици, и ако
те не са се възползвали вече,

4
00:00:19,020 --> 00:00:21,790
Знам, че ще има обяд
този петък, както обикновено, когато

5
00:00:21,790 --> 00:00:25,430
можете да се насладите на добър разговор
и храните на Огън и лед

6
00:00:25,430 --> 00:00:27,980
с някои от CS50 е
персонал и съученици.

7
00:00:27,980 --> 00:00:30,170
Насочете се към този URL тук.

8
00:00:30,170 --> 00:00:33,420
>> Сега може би си спомняте, или можете
скоро може да се запознае с,

9
00:00:33,420 --> 00:00:35,970
тези неща тук, които
са дадени в края

10
00:00:35,970 --> 00:00:37,850
на семестъра в продължение на много часове.

11
00:00:37,850 --> 00:00:40,870
Така наречените изпитни сини книги, в които
пишете вашите отговори на изпити.

12
00:00:40,870 --> 00:00:44,240
Сега имам тук 26 такива
сини книги, за всеки от тях

13
00:00:44,240 --> 00:00:47,580
е написано едно име, от А до Z. И
наистина имената са толкова просто, A

14
00:00:47,580 --> 00:00:50,490
чрез Z. И един от
целите на днес ръка

15
00:00:50,490 --> 00:00:53,910
ще бъде да продължи това, което
сме започнали в понеделник, което не е

16
00:00:53,910 --> 00:00:57,830
толкова много гледа код, но наистина
търси в идеи и решаване на проблеми.

17
00:00:57,830 --> 00:01:00,170
Една от целите и
обещания за този курс

18
00:01:00,170 --> 00:01:02,985
е да ви научи да мисли повече
внимателно, по-методично,

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

20
00:01:05,400 --> 00:01:09,526
И наистина, ние можем да направим, че наистина
без дори да докосва линията на код.

21
00:01:09,526 --> 00:01:12,150
Така че аз имам няколко слонове
тук днес, оранжево и синьо,

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

23
00:01:15,780 --> 00:01:18,070
Какво ще кажете за точно там, хайде надолу.

24
00:01:18,070 --> 00:01:24,180
Целта на която ще бъде да
помогне плюс администрира този изпит тук.

25
00:01:24,180 --> 00:01:24,935
Как ти е името?

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

27
00:01:25,768 --> 00:01:27,560
Лектор: Мери Бет, хайде нагоре.

28
00:01:27,560 --> 00:01:29,560
Нека си микрофона тук за вас.

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

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

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

32
00:01:34,005 --> 00:01:36,790
Лектор: Добре, така че аз нямам
тук синьо книги от А до Z,

33
00:01:36,790 --> 00:01:41,680
и аз отивам да се преструвам, че
Имам един от студентите,

34
00:01:41,680 --> 00:01:45,770
и те идват в известна степен произволно
в края на три часа изпит блок,

35
00:01:45,770 --> 00:01:49,400
така че те са завършващ в някои
полу-случаен ред като този.

36
00:01:49,400 --> 00:01:54,510
Сега вашата работа, в един момент ще
да е-- това всъщност е как те ще получат

37
00:01:54,510 --> 00:01:56,820
беше в края на
класа, най-вероятно.

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

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

40
00:02:05,220 --> 00:02:08,400
>> АУДИТОРИЯ: О, това е
ще отнеме цяла вечност.

41
00:02:08,400 --> 00:02:13,747
>> Лектор: И ние ще гледаме
както можете да направите това, няма натиск.

42
00:02:13,747 --> 00:02:15,330
АУДИТОРИЯ: Не, никакъв натиск или нещо подобно.

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

44
00:02:19,230 --> 00:02:23,570
>> Лектор: И за забавление,
нека да се примири с таймер.

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

46
00:02:26,680 --> 00:02:28,700
>> АУДИТОРИЯ: Толкова много забавно, така че много по-забавно.

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

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: Мога да държи микрофона ви.

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
Така че в същото време, нека да представлява това, което е
ще бъде въпросът за Mary Beth

52
00:02:49,060 --> 00:02:51,540
е това, което прави тя, как е
тя става за решаването на този?

53
00:02:51,540 --> 00:02:54,040
И в действителност, не може да има
някога мисълта за нещо

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

55
00:02:57,440 --> 00:02:59,350
което е нужно физическо
разпорежда с тях.

56
00:02:59,350 --> 00:03:01,335
Какъв е процесът
че всъщност използвате?

57
00:03:01,335 --> 00:03:03,770
Дали е доста произволно просто
бране на първия милион, което виждате

58
00:03:03,770 --> 00:03:05,250
и да я постави на негово място?

59
00:03:05,250 --> 00:03:09,680
Смятате ли, първо се движи ръцете си около
Търсите после търсите B?

60
00:03:09,680 --> 00:03:11,722
Смятате ли да погледнем на
двойка от тях рамо до рамо

61
00:03:11,722 --> 00:03:14,680
и просто да кажа, чакай малко, това
Не е правилно, и след това сменяте поръчката?

62
00:03:14,680 --> 00:03:16,960
Ние вече видяхме в понеделник
че има няколко начина

63
00:03:16,960 --> 00:03:22,140
, в който можем да направим това, и
наистина, тъй като ние в края тук,

64
00:03:22,140 --> 00:03:26,360
Аз ще взема бележка може би
от това, което Мери Бет прави.

65
00:03:26,360 --> 00:03:30,040
Имаме няколко пилоти изглежда, а
по-голям един, три по-малки такива.

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

67
00:03:33,790 --> 00:03:36,415
>> АУДИТОРИЯ: Аз съм ги поръчате
когато намеря две писма

68
00:03:36,415 --> 00:03:39,540
Знам, че сме заедно в последователност,
Сложих ги заедно, така че аз не правя

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

70
00:03:42,915 --> 00:03:45,706
Това е просто, о, А е първата,
Имам тази купчина тук.

71
00:03:45,706 --> 00:03:47,580
Лектор: Така, почти като
пъзел парчета, които

72
00:03:47,580 --> 00:03:49,860
имат право форма
съвпадат един с друг.

73
00:03:49,860 --> 00:03:51,026
АУДИТОРИЯ: Доста, да.

74
00:03:51,026 --> 00:03:55,320
Лектор: OK, отлично.

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
>> Лектор: Добре, A чрез Z. All
Добре, поздравления, ти си го направил.

78
00:04:09,900 --> 00:04:11,461
Вие имате избор.

79
00:04:11,461 --> 00:04:11,960
Blue?

80
00:04:11,960 --> 00:04:13,530
Добре, благодаря ви за това.

81
00:04:13,530 --> 00:04:16,679
Така Мери Бет е предложила
какъв подход си беше,

82
00:04:16,679 --> 00:04:19,720
но това, което е друг подход как
може да отиде за сортиране на тези неща?

83
00:04:19,720 --> 00:04:21,130
Какво щеше да направиш?

84
00:04:21,130 --> 00:04:24,060
Записът да победи би бил
една минута и 50 секунди, или така,

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

86
00:04:26,039 --> 00:04:27,080
Какво щеше да направиш?

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

88
00:04:27,579 --> 00:04:28,735
АУДИТОРИЯ: Обърнете стека.

89
00:04:28,735 --> 00:04:29,776
Започнете от самото начало.

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

91
00:04:32,284 --> 00:04:36,586
И ако в началото на един е по-висока
от, може би, те са,

92
00:04:36,586 --> 00:04:38,980
долната един е
по-висока, а след това ги включите.

93
00:04:38,980 --> 00:04:41,300
>> Лектор: ОК, така че като се започне
в горната и долната част,

94
00:04:41,300 --> 00:04:43,716
и след това да работи пътя си
навътре така, смяна на тях?

95
00:04:43,716 --> 00:04:46,580
ОК, така че малко по подобен
в дух на балон вид,

96
00:04:46,580 --> 00:04:49,160
но избора на крайностите
Не съседните двойки.

97
00:04:49,160 --> 00:04:52,080
Но в краткосрочен от него е, че има
със сигурност един куп различни начини

98
00:04:52,080 --> 00:04:54,210
бихме могли да направим това и
Честно казано, мисля, че ти вид

99
00:04:54,210 --> 00:04:55,700
прие няколко подхода, нали?

100
00:04:55,700 --> 00:05:00,567
Ти направи нещо като четири сортирани пилоти, и
след това ефективно да ги слива заедно.

101
00:05:00,567 --> 00:05:02,650
И това е, смея да кажа, друг
техника напълно.

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

103
00:05:06,950 --> 00:05:09,820
ако щете, и след това някак си
им се сляха в края.

104
00:05:09,820 --> 00:05:13,410
>> Така че нека да се разгледа, в крайна сметка,
Как иначе бихме могли да направим това.

105
00:05:13,410 --> 00:05:15,860
Ние официално понятието
на балон вид последен път,

106
00:05:15,860 --> 00:05:18,780
и балон вид отзоваване беше
алгоритъм, който ние визуализира

107
00:05:18,780 --> 00:05:22,640
с осем от съучениците си до тук,
привидно случайно подредени на първо време.

108
00:05:22,640 --> 00:05:26,110
И ние след това реши по двойки, ако
два елемента са в ред,

109
00:05:26,110 --> 00:05:26,950
просто да ги сменяте.

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

111
00:05:28,930 --> 00:05:31,080
така че тези две съученици
размени мястото.

112
00:05:31,080 --> 00:05:35,390
И тогава ние се повтори с четири и шест,
След шест и осем, на всяка итерация,

113
00:05:35,390 --> 00:05:36,980
движещи се в дясно.

114
00:05:36,980 --> 00:05:42,590
>> Така че, като се има предвид осем души, колко двойки
сравнения съм направил по време на ходене от

115
00:05:42,590 --> 00:05:45,220
от ляво на дясно в едно такова повторение?

116
00:05:45,220 --> 00:05:48,410
Колко сравнения?

117
00:05:48,410 --> 00:05:49,197
Seven, нали?

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
Вървях от ляво на дясно по
етап, взе ме н минус 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
п минус 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 е броят на хората.

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

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
Но какво ще стане, ако ние
сега плъг-ин на стойност?

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
Но в действителност тя не предполага, че като п
получава по-голям и по-голям, този алгоритъм

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

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

190
00:09:20,450 --> 00:09:21,770
която добавя доста бързо.

191
00:09:21,770 --> 00:09:25,340
И тази подробност не е
загубени на хора, в действителност

192
00:09:25,340 --> 00:09:29,640
Преди няколко години определено сенатор, който е бил
провеждане на кампании, седнах за интервю

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

194
00:09:32,180 --> 00:09:36,380
и е обжалван с въпрос
много прилича поручваме днес.

195
00:09:36,380 --> 00:09:38,468
Нека хвърлим един поглед.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO PLAYBACK]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Че сте тук
в Google, и ми харесва

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

199
00:09:53,382 --> 00:09:56,434
Сега, това е трудно да се получи
работа като президент,

200
00:09:56,434 --> 00:09:58,100
и ти започваш през трудностите сега.

201
00:09:58,100 --> 00:10:01,860
То също е трудно да си намеря работа в Google.

202
00:10:01,860 --> 00:10:05,490
Ние имаме въпроси, и ние
попитайте нашите кандидати въпроси,

203
00:10:05,490 --> 00:10:09,770
и това е един от Лари Швимер.

204
00:10:09,770 --> 00:10:14,760
Какво-- ви момчета, че съм
Шегувам се, това е точно тук.

205
00:10:14,760 --> 00:10:17,930
Какво е най-ефективният начин да се
сортирате милион 32-битови цели числа?

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

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

208
00:10:24,350 --> 00:10:25,200
>> Съжалявам, би--

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

210
00:10:27,400 --> 00:10:30,700
Мисля, че подобно на балон
би било грешен начин да отида.

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

212
00:10:34,165 --> 00:10:38,180
>> Хайде, кой го каза това?

213
00:10:38,180 --> 00:10:40,590
Аз не виждам компютър
науката във вашия фон.

214
00:10:40,590 --> 00:10:42,130
>> -Имаме Нашите шпиони там.

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

216
00:10:44,930 --> 00:10:48,444
>> -OK, Нека попитаме различен
интервю въпрос.

217
00:10:48,444 --> 00:10:49,300
>> [END възпроизвеждане на видео]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: Значи говорим за
конкретни цифри все пак,

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, разделено на две.

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
Той доминира на другия
Терминът, п квадрат разделен от 2

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

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
ние трябва да се търси, толкова повече
Приятелите, които си във Фейсбук.

241
00:12:02,690 --> 00:12:07,340
>> Както п получава по-голям, ние сме наистина
Ще се грижим за най-големите

242
00:12:07,340 --> 00:12:11,560
Терминът в такова анализ на
нашата работа алгоритми.

243
00:12:11,560 --> 00:12:16,230
И аз щях да кажа, знаеш ли какво,
балон вид е от порядъка на голям O,

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

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

246
00:12:20,090 --> 00:12:22,060
но кой наистина го е грижа
за тези по-малки срокове,

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

248
00:12:24,390 --> 00:12:25,870
Това е просто един постоянен фактор.

249
00:12:25,870 --> 00:12:29,480
И е 500 милиарда в сравнение с 250
милиарда наистина, че голяма сделка?

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

251
00:12:32,190 --> 00:12:34,810
получи два пъти по-бързо в хардуера,
и че нещо разлика

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

253
00:12:36,650 --> 00:12:39,300
>> Какво ни е грижа за е
експресията, частта

254
00:12:39,300 --> 00:12:42,489
на израза, че няма да се различават
като наш принос стане по-голям и по-голям.

255
00:12:42,489 --> 00:12:45,280
И наистина, в реалния свят,
това е, което се случва все по-често

256
00:12:45,280 --> 00:12:48,330
е входовете на нашите проблеми и
алгоритми са все по-големи.

257
00:12:48,330 --> 00:12:53,470
Така че голяма O ще бъде нотацията,
асимптотичната нотация, че ние просто

258
00:12:53,470 --> 00:12:57,160
използвате като компютърни специалисти, за да опише
изпълнение, или времето за бягане,

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

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

261
00:13:00,800 --> 00:13:04,170
от различни хора, с помощта на
някои фундаментално подобен метричен

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

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

264
00:13:08,140 --> 00:13:11,910
>> Това, което ние няма да
брой е сумата от време

265
00:13:11,910 --> 00:13:13,981
който преминава на часовника
на стената обикновено.

266
00:13:13,981 --> 00:13:16,230
Това, което ние не започваш да се притесняваш
, е колко памет

267
00:13:16,230 --> 00:13:17,820
вие използвате днес
малко, макар че е

268
00:13:17,820 --> 00:13:19,370
друг ресурс можем да се измери.

269
00:13:19,370 --> 00:13:23,610
Ние ще се опитаме да основаваме нашите анализи
само върху основните операции, онези,

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

271
00:13:25,930 --> 00:13:30,700
Така е и с нещо като голяма O на п
квадрат, аз твърдя, че O на 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
тя ще бъде в големия О от п
квадрат в този случай, горна граница.

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
>> Лектор: Perfect, намирането
най-голям брой в списък.

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
Така че със сигурност, п е горна граница.

300
00:14:45,340 --> 00:14:47,420
Не трябва да се предприемат
повече стъпки от това.

301
00:14:47,420 --> 00:14:51,580
>> И какво, ако вместо това предложи
има алгоритми, в този свят, който

302
00:14:51,580 --> 00:14:57,750
имат течаща време, че е
ограничена от голям O на дневник п, влезте н?

303
00:14:57,750 --> 00:15:00,390
Къде сме виждали това преди?

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

305
00:15:00,890 --> 00:15:03,309
>> АУДИТОРИЯ: В проблема с телефонния указател?

306
00:15:03,309 --> 00:15:04,850
Лектор: Подобно на проблема с телефонния указател.

307
00:15:04,850 --> 00:15:07,754
Какво е мярка за това колко
много време или колко сълзи ИТ

308
00:15:07,754 --> 00:15:10,170
ми отне да се намери някой като
Mike Smith в телефонния указател?

309
00:15:10,170 --> 00:15:13,212
Ние твърди, че е дневник п и
дори ако непознат или да го е

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

311
00:15:15,170 --> 00:15:17,650
просто не забравяйте, че дневник п
обикновено се отнася до процеса,

312
00:15:17,650 --> 00:15:20,790
в този случай на разделяне
нещо в половината отново, и отново,

313
00:15:20,790 --> 00:15:25,790
и отново, и отново, така че тя
получава все по-малък, както правите това.

314
00:15:25,790 --> 00:15:28,470
>> Така влезете на п се отнася, разбира се,
за пример на телефонен указател,

315
00:15:28,470 --> 00:15:32,662
за търсене двоичен на теория, когато ние
имаше виртуалните врати на борда,

316
00:15:32,662 --> 00:15:34,370
или когато Шон е бил
търсене на нещо.

317
00:15:34,370 --> 00:15:37,374
Ако той е използвал двоично търсене, влезте п
ще бъде горната граница на колко

318
00:15:37,374 --> 00:15:38,040
времето, което отнема.

319
00:15:38,040 --> 00:15:44,027
Но тези алгоритми, които се стичаха в
дневника н предположи какво ключов детайл?

320
00:15:44,027 --> 00:15:45,360
Това, че списъкът е подредени, нали?

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

322
00:15:47,789 --> 00:15:49,830
и все още сте с помощта
нещо като двоично търсене

323
00:15:49,830 --> 00:15:51,704
защото може да скочи
право върху елемент

324
00:15:51,704 --> 00:15:53,600
без да осъзнават, че е наистина там.

325
00:15:53,600 --> 00:15:55,600
>> Сега какво може да означава това, голяма O на една?

326
00:15:55,600 --> 00:15:59,117
Това не означава, че алгоритъма си
има една и само една стъпка,

327
00:15:59,117 --> 00:16:01,200
това просто означава, че отнема
постоянен брой стъпки.

328
00:16:01,200 --> 00:16:04,060
Може би това е един, може би това е
10, може би това е 1000,

329
00:16:04,060 --> 00:16:07,750
но тя е независима от
размера на проблема.

330
00:16:07,750 --> 00:16:10,850
Без значение колко е голям н е,
постоянна алгоритъм време

331
00:16:10,850 --> 00:16:12,747
винаги се същия брой стъпки.

332
00:16:12,747 --> 00:16:15,080
Така че това, което може да се окаже един алгоритъм
ние говорихме за или просто

333
00:16:15,080 --> 00:16:20,418
интуитивно, че идва при вас, че
винаги работи в така наречената константа време?

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

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

336
00:16:22,001 --> 00:16:25,320
Лектор: Добавете две числа,
2 плюс 2 е равно на 4, направено.

337
00:16:25,320 --> 00:16:27,227
Така, че може да работи, какво друго?

338
00:16:27,227 --> 00:16:28,560
Какво ще кажете за по-реалния свят, така ли?

339
00:16:28,560 --> 00:16:30,686
>> АУДИТОРИЯ: Намирането на
Първото нещо в списъка.

340
00:16:30,686 --> 00:16:32,810
Лектор: Намирането на първа
елемент в списък, разбира се.

341
00:16:32,810 --> 00:16:34,540
Ние сме били действително говори
за масиви вече

342
00:16:34,540 --> 00:16:36,540
как да получите в
първият елемент в масив,

343
00:16:36,540 --> 00:16:40,465
без значение колко дълго
масив е в 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
когато направихме Scratch.

350
00:16:53,900 --> 00:16:59,707
Колко време отне на
каже блок в Scratch да изпълни?

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
>> АУДИТОРИЯ: Bubble вид?

366
00:17:37,910 --> 00:17:41,610
>> Лектор: Bubble вид отнема
вие минимално 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
SPEAKER: Точно така.

374
00:17:52,360 --> 00:17:55,810
В най-добрия възможен сценарий на
балон вид, и много алгоритми,

375
00:17:55,810 --> 00:17:58,769
ако ви предам осем души
които вече са подредени,

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

377
00:18:00,560 --> 00:18:02,202
да се върна и назад
повече от веднъж, нали?

378
00:18:02,202 --> 00:18:04,285
Защото веднага след като си
преминете през списъка веднъж,

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

380
00:18:08,090 --> 00:18:09,700
Но това няма да ти п стъпки предприемат.

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

382
00:18:12,033 --> 00:18:15,240
Bubble вид е омега,
така да се каже, на 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
Една стъпка, две стъпки, 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
>> АУДИТОРИЯ: ФОРМАТ?

404
00:19:05,309 --> 00:19:06,183
Лектор: Какво е това?

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

406
00:19:07,184 --> 00:19:07,850
Лектор: ФОРМАТ.

407
00:19:07,850 --> 00:19:08,400
OK, разбира се.

408
00:19:08,400 --> 00:19:10,720
Така се определен брой стъпки.

409
00:19:10,720 --> 00:19:13,170
И аз трябва да сега-- сега, че
ние не говорим за C код

410
00:19:13,170 --> 00:19:16,040
и не Scratch, нещо
като да речем, с ФОРМАТ,

411
00:19:16,040 --> 00:19:17,710
трябва да започнем да се внимава.

412
00:19:17,710 --> 00:19:21,090
Защото ФОРМАТ взема
вход, това е низ,

413
00:19:21,090 --> 00:19:23,220
и струни да имат технически дължина.

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

415
00:19:25,530 --> 00:19:29,430
технически бихме могли да твърдим, че ФОРМАТ
взема вход променлива дължина,

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
Ами Mike Smith в телефона
книга, или двоично търсене по-общо?

420
00:19:40,450 --> 00:19:42,220
В най-добрия случай, това, което може да се случи?

421
00:19:42,220 --> 00:19:45,577
I отворите телефонния указател и, бам,
има редица Майк Смит.

422
00:19:45,577 --> 00:19:46,660
Мога да му се обадя веднага.

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

424
00:19:49,390 --> 00:19:50,230
ако имам късмет.

425
00:19:50,230 --> 00:19:52,570
И честно казано, видяхме на
Понеделник си съученик

426
00:19:52,570 --> 00:19:54,710
получи доста късмет два пъти подред.

427
00:19:54,710 --> 00:19:57,050
И това наистина е постоянна
време в ниски граници

428
00:19:57,050 --> 00:20:01,280
на алгоритъма въпросната за намиране
броя 50 зад тези затворени

429
00:20:01,280 --> 00:20:01,830
врати.

430
00:20:01,830 --> 00:20:06,400
>> Сега, като се отмени, ако откриете
че и двете големи O, горната граница,

431
00:20:06,400 --> 00:20:09,310
и Омега, долна граница,
са един в същото, че

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

433
00:20:11,830 --> 00:20:15,170
се каже, само за да се фантазия,
че нещо е в тета

434
00:20:15,170 --> 00:20:18,270
п или тета друга стойност.

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

436
00:20:20,661 --> 00:20:21,910
Сега какво да кажем за избор вид?

437
00:20:21,910 --> 00:20:23,400
Нека използваме тази нова лексика.

438
00:20:23,400 --> 00:20:27,407
При избор на сортиране, което бяхме
прави отново, и отново, и отново?

439
00:20:27,407 --> 00:20:29,990
Щях напред и назад през
списъка, търсейки кого?

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

441
00:20:33,260 --> 00:20:34,730
Най-малкият номер.

442
00:20:34,730 --> 00:20:37,560
>> Е, как много стъпки, как
много сравнения направих

443
00:20:37,560 --> 00:20:43,250
трябва да се направи, за да разбера кой
най-малкия елемент в списъка е?

444
00:20:43,250 --> 00:20:44,437
п минус 1, нали?

445
00:20:44,437 --> 00:20:47,770
Защото, ако аз просто започнете с едно съм
като се има предвид и да започна да го или я сравняват,

446
00:20:47,770 --> 00:20:49,519
след него, го
или нея, него или нея,

447
00:20:49,519 --> 00:20:52,010
да сдвоите само елементи
заедно N минус 1 пъти.

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

449
00:20:55,630 --> 00:20:59,540
>> Колко стъпки пък ме отведе до
намери втория най-малък елемент?

450
00:20:59,540 --> 00:21:02,920
п минус 2, защото аз съм като ням
ако продължавам да гледам едни и същи хора

451
00:21:02,920 --> 00:21:06,280
отново, ако вече съм го избрали
или си и ги постави на мястото им.

452
00:21:06,280 --> 00:21:09,270
И третата стъпка, п
минус 3, тогава п минус 4.

453
00:21:09,270 --> 00:21:11,020
Видяхме този модел
преди, и наистина

454
00:21:11,020 --> 00:21:13,460
избор на сортиране по подобен начин
има горна граница

455
00:21:13,460 --> 00:21:16,210
п квадрат ако правим нагоре, че сумиране.

456
00:21:16,210 --> 00:21:19,790
Каква е неговата долна граница, избор на вид?

457
00:21:19,790 --> 00:21:25,350
Минимално, колко селекция път, трябва да
подреди вземе, тъй като ние я определя в понеделник?

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

459
00:21:29,370 --> 00:21:30,490
Предлага две възможности.

460
00:21:30,490 --> 00:21:32,360
Може би това е N, както и преди.

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

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

463
00:21:35,874 --> 00:21:36,664
SPEAKER: 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
>> SPEAKER: Точно така.

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

474
00:21:57,080 --> 00:22:00,667
>> Какво ще кажете за вмъкване на сортиране, където взех
който ми беше даден, и тогава аз го пльосна

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

476
00:22:01,750 --> 00:22:04,958
След това пристъпва към втория човек,
него или нея се пльосна на правилното място.

477
00:22:04,958 --> 00:22:07,910
След това на следващия човек, пльосна
него или нея в правилното място.

478
00:22:07,910 --> 00:22:10,537
Забележете, че това е много
линейна, така да се каже.

479
00:22:10,537 --> 00:22:12,620
Аз съм по права линия, аз съм
не върви напред и назад,

480
00:22:12,620 --> 00:22:16,080
Никога не съм гледам назад наистина, но
какво се случва, когато го поставете

481
00:22:16,080 --> 00:22:20,302
или я в началото на
списъка, както направихме в понеделник?

482
00:22:20,302 --> 00:22:21,010
Какво се случва?

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

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

485
00:22:23,122 --> 00:22:24,830
Лектор: Да, това
е уловката, нали?

486
00:22:24,830 --> 00:22:26,746
Може да се припомни, от
съучениците си, ако те

487
00:22:26,746 --> 00:22:29,670
са били прави всяко движение с
краката си, това беше една операция.

488
00:22:29,670 --> 00:22:33,610
Така че, ако е имало трима души тук и
новото лице принадлежеше начин там,

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

490
00:22:37,360 --> 00:22:40,074
Но ако си мислите за
компютър и масив на памет,

491
00:22:40,074 --> 00:22:41,990
тези хора ще
трябва да разбъркате над

492
00:22:41,990 --> 00:22:43,260
за да направи място за това лице.

493
00:22:43,260 --> 00:22:46,930
И така, това, че п минус 1 shufflings,
п минус 2 shufflings, н

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

495
00:22:50,660 --> 00:22:52,710
както преди, в известен смисъл.

499
00:22:52,557 --> 00:22:54,640
Сега като настрана, и като
може да сте онлайн

500
00:22:54,640 --> 00:22:57,699
ако започнете да изпълзяват около около
видове, има толкова много различни хора

501
00:22:57,699 --> 00:22:59,490
там, някои от тях
по-добре от други.

502
00:22:59,490 --> 00:23:02,200
Всъщност, bogosort е един
че е забавно да гледам нагоре.

503
00:23:02,200 --> 00:23:06,650
Bogosort се набор от
номера или да кажа едно тесте карти,

504
00:23:06,650 --> 00:23:09,870
случайно ги разбърква, и
проверки, ако те се сортират.

505
00:23:09,870 --> 00:23:12,130
И ако не е, го прави отново.

506
00:23:12,130 --> 00:23:14,140
И ако не е, го прави отново.

507
00:23:14,140 --> 00:23:15,440
Ако не, да го прави отново.

508
00:23:15,440 --> 00:23:17,060
Невероятно глупава.

509
00:23:17,060 --> 00:23:19,520
>> И наистина, ако четете
като статията Wikipedia,

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
Какво ще кажете за един тук, и
нека go-- никой не там?

517
00:23:40,972 --> 00:23:41,722
Никой не там?

518
00:23:41,722 --> 00:23:42,221
OK.

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
>> АУДИТОРИЯ: Peter.

522
00:23:45,720 --> 00:23:46,100
>> Лектор: Какво е това?

523
00:23:46,100 --> 00:23:46,766
>> АУДИТОРИЯ: Peter.

524
00:23:46,766 --> 00:23:49,450
Лектор: Петър, Давид, хубаво е да се запознаем.

525
00:23:49,450 --> 00:23:53,670
Добре, имаме Peter тук, ако сте
искат да дойдат на масата тук.

526
00:23:53,670 --> 00:23:54,550
А какво е твоето име?

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

528
00:23:55,216 --> 00:23:55,970
Лектор: Елена.

529
00:23:55,970 --> 00:23:57,030
Добре, хубаво е да се запознаем.

530
00:23:57,030 --> 00:23:58,060
Елена срещне Питър.

531
00:23:58,060 --> 00:23:59,170
Peter, Елена.

532
00:23:59,170 --> 00:24:02,290
И ще имаме нужда от Andrew
тук, както и, моля те.

533
00:24:02,290 --> 00:24:06,107
И си предизвикателство ще
да бъде да сортирате тесте карти.

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

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

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

537
00:24:13,660 --> 00:24:15,570
по целия път до цар.

538
00:24:15,570 --> 00:24:20,890
>> Картите аз ще ви дам
ще бъде 52 в количество.

539
00:24:20,890 --> 00:24:23,160
Отиваме по подобен начин
Вашето време, в един момент.

540
00:24:23,160 --> 00:24:26,410
Отиваме, за да хвърлят Andrew
на екрана тук,

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
това са картите се качих на Amazon.

544
00:24:33,490 --> 00:24:42,861
Така че те вече са на случаен принцип
подредени, а ние ще ви време.

545
00:24:42,861 --> 00:24:44,610
И ние ще се
я държи недвижими този път,

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

547
00:24:47,820 --> 00:24:48,460
бързо.

548
00:24:48,460 --> 00:24:53,860
Ако можеше да се процедира, за да сортирате 52
елементи заедно чрез някои средства, веднага.

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

550
00:25:04,710 --> 00:25:07,180
>> И отново, както ние гледаме тези
момчета правят това, в края на краищата

551
00:25:07,180 --> 00:25:10,200
ще се произвежда очевидна
резултат, мисля за наистина

552
00:25:10,200 --> 00:25:12,962
как те всеки го прави,
как бихте могли да го опиша.

553
00:25:12,962 --> 00:25:15,045
Защото отново, те са
Всички процеси, алгоритми

554
00:25:15,045 --> 00:25:17,090
че ние приемаме за даденост, като човек.

555
00:25:17,090 --> 00:25:22,349
Но вероятно сте отдавна има
интуиция, дълго преди да можете дори

556
00:25:22,349 --> 00:25:24,390
мислех за вземане на
компютърни науки ви клас

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

558
00:25:27,223 --> 00:25:29,560
Но след като веднъж сте се признае
моделите и да започне

559
00:25:29,560 --> 00:25:32,407
да се формализира стъпките, с които
сте решаване на тези проблеми,

560
00:25:32,407 --> 00:25:35,490
ще откриете, че можете да решите много
по-интересна и много по-сложна

561
00:25:35,490 --> 00:25:39,190
проблеми бързо.

562
00:25:39,190 --> 00:25:42,351
Значи някой от публиката, какво е
най-малко един елемент на алгоритъма

563
00:25:42,351 --> 00:25:43,350
че те използват тук?

564
00:25:43,350 --> 00:25:44,275
>> АУДИТОРИЯ: [недоловим]

565
00:25:44,275 --> 00:25:45,150
Лектор: Какво е това?

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

567
00:25:47,062 --> 00:25:47,770
Лектор: С костюм.

568
00:25:47,770 --> 00:25:50,630
Така че първо те са съсредоточени
всички от диамантите заедно

569
00:25:50,630 --> 00:25:52,560
изглежда, всички от
сърца заедно изглежда,

570
00:25:52,560 --> 00:25:56,520
и т.н., без отношение
за номерата на картите.

571
00:25:56,520 --> 00:26:00,900
И сега те се появяват, например,
да им сортиране по номер.

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

573
00:26:06,870 --> 00:26:08,910
Много добре.

574
00:26:08,910 --> 00:26:12,370
>> Добре, така че какво ще се
да бъде последната стъпка, след това тук?

575
00:26:12,370 --> 00:26:16,950
След като имаме четири сортирани костюми, какво
ние трябва да направим, за да четирите купчини

576
00:26:16,950 --> 00:26:20,059
за да се постигне една
подредени палубата, съвсем просто?

577
00:26:20,059 --> 00:26:21,350
Така че ние трябва да ги слее отново.

578
00:26:21,350 --> 00:26:25,160
>> Така че там е интересна идея, която
отново, смея да кажа, е много интуитивен дори

579
00:26:25,160 --> 00:26:28,140
ако никога не би могъл да зашлеви
този вид на етикет върху него.

580
00:26:28,140 --> 00:26:31,900
Тази фундаментална идея за разделяне
проблемът не в половината от това време,

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

582
00:26:33,410 --> 00:26:36,810
Решаване на почти
фундаментално идентични проблеми

583
00:26:36,810 --> 00:26:40,480
отделно един от друг,
и след това обединяване на резултатите.

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

585
00:26:46,940 --> 00:26:50,140
И, отлично, направи.

586
00:26:50,140 --> 00:26:52,140
Добре, един голям кръг
аплодисменти, ако можехме.

587
00:26:52,140 --> 00:26:56,480
>> [APPLAUSE]

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 I
изброените по-методичен начин

598
00:27:25,150 --> 00:27:28,400
за описване как съм направил много интуитивен
човешки алгоритъм на разделяне на телефона

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

600
00:27:31,650 --> 00:27:33,790
ако той наистина е в телефонния указател.

601
00:27:33,790 --> 00:27:37,610
>> Но аз вид се използва това, което аз ще се обадя
много итеративен подход тук,

602
00:27:37,610 --> 00:27:42,160
по-специално известие линия 8 и линия 11.

603
00:27:42,160 --> 00:27:46,750
Тези, които са доказателство за един повтарящ
подход, подход на примка,

604
00:27:46,750 --> 00:27:49,040
защото това е точно
поведението предизвикват.

605
00:27:49,040 --> 00:27:52,910
Тези линии и двете казват, отидете на
трета линия, и ще можете да вид

606
00:27:52,910 --> 00:27:55,140
мисля, че в
окото на ума, че е на линия.

607
00:27:55,140 --> 00:27:59,080
Той ти казва да се върнете до стъпка
три и се повтаря отново и отново,

608
00:27:59,080 --> 00:28:00,010
и отново.

609
00:28:00,010 --> 00:28:04,410
>> Но какво, ако ние се наберат ключова идея
И ето, че не сме за последен път,

610
00:28:04,410 --> 00:28:10,280
и опростяване на линия 8 и
ред 11 и техните съседи

611
00:28:10,280 --> 00:28:12,840
като само този, в жълто.

612
00:28:12,840 --> 00:28:16,480
Това не е фундаментално скъсяване
на 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
>> С други думи, ако
I започнете от стъпка едно,

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
ако Смит е по-рано в книгата, стъпка седем
търси за Mike в лявата половина на книгата.

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
търси за Mike в ляво
половината от телефонния указател?

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
защото имаме тези мерки StopGAP,
този алгоритъм ще бъде прекратен, ако ние

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, ако п е по-малко от 2,

644
00:30:00,170 --> 00:30:01,040
се върне.

645
00:30:01,040 --> 00:30:03,610
Така че, защо да имам, че
здрав разум проверите първо?

646
00:30:03,610 --> 00:30:09,477
Какъв е изводът, ако ви предаде
масив с дължина п е по-малко от 2?

647
00:30:09,477 --> 00:30:11,060
Той вече подредени, очевидно, нали?

648
00:30:11,060 --> 00:30:13,640
Тъй като списъка или има
един елемент, който е тривиално

649
00:30:13,640 --> 00:30:15,180
подредени, защото това е
единственото нещо, което има.

650
00:30:15,180 --> 00:30:18,138
Или, това е с размер нула, което означава,
няма за какво да се справи, така че по природа

651
00:30:18,138 --> 00:30:18,720
тя се сортира.

652
00:30:18,720 --> 00:30:20,410
Има само нищо лошо там.

653
00:30:20,410 --> 00:30:22,310
Така че това е нашата т.нар базов модел.

654
00:30:22,310 --> 00:30:24,440
>> Това е подобна по дух
на това, което направихме с Майк.

655
00:30:24,440 --> 00:30:26,023
Ако Майк в телефонния указател, обадете се на него.

656
00:30:26,023 --> 00:30:27,740
Ако той не е там, да се откажа.

657
00:30:27,740 --> 00:30:31,240
Това е така наречения базов модел, за да се уверите
този алгоритъм в края на деня

658
00:30:31,240 --> 00:30:33,540
ще спре при определени обстоятелства.

659
00:30:33,540 --> 00:30:37,890
>> Но тук е скок на вярата сега, друг,
сортирате лявата половина на елементите,

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

661
00:30:39,740 --> 00:30:41,189
и след това се слеят сортирани половини.

662
00:30:41,189 --> 00:30:43,230
И тук е мястото, където тя се чувства
като сме copping навън.

663
00:30:43,230 --> 00:30:46,900
Помолих те да сортирате
п елементи, и аз съм

664
00:30:46,900 --> 00:30:50,712
казвайки: Добре, не го чрез сортиране
Левият и сортиране на правото.

665
00:30:50,712 --> 00:30:52,420
Но аз казвам, че един
друго нещо, и това

666
00:30:52,420 --> 00:30:55,530
е ключовата тема изглежда
в интуицията до този момент,

667
00:30:55,530 --> 00:30:57,380
там е тази трета стъпка за обединяване.

668
00:30:57,380 --> 00:31:00,430
Което, въпреки че
изглежда толкова тъпа по дух,

669
00:31:00,430 --> 00:31:02,320
като просто се сливат неща
заедно, изглежда

670
00:31:02,320 --> 00:31:05,380
да бъде ключова стъпка към
сглобяване на два проблема, които

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

672
00:31:07,330 --> 00:31:12,090
>> Така се сливат вид, нека да направим това, ако вие ще
хумор мен, с още една демонстрация,

673
00:31:12,090 --> 00:31:14,730
просто така, че ние имаме някаква
номера, за да работим.

674
00:31:14,730 --> 00:31:19,470
Мога ли да обменят осем стрес
топки за осем души?

675
00:31:19,470 --> 00:31:29,320
Добре, какво ще кажеш ти три, ти четири
в този раздел, пет, шест, и нека

676
00:31:29,320 --> 00:31:30,720
са 7, 8, хайде нагоре.

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

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

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

680
00:31:38,640 --> 00:31:39,150
Отлично.

681
00:31:39,150 --> 00:31:42,000
Добре хайде нагоре, нека
бързо ви даде номера.

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

683
00:31:50,800 --> 00:31:52,140
Направих осем правилно този път.

684
00:31:52,140 --> 00:31:56,390
>> ОК, така че давай напред, ако можеш, и
нека да сортирате в първоначалния ред

685
00:31:56,390 --> 00:31:59,810
че имахме вчера, която изглеждаше
по този начин, ако не би имал нищо против.

686
00:31:59,810 --> 00:32:03,620
И нека го направим в предната част на таблицата.

687
00:32:03,620 --> 00:32:06,510
Добре, така че се сливат вид.

688
00:32:06,510 --> 00:32:08,820
Това е мястото, където става
за да получите вид интересно,

689
00:32:08,820 --> 00:32:12,800
защото аз като че ли да се даде себе си
толкова по-малко информация днес.

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

691
00:32:15,149 --> 00:32:18,440
и очевидно не е по-малко от два, е
осем, така че имам още малко работа за вършене.

692
00:32:18,440 --> 00:32:21,140
Така че сега ние мислено като клас
сега са в бранша друго,

693
00:32:21,140 --> 00:32:22,540
което означава три стъпки.

694
00:32:22,540 --> 00:32:25,017
Първо, трябва да се справи със
лявата половина на елементите.

695
00:32:25,017 --> 00:32:26,350
И така, как мога да отида за правиш това?

696
00:32:26,350 --> 00:32:28,950
Е, аз отивам да се вид
умствено разделят списъка тук,

697
00:32:28,950 --> 00:32:30,700
не е нужно да се
физически се движат, и аз съм

698
00:32:30,700 --> 00:32:33,180
ще се съсредоточи само върху
лявата половина на елементи тук.

699
00:32:33,180 --> 00:32:36,770
И така, как мога да отида за сортиране
списък сега с размер четири?

700
00:32:36,770 --> 00:32:38,730
Какво ми алгоритъм?

701
00:32:38,730 --> 00:32:42,580
Първо ще се провери, е п-малко от две, не,
така че аз се пристъпи към друг блок отново.

702
00:32:42,580 --> 00:32:43,900
Sort лявата половина на елементи.

703
00:32:43,900 --> 00:32:45,608
>> Така че сега отново, умствено,
и това е мястото, където

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

705
00:32:49,550 --> 00:32:51,940
Сега съм сортиране ляво
половината от лявата половина.

706
00:32:51,940 --> 00:32:57,000
Добре, така че сега аз наричам моя същия сливат
сортиране алгоритъм, е п-малко от два?

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

708
00:33:00,590 --> 00:33:02,042
Така че тук ние тръгваме, сортирате лявата половина.

709
00:33:02,042 --> 00:33:03,750
Защо просто не
вземете една крачка напред.

710
00:33:03,750 --> 00:33:04,415
Как ти е името?

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

712
00:33:04,860 --> 00:33:05,260
>> Лектор: Дан.

713
00:33:05,260 --> 00:33:06,040
Дан пристъпи напред.

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

715
00:33:06,748 --> 00:33:09,000
Лектор: Darren, направено.

716
00:33:09,000 --> 00:33:10,090
Знаете ли, казват, Darren или Дан?

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
OK, Darren активизира
напред и той вече е сортиран.

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
Така че дясната половина, така че нека да се движат Luke над
тук на първоначалното място на Дарън.

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
се види, че стигнахме до този
точка на Люк и Darren

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
>> АУДИТОРИЯ: Alex.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: Alex сега се сортира.

762
00:34:38,379 --> 00:34:40,750
Лявата половина, дясната половина,
това, което е последната стъпка?

763
00:34:40,750 --> 00:34:41,250
Merge.

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
>> Лектор: Omar, стъпка напред, направи.

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
>> АУДИТОРИЯ: Chris.

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
Merge.

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

789
00:35:30,509 --> 00:35:32,930
и три ще се
да направи крачка назад, се слеят.

790
00:35:32,930 --> 00:35:38,080
Така че лявата половина на
дясната половина, сега се сортира.

791
00:35:38,080 --> 00:35:41,747
Честно казано, този алгоритъм се чувства като ние
Губиш начин повече време, отколкото преди,

792
00:35:41,747 --> 00:35:44,830
но ако сме направили това в реално време, ние ще
видим какво храна за вкъщи ще бъде.

793
00:35:44,830 --> 00:35:47,970
Сега аз съм тук, нали
половината от дясната половина,

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

795
00:35:50,170 --> 00:35:51,482
Стъпка напред, какво е вашето име?

796
00:35:51,482 --> 00:35:52,190
АУДИТОРИЯ: Рамзи.

797
00:35:52,190 --> 00:35:53,210
Лектор: Ramsey сега се сортира.

798
00:35:53,210 --> 00:35:53,570
Как ти е името?

799
00:35:53,570 --> 00:35:54,200
>> АУДИТОРИЯ: Marina.

800
00:35:54,200 --> 00:35:57,033
>> Лектор: Marina сега се сортира като
добре, ако вземете една крачка напред.

801
00:35:57,033 --> 00:36:00,690
Key стъпка тук, сега се слеят, аз съм
ще извади от двете ми списъци,

802
00:36:00,690 --> 00:36:01,720
наляво и надясно.

803
00:36:01,720 --> 00:36:05,150
Five ще дойде първо,
и седем ще дойде следващата.

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
Имаме Luke с номер две
или Chris с номер три.

829
00:37:05,000 --> 00:37:07,460
Очевидно Лука, брой
две, така ли да дойдеш тук.

830
00:37:07,460 --> 00:37:11,270
>> Но лявата ми ръка, сега ще се
да бъде увеличен, за да се отбележи в Darren,

831
00:37:11,270 --> 00:37:15,160
и тук е ключът отнеме с
сливане, аз ще продължа да правя това,

832
00:37:15,160 --> 00:37:17,340
Очевидно е, че ако сте вид
от следваме логиката.

833
00:37:17,340 --> 00:37:19,670
Но ръцете ми никога не са
Ще се върнете назад,

834
00:37:19,670 --> 00:37:23,861
което означава, че аз съм само някога се премести в
наляво с моя процес сливане

835
00:37:23,861 --> 00:37:26,360
и това ще бъде от ключово значение, за да
нашия анализ в един момент.

836
00:37:26,360 --> 00:37:27,859
>> Така че сега нека да довърша това бързо.

837
00:37:27,859 --> 00:37:31,650
Така три идва следващия,
След четири идва следващия,

838
00:37:31,650 --> 00:37:38,750
и сега пет идва следващия, след това шест,
и седем, а след това най-накрая осем.

839
00:37:38,750 --> 00:37:42,960
Усеща се най-бавният алгоритъм
все още, но не и ако ние всъщност

840
00:37:42,960 --> 00:37:45,510
тя тече от същия вид
на тактова честота, така че да

841
00:37:45,510 --> 00:37:48,106
говори, със същите
тиктака часовник, както и преди.

842
00:37:48,106 --> 00:37:48,605
Защо?

843
00:37:48,605 --> 00:37:51,100
Е, нека хвърлим един
погледнете крайния резултат.

844
00:37:51,100 --> 00:37:56,990
>> Нека да се върнем тук, позволете ми да
издърпайте нагоре демонстрация визуално

845
00:37:56,990 --> 00:37:59,030
от това, което току-що го направих.

846
00:37:59,030 --> 00:38:06,110
Увеличение тук, на тази
страница тук, казва Firefox

847
00:38:06,110 --> 00:38:08,200
че искаме да си вадя
в това поле, нека

848
00:38:08,200 --> 00:38:11,260
каже балон вид, с които
сега сме добре запознати,

849
00:38:11,260 --> 00:38:14,130
избор на сортиране, който е друг
сравнително лесно един,

850
00:38:14,130 --> 00:38:18,250
и сега днешния сливат вид, който
За нас ще бъде кулминационен край.

851
00:38:18,250 --> 00:38:21,530
Причината за това отне толкова много по-дълго
тук с хората и ми е устно,

852
00:38:21,530 --> 00:38:23,480
Очевидно е, че аз съм за обяснение на всяка стъпка.

853
00:38:23,480 --> 00:38:26,920
Но ако просто изпълни това, много по-
както направихме нещо като балон и избор

854
00:38:26,920 --> 00:38:30,890
вид не само визуално, часовник
колко по-ефективно

855
00:38:30,890 --> 00:38:33,330
това деблокирането на
разделяне и завладяване

856
00:38:33,330 --> 00:38:39,150
може да бъде, когато се прилага по отношение на набор данни, че е
Дори не размер осем, но дори и много,

857
00:38:39,150 --> 00:38:39,970
много по-голяма.

858
00:38:39,970 --> 00:38:44,585
Давам ви се слеят вид, рамо до
страна с тези на други алгоритми.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Това ще се получи болезнен
бързо, и краят

861
00:38:58,530 --> 00:39:00,890
не е особено климатични,
те просто свърши подредени.

862
00:39:00,890 --> 00:39:05,280
Но ключът отнемат е, че
Виж колко много по-бързо се сливат вид

863
00:39:05,280 --> 00:39:08,110
е, освен ако не мислиш, че съм
просто вид на каша с вас.

864
00:39:08,110 --> 00:39:13,100
Ако правим това за последен път,
Нека да презареди това, нека се върнем

865
00:39:13,100 --> 00:39:14,960
и изберете балон вид,
и само за ритници,

866
00:39:14,960 --> 00:39:17,330
нека изберем вмъкване
вид, само за добра мярка.

867
00:39:17,330 --> 00:39:20,020
И този път отново, нека
изберете сливат вид и нека

868
00:39:20,020 --> 00:39:21,595
всъщност изпълните тези рамо до рамо.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> И това не е, в действителност, една щастлива случайност.

871
00:39:26,930 --> 00:39:31,140
Това, което съм направил, е ефективно Имам
разделена моя вход в половината, отново,

872
00:39:31,140 --> 00:39:32,240
и отново и отново.

873
00:39:32,240 --> 00:39:35,590
И има само толкова много пъти може да
разделите вашия вход на две половини, наляво

874
00:39:35,590 --> 00:39:36,240
и надясно.

875
00:39:36,240 --> 00:39:39,425
Каква е формулата, която пазим виждайки
който описва разделението на половина

876
00:39:39,425 --> 00:39:41,050
отново, и отново, и отново, и отново?

877
00:39:41,050 --> 00:39:41,890
>> АУДИТОРИЯ: Влезте п.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: Влезте п.

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

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
Трябва да се минимално погледнете наш елементи
да бъде сигурен, п елементи са подредени,

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
и сливането в крайна сметка се п
стъпки, това, което може да бъде А най-горните

896
00:40:33,880 --> 00:40:37,000
граница на протичане
време на нашия алгоритъм?

897
00:40:37,000 --> 00:40:37,980
п влезете п.

898
00:40:37,980 --> 00:40:40,560
>> И наистина, това е, което
ние сме постигнали тук.

899
00:40:40,560 --> 00:40:44,650
Така усещането, че виждате визуално, когато
тези три неща работят рамо до рамо

900
00:40:44,650 --> 00:40:47,930
п е квадрат срещу 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