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
Гэта CS50, і гэта
канец тыдня тры.

4
00:00:16,730 --> 00:00:20,230
Так што мы тут сёння, а не ў Сандэрс
Тэатр, замест гэтага ў Weidner бібліятэкі.

5
00:00:20,230 --> 00:00:23,170
Усярэдзіне якога з'яўляецца студыя
вядомы як Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
або, скажам, студыя H, ці павінны
мы say-- калі вам спадабалася, што жарт,

7
00:00:28,310 --> 00:00:30,540
гэта на самай справе ад
аднакласнік, Марк, онлайн,

8
00:00:30,540 --> 00:00:32,420
які прапанаваў столькі з дапамогай Twitter.

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
так бы мовіць, што азначае, што CS50-х
Вытворчасць каманда, без майго ведама

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
у выніку чаго лепш мы рабілі сартавання
мудры быў верхняя мяжа Big O п

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
Іншымі словамі, калі Mike
Сміт раней у кнізе,

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
чаму б нам проста не працытаваць Unquote пошуку
Майка ў правай палове кнігі.

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
Дакладна?

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 сакавік,

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
Дакладна?

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
fingers-- sorry-- калі я
атрымаў чатыры пальца сюды,

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
Такім чынам, вышыня гэтага працэсу часопіса N,
шырыня гэтага працэсу, так бы мовіць,

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
>> Іншымі словамі, мы падзялілі
спіс, часопіс N раз,

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
мы бяжым у Big O
лог н час, так бы мовіць.

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
ПЧ і яшчэ ў тым выпадку, калі,
Калі N менш, чым 2, толькі вяртацца.

457
00:20:46,280 --> 00:20:47,580
Па адчуваннях сталай часу.

458
00:20:47,580 --> 00:20:50,970
Гэта, свайго роду, як два этапы,
Калі N менш, чым 2, а затым вярнуцца.

459
00:20:50,970 --> 00:20:54,580
Але, як мы сказалі, у панядзелак,
пастаянная часу, або Big O 1,

460
00:20:54,580 --> 00:20:57,130
можа быць два, тры крокі
крокі, нават 1000 крокаў.

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
будзе ступень, у якой мы
аформіць гэта права now-- Т п,

466
00:21:09,910 --> 00:21:15,030
час працы задачы
які прымае п нешта ў якасці ўваходных,

467
00:21:15,030 --> 00:21:19,150
роўная Big O з аднаго,
Калі N менш, чым 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
Ён адчувае, як гэта Big O з п крокаў?

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
>> Так сапраўды formulaically,
мы можам выказаць гэта,

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
У гэтым выпадку, у выпадку ELSE, Т п
дзеліцца на 2, плюс Т N дзеліцца на 2,

496
00:22:42,500 --> 00:22:45,320
плюс Big O п, некаторыя
лінейны шэраг крокаў,

497
00:22:45,320 --> 00:22:51,630
магчыма роўна п, можа быць, у 2 разы
п, але гэта прыкладна, парадак п.

498
00:22:51,630 --> 00:22:54,060
Так што, таксама, як мы можам
выказаць гэта formulaically.

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
але гэта, сапраўды, збіраецца
даць нам Big O н часопіса п

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
ці вы зрабілі гэта formulaically, вы б
бачыць, што гэта, таму што гэтай формуле

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
можа выглядаць крыху знаёмыя,
хто сеў з Эрыкам ад Google

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
>> Эрык Шміт: Цяпер сенатар,
Вы тут Google,

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
Гэта таксама цяжка атрымаць працу ў Google.

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
>> Прэзідэнт Абама: Well--

536
00:24:38,979 --> 00:24:41,020
Эрык Шміт: Часам,
можа быць, мне шкада, maybe--

537
00:24:41,020 --> 00:24:42,750
Прэзідэнт Абама: Не, няма,
няма, няма, няма, я think--

538
00:24:42,750 --> 00:24:43,240
Эрык Шміт: Гэта не it--

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
Я не зрабіў інфарматыка on--

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
дзе яна друкуе, Hello World.

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
Вы бераце зыходны код, прайсці
гэта праз кампілятар, як Clang,

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
кожны раз, калі вы робіце праграму,
з дапамогай Марка і CF 50 IDE.

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
і скампіляваць яго, тое, што першы
час выводны Clang

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
Ляск Dash вялікай літары hello.c,
і гэта стварыла файл

576
00:26:16,260 --> 00:26:19,490
для мяне, званых hello.s,
усярэдзіне якога былі дакладна

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
Мы PRINTF пасярэдзіне.

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
>> Цяпер Clang супер складаныя,
як шмат кампілятараў,

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
>> Але давайце таксама разгледзець цяпер, нават
што супер простая праграма, hello.c,

603
00:27:38,860 --> 00:27:40,540
называецца функцыяй.

604
00:27:40,540 --> 00:27:41,870
Ён заклікаў Printf.

605
00:27:41,870 --> 00:27:46,900
Але я не напісаць Printf, сапраўды,
які пастаўляецца з з, так бы мовіць.

606
00:27:46,900 --> 00:27:51,139
Гэта функцыя нагадаем, што гэта
заявіў у стандартным io.h, які

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
файлам кода, файл зыходнага кода, так
гэтак жа, як існуе стандартная io.h.

611
00:28:02,920 --> 00:28:05,930
>> Некаторы час таму, хто-то,
ці каму-небудзь, таксама напісаў

612
00:28:05,930 --> 00:28:11,040
файл называецца стандартным io.c, у
якія фактычныя вызначэння,

613
00:28:11,040 --> 00:28:15,220
або рэалізацыі Printf,
і гронкі іншых функцый,

614
00:28:15,220 --> 00:28:16,870
на самай справе напісана.

615
00:28:16,870 --> 00:28:22,140
Таму, улічваючы, што, калі мы лічым, маючы
тут, на левым, hello.c, што, калі

616
00:28:22,140 --> 00:28:26,250
складзены, дае нам hello.s, нават калі
Clang не турбуе захаванне ў месцы

617
00:28:26,250 --> 00:28:31,360
мы можам убачыць яго, і што зборка код
атрымлівае сабраны ў hello.o, які

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
>> У прыватнасці дзесьці
у CS50 IDE, а гэта,

623
00:28:47,290 --> 00:28:49,870
таксама будзе чымсьці накшталт
спрашчэнне на імгненне,

624
00:28:49,870 --> 00:28:54,670
ёсць, ці быў на той час,
файл называецца стандартным io.c,

625
00:28:54,670 --> 00:28:58,440
што хтосьці сабраны ў
Стандартныя io.s або эквівалент,

626
00:28:58,440 --> 00:29:02,010
што хто-то затым сабраны
у стандартнай io.o,

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
hello.c, што проста кажа, прывітанне свет,
і я з дапамогай кода чужой

632
00:29:17,870 --> 00:29:22,480
як Printf, які быў давным-
Час, у файле пад назвай стандарт io.c,

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
і ўсё нулі
і тыя, для Printf.

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
іншаму магчымасцю C, што
у нас не было, каб выкарыстоўваць, хутчэй за ўсё,

648
00:30:08,620 --> 00:30:11,250
на сённяшні дзень, вядомы як пабітавае аператары.

649
00:30:11,250 --> 00:30:15,220
Іншымі словамі, да гэтага часу, мы ў любы час
справу з дадзенымі ў C або зменных ў C,

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
Цяпер высвятляецца, што ў C, вы
можа атрымаць доступ да асобных бітам,

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
Для доступу да асобных
Біты ў межах праграмы C.

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
>> У адрозненне ад AND
Аператар, Ампэрсанд,

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
На клавіятуры Утрыманне SHIFT і
то адно з лікаў на вяршыні вашага ЗША

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 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Я хачу сказаць, заўсёды 0.

731
00:34:39,650 --> 00:34:41,400
Гэта вызначэнне XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 будзе 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 будзе 1,
і 1 XOR 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
Гэта было CS50.

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