1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [За възпроизвеждане на музика]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Добре.

4
00:00:13,500 --> 00:00:14,670
Добре, добре дошъл отново.

5
00:00:14,670 --> 00:00:18,120
Така че това е седмица 4, началото
от него, вече.

6
00:00:18,120 --> 00:00:21,320
И вие си спомняте, че миналата седмица, ще се постави
код отмени само малко

7
00:00:21,320 --> 00:00:24,240
и започнахме да говорим малко по-
на високо равнище, за такива неща

8
00:00:24,240 --> 00:00:28,130
търсене и сортиране, които макар и
малко прости идеи, са

9
00:00:28,130 --> 00:00:31,840
представител на даден клас проблеми
вие ще започнете да се реши по-специално

10
00:00:31,840 --> 00:00:34,820
като започнем да мислим за финал
проекти и интересни решения ви

11
00:00:34,820 --> 00:00:36,760
Може би трябва да проблемите на реалния свят.

12
00:00:36,760 --> 00:00:39,490
Сега балон вид е един от най-простите
такива алгоритми, и то

13
00:00:39,490 --> 00:00:42,900
работил като от тези малки числа
в списък или в масив вид

14
00:00:42,900 --> 00:00:46,530
балон пътя си до върха, и
големите цифри премести своя път надолу, за да

15
00:00:46,530 --> 00:00:47,930
В края на този списък.

16
00:00:47,930 --> 00:00:50,650
>> И припомни, че бихме могли да се визуализира
балон подреди малко

17
00:00:50,650 --> 00:00:52,310
нещо като това.

18
00:00:52,310 --> 00:00:53,640
Така че нека да вървим напред и щракнете върху Старт.

19
00:00:53,640 --> 00:00:55,350
Аз бях избрана предварително балон подреди.

20
00:00:55,350 --> 00:00:58,920
И ако си спомняте, че по-високият синьо
Линиите представляват големите цифри, малки

21
00:00:58,920 --> 00:01:03,300
Сините линии представляват малки номера, като
ние преминаваме през това отново и отново, и

22
00:01:03,300 --> 00:01:07,680
отново, като се сравняват два бара до всеки
други в червено, отиваме да сменяте

23
00:01:07,680 --> 00:01:11,010
най-голямата и най-малката, ако
те са в ред.

24
00:01:11,010 --> 00:01:14,150
>> Така че това ще продължи и продължи и да се
на, и ще видите, че по-голямата

25
00:01:14,150 --> 00:01:16,700
елементи са си проправяха път към
право, и по-малките елементи са

26
00:01:16,700 --> 00:01:17,900
вземане на пътя си наляво.

27
00:01:17,900 --> 00:01:21,380
Но ние започнахме да се определи количествено
на ефективност,

28
00:01:21,380 --> 00:01:22,970
Качеството на този алгоритъм.

29
00:01:22,970 --> 00:01:25,200
И ние казахме, че в най-лошия
случай, този алгоритъм се

30
00:01:25,200 --> 00:01:27,940
приблизително колко стъпки?

31
00:01:27,940 --> 00:01:28,980
>> Така п квадрат.

32
00:01:28,980 --> 00:01:30,402
И това, което е п?

33
00:01:30,402 --> 00:01:31,650
>> Публика: Брой елементи.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Значи п е
броя на елементите.

35
00:01:32,790 --> 00:01:33,730
И така, ние ще направим това често.

36
00:01:33,730 --> 00:01:36,650
Всеки път, когато искам да говоря за размера
на даден проблем или размера на

37
00:01:36,650 --> 00:01:39,140
вход, или размера на времето, необходимо
да произвеждат продукция, ние просто ще

38
00:01:39,140 --> 00:01:41,610
генерализирана каквото
на входа е като п.

39
00:01:41,610 --> 00:01:45,970
Така че обратно в Седмица 0, броя страници
в телефонния указател е п.

40
00:01:45,970 --> 00:01:47,550
Броят на учениците
в стаята беше п.

41
00:01:47,550 --> 00:01:49,630
Така че и тук, ние сме след
този модел.

42
00:01:49,630 --> 00:01:52,800
>> Сега п квадрат не е особено
бързо, така че ние се опитахме да направим по-добре.

43
00:01:52,800 --> 00:01:55,970
И така, разгледахме няколко
други алгоритми, сред които

44
00:01:55,970 --> 00:01:57,690
бяха селекция вид.

45
00:01:57,690 --> 00:01:59,180
Така че избора е вид
малко по-различна.

46
00:01:59,180 --> 00:02:03,130
Беше почти опростена, смея да кажа,
при което I започва в началото на

47
00:02:03,130 --> 00:02:06,740
списък на нашите доброволци и аз просто отново
и отново, и отново премина през

48
00:02:06,740 --> 00:02:10,060
списъка, скубане от най-малките
елемент в даден момент и пускането му или

49
00:02:10,060 --> 00:02:13,040
я в началото на списъка.

50
00:02:13,040 --> 00:02:16,410
>> Но това също, след като започнах да мисля
чрез математиката и по-голяма

51
00:02:16,410 --> 00:02:19,860
картина, помисли си колко пъти
Щях назад и напред и назад

52
00:02:19,860 --> 00:02:24,090
и напред, ние се казва в най-лошия случай,
избор подреди също беше какво?

53
00:02:24,090 --> 00:02:24,960
N на квадрат.

54
00:02:24,960 --> 00:02:27,490
Сега в реалния свят, може да
действително да бъде малко по-бързо.

55
00:02:27,490 --> 00:02:30,620
Защото отново, аз не трябва да се запази
връщане назад, след като бях подредени на

56
00:02:30,620 --> 00:02:31,880
най-малките елементи.

57
00:02:31,880 --> 00:02:35,090
Но ако се замислим много голяма п и
ако нещо се направи по математика като

58
00:02:35,090 --> 00:02:39,170
Направих на дъската, с N на квадрат
минус нещо, всичко останало

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

60
00:02:41,850 --> 00:02:42,850
значение толкова много.

61
00:02:42,850 --> 00:02:45,470
Така че като компютърни специалисти, ние някак
си затварят очите за по-малките

62
00:02:45,470 --> 00:02:49,220
фактори и се съсредоточи само върху фактор в
израз, който ще ви накара

63
00:02:49,220 --> 00:02:50,330
най-голямата разлика.

64
00:02:50,330 --> 00:02:52,840
>> Е, накрая, погледнахме
при поставяне подреди.

65
00:02:52,840 --> 00:02:56,620
И това е сходна по дух, но
вместо да мине през итеративно и

66
00:02:56,620 --> 00:03:01,250
изберете най-малкия елемент един по един
път I вместо пое ръката, че

67
00:03:01,250 --> 00:03:04,070
успя да се справи, и аз реших, всички
Добре, ти е мястото тук.

68
00:03:04,070 --> 00:03:06,160
След това се преместих към следващия елемент
и реши, че той или

69
00:03:06,160 --> 00:03:07,470
тя принадлежи тук.

70
00:03:07,470 --> 00:03:08,810
И след това се преместих на и на.

71
00:03:08,810 --> 00:03:11,780
И аз може да, по протежение на пътя,
смени тези момчета, за да се

72
00:03:11,780 --> 00:03:13,030
направи място за тях.

73
00:03:13,030 --> 00:03:16,880
Така че това е нещо като психическо възстановяване
избор на вида, който ние

74
00:03:16,880 --> 00:03:18,630
нарича вмъкване вид.

75
00:03:18,630 --> 00:03:20,810
>> Така че, тези теми да се появят
в реалния свят.

76
00:03:20,810 --> 00:03:23,640
Само преди няколко години, когато определен
Сенаторът се кандидатира за президент,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, по времето, когато изпълнителен директор на
Google, имал действително възможност

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

79
00:03:28,040 --> 00:03:32,010
И ние смятахме, че ще споделя това YouTube
клип за теб, ако можем да се появи

80
00:03:32,010 --> 00:03:32,950
силата на звука.

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO PLAYBACK]

82
00:03:39,360 --> 00:03:44,620
>> -Сега, Senator, ти си тук в Google,
и аз предпочитам да мисля за президентския пост

83
00:03:44,620 --> 00:03:46,042
като интервю за работа.

84
00:03:46,042 --> 00:03:47,770
>> [СМЯХ]

85
00:03:47,770 --> 00:03:50,800
>> -Сега е трудно да се получи
работа като президент.

86
00:03:50,800 --> 00:03:52,480
И, което става чрез
тръпки предприятието.

87
00:03:52,480 --> 00:03:54,330
То също е трудно да се намери работа в Google.

88
00:03:54,330 --> 00:03:59,610
Ние имаме въпроси и искаме
нашите кандидати въпроси.

89
00:03:59,610 --> 00:04:02,250
И това е една от Larry Швимер.

90
00:04:02,250 --> 00:04:05,325
>> [СМЯХ]

91
00:04:05,325 --> 00:04:06,400
-Мислите, че се шегувам?

92
00:04:06,400 --> 00:04:08,750
Това е точно тук.

93
00:04:08,750 --> 00:04:12,110
Какво е най-ефективният начин да се
сортирате един милион две-битови цели числа?

94
00:04:12,110 --> 00:04:15,810
>> [СМЯХ]

95
00:04:15,810 --> 00:04:18,260
>> -Ами, ъ-ъ -

96
00:04:18,260 --> 00:04:19,029
>> -Съжалявам.

97
00:04:19,029 --> 00:04:19,745
Може би трябва -

98
00:04:19,745 --> 00:04:21,000
>> -Не, не, не, не, не.

99
00:04:21,000 --> 00:04:21,470
>> -Това не е -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Мисля, че балонът ще подреди
бъде по грешен начин да отида.

102
00:04:25,328 --> 00:04:26,792
>> [СМЯХ]

103
00:04:26,792 --> 00:04:28,510
>> [Аплодисменти и аплодисменти]

104
00:04:28,510 --> 00:04:31,211
>> -Хайде, кой му е казал?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [END възпроизвеждане на видео]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Така че има ли го.

108
00:04:35,070 --> 00:04:39,600
Така че ние започнахме да се определи количествено тези текущи
пъти, така да се каже, с нещо

109
00:04:39,600 --> 00:04:43,480
нарича асимптотичната нотация, която е
просто се позовава на нашия вид на завъртане

110
00:04:43,480 --> 00:04:47,420
си затварят очите за тези по-малки фактори и
само гледа на времето за работа,

111
00:04:47,420 --> 00:04:51,250
изпълнението на тези алгоритми,
като н стане наистина голяма с течение на времето.

112
00:04:51,250 --> 00:04:55,110
И така, ние въведохме голям O. И голяма O
представлява нещо, което си мислехме

113
00:04:55,110 --> 00:04:57,000
на като горна граница.

114
00:04:57,000 --> 00:04:59,570
И всъщност, Бари, може ли да намали
от микрофона за малко?

115
00:04:59,570 --> 00:05:01,040
>> Ние решихме, че това е горна граница.

116
00:05:01,040 --> 00:05:04,710
Така че голяма O от квадратите на средства п, че в
най-лошия случай, нещо като

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

118
00:05:07,780 --> 00:05:10,310
Или нещо подобно вмъкване сортиране
би н идеален стъпки.

119
00:05:10,310 --> 00:05:15,150
Сега за нещо като вмъкване
вид, това, което беше най-лошия случай?

120
00:05:15,150 --> 00:05:18,200
Като се има предвид масив, това, което е най-лошото
възможно сценарий, който може да откриете

121
00:05:18,200 --> 00:05:20,650
се сблъскват с?

122
00:05:20,650 --> 00:05:21,860
>> Това е напълно назад, нали?

123
00:05:21,860 --> 00:05:24,530
Защото, ако е напълно назад,
което трябва да направите един куп работа.

124
00:05:24,530 --> 00:05:26,420
Защото, ако ти си напълно назад,
вие ще намерите

125
00:05:26,420 --> 00:05:28,840
най-големият елемент тук, въпреки че
принадлежи там.

126
00:05:28,840 --> 00:05:31,140
Така че ти започваш да се каже, добре, най-
настоящия момент, ти е мястото тук,

127
00:05:31,140 --> 00:05:32,310
така ли да го оставят на мира.

128
00:05:32,310 --> 00:05:35,425
>> Тогава осъзнаваш, о, по дяволите, трябва да
преместите тази малко по-малък елемент, който да

129
00:05:35,425 --> 00:05:36,470
вляво от вас.

130
00:05:36,470 --> 00:05:38,770
Тогава аз трябва да го направя отново
и отново и отново.

131
00:05:38,770 --> 00:05:41,410
И ако аз тръгна напред и назад, вие
би някак да се чувстват изпълнението на

132
00:05:41,410 --> 00:05:45,540
че алгоритъм, защото постоянно съм
размесването на всички останали надолу в

133
00:05:45,540 --> 00:05:46,510
масив за да направи място за него.

134
00:05:46,510 --> 00:05:47,750
Така че това е най-лошия случай.

135
00:05:47,750 --> 00:05:48,570
>> От друга страна -

136
00:05:48,570 --> 00:05:50,320
и това е Катерачът последен път -

137
00:05:50,320 --> 00:05:54,065
казахме, че поставянето сортиране
е омегата на какво?

138
00:05:54,065 --> 00:05:57,530
Какъв е най-добрия случай работа
поставянето им вид?

139
00:05:57,530 --> 00:05:58,520
Така че това е всъщност п.

140
00:05:58,520 --> 00:06:00,980
Това беше празен, че си тръгнахме
на борда последен път.

141
00:06:00,980 --> 00:06:03,160
>> И това е омега на N, защото защо?

142
00:06:03,160 --> 00:06:06,630
Е, в най-добрия случай, това, което е
вмъкване вид ще бъде предаден?

143
00:06:06,630 --> 00:06:09,830
Е, списък, който е напълно сортирани
вече, минимална работа за вършене.

144
00:06:09,830 --> 00:06:12,460
Но това, което е чист за вмъкване сортиране
е, че тъй като започва тук

145
00:06:12,460 --> 00:06:15,340
реши, о, ти си номер
едно, ти е мястото тук.

146
00:06:15,340 --> 00:06:16,970
О, какъв късмет.

