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
Значи ние сме денес овде, не во Сандерс
Театар, наместо во Вајднер библиотека.

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

6
00:00:23,170 --> 00:00:28,310
или ќе кажеме Студио Н, или ќе
ние say-- Ако уживаше дека е шега,

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

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

9
00:00:32,420 --> 00:00:34,270
Сега што е кул за
да се биде овде во студио

10
00:00:34,270 --> 00:00:38,410
е дека јас сум опкружен со овие зелени
ѕидови, зелен екран или 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
>> За сега се потсетиме дека на почетокот на оваа недела
имавме ова cliffhanger, ако сакате,

36
00:01:47,610 --> 00:01:52,560
при што најдобро го правевте сортирање
мудар е горна граница на Биг О на n

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
се сведе на еден n квадрат трчање
време, во најлош случај.

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

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

71
00:03:31,790 --> 00:03:33,620
малку повеќе акција.

72
00:03:33,620 --> 00:03:35,960
Всушност, она што јас барам
при тука на екранот,

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

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

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

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

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

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

79
00:03:56,920 --> 00:03:58,960
Зошто не можеме да само наместо тоа,
да речеме, поопшто,

80
00:03:58,960 --> 00:04:01,500
пребарувате за Мајк во
левата половина од книгата.

81
00:04:01,500 --> 00:04:03,960
>> И обратно, ако Мајк е
всушност подоцна во книгата,

82
00:04:03,960 --> 00:04:07,540
зошто да не само цитат 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
е buzzword за сега,
и тоа е овој процес

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
Па тука е pseudocode, со
кои би можеле да излеземе сортирање,

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
За внесување на n елементи,
со други зборови, ако сте

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

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

111
00:05:22,430 --> 00:05:22,930
Нели?

112
00:05:22,930 --> 00:05:26,430
Бидејќи, ако n е помалку од 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
Сите што рековме е, со оглед на листа на
n елементи, сортирање на левата половина,

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
спојат вид, како на овој pseudocode?

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
Ако pseudocode е ова,
и јас сум се дадени осум елементи,

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
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
И тоа не е сосема најавите на n, но
тука е логаритамска компонента

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
Така да се логирате на n, повторно беше
голем трчање време,

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 од n, па дури и
иако во повеќето часови по математика,

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 од n, но она што е n во овој случај.

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

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

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

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

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

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

398
00:17:36,160 --> 00:17:36,660
Нели?

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
>> Па сега, што друго е вклучена во оваа ситуација? n.

403
00:17:50,180 --> 00:17:53,440
Така да се забележи дека секој
време јас се подели на листата,

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

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
Значи иако висината на овој
дијаграм е со големина n најавите на n или 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
>> Па, јас не n чекори
работат, затоа што ако јас сум

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
е n, па она што се чини дека ние
да има, во крајна линија, е

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

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
беше n чекор, па ние имаме n пати се најавите n,
или како компјутерски инженер би рекол,

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

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

435
00:19:38,200 --> 00:19:39,990
И можете да, вид, видете го тоа овде.

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

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

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-пати, 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
АКО и на друго место во случај ако,
Ако 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
Но, како што рековме, во понеделникот,
постојана време, или Биг О од 1,

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

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

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

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-- Т од n,

466
00:21:09,910 --> 00:21:15,030
трчање време на проблем
кој ги зема n somethings како влез,

467
00:21:15,030 --> 00:21:19,150
еднакво голем o на една,
Ако n е помалку од 2.

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

469
00:21:20,640 --> 00:21:24,150
Така да биде јасно, ако n е помал од
2, имаме една многу кратка листа, тогаш

470
00:21:24,150 --> 00:21:29,151
трчање време, T на 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
>> Па сочно дел сигурно мора да биде во
другиот случај во pseudocode.

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
Па, ако водењето
време да се најде решение за n елементи

479
00:21:49,780 --> 00:21:53,010
е, ајде да го наречеме многу
генерички, T на n,

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

481
00:21:55,500 --> 00:21:59,720
е, вид на, како да кажеш,
T на n поделено со 2,

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

483
00:22:03,000 --> 00:22:06,974
T на 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
Таа се чувствува како тоа е голема о од n чекори?

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

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

491
00:22:25,270 --> 00:22:27,360
>> Така навистина formulaically,
можеме да го изразат тоа,

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

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

494
00:22:31,600 --> 00:22:35,710
Трчање време, Т на n, ако n
е поголемо од или еднакво на 2.

495
00:22:35,710 --> 00:22:42,500
Во овој случај, случајот што друго, е Т на n
поделен со 2, плус на Т Н поделено со 2,

496
00:22:42,500 --> 00:22:45,320
плус голем о на n, некои
линеарни бројот на чекори,

