1
00:00:00,000 --> 00:00:11,904
>> [Мусиц плаиинг]

2
00:00:11,904 --> 00:00:12,910
>> ПРОФЕСОР: У реду.

3
00:00:12,910 --> 00:00:16,730
То је ЦС50 а ово је
крај недеље три.

4
00:00:16,730 --> 00:00:20,230
Дакле, ми смо овде данас, не Сандерс
Позориште, уместо у Веиднер библиотеци.

5
00:00:20,230 --> 00:00:23,170
Унутар чији је студио
познат као Хаусер Студио,

6
00:00:23,170 --> 00:00:28,310
или ћемо рећи Студио Х, или ће
ми говоре-- Ако сте уживали у онај виц,

7
00:00:28,310 --> 00:00:30,540
то је у ствари од
школски друг, Марко, на мрежи,

8
00:00:30,540 --> 00:00:32,420
који је предложио толико преко Твиттер.

9
00:00:32,420 --> 00:00:34,270
Шта је сад супер о
што сам овде у студију

10
00:00:34,270 --> 00:00:38,410
је да сам окружен ове зелене
зидови, зелени екран или Цхромакеи,

11
00:00:38,410 --> 00:00:43,290
да тако кажем, што значи да је ЦС50
продукцијски тим, без знања за мене

12
00:00:43,290 --> 00:00:47,380
сада би могло бити стављање
ме највише било где у свету,

13
00:00:47,380 --> 00:00:48,660
за боље или горе.

14
00:00:48,660 --> 00:00:51,800
>> Шта сад лежи испред, проблема сет
два је у вашим рукама за ову недељу,

15
00:00:51,800 --> 00:00:53,830
али са проблемом сет
три ове недеље,

16
00:00:53,830 --> 00:00:56,600
бићете изазов са
тзв игра 15,

17
00:00:56,600 --> 00:00:58,960
стара странка услугу која
можда се сећате пријема

18
00:00:58,960 --> 00:01:02,030
као дете које има гомилу
бројева који могу да клизе горе, доле,

19
00:01:02,030 --> 00:01:05,790
лево и десно, и ту је једна празнина
у оквиру слагалице, у којој сте

20
00:01:05,790 --> 00:01:07,840
заправо може клизи те делове слагалице.

21
00:01:07,840 --> 00:01:11,150
На крају сте добили ово
пуззле у неком полу случајним редоследом,

22
00:01:11,150 --> 00:01:12,940
а циљ је да се
Сорт Ит, од врха до дна,

23
00:01:12,940 --> 00:01:16,310
лева на десно, од једног
скроз горе до 15.

24
00:01:16,310 --> 00:01:19,360
>> Нажалост, имплементација
имаћете при руци

25
00:01:19,360 --> 00:01:21,590
ће бити софтвер
заснована, не физички.

26
00:01:21,590 --> 00:01:25,280
Стварно ћеш морати написати
Код са којим студент или корисник може

27
00:01:25,280 --> 00:01:26,760
играју игру 15.

28
00:01:26,760 --> 00:01:29,030
И у ствари, у хакер
издање игре 15,

29
00:01:29,030 --> 00:01:32,155
ћете бити изазов за имплементацију,
не само свирање ове старе школе

30
00:01:32,155 --> 00:01:35,010
игра, већ решавање
о томе, спровођење Год Моде,

31
00:01:35,010 --> 00:01:38,280
да тако кажем, који заправо
решава слагалицу за човека,

32
00:01:38,280 --> 00:01:41,080
пружајући им хинт,
после наговештаја, после наговештаја.

33
00:01:41,080 --> 00:01:42,280
Дакле, више о тој следеће недеље.

34
00:01:42,280 --> 00:01:43,720
Али то је оно што је пред нама.

35
00:01:43,720 --> 00:01:47,610
>> За сада се сетим да је раније ове недеље
имали смо Цлиффхангер, ако хоћете,

36
00:01:47,610 --> 00:01:52,560
при чему је најбољи смо радили за сортирање
Мудар је био горња граница Биг О од н

37
00:01:52,560 --> 00:01:53,210
квадрат.

38
00:01:53,210 --> 00:01:56,520
Другим речима, балон врста,
Избор врста, уметање врста,

39
00:01:56,520 --> 00:01:59,120
сви они, а различити
у њиховој реализацији,

40
00:01:59,120 --> 00:02:03,480
пренета у једном н на квадрат руннинг
Време у врло најгорем случају.

41
00:02:03,480 --> 00:02:06,010
И генерално претпостављамо да
веома најгори случај за сортирање

42
00:02:06,010 --> 00:02:08,814
је онај који ти улази
потпуно уназад.

43
00:02:08,814 --> 00:02:11,980
И заиста, то је прилично неколико корака
да спроведе сваки од тих алгоритама.

44
00:02:11,980 --> 00:02:15,110
>> Сада на самом крају класе
опозив, упоредили смо буббле врсту

45
00:02:15,110 --> 00:02:19,390
против селекције врсте против једног другог
да смо звали стапања врсту у то време,

46
00:02:19,390 --> 00:02:22,120
и ја предлажем да се узима
Предност лекције из недеље

47
00:02:22,120 --> 00:02:24,060
нула, завади па владај.

48
00:02:24,060 --> 00:02:28,810
И некако постизање неке врсте
логаритамске времена рада на крају,

49
00:02:28,810 --> 00:02:31,024
уместо нечега
То је чисто квадратна.

50
00:02:31,024 --> 00:02:33,440
И није баш логаритамска,
то је мало више од тога.

51
00:02:33,440 --> 00:02:36,520
Али, ако се сећате из класе,
било је много, много брже.

52
00:02:36,520 --> 00:02:38,210
Хајде да погледамо где смо стали.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Буббле сорт односу на избор
Сортирај у односу на стапања врсте.

55
00:02:45,370 --> 00:02:47,700
Сада су сви јуримо у
теорију, у исто време.

56
00:02:47,700 --> 00:02:50,510
Процесор ради на истом брзином.

57
00:02:50,510 --> 00:02:54,990
Али можете осетити како ова досадна
врло брзо ће постати,

58
00:02:54,990 --> 00:02:58,790
и колико брзо, када смо убризгати
мало недеље Зеро алгоритама,

59
00:02:58,790 --> 00:03:00,080
можемо убрзати ствари.

60
00:03:00,080 --> 00:03:01,630
>> Тако ознака врста изгледа невероватно.

61
00:03:01,630 --> 00:03:05,220
Како можемо да искористе, како
за сортирање бројева брже.

62
00:03:05,220 --> 00:03:07,140
Па хајде да размислим
до састојак који смо

63
00:03:07,140 --> 00:03:10,380
Имао поново у недељу нула, а то је
у потрази за некога у телефонском именику,

64
00:03:10,380 --> 00:03:12,380
и сећам се да је
Псеудокод да смо предложили,

65
00:03:12,380 --> 00:03:14,560
преко којих можемо да нађемо
неко као Мајк Смит,

66
00:03:14,560 --> 00:03:16,310
Погледао нешто овако.

67
00:03:16,310 --> 00:03:20,820
>> Сада погледајте у посебно
у линији 7 и 8, и 10 и 11,

68
00:03:20,820 --> 00:03:25,240
који изазивају ту петљу, где смо држали
да се вратимо на линији 3 опет, и опет,

69
00:03:25,240 --> 00:03:26,520
и поново.

70
00:03:26,520 --> 00:03:31,790
Али испоставило се да можемо да видите
Овај алгоритам, овде у псеудокоду,

71
00:03:31,790 --> 00:03:33,620
мало више холистички.

72
00:03:33,620 --> 00:03:35,960
У ствари, оно што ја тражим
у овде на екрану,

73
00:03:35,960 --> 00:03:41,180
је алгоритам за претрагу
Мајк Смит међу неког скупа страница.

74
00:03:41,180 --> 00:03:45,520
И заиста, могли смо да поједноставимо
алгоритам у тим линијама 7 и 8,

75
00:03:45,520 --> 00:03:49,860
и 10 и 11 да кажем само ово,
које сам представио овде у жуто.

76
00:03:49,860 --> 00:03:52,210
Другим речима, ако Мајк
Смит је раније у књизи,

77
00:03:52,210 --> 00:03:55,004
не треба да одредите корак
по корак сад како да га нађем.

78
00:03:55,004 --> 00:03:56,920
Ми не морамо да одредите
да се вратимо на линији 3,

79
00:03:56,920 --> 00:03:58,960
зашто не бисмо уместо тога,
рецимо, уопштеније,

80
00:03:58,960 --> 00:04:01,500
сеарцх фор Мике у
лева половина књиге.

81
00:04:01,500 --> 00:04:03,960
>> С друге стране, ако је Мајк
заправо касније у књизи,

82
00:04:03,960 --> 00:04:07,540
зашто не бисмо под знацима навода претрагу
за Мике у десној половини књиге.

83
00:04:07,540 --> 00:04:11,030
Другим речима, зашто не бисмо
некако пунт да сами говоре,

84
00:04:11,030 --> 00:04:13,130
сеарцх фор Мике у овом
подскуп књиге,

85
00:04:13,130 --> 00:04:16,279
и оставите га да нашим постојећим
алгоритам да нам каже

86
00:04:16,279 --> 00:04:18,750
како да тражи у Мике
да лева половина књиге.

87
00:04:18,750 --> 00:04:20,750
Другим речима, наш
алгоритам ради да ли је

88
00:04:20,750 --> 00:04:24,670
телефонски именик ове дебљине, овога
дебљине, или било дебљине уопште.

89
00:04:24,670 --> 00:04:27,826
Тако смо рекурсивно цан
дефинишу овај алгоритам.

90
00:04:27,826 --> 00:04:29,950
Другим речима, на
Екран овде је алгоритам

91
00:04:29,950 --> 00:04:33,130
за тражење Мике Смитх
међу страницама именика.

92
00:04:33,130 --> 00:04:37,410
Дакле, у складу 7. и 10., идемо
само реци управо то.

93
00:04:37,410 --> 00:04:40,250
И ја користим овај термин на тренутак
пре, и заиста, рекурзије

94
00:04:40,250 --> 00:04:42,450
је крилатица за сада,
и то је тај процес

95
00:04:42,450 --> 00:04:47,210
да уради нешто цикличне од некако
коришћењем код који сте већ,

96
00:04:47,210 --> 00:04:49,722
и називајући поново,
и опет, и опет.