147
00:06:16,970 --> 00:06:17,740
>> Ти си номер две.

148
00:06:17,740 --> 00:06:19,030
Можете също е тук.

149
00:06:19,030 --> 00:06:21,010
Номер три, още по-добре,
ти е мястото тук.

150
00:06:21,010 --> 00:06:25,210
Веднага след като стигне до края на
списък, за вмъкване вид на pseudocode

151
00:06:25,210 --> 00:06:28,010
че вървяхме устно
Последният път, това е направено.

152
00:06:28,010 --> 00:06:32,790
Но избора сортиране, от друга страна,
съхраняват какво?

153
00:06:32,790 --> 00:06:35,260
>> Продължих през списъка
отново и отново и отново.

154
00:06:35,260 --> 00:06:39,160
Тъй като ключовата поглед има само
след като погледна по целия път до

155
00:06:39,160 --> 00:06:42,500
края на списъка може да бъде определен
че елементът, който сте избрали е

156
00:06:42,500 --> 00:06:45,560
В действителност в момента малкият елемент.

157
00:06:45,560 --> 00:06:48,920
Така че тези различни умствени края модели
до което се получават някои много реалния свят

158
00:06:48,920 --> 00:06:53,130
разлики за нас, както и тези
теоретични асимптотичната различия.

159
00:06:53,130 --> 00:06:56,910
>> Така че просто да обобщим, след това, голяма O на п
квадрат, видяхме няколко такива

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

161
00:06:58,350 --> 00:06:59,580
Big O на п?

162
00:06:59,580 --> 00:07:02,870
Какво е алгоритъм, който може да
се казва, че е голяма О п?

163
00:07:02,870 --> 00:07:06,930
В най-лошия случай, е необходимо
линейна редица стъпки.

164
00:07:06,930 --> 00:07:07,810
>> OK, линейно търсене.

165
00:07:07,810 --> 00:07:10,470
И в най-лошия случай, когато е
елемент, което търсите, когато

166
00:07:10,470 --> 00:07:12,950
прилагане на линейно търсене?

167
00:07:12,950 --> 00:07:14,680
>> OK, в най-лошия случай,
дори не е там.

168
00:07:14,680 --> 00:07:17,000
Или на втория най-лошия случай, че е
чак в края, което е

169
00:07:17,000 --> 00:07:18,880
плюс или минус една стъпка разлика.

170
00:07:18,880 --> 00:07:21,180
Така в края на деня,
можем да кажем, че е линейна.

171
00:07:21,180 --> 00:07:23,910
Big O на N ще бъде линейна търсене,
тъй като в най-лошия случай,

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

173
00:07:26,610 --> 00:07:29,370
>> Е, голяма O на дневника на п.

174
00:07:29,370 --> 00:07:32,760
Не говорихме много подробно за
това, но сме виждали и преди.

175
00:07:32,760 --> 00:07:36,840
Това, което работи в така наречената логаритмична
време, в най-лошия случай?

176
00:07:36,840 --> 00:07:38,500
>> Да, така двоично търсене.

177
00:07:38,500 --> 00:07:42,930
И двоично търсене в най-лошия случай
може да има елемент някъде в

178
00:07:42,930 --> 00:07:45,640
средата, или някъде
във вътрешността на масива.

179
00:07:45,640 --> 00:07:48,040
Но само да го намерите, след като
разделят списък на половина, в

180
00:07:48,040 --> 00:07:48,940
половина на половина, на половина.

181
00:07:48,940 --> 00:07:50,200
И тогава готово, че е там.

182
00:07:50,200 --> 00:07:52,500
Или пък най-лошия случай,
дори не е там.

183
00:07:52,500 --> 00:07:56,770
Но ти не знаеш, че не е там
докато вид достигне до това последно

184
00:07:56,770 --> 00:08:00,470
отдолу повечето елементи от намаляване наполовина
и намаляване наполовина и намаляване наполовина.

185
00:08:00,470 --> 00:08:01,400
>> Big O от 1.

186
00:08:01,400 --> 00:08:03,540
Така че бихме могли голям от 2 O, O голяма от 3.

187
00:08:03,540 --> 00:08:06,260
Всеки път, когато искате просто постоянно число,
ние просто някак от само опростяване

188
00:08:06,260 --> 00:08:07,280
, че по-голям от 1 Н.

189
00:08:07,280 --> 00:08:10,440
Въпреки че, ако реалистично, е необходимо
2 или дори 100 стъпки, ако това е

190
00:08:10,440 --> 00:08:13,680
постоянен брой стъпки,
ние само да кажа голямо O от 1.

191
00:08:13,680 --> 00:08:15,930
Какво е алгоритъм, който е
в голяма О от 1?

192
00:08:15,930 --> 00:08:18,350
>> Публика: Намирането на дължина
на променлива.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Намирането на
дължина на променлива?

194
00:08:21,090 --> 00:08:23,870
>> Публика: Не, дължината
ако той вече е сортиран.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Добре.

196
00:08:24,160 --> 00:08:27,850
ОК, така че намирането на дължината на нещо
Ако дължината на, че нещо, като

197
00:08:27,850 --> 00:08:30,020
масив, се съхранява в някои променлива.

198
00:08:30,020 --> 00:08:33,380
Защото може просто да прочетете променлива,
или отпечатване на променлива, или

199
00:08:33,380 --> 00:08:34,960
Просто обикновено достъп до тази променлива.

200
00:08:34,960 --> 00:08:37,299
И готово, че отнема константно време.

201
00:08:37,299 --> 00:08:38,909
>> От друга страна, мисля, обратно към нулата.

202
00:08:38,909 --> 00:08:42,460
Спомни си за първата седмица на C,
призовава просто ФОРМАТ и печат

203
00:08:42,460 --> 00:08:46,240
нещо на екрана, е може би
константно време, защото това просто отнема

204
00:08:46,240 --> 00:08:50,880
някои броя на процесорните цикли, за да покаже
че текста на екрана.

205
00:08:50,880 --> 00:08:52,720
Или чакаме - нали?

206
00:08:52,720 --> 00:08:56,430
Как иначе може да се моделира
изпълнение на ФОРМАТ?

207
00:08:56,430 --> 00:09:00,420
Някой би ли искал да не се съглася, че
може би това не е наистина константно време?

208
00:09:00,420 --> 00:09:03,600
В какъв смисъл може ФОРМАТ бяга
време, да я отпечатате в низ от

209
00:09:03,600 --> 00:09:05,580
на екрана, е нещо
различни от постоянна.

210
00:09:05,580 --> 00:09:07,860
>> Публиката: [недоловим].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Да.

212
00:09:08,230 --> 00:09:09,300
Така че зависи от наша гледна точка.

213
00:09:09,300 --> 00:09:13,390
Ако ние всъщност мислим за приноса към
ФОРМАТ като низ, и

214
00:09:13,390 --> 00:09:16,380
Затова ние измерваме размера на това
въвеждане на данни от своята дължина - така да го наречем

215
00:09:16,380 --> 00:09:17,780
тази дължина N, както и -

216
00:09:17,780 --> 00:09:21,990
може би, ФОРМАТ себе си е голяма O на п
защото тя ще ви отведе п стъпки

217
00:09:21,990 --> 00:09:24,750
да отпечатате всяка от тези п
герои, най-вероятно.

218
00:09:24,750 --> 00:09:27,730
Най-малко до степен, че да поеме
че може би това е използване за линия

219
00:09:27,730 --> 00:09:28,560
под предния капак.

220
00:09:28,560 --> 00:09:30,860
>> Но ние ще трябва да погледнете, че
код, за да разберат по-добре.

221
00:09:30,860 --> 00:09:33,650
И наистина, след като вие започнете
анализира вашите собствени алгоритми, ще

222
00:09:33,650 --> 00:09:34,900
буквално направи точно това.

223
00:09:34,900 --> 00:09:37,765
Сортиране на очната ябълка кода си и мисля,
за - Добре, аз имам този цикъл

224
00:09:37,765 --> 00:09:41,870
тук или имам вложени цикъла тук,
че ще направи н неща п пъти,

225
00:09:41,870 --> 00:09:46,050
и можете да сортирате на разума си път
чрез кода, дори ако това е

226
00:09:46,050 --> 00:09:47,980
pseudocode а не действителният код.

227
00:09:47,980 --> 00:09:49,730
>> Така че какво да кажем за омегата на п квадрат?

228
00:09:49,730 --> 00:09:53,582
Какво е алгоритъм, който по най-добрия
случай, все още се п квадрат стъпки?

229
00:09:53,582 --> 00:09:54,014
Да?

230
00:09:54,014 --> 00:09:54,880
>> Публиката: [недоловим].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Така че избор подреди.

232
00:09:55,900 --> 00:09:59,150
Поради това, че проблемът наистина намалява
на факта, че отново, аз не знам

233
00:09:59,150 --> 00:10:02,600
Аз открих текущата най-малката до
Аз направих всички дяволски елементи.

234
00:10:02,600 --> 00:10:08,050
Така че омега на, да речем, п, ние
Просто дойде с една.

235
00:10:08,050 --> 00:10:09,300
Insertion вид.

236
00:10:09,300 --> 00:10:12,370
Ако списъкът се случва да се сортират
вече, в най-добрия случай ние просто трябва

237
00:10:12,370 --> 00:10:15,090
да се направи една атака през него,
в който момент сме сигурни.

238
00:10:15,090 --> 00:10:17,890
И след това, че може да се каже
да бъде линейна, със сигурност.

239
00:10:17,890 --> 00:10:20,570
>> Ами омегата на един?

240
00:10:20,570 --> 00:10:23,790
Какво, в най-добрия случай може да отнеме
постоянен брой стъпки?

241
00:10:23,790 --> 00:10:27,220
Така линейно търсене, ако просто се късметлия
и елемента, което търсите

242
00:10:27,220 --> 00:10:31,000
е точно в началото на списъка,
ако това е, когато сте се започне вашата

243
00:10:31,000 --> 00:10:33,070
линейна прекосявам на този списък.

244
00:10:33,070 --> 00:10:35,180
>> И това е вярно на
редица неща.

245
00:10:35,180 --> 00:10:37,660
Например, дори двоичен
търсене е омега на 1.

246
00:10:37,660 --> 00:10:40,310
Защото какво, ако получите наистина дяволски
късмет и да пляскам-DAB в средата на

247
00:10:40,310 --> 00:10:42,950
си масив е броят
, което търсите?

248
00:10:42,950 --> 00:10:45,730
Така че можете да получите късмет там, както добре.

249
00:10:45,730 --> 00:10:49,190
>> Това, на последно място, омега на п дневник п.

250
00:10:49,190 --> 00:10:52,573
Така п дневник N, всъщност не
говори за още, но -

251
00:10:52,573 --> 00:10:53,300
>> Публика: Обединяване вид?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: Merge вид.

253
00:10:53,960 --> 00:10:56,920
Това беше Катерачът от последния път,
когато ние предложихме, и ние показахме,

254
00:10:56,920 --> 00:10:58,600
визуално, че има алгоритми.

255
00:10:58,600 --> 00:11:02,470
И се сливат вид само един такъв
алгоритъм, който е фундаментално по-бързо

256
00:11:02,470 --> 00:11:03,450
, отколкото някои от другите момчета.

257
00:11:03,450 --> 00:11:07,800
В действителност, слива кратко е не само в
най-добрия случай н н лог, в най-лошия

258
00:11:07,800 --> 00:11:09,460
Дело N N лог.

259
00:11:09,460 --> 00:11:14,540
И когато имате това съвпадение на
омега и големи O е едно и също нещо?

260
00:11:14,540 --> 00:11:17,310
Ние всъщност може да опише, че това, което е
нарича тета, въпреки че това е

261
00:11:17,310 --> 00:11:18,220
малко по-рядко.

262
00:11:18,220 --> 00:11:21,730
Но това означава само на два скока,
В този случай, са едни и същи.

263
00:11:21,730 --> 00:11:25,770
>> Така се слеят вид, това, което прави това
наистина се свеждат до за нас?

264
00:11:25,770 --> 00:11:27,000
Е, припомни мотивация.

265
00:11:27,000 --> 00:11:30,340
Позволете ми да спра друга анимация, която
ние не погледна за последен път.

266
00:11:30,340 --> 00:11:33,390
Това, същата идея, но
това е малко по-голям.

267
00:11:33,390 --> 00:11:36,160
И аз ще отида напред и да се отбележи,
първо - имаме вмъкване вид на

268
00:11:36,160 --> 00:11:39,410
горния ляв ъгъл, след това избор на вид,
балон вид, няколко други видове -

269
00:11:39,410 --> 00:11:42,670
черупката и бързо - че не сме говорили
за, и куп и се сливат вид.

270
00:11:42,670 --> 00:11:47,090
>> Така поне се опита да се съсредоточи очите си
челната тройка в ляво и след това

271
00:11:47,090 --> 00:11:49,120
сливат подреди когато щракнете
тази зелена стрелка.

272
00:11:49,120 --> 00:11:51,900
Но ще ти дам всички от тях тече, само за да
ще ви даде усещане за разнообразието на

273
00:11:51,900 --> 00:11:53,980
алгоритми, които съществуват в света.

274
00:11:53,980 --> 00:11:56,180
Аз няма да позволя този план
само за няколко секунди.

275
00:11:56,180 --> 00:11:59,640
И ако се съсредоточи очите си - изберете по-
алгоритъм, се фокусира върху него само за

276
00:11:59,640 --> 00:12:02,970
секунда - ще започнем да виждаме
модел, че това е изпълнение.

277
00:12:02,970 --> 00:12:04,530
>> Обединяване вид, забележка, е направено.

278
00:12:04,530 --> 00:12:06,430
Heap вид, бързо сортиране, черупки -

279
00:12:06,430 --> 00:12:09,480
така че изглежда, ние въведохме три
лошите алгоритми миналата седмица.

280
00:12:09,480 --> 00:12:12,960
Но това е добре, че сме тук днес, за да
Посетете вид сливане, което е една от

281
00:12:12,960 --> 00:12:16,500
по-лесно тези, е да погледнете, дори
въпреки че вероятно ще огъне ума си