497
00:22:45,320 --> 00:22:51,630
можеби точно n, можеби 2 пати
n, но тоа е грубо, цел на n.

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
но ова е, всушност, ќе се
ни даде голема о од n log n,

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
само по себе е рекурзивен, со т
n над нешто по десната страна,

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

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

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
во моментот работи на спојување вид
само врз основа на нејзините pseudocode.

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
назначено со тоа, отпечатоци, Здраво светот.

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

558
00:25:27,610 --> 00:25:28,430
е токму ова.

559
00:25:28,430 --> 00:25:31,180
Ве однесе вашиот изворен код, да помине
тоа преку компајлер, како ѕвекот,

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

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

562
00:25:37,880 --> 00:25:39,760
во крајна линија го разбира.

563
00:25:39,760 --> 00:25:42,460
>> Излегува дека тоа е
малку на симплификација,

564
00:25:42,460 --> 00:25:44,480
дека сега сме во
позиција да ги разграничат

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

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

567
00:25:48,600 --> 00:25:53,040
секој пат кога ќе се направи програма,
Направете користење и CF 50 ИРО.

568
00:25:53,040 --> 00:25:56,760
Особено, работи како
Ова е прво се создава,

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

570
00:25:58,684 --> 00:26:00,600
Со други зборови, кога ќе
да направиш тест на изворниот код

571
00:26:00,600 --> 00:26:04,390
и состави, што е прв
се емитираат од ѕвекот

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

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

574
00:26:08,990 --> 00:26:11,170
>> Истрчав команда во
командната линија порано.

575
00:26:11,170 --> 00:26:16,260
Ѕвекот цртичка капитал ОК 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
но јас сум се стави на juiciest
информации тука на екранот.

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
И ние исто така имаат здраво светот
обратна коса црта n во наводници долу.

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

584
00:26:42,450 --> 00:26:45,500
дека процесорот на компјутерот го разбира.

585
00:26:45,500 --> 00:26:50,090
Инструкции процесорот, кои се движат меморија
околу себе, дека товарот низи од меморијата,

586
00:26:50,090 --> 00:26:52,750
и на крајот, за печатење
работите на екранот.

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

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

589
00:26:59,964 --> 00:27:02,630
Но чекорите кои имаат навистина
се случува под хаубата

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

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

592
00:27:08,390 --> 00:27:11,930
и оперативни зборови тука се дека,
кога ќе компајлирате вашиот изворен код,

593
00:27:11,930 --> 00:27:16,300
да излезе надвор код собранието, а потоа
кога ќе се соберат вашиот асемблерски код,

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

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

596
00:27:20,360 --> 00:27:23,151
и тоа го прави сите овие чекори
заедно, и тоа не мора да значи

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

598
00:27:25,360 --> 00:27:28,400
Тоа само ги собира нешта,
кој е општ термин кој

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

600
00:27:30,000 --> 00:27:32,000
Но, ако навистина сакаат
да се биде конкретен, има

601
00:27:32,000 --> 00:27:34,330
многу повеќе се случува таму, како и.

602
00:27:34,330 --> 00:27:38,860
>> Но, ајде да исто така, сметаат дека дури и сега
тоа супер едноставна програма, 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, дури и ако
Ѕвекот не се интересира за заштеда на место

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 ИРО, а тоа,

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
остави со нули и единици, кои
е, всушност, голема segue сега

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

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

649
00:30:11,250 --> 00:30:15,220
Со други зборови, досега, во секое време имаме
занимаваа со податоци во C или променливи во C,

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

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
>> Па ајде да ги разгледаме
во bitwise оператори.

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
Bitwise оператори, кои ние ќе
види работат на битови поединечно,

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
кој е bitwise И оператор.

677
00:31:39,560 --> 00:31:42,130
Со други зборови, ова е
оператор кој им овозможува на

678
00:31:42,130 --> 00:31:45,930
мене да има променлива a Лево
Типично, променлива и десната страна,

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
Тоа е bitwise и оператор.

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 малку и јас
Или тоа со, bitwise

704
00:33:06,710 --> 00:33:11,030
ИЛИ оператор, друга 0 бит,
кој ќе ми даде 0.

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

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

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

708
00:33:23,380 --> 00:33:26,560
Дозволете ми да го преработи уште еднаш на сите
мојот 1 е малку повеќе

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

710
00:33:32,700 --> 00:33:39,060
и ако имам 1 или 1, кој,
исто така, се случува да биде 1.

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

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

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

714
00:33:52,480 --> 00:33:55,580
>> Од друга страна со И
оператор, симболот,

715
00:33:55,580 --> 00:34:00,940
само ако имам две 1 во
равенка, можам да всушност се добие 1 надвор.

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

717
00:34:02,850 --> 00:34:04,810
Еден од нив е малку повеќе вклучени.

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

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

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

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

722
00:34:18,210 --> 00:34:21,420
на тастатурата за држење 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