97
00:04:49,722 --> 00:04:51,930
Сада ће бити важно
да смо некако дно

98
00:04:51,930 --> 00:04:53,821
напоље, а не да раде бесконачно дуго.

99
00:04:53,821 --> 00:04:56,070
У супротном ћемо
имају заиста бесконачну петљу.

100
00:04:56,070 --> 00:04:59,810
Али хајде да видимо да ли можемо да позајмим идеју
од рекурзије, опет радим нешто

101
00:04:59,810 --> 00:05:03,600
и опет и опет, да се реши
проблем сортирање преко спајања

102
00:05:03,600 --> 00:05:05,900
врста, све ефикасније.

103
00:05:05,900 --> 00:05:06,970
>> Зато сам вам дати врста спојити.

104
00:05:06,970 --> 00:05:07,920
Хајде да погледамо.

105
00:05:07,920 --> 00:05:10,850
Дакле, овде је Псеудокод, са
који би могли имплементирати сортирање,

106
00:05:10,850 --> 00:05:12,640
Коришћењем овог алгоритма који се зове спајање врста.

107
00:05:12,640 --> 00:05:13,880
И то је једноставно ово.

108
00:05:13,880 --> 00:05:15,940
На улазу н елемената,
Другим речима, ако сте

109
00:05:15,940 --> 00:05:18,830
с обзиром н елемената и бројеви и
писма или шта год је унос,

110
00:05:18,830 --> 00:05:22,430
ако ти је дато н елемената, ако
н мање од 2, само се врати.

111
00:05:22,430 --> 00:05:22,930
Jel tako?

112
00:05:22,930 --> 00:05:26,430
Јер ако н је мања од 2, то
значи да је мој списак елемената

113
00:05:26,430 --> 00:05:30,446
је или величине 0 или 1, и
у оба та тривијалним случајевима,

114
00:05:30,446 --> 00:05:31,570
листа је већ сортирају.

115
00:05:31,570 --> 00:05:32,810
Ако нема листа, то је средјено.

116
00:05:32,810 --> 00:05:35,185
И ако постоји списак дужине
1, то је очигледно поредани.

117
00:05:35,185 --> 00:05:38,280
Дакле, алгоритам треба само да
Заиста нешто занимљиво,

118
00:05:38,280 --> 00:05:40,870
ако имамо два или више
елементи дато нама.

119
00:05:40,870 --> 00:05:42,440
Дакле, хајде да погледамо магију онда.

120
00:05:42,440 --> 00:05:47,500
Друго сортирање левој половини елемената,
затим сортирање десне половине елемената,

121
00:05:47,500 --> 00:05:49,640
затим се стапа сортиране половине.

122
00:05:49,640 --> 00:05:52,440
А шта је некако ума савијања
овде, да не знам стварно

123
00:05:52,440 --> 00:05:56,190
изгледају да су ти рекао
ништа још увек, зар не?

124
00:05:56,190 --> 00:05:59,560
Све што сам рекао је, с обзиром списак
н елемената, сортирају левој половини,

125
00:05:59,560 --> 00:06:01,800
онда је десна половина, онда
спојити сортиране половине,

126
00:06:01,800 --> 00:06:03,840
али где је стварна тајни сос?

127
00:06:03,840 --> 00:06:05,260
Где је алгоритам?

128
00:06:05,260 --> 00:06:09,150
Па испада да те две линије
Прво, врста левој половини елемената,

129
00:06:09,150 --> 00:06:13,970
и некако десна половина елемената,
су рекурзивни позиви, да тако кажем.

130
00:06:13,970 --> 00:06:16,120
>> Уосталом, ово
тачка у времену, имам

131
00:06:16,120 --> 00:06:18,950
алгоритам са којима се
сортирање гомилу елемената?

132
00:06:18,950 --> 00:06:19,450
Да.

133
00:06:19,450 --> 00:06:20,620
То је овде.

134
00:06:20,620 --> 00:06:25,180
То је овде на екрану, и
тако да могу да користе тај исти скуп корака

135
00:06:25,180 --> 00:06:28,500
за сортирање левој половини,
колико могу десна половина.

136
00:06:28,500 --> 00:06:30,420
И заиста, опет, и опет.

137
00:06:30,420 --> 00:06:34,210
Дакле, на неки начин, и ми ускоро
види ово, магију стапања врсте

138
00:06:34,210 --> 00:06:37,967
је уграђен у томе веома финалу
линија, спајање разврстане половине.

139
00:06:37,967 --> 00:06:39,300
И то изгледа прилично интуитивно.

140
00:06:39,300 --> 00:06:41,050
Узмеш две половине, и ти,
некако, споји их заједно,

141
00:06:41,050 --> 00:06:43,260
па ћемо видети
конкретно у овом тренутку.

142
00:06:43,260 --> 00:06:45,080
>> Али ово је комплетан алгоритам.

143
00:06:45,080 --> 00:06:46,640
И да управо зато видимо.

144
00:06:46,640 --> 00:06:50,912
Па претпоставимо да смо дали те исте
Осам елемената овде на екрану, један

145
00:06:50,912 --> 00:06:53,120
кроз осам, али они су
у наизглед случајним редоследом.

146
00:06:53,120 --> 00:06:55,320
А циљ је на дохват руке
за сортирање ове елементе.

147
00:06:55,320 --> 00:06:58,280
Па како да идем о
ради се користе, опет,

148
00:06:58,280 --> 00:07:00,407
спајање врста, по овом псеудокоду?

149
00:07:00,407 --> 00:07:02,740
И опет, Окорио ово
ваш ум, само на тренутак.

150
00:07:02,740 --> 00:07:05,270
Први случај је прилично
тривијална, ако је мање од 2,

151
00:07:05,270 --> 00:07:07,060
само се врати, нема посла да се уради.

152
00:07:07,060 --> 00:07:09,290
Дакле, стварно само три ту
кораци да стварно имати на уму.

153
00:07:09,290 --> 00:07:11,081
Опет, и опет, ја сам
хтети да има

154
00:07:11,081 --> 00:07:13,980
за сортирање левој половини,
сортирање десној половини,

155
00:07:13,980 --> 00:07:15,890
и онда када им
Две половине су поредани,

156
00:07:15,890 --> 00:07:18,710
Желим да их споји заједно
у један сортирани списак.

157
00:07:18,710 --> 00:07:19,940
Дакле, имајте то на уму.

158
00:07:19,940 --> 00:07:21,310
>> Дакле, овде је оригинална листа.

159
00:07:21,310 --> 00:07:23,510
Хајде да третирамо ово као
Арраи, као што смо почели да

160
00:07:23,510 --> 00:07:25,800
у недељу две, што представља
суседни блок меморије.

161
00:07:25,800 --> 00:07:28,480
У овом случају, садрже осам
Бројеви, бацк то бацк то бацк.

162
00:07:28,480 --> 00:07:30,700
А да се сада примењују стапања врсту.

163
00:07:30,700 --> 00:07:33,300
Дакле, прво желим да средим
лева половина ове листе,

164
00:07:33,300 --> 00:07:37,370
И да, стога,
фокусирати на 4, 8, 6, и 2.

165
00:07:37,370 --> 00:07:41,000
>> Како сад да идем о
сортирање листу величине 4?

166
00:07:41,000 --> 00:07:45,990
Па ја сад морам да размотри
сортирање леве левој половини.

167
00:07:45,990 --> 00:07:47,720
Опет, да уназад за тренутак.

168
00:07:47,720 --> 00:07:51,010
Ако је Псеудокод је ово,
и ја дао осам елемената,

169
00:07:51,010 --> 00:07:53,230
8 је очигледно већи
од или једнако 2.

170
00:07:53,230 --> 00:07:54,980
Дакле, са први случај не односи.

171
00:07:54,980 --> 00:07:58,120
Дакле, за сортирање осам елемената, сам први пут
сортирање левој половини елемената,

172
00:07:58,120 --> 00:08:01,930
онда сам сортирање десне половине, онда сам спојити
две половине сортирана, сваки величине 4.

173
00:08:01,930 --> 00:08:02,470
ОК.

174
00:08:02,470 --> 00:08:07,480
>> Али ако само сте ми рекли, сортирање
Лева половина, која је сада величине 4,

175
00:08:07,480 --> 00:08:09,350
како да сортирају левој половини?

176
00:08:09,350 --> 00:08:11,430
Па ако имам
унос четири елемента,

177
00:08:11,430 --> 00:08:14,590
Први пут сам сортирање лево
два, онда десно два,

178
00:08:14,590 --> 00:08:16,210
и онда сам их спојити заједно.

179
00:08:16,210 --> 00:08:18,700
Дакле, поново постаје помало
од ума савијања игра овде,

180
00:08:18,700 --> 00:08:21,450
јер ти, некако, морам да
сетите где сте у причи,

181
00:08:21,450 --> 00:08:23,620
али на крају дана,
дата никаква број елемената,

182
00:08:23,620 --> 00:08:25,620
прво желите да учини нешто
Лева половина, онда је десна половина,

183
00:08:25,620 --> 00:08:26,661
а затим их спојити заједно.

184
00:08:26,661 --> 00:08:28,630
Почнимо да управо то.

185
00:08:28,630 --> 00:08:30,170
Овде је улаз од осам елемената.

186
00:08:30,170 --> 00:08:31,910
Сада гледамо левој половини овде.

187
00:08:31,910 --> 00:08:33,720
Како да сортирају четири елемента?

188
00:08:33,720 --> 00:08:35,610
Па сам први пут сортирање левој половини.

189
00:08:35,610 --> 00:08:37,720
Сада како да сортирају левој половини?

190
00:08:37,720 --> 00:08:39,419
Па сам дао два елемента.

191
00:08:39,419 --> 00:08:41,240
Дакле, хајде да сортирају ова два елемента.

192
00:08:41,240 --> 00:08:44,540
2 је већи или
једнако 2, наравно.

193
00:08:44,540 --> 00:08:46,170
Тако да први случај не важи.

194
00:08:46,170 --> 00:08:49,010
>> Тако да сада да учини нешто леви
половина ова два елемента.

195
00:08:49,010 --> 00:08:50,870
Лева половина, наравно, само 4.

196
00:08:50,870 --> 00:08:54,020
Па како да сортирају листу једног елемента?

197
00:08:54,020 --> 00:08:57,960
Па сад, да се посебна база случај
до врха, да тако кажем, важи.

198
00:08:57,960 --> 00:09:01,470
1 је мање од 2, и мој
Списак је заиста величине 1.

199
00:09:01,470 --> 00:09:02,747
Тако сам се вратити.

200
00:09:02,747 --> 00:09:03,580
Ја не радим ништа.

201
00:09:03,580 --> 00:09:06,770
И заиста, погледај шта сам
учињено, 4 је већ поредани.

202
00:09:06,770 --> 00:09:09,220
Као што сам већ сам
делимично успешни овде.

203
00:09:09,220 --> 00:09:11,750
>> Сада то изгледа глупо
да тражи, али то је истина.

204
00:09:11,750 --> 00:09:13,700
4 је листа величине 1.

205
00:09:13,700 --> 00:09:15,090
Већ је средјено.

206
00:09:15,090 --> 00:09:16,270
То је лево пола.

207
00:09:16,270 --> 00:09:18,010
Сада сортирање десној половини.

208
00:09:18,010 --> 00:09:22,310
Мој улаз је један елемент, 8
Слично томе, већ поредани.

209
00:09:22,310 --> 00:09:25,170
Глупо, такође, али опет,
Овај основни принцип

210
00:09:25,170 --> 00:09:28,310
ће нам омогућити да сада градимо
на врху ове успешно.

211
00:09:28,310 --> 00:09:32,260
4 поредани, 8 сортира, сада
шта је то било последњи корак?

212
00:09:32,260 --> 00:09:35,330
Дакле, трећи и последњи корак, било
Време ви сортирање листе, опозив,

213
00:09:35,330 --> 00:09:38,310
је да споји две половине,
лево и десно.

214
00:09:38,310 --> 00:09:39,900
Па хајде да управо то.

215
00:09:39,900 --> 00:09:41,940
Моја лева половина је, наравно, 4.

216
00:09:41,940 --> 00:09:43,310
Моја десна половина је 8.

217
00:09:43,310 --> 00:09:44,100
>> Па хајде да урадимо то.

218
00:09:44,100 --> 00:09:46,410
Прво ћу да издвоји
неке додатне меморије,

219
00:09:46,410 --> 00:09:48,680
да ћу представљају овде,
само као секундарни низ,

220
00:09:48,680 --> 00:09:49,660
То је довољно велика да стане ово.

221
00:09:49,660 --> 00:09:52,243
Али можете замислити проширење
да правоугаоник цела дужина,

222
00:09:52,243 --> 00:09:53,290
ако нам треба више касније.

223
00:09:53,290 --> 00:09:58,440
Како да се 4 и 8, и спајање
те две листе величине 1 заједно?

224
00:09:58,440 --> 00:10:00,270
Овде, такође, прилично једноставно.

225
00:10:00,270 --> 00:10:03,300
4 на првом месту, онда долази 8.

226
00:10:03,300 --> 00:10:07,130
Јер ако желим да учини нешто
Лева половина, онда је десна половина,

227
00:10:07,130 --> 00:10:09,900
и онда споји те две половине
заједно, у сортиране,

228
00:10:09,900 --> 00:10:11,940
4 на првом месту, онда долази 8.

229
00:10:11,940 --> 00:10:15,810
>> Дакле, изгледа да се напредује, чак и
иако нисам учинио никакву стварну посао.

230
00:10:15,810 --> 00:10:17,800
Али запамтите где смо у причи.

231
00:10:17,800 --> 00:10:19,360
Ми првобитно је осам елемената.

232
00:10:19,360 --> 00:10:21,480
Ми поредани левој половини, што је 4.

233
00:10:21,480 --> 00:10:24,450
Онда смо поредани левој половини
леве полувремена, која је била 2.

234
00:10:24,450 --> 00:10:25,270
И идемо.

235
00:10:25,270 --> 00:10:26,920
Завршили смо са тим кораком.

236
00:10:26,920 --> 00:10:29,930
>> Дакле, ако смо поредани
лева половина од 2, сада

237
00:10:29,930 --> 00:10:32,130
има за сортирање десне половине 2.

238
00:10:32,130 --> 00:10:35,710
Тако је десна половина 2 је
ове две вредности овде, 6 и 2.

239
00:10:35,710 --> 00:10:40,620
Па хајде сада да улаз величине
2, и сортирање левој половини, а затим

240
00:10:40,620 --> 00:10:42,610
десна половина, а затим
споји их заједно.

241
00:10:42,610 --> 00:10:45,722
Па како да сортирају листу величине
1, који садржи само број 6?

242
00:10:45,722 --> 00:10:46,430
Већ сам урадио.

243
00:10:46,430 --> 00:10:48,680
Та листа величине 1 је поредани.

244
00:10:48,680 --> 00:10:52,140
>> Како да сортирају још један списак
величина 1, тзв десна половина.

245
00:10:52,140 --> 00:10:54,690
Па и она је већ поредани.

246
00:10:54,690 --> 00:10:56,190
Број 2 је сама.

247
00:10:56,190 --> 00:11:00,160
Тако да сада имам две половине, лево и
Добро, треба да их споји заједно.

248
00:11:00,160 --> 00:11:01,800
Дозволите ми да себи дам додатни простор.

249
00:11:01,800 --> 00:11:05,580
И пут 2 тамо,
онда 6 тамо, тако

250
00:11:05,580 --> 00:11:10,740
сортирање тај списак, лево и десно,
и то спајањем, на крају.

251
00:11:10,740 --> 00:11:12,160
Дакле, ја сам у мало бољем стању.

252
00:11:12,160 --> 00:11:16,250
Нисам завршио, јер је очигледно 4, 8, 2,
6 није коначан наручивање што желим.

253
00:11:16,250 --> 00:11:20,640
Али ја сада имају двије листе величине 2, да
су оба, респективно, су поредани.

254
00:11:20,640 --> 00:11:24,580
Дакле, сада ако уназад у ваш ум је
ока, где су нас то води?

255
00:11:24,580 --> 00:11:28,520
Почео сам са осам елемената, онда сам
сведено га на леву половину 4,

256
00:11:28,520 --> 00:11:31,386
затим левог дела од 2, и
онда је десна половина 2,

257
00:11:31,386 --> 00:11:34,510
Завршио сам, дакле, сортирање леви
пола 2, а десна половина 2,

258
00:11:34,510 --> 00:11:37,800
па шта је трећи и коначни корак овде?

259
00:11:37,800 --> 00:11:41,290
Морам да споји заједно
две листе величине 2.

260
00:11:41,290 --> 00:11:42,040
Дакле, идемо напред.

261
00:11:42,040 --> 00:11:43,940
И на екрану овде, дај
ми неке додатне меморије,

262
00:11:43,940 --> 00:11:47,170
иако технички, приметити да имам
Имам гомилу бланк простора до врха

263
00:11:47,170 --> 00:11:47,670
тамо.

264
00:11:47,670 --> 00:11:50,044
Ако желим да будем посебно
ефикасан простор мудар,

265
00:11:50,044 --> 00:11:52,960
Могао бих почети креће елементе
напред и назад, горњи и доњи.

266
00:11:52,960 --> 00:11:55,460
Али само за визуелну јасноћу,
Ја ћу да га ставим доле,

267
00:11:55,460 --> 00:11:56,800
да би ствари лепо и чисто.

268
00:11:56,800 --> 00:11:58,150
>> Дакле, имам две листе величине 2.

269
00:11:58,150 --> 00:11:59,770
Прва листа има 4 и 8.

270
00:11:59,770 --> 00:12:01,500
Друга листа има 2 и 6.

271
00:12:01,500 --> 00:12:03,950
Хајде да споји оне
заједно сортиране.

272
00:12:03,950 --> 00:12:09,910
2, наравно, на првом месту,
па 4, па 6, па 8.

273
00:12:09,910 --> 00:12:12,560
А сада Изгледа да се
негде занимљиво.

274
00:12:12,560 --> 00:12:15,720
Сада сам поредани половина
лист, и случајно, то је

275
00:12:15,720 --> 00:12:18,650
сви парни бројеви, али да
је, заиста, само случајност.

276
00:12:18,650 --> 00:12:22,220
И сада поредани лево
пола, тако да је 2, 4, 6 и 8.

277
00:12:22,220 --> 00:12:23,430
Ништа не ради.

278
00:12:23,430 --> 00:12:24,620
То се осећа као напредак.

279
00:12:24,620 --> 00:12:26,650
>> Сада се осећа као да сам
Разговарао заувек сада,

280
00:12:26,650 --> 00:12:29,850
па шта остаје да се види да ли ова
Алгоритам је, заиста, ефикаснија.

281
00:12:29,850 --> 00:12:31,766
Али идемо кроз
буде супер методично.

282
00:12:31,766 --> 00:12:34,060
Компјутер, наравно,
би то тако.

283
00:12:34,060 --> 00:12:34,840
Па, где смо?

284
00:12:34,840 --> 00:12:36,180
Почели смо са осам елемената.

285
00:12:36,180 --> 00:12:37,840
Ја поредани левој половини 4.

286
00:12:37,840 --> 00:12:39,290
Чини ми се да се уради са тим.

287
00:12:39,290 --> 00:12:42,535
Дакле, сада је следећи корак да
сортирање десне половине 4.

288
00:12:42,535 --> 00:12:44,410
И овај дио можемо ићи
кроз Литтле Море

289
00:12:44,410 --> 00:12:47,140
брзо, иако сте
Велцоме то уназад или паузирати, само

290
00:12:47,140 --> 00:12:49,910
Мислим кроз њега у
сопственим темпом, али шта

291
00:12:49,910 --> 00:12:53,290
имамо сада је прилика да
раде потпуно исту алгоритам на четири

292
00:12:53,290 --> 00:12:54,380
различити бројеви.

293
00:12:54,380 --> 00:12:57,740
>> Дакле, идемо напред, и фокусирати се на
десна половина, које смо овде.

294
00:12:57,740 --> 00:13:01,260
Лева половина од тога
десна половина, а сада

295
00:13:01,260 --> 00:13:04,560
лева половина леве стране
половина тог десној половини,

296
00:13:04,560 --> 00:13:08,030
и како да сортирају листу величине
1 који садржи само број 1?

297
00:13:08,030 --> 00:13:09,030
То је већ урађено.

298
00:13:09,030 --> 00:13:11,830
Како то да урадим исто за листу
величине 1 садржи само 7?

299
00:13:11,830 --> 00:13:12,840
То је већ урађено.

300
00:13:12,840 --> 00:13:16,790
Трећи корак за ову половину онда
је да споји ова два елемента

301
00:13:16,790 --> 00:13:20,889
у нову листу величине 2, 1 и 7.

302
00:13:20,889 --> 00:13:23,180
Изгледа да нису урадили све
толико интересантан посао.

303
00:13:23,180 --> 00:13:24,346
Да видимо шта ће се десити следеће.

304
00:13:24,346 --> 00:13:29,210
Само поредани на левој половини
десна половина мог оригиналног улаза.

305
00:13:29,210 --> 00:13:32,360
Сада ћемо сортирање право
половине, који садржи 5 и 3.

306
00:13:32,360 --> 00:13:35,740
Хајде да поново погледамо лево
половина, поредани, десна половина, сортирано,

307
00:13:35,740 --> 00:13:39,120
и спојити та два заједно,
у неким додатни простор,

308
00:13:39,120 --> 00:13:41,670
3 на првом месту, онда долази 5.

309
00:13:41,670 --> 00:13:46,190
И сада смо поредани
лева половина десне половине

310
00:13:46,190 --> 00:13:49,420
оригиналног проблема и
право половина десне половине

311
00:13:49,420 --> 00:13:50,800
оригиналног проблема.

312
00:13:50,800 --> 00:13:52,480
Шта је трећи и последњи корак?

313
00:13:52,480 --> 00:13:54,854
Па да споји ове две половине заједно.

314
00:13:54,854 --> 00:13:57,020
Дакле, да себи узмем
Додатни простор, али, опет,

315
00:13:57,020 --> 00:13:58,699
може бити користећи тај резервни простор одозго.

316
00:13:58,699 --> 00:14:00,490
Али ми ћемо задржати
визуелно једноставна.

317
00:14:00,490 --> 00:14:07,070
Пусти ме спојити у нов 1, и
тада 3, а затим 5, а затим 7.

318
00:14:07,070 --> 00:14:10,740
На тај начин ми остављајући сада са
десна половина оригиналне проблема

319
00:14:10,740 --> 00:14:12,840
То је потпуно средјено.

320
00:14:12,840 --> 00:14:13,662
>> Дакле, шта остаје?

321
00:14:13,662 --> 00:14:16,120
Осећам се као да стално тврдећи да је
исте ствари опет, и опет,

322
00:14:16,120 --> 00:14:18,700
али то је одражавају од
Чињеница да смо користећи рекурзију.

323
00:14:18,700 --> 00:14:21,050
Процес коришћењем
алгоритам опет, и опет,

324
00:14:21,050 --> 00:14:23,940
на мањим подгрупе
оригинални проблема.

325
00:14:23,940 --> 00:14:27,580
Тако да сам сада левој поредани
половина некадашњег проблема.

326
00:14:27,580 --> 00:14:30,847
Имам право сортирану пола
оригиналног проблема.

327
00:14:30,847 --> 00:14:32,180
Шта је трећи и последњи корак?

328
00:14:32,180 --> 00:14:33,590
О, то је спајање.

329
00:14:33,590 --> 00:14:34,480
Па хајде да урадимо то.

330
00:14:34,480 --> 00:14:36,420
Хајде да издвоје неке додатне
меморије, али Боже мој, ми

331
00:14:36,420 --> 00:14:37,503
да га стави где сада.

332
00:14:37,503 --> 00:14:40,356
Имамо толико простора на располагању
за нас, али ми ћемо га задржати једноставно.

333
00:14:40,356 --> 00:14:42,730
Уместо да се вратимо и
напред са нашим оригиналним меморије,

334
00:14:42,730 --> 00:14:44,480
хајде да то уради
визуелно овде доле,

335
00:14:44,480 --> 00:14:47,240
завршити спајањем
Лева половина и десна половина.

336
00:14:47,240 --> 00:14:49,279
>> Тако спајањем, шта треба да урадим?

337
00:14:49,279 --> 00:14:50,820
Желим да елементе како.

338
00:14:50,820 --> 00:14:53,230
Дакле, гледајући левој половини,
Видим да је први број је 2.

339
00:14:53,230 --> 00:14:55,230
Гледам на десној половини,
Видим први број

340
00:14:55,230 --> 00:14:58,290
је 1, очигледно која
Број желим да ишчупам,

341
00:14:58,290 --> 00:15:00,430
и стави први у мојој коначној листи?

342
00:15:00,430 --> 00:15:01,449
Наравно, 1.

343
00:15:01,449 --> 00:15:02,990
Сада желим да поставим то исто питање.

344
00:15:02,990 --> 00:15:05,040
На левој половини, ја сам
увек има број 2.

345
00:15:05,040 --> 00:15:07,490
На десној половини,
Имам број 3.

346
00:15:07,490 --> 00:15:08,930
Који желим да изаберем?

347
00:15:08,930 --> 00:15:11,760
Наравно, број 2 и
сада приметити кандидата

348
00:15:11,760 --> 00:15:13,620
су 4 са леве стране, 3 на десној страни.

349
00:15:13,620 --> 00:15:15,020
Идемо, наравно, изабрати 3.

350
00:15:15,020 --> 00:15:18,020
Сада кандидати су 4 на
лева, 5 на десној страни.

351
00:15:18,020 --> 00:15:19,460
Ми, наравно, изаберите 4.

352
00:15:19,460 --> 00:15:21,240
6 лево, 5 на десној страни.

353
00:15:21,240 --> 00:15:22,730
Ми, наравно, изабрати 5.

354
00:15:22,730 --> 00:15:25,020
6 лево, 7 на десној страни.

355
00:15:25,020 --> 00:15:29,320
Бирамо 6, а онда смо
изабрати 7, а онда бирамо 8.

356
00:15:29,320 --> 00:15:30,100
Воила.

357
00:15:30,100 --> 00:15:34,370
>> Дакле, огроман број речи касније,
су поредани ову листу од осам елемената

358
00:15:34,370 --> 00:15:38,450
у листу један кроз осам,
који расте са сваком кораку,

359
00:15:38,450 --> 00:15:40,850
али колико времена урадили
нам требати за то.

360
00:15:40,850 --> 00:15:43,190
Па ја сам намерно
ених ствари сликовито

361
00:15:43,190 --> 00:15:46,330
овде, тако да можемо некако
види или ценити поделу

362
00:15:46,330 --> 00:15:49,060
у освајању да се дешава.

363
00:15:49,060 --> 00:15:52,830
>> Заиста, ако се осврнете на трагу,
Оставио сам све ове тачкастим линијама

364
00:15:52,830 --> 00:15:55,660
у носиоцима месту, можете,
врста, види, обрнутим редоследом,

365
00:15:55,660 --> 00:15:58,800
ако врста лоок бацк у
Историја сад, моја првобитна листа

366
00:15:58,800 --> 00:16:00,250
је, наравно, величине 8.

367
00:16:00,250 --> 00:16:03,480
А онда раније, био сам
суочавање са две листе величине 4,

368
00:16:03,480 --> 00:16:08,400
а затим четири листа величине 2,
затим осам листе величину 1.

369
00:16:08,400 --> 00:16:10,151
>> Дакле, шта ово,
врста, да вас подсетим?

370
00:16:10,151 --> 00:16:11,858
Свакако, било који од
алгоритми смо

371
00:16:11,858 --> 00:16:14,430
Погледао до сада где смо
завади, и поделе, и подела,

372
00:16:14,430 --> 00:16:19,500
даље имам ствари поново, и
Опет, резултати у овом општем идеји.

373
00:16:19,500 --> 00:16:23,100
И тако нешто
логаритамске се овде дешава.

374
00:16:23,100 --> 00:16:26,790
И није баш дневник н, али
ту је логаритамска компонента

375
00:16:26,790 --> 00:16:28,280
да оно што смо управо урадили.

376
00:16:28,280 --> 00:16:31,570
>> Сада ћемо размотрити како то заправо јесте.

377
00:16:31,570 --> 00:16:34,481
Дакле, лог Н, поново био
велики трајање,

378
00:16:34,481 --> 00:16:36,980
када смо урадили нешто слично
бинарна претрага, као што сада зову,

379
00:16:36,980 --> 00:16:40,090
подела па владај стратегије
преко које смо нашли Мике Смитх.

380
00:16:40,090 --> 00:16:41,020
Сада технички.

381
00:16:41,020 --> 00:16:43,640
То је дневник база 2 Н, чак и
иако у већини класа математике,

382
00:16:43,640 --> 00:16:45,770
10 је обично основа да претпоставимо.

383
00:16:45,770 --> 00:16:48,940
Али компјутерски научници скоро увек
мисле и говоре у смислу основе 2,

384
00:16:48,940 --> 00:16:52,569
тако да смо углавном само рећи дневника
н, уместо лог основом 2 од н,

385
00:16:52,569 --> 00:16:55,110
али они су тачно један и
Исто у свету рачунара

386
00:16:55,110 --> 00:16:57,234
науке, и као успут,
постоји стални фактор

387
00:16:57,234 --> 00:17:01,070
Разлика између та два, тако да је
Моот сваком случају, за више формалних разлога.

388
00:17:01,070 --> 00:17:04,520
>> Али за сада, оно што ми је стало
о је овај пример.

389
00:17:04,520 --> 00:17:08,520
Дакле, немојмо докаже пример, али у
најмање користе пример бројева

390
00:17:08,520 --> 00:17:10,730
при руци као проверу исправности, ако хоћете.

391
00:17:10,730 --> 00:17:14,510
Дакле, претходно је формула била евиденција база
2 од н, али оно што је н у овом случају.

392
00:17:14,510 --> 00:17:18,526
Имао сам н оригиналне бројеве, или 8
оригиналне броја конкретно.

393
00:17:18,526 --> 00:17:20,359
Сада је мало
док, али сам прилично

394
00:17:20,359 --> 00:17:25,300
да ли дневник база 2
од вредности 8 је 3,

395
00:17:25,300 --> 00:17:29,630
и заиста, шта је лепо о томе се
да 3 је управо број пута

396
00:17:29,630 --> 00:17:33,320
да можете поделити списак
дужине 8 опет, и опет,

397
00:17:33,320 --> 00:17:36,160
и опет, све док сте напустили
са списковима само величине 1.

398
00:17:36,160 --> 00:17:36,660
Jel tako?

399
00:17:36,660 --> 00:17:40,790
8 иде до 4, иде на 2,
иде до 1, и то је

400
00:17:40,790 --> 00:17:43,470
одражава управо то
слика коју смо имали пре неколико тренутака.

401
00:17:43,470 --> 00:17:47,160
Дакле, мало разум проверите и где
логаритам је заправо укључен.

402
00:17:47,160 --> 00:17:50,180
>> Дакле, сада, шта још је укључен овде? н.

403
00:17:50,180 --> 00:17:53,440
Дакле, приметио да сваки
пут када сам поделио списак,

404
00:17:53,440 --> 00:17:58,260
мада у обрнутом редоследу у историји
овде, ја сам још увек радиш ствари н.

405
00:17:58,260 --> 00:18:02,320
То спајање корак потребно да
Ја тоуцх сваки од бројева,

406
00:18:02,320 --> 00:18:05,060
како би га склизне у
њена одговарајућа локација.

407
00:18:05,060 --> 00:18:10,760
Дакле, иако је висина ове
дијаграм је величина дневника н од н или 3,

408
00:18:10,760 --> 00:18:13,860
конкретно, другим речима,
Ја сам три дивизије овде.

409
00:18:13,860 --> 00:18:18,800
Колико посла сам хоризонтално урадити
дуж овог графикону сваки пут?

410
00:18:18,800 --> 00:18:21,110
>> Па, јесам н кораке
радити, јер ако имам

411
00:18:21,110 --> 00:18:24,080
Има четири елемента и четири елемента,
и морам да их спојити заједно.

412
00:18:24,080 --> 00:18:26,040
Морам да идем кроз
ово четворо и њих четири,

413
00:18:26,040 --> 00:18:28,123
на крају спојити их
назад у осам елемената.

414
00:18:28,123 --> 00:18:32,182
Ако обрнуто имам осам прстију
овамо, што не знам, и осам

415
00:18:32,182 --> 00:18:34,390
фингерс-- је-- Ако сам
Има четири прста овде,

416
00:18:34,390 --> 00:18:37,380
што да радим, четири прста
овамо, што радим,

417
00:18:37,380 --> 00:18:40,590
онда је то исто
пример као и раније, ако то урадим

418
00:18:40,590 --> 00:18:44,010
има осам прсте, иако у
укупно, што могу, некако, да.

419
00:18:44,010 --> 00:18:47,950
Ја тачно могу да радим овде,
онда свакако да могу

420
00:18:47,950 --> 00:18:50,370
спајање свих ових спискова
величине 1 заједно.

421
00:18:50,370 --> 00:18:54,050
Али свакако да погледам
у сваком елементу тачно једанпут.

422
00:18:54,050 --> 00:18:59,640
Дакле, висина овог процеса је лог н,
ширина овог процеса, да тако кажем,

423
00:18:59,640 --> 00:19:02,490
је н, тако да оно што изгледа
да, на крају, је

424
00:19:02,490 --> 00:19:06,470
руннинг време величине н пута лог н.

425
00:19:06,470 --> 00:19:08,977
>> Другим речима, ми подијељени
листа, евиденција н пута,

426
00:19:08,977 --> 00:19:11,810
али сваки пут смо то урадили, имали смо
да додирне сваки од елемената

427
00:19:11,810 --> 00:19:13,560
како би их спојили
сви заједно, што

428
00:19:13,560 --> 00:19:18,120
Вас н корак, тако да имамо н пута лог н
или као компјутерски научник би рекли,

429
00:19:18,120 --> 00:19:20,380
асимптотично, која
ће бити велика реч

430
00:19:20,380 --> 00:19:22,810
да опише горњи
везан на време рада,

431
00:19:22,810 --> 00:19:28,010
трчимо у Биг О
од лог н време, да се тако изразим.

432
00:19:28,010 --> 00:19:31,510
>> Ово је значајно, јер
сећате шта су руннинг пута били

433
00:19:31,510 --> 00:19:34,120
са буббле сорт, и избор
врста, и уметање врста,

434
00:19:34,120 --> 00:19:38,200
па чак и неколико других које постоје,
Н квадрат је где смо били у.

435
00:19:38,200 --> 00:19:39,990
И можете, некако, погледајте ово овде.

436
00:19:39,990 --> 00:19:45,720
Ако је н квадрат је очигледно н пута
Н, али овде имамо н пута лог н

437
00:19:45,720 --> 00:19:48,770
а ми већ знамо из недеље
нула, то лог н, логаритамска,

438
00:19:48,770 --> 00:19:50,550
је боље него нешто линеарно.

439
00:19:50,550 --> 00:19:52,930
Уосталом, сећам се слику
са црвеном и жута

440
00:19:52,930 --> 00:19:56,500
и зелене линије које смо изазвале, Тхе
зелена логаритамске линија је била много мања.

441
00:19:56,500 --> 00:20:00,920
И зато, много боље и брже
од равне жуте и црвене линије,

442
00:20:00,920 --> 00:20:05,900
н пута лог н је, заиста боље,
него н пута н, или н квадрат.

443
00:20:05,900 --> 00:20:09,110
>> Дакле, изгледа да имамо
идентификовао стопи алгоритам

444
00:20:09,110 --> 00:20:11,870
врста која ради у много
бржи пут, и заиста,

445
00:20:11,870 --> 00:20:16,560
Зато, раније ове недеље, када
видели смо да је такмичење између буббле

446
00:20:16,560 --> 00:20:20,750
врста, избор врста и спајање
врста, спајање врста стварно, стварно победио.

447
00:20:20,750 --> 00:20:23,660
И заиста, нисмо ни чекати
за буббле сорт и избор врсте

448
00:20:23,660 --> 00:20:24,790
завршити.

449
00:20:24,790 --> 00:20:27,410
>> Сада узмимо још једну пропусницу
ово, са мало више

450
00:20:27,410 --> 00:20:31,030
формалне тачке гледишта, само у
случају, то одјекује боље

451
00:20:31,030 --> 00:20:33,380
од тога виши ниво дискусије.

452
00:20:33,380 --> 00:20:34,880
Ево опет алгоритам.

453
00:20:34,880 --> 00:20:36,770
Хајде да се запитамо,
шта руннинг тиме

454
00:20:36,770 --> 00:20:39,287
је ово алгоритама различите кораке?

455
00:20:39,287 --> 00:20:41,620
Хајде да га поделимо на први
Случај и други случај.

456
00:20:41,620 --> 00:20:46,280
ИФ и друго у случају да,
Ако је н мање од 2, само се врати.

457
00:20:46,280 --> 00:20:47,580
Осећа се сталном време.

458
00:20:47,580 --> 00:20:50,970
То је, некако, као два корака,
Ако је н мање од 2, а затим се вратите.

459
00:20:50,970 --> 00:20:54,580
Али, као што смо рекли у понедељак,
константа време, или Биг О 1,

460
00:20:54,580 --> 00:20:57,130
могу бити два корака, три
кораци, чак 1.000 корака.

461
00:20:57,130 --> 00:20:59,870
Оно што је битно је да је
исти број корака.

462
00:20:59,870 --> 00:21:03,240
Дакле, жута истакао Псеудокод
овде ради у, ми ћемо га назвати,

463
00:21:03,240 --> 00:21:04,490
константа време.

464
00:21:04,490 --> 00:21:06,780
Тако је формално више, и
идемо да-- ово

465
00:21:06,780 --> 00:21:09,910
биће у којој мери смо
формализују то право сада-- Т Н,

466
00:21:09,910 --> 00:21:15,030
прирастао време проблем
да се н Сометхинг као улаз,

467
00:21:15,030 --> 00:21:19,150
једнако Биг О једне,
Ако је н мање од 2.

468
00:21:19,150 --> 00:21:20,640
Дакле, то је условљено о томе.

469
00:21:20,640 --> 00:21:24,150
Дакле, да буде јасно, ако је н мање од
2, имамо врло кратак списак, а затим

470
00:21:24,150 --> 00:21:29,151
руннинг тиме, Т. од н, где је н
1 или 0, у овом веома конкретном случају,

471
00:21:29,151 --> 00:21:30,650
само ће бити константна времена.

472
00:21:30,650 --> 00:21:32,691
То ће трајати један
корак, два корака, како год.

473
00:21:32,691 --> 00:21:33,950
То је фиксни број корака.

474
00:21:33,950 --> 00:21:38,840
>> Дакле, сочно део сигурно бити у
друга случај у псеудокоду.

475
00:21:38,840 --> 00:21:40,220
Елсе случај.

476
00:21:40,220 --> 00:21:44,870
Врста лева половина елемената, некако у реду
половина елемената, спајање разврстане половине.

477
00:21:44,870 --> 00:21:46,800
Колико дуго траје сваки од ових корака узети?

478
00:21:46,800 --> 00:21:49,780
Па, ако је трчање
Време за сортирање н елемената

479
00:21:49,780 --> 00:21:53,010
је, назовимо то врло
генерички, Т. од н,

480
00:21:53,010 --> 00:21:55,500
затим сортирање лево
половина елемената

481
00:21:55,500 --> 00:21:59,720
је, некако, као да кажеш,
Т од н подељено са 2,

482
00:21:59,720 --> 00:22:03,000
и слично сортирање десне половине
елемената је, некако, као да кажеш,

483
00:22:03,000 --> 00:22:06,974
Т од н подељена 2, а затим
спајањем сортиране половине.

484
00:22:06,974 --> 00:22:08,890
Па ако Имам неке
број елемената овде,

485
00:22:08,890 --> 00:22:11,230
као четири, а неки број
елемената овде, као четири,

486
00:22:11,230 --> 00:22:14,650
и ја морати да се повежу сваки од ова четири
у, и свака од ових четири у, један

487
00:22:14,650 --> 00:22:17,160
после друге, тако да
на крају крајева ја имам осам елемената.

488
00:22:17,160 --> 00:22:20,230
Изгледа као да је Биг О од н корака?

489
00:22:20,230 --> 00:22:23,500
Ако имам н прсте и свака од
да мора да се споје у месту,

490
00:22:23,500 --> 00:22:25,270
то је као да још н корака.

491
00:22:25,270 --> 00:22:27,360
>> И заиста формулаицалли,
можемо изразити ово,

492
00:22:27,360 --> 00:22:29,960
мада мало сцарили у почетку
поглед, али то је нешто

493
00:22:29,960 --> 00:22:31,600
да снима баш ту логику.

494
00:22:31,600 --> 00:22:35,710
Време ради, Т од н, ако је н
је већи од или једнако 2.

495
00:22:35,710 --> 00:22:42,500
У овом случају, елсе случају, је Т од н
подељено са 2 плус Т од н подељено са 2,

496
00:22:42,500 --> 00:22:45,320
плус Биг О Н, неки
линеарна број корака,

497
00:22:45,320 --> 00:22:51,630
можда тачно, можда н 2 пута
Н, али је отприлике ред н.

498
00:22:51,630 --> 00:22:54,060
Тако да је, такође, како можемо
изразити ово формулаицалли.

499
00:22:54,060 --> 00:22:56,809
Сада не знам, осим ако
сте га снимили у вашем уму,

500
00:22:56,809 --> 00:22:58,710
или га потражите у
задњи део уџбеника, који

501
00:22:58,710 --> 00:23:00,501
можда има мало
Цхеат Схеет на крају,

502
00:23:00,501 --> 00:23:03,940
али ово је, заиста, да
дај нам велики О од н лог н,

503
00:23:03,940 --> 00:23:06,620
јер рекурентну која
ви овде видите на екрану,

504
00:23:06,620 --> 00:23:09,550
ако га стварно урадили да, са
бесконачан број примјера,

505
00:23:09,550 --> 00:23:13,000
или сте то урадили формулаицалли, ти би
видим да ово, јер ове формуле

506
00:23:13,000 --> 00:23:17,100
Сама је рекурзивни, са т
Н преко нечега на десној страни,

507
00:23:17,100 --> 00:23:21,680
и т н преко са леве стране, ово може
заправо може изразити, на крају,

508
00:23:21,680 --> 00:23:24,339
као велики иди од н лог н.

509
00:23:24,339 --> 00:23:26,130
Ако није убеђен, да је
Добро за сада, само

510
00:23:26,130 --> 00:23:28,960
преузимају вери, да је то, заиста,
шта је то рецидив доводи до,

511
00:23:28,960 --> 00:23:31,780
али ово је само мало више Паге
математички приступ у потрази

512
00:23:31,780 --> 00:23:36,520
у покренут време стапања врсте
на основу своје псеудокоду сам.

513
00:23:36,520 --> 00:23:39,030
>> Сада узмимо мало
бреатхер од свега тога,

514
00:23:39,030 --> 00:23:41,710
те да погледам
сигурно бивши сенатор, који је

515
00:23:41,710 --> 00:23:44,260
може изгледати мало познато,
који седе са Гоогле Ериц

516
00:23:44,260 --> 00:23:48,410
Шмит, пре извесног времена, за интервју
на бини, испред гомила

517
00:23:48,410 --> 00:23:53,710
људи, говори о крају
тема, то је прилично сада познато.

518
00:23:53,710 --> 00:23:54,575
Хајде да погледамо.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Ерик Шмит: Сада сенатор,
да си овде на Гоогле,

521
00:24:03,890 --> 00:24:09,490
и ја волим да мислим да од
Предсједништво као интервју за посао.

522
00:24:09,490 --> 00:24:11,712
Сада је тешко добити посао као председника.

523
00:24:11,712 --> 00:24:12,670
Председник Обама: Добро.

524
00:24:12,670 --> 00:24:13,940
Ерик Шмит: А ти си
урадити [неразумљиво] сада.

525
00:24:13,940 --> 00:24:15,523
Такође је тешко добити посао у Гоогле-у.

526
00:24:15,523 --> 00:24:17,700
Председник Обама: Добро.

527
00:24:17,700 --> 00:24:21,330
>> Ерик Шмит: Ми имамо питања,
и тражимо наших кандидата питања,

528
00:24:21,330 --> 00:24:24,310
а ово је један од Ларри Швимер.

529
00:24:24,310 --> 00:24:25,890
>> Председник Обама: У реду.

530
00:24:25,890 --> 00:24:27,005
>> Ерик Шмит: Шта?

531
00:24:27,005 --> 00:24:28,130
Мислите да се шалим?

532
00:24:28,130 --> 00:24:30,590
То је овде.

533
00:24:30,590 --> 00:24:33,490
Који је најефикаснији начин да се
сортирање милиона 32 битне целе бројеве?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> Председник Обама: Па--

536
00:24:38,979 --> 00:24:41,020
Ерик Шмит: Понекад,
Можда Жао ми је, маибе--

537
00:24:41,020 --> 00:24:42,750
Председник Обама: Не, не,
Не, не, не, мислим--

538
00:24:42,750 --> 00:24:43,240
Ерик Шмит: То није то--

539
00:24:43,240 --> 00:24:45,430
Председник Обама: Ја
Мислим, мислим да је мехур

540
00:24:45,430 --> 00:24:46,875
Сорт би био погрешан пут којим треба ићи.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Ерик Шмит: Хајде.

543
00:24:50,535 --> 00:24:52,200
Ко му је то рекао?

544
00:24:52,200 --> 00:24:54,020
ОК.

545
00:24:54,020 --> 00:24:55,590
Нисам рачунар наука ајде--

546
00:24:55,590 --> 00:24:58,986
>> Председник Обама: Морамо
имамо своје шпијуне тамо.

547
00:24:58,986 --> 00:24:59,860
ПРОФЕСОР: У реду.

548
00:24:59,860 --> 00:25:03,370
Оставимо иза нас сада
теоријски свет алгоритама

549
00:25:03,370 --> 00:25:06,520
у Асимптотска
истих, и вратите се у неким темама

550
00:25:06,520 --> 00:25:09,940
од недеље нула и један, и старт
да уклоне неке точкова обуке,

551
00:25:09,940 --> 00:25:10,450
ако хоћете.

552
00:25:10,450 --> 00:25:13,241
Тако да заиста разумеју
на крају из темеља, што је

553
00:25:13,241 --> 00:25:16,805
дешава испод хаубе када вас
пишу, састављају и извршава програме.

554
00:25:16,805 --> 00:25:19,680
Подсетимо посебно, да је
први Ц програм смо гледали,

555
00:25:19,680 --> 00:25:22,840
канонски, једноставан програм
нека врста, релативно говорећи,

556
00:25:22,840 --> 00:25:24,620
где, он га штампа, Хелло Ворлд.

557
00:25:24,620 --> 00:25:27,610
И сећам се да сам рекао, процес
да изворни код пролази кроз

558
00:25:27,610 --> 00:25:28,430
је управо то.

559
00:25:28,430 --> 00:25:31,180
Узмеш свој изворни код, пролазе
се кроз компајлер, као Цланг,

560
00:25:31,180 --> 00:25:34,650
и изађе објецт код, који
може изгледати овако, нула и јединица

561
00:25:34,650 --> 00:25:37,880
да процесор рачунара, централно
обрада јединица или мозга,

562
00:25:37,880 --> 00:25:39,760
на крају разуме.

563
00:25:39,760 --> 00:25:42,460
>> Испоставило се да је то
помало поједностављења,

564
00:25:42,460 --> 00:25:44,480
да смо сада смо у
Положај то теасе осим

565
00:25:44,480 --> 00:25:46,720
да разумете шта је заиста био
дешава испод хаубе

566
00:25:46,720 --> 00:25:48,600
сваки пут када покренете
Кланг, или уопште,

567
00:25:48,600 --> 00:25:53,040
сваки пут када направите програм,
користећи Направите и ЦФ 50 САТА.

568
00:25:53,040 --> 00:25:56,760
Посебно, такве ствари
ово је прво генерише,

569
00:25:56,760 --> 00:25:58,684
када сте први пут саставити ваш програм.

570
00:25:58,684 --> 00:26:00,600
Другим речима, када вас
узети изворни код

571
00:26:00,600 --> 00:26:04,390
и саставити га, шта је прва
се имати излаз од Цланг

572
00:26:04,390 --> 00:26:06,370
је нешто познат као склапање кода.

573
00:26:06,370 --> 00:26:08,990
И у ствари, изгледа баш овако.

574
00:26:08,990 --> 00:26:11,170
>> Водио сам командом у
командна линија раније.

575
00:26:11,170 --> 00:26:16,260
Цланг Дасх главног града с хелло.ц,
и то је створио слику

576
00:26:16,260 --> 00:26:19,490
за мене зову хелло.с,
унутар којих се тачно

577
00:26:19,490 --> 00:26:22,290
ови садржаји, и мало више
изнад и мало више у наставку,

578
00:26:22,290 --> 00:26:25,080
али сам ставио Јуициест
информације овде на екрану.

579
00:26:25,080 --> 00:26:29,190
А ако мало боље погледате, видећете
бар неколико познатих кључне речи.

580
00:26:29,190 --> 00:26:31,330
Имамо главни на врху.

581
00:26:31,330 --> 00:26:35,140
Ми смо принтф доле у ​​средини.

582
00:26:35,140 --> 00:26:38,670
Такође имамо Хелло Ворлд
обрнута коса црта н у наводницима доле.

583
00:26:38,670 --> 00:26:42,450
>> И све остало овде
је инструкције врло низак ниво

584
00:26:42,450 --> 00:26:45,500
да процесор рачунара разуме.

585
00:26:45,500 --> 00:26:50,090
Инструкције које се крећу ЦПУ меморије
око, то оптерећење жице из меморије,

586
00:26:50,090 --> 00:26:52,750
и на крају, штампање
ствари на екрану.

587
00:26:52,750 --> 00:26:56,780
Шта сад дешава иако је после
овај скуп код се генерише?

588
00:26:56,780 --> 00:26:59,964
На крају, ти, заиста,
и даље генерише објекат код.

589
00:26:59,964 --> 00:27:02,630
Али кораци који имају заиста
се дешава испод хаубе

590
00:27:02,630 --> 00:27:04,180
изгледају мало више овако.

591
00:27:04,180 --> 00:27:08,390
Изворни код постаје скупштина код,
који тада постаје објекат код,

592
00:27:08,390 --> 00:27:11,930
и Оперативне речи су овде да
када саставити свој изворни код,

593
00:27:11,930 --> 00:27:16,300
изађе склапање шифру, а затим
Када саставите свој код монтаже,

594
00:27:16,300 --> 00:27:17,800
изађе објекат код.

595
00:27:17,800 --> 00:27:20,360
>> Сада кланг је супер софистициран,
као и много компајлера,

596
00:27:20,360 --> 00:27:23,151
и то не свих ових корака
заједно, а не нужно

597
00:27:23,151 --> 00:27:25,360
излаз неки посредник
датотеке које можете чак и видети.

598
00:27:25,360 --> 00:27:28,400
Само саставља ствари,
што је општи назив који

599
00:27:28,400 --> 00:27:30,000
описује цео овај процес.

600
00:27:30,000 --> 00:27:32,000
Али ако заиста желите
да будемо врло конкретан, ено

601
00:27:32,000 --> 00:27:34,330
много више дешава тамо.

602
00:27:34,330 --> 00:27:38,860
>> Али, хајде да размотримо сада и да чак
то супер једноставан програм, хелло.ц,

603
00:27:38,860 --> 00:27:40,540
назива функција.

604
00:27:40,540 --> 00:27:41,870
То се зове принтф.

605
00:27:41,870 --> 00:27:46,900
Али ја нисам писао принтф, заиста,
који долази са ц, да тако кажем.

606
00:27:46,900 --> 00:27:51,139
То је функција Подсетимо се да је
декларисана у стандардном ио.х, који

607
00:27:51,139 --> 00:27:53,180
је заглавље фајл који
је тема ми заправо ћемо

608
00:27:53,180 --> 00:27:55,780
зарони у дубину више пре времена.

609
00:27:55,780 --> 00:27:58,000
Али заглавље фајл је
обично прати

610
00:27:58,000 --> 00:28:02,920
од датотеци код, Соурце Цоде датотеке, тако
слично постоји стандард ио.х.

611
00:28:02,920 --> 00:28:05,930
>> Негде пре, неко,
или нечији, такође написао

612
00:28:05,930 --> 00:28:11,040
фајл који се зове стандардни ио.ц, у
који су стварни дефиниције,

613
00:28:11,040 --> 00:28:15,220
или имплементације принтф,
и гомиле других функција,

614
00:28:15,220 --> 00:28:16,870
заправо написао.

615
00:28:16,870 --> 00:28:22,140
Дакле, с обзиром да, ако узмемо у обзир да
овде на лево, хелло.ц, када

616
00:28:22,140 --> 00:28:26,250
састављен, нам даје хелло.с, чак и ако
Цланг не смета штедњу у месту

617
00:28:26,250 --> 00:28:31,360
можемо видети, и то код монтажа
бива монтира у хелло.о који

618
00:28:31,360 --> 00:28:34,630
је, заиста, подразумевано име
с обзиром кад год саставити извор

619
00:28:34,630 --> 00:28:39,350
код у објекту код, али нису
потпуно спреман да га изврши још,

620
00:28:39,350 --> 00:28:41,460
јер још један корак
мора да се деси, и има

621
00:28:41,460 --> 00:28:44,440
дешавало у последњих неколико
недеља, можда без знања вас.

622
00:28:44,440 --> 00:28:47,290
>> Конкретно негде
у ЦС50 ИДЕ, и то,

623
00:28:47,290 --> 00:28:49,870
такође, ће бити помало
упрошћавање за тренутак,

624
00:28:49,870 --> 00:28:54,670
постоји, или је упон а тиме,
фајл који се зове стандардни ио.ц,

625
00:28:54,670 --> 00:28:58,440
да неко саставио у
стандардне ио.с или еквивалент,

626
00:28:58,440 --> 00:29:02,010
то онда неко монтира
у стандардном ио.о,

627
00:29:02,010 --> 00:29:04,600
или се испостави у један
мало другачији фајл

628
00:29:04,600 --> 00:29:07,220
формат који може имати другачији
филе укупно продужетак,

629
00:29:07,220 --> 00:29:11,720
али у теорији и концептуално, тачно
ти кораци морало да се деси у некој форми.

630
00:29:11,720 --> 00:29:14,060
Што ће рећи, да је сада
када пишем програм,

631
00:29:14,060 --> 00:29:17,870
хелло.ц, да само каже, здраво свет,
и ја користим код туђем

632
00:29:17,870 --> 00:29:22,480
као принтф, која је Онце Упон А
време, у фајлу названом стандардни ио.ц,

633
00:29:22,480 --> 00:29:26,390
онда некако морам да узмем
објекат код, моји нуле и јединице,

634
00:29:26,390 --> 00:29:29,260
и објекат те особе
код, или нуле и јединице,

635
00:29:29,260 --> 00:29:34,970
и некако их повезују у
једна коначна фајл, под називом здраво, да

636
00:29:34,970 --> 00:29:38,070
има све нуле и
Они из моје основне функције,

637
00:29:38,070 --> 00:29:40,830
и свако од нула
и оне за принтф.

638
00:29:40,830 --> 00:29:44,900
>> И заиста, тај последњи процес
назива, повезујући свој код објекта.

639
00:29:44,900 --> 00:29:47,490
Од чега Излаз
је извршна датотека.

640
00:29:47,490 --> 00:29:49,780
Дакле, у правичност, на
Енд оф тхе даи, ништа

641
00:29:49,780 --> 00:29:52,660
се променило од недеље један, када смо
Први је почео изради програма.

642
00:29:52,660 --> 00:29:55,200
Заиста, све ово је било
дешава испод хаубе,

643
00:29:55,200 --> 00:29:57,241
али сада смо у позицији
где можемо да

644
00:29:57,241 --> 00:29:58,794
задиркивати осим ове различите кораке.

645
00:29:58,794 --> 00:30:00,710
И заиста, на крају
дана, и даље смо

646
00:30:00,710 --> 00:30:04,480
остало нула и јединица, које
је заправо велики Сегуе сада

647
00:30:04,480 --> 00:30:08,620
на другу способности Ц, која
нисмо имали да највероватније искористити

648
00:30:08,620 --> 00:30:11,250
до данас, познат као битовима оператера.

649
00:30:11,250 --> 00:30:15,220
Другим речима, до сада, било кад имамо
бавио података у Ц или променљивих у Ц,

650
00:30:15,220 --> 00:30:17,660
имали смо такве ствари
знакова и плута и компоненте

651
00:30:17,660 --> 00:30:21,990
и чезне и дубл и слично, али
сви они су најмање осам битова.

652
00:30:21,990 --> 00:30:25,550
Никада нисмо увек били у стању да
манипулисати појединачне делове,

653
00:30:25,550 --> 00:30:28,970
иако појединачног бита, ми
знам, могу представљати 0 и 1.

654
00:30:28,970 --> 00:30:32,640
Сада испада да је у Ц, ви
могу добити приступ појединим бита,

655
00:30:32,640 --> 00:30:35,530
ако знате синтаксу,
са којом да се на њих.

656
00:30:35,530 --> 00:30:38,010
>> Дакле, хајде да погледамо
у битовима оператера.

657
00:30:38,010 --> 00:30:41,700
Дакле, на слици ево неколико симболи који
смо, некако, на неки начин, раније.

658
00:30:41,700 --> 00:30:45,580
Видим амперсанд, вертикално
бар и неки други, као,

659
00:30:45,580 --> 00:30:49,430
и сећам се тог амперсанд амперсанд
је нешто што смо раније видели.

660
00:30:49,430 --> 00:30:54,060
Логично и оператер, где имате
њих двојица заједно, или логично ИЛИ

661
00:30:54,060 --> 00:30:56,300
Оператер, где сте
имају два вертикалне пруге.

662
00:30:56,300 --> 00:31:00,550
Битовима оператери, који ћемо
види раде на битовима појединачно,

663
00:31:00,550 --> 00:31:03,810
само користити једну амперсанд, А
једна вертикална бар, Царет симбол

664
00:31:03,810 --> 00:31:06,620
следи, мали
Тилде, а затим напустио

665
00:31:06,620 --> 00:31:08,990
носач лево брацкет, или
Право носач десно конзола.

666
00:31:08,990 --> 00:31:10,770
Сваки од њих има различита значења.

667
00:31:10,770 --> 00:31:11,950
>> У ствари, хајде да погледамо.

668
00:31:11,950 --> 00:31:16,560
Идемо стара школа данас, и употреба
екран осетљив на додир од прошлих,

669
00:31:16,560 --> 00:31:18,002
познат као белу одбор.

670
00:31:18,002 --> 00:31:19,710
А ово бело плоча
ће нам дозволити

671
00:31:19,710 --> 00:31:27,360
да изразим неке прилично једноставне симболе,
односно неке прилично једноставне формуле,

672
00:31:27,360 --> 00:31:29,560
да онда можемо на крају
моћ, како би

673
00:31:29,560 --> 00:31:33,230
индивидуални приступ
бита у оквиру Ц програма.

674
00:31:33,230 --> 00:31:34,480
Другим речима, урадимо то.

675
00:31:34,480 --> 00:31:37,080
Хајде да прво попричамо на
Тренутак за амперсанд,

676
00:31:37,080 --> 00:31:39,560
која је битовима и оператер.

677
00:31:39,560 --> 00:31:42,130
Другим речима, ово је
оператор који омогућава

678
00:31:42,130 --> 00:31:45,930
да има леви променљиву
обично, а десна променљива,

679
00:31:45,930 --> 00:31:50,640
или појединачна вредност, да ако И
их заједно, ми даје коначан резултат.

680
00:31:50,640 --> 00:31:51,560
Па шта мислим?

681
00:31:51,560 --> 00:31:54,840
Ако у програму, имате променљиву
која садржи једну од тих вредности,

682
00:31:54,840 --> 00:31:58,000
или нека буде једноставно и само
написати нула и јединица појединачно,

683
00:31:58,000 --> 00:32:00,940
ево како оператор Амперсанд ради.

684
00:32:00,940 --> 00:32:06,400
0 Амперсанд 0 ће једнака 0.

685
00:32:06,400 --> 00:32:07,210
А зашто је то тако?

686
00:32:07,210 --> 00:32:09,291
>> То је врло слично
Боолеан изрази,

687
00:32:09,291 --> 00:32:10,540
да смо разговарали до сада.

688
00:32:10,540 --> 00:32:15,800
Ако мислите на крају крајева, 0 је
лажна, 0 је лажно, лажно и лажно

689
00:32:15,800 --> 00:32:18,720
је, као што смо разговарали
логички, такође лажна.

690
00:32:18,720 --> 00:32:20,270
Тако смо добили 0 и овде.

691
00:32:20,270 --> 00:32:24,390
Ако узмете 0 амперсанд
1, и то, такође,

692
00:32:24,390 --> 00:32:29,890
ће бити 0, јер је за ово
леви израз да би било истинито или 1,

693
00:32:29,890 --> 00:32:32,360
то би требало да буде истина и истина.

694
00:32:32,360 --> 00:32:36,320
Али овде имамо лажна
и истина, или 0 и 1.

695
00:32:36,320 --> 00:32:42,000
Сада опет, ако имамо 1 амперсанд
0, да, такође, ће бити 0,

696
00:32:42,000 --> 00:32:47,240
и ако имамо 1 амперсанд 1,
коначно да имамо 1 бит.

697
00:32:47,240 --> 00:32:50,340
Другим речима, не радимо
нешто интересантно са овим оператером

698
00:32:50,340 --> 00:32:51,850
још увек, ово Амперсанд оператер.

699
00:32:51,850 --> 00:32:53,780
То је битовима и оператер.

700
00:32:53,780 --> 00:32:57,290
Али ово су састојци
преко којих можемо да урадимо

701
00:32:57,290 --> 00:32:59,240
интересантне ствари, као што ћемо ускоро видети.

702
00:32:59,240 --> 00:33:02,790
>> Сада погледајмо само један
Вертикални бар овде на десној страни.

703
00:33:02,790 --> 00:33:06,710
Ако имам 0 мало и
Или га са, битовима

704
00:33:06,710 --> 00:33:11,030
Оператор ОР, још мало 0,
да ће ми дати 0.

705
00:33:11,030 --> 00:33:17,540
Ако узмем мало и 0 или је са
А 1 мало, онда ћу добити 1.

706
00:33:17,540 --> 00:33:19,830
И, у ствари, само
јасноћа, пусти ме да се вратим,

707
00:33:19,830 --> 00:33:23,380
тако да ми вертикалне пруге
се не варам за 1-а.

708
00:33:23,380 --> 00:33:26,560
Дозволите ми преписати све
мој 1 је мало више

709
00:33:26,560 --> 00:33:32,700
јасно, тако да смо следећи пут видели, ако
су 1 или 0, то ће бити 1,

710
00:33:32,700 --> 00:33:39,060
и ако имам 1 или 1 да,
такође, ће бити 1.

711
00:33:39,060 --> 00:33:42,900
Дакле, можете видети да је логично ИЛИ
оператер понаша сасвим другачије.

712
00:33:42,900 --> 00:33:48,070
То ми даје 0 0 ИЛИ ми даје 0, али
свака друга комбинација ми даје 1.

713
00:33:48,070 --> 00:33:52,480
Докле год имам једну 1 у
формула, резултат ће бити 1.

714
00:33:52,480 --> 00:33:55,580
>> Насупрот АНД
оператер, амперсендом,

715
00:33:55,580 --> 00:34:00,940
само ако имам два 1 је у
једначина, ја заиста повео са 1 аут.

716
00:34:00,940 --> 00:34:02,850
Сада постоји неколико других
оператери као добро.

717
00:34:02,850 --> 00:34:04,810
Један од њих је мало више укључени.

718
00:34:04,810 --> 00:34:07,980
Па нека ми само напред и брисање
то ослободили простор.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
И хајде да погледају
Царет симбол, само на тренутак.

721
00:34:16,460 --> 00:34:18,210
Ово је типично
карактер можете уписати

722
00:34:18,210 --> 00:34:21,420
на тастатура холдинг Схифт и
онда један од бројева вершине иоур САД

723
00:34:21,420 --> 00:34:22,250
тастатура.

724
00:34:22,250 --> 00:34:26,190
>> Дакле, ово је ексклузивни
Оператор ОР, ексклузивно ИЛИ.

725
00:34:26,190 --> 00:34:27,790
Тако смо видели или оператера.

726
00:34:27,790 --> 00:34:29,348
Ово је ексклузивни оператор ОР.

727
00:34:29,348 --> 00:34:30,639
Шта је заправо разлика?

728
00:34:30,639 --> 00:34:34,570
Па хајде да погледамо формулу,
и користити као састојци крају.

729
00:34:34,570 --> 00:34:37,690
0 ЛОЛ 0.

730
00:34:37,690 --> 00:34:39,650
Ја ћу рећи је увек 0.

731
00:34:39,650 --> 00:34:41,400
То је дефиниција КСОР.

732
00:34:41,400 --> 00:34:47,104
0 ЛОЛ 1 ће бити 1.

733
00:34:47,104 --> 00:34:58,810
1 ЛОЛ 0 ће бити 1,
и 1 ЛОЛ 1 ће бити?

734
00:34:58,810 --> 00:34:59,890
Погрешно?

735
00:34:59,890 --> 00:35:00,520
Или зар не?

736
00:35:00,520 --> 00:35:01,860
Не знам.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Сада шта се дешава овде?

739
00:35:04,700 --> 00:35:06,630
Па мислим о
назив овог оператора.

740
00:35:06,630 --> 00:35:09,980
Ексклузивна или, тако да како
име, врста, предлаже,

741
00:35:09,980 --> 00:35:13,940
одговор ће само бити
А 1 ако су улази су ексклузивни,

742
00:35:13,940 --> 00:35:15,560
искључиво другачији.

743
00:35:15,560 --> 00:35:18,170
Дакле, овде су улази су
исти, тако излаз је 0.

744
00:35:18,170 --> 00:35:20,700
Овде су улази су
исти, тако излаз је 0.

745
00:35:20,700 --> 00:35:25,640
Ево резултати су различити, они
су ексклузивни, па излаз је 1.

746
00:35:25,640 --> 00:35:28,190
Тако да је врло слично
И, то је врло слично,

747
00:35:28,190 --> 00:35:32,760
односно врло је сличан
ИЛИ, али само у ексклузивном начин.

748
00:35:32,760 --> 00:35:36,210
Ово више није 1,
јер имамо два 1 је,

749
00:35:36,210 --> 00:35:38,621
а не искључиво, само један од њих.

750
00:35:38,621 --> 00:35:39,120
У реду.

751
00:35:39,120 --> 00:35:40,080
Шта је са осталима?

752
00:35:40,080 --> 00:35:44,220
Велл Тилде, у међувремену, је
стварно лепо и једноставно, на срећу.

753
00:35:44,220 --> 00:35:46,410
И ово је Унарни
оператор, што значи

754
00:35:46,410 --> 00:35:50,400
то применити на само један улаз,
један операнд, да тако кажем.

755
00:35:50,400 --> 00:35:51,800
Не лева и десна.

756
00:35:51,800 --> 00:35:56,050
Другим речима, ако узмете у Тилде
0, одговор ће бити супротно.

757
00:35:56,050 --> 00:35:59,710
А ако узмете Тилде од 1,
одговор ће бити супротно.

758
00:35:59,710 --> 00:36:02,570
Дакле, Тилде оператор
начин негира мало,

759
00:36:02,570 --> 00:36:06,000
или окренете мало из
0 до 1, или 1 до 0.

760
00:36:06,000 --> 00:36:09,820
>> И то нас оставља на крају
са само два финална оператера,

761
00:36:09,820 --> 00:36:13,840
тзв лево смена, а
тзв праву оператер смене.

762
00:36:13,840 --> 00:36:16,620
Хајде да погледамо како ти раду.

763
00:36:16,620 --> 00:36:20,780
Леви оператер помак, написано
са два угластим заградама као да,

764
00:36:20,780 --> 00:36:22,110
ради на следећи начин.

765
00:36:22,110 --> 00:36:27,390
Ако мој улаз, или мој операнда, са леве стране
оператер помак је сасвим једноставно 1.

766
00:36:27,390 --> 00:36:33,750
И онда кажем рачунар са
лево заокрет који 1, рецимо седам места,

767
00:36:33,750 --> 00:36:37,150
резултат је као да сам
Таке Тхат 1, и померите га

768
00:36:37,150 --> 00:36:40,160
седам места у руке
лево, а по дефаулту,

769
00:36:40,160 --> 00:36:42,270
ћемо претпоставити да
простор на десној страни

770
00:36:42,270 --> 00:36:44,080
биће постављен је нула.

771
00:36:44,080 --> 00:36:50,316
Другим речима, 1 је напустио смена 7 иде
да ми то дају 1, затим 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 нуле.

773
00:36:54,060 --> 00:36:57,380
Дакле, на неки начин, то вам омогућава да
узети мали број Лике 1,

774
00:36:57,380 --> 00:37:00,740
и јасно је да много
много, много већи на овај начин,

775
00:37:00,740 --> 00:37:06,460
али ћемо заправо видети
паметнији приступи за то

776
00:37:06,460 --> 00:37:08,080
уместо тога, такође,

777
00:37:08,080 --> 00:37:08,720
>> У реду.

778
00:37:08,720 --> 00:37:10,060
То је то за недељу дана три.

779
00:37:10,060 --> 00:37:11,400
Ми ћемо вас следећи пут.

780
00:37:11,400 --> 00:37:12,770
Ово је ЦС50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [Мусиц плаиинг]

783
00:37:22,243 --> 00:37:25,766
>> СПЕАКЕР 1: Био је у ужину
бар једе Хот Фудге сладолед.

784
00:37:25,766 --> 00:37:28,090
Све је имао преко његовог лица.

785
00:37:28,090 --> 00:37:30,506
Он је носио ту чоколаду као брадом

786
00:37:30,506 --> 00:37:31,756
Звучник 2: Шта радиш?

787
00:37:31,756 --> 00:37:32,422
Спеакер 3: Хммм?

788
00:37:32,422 --> 00:37:33,500
Шта?

789
00:37:33,500 --> 00:37:36,800
>> Звучник 2: Да ли сте само Доубле Дип?

790
00:37:36,800 --> 00:37:38,585
Ви дупло оборена чип.

791
00:37:38,585 --> 00:37:39,460
Спеакер 3: Извините.

792
00:37:39,460 --> 00:37:44,440
Звучник 2: пала си чип, ви
узео залогај, а ти опет оборена.

793
00:37:44,440 --> 00:37:44,940
Спеакер 3:

794
00:37:44,940 --> 00:37:48,440
Звучник 2: Па то је као стављање
Ваш цела десна уста у умак.

795
00:37:48,440 --> 00:37:52,400
Следећи пут када се чип,
Само је уроните једном, и завршити га.

796
00:37:52,400 --> 00:37:53,890
>> Спеакер 3: Знаш шта, Дан?

797
00:37:53,890 --> 00:37:58,006
Ви дип начин на који желите да дип.

798
00:37:58,006 --> 00:38:01,900
Ја ћу дип начин на који желим да дип.

799
00:38:01,900 --> 00:38:03,194