282
00:12:16,500 --> 00:12:17,490
само малко.

283
00:12:17,490 --> 00:12:21,130
Тук можем да видим точно колко
избор подреди гадно.

284
00:12:21,130 --> 00:12:24,600
>> Но от друга страна, това е
много лесно за изпълнение.

285
00:12:24,600 --> 00:12:28,160
И може би за Set P 3, това е един от най-
алгоритми, които сте избрали да прилагат

286
00:12:28,160 --> 00:12:28,960
за стандартното издание.

287
00:12:28,960 --> 00:12:30,970
Съвършено глоба, съвсем верен.

288
00:12:30,970 --> 00:12:35,210
>> Но отново, като п получава голям, ако
да изберат да изпълняват по-бърз алгоритъм

289
00:12:35,210 --> 00:12:39,020
като се слеят вид, шансовете са по-големи и
по-големи входове, кода си е просто

290
00:12:39,020 --> 00:12:39,800
ще работи по-бързо.

291
00:12:39,800 --> 00:12:41,090
Вашият сайт ще работи по-добре.

292
00:12:41,090 --> 00:12:42,650
Вашите потребители ще бъде по-щастлив.

293
00:12:42,650 --> 00:12:45,280
И така, там са тези ефекти
на всъщност дава

294
00:12:45,280 --> 00:12:47,350
ни малко по-дълбоко и мислех.

295
00:12:47,350 --> 00:12:49,990
>> Така че нека да погледнем какво се слеят
Сортът е всъщност всичко.

296
00:12:49,990 --> 00:12:52,992
В готино нещо е, че се слеят
Сортът е точно това.

297
00:12:52,992 --> 00:12:56,300
Това е, отново, това, което сме нарича
pseudocode, pseudocode същество

298
00:12:56,300 --> 00:12:57,720
English-подобен синтаксис.

299
00:12:57,720 --> 00:12:59,890
И простотата е
нещо очарователно.

300
00:12:59,890 --> 00:13:02,840
>> Така че на входа на наш елементи - така че
просто означава, ето един масив.

301
00:13:02,840 --> 00:13:04,000
Той има п неща в него.

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

303
00:13:05,370 --> 00:13:07,560
>> Ако п е по-малко от 2, се върне.

304
00:13:07,560 --> 00:13:08,640
Така че това е просто тривиално случай.

305
00:13:08,640 --> 00:13:12,580
Ако п е по-малко от 2, а след това очевидно е
1 или 0, като в този случай нещо

306
00:13:12,580 --> 00:13:14,780
вече подредени или несъществуващи,
Така че просто се върнете.

307
00:13:14,780 --> 00:13:15,900
Няма какво да направя.

308
00:13:15,900 --> 00:13:18,360
Така че това е обикновен случай да скубя.

309
00:13:18,360 --> 00:13:20,110
>> Иначе, имаме три стъпки.

310
00:13:20,110 --> 00:13:23,650
Пъзел с лявата половина на елементите, сортиране
дясната половина на елементите,

311
00:13:23,650 --> 00:13:26,650
и след сливане на сортирани половини.

312
00:13:26,650 --> 00:13:29,400
Интересното тук е, че
Аз съм един вид на плоскодънни лодки, нали?

313
00:13:29,400 --> 00:13:32,300
Има вид на кръгов определение
за този алгоритъм.

314
00:13:32,300 --> 00:13:35,986
В какъв смисъл е този алгоритъм е
определение кръгла?

315
00:13:35,986 --> 00:13:37,850
>> Публиката: [недоловим].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Да, моя алгоритъм за сортиране,
двама от неговите стъпки са "вид

317
00:13:41,670 --> 00:13:44,640
нещо. "И така, това повдига
въпрос, добре, аз какво ще използвате

318
00:13:44,640 --> 00:13:46,460
да се справи със лявата половина
и дясната половина?

319
00:13:46,460 --> 00:13:49,600
А най-хубавото тук е, че въпреки че
Отново, това е оказващ влияние

320
00:13:49,600 --> 00:13:54,030
част потенциално, можете да използвате същия
алгоритъм, за да се справи със лявата половина.

321
00:13:54,030 --> 00:13:54,700
>> Но почакайте.

322
00:13:54,700 --> 00:13:57,070
Когато ти се казва да се справи със
лявата половина, какви са два

323
00:13:57,070 --> 00:13:58,240
стъпки ще е следващия?

324
00:13:58,240 --> 00:14:00,550
Ще се справи със лявата половина на
лявата половина и правото

325
00:14:00,550 --> 00:14:01,420
половина на лявата половина.

326
00:14:01,420 --> 00:14:04,430
По дяволите, как мога да сортирате тези две
половинки или четвъртинки, сега?

327
00:14:04,430 --> 00:14:05,260
>> Но това е ОК.

328
00:14:05,260 --> 00:14:07,830
Ние имаме алгоритъм за сортиране тук.

329
00:14:07,830 --> 00:14:10,660
И въпреки, че може да се тревожи в
първо това е нещо безкрайно

330
00:14:10,660 --> 00:14:12,780
линия, това е цикъл, който никога не е
ще свърши - това ще

331
00:14:12,780 --> 00:14:15,770
приключва, след това, което се случва?

332
00:14:15,770 --> 00:14:16,970
След като п е по-малко от 2.

333
00:14:16,970 --> 00:14:19,180
Което в крайна сметка ще се случи,
защото ако продължаваш да се намали наполовина и

334
00:14:19,180 --> 00:14:23,020
намаляване наполовина в намаляване наполовина тези половинки, със сигурност
в крайна сметка, което ще свърши

335
00:14:23,020 --> 00:14:25,350
нагоре само с 1 или 0 елементи.

336
00:14:25,350 --> 00:14:28,500
В този момент, този алгоритъм
казва, сте готови.

337
00:14:28,500 --> 00:14:31,020
>> Така че истинската магия в тази
алгоритъм изглежда да е в

338
00:14:31,020 --> 00:14:33,470
че последната стъпка, сливане.

339
00:14:33,470 --> 00:14:37,190
Тази проста идея просто сливане две
неща, че това, което е в крайна сметка ще

340
00:14:37,190 --> 00:14:40,920
да ни позволи да сортирате множество,
да речем, осем елементи.

341
00:14:40,920 --> 00:14:44,410
Така че аз имам още осем топки стрес нагоре
Оттук осем парчета хартия и един

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
които съм се да запазите.

344
00:14:46,140 --> 00:14:46,960
>> [СМЯХ]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Ако можем да вземем осем
доброволци, и да видим дали можем да

346
00:14:48,970 --> 00:14:51,430
играят това, така.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Компютърни науки става забавно.

349
00:14:53,565 --> 00:14:54,320
Добре.

350
00:14:54,320 --> 00:14:57,770
Е, как за теб три,
голямата ръка там.

351
00:14:57,770 --> 00:14:58,580
Четири в гърба.

352
00:14:58,580 --> 00:15:02,220
А какво ще кажеш, че ще правиш
три в този ред?

353
00:15:02,220 --> 00:15:03,390
И четири в предната част.

354
00:15:03,390 --> 00:15:04,920
Така че осем, качвай се.

355
00:15:04,920 --> 00:15:12,060
>> [СМЯХ]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Всъщност съм
Не съм сигурен какво е то.

357
00:15:13,450 --> 00:15:14,810
Дали е стрес топки?

358
00:15:14,810 --> 00:15:16,510
Бюрото лампи?

359
00:15:16,510 --> 00:15:18,650
Материалът?

360
00:15:18,650 --> 00:15:19,680
Интернет?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Така че качвай се.

363
00:15:21,310 --> 00:15:22,310
Кой би искал -

364
00:15:22,310 --> 00:15:23,570
продължаваме да правим.

365
00:15:23,570 --> 00:15:24,240
Нека да видим.

366
00:15:24,240 --> 00:15:26,460
И това ви поставя в населено място -

367
00:15:26,460 --> 00:15:27,940
сте в населено място един.

368
00:15:27,940 --> 00:15:28,670
Опа, чакай малко.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - Добре.

370
00:15:30,760 --> 00:15:31,310
Добре, всичко е наред.

371
00:15:31,310 --> 00:15:35,130
Добре, така че всеки да има място,
но не и по Glass Google.

372
00:15:35,130 --> 00:15:36,475
Нека да си вадя тези нагоре.

373
00:15:36,475 --> 00:15:37,115
Как се казваш?

374
00:15:37,115 --> 00:15:37,440
>> Мишел: Мишел.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Мишел?

376
00:15:38,090 --> 00:15:42,000
Добре, вие получавате да изглежда като
онази, ако това е ОК.

377
00:15:42,000 --> 00:15:44,625
Е, аз правя прекалено, предполагам,
само за миг.

378
00:15:44,625 --> 00:15:45,875
Добре, режим на готовност.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Опитваме се да излезе с
използват случая за Google Glass, и ние

381
00:15:50,950 --> 00:15:53,750
Мислех, че ще е забавно да правя просто
това, когато хората са на сцената.

382
00:15:53,750 --> 00:15:57,120
Ние ще запише света
от тяхна гледна точка.

383
00:15:57,120 --> 00:15:58,410
Добре.

384
00:15:58,410 --> 00:15:59,830
Не е вероятно това, което Google предназначен.

385
00:15:59,830 --> 00:16:02,260
Добре, ако нямате нищо против носенето
това за следващите неудобни-та минута,

386
00:16:02,260 --> 00:16:03,150
това би било чудесно.

387
00:16:03,150 --> 00:16:08,620
>> Добре, така че ние имаме тук един набор от
елементи, както и че на масиви, според

388
00:16:08,620 --> 00:16:11,480
хартийки в тези хора "
ръцете, в момента е в несортиран.

389
00:16:11,480 --> 00:16:12,050
>> Мишел: О, това е толкова странно.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Това е почти случайна.

391
00:16:12,810 --> 00:16:15,760
И в един момент, ние ще се опитаме
за изпълнение се слеят подреди заедно

392
00:16:15,760 --> 00:16:17,950
и да видим къде е този ключ прозрение.

393
00:16:17,950 --> 00:16:21,970
И този трик тук с вид сливане е
нещо, което не са поели още.

394
00:16:21,970 --> 00:16:24,030
Ние действително се нуждаят от
допълнително пространство.

395
00:16:24,030 --> 00:16:26,650
Така че това, което ще бъде особено
интересно за това е, че тези

396
00:16:26,650 --> 00:16:29,270
момчета ще се придвижват малко
малко, защото аз отивам да се предположи, че

397
00:16:29,270 --> 00:16:31,880
има допълнителен набор от пространство,
да речем, точно зад тях.

398
00:16:31,880 --> 00:16:34,570
>> Така че, ако те са зад стола си,
това е вторичен масив.

399
00:16:34,570 --> 00:16:36,960
Ако те са седнали тук, това е
първичния масив.

400
00:16:36,960 --> 00:16:40,170
Но това е ресурс, който трябва
не използват ливъридж до този момент с балон

401
00:16:40,170 --> 00:16:42,040
вид, с избор сортиране,
с вмъкване вид.

402
00:16:42,040 --> 00:16:44,600
Спомнете си миналата седмица, всеки просто
вид прокара на място.

403
00:16:44,600 --> 00:16:46,840
Те не са използвали нито допълнителна памет.

404
00:16:46,840 --> 00:16:49,310
Направихме стая за хора с
придвижване на хора наоколо.

405
00:16:49,310 --> 00:16:50,580
>> Така че това е ключово прозрение, също.

406
00:16:50,580 --> 00:16:53,410
Има един компромис, като цяло в
компютърни науки, на ресурсите.

407
00:16:53,410 --> 00:16:55,800
Ако искате да се ускори нещо
като време, започваш да

408
00:16:55,800 --> 00:16:56,900
трябва да платят цената.

409
00:16:56,900 --> 00:17:00,750
И един от тези цени е много често
пространство, обема памет или твърд

410
00:17:00,750 --> 00:17:01,700
дисково пространство, че използвате.

411
00:17:01,700 --> 00:17:03,640
Или, честно казано, сумата
на програмист време.

412
00:17:03,640 --> 00:17:06,700
Колко време ви отнема, човешкото,
действително да се приложат някои повече

413
00:17:06,700 --> 00:17:07,829
сложен алгоритъм.

414
00:17:07,829 --> 00:17:09,760
Но за днес, на компромис
е времето и пространството.

415
00:17:09,760 --> 00:17:11,930
>> Така че, ако вие може просто да задържите Вашия
числа, така че ние можем да видим, че си

416
00:17:11,930 --> 00:17:15,839
Всъщност съвпадение 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excellent.

418
00:17:16,599 --> 00:17:19,520
Така че аз ще се опитам да организирам
неща, ако вие може просто да

419
00:17:19,520 --> 00:17:21,800
следвай тук.

420
00:17:21,800 --> 00:17:26,650
>> Така че аз отивам да се прилага, от една страна,
Първата стъпка на pseudocode, който е

421
00:17:26,650 --> 00:17:29,440
за въвеждане на елементи N, ако п е
по-малко от два, след това се върнете.

422
00:17:29,440 --> 00:17:31,370
Очевидно е, че не
се прилагат, за да можем да продължат напред.

423
00:17:31,370 --> 00:17:33,340
Така сортирате лявата половина на елементите.

424
00:17:33,340 --> 00:17:36,220
Така че това означава, че аз ще се фокусирам
внимание само за момент за тези

425
00:17:36,220 --> 00:17:37,310
четири момчета тук.

426
00:17:37,310 --> 00:17:39,774
Добре, какво да направя следващия?

427
00:17:39,774 --> 00:17:40,570
>> Публика: Пъзел в лявата половина.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Така че сега трябва да се справи
лявата половина на тези момчета.

429
00:17:42,780 --> 00:17:45,580
Защото отново, да предположим, да си на
Целта е да се справи със лявата половина.

430
00:17:45,580 --> 00:17:46,440
Как се прави това?

431
00:17:46,440 --> 00:17:49,140
Просто следвайте инструкциите, дори
въпреки че го правим отново.

432
00:17:49,140 --> 00:17:50,160
Така сортирате лявата половина.

433
00:17:50,160 --> 00:17:52,030
Сега съм сортиране тези две момчета.

434
00:17:52,030 --> 00:17:53,563
Какво следва?

435
00:17:53,563 --> 00:17:54,510
>> Публика: Пъзел в лявата половина.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Пъзел в лявата половина.

437
00:17:55,460 --> 00:18:00,680
Така че сега това, това място тук,
е даден списък на площ 1.

438
00:18:00,680 --> 00:18:01,365
И какво ти беше името?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Принцеса Дейзи.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Принцеса Дейзи е тук.

441
00:18:03,690 --> 00:18:07,470
И така, тя е вече сортирана, защото
списъкът е с размер 1.

442
00:18:07,470 --> 00:18:09,490
Какво да правя следващия?

443
00:18:09,490 --> 00:18:13,680
OK, върни се, защото това е списък на
размер 1, което е по-малко от 2.

444
00:18:13,680 --> 00:18:14,320
Тогава каква е следващата стъпка?

445
00:18:14,320 --> 00:18:17,490
И сега трябва да се вид
изляза от ситуацията в ума си.

446
00:18:17,490 --> 00:18:19,340
>> Пъзел с дясната половина, което е -

447
00:18:19,340 --> 00:18:19,570
как ти е името?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
И така, какво ще правим сега, че
Имаме списък с размер 1?

451
00:18:23,210 --> 00:18:24,440
>> Публика: Върни.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: Внимателно.

453
00:18:24,760 --> 00:18:29,540
Връщаме първи, а сега трети
етап - и ако аз един вид го изобразяват с

454
00:18:29,540 --> 00:18:33,490
обхващащ две места сега, сега
трябва да се слеят тези два елемента.

455
00:18:33,490 --> 00:18:35,530
Така че сега, за съжаление, елементите
не са в ред.

456
00:18:35,530 --> 00:18:39,920
Но това е, когато процеса на сливане
започва да се непреодолими.

457
00:18:39,920 --> 00:18:42,410
>> Така че, ако вие може да се изправи само за
миг, че ще ви трябва, в

458
00:18:42,410 --> 00:18:44,170
момент, да се оттегли зад стола си.

459
00:18:44,170 --> 00:18:46,480
И ако Linda, защото 2 е
по-малък от 4, защо не

460
00:18:46,480 --> 00:18:48,130
когато си наоколо първи?

461
00:18:48,130 --> 00:18:48,690
Стой там.

462
00:18:48,690 --> 00:18:50,520
Така че Линда, когато си наоколо първи.

463
00:18:50,520 --> 00:18:53,820
>> Сега в действителност, ако това е просто масив
бихме могли просто да я преместим в реално време

464
00:18:53,820 --> 00:18:55,360
от този стол до това място.

465
00:18:55,360 --> 00:18:57,770
Така че представете си, че отне известно постоянно
брой стъпки 1.

466
00:18:57,770 --> 00:18:58,480
И сега -

467
00:18:58,480 --> 00:19:01,490
но ние трябва да ви постави в
първото място тук.

468
00:19:01,490 --> 00:19:03,930
>> И сега, ако можете да си наоколо,
, както и, ние ще

469
00:19:03,930 --> 00:19:06,300
да бъде в населено място два.

470
00:19:06,300 --> 00:19:09,120
И въпреки, че това се чувства като тя е
като известно време, това, което е хубаво в момента е

471
00:19:09,120 --> 00:19:14,710
че лявата половина на
лявата половина е вече подредени.

472
00:19:14,710 --> 00:19:18,010
И така, какво е следващата стъпка, ако сега
назад по-нататък в историята?

473
00:19:18,010 --> 00:19:18,980
>> Публика: дясната половина.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Пъзел в дясната половина.

475
00:19:19,900 --> 00:19:21,320
Така че вие ​​трябва да направите това, както добре.

476
00:19:21,320 --> 00:19:23,510
Така че, ако можех да се изправя
само за миг?

477
00:19:23,510 --> 00:19:25,192
И как ти е името?

478
00:19:25,192 --> 00:19:25,540
>> ДЖЕС: Джес.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Джес.

480
00:19:25,870 --> 00:19:29,720
ОК, така че Джес е сега в ляво
половина на дясната половина.

481
00:19:29,720 --> 00:19:31,400
И така, тя е списъка с размер 1.

482
00:19:31,400 --> 00:19:32,380
Тя очевидно подредени.

483
00:19:32,380 --> 00:19:33,070
И ти беше името?

484
00:19:33,070 --> 00:19:33,630
>> Мишел: Мишел.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle е очевидно
списък с размер 1.

486
00:19:35,340 --> 00:19:36,050
Тя вече подредени.

487
00:19:36,050 --> 00:19:38,690
Така че сега се случва магията,
процеса на сливане.

488
00:19:38,690 --> 00:19:39,790
Така че кой ще дойде?

489
00:19:39,790 --> 00:19:41,560
Очевидно Мишел.

490
00:19:41,560 --> 00:19:43,280
Така че, ако може да дойде отзад.

491
00:19:43,280 --> 00:19:47,090
Пространството, което имате на разположение за нея сега
е точно зад този стол тук.

492
00:19:47,090 --> 00:19:51,580
И сега, ако може да се върне, както и,
сега ние имаме, да бъде ясна, две

493
00:19:51,580 --> 00:19:53,810
половини, всяка от които с размер 2 -

494
00:19:53,810 --> 00:19:57,090
и само заради изобразяването му, ако
може да направи малко място -

495
00:19:57,090 --> 00:19:59,780
един лявата половина тук, един
дясната половина тук.

496
00:19:59,780 --> 00:20:01,160
>> Пренавиване напред в историята.

497
00:20:01,160 --> 00:20:02,270
Каква е следващата стъпка?

498
00:20:02,270 --> 00:20:03,030
>> Публика: Обединяване.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Така че сега трябва да се слеят.

500
00:20:04,160 --> 00:20:07,490
Така че, ОК, така че сега, за щастие, ние
просто освободени четири стола.

501
00:20:07,490 --> 00:20:11,480
Така че ние сме използвали два пъти повече памет, но
можем да дадем флип-флоп между

502
00:20:11,480 --> 00:20:12,330
на два масива.

503
00:20:12,330 --> 00:20:14,190
Така че кой номер е да са на първо място?

504
00:20:14,190 --> 00:20:14,850
Така Мишел, очевидно.

505
00:20:14,850 --> 00:20:16,680
Така дойде и поеми
мястото си тук.

506
00:20:16,680 --> 00:20:19,120
И след това номер 2 е очевидно
следващия, така че ела тук.

507
00:20:19,120 --> 00:20:21,520
Номер 4, номер 6.

508
00:20:21,520 --> 00:20:23,390
И отново, въпреки че има
малко ходене участва,

509
00:20:23,390 --> 00:20:26,010
Наистина, това може да се случи незабавно,
чрез преместване на един -

510
00:20:26,010 --> 00:20:26,880
OK, добре играе.

511
00:20:26,880 --> 00:20:28,350
>> [СМЯХ]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: И сега сме
в доста добра форма.

513
00:20:29,680 --> 00:20:34,910
В лявата половина на цялата
вход вече е сортиран.

514
00:20:34,910 --> 00:20:37,370
Добре, така че тези момчета трябваше
предимството си -

515
00:20:37,370 --> 00:20:40,340
как е в крайна сметка всички момичета на
наляво и всички момчета от дясно?

516
00:20:40,340 --> 00:20:42,450
>> ОК, така че момчета "до сега.

517
00:20:42,450 --> 00:20:44,680
Така че аз няма да ви преведе през
тези стъпки.

518
00:20:44,680 --> 00:20:46,550
Ще видим дали можем да кандидатства отново
същото pseudocode.

519
00:20:46,550 --> 00:20:50,050
Ако искате да отидете напред и да се изправя,
и момчета, нека да ви дам микрофона.

520
00:20:50,050 --> 00:20:52,990
Виж, ако не може да се реплицира какво
ние що го направих тук, на

521
00:20:52,990 --> 00:20:53,880
другия край на списъка.

522
00:20:53,880 --> 00:20:59,530
Кой трябва да говори първо,
въз основа на алгоритъм?

523
00:20:59,530 --> 00:21:03,210
Така обясни това, което правите, преди да
да извършите каквито и крака движения.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Добре, тъй като
Аз съм на лявата половина на

525
00:21:05,930 --> 00:21:07,790
лявата половина, се върна.

526
00:21:07,790 --> 00:21:08,730
Така ли е?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Добре.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: И след това -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Кой прави
микрофона преминете към следващата?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: Next номер.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Така че аз съм в дясната половина
на лявата половина на

532
00:21:14,720 --> 00:21:17,830
лявата половина, и се върна.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Добре.

534
00:21:18,050 --> 00:21:18,550
Ще се върнете.

535
00:21:18,550 --> 00:21:21,855
Така че сега, каква е следващата за вас двамата?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Искаме да видим кой е по-малък.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Точно така.

538
00:21:24,200 --> 00:21:24,940
Ние искаме да се слеят.

539
00:21:24,940 --> 00:21:27,590
Мястото, ние ще използваме, за да се слеят
ти в, въпреки че те са

540
00:21:27,590 --> 00:21:30,250
очевидно подредени вече, ние ще
да следват същия алгоритъм.

541
00:21:30,250 --> 00:21:31,560
Така че, който отива в гърба първо?

542
00:21:31,560 --> 00:21:35,720
Така 3, и след това 7.

543
00:21:35,720 --> 00:21:38,570
И сега микрофона отива
за тези момчета, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Така че аз съм на дясната половина на
лявата половина, и ми н е по-малко от

545
00:21:43,590 --> 00:21:45,048
1, така че аз съм просто ще мине -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Добре.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Аз съм дясната половина на
дясната половина на дясната половина, а аз съм

548
00:21:49,450 --> 00:21:51,740
Също така един човек, така че аз съм
ще се върне.

549
00:21:51,740 --> 00:21:52,990
Така че сега ние се слеят.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Така че да се върнем.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Така че отидете в гърба.

553
00:21:57,160 --> 00:21:59,200
Така 5 отива, а след това 8.

554
00:21:59,200 --> 00:22:01,240
И сега аудитория, която е
стъпка, която трябва да сега назад

555
00:22:01,240 --> 00:22:02,200
архивирате в нашите умове?

556
00:22:02,200 --> 00:22:02,940
>> Публика: Обединяване.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: Сливане на лявата половина и дясната
половината от първоначалния лявата половина.

558
00:22:07,270 --> 00:22:08,840
Така че сега -

559
00:22:08,840 --> 00:22:10,520
и само за да направи това ясно,
направи малко пространство

560
00:22:10,520 --> 00:22:11,690
между вас двамата.

561
00:22:11,690 --> 00:22:13,800
Така че сега е на два списъка,
наляво и надясно.

562
00:22:13,800 --> 00:22:18,320
Е, как сега да се слеят момчета в
на предния ред седалки отново?

563
00:22:18,320 --> 00:22:19,600
>> 3 отива на първо място.

564
00:22:19,600 --> 00:22:20,850
След 5, очевидно.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
След 7, а сега 8.

567
00:22:27,330 --> 00:22:28,710
OK, а сега сме ние?

568
00:22:28,710 --> 00:22:29,650
>> Публика: Не е направено.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Не е направено, тъй като
Очевидно е, че има един етап преди края.

570
00:22:32,440 --> 00:22:35,720
Но отново, причината, аз съм с този
жаргон като "назад в ума си"

571
00:22:35,720 --> 00:22:37,160
това е, защото това е наистина
какво се случва.

572
00:22:37,160 --> 00:22:39,610
Преминаваме през всички тези стъпки,
но ние сме нещо като пауза за

573
00:22:39,610 --> 00:22:42,480
момент, гмуркане дълбоко в
алгоритъм, спирайки за момент,

574
00:22:42,480 --> 00:22:45,840
гмуркане дълбоко в алгоритъм, и
сега трябва да се справи на назад в нашата

575
00:22:45,840 --> 00:22:49,430
умовете и връщане на всички тези слоеве
, че сме нещо като задържа.

576
00:22:49,430 --> 00:22:51,790
>> Така че сега имаме два списъка с размер 4.

577
00:22:51,790 --> 00:22:54,790
Ако вие може да се изправи за последен път
и да направи малко място тук, за да

578
00:22:54,790 --> 00:22:57,230
стане ясно, че това е най-ляво
половината от оригинала,

579
00:22:57,230 --> 00:22:58,620
дясната половина на оригинала.

580
00:22:58,620 --> 00:23:01,060
Кой е първият номер, който ние
трябва да дръпнете в гърба?

581
00:23:01,060 --> 00:23:01,870
Michelle, разбира се.

582
00:23:01,870 --> 00:23:03,230
>> Затова ние Michelle тук.

583
00:23:03,230 --> 00:23:05,080
И кой е номер 2?

584
00:23:05,080 --> 00:23:06,440
Номер 2 е по гръб, както добре.

585
00:23:06,440 --> 00:23:07,800
Номер 3?

586
00:23:07,800 --> 00:23:08,510
Excellent.

587
00:23:08,510 --> 00:23:16,570
Номер 4, номер 5, № 6,
номер 7 и номер 8.

588
00:23:16,570 --> 00:23:18,850
>> ОК, така че се чувствах като много
от стъпки, със сигурност.

589
00:23:18,850 --> 00:23:22,390
Но сега нека да видим дали не можем да потвърдим
нещо интуитивно, че това

590
00:23:22,390 --> 00:23:26,190
алгоритъм фундаментално, по-специално като
п стане наистина голям, тъй като сме виждали

591
00:23:26,190 --> 00:23:29,170
с анимации, е
основно по-бързо.

592
00:23:29,170 --> 00:23:33,400
Така че аз твърдя, този алгоритъм, в най-лошия
случай и дори в най-добрия случай,

593
00:23:33,400 --> 00:23:36,160
е голям O на п пъти дневник п.

594
00:23:36,160 --> 00:23:39,160
Това означава, че има някои аспекти на настоящото
алгоритъм, който взема п стъпки, но

595
00:23:39,160 --> 00:23:43,110
има и друг аспект някъде в
че итерация, че примка, че

596
00:23:43,110 --> 00:23:44,410
се лог н стъпки.

597
00:23:44,410 --> 00:23:49,154
Можем ли да постави пръста си върху това, което тези
две числа се отнасят до това?

598
00:23:49,154 --> 00:23:51,320
Е, къде -

599
00:23:51,320 --> 00:23:54,160
откъде микрофона отидете?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Бихте дневника п бъде
счупи ни на две -

601
00:23:58,660 --> 00:23:59,630
разделяне на две, по същество.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Точно така.

603
00:24:00,120 --> 00:24:03,000
Всеки път, когато виждаме във всеки алгоритъм, като по този начин
Досега е имало този модел на

604
00:24:03,000 --> 00:24:04,200
разделяне, разделяне, разделяне.

605
00:24:04,200 --> 00:24:05,700
И това обикновено намалява
за нещо, което е

606
00:24:05,700 --> 00:24:07,100
логаритмична, влезте основата 2.

607
00:24:07,100 --> 00:24:10,180
Но тя наистина може да бъде всичко,
но влезте основата 2.

608
00:24:10,180 --> 00:24:11,330
>> Сега какво ще кажете за п?

609
00:24:11,330 --> 00:24:14,550
Виждам, че ние любезно от ваша страна разделена
момчета - те разделят, те разделят,

610
00:24:14,550 --> 00:24:15,910
ви разделят, те разделят.

611
00:24:15,910 --> 00:24:18,760
Откъде идва краят идва?

612
00:24:18,760 --> 00:24:19,810
>> Така че това е сливане.

613
00:24:19,810 --> 00:24:20,610
Защото мисля за това.

614
00:24:20,610 --> 00:24:25,420
Когато обединявате осем души заедно,
при която половината от тях са набор от четири

615
00:24:25,420 --> 00:24:27,770
, а другата половина са друг
комплект от четири, как да отида

616
00:24:27,770 --> 00:24:28,820
за правене на сливането?

617
00:24:28,820 --> 00:24:30,830
Е, вие го е направил
доста интуитивно.

618
00:24:30,830 --> 00:24:34,140
>> Но ако вместо да го направи малко по-
методично, може би щях да посочи

619
00:24:34,140 --> 00:24:38,090
най-лявата лице за първи път с лявата си
ръка и посочи към най-лявата лице

620
00:24:38,090 --> 00:24:42,080
на, че половината с дясната си ръка, и
Просто впоследствие мина през

621
00:24:42,080 --> 00:24:46,990
списък и посочи най-малкия елемент
всеки път, движейки пръста си отново и

622
00:24:46,990 --> 00:24:48,970
повече, ако е необходимо в рамките на списъка.

623
00:24:48,970 --> 00:24:51,890
Но това, което е ключова за това сливане
Процесът е аз съм сравняване на тези двойки

624
00:24:51,890 --> 00:24:53,460
елементи.

625
00:24:53,460 --> 00:24:57,270
От дясната половина и отляво
половина, аз никога не съм веднъж връщане назад.

626
00:24:57,270 --> 00:25:00,570
>> Така че самото сливане е като
не повече от п стъпки.

627
00:25:00,570 --> 00:25:03,250
И колко пъти трябва
да направи това сливане?

628
00:25:03,250 --> 00:25:07,150
Е, не повече от N, и ние просто
видя, че с окончателното сливане.

629
00:25:07,150 --> 00:25:13,120
И така, ако направите нещо, което се
влезте п стъпки п пъти, или обратното,

630
00:25:13,120 --> 00:25:15,210
това ще ни даде п пъти дневник п.

631
00:25:15,210 --> 00:25:16,310
>> И защо това е по-добре?

632
00:25:16,310 --> 00:25:19,600
Е, ако ние вече знаем, че дневника
п е по-добре от N - нали?

633
00:25:19,600 --> 00:25:22,590
Видяхме в двоично търсене, телефонния указател
Например, дневник п определено беше

634
00:25:22,590 --> 00:25:23,760
по-добре от линейни.

635
00:25:23,760 --> 00:25:28,420
Така че това означава, че N пъти дневник п е
определено по-добре от време п друга

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

637
00:25:30,390 --> 00:25:32,400
И това е, което в крайна сметка се чувстват.

638
00:25:32,400 --> 00:25:34,928
>> Така аплодисменти, ако
можем, за тези момчета.

639
00:25:34,928 --> 00:25:38,920
>> [APPLAUSE]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: И вашите прощални подаръци -
може да запази номера,

641
00:25:41,550 --> 00:25:44,010
ако искате.

642
00:25:44,010 --> 00:25:45,620
И си прощален подарък, както обикновено.

643
00:25:45,620 --> 00:25:47,290
О, и ние ще Ви изпратим
кадри, Мишел.

644
00:25:47,290 --> 00:25:48,343
Благодаря.

645
00:25:48,343 --> 00:25:49,250
Добре.

646
00:25:49,250 --> 00:25:50,400
Помощ за себе си до стрес топката.

647
00:25:50,400 --> 00:25:54,110
>> И нека да спра, междувременно,
нашият приятел Rob Bowden да предложи

648
00:25:54,110 --> 00:25:59,520
малко по-различна гледна точка по този въпрос,
тъй като можете да мислите за тях

649
00:25:59,520 --> 00:26:01,280
стъпки, които се случват в малко
различен начин.

650
00:26:01,280 --> 00:26:04,750
В действителност, настройка за това, което е около Rob
да ни покаже предполага, че ние сме

651
00:26:04,750 --> 00:26:09,030
вече е направено на разделяне на
голям списък на осем малки списъци,

652
00:26:09,030 --> 00:26:10,570
всяка с размер 1.

653
00:26:10,570 --> 00:26:13,350
>> Така че промяна на pseudocode на
малко по-просто някак да стигнат до

654
00:26:13,350 --> 00:26:15,320
Основната идея на това как работи сливане.

655
00:26:15,320 --> 00:26:17,600
Но времето на работа на това, което
той е на път да направите, е все още

656
00:26:17,600 --> 00:26:19,110
ще бъде един и същ.

657
00:26:19,110 --> 00:26:23,540
И отново, за настройка тук е, че той е
започна с осем списъци с размер 1.

658
00:26:23,540 --> 00:26:27,730
Така че не сте пропуснали тази част, където той е
всъщност направи дневника N, N дневник, дневник п

659
00:26:27,730 --> 00:26:31,205
разделяне на входа.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO PLAYBACK]

661
00:26:32,120 --> 00:26:33,615
>> -Това е всичко за една стъпка.

662
00:26:33,615 --> 00:26:38,270
За втора стъпка, многократно
сливат чифта списъци.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Само аудио идва
от моя компютър.

665
00:26:41,270 --> 00:26:42,520
Нека да опитаме отново.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Просто произволно подбирате кои -
сега имаме четири списъка.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Научете преди.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Ето.

671
00:26:53,040 --> 00:27:00,510
>> -Обединяване на 108 и 15, ние в крайна
с списъка 15, 108.

672
00:27:00,510 --> 00:27:07,170
Сливане на 50 и 4, ние
свърши с 4, 50.

673
00:27:07,170 --> 00:27:12,990
Сливане на 8 и 42, ние
свърши с 8, 42.

674
00:27:12,990 --> 00:27:19,970
И сливане 23 и 16, ние
в крайна сметка с 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Сега всички наши списъци са с размер 2.

676
00:27:23,270 --> 00:27:26,690
Забележете, че всяка
четири списъка е сортиран.

677
00:27:26,690 --> 00:27:29,450
Така че можем да започнем обединяване
чифта списъци отново.

678
00:27:29,450 --> 00:27:38,420
Сливане на 15 и 108 и 4 и 50 години, ние
първо извади 4, а след това на 15, а след това

679
00:27:38,420 --> 00:27:41,500
50, след това 108.

680
00:27:41,500 --> 00:27:50,610
Сливане на 8, 42 и 16, 23, за първи път се
8, а след това на 16, а след това на 23,

681
00:27:50,610 --> 00:27:52,700
след това на 42.

682
00:27:52,700 --> 00:27:57,600
>> Така че сега ние имаме само два списъка с размер
4, всеки от които е сортирани.

683
00:27:57,600 --> 00:28:01,170
Така че сега ние се слеят тези два списъка.

684
00:28:01,170 --> 00:28:11,835
На първо място, ние се на 4, а след това вземем
8, след това вземем 15, след това 16, след това

685
00:28:11,835 --> 00:28:19,456
23, след това 42, след това 50, след това 108.

686
00:28:19,456 --> 00:28:19,872
>> [END възпроизвеждане на видео]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Отново, бележка, той никога
докосна дадена чашата повече от един път

688
00:28:23,430 --> 00:28:24,860
след напредък отвъд него.

689
00:28:24,860 --> 00:28:26,200
Така че той никога не е повтаряне.

690
00:28:26,200 --> 00:28:29,850
Така че той винаги се премести в страна,
и това е, когато имаме нашата п.

691
00:28:29,850 --> 00:28:33,290
>> Защо не нека да спра един анимация
които видяхме по-рано, но този път

692
00:28:33,290 --> 00:28:35,110
съсредоточи само върху подреди сливат.

693
00:28:35,110 --> 00:28:38,030
Позволете ми да отида напред и да я увеличите
в на този тук.

694
00:28:38,030 --> 00:28:42,530
Нека първо да изберете произволен вход,
подчертае това, и ще можете да сортирате виж

695
00:28:42,530 --> 00:28:46,600
това, което сме смятали за даденост, по-рано,
сливат подреди всъщност прави.

696
00:28:46,600 --> 00:28:50,330
>> Така забележите, че получавате тези половинки или
тези квартали или те отдават на

697
00:28:50,330 --> 00:28:53,140
Проблемът, който изведнъж
започнете да приемате добра форма.

698
00:28:53,140 --> 00:28:57,070
И накрая, ще се видим в
самия край, че бам,

699
00:28:57,070 --> 00:28:58,860
всичко се слива заедно.

700
00:28:58,860 --> 00:29:01,690
>> Така че това са само три различни
се на същата идея.

701
00:29:01,690 --> 00:29:05,980
Но ключът прозрение, точно като разделение
и владей в първия клас,

702
00:29:05,980 --> 00:29:10,640
е, че ние решихме да се разделят по някакъв начин
на проблема в нещо по-голямо, в

703
00:29:10,640 --> 00:29:14,760
нещо, нещо като еднакви по дух,
но по-малки и по-малки и по-малки

704
00:29:14,760 --> 00:29:15,660
и по-малки.

705
00:29:15,660 --> 00:29:18,420
>> Сега още един забавен начин да сортирате мисля
за тях, въпреки че това не е

706
00:29:18,420 --> 00:29:20,520
ще ви дам същия интуитивен
разбиране, е

707
00:29:20,520 --> 00:29:21,640
следното анимация.

708
00:29:21,640 --> 00:29:25,400
Така че това е видео някой, взети заедно
този, свързан различен

709
00:29:25,400 --> 00:29:29,970
звуци с различни операции за
вмъкване вид, за сортиране сливане, и

710
00:29:29,970 --> 00:29:31,150
за няколко други.

711
00:29:31,150 --> 00:29:32,330
Така че в един момент, аз отивам да се удари игра.

712
00:29:32,330 --> 00:29:33,600
Това е около една минута време.

713
00:29:33,600 --> 00:29:37,410
И въпреки че все още можете да видите
модели случва, този път може да

714
00:29:37,410 --> 00:29:41,420
също така да изслушат как тези алгоритми са
изпълнение по различен начин и с

715
00:29:41,420 --> 00:29:43,950
малко по-различни модели.

716
00:29:43,950 --> 00:29:45,830
>> Това е вмъкване вид.

717
00:29:45,830 --> 00:29:50,400
>> [ТОНОВЕ ЗВУЧИ]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Той отново се опитва
да вмъкнете всеки елемент

719
00:29:52,400 --> 00:29:52,900
в която той принадлежи.

720
00:29:52,900 --> 00:29:54,628
Това е балон подреди.

721
00:29:54,628 --> 00:30:10,097
>> [ТОНОВЕ ЗВУЧИ]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: И можете да сортирате на усещане
как сравнително малко работа, тя прави

723
00:30:13,630 --> 00:30:15,834
на всяка стъпка.

724
00:30:15,834 --> 00:30:20,470
Това е, което tediousness звучи.

725
00:30:20,470 --> 00:30:21,472
>> [ТОНОВЕ ЗВУЧИ]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Това е избор на вид,
където изберете елемент искаме от

727
00:30:25,222 --> 00:30:28,845
преживява отново и отново и отново
и да я постави в началото.

728
00:30:28,845 --> 00:30:37,674
>> [ТОНОВЕ ЗВУЧИ]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Това е сливат вид, които
наистина може да започнете да се чувствате.

730
00:30:43,970 --> 00:30:51,810
>> [ТОНОВЕ ЗВУЧИ]

731
00:30:51,810 --> 00:30:54,770
>> [СМЯХ]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: нещо, наречено GNOME
вид, които не сме разглеждали.

733
00:30:58,395 --> 00:31:13,630
>> [ТОНОВЕ ЗВУЧИ]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Така че нека да видя, сега,
разсеян, колкото се надяваме, са от

735
00:31:17,910 --> 00:31:21,110
музика, ако мога да се измъкне малко
малко математика тук.

736
00:31:21,110 --> 00:31:24,850
Така че има и четвърти начин, по който можем да
мисля за това, какво означава това

737
00:31:24,850 --> 00:31:29,210
функции, за да бъде по-бързо, отколкото тези,
че сме виждали преди.

738
00:31:29,210 --> 00:31:32,470
И ако идваш на курса от
математика фон, можете

739
00:31:32,470 --> 00:31:36,030
всъщност знаят, може би вече, че
може да шамар срок на тази техника -

740
00:31:36,030 --> 00:31:40,400
а именно рекурсия, функция
че по някакъв начин се призовава.

741
00:31:40,400 --> 00:31:44,780
>> И отново припомни, че подреди сливат
pseudocode е рекурсивно в смисъл,

742
00:31:44,780 --> 00:31:48,460
че една от стъпките сливат подреди на
беше да се обадя вид -

743
00:31:48,460 --> 00:31:49,740
т.е. себе си.

744
00:31:49,740 --> 00:31:52,480
Но слава Богу, защото ние продължавахме
призовава вид, или да се слеят вид,

745
00:31:52,480 --> 00:31:55,880
специално, по-малък и по-малки
и по-малък списък, ние в крайна сметка

746
00:31:55,880 --> 00:32:00,005
стигна дъното, благодарение на това, което ние ще се обадя
база случай, трудно кодирани случай, че

747
00:32:00,005 --> 00:32:04,270
каза, че ако в списъка е малък, по-малко от 2
В този случай, просто се върнете веднага.

748
00:32:04,270 --> 00:32:07,550
Ако ние не разполагаме с този специален случай
алгоритъм никога няма да намерят дъно,

749
00:32:07,550 --> 00:32:11,010
и вие наистина ще влязат в един
безкраен цикъл наистина завинаги.

750
00:32:11,010 --> 00:32:14,330
>> Но да предположим, че искаме да сложи сега
някои номера на този, отново, като се използва п

751
00:32:14,330 --> 00:32:15,660
като размера на входа.

752
00:32:15,660 --> 00:32:18,680
И аз исках да ви попитам, какво е
общото време участва в

753
00:32:18,680 --> 00:32:19,800
работи сливат вид?

754
00:32:19,800 --> 00:32:22,960
Или по-общо, това, което е
стойността на това във времето?

755
00:32:22,960 --> 00:32:24,730
>> Ами това е доста лесно да се измери това.

756
00:32:24,730 --> 00:32:29,010
Ако п е по-малко от 2, времето, необходимо
в сортирането на н елементи,

757
00:32:29,010 --> 00:32:30,480
където п е 2, е 0.

758
00:32:30,480 --> 00:32:31,410
Защото ние просто се върнете.

759
00:32:31,410 --> 00:32:32,510
Не е работа да се свърши.

760
00:32:32,510 --> 00:32:35,660
Сега може би, може би това е една стъпка или две
стъпки, за да разбера размера на

761
00:32:35,660 --> 00:32:38,420
работи, но това е достатъчно близо до 0, че
Аз съм просто ще кажа, няма такава работа

762
00:32:38,420 --> 00:32:40,940
изисква, ако списъкът е толкова малка,
да бъде безинтересно.

763
00:32:40,940 --> 00:32:42,580
>> Но този случай е интересен.

764
00:32:42,580 --> 00:32:47,320
The рекурсивни случай е клон на
на pseudocode че каза друго, нещо

765
00:32:47,320 --> 00:32:52,000
лявата половина, сортирате правото
половина, слее двете половини.

766
00:32:52,000 --> 00:32:55,530
Сега защо този израз
представляват тази сметка?

767
00:32:55,530 --> 00:32:58,690
Е, T на п просто означава
време, за да сортирате н елементи.

768
00:32:58,690 --> 00:33:03,070
И след това в дясната страна на
знак за равенство там, T п разделени

769
00:33:03,070 --> 00:33:06,600
с 2 се отнася за цената на какво?

770
00:33:06,600 --> 00:33:07,570
Сортиране лявата половина.

771
00:33:07,570 --> 00:33:10,990
Другият T п разделена на 2 е
предполага, че се отнасят до разходи за

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

773
00:33:12,390 --> 00:33:14,590
>> И тогава п плюс?

774
00:33:14,590 --> 00:33:15,420
Дали сливане.

775
00:33:15,420 --> 00:33:19,120
Защото, ако имате два списъка, единият от
размер н над 2 или подобен на размера н

776
00:33:19,120 --> 00:33:22,580
над 2, трябва да се докосват по същество
всеки от тези елементи, също като Rob

777
00:33:22,580 --> 00:33:24,990
докосна всяка от чашите, а само
както отбелязахме по всяка от

778
00:33:24,990 --> 00:33:26,310
доброволци на сцената.

779
00:33:26,310 --> 00:33:28,790
Така че п е за сметка на сливане.

780
00:33:28,790 --> 00:33:31,780
>> Сега за съжаление, тази формула
е също така да се рекурсивно.

781
00:33:31,780 --> 00:33:36,390
Така че, ако зададе въпроса, ако п е, да речем,
16, ако има 16 души на сцената

782
00:33:36,390 --> 00:33:40,670
или 16 чаши във видеото, колко общо
стъпки отнема да ги сортирате

783
00:33:40,670 --> 00:33:41,550
с вид сливане?

784
00:33:41,550 --> 00:33:45,790
То всъщност не е очевиден отговор,
защото сега ще трябва да се справи с

785
00:33:45,790 --> 00:33:48,500
рекурсивно отговори на тази формула.

786
00:33:48,500 --> 00:33:51,190
>> Но това е ОК, защото нека да предложи
което правим следното.

787
00:33:51,190 --> 00:33:56,670
В момента участват 16 души, за да сортирате или
16 чаши ще бъдат представени

788
00:33:56,670 --> 00:33:58,020
обикновено като Т от 16.

789
00:33:58,020 --> 00:34:01,400
Но това се равнява, според нашите
предишна формула, 2 пъти количеството

790
00:34:01,400 --> 00:34:04,780
на времето, необходимо, за да сортирате
8 чаши плюс 16.

791
00:34:04,780 --> 00:34:08,590
И отново, плюс 16 е времето да се слеят,
и два пъти по-T на 8 е

792
00:34:08,590 --> 00:34:10,790
време, за да сортирате лявата половина и дясната половина.

793
00:34:10,790 --> 00:34:11,989
>> Но пак, това не е достатъчно.

794
00:34:11,989 --> 00:34:13,210
Трябва да се потопите още по-дълбоко.

795
00:34:13,210 --> 00:34:16,409
Това означава, че трябва да отговорим на
въпрос, какво е Т на 8?

796
00:34:16,409 --> 00:34:19,610
Е T на 8 е само на 2
T пъти на 4 плюс 8.

797
00:34:19,610 --> 00:34:20,520
Е, това, което е на 4 T?

798
00:34:20,520 --> 00:34:23,780
T на 4 е само на два пъти T от 2 плюс 4.

799
00:34:23,780 --> 00:34:25,489
Е, какво е T на две?

800
00:34:25,489 --> 00:34:29,030
T на 2 е само на два пъти T на 1 плюс 2.

801
00:34:29,030 --> 00:34:31,940
>> И пак, ние сме вид се
остана в този цикъл.

802
00:34:31,940 --> 00:34:34,790
Но това е на път да удари, че
така наречената база случай.

803
00:34:34,790 --> 00:34:37,310
Защото това, което е на T 1, се твърди?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Така че сега най-накрая можем да работим назад.

806
00:34:39,730 --> 00:34:44,290
>> Ако T на 1 е 0, сега мога да се върна с още един
ред в този човек тук, и мога да

807
00:34:44,290 --> 00:34:46,330
включете 0 за T на 1.

808
00:34:46,330 --> 00:34:51,770
Така че това означава, че то се равнява на два пъти нула,
иначе известни като 0, плюс 2.

809
00:34:51,770 --> 00:34:53,739
И така, че целият израз е 2.

810
00:34:53,739 --> 00:34:58,740
>> Сега, ако съм на T на две, чийто отговор
е 2, го включете в средната линия, T

811
00:34:58,740 --> 00:35:02,740
на 4, че ми дава 2 пъти
2 плюс 4, така че 8.

812
00:35:02,740 --> 00:35:07,080
Ако след това включете в 8 с предходната
ред, че ми дава 2 пъти 8, 16.

813
00:35:07,080 --> 00:35:12,470
И ако след това продължи, че с
24, добавяйки в 16, ние най-накрая се получи

814
00:35:12,470 --> 00:35:13,820
стойност на 64.

815
00:35:13,820 --> 00:35:18,480
>> Сега, само по себе си вид говори
нищо означението М, на

816
00:35:18,480 --> 00:35:20,700
голям О, омега, че сме
говорим за.

817
00:35:20,700 --> 00:35:24,890
Но се оказва, че 64 е наистина
16, размерът на входа,

818
00:35:24,890 --> 00:35:27,110
влезте база 2 от 16.

819
00:35:27,110 --> 00:35:30,200
И ако това е малко непознат, просто
мисля обратно, и то ще се върне

820
00:35:30,200 --> 00:35:30,700
да в крайна сметка.

821
00:35:30,700 --> 00:35:33,775
Ако това е регистър на база 2, това е като две
издигнат до това, което ви дава 16?

822
00:35:33,775 --> 00:35:36,380
О, това е 4, така че е 16 пъти по четири.

823
00:35:36,380 --> 00:35:39,380
>> И пак, това не е голяма работа, ако това
е нещо като неясен спомен сега.

824
00:35:39,380 --> 00:35:43,720
Но за сега, да вземе на вярата
че 16 дневник 16 е 64.

825
00:35:43,720 --> 00:35:46,590
И така, наистина, с този прост здрав разум
проверите, като потвърдим -

826
00:35:46,590 --> 00:35:48,250
но не се оказа официално -

827
00:35:48,250 --> 00:35:52,800
че времето за работа на обединяването
Сортът е наистина N влезте п.

828
00:35:52,800 --> 00:35:53,790
>> Така че не е зле.

829
00:35:53,790 --> 00:35:57,260
Определено е по-добре от
алгоритми, които сме виждали до този момент, и

830
00:35:57,260 --> 00:36:00,710
това е, защото сме ливъридж, един,
техника, наречена рекурсия.

831
00:36:00,710 --> 00:36:03,880
Но по-интересно от това, че
идеята за разделяне и завладяване.

832
00:36:03,880 --> 00:36:07,460
Отново, наистина седмици 0 неща, които
дори и сега се повтаря в

833
00:36:07,460 --> 00:36:08,740
по-убедителен начин.

834
00:36:08,740 --> 00:36:11,750
>> Сега забавно малко упражнения, ако сте
никога не е правил това - и най-вероятно

835
00:36:11,750 --> 00:36:14,660
няма да има, защото нещо нормално
хора не мислят за това.

836
00:36:14,660 --> 00:36:20,650
Но ако отидете на google.com и ако
Аз искам да науча нещо за

837
00:36:20,650 --> 00:36:22,356
рекурсия, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [СМЯХ]

840
00:36:29,058 --> 00:36:32,030
[Смях]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad шега бавно разпространение.

842
00:36:33,385 --> 00:36:34,450
[СМЯХ]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Само в случай, че е там.

844
00:36:36,970 --> 00:36:38,710
Аз не пише правилно,
и там е шега.

845
00:36:38,710 --> 00:36:40,810
Добре.

846
00:36:40,810 --> 00:36:42,950
Обяснете го на хората до вас, ако
това не е съвсем кликнали, просто все още.

847
00:36:42,950 --> 00:36:47,650
Но рекурсия, по-общо, се отнася
в процеса на функции за извикване

848
00:36:47,650 --> 00:36:51,430
себе си, или по-общо, се раздели
Проблемът в нещо, което може да бъде

849
00:36:51,430 --> 00:36:56,220
решен парче чрез решаване на идентични
представителни проблеми.

850
00:36:56,220 --> 00:36:58,400
>> Е, нека смяна на предавките
само за миг.

851
00:36:58,400 --> 00:37:00,840
Ние обичаме да приключи на някои cliffhangers,
така че нека започнем да настроите

852
00:37:00,840 --> 00:37:05,870
на етапа, в продължение на няколко минути,
по една много проста идея -

853
00:37:05,870 --> 00:37:07,620
че на смяна на два елемента, нали?

854
00:37:07,620 --> 00:37:10,040
Всички тези алгоритми, ние сме били
говорим за последните няколко

855
00:37:10,040 --> 00:37:12,420
Лекциите включват някои
вид на дискове.

856
00:37:12,420 --> 00:37:14,630
Днес се визуализират чрез повдигайки
нагоре от столовете и

857
00:37:14,630 --> 00:37:18,570
разхождате, но в кода, бихме
просто да е елемент от един масив

858
00:37:18,570 --> 00:37:20,370
и цоп го на друг.

859
00:37:20,370 --> 00:37:21,880
>> И как ще го направим?

860
00:37:21,880 --> 00:37:24,850
Е, нека да вървим напред и пишат
бърза програма тук.

861
00:37:24,850 --> 00:37:31,600
Аз ще отида напред и да направим
това като следното.

862
00:37:31,600 --> 00:37:33,910
Нека наречем това -

863
00:37:33,910 --> 00:37:38,070
какво искаме да се обадя на този?

864
00:37:38,070 --> 00:37:38,650
>> Всъщност, не.

865
00:37:38,650 --> 00:37:39,420
Нека назад.

866
00:37:39,420 --> 00:37:41,220
Аз не искам да правя това
Катерачът още.

867
00:37:41,220 --> 00:37:42,270
Тя ще развали забавно.

868
00:37:42,270 --> 00:37:43,600
Да го направим вместо това.

869
00:37:43,600 --> 00:37:47,430
>> Да предположим, че искам да напиша малко
програма и че сега обхваща тази

870
00:37:47,430 --> 00:37:48,700
Идеята на рекурсия.

871
00:37:48,700 --> 00:37:50,370
Някак си имам избързвам там.

872
00:37:50,370 --> 00:37:51,420
Отивам да направите следното.

873
00:37:51,420 --> 00:38:00,220
>> Първо, един бърз включва стандартен io.h,
както и включват на cs50.h.

874
00:38:00,220 --> 00:38:03,200
И тогава аз ще вървим напред
и декларира Int основната невалидни

875
00:38:03,200 --> 00:38:04,360
по обичайния начин.

876
00:38:04,360 --> 00:38:07,920
Разбрах, че съм сполучлив термин на файл, така че
нека само да се добави. в разширяването тук, така че

877
00:38:07,920 --> 00:38:09,510
че можем да го компилирате правилно.

878
00:38:09,510 --> 00:38:10,970
Започнете тази функция изключване.

879
00:38:10,970 --> 00:38:13,290
>> И функцията искам да пиша, доста
просто, е тази, която изисква от

880
00:38:13,290 --> 00:38:16,210
ръководство за броя и след това добавя
всички числа, между които

881
00:38:16,210 --> 00:38:19,920
номер и, да речем, 0.

882
00:38:19,920 --> 00:38:22,510
Така че първо аз ще вървим напред
и декларира вътр п.

883
00:38:22,510 --> 00:38:24,760
След това копирате някакъв код, че
сме използвали за известно време.

884
00:38:24,760 --> 00:38:26,660
Докато нещо не е вярно.

885
00:38:26,660 --> 00:38:28,000
Аз ще се върна на това след малко.

886
00:38:28,000 --> 00:38:29,010
>> Какво искате да направите?

887
00:38:29,010 --> 00:38:33,460
Искам да кажа, ФОРМАТ положителна
цяло число, моля.

888
00:38:33,460 --> 00:38:36,130
И тогава аз ще
казват п получава получите вътр.

889
00:38:36,130 --> 00:38:38,800
Така че отново, някои стереотипния код
че сме използвали преди.

890
00:38:38,800 --> 00:38:40,810
И аз ще го направя
а п е по-малко от 1.

891
00:38:40,810 --> 00:38:44,120
Така че това ще гарантира, че на потребителя
ми дава положително число.

892
00:38:44,120 --> 00:38:45,490
>> И сега ще направя следното.

893
00:38:45,490 --> 00:38:51,020
Искам да добавите до всички номера
между 1 и и п, или 0 и п,

894
00:38:51,020 --> 00:38:52,570
което е същото, за да получите общата сума.

895
00:38:52,570 --> 00:38:55,100
Така че големият символ сигма
че може да изземат.

896
00:38:55,100 --> 00:38:59,050
Така че аз ще направя това, като първо призвание
функция, наречена Sigma,

897
00:38:59,050 --> 00:39:06,030
минаваща го в N, а след това аз ще
казват ФОРМАТ, отговорът е точно там.

898
00:39:06,030 --> 00:39:08,180
>> Така че в кратко, да получа и
INT от потребителя.

899
00:39:08,180 --> 00:39:09,280
Аз се гарантира, че е положителна.

900
00:39:09,280 --> 00:39:12,700
Декларирам, променлива наречена отговор на
тип Int и се съхранява в него на връщане

901
00:39:12,700 --> 00:39:15,610
стойност на сигма, преминавайки в п като вход.

902
00:39:15,610 --> 00:39:17,060
И тогава аз разпечатате този отговор.

903
00:39:17,060 --> 00:39:19,550
>> За съжаление, въпреки че сигма звучи
като нещо, което може да бъде в

904
00:39:19,550 --> 00:39:24,040
на math.h файл, декларацията си,
това всъщност не е така.

905
00:39:24,040 --> 00:39:24,690
Така че това е ОК.

906
00:39:24,690 --> 00:39:26,170
I може да реализира това сам.

907
00:39:26,170 --> 00:39:29,160
Отивам да се приложи нарича функция
сигма, и това ще отнеме

908
00:39:29,160 --> 00:39:29,900
параметър -

909
00:39:29,900 --> 00:39:32,100
нека просто го наречем m, само
така че е по-различно.

910
00:39:32,100 --> 00:39:35,910
И след това тук, аз ще кажа,
Е, ако М е по-малко от 1 - това е

911
00:39:35,910 --> 00:39:38,180
много безинтересно програма.

912
00:39:38,180 --> 00:39:41,700
Така че аз ще отида напред и
незабавно да върне 0.

913
00:39:41,700 --> 00:39:45,920
Просто няма смисъл да добавите до всички
на числа между 1 и М, ако т

914
00:39:45,920 --> 00:39:48,470
е самата 0 или отрицателни.

915
00:39:48,470 --> 00:39:50,900
>> И тогава аз ще вървим напред
и направите това много итеративно.

916
00:39:50,900 --> 00:39:53,090
Аз ще направя този вид на старата школа,
и аз отивам да вървим напред

917
00:39:53,090 --> 00:39:57,150
и да кажа, че аз ще
обяви сумата да бъде 0.

918
00:39:57,150 --> 00:39:59,630
Тогава ще се наложи
за линия на Int -

919
00:39:59,630 --> 00:40:02,820
и ме остави да го направя и нашето
разпространение на кодове, така че имате копие

920
00:40:02,820 --> 00:40:07,500
у дома. Int I получава 1 на до
I е по-малко от или равно на m.

921
00:40:07,500 --> 00:40:09,430
Аз плюс плюс.

922
00:40:09,430 --> 00:40:11,430
И тогава вътре в този за линия -

923
00:40:11,430 --> 00:40:12,440
ние сме почти там -

924
00:40:12,440 --> 00:40:15,810
Сумата получава сума плюс 1.

925
00:40:15,810 --> 00:40:17,670
И тогава аз ще върне сумата.

926
00:40:17,670 --> 00:40:19,420
>> Така и направих това бързо,
съвсем естествено.

927
00:40:19,420 --> 00:40:22,775
Но отново, чиято основна функция е доста
ясно, на базата на код, ние сме

928
00:40:22,775 --> 00:40:23,190
дадени до този момент.

929
00:40:23,190 --> 00:40:25,610
Използва двойна линия, за да получите положителен
INT от потребителя.

930
00:40:25,610 --> 00:40:29,870
След това така, че средно за нова функция
наречена Sigma, като го нарече, отново, п.

931
00:40:29,870 --> 00:40:33,100
И аз се съхранява на върнатата стойност, отговорът
от черна кутия в момента

932
00:40:33,100 --> 00:40:35,460
известен като сигма, в променлива
наречен отговор.

933
00:40:35,460 --> 00:40:36,580
Тогава аз го отпечатате.

934
00:40:36,580 --> 00:40:39,090
>> Ако сега продължава историята,
как се сигма приложени?

935
00:40:39,090 --> 00:40:40,840
Аз предлагам да се прилага, както следва.

936
00:40:40,840 --> 00:40:43,560
Първо, малко за проверка на грешки
за да се уверите, че потребителят не е

937
00:40:43,560 --> 00:40:46,480
каша с мен и минаваща през
някои отрицателни или стойност 0.

938
00:40:46,480 --> 00:40:49,710
Тогава обяви нарича променлива
обобщение и това трябва да е 0.

939
00:40:49,710 --> 00:40:55,910
>> И сега започват да се движат от и равен
1 по целия път до и включително m,

940
00:40:55,910 --> 00:41:00,130
защото искам да се включи цялата
числа от едно до m включително.

941
00:41:00,130 --> 00:41:04,350
И вътре в този за линия, аз просто правя
Сумата получава каквото и да е сега, плюс

942
00:41:04,350 --> 00:41:08,900
стойността на I.

943
00:41:08,900 --> 00:41:10,370
Плюс стойността на I.

944
00:41:10,370 --> 00:41:14,090
>> Като настрана, ако не сте виждали това
преди, има някаква синтактична захар

945
00:41:14,090 --> 00:41:14,870
за тази линия.

946
00:41:14,870 --> 00:41:21,120
Мога да пренапише това като плюс и равни,
само за да си спестя няколко натискания на клавиши

947
00:41:21,120 --> 00:41:22,570
и да изглежда малко по-хладно.

948
00:41:22,570 --> 00:41:23,140
Но това е всичко.

949
00:41:23,140 --> 00:41:24,660
Това е функционално и също нещо.

950
00:41:24,660 --> 00:41:26,710
>> За съжаление, този код е
Няма да съставят все още.

951
00:41:26,710 --> 00:41:31,600
Ако аз тичам да сигма 0, как съм
Аз ще се развика?

952
00:41:31,600 --> 00:41:33,473
Какво ще да не харесваш?

953
00:41:33,473 --> 00:41:35,740
>> Публиката: [недоловим].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Да, не е декларирал
функцията на върха, нали?

955
00:41:37,800 --> 00:41:40,590
C е много глупаво, по това, че само
прави това, което му казвате да прави, и вие

956
00:41:40,590 --> 00:41:41,880
трябва да го направим в този ред.

957
00:41:41,880 --> 00:41:45,910
И така, ако аз хит Въведете тук, аз отивам да
получите предупреждение за сигма имплицитно

958
00:41:45,910 --> 00:41:46,860
декларация.

959
00:41:46,860 --> 00:41:48,120
>> О, не е проблем.

960
00:41:48,120 --> 00:41:50,370
I може да стигнат до върха, и мога да
казват, добре, чакай малко.

961
00:41:50,370 --> 00:41:54,240
Sigma е функция, която връща
едно цяло число и да го очаква

962
00:41:54,240 --> 00:41:56,620
Int като вход, точка и запетая.

963
00:41:56,620 --> 00:41:59,550
Или би могло да постави цялата функция
над основната, но като цяло, бих

964
00:41:59,550 --> 00:42:02,260
Препоръчваме срещу това, защото това е
хубаво винаги да има основна през тавана, така

965
00:42:02,260 --> 00:42:06,310
можете да се потопите в правото и да знае какво е
Програмата прави с четене основната първи.

966
00:42:06,310 --> 00:42:07,930
>> Така че сега нека да изчистите екрана.

967
00:42:07,930 --> 00:42:09,330
Римейк сигма 0.

968
00:42:09,330 --> 00:42:10,340
Всичко изглежда да се провери.

969
00:42:10,340 --> 00:42:11,970
Нека да тече сигма 0.

970
00:42:11,970 --> 00:42:12,770
Положителен наред.

971
00:42:12,770 --> 00:42:15,580
Аз ще го дам номера
3 да го прости.

972
00:42:15,580 --> 00:42:18,710
Така, че трябва да ми даде 3
плюс две плюс едно, така че 6.

973
00:42:18,710 --> 00:42:20,750
Въведете и наистина да получа 6.

974
00:42:20,750 --> 00:42:21,820
>> Мога да направя нещо по-голямо -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Точно както допирателната, аз ще направя
нещо нелепо като наистина голяма

977
00:42:27,690 --> 00:42:30,375
номер, О, това действително отработени изход -

978
00:42:30,375 --> 00:42:31,600
а, аз не мисля, че е прав.

979
00:42:31,600 --> 00:42:32,810
Нека да видим.

980
00:42:32,810 --> 00:42:34,060
Нека наистина се забъркваш с него.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Това е проблем.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Какво става?

985
00:42:44,970 --> 00:42:46,050
Кодът не е толкова зле.

986
00:42:46,050 --> 00:42:48,470
Тя все още е линейна.

987
00:42:48,470 --> 00:42:50,810
Свирене е добър ефект, все пак.

988
00:42:50,810 --> 00:42:52,060
Какво става?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Не съм сигурен дали съм го чувал.

991
00:42:55,620 --> 00:42:57,620
Така се оказва - и
това е като настрана.

992
00:42:57,620 --> 00:42:59,400
Това не е в основата на
Идеята на рекурсия.

993
00:42:59,400 --> 00:43:02,480
Оказва се, защото се опитвам да
представляват такъв голям брой, най-

994
00:43:02,480 --> 00:43:06,980
вероятно това е погрешно да се
от C като не положително число,

995
00:43:06,980 --> 00:43:09,980
но отрицателно число.

996
00:43:09,980 --> 00:43:12,690
>> Ние не сме говорили за това, но то
Оказва се, че са отрицателни числа

997
00:43:12,690 --> 00:43:14,210
в света в допълнение
до положителни числа.

998
00:43:14,210 --> 00:43:16,290
И начините, по които можете да
представлява отрицателно число

999
00:43:16,290 --> 00:43:19,530
по същество е, като използвате един
специален малко, за да показват,

1000
00:43:19,530 --> 00:43:20,400
положително върху отрицателни.

1001
00:43:20,400 --> 00:43:22,950
Това е малко по-сложно,
но това е основната идея.

1002
00:43:22,950 --> 00:43:26,740
>> Така че, за съжаление, ако C е объркващо един
на тези битове като всъщност означава,

1003
00:43:26,740 --> 00:43:30,790
О, това е отрицателно число, моята линия
тук, например, всъщност никога не е

1004
00:43:30,790 --> 00:43:31,740
ще се прекрати.

1005
00:43:31,740 --> 00:43:33,850
Така че, ако са били действително отпечатване нещо
отново и отново, ние ще

1006
00:43:33,850 --> 00:43:34,650
виж цяло много.

1007
00:43:34,650 --> 00:43:36,220
Но отново, това е освен точка.

1008
00:43:36,220 --> 00:43:38,590
Това е наистина само един вид
интелектуалното любопитство, че ще дойдем

1009
00:43:38,590 --> 00:43:39,550
обратно към евентуално.

1010
00:43:39,550 --> 00:43:43,400
Но за сега, това е правилно
изпълнението, ако приемем, че

1011
00:43:43,400 --> 00:43:45,970
потребителят ще осигури целочислени
които се побират в цели числа.

1012
00:43:45,970 --> 00:43:49,370
>> Но аз твърдя, че този код, честно казано,
може да се направи много по-просто.

1013
00:43:49,370 --> 00:43:54,060
Ако целта на ръка е да се предприемат редица
като m и добавете цялото количество

1014
00:43:54,060 --> 00:43:59,510
номера между него и един, или обратното
между 1 и, смея да твърдя

1015
00:43:59,510 --> 00:44:03,380
че мога да взема това идеята, че се слеят
подреди имаше, което беше като проблем

1016
00:44:03,380 --> 00:44:05,660
с този размер и разделянето на
в нещо по-малко.

1017
00:44:05,660 --> 00:44:09,875
Може би не половината, но по-малки, но
представителен същото.

1018
00:44:09,875 --> 00:44:12,130
Същата идея, но по-малък проблем.

1019
00:44:12,130 --> 00:44:15,470
>> Така че аз съм всъщност - да ме спаси този файл
с различен брой версия.

1020
00:44:15,470 --> 00:44:17,670
Ще се обадя тази версия
1 вместо 0.

1021
00:44:17,670 --> 00:44:20,790
И аз твърдя, че всъщност мога да
reimplement това в този вид

1022
00:44:20,790 --> 00:44:22,160
оказващ влияние начин.

1023
00:44:22,160 --> 00:44:23,710
>> Отивам да оставите част от него сам.

1024
00:44:23,710 --> 00:44:27,710
Аз ще кажа, ако m е по-малко
от или дори равни на 0 -

1025
00:44:27,710 --> 00:44:29,280
Аз съм просто ще бъде малко
по това време анален

1026
00:44:29,280 --> 00:44:30,520
с моята проверка за грешки -

1027
00:44:30,520 --> 00:44:33,190
Аз ще отида напред и да се върне 0.

1028
00:44:33,190 --> 00:44:34,490
Това е произволно.

1029
00:44:34,490 --> 00:44:37,500
Аз съм просто реши, ако потребителят
ми дава отрицателно число, аз съм

1030
00:44:37,500 --> 00:44:41,490
връща 0, и те е трябвало да прочетете
документацията по-отблизо.

1031
00:44:41,490 --> 00:44:42,170
>> Друго -

1032
00:44:42,170 --> 00:44:44,070
забележите това, което аз ще направя.

1033
00:44:44,070 --> 00:44:49,260
Друго аз отивам да се върне m плюс -

1034
00:44:49,260 --> 00:44:51,010
това, което е сигма на т?

1035
00:44:51,010 --> 00:44:56,710
Е, сигма на m плюс минус 1 m,
m плюс минус 2, плюс минус 3 m.

1036
00:44:56,710 --> 00:44:58,030
Аз не искам да пиша всичко това.

1037
00:44:58,030 --> 00:44:59,120
Защо не правя просто шута?

1038
00:44:59,120 --> 00:45:05,080
Рекурсивно се наричам с леко
по-малък проблем, точка и запетая,

1039
00:45:05,080 --> 00:45:06,840
и го наричат ​​на ден?

1040
00:45:06,840 --> 00:45:07,040
>> Така ли е?

1041
00:45:07,040 --> 00:45:10,980
Сега тук също може да се чувстват или тревожи
че това е един безкраен цикъл, че съм

1042
00:45:10,980 --> 00:45:15,450
предизвикване, което аз съм за прилагане
сигма като се обадите на сигма.

1043
00:45:15,450 --> 00:45:20,342
Но това е подсъдно, защото
мислех напред добавена кои редове?

1044
00:45:20,342 --> 00:45:22,600
>> Публиката: [недоловим].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: от 23 до 26, които
е ми ако състояние.

1046
00:45:25,430 --> 00:45:28,390
Защото това, което е хубаво за
изваждане тук, защото аз държа

1047
00:45:28,390 --> 00:45:31,180
раздават сигма-малки проблеми, по-малки
проблеми, по-малък - това не е

1048
00:45:31,180 --> 00:45:31,870
половината от размера.

1049
00:45:31,870 --> 00:45:34,380
Това е само една малка стъпка бебе,
но това е ОК.

1050
00:45:34,380 --> 00:45:38,050
Защото в крайна сметка, ние ще работим
нашия път до 1 или 0.

1051
00:45:38,050 --> 00:45:41,630
И след като ударихме 0, сигма е не
ще се обади повече.

1052
00:45:41,630 --> 00:45:43,590
Ще се върнете незабавно 0.

1053
00:45:43,590 --> 00:45:47,960
>> Така че ефектът, ако нещо вятър тази
в ума си, е да се добави m плюс

1054
00:45:47,960 --> 00:45:52,740
m минус 1, плюс m минус 2, плюс минус m
3, плюс точка, точка, точка, m минус

1055
00:45:52,740 --> 00:45:57,820
m, в крайна сметка ти дава 0, и
Ефектът е в крайна сметка да се добавят всички

1056
00:45:57,820 --> 00:45:59,070
тези неща заедно.

1057
00:45:59,070 --> 00:46:02,380
Така че ние не трябва, с рекурсия,
решен проблемът, че ние

1058
00:46:02,380 --> 00:46:03,470
не може да реши преди.

1059
00:46:03,470 --> 00:46:06,840
В действителност, версия 0 на това, и всяка
проблем към днешна дата, е решими

1060
00:46:06,840 --> 00:46:09,980
само с помощта на вериги или по време на
вериги или подобни конструкции.

1061
00:46:09,980 --> 00:46:13,150
>> Но рекурсия, смея да кажа, ни дава
различен начин на мислене за

1062
00:46:13,150 --> 00:46:17,010
проблеми, при което, ако можем да вземе
проблем, тя се разделя от нещо

1063
00:46:17,010 --> 00:46:22,340
малко голям в нещо малко по-
по-малки, аз твърдя, че ние можем да го решим

1064
00:46:22,340 --> 00:46:26,040
може би малко по-елегантно от гледна точка
на проекта, с по-малко код,

1065
00:46:26,040 --> 00:46:30,980
и може би дори и решаване на проблеми, които биха
бъде по-трудно, тъй като ние в крайна сметка ще

1066
00:46:30,980 --> 00:46:33,280
виж, решаване на чисто итеративно.

1067
00:46:33,280 --> 00:46:35,980
>> Но Катерачът, че го направих
искат да ни оставят на това беше.

1068
00:46:35,980 --> 00:46:40,720
Нека да вървим напред и да се отворят
създаване на файл от -

1069
00:46:40,720 --> 00:46:44,300
Всъщност, нека отида и
направите това много бързо.

1070
00:46:44,300 --> 00:46:46,875
Нека да вървим напред и да предложи
следното.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Сред днешния закон е този файл тук.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Този тук, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Така че това е една глупава програма, която
I шибна, която претендира да направя

1076
00:47:06,260 --> 00:47:06,940
следното.

1077
00:47:06,940 --> 00:47:10,140
В главната, тя първо декларира
Int нарича х и е възложила

1078
00:47:10,140 --> 00:47:11,100
стойността на 1.

1079
00:47:11,100 --> 00:47:13,520
След това го декларира Int Y и
възлага това на стойност 2.

1080
00:47:13,520 --> 00:47:15,310
Тогава той печата какво х и у е.

1081
00:47:15,310 --> 00:47:17,781
Тогава казва: смяна, точка точка точка.

1082
00:47:17,781 --> 00:47:21,670
>> След това той твърди, че се обажда функция
наречен суап, минаваща през X и

1083
00:47:21,670 --> 00:47:24,290
Y, идеята за което е, че се надяваме
х и у ще се върне

1084
00:47:24,290 --> 00:47:25,620
различни, точно обратното.

1085
00:47:25,620 --> 00:47:27,110
След това го твърдят разменят!

1086
00:47:27,110 --> 00:47:28,420
с удивителен знак.

1087
00:47:28,420 --> 00:47:30,190
След това го отпечатва х и у.

1088
00:47:30,190 --> 00:47:33,480
>> Но се оказва, че това много
проста демонстрация надолу

1089
00:47:33,480 --> 00:47:35,570
тук е всъщност бъги.

1090
00:47:35,570 --> 00:47:38,870
Въпреки, че аз съм за обявяване на временна
променлива и временно удар в

1091
00:47:38,870 --> 00:47:42,010
това, тогава аз съм пренасочване
а стойността на б -

1092
00:47:42,010 --> 00:47:45,080
който се чувства разумно, защото съм
спаси копие на в темп.

1093
00:47:45,080 --> 00:47:48,410
Тогава актуализира б на равно
каквото е в темп.

1094
00:47:48,410 --> 00:47:51,610
Този вид на черупката игра на преместване на
в Б и В, а с помощта на тази

1095
00:47:51,610 --> 00:47:54,360
средна температура се чувства човек на име
напълно разумна.

1096
00:47:54,360 --> 00:47:57,270
>> Но аз твърдя, че когато пускам това
код, като ще правим сега -

1097
00:47:57,270 --> 00:47:59,490
нека да вървим напред и да го добавите тук.

1098
00:47:59,490 --> 00:48:01,995
Ще се обадя на този noswap.c.

1099
00:48:01,995 --> 00:48:05,630
И както подсказва и името, това не е
Ще бъде правилната програма.

1100
00:48:05,630 --> 00:48:09,460
Направи noswap. / Не суап.

1101
00:48:09,460 --> 00:48:12,110
х е 1, у е 2, размяна, разменят.

1102
00:48:12,110 --> 00:48:14,220
х е 1, у е 2.

1103
00:48:14,220 --> 00:48:16,920
Това е фундаментално погрешно, дори
че това изглежда перфектно

1104
00:48:16,920 --> 00:48:17,730
разумен за мен.

1105
00:48:17,730 --> 00:48:21,330
И има причина, но не сме
ще разкрие причината, просто все още.

1106
00:48:21,330 --> 00:48:24,610
>> За сега втората Катерачът исках
да ви оставя с е този, на

1107
00:48:24,610 --> 00:48:27,120
обявяването на видове за купон кодове.

1108
00:48:27,120 --> 00:48:31,590
Нашата иновациите с късни дни тази година
предизвика нетривиален брой

1109
00:48:31,590 --> 00:48:33,830
на въпроса, който беше
не нашето намерение.

1110
00:48:33,830 --> 00:48:36,590
Намерението на тези купони,
при което, ако го направите част от проблема

1111
00:48:36,590 --> 00:48:39,850
определени по-рано, като по този начин става един допълнителен ден,
Беше наистина да ви помогна да помогне

1112
00:48:39,850 --> 00:48:42,420
се започне рано, сортиране
на стимулите от вас.

1113
00:48:42,420 --> 00:48:44,880
Ни помага да разпространявате натоварване в
работно време по-добре, така че

1114
00:48:44,880 --> 00:48:45,740
Това е нещо печеливша.

1115
00:48:45,740 --> 00:48:48,860
>> За съжаление, мисля, че моите инструкции
не са били, към днешна дата, много ясно, така че

1116
00:48:48,860 --> 00:48:52,230
Върнах се този уикенд и се актуализира
спец. в по-големи, по-смели текст

1117
00:48:52,230 --> 00:48:53,600
обясни куршуми като тези.

1118
00:48:53,600 --> 00:48:56,900
И за да го кажа по-публично, чрез
подразбиране, проблемни групи се дължат четвъртък

1119
00:48:56,900 --> 00:48:58,400
по обед на учебната програма.

1120
00:48:58,400 --> 00:49:02,030
Ако започне рано, за довършителни работи част от
на проблема, определен от сряда в 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, частта, която се отнася за купон
код, идеята е, че можете да удължите

1122
00:49:05,170 --> 00:49:07,710
си крайният срок за
P зададете до петък.

1123
00:49:07,710 --> 00:49:10,890
Това е, отхапа малка част от P
настроите спрямо това, което обикновено е

1124
00:49:10,890 --> 00:49:13,200
по-голям проблем, и да купите
себе си един допълнителен ден.

1125
00:49:13,200 --> 00:49:15,190
Отново, това стане ли мисли за
проблема набор, получава възможност да

1126
00:49:15,190 --> 00:49:16,380
работно време по-рано.

1127
00:49:16,380 --> 00:49:20,670
Но проблемът купон кодекс е все още
длъжни, дори и ако не го представя.

1128
00:49:20,670 --> 00:49:23,340
>> Но по-убедително е това.

1129
00:49:23,340 --> 00:49:26,520
(Настрана) и тези хора напускане
рано са ще съжаляваш.

1130
00:49:26,520 --> 00:49:28,620
Както са хората на балкона.

1131
00:49:28,620 --> 00:49:32,510
Извиняваме предварително на хора на
балкона поради причини, които ще бъдат

1132
00:49:32,510 --> 00:49:33,920
ясно в един момент.

1133
00:49:33,920 --> 00:49:37,050
>> Така че ние сме щастливи, че имаме една от
Бивши CS50 си събратя главата преподаване в

1134
00:49:37,050 --> 00:49:39,302
една компания, наречена dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Те са много щедро дарява
купон код тук за тази много място,

1136
00:49:45,500 --> 00:49:48,180
което е нагоре от
обичайните 2 гигабайта.

1137
00:49:48,180 --> 00:49:51,740
Така си и мислех, че ще направим по този
последна бележка е да направи малко на награди,

1138
00:49:51,740 --> 00:49:55,380
при което в един момент, ние ще разкрие
победителят и кой има купон

1139
00:49:55,380 --> 00:49:57,980
код, който можете да преминете към тяхното
сайт, го въведете, и готово, може да получи

1140
00:49:57,980 --> 00:50:01,370
много повече Dropbox пространство за Вашия
уреда и за личните си файлове.

1141
00:50:01,370 --> 00:50:05,690
>> И първото, които биха искали да участват
в тази рисунка?

1142
00:50:05,690 --> 00:50:09,630
Добре, сега, че го прави още по-забавно.

1143
00:50:09,630 --> 00:50:14,010
Човекът, който получава тази 25-гигабайтов
купон код - което е далеч

1144
00:50:14,010 --> 00:50:16,150
по-наложителна от края на
ден сега, може би -

1145
00:50:16,150 --> 00:50:20,620
е този, който е седнал на върха на
седалката, под който има

1146
00:50:20,620 --> 00:50:21,620
че купон код.

1147
00:50:21,620 --> 00:50:23,480
Сега можете да погледнете под
си седалката.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO PLAYBACK]

1150
00:50:29,680 --> 00:50:31,620
>> -Едно, две, три.

1151
00:50:31,620 --> 00:50:35,015
>> [Крещи]

1152
00:50:35,015 --> 00:50:35,985
>> -Можете да получите колата!

1153
00:50:35,985 --> 00:50:36,670
Можете да получите колата!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Ще видим
ти в сряда.

1155
00:50:37,970 --> 00:50:38,904
>> -Можете да получите колата!

1156
00:50:38,904 --> 00:50:39,371
Можете да получите колата!

1157
00:50:39,371 --> 00:50:40,305
Можете да получите колата!

1158
00:50:40,305 --> 00:50:41,706
Можете да получите колата!

1159
00:50:41,706 --> 00:50:43,107
Можете да получите колата!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: Балкон хора, хайде
тук на фронта,

1161
00:50:45,530 --> 00:50:46,866
където имаме екстри.

1162
00:50:46,866 --> 00:50:50,282
>> -Всеки получава една кола!

1163
00:50:50,282 --> 00:50:52,234
Всеки получава една кола!

1164
00:50:52,234 --> 00:50:52,722
>> [END възпроизвеждане на видео]

1165
00:50:52,722 --> 00:50:54,590
>> Разказвач: На следващото CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: О, Боже мой, Боже, Боже, Боже
Боже, Боже, Боже, Боже, Боже, Боже -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE ПИЕСИ]