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
Така че ние сме тук днес, не, в Sanders
Theater, вместо в Weidner Library.

5
00:00:20,230 --> 00:00:23,170
Inside от които е студио
известен като Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
или да кажем Studio H, или ще
ние say-- ако ви хареса, че е шега,

7
00:00:28,310 --> 00:00:30,540
това е действително от
съученик, Mark, онлайн,

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
е, че аз съм заобиколен от тях зелено
стени, зелен екран или chromakey,

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

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
>> Bubble подреди срещу селекция
подреди срещу сливането на сортиране.

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

81
00:04:01,500 --> 00:04:03,960
>> И обратното, ако е Mike
всъщност по-късно в книгата,

82
00:04:03,960 --> 00:04:07,540
защо не просто цитирам цитата търсене
за Mike в дясната половина на книгата.

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

84
00:04:11,030 --> 00:04:13,130
търси за Mike в тази
подмножество на книгата,

85
00:04:13,130 --> 00:04:16,279
и го оставете да съществуващата ни
алгоритъм, за да ни каже

86
00:04:16,279 --> 00:04:18,750
как да търсите Mike в
че лявата половина на книгата.

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
за търсене на Mike Smith
сред страниците на телефонен указател.

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
Else сортирате лявата половина на елементите,
След сортирате дясната половина на елементи,

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
Stupid, също, но отново,
този основен принцип

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

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
Разбира се, един.

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

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
така че ние обикновено просто кажем лог
N, вместо Вход основата 2 на N,

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

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
Така че забележите, че всеки
път I разделя списъка,

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
Така че височината на този процес е дневник п,
ширината на този процес, така да се каже,

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

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
В МФ и другаде по делото IF,
АКО п е по-малко от 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
може да има две, три стъпки
стъпки, дори 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
Така че по-официално, и
отиваме to-- това

465
00:21:06,780 --> 00:21:09,910
ще бъде степента, в която ние
формализира това право now-- T на п,

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

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
е, нека го наречем много
общо, Т на N,

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

481
00:21:55,500 --> 00:21:59,720
е, вид, като да кажеш,
Т на N разделена на две,

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

483
00:22:03,000 --> 00:22:06,974
Т на N разделен 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
>> Така че наистина 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
Времето на работа, T на п, ако п
е по-голямо от или равно на 2.

495
00:22:35,710 --> 00:22:42,500
В този случай, делото ELSE, е T на п
разделена на две, плюс Т N разделена на две,

496
00:22:42,500 --> 00:22:45,320
плюс голям от О N, някои
линейна поредица от стъпки,

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
но това е, наистина, ще
ни даде голяма о п п дневник,

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
и Т на N ляво, това може да
всъщност се изразява в крайна сметка,

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
може да изглежда малко по-запознати,
който седна с Eric на Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, преди известно време, за интервю
на сцената, пред цял куп

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
>> Президентът Обама: OK.

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
Президентът Обама: I
мисля, мисля, че балонът

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
Припомнете си, по-специално, че това е
първата програма C разгледахме,

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

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

561
00:25:34,650 --> 00:25:37,880
че CPU на компютъра, централно
процесор или мозъка,

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

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
Звън пробив капитала 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
Ние ФОРМАТ надолу в средата.

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
че CPU на компютъра разбира.

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
>> Но нека да помисли сега, че дори и
че супер проста програма, hello.c,

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
Това е функция, която е изземване
декларирани в стандартната 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
или реализации на ФОРМАТ,
и букети от други функции,

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, дори ако
Звън не притеснява пестене на място

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
като ФОРМАТ, който някога е бил върху
време, във файл, наречен стандартен 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
и всички нули
и такива за ФОРМАТ.

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
останах с нули и единици, които
всъщност е страхотно Segue сега

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

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

696
00:32:42,000 --> 00:32:47,240
и ако имаме един амперсанд 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 битов и аз
OR го с, битуайз

704
00:33:06,710 --> 00:33:11,030
OR оператор, друг 0 ​​битов,
че ще ми даде 0.

705
00:33:11,030 --> 00:33:17,540
Ако аз взема 0 битова и OR го с
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, че ще бъде един,

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
Докато имам един милион в
формула, резултатът ще бъде един.

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
на вашата клавиатура стопанство Shift и
След това един от номерата на върха си US

723
00:34:21,420 --> 00:34:22,250
клавиатура.

724
00:34:22,250 --> 00:34:26,190
>> Така че това е изключителен
OR оператор, изключителната OR.

725
00:34:26,190 --> 00:34:27,790
Така че ние просто видях оператора OR.

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

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
Wrong?

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
Exclusive OR, така че на
име, вид, предполага,

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

746
00:35:25,640 --> 00:35:28,190
Така че това е много подобен на
И това е много подобна,

747
00:35:28,190 --> 00:35:32,760
или по-скоро това е много подобен на
OR, но само в един изключителен начин.

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

766
00:36:27,390 --> 00:36:33,750
И аз тогава кажете на компютъра, за да
олевяване, че един, казват седем места,

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
>> SPEAKER 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
SPEAKER 2: Какво правиш?

787
00:37:31,756 --> 00:37:32,422
SPEAKER 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Какво?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Знаете ли, просто двоен спад?

790
00:37:36,800 --> 00:37:38,585
Можете двойно потопени чипа.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Извинете ме.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Можете къси чипа, вие
отхапа, а вие потопи отново.

793
00:37:44,440 --> 00:37:44,940
SPEAKER 3:

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Така че това е като да сложиш
целия си прав устата в натопи.

795
00:37:48,440 --> 00:37:52,400
Следващия път, когато се вземат с чип,
Просто го натопи веднъж, и то свърши.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 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