1
00:00:00,000 --> 00:00:11,904
>> [MUSIC PLAYING]

2
00:00:11,904 --> 00:00:12,910
>> PROFESSOR: Bütün hüququ.

3
00:00:12,910 --> 00:00:16,730
Bu CS50 və bu
Həftə üç sonu.

4
00:00:16,730 --> 00:00:20,230
Beləliklə, biz bu gün burada istəyirik, deyil Sanders
Əvəzinə Weidner Kitabxana teatr.

5
00:00:20,230 --> 00:00:23,170
Olan Inside a studio deyil
Hauser Studio kimi tanınan,

6
00:00:23,170 --> 00:00:28,310
və ya biz Studio H demək, və ya edilir edilir
ki, zarafat həzz əgər biz demək,

7
00:00:28,310 --> 00:00:30,540
Bu həqiqətən var
sinif yoldaşı, Mark, online,

8
00:00:30,540 --> 00:00:32,420
olan Twitter vasitəsilə daha çox təklif edir.

9
00:00:32,420 --> 00:00:34,270
İndi haqqında cool nə
bir studiyada burada

10
00:00:34,270 --> 00:00:38,410
Mən bu yaşıl ilə əhatə alıram ki,
divarları, yaşıl ekran və ya chromakey,

11
00:00:38,410 --> 00:00:43,290
belə CS50 nin o deməkdir ki, danışmaq
Mənə unbeknownst istehsal komanda,

12
00:00:43,290 --> 00:00:47,380
İndi, qoyulması ola bilər
Məni ən çox dünyanın hər hansı,

13
00:00:47,380 --> 00:00:48,660
yaxşı və ya pis üçün.

14
00:00:48,660 --> 00:00:51,800
>> İndi nə irəli, problem müəyyən yatır
iki, bu həftə üçün sizin əlinizdədir

15
00:00:51,800 --> 00:00:53,830
lakin problem ilə müəyyən
üç bu gələn həftə

16
00:00:53,830 --> 00:00:56,600
Siz etiraz ediləcək
15 sözdə oyun

17
00:00:56,600 --> 00:00:58,960
köhnə partiya yaxşılıq ki,
Siz qəbul xatırlayıram bilər

18
00:00:58,960 --> 00:01:02,030
bütün dəstə var bir uşaq kimi
aşağı, Slaydı bilər nömrələri,

19
00:01:02,030 --> 00:01:05,790
sol və sağ, və bir boşluq var
puzzle çərçivəsində hansı daxil

20
00:01:05,790 --> 00:01:07,840
həqiqətən o puzzle ədəd slide bilər.

21
00:01:07,840 --> 00:01:11,150
Nəticədə bu almaq
bəzi yarı təsadüfi qaydada puzzle,

22
00:01:11,150 --> 00:01:12,940
və məqsədi üçün
alt, üst sort,

23
00:01:12,940 --> 00:01:16,310
bir, sağ
15 vasitəsilə bütün yol.

24
00:01:16,310 --> 00:01:19,360
>> Təəssüf ki, həyata keçirilməsi
Siz tərəfdən lazımdır

25
00:01:19,360 --> 00:01:21,590
proqram olacaq
based deyil, fiziki.

26
00:01:21,590 --> 00:01:25,280
Siz, həqiqətən, yazmaq olacaq
code hansı bir tələbə və ya istifadəçi ilə

27
00:01:25,280 --> 00:01:26,760
15 oyun oynayır.

28
00:01:26,760 --> 00:01:29,030
Və əslində, hacker da
15 oyun nəşr,

29
00:01:29,030 --> 00:01:32,155
Bir problem həyata keçirmək olacaq,
Bu köhnə məktəb deyil, yalnız oyun

30
00:01:32,155 --> 00:01:35,010
Oyun deyil, həll
bu, Allah rejimi həyata keçirilməsi,

31
00:01:35,010 --> 00:01:38,280
belə ki, danışmaq, həqiqətən,
insan üçün puzzle həll edir,

32
00:01:38,280 --> 00:01:41,080
işarə ilə təmin etməklə,
işarə sonra işarə etdi.

33
00:01:41,080 --> 00:01:42,280
Ki, gələn həftə daha çox.

34
00:01:42,280 --> 00:01:43,720
Amma ki, irəlidə yalan nə var.

35
00:01:43,720 --> 00:01:47,610
>> İndi geri ki, əvvəllər bu həftə
Siz əgər biz, bu cliffhanger idi

36
00:01:47,610 --> 00:01:52,560
vasitəsi biz çeşidlənməsi bunu yaxşı
Müdrik n o böyük bir üst bound idi

37
00:01:52,560 --> 00:01:53,210
kvadrat.

38
00:01:53,210 --> 00:01:56,520
Başqa sözlə, bubble sort,
seçim sort, durub sort,

39
00:01:56,520 --> 00:01:59,120
onların hamısı müxtəlif isə
onların həyata keçirilməsində,

40
00:01:59,120 --> 00:02:03,480
çalışan kvadrat bir n daxil keçir
çox pis halda dəfə.

41
00:02:03,480 --> 00:02:06,010
Və biz ümumiyyətlə güman
çeşidlənməsi üçün çox pis hal

42
00:02:06,010 --> 00:02:08,814
bir ki, giriş deyil
tamamilə geri edir.

43
00:02:08,814 --> 00:02:11,980
Şübhəsiz ki, bu, olduqca bir neçə addımlar atmışdır
bu alqoritmlərin hər həyata keçirilməsi üçün.

44
00:02:11,980 --> 00:02:15,110
>> İndi sinif çox sonunda
Xatırladaq ki, biz bubble sırala müqayisədə

45
00:02:15,110 --> 00:02:19,390
digər bir qarşı seçim sort qarşı
ki, vaxt birləşməsi növ adlı

46
00:02:19,390 --> 00:02:22,120
və mən alaraq ki, təklif
həftə bir dərs üstünlüyü

47
00:02:22,120 --> 00:02:24,060
sıfır, bölmək və fəth.

48
00:02:24,060 --> 00:02:28,810
Və elə bir növ nail olmaq
logarithmic nəticədə vaxt, zaman çalışan,

49
00:02:28,810 --> 00:02:31,024
əvəzinə bir şey
ki, sırf kvadrat var.

50
00:02:31,024 --> 00:02:33,440
Və bu, olduqca loqarifmik deyil
ki, bir az daha var.

51
00:02:33,440 --> 00:02:36,520
Amma sinif geri əgər,
Bu çox daha sürətli, çox idi.

52
00:02:36,520 --> 00:02:38,210
Biz off sol harada nəzər salaq.

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

54
00:02:41,880 --> 00:02:45,370
>> Seçim qarşı bubble sırala
sort daxil sort qarşı.

55
00:02:45,370 --> 00:02:47,700
İndi onlar bütün, yayınlıyorsanız
nəzəriyyəsi, eyni zamanda.

56
00:02:47,700 --> 00:02:50,510
CPU eyni sürətlə çalışan.

57
00:02:50,510 --> 00:02:54,990
Amma necə darıxdırıcı bu hiss edə bilər
çox tez olmaq niyyətindədir,

58
00:02:54,990 --> 00:02:58,790
və necə sürətli, biz zaman yeritmək
Həftə sıfır nin alqoritmlər bir az,

59
00:02:58,790 --> 00:03:00,080
biz hər şeyi sürətləndirmək bilər.

60
00:03:00,080 --> 00:03:01,630
>> Belə ki, mark sort gözəl görünür.

61
00:03:01,630 --> 00:03:05,220
Necə ki, biz üçün, leverage bilər
daha tez nömrələri düzmək üçün.

62
00:03:05,220 --> 00:03:07,140
Yaxşı geri hesab edək
bir tərkib hissəsi olduğunu biz

63
00:03:07,140 --> 00:03:10,380
ki, həftə sıfır geri idi
bir telefon kitab kimsə üçün axtarış,

64
00:03:10,380 --> 00:03:12,380
və geri
biz təklif pseudocode,

65
00:03:12,380 --> 00:03:14,560
olan vasitəsilə biz tapa bilərsiniz
Mike Smith kimi kimsə,

66
00:03:14,560 --> 00:03:16,310
bu kimi bir az bir şey baxdı.

67
00:03:16,310 --> 00:03:20,820
>> İndi xüsusi bir nəzər
xəttində 7 və 8 və 10 və 11,

68
00:03:20,820 --> 00:03:25,240
biz sizə vasitəsi olan ki, loop vadar
yenidən və yenidən geri xətti 3 gedir,

69
00:03:25,240 --> 00:03:26,520
və yenidən.

70
00:03:26,520 --> 00:03:31,790
Amma biz bilərsiniz çıxır ki,
bu alqoritm, burada pseudocode,

71
00:03:31,790 --> 00:03:33,620
daha holistically bir az.

72
00:03:33,620 --> 00:03:35,960
Əslində, mən nə arıyorum
burada ekranda,

73
00:03:35,960 --> 00:03:41,180
üçün axtarış üçün alqoritm
Pages bəzi set arasında Mike Smith.

74
00:03:41,180 --> 00:03:45,520
And olsun ki, biz bu sadələşdirmək bilər
bu xətləri 7 və 8 alqoritm,

75
00:03:45,520 --> 00:03:49,860
10 və 11 yalnız bu demək
Mən sarı burada təqdim etdik.

76
00:03:49,860 --> 00:03:52,210
Başqa sözlə, əgər Mike
Smith, əvvəllər kitab deyil

77
00:03:52,210 --> 00:03:55,004
biz addım müəyyən etmək üçün ehtiyac yoxdur
addım indi necə onu tapmaq getmək üçün.

78
00:03:55,004 --> 00:03:56,920
Biz müəyyən etmək yoxdur
xətti 3 geri,

79
00:03:56,920 --> 00:03:58,960
niyə biz yalnız əvəzinə deyil,
demək, ümumiyyətlə,

80
00:03:58,960 --> 00:04:01,500
Mike üçün axtarış
Kitabın sol yarısı.

81
00:04:01,500 --> 00:04:03,960
>> Əksinə, Mike əgər
həqiqətən sonra kitab,

82
00:04:03,960 --> 00:04:07,540
niyə biz yalnız dırnağı bağlamaq axtarış sitat deyil
Kitabın doğru yarısında Mike üçün.

83
00:04:07,540 --> 00:04:11,030
Başqa sözlə, niyə biz yalnız deyil
sort özümüzü söyləyərək ayaqla zərbə,

84
00:04:11,030 --> 00:04:13,130
Bu Mike üçün axtarış
Kitabın alt,

85
00:04:13,130 --> 00:04:16,279
və mövcud onu tərk
alqoritm bizə

86
00:04:16,279 --> 00:04:18,750
Mike axtarmaq üçün necə
Kitabın ki, sol yarısı.

87
00:04:18,750 --> 00:04:20,750
Başqa sözlə, bizim
alqoritm olsun işləyir

88
00:04:20,750 --> 00:04:24,670
Bu bu qalınlığı bir telefon kitab,
qalınlığı, və ya hər hansı qalınlığı.

89
00:04:24,670 --> 00:04:27,826
Beləliklə, biz recursively bilər
bu alqoritm müəyyən edir.

90
00:04:27,826 --> 00:04:29,950
Başqa sözlə, on
burada ekran alqoritm

91
00:04:29,950 --> 00:04:33,130
Mike Smith üçün axtarış üçün
bir telefon kitab pages arasında.

92
00:04:33,130 --> 00:04:37,410
Belə ki, xətt 7 və 10, edək
yalnız tam olaraq deyirlər.

93
00:04:37,410 --> 00:04:40,250
Mən bu müddət bir an istifadə
əvvəl və həqiqətən, recursion

94
00:04:40,250 --> 00:04:42,450
buzzword, indi üçün
və bu proses var

95
00:04:42,450 --> 00:04:47,210
elə tərəfindən cyclical bir şey bunu
siz artıq kodu istifadə edərək,

96
00:04:47,210 --> 00:04:49,722
və yenə zəng
və yenidən və yenidən.

97
00:04:49,722 --> 00:04:51,930
İndi əhəmiyyətli olacaq
biz elə alt ki

98
00:04:51,930 --> 00:04:53,821
həyata, və sonsuz uzun ki, yoxdur.

99
00:04:53,821 --> 00:04:56,070
Əks halda, biz olacaq
Həqiqətən sonsuz loop var.

100
00:04:56,070 --> 00:04:59,810
Amma biz bu fikir borc bilər əgər in görək
bir recursion, yenə bir şey bunu

101
00:04:59,810 --> 00:05:03,600
və təkrar həll etmək
birləşməsi vasitəsilə çeşidlənməsi problem

102
00:05:03,600 --> 00:05:05,900
sort, bütün daha səmərəli.

103
00:05:05,900 --> 00:05:06,970
>> Mən sizə sort daxil verir.

104
00:05:06,970 --> 00:05:07,920
Bir nəzər salaq.

105
00:05:07,920 --> 00:05:10,850
Belə ki, burada pseudocode ilə,
biz çeşidlənməsi həyata bilər ki,

106
00:05:10,850 --> 00:05:12,640
birləşməsi sort adlanan bu alqoritm istifadə edərək.

107
00:05:12,640 --> 00:05:13,880
Və sadəcə bu var.

108
00:05:13,880 --> 00:05:15,940
N elementlərin yığımı,
başqa sözlə, siz əgər

109
00:05:15,940 --> 00:05:18,830
verilmiş n elementləri və nömrələri və
giriş və ya hər hansı məktublar,

110
00:05:18,830 --> 00:05:22,430
Siz n elementləri, əgər sunulur əgər
n 2 az, yalnız qayıtmaq.

111
00:05:22,430 --> 00:05:22,930
Sağ?

112
00:05:22,930 --> 00:05:26,430
N ki, 2 az, çünki
o deməkdir ki, elementlərin mənim siyahısı

113
00:05:26,430 --> 00:05:30,446
ölçüsü 0 və ya 1 ya və
bu mənasız hallarda, həm də,

114
00:05:30,446 --> 00:05:31,570
siyahısı artıq çeşidlənir.

115
00:05:31,570 --> 00:05:32,810
Heç bir var, bu, sıralanır.

116
00:05:32,810 --> 00:05:35,185
Və uzunluğu bir siyahısı var, əgər
1, açıq-aydın sıralanır.

117
00:05:35,185 --> 00:05:38,280
Belə ki, alqoritm yalnız lazımdır
həqiqətən maraqlı bir şey,

118
00:05:38,280 --> 00:05:40,870
biz iki və ya daha çox varsa
elementləri bizə verilir.

119
00:05:40,870 --> 00:05:42,440
Belə ki, sonra sehrli baxaq.

120
00:05:42,440 --> 00:05:47,500
Else elementləri sol yarım sort,
sonra elementləri sağ yarım sort,

121
00:05:47,500 --> 00:05:49,640
sonra sıralanır yarıya indirir daxil.

122
00:05:49,640 --> 00:05:52,440
Və mind əyilmə cür nə var
burada, mən, həqiqətən, yoxdur ki,

123
00:05:52,440 --> 00:05:56,190
izah etdik görünür
yalnız hələ bir şey, sağ?

124
00:05:56,190 --> 00:05:59,560
All I siyahısını verilir bildirib etdik
n elementləri, sol yarım sort

125
00:05:59,560 --> 00:06:01,800
sonra sağ yarım, sonra
sıralanır yarıya indirir daxil,

126
00:06:01,800 --> 00:06:03,840
lakin faktiki gizli sousu edir?

127
00:06:03,840 --> 00:06:05,260
Alqoritm haradadır?

128
00:06:05,260 --> 00:06:09,150
Yaxşı bu iki xətləri çıxır ki,
ilk elementləri sort sol yarısı,

129
00:06:09,150 --> 00:06:13,970
və elementləri sort sağ yarım,
recursive zənglər, belə ki, danışmaq.

130
00:06:13,970 --> 00:06:16,120
>> Bütün sonra, bu da
vaxt point, mən var

131
00:06:16,120 --> 00:06:18,950
olan bir alqoritm
elementləri bütün dəstə sort?

132
00:06:18,950 --> 00:06:19,450
Bəli.

133
00:06:19,450 --> 00:06:20,620
Bu hüququ burada.

134
00:06:20,620 --> 00:06:25,180
Bu ekranda burada, və
mən addımlar ki, eyni istifadə edə bilərsiniz

135
00:06:25,180 --> 00:06:28,500
sol yarım sort,
sağ yarım mən kimi.

136
00:06:28,500 --> 00:06:30,420
And olsun ki, yenidən və yenidən.

137
00:06:30,420 --> 00:06:34,210
Belə ki, elə ya digər və biz tezliklə lazımdır
, birləşməsi növ sehrli görürük

138
00:06:34,210 --> 00:06:37,967
çox final daxil edilir
line, sorted yarıya indirir birləşməsi.

139
00:06:37,967 --> 00:06:39,300
Və kifayət qədər asan görünür.

140
00:06:39,300 --> 00:06:41,050
Siz iki yarıya indirir, və
elə, onlara birlikdə birləşməsi,

141
00:06:41,050 --> 00:06:43,260
və biz bu görürsünüz
konkret bir anda.

142
00:06:43,260 --> 00:06:45,080
>> Amma bu tam bir alqoritm edir.

143
00:06:45,080 --> 00:06:46,640
Və dəqiq nə görmək bildirin.

144
00:06:46,640 --> 00:06:50,912
Yaxşı bu eyni sunulur Güman
Ekranda burada səkkiz elementləri, bir

145
00:06:50,912 --> 00:06:53,120
səkkiz vasitəsilə, lakin onlar
zahirən təsadüfi qaydada.

146
00:06:53,120 --> 00:06:55,320
Və əl məqsədi
bu elementlər düzmək üçün.

147
00:06:55,320 --> 00:06:58,280
Yaxşı mən necə getmək olar
yenidən istifadə bunu,

148
00:06:58,280 --> 00:07:00,407
Bu pseudocode kimi, sort daxil?

149
00:07:00,407 --> 00:07:02,740
Və yenə, bu ingrain
fikrinizi, yalnız bir an üçün.

150
00:07:02,740 --> 00:07:05,270
ilk işi olduqca
mənasız, bu 2-dən az varsa,

151
00:07:05,270 --> 00:07:07,060
yalnız ediləcək heç bir iş var, qayıtmaq.

152
00:07:07,060 --> 00:07:09,290
Belə ki, həqiqətən yalnız üç var
addımlar həqiqətən unutmayın.

153
00:07:09,290 --> 00:07:11,081
Yenə və yenə mən
etmək istəyirəm olacaq

154
00:07:11,081 --> 00:07:13,980
sol yarım sort,
sağ yarım sort,

155
00:07:13,980 --> 00:07:15,890
və sonra bir dəfə onların
iki yarıya indirir, sıralanır

156
00:07:15,890 --> 00:07:18,710
Mən onlara birlikdə daxil etmək istəyirəm
bir sıralanır siyahısına daxil.

157
00:07:18,710 --> 00:07:19,940
Belə ki, nəzərə ki, saxlamaq.

158
00:07:19,940 --> 00:07:21,310
>> Belə ki, burada orijinal siyahısı.

159
00:07:21,310 --> 00:07:23,510
Nin bu müalicə edək
array, biz başladı

160
00:07:23,510 --> 00:07:25,800
Həftə iki olan bir var
yaddaş bitişik blok.

161
00:07:25,800 --> 00:07:28,480
Bu halda, səkkiz olan
nömrələri, geri geri geri.

162
00:07:28,480 --> 00:07:30,700
Və indi birləşməsi sort tətbiq edək.

163
00:07:30,700 --> 00:07:33,300
Belə ki, mən ilk düzmək istəyirəm
Bu siyahıda sol yarısı,

164
00:07:33,300 --> 00:07:37,370
və buna görə də, edək
4, 8, 6 və 2 yönəldir.

165
00:07:37,370 --> 00:07:41,000
>> İndi haqqında necə getmək yoxdur
ölçüsü 4 bir siyahısını çeşidlənməsi?

166
00:07:41,000 --> 00:07:45,990
Yaxşı mən indi hesab var
sol yarım sol çeşidlənməsi.

167
00:07:45,990 --> 00:07:47,720
Yenə yalnız bir an geri bildirin.

168
00:07:47,720 --> 00:07:51,010
Pseudocode bu deyil,
Mən səkkiz elementləri verilmiş alıram,

169
00:07:51,010 --> 00:07:53,230
8 açıq-aydın böyük
çox və ya 2 bərabər.

170
00:07:53,230 --> 00:07:54,980
Belə ki, ilk işi tətbiq edilmir.

171
00:07:54,980 --> 00:07:58,120
Belə ki, səkkiz elementləri düzmək, mən ilk
elementləri sol yarım sort

172
00:07:58,120 --> 00:08:01,930
sonra mən sonra mən daxil, sağ yarım sort
iki sorted yarıya indirir, ölçüsü 4 hər.

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

174
00:08:02,470 --> 00:08:07,480
>> Yalnız mənə, əgər Lakin, sort
İndi ölçüsü 4 sol yarısı,

175
00:08:07,480 --> 00:08:09,350
necə sol yarım sort yoxdur?

176
00:08:09,350 --> 00:08:11,430
Yaxşı mən bir varsa
dörd elementləri daxil,

177
00:08:11,430 --> 00:08:14,590
Mən ilk sol sort
iki, sonra sağ iki,

178
00:08:14,590 --> 00:08:16,210
və sonra mən onları birlikdə birləşməsi.

179
00:08:16,210 --> 00:08:18,700
Belə ki, yenə, bir az olur
bir ruh burada oyun əyilmə,

180
00:08:18,700 --> 00:08:21,450
çünki cür, var
Siz hekayə olduğu xatırlayıram,

181
00:08:21,450 --> 00:08:23,620
lakin günün sonunda,
elementlərin hər hansı bir sayı nəzərə alaraq,

182
00:08:23,620 --> 00:08:25,620
Siz ilk düzmək istəyirəm
sol yarısı, sonra sağ yarım,

183
00:08:25,620 --> 00:08:26,661
sonra onları birlikdə birləşməsi.

184
00:08:26,661 --> 00:08:28,630
Tam da bunu başlamaq edək.

185
00:08:28,630 --> 00:08:30,170
Burada səkkiz elementləri daxil edir.

186
00:08:30,170 --> 00:08:31,910
İndi biz burada sol yarısında baxırıq.

187
00:08:31,910 --> 00:08:33,720
Necə dörd elementləri sort yoxdur?

188
00:08:33,720 --> 00:08:35,610
Yaxşı mən ilk sol yarım sort.

189
00:08:35,610 --> 00:08:37,720
İndi necə sol yarım sort yoxdur?

190
00:08:37,720 --> 00:08:39,419
Yaxşı mən iki elementləri verilmiş etdik.

191
00:08:39,419 --> 00:08:41,240
Belə ki, bu iki elementləri sort imkan verir.

192
00:08:41,240 --> 00:08:44,540
2 və ya daha çox
2 bərabər, əlbəttə.

193
00:08:44,540 --> 00:08:46,170
Belə ki, birinci halda tətbiq edilmir.

194
00:08:46,170 --> 00:08:49,010
>> Mən indi sol düzmək lazımdır
Bu iki elementləri yarım.

195
00:08:49,010 --> 00:08:50,870
sol yarısı, əlbəttə, yalnız 4.

196
00:08:50,870 --> 00:08:54,020
Belə ki, necə bir element bir siyahısını sort yoxdur?

197
00:08:54,020 --> 00:08:57,960
Yaxşı, indi ki, xüsusi əsas işi
üst qədər, belə ki, danışmaq, tətbiq edilir.

198
00:08:57,960 --> 00:09:01,470
1 az 2 və mənim
siyahısı həqiqətən ölçüsü 1 daşıyır.

199
00:09:01,470 --> 00:09:02,747
Mən yalnız qayıtmaq.

200
00:09:02,747 --> 00:09:03,580
Mən heç bir şey yoxdur.

201
00:09:03,580 --> 00:09:06,770
And olsun ki, mən var nə baxmaq
həyata, 4 artıq çeşidlənir.

202
00:09:06,770 --> 00:09:09,220
Mən artıq deyiləm
burada qismən uğurlu.

203
00:09:09,220 --> 00:09:11,750
>> İndi cür axmaq görünür
iddia, ancaq bu doğru deyil.

204
00:09:11,750 --> 00:09:13,700
4 ölçüsü 1 bir siyahısı.

205
00:09:13,700 --> 00:09:15,090
Bu, artıq sıralanır.

206
00:09:15,090 --> 00:09:16,270
Ki, sol yarım var.

207
00:09:16,270 --> 00:09:18,010
İndi sağ yarım sort.

208
00:09:18,010 --> 00:09:22,310
Mənim input 8, bir elementidir
Eynilə, artıq çeşidlənir.

209
00:09:22,310 --> 00:09:25,170
Stupid, çox amma yenə,
bu əsas prinsipi

210
00:09:25,170 --> 00:09:28,310
İndi qurmaq imkan gedir
bu üst uğurla.

211
00:09:28,310 --> 00:09:32,260
4 İndi, 8 çeşidlənir, sıralaması
ki, ötən addım nə idi?

212
00:09:32,260 --> 00:09:35,330
Belə ki, üçüncü və son addım, hər hansı bir
zaman, siyahısı, geri çeşidlənməsi edirik

213
00:09:35,330 --> 00:09:38,310
iki yarıya indirir daxil idi
sol və sağ.

214
00:09:38,310 --> 00:09:39,900
Belə ki, məhz bunu edək.

215
00:09:39,900 --> 00:09:41,940
Mənim sol yarısı, əlbəttə, 4.

216
00:09:41,940 --> 00:09:43,310
Mənim sağ yarım 8.

217
00:09:43,310 --> 00:09:44,100
>> Belə ki, bunu edək.

218
00:09:44,100 --> 00:09:46,410
Birinci mən ayrılması gedirəm
bəzi əlavə yaddaş,

219
00:09:46,410 --> 00:09:48,680
Mən burada təmsil lazımdır ki,
Yalnız bir orta sıra kimi,

220
00:09:48,680 --> 00:09:49,660
bu uyğun kifayət qədər böyük deyil.

221
00:09:49,660 --> 00:09:52,243
Amma uzanan təsəvvür edə bilərsiniz
ki, düzbucaqlı bütün uzunluğu,

222
00:09:52,243 --> 00:09:53,290
biz daha sonra lazımdır.

223
00:09:53,290 --> 00:09:58,440
4 və 8 və daxil necə
birlikdə ölçüsü 1 bu iki siyahıları?

224
00:09:58,440 --> 00:10:00,270
Burada da olduqca sadə.

225
00:10:00,270 --> 00:10:03,300
4 sonra, ilk gəlir 8 gəlir.

226
00:10:03,300 --> 00:10:07,130
Mən sort istəyirsinizsə Çünki
sol yarısı, sonra sağ yarım,

227
00:10:07,130 --> 00:10:09,900
və sonra bu iki yarıya indirir birləşməsi
birlikdə, sorted üçün,

228
00:10:09,900 --> 00:10:11,940
4 sonra, ilk gəlir 8 gəlir.

229
00:10:11,940 --> 00:10:15,810
>> Beləliklə, biz hətta tərəqqi görünür
Mən heç bir faktiki iş deyil baxmayaraq.

230
00:10:15,810 --> 00:10:17,800
Biz hekayə olduğu Amma unutmayın.

231
00:10:17,800 --> 00:10:19,360
Biz ilk səkkiz elementləri etdi.

232
00:10:19,360 --> 00:10:21,480
Biz 4 sol yarım sıralanır.

233
00:10:21,480 --> 00:10:24,450
Sonra biz sol yarım sıralaması
2 idi sol yarısı.

234
00:10:24,450 --> 00:10:25,270
Və burada biz gedin.

235
00:10:25,270 --> 00:10:26,920
Biz bu addımı ilə tamamlayın.

236
00:10:26,920 --> 00:10:29,930
>> Biz sıralanır, əgər belə
biz indi, 2 yarım buraxdı

237
00:10:29,930 --> 00:10:32,130
2 sağ yarım düzmək lazımdır.

238
00:10:32,130 --> 00:10:35,710
Belə ki, 2 sağ yarısı
Burada bu iki dəyərlər, 6 və 2.

239
00:10:35,710 --> 00:10:40,620
Belə ki, indi ölçüsü bir daxil götürək
2 və sonra sol yarım sort və

240
00:10:40,620 --> 00:10:42,610
sağ yarım və sonra
onlara birlikdə birləşməsi.

241
00:10:42,610 --> 00:10:45,722
Yaxşı necə ölçülü bir siyahısını sort yoxdur
1, yalnız sayı 6 olan?

242
00:10:45,722 --> 00:10:46,430
Mən artıq bitirdim.

243
00:10:46,430 --> 00:10:48,680
Ölçüsü 1 ki siyahısı çeşidlənir.

244
00:10:48,680 --> 00:10:52,140
>> Mən bir siyahısını düzmək necə
ölçüsü 1, qondarma sağ yarım.

245
00:10:52,140 --> 00:10:54,690
Yaxşı, çox, artıq çeşidlənir.

246
00:10:54,690 --> 00:10:56,190
2 nömrəli tək deyil.

247
00:10:56,190 --> 00:11:00,160
Belə ki, indi mən iki yarıya indirir var, sol və
sağ, mən onlara birlikdə daxil etmək lazımdır.

248
00:11:00,160 --> 00:11:01,800
Mənə özümü bəzi əlavə yer verim.

249
00:11:01,800 --> 00:11:05,580
Və, orada 2 qoymaq
sonra 6 orada, bununla

250
00:11:05,580 --> 00:11:10,740
ki, siyahı çeşidlənməsi, sol və sağ
və nəticədə, birlikdə birləşmə.

251
00:11:10,740 --> 00:11:12,160
Belə ki, bir az daha yaxşı forma edirəm.

252
00:11:12,160 --> 00:11:16,250
Mən görülən çünki deyiləm aydın 4, 8, 2,
6 istəyirəm final sifariş deyil.

253
00:11:16,250 --> 00:11:20,640
Amma indi ki, ölçüsü 2 iki siyahıları var
həm də, müvafiq olaraq, sıralanır edilmişdir.

254
00:11:20,640 --> 00:11:24,580
Belə ki, indi sizin fikrinizi nin geri əgər
göz, ​​harada ki, tərk etdiniz?

255
00:11:24,580 --> 00:11:28,520
Mən səkkiz elementləri ilə başladı I
4 sol yarısı aşağı whittled

256
00:11:28,520 --> 00:11:31,386
sonra 2 sol yarısı, və
sonra 2 sağ yarım,

257
00:11:31,386 --> 00:11:34,510
Mən sol çeşidlənməsi, buna görə də, başa
2 yarısı və 2 sağ yarım,

258
00:11:34,510 --> 00:11:37,800
belə üçüncü və son addım burada nə var?

259
00:11:37,800 --> 00:11:41,290
Mən birlikdə daxil etmək üçün var
ölçüsü 2 iki siyahıları.

260
00:11:41,290 --> 00:11:42,040
Belə nin irəli gedək.

261
00:11:42,040 --> 00:11:43,940
Və burada ekranda vermək
Mənə bəzi əlavə yaddaş,

262
00:11:43,940 --> 00:11:47,170
texniki baxmayaraq ki, mən var ki, qeyd
boş up üst bütün dəstə var

263
00:11:47,170 --> 00:11:47,670
var.

264
00:11:47,670 --> 00:11:50,044
Mən xüsusilə olmaq istəyirsinizsə
səmərəli kosmik müdrik,

265
00:11:50,044 --> 00:11:52,960
Mən yalnız elementləri hərəkət başlamaq bilər
geri və irəli, üst və alt.

266
00:11:52,960 --> 00:11:55,460
Amma yalnız vizual aydınlıq üçün,
Mən, aşağıda onu qoymaq gedirəm

267
00:11:55,460 --> 00:11:56,800
gözəl və təmiz şeyi saxlamaq üçün.

268
00:11:56,800 --> 00:11:58,150
>> Beləliklə, mən ölçüsü 2 iki siyahıları var.

269
00:11:58,150 --> 00:11:59,770
ilk siyahısı 4 və 8 var.

270
00:11:59,770 --> 00:12:01,500
İkinci siyahısı 2 və 6 var.

271
00:12:01,500 --> 00:12:03,950
Həmin birləşməsi edək
birlikdə sıralanır üçün.

272
00:12:03,950 --> 00:12:09,910
2, əlbəttə, ilk gəlir
sonra 4, sonra 6, sonra 8.

273
00:12:09,910 --> 00:12:12,560
İndi biz əldə görünür
haradasa maraqlı.

274
00:12:12,560 --> 00:12:15,720
İndi mən sıralanır etdik yarım
siyahısı, və təsadüfən, bu

275
00:12:15,720 --> 00:12:18,650
bütün hətta nömrələri, lakin
, həqiqətən, yalnız bir təsadüf deyil.

276
00:12:18,650 --> 00:12:22,220
Və mən indi sol sıralaması var
yarım, 2, 4, 6 və 8 var ki.

277
00:12:22,220 --> 00:12:23,430
Heç bir şey üçün həyata var.

278
00:12:23,430 --> 00:12:24,620
Ki, davam kimi hiss edir.

279
00:12:24,620 --> 00:12:26,650
>> Mən var kimi İndi hiss
İndi əbədi söhbət,

280
00:12:26,650 --> 00:12:29,850
Belə ki, nə bu halda göründüyü qalır
alqoritm həqiqətən, daha səmərəli edir.

281
00:12:29,850 --> 00:12:31,766
Amma biz vasitəsilə olacaq
Bu super metodik.

282
00:12:31,766 --> 00:12:34,060
Kompüter, əlbəttə,
kimi bunu.

283
00:12:34,060 --> 00:12:34,840
Beləliklə, biz burada?

284
00:12:34,840 --> 00:12:36,180
Biz səkkiz elementləri ilə başladı.

285
00:12:36,180 --> 00:12:37,840
Mən 4 sol yarım sıralanır.

286
00:12:37,840 --> 00:12:39,290
Mən ki, görülən görünür.

287
00:12:39,290 --> 00:12:42,535
Belə ki, indi növbəti addım üçün
4 sağ yarım sort.

288
00:12:42,535 --> 00:12:44,410
Bu hissəsi biz getmək olar
Bir az daha vasitəsilə

289
00:12:44,410 --> 00:12:47,140
tez sen baxmayaraq
yalnız geri və ya fasilə xoş gəlmisiniz

290
00:12:47,140 --> 00:12:49,910
onu vasitəsilə düşünmək
Öz tempi, lakin nə

291
00:12:49,910 --> 00:12:53,290
biz indi bir fürsət var
dörd eyni alqoritm nə

292
00:12:53,290 --> 00:12:54,380
müxtəlif nömrələri.

293
00:12:54,380 --> 00:12:57,740
>> Belə nin irəli gedək və diqqət
biz burada sağ yarım.

294
00:12:57,740 --> 00:13:01,260
ki, sol yarısı
sağ yarım və indi

295
00:13:01,260 --> 00:13:04,560
sol sol yarısı
sağ yarısı yarısı,

296
00:13:04,560 --> 00:13:08,030
Mən ölçüsü siyahısı düzmək necə
1 yalnız sayı 1 olan?

297
00:13:08,030 --> 00:13:09,030
Artıq həyata.

298
00:13:09,030 --> 00:13:11,830
Mən bir siyahısı üçün eyni necə
yalnız 7 olan ölçüsü 1?

299
00:13:11,830 --> 00:13:12,840
Artıq həyata.

300
00:13:12,840 --> 00:13:16,790
Onda bu yarı Step üç
Bu iki elementləri daxil etmək

301
00:13:16,790 --> 00:13:20,889
ölçüsü 2, 1 və 7 yeni siyahısına daxil.

302
00:13:20,889 --> 00:13:23,180
Bütün etmişik görünmür
ki, çox maraqlı iş.

303
00:13:23,180 --> 00:13:24,346
Növbəti nə görmək edək.

304
00:13:24,346 --> 00:13:29,210
Mən yalnız sol yarım sıralanır
mənim orijinal girdi sağ yarım.

305
00:13:29,210 --> 00:13:32,360
İndi hüququ sort imkan
5 və 3 ehtiva yarım.

306
00:13:32,360 --> 00:13:35,740
Yenə sol baxaq
yarım sıralanır, sağ yarım, çeşidlənir,

307
00:13:35,740 --> 00:13:39,120
və birlikdə bu iki birləşməsi
bəzi əlavə kosmosa,

308
00:13:39,120 --> 00:13:41,670
3, sonra ilk gəlir 5 gəlir.

309
00:13:41,670 --> 00:13:46,190
Və indi, biz bilmişik
sağ yarım sol yarısı

310
00:13:46,190 --> 00:13:49,420
orijinal problem və
sağ yarım sağ yarım

311
00:13:49,420 --> 00:13:50,800
orijinal problem.

312
00:13:50,800 --> 00:13:52,480
Üçüncü və son addım nədir?

313
00:13:52,480 --> 00:13:54,854
Yaxşı birlikdə bu iki yarıya indirir daxil etmək üçün.

314
00:13:54,854 --> 00:13:57,020
Belə ki, mənə özümü bir imkan
yenidən əlavə yer, lakin, mən

315
00:13:57,020 --> 00:13:58,699
ki, ehtiyat kosmik up üst istifadə ola bilər.

316
00:13:58,699 --> 00:14:00,490
Amma biz saxlamaq olacaq
vizual sadə.

317
00:14:00,490 --> 00:14:07,070
Mənə indi 1 birləşməsi edək və
sonra 3, sonra 5 və daha sonra 7.

318
00:14:07,070 --> 00:14:10,740
Beləliklə indi məni tərk
orijinal problem sağ yarım

319
00:14:10,740 --> 00:14:12,840
ki, mükəmməl sıralanır.

320
00:14:12,840 --> 00:14:13,662
>> Belə ki, nə qalır?

321
00:14:13,662 --> 00:14:16,120
Deyərək saxlamaq kimi mən hiss edirəm
yenidən və yenidən eyni şeyi,

322
00:14:16,120 --> 00:14:18,700
lakin əks var
biz recursion istifadə etdiyiniz ki.

323
00:14:18,700 --> 00:14:21,050
Bir istifadə prosesi
yenidən və yenidən alqoritm,

324
00:14:21,050 --> 00:14:23,940
kiçik alt çoxluqları
orijinal problem.

325
00:14:23,940 --> 00:14:27,580
Belə ki, indi sol bilmişik
orijinal problem yarısı.

326
00:14:27,580 --> 00:14:30,847
Mən sağ sorted yarısı
orijinal problem.

327
00:14:30,847 --> 00:14:32,180
Üçüncü və son addım nədir?

328
00:14:32,180 --> 00:14:33,590
Oh, bu birləşmə var.

329
00:14:33,590 --> 00:14:34,480
Belə ki, nə edək.

330
00:14:34,480 --> 00:14:36,420
Bəzi əlavə ayrılması bildirin
yaddaş, lakin mənim tanrı, biz

331
00:14:36,420 --> 00:14:37,503
İndi hər yerdə qoymaq bilər.

332
00:14:37,503 --> 00:14:40,356
Biz çox yer var
bizə, lakin biz sadə saxlamaq lazımdır.

333
00:14:40,356 --> 00:14:42,730
Əvəzində geri gedir və
irəli orijinal yaddaş,

334
00:14:42,730 --> 00:14:44,480
yalnız bunu edək
vizual burada aşağı,

335
00:14:44,480 --> 00:14:47,240
birləşmə bitirmək üçün
sol yarısı və sağ yarım.

336
00:14:47,240 --> 00:14:49,279
>> Birləşməsi ilə, belə ki, mən nə etməliyəm?

337
00:14:49,279 --> 00:14:50,820
Mən üçün elementləri etmək istəyirəm.

338
00:14:50,820 --> 00:14:53,230
Belə ki, sol yarım axtarır,
Mən ilk sayı 2 oldu.

339
00:14:53,230 --> 00:14:55,230
Mən yarım baxmaq,
Mən ilk sayı görmək

340
00:14:55,230 --> 00:14:58,290
belə açıq-aydın, 1 olan
nömrəsi, mən dərmək istəyirsiniz

341
00:14:58,290 --> 00:15:00,430
və mənim son siyahısında ilk qoymaq?

342
00:15:00,430 --> 00:15:01,449
Əlbəttə ki, 1.

343
00:15:01,449 --> 00:15:02,990
İndi həmin sual soruşmaq istəyirəm.

344
00:15:02,990 --> 00:15:05,040
Sol yarım, mən var
hələ sayı 2 var.

345
00:15:05,040 --> 00:15:07,490
Sağ yarısında,
Mən sayı 3 var.

346
00:15:07,490 --> 00:15:08,930
Hansı bir mən seçmək istəyirsiniz?

347
00:15:08,930 --> 00:15:11,760
Əlbəttə ki, sayı 2
İndi namizədlər qeyd

348
00:15:11,760 --> 00:15:13,620
sağ sol 3 4 var.

349
00:15:13,620 --> 00:15:15,020
Nin, əlbəttə, 3 seçin bildirin.

350
00:15:15,020 --> 00:15:18,020
İndi namizədlər 4 var
sağ sol, 5.

351
00:15:18,020 --> 00:15:19,460
Biz, əlbəttə, 4 download.

352
00:15:19,460 --> 00:15:21,240
Sağ sol, 5 6.

353
00:15:21,240 --> 00:15:22,730
Biz, əlbəttə, 5 download.

354
00:15:22,730 --> 00:15:25,020
Sağ sol, 7 6.

355
00:15:25,020 --> 00:15:29,320
Biz 6 seçin və sonra biz
7 seçin və sonra biz 8 download.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Sözləri Belə ki, bir çox sonra, biz
səkkiz elementləri bu siyahıda bilmişik

358
00:15:34,370 --> 00:15:38,450
səkkiz vasitəsilə bir siyahısına daxil,
ki, hər bir addım artır ki,

359
00:15:38,450 --> 00:15:40,850
lakin nə qədər vaxt etdi
bunu bizi.

360
00:15:40,850 --> 00:15:43,190
Yaxşı mən qəsdən var
pictorially çəkilmiş şeyi

361
00:15:43,190 --> 00:15:46,330
burada, belə ki, biz növ
və ya şöbə təşəkkür edirik

362
00:15:46,330 --> 00:15:49,060
fəth ki, baş verən edilmişdir.

363
00:15:49,060 --> 00:15:52,830
>> Siz sonra geri baxmaq Həqiqətən, əgər,
Mən bu dotted xətləri bütün tərk etdik

364
00:15:52,830 --> 00:15:55,660
yer sahibləri, siz bilərsiniz,
cür, əks qaydada, bax,

365
00:15:55,660 --> 00:15:58,800
cür geri baxmaq əgər
tarixi, indi mənim orijinal siyahısı

366
00:15:58,800 --> 00:16:00,250
ölçüsü 8, əlbəttə, var.

367
00:16:00,250 --> 00:16:03,480
Və sonra əvvəllər mən
ölçüsü 4 iki siyahıları ilə məşğul olan,

368
00:16:03,480 --> 00:16:08,400
və sonra ölçüsü 2 dörd siyahıları,
və sonra ölçüsü 1 səkkiz siyahıları.

369
00:16:08,400 --> 00:16:10,151
>> Belə ki, bu nə,
cür, sizə xatırlatmaq?

370
00:16:10,151 --> 00:16:11,858
Yaxşı, həqiqətən, hər hansı bir
biz alqoritmlər

371
00:16:11,858 --> 00:16:14,430
indiyə qədər baxdı biz
bölmək və bölmək və bölmək,

372
00:16:14,430 --> 00:16:19,500
yenidən şeyi olan saxlamaq və
yenə bu ümumi fikir ilə nəticələnir.

373
00:16:19,500 --> 00:16:23,100
Və belə bir şey var
logarithmic burada davam.

374
00:16:23,100 --> 00:16:26,790
Və n olduqca log, deyil, lakin
bir logarithmic komponenti var

375
00:16:26,790 --> 00:16:28,280
biz yalnız etdik nə.

376
00:16:28,280 --> 00:16:31,570
>> İndi ki, əslində necə hesab edək.

377
00:16:31,570 --> 00:16:34,481
Belə ki, yenə n daxil olub
böyük çalışan zaman,

378
00:16:34,481 --> 00:16:36,980
biz kimi bir şey idi zaman
ikili axtarış, indi zəng kimi,

379
00:16:36,980 --> 00:16:40,090
bölmək və fəth strategiya
olan vasitəsilə biz Mike Smith tapılmadı.

380
00:16:40,090 --> 00:16:41,020
İndi texniki.

381
00:16:41,020 --> 00:16:43,640
Ki, hətta, n log bazası 2 var
ən riyaziyyat dərslərində də,

382
00:16:43,640 --> 00:16:45,770
10 adətən güman baza var.

383
00:16:45,770 --> 00:16:48,940
Lakin kompüter alimləri həmişə
düşünmək və baza 2 baxımından danışmaq,

384
00:16:48,940 --> 00:16:52,569
belə ki, biz ümumiyyətlə yalnız log demək
n yerinə n log bazasının 2,

385
00:16:52,569 --> 00:16:55,110
lakin onlar tam bir və istəyirik
kompüter dünyada eyni

386
00:16:55,110 --> 00:16:57,234
elm və bir kənara kimi,
daimi amil var

387
00:16:57,234 --> 00:17:01,070
Arasında fərq, bu belə
daha formal səbəblərə görə, hər halda mübahisəli.

388
00:17:01,070 --> 00:17:04,520
>> Amma indi, biz nə qayğı
bu nümunəsidir.

389
00:17:04,520 --> 00:17:08,520
Belə ki, nümunə sübut edək, lakin
ən azı ədəd nümunə istifadə

390
00:17:08,520 --> 00:17:10,730
tərəfdən bir ağlı başında olma çek kimi, Siz.

391
00:17:10,730 --> 00:17:14,510
Belə ki, əvvəllər formula log baza idi
N 2, lakin bu halda n edir.

392
00:17:14,510 --> 00:17:18,526
Mən n orijinal nömrələri idi, və ya 8
orijinal sıra xüsusi.

393
00:17:18,526 --> 00:17:20,359
İndi bir az oldu
isə, amma mən olduqca

394
00:17:20,359 --> 00:17:25,300
əmin log baza 2
8 3 dəyər,

395
00:17:25,300 --> 00:17:29,630
və həqiqətən, nə ki, haqqında gözəl
3. dəfə dəqiq sayı

396
00:17:29,630 --> 00:17:33,320
bir siyahısını bölmək olar ki,
yenidən və yenidən uzunluğu 8,

397
00:17:33,320 --> 00:17:36,160
və yenidən, siz tərk edirik qədər
yalnız ölçüsü 1 siyahıları ilə.

398
00:17:36,160 --> 00:17:36,660
Sağ?

399
00:17:36,660 --> 00:17:40,790
8, 4 gedir 2 gedir,
1 gedir və ki

400
00:17:40,790 --> 00:17:43,470
tam ki, reflective
şəkil biz yalnız bir an əvvəl idi.

401
00:17:43,470 --> 00:17:47,160
Belə ki, bir az ağlı başında olma olduğu kimi deyil
logarithm həqiqətən iştirak edir.

402
00:17:47,160 --> 00:17:50,180
>> Belə ki, indi nə burada iştirak edir? n.

403
00:17:50,180 --> 00:17:53,440
Belə ki, hər fark
dəfə, siyahısı split

404
00:17:53,440 --> 00:17:58,260
tarixində əks qaydada olsa
Burada mən hələ n hər şeyi edirdi.

405
00:17:58,260 --> 00:18:02,320
Bu birləşmə addım tələb
Mən nömrələri hər bir toxunmaq

406
00:18:02,320 --> 00:18:05,060
onu uçmaq üçün
müvafiq yer.

407
00:18:05,060 --> 00:18:10,760
Belə ki, baxmayaraq ki, bu hündürlüyü
diaqram, n və ya 3 ölçüsü log n edir

408
00:18:10,760 --> 00:18:13,860
xüsusi, başqa sözlə,
Burada üç bölmələri etdi.

409
00:18:13,860 --> 00:18:18,800
Nə qədər iş I üfüqi idi
Bu chart hər zaman birlikdə?

410
00:18:18,800 --> 00:18:21,110
>> Bəli, mən n addımlar etdi
Mən var, çünki, iş

411
00:18:21,110 --> 00:18:24,080
, dörd elementləri və dörd elementləri var
və mən birlikdə onlara daxil etmək lazımdır.

412
00:18:24,080 --> 00:18:26,040
Mən keçmək lazımdır
bu dörd və bu dörd,

413
00:18:26,040 --> 00:18:28,123
nəticədə onları daxil etmək üçün
geri səkkiz elementləri daxil.

414
00:18:28,123 --> 00:18:32,182
Əksinə, mən səkkiz barmaqları var
Mən bunu ki, burada, və səkkiz

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry mən var varsa
burada dörd barmaqlarını var

416
00:18:34,390 --> 00:18:37,380
Mən dörd barmaq hansı
burada, mən ki,

417
00:18:37,380 --> 00:18:40,590
o eyni
Məsələn əvvəlki kimi, mən əgər

418
00:18:40,590 --> 00:18:44,010
olsa səkkiz barmaqları var
Mən cür edə bilər ki, ümumi.

419
00:18:44,010 --> 00:18:47,950
Mən dəqiq, burada edə bilərsiniz
sonra əlbəttə bilər

420
00:18:47,950 --> 00:18:50,370
bu siyahıları bütün birləşməsi
birlikdə ölçüsü 1.

421
00:18:50,370 --> 00:18:54,050
Amma əlbəttə ki, baxmaq
hər element dəqiq bir dəfə.

422
00:18:54,050 --> 00:18:59,640
Belə ki, bu prosesin hündürlüyü log n
Bu prosesin eni, belə ki, danışmaq

423
00:18:59,640 --> 00:19:02,490
belə ki, biz görünür nə, n
nəticədə ki, var

424
00:19:02,490 --> 00:19:06,470
ölçüsü n dəfə çalışan zaman n daxil olun.

425
00:19:06,470 --> 00:19:08,977
>> Başqa sözlə, biz bölünür
siyahısı, log n dəfə,

426
00:19:08,977 --> 00:19:11,810
lakin biz etdi hər dəfə biz idi
elementlərin hər bir toxunmaq

427
00:19:11,810 --> 00:19:13,560
onlara daxil etmək üçün
bütün birlikdə olan

428
00:19:13,560 --> 00:19:18,120
addım n, belə ki, biz n dəfə n daxil edilib
və ya kompüter alim deyərdim,

429
00:19:18,120 --> 00:19:20,380
asimptotik olan
böyük söz olardı

430
00:19:20,380 --> 00:19:22,810
yuxarı təsvir etmək
çalışan zaman bağlı,

431
00:19:22,810 --> 00:19:28,010
biz böyük bir o çalışan
Giriş n vaxt, belə danışmaq.

432
00:19:28,010 --> 00:19:31,510
>> İndi bu, çünki əhəmiyyətli
çalışan dəfə idi nə geri

433
00:19:31,510 --> 00:19:34,120
bubble sırala və seçimi ilə
sort və durub sort,

434
00:19:34,120 --> 00:19:38,200
və mövcud hətta bir neçə digər
n biz olduğu idi kvadrat.

435
00:19:38,200 --> 00:19:39,990
Və cür, burada bu bilərsiniz.

436
00:19:39,990 --> 00:19:45,720
N kvadrat əgər açıq-aydın n dəfə
n, lakin burada biz n dəfə n log,

437
00:19:45,720 --> 00:19:48,770
və biz artıq həftə bilirik
sıfır ki, log n, logarithmic,

438
00:19:48,770 --> 00:19:50,550
bir şey xətti daha yaxşıdır.

439
00:19:50,550 --> 00:19:52,930
Bütün sonra, şəkil geri
qırmızı və sarı ilə

440
00:19:52,930 --> 00:19:56,500
biz çəkdi və yaşıl xətləri,
yaşıl logarithmic line çox aşağı idi.

441
00:19:56,500 --> 00:20:00,920
Ona görə də, daha yaxşı və daha sürətli
düz sarı və qırmızı xətləri daha,

442
00:20:00,920 --> 00:20:05,900
n dəfə həqiqətən, n log, daha yaxşı
n dəfədən n, və ya n kvadrat.

443
00:20:05,900 --> 00:20:09,110
>> Belə ki, biz var görünür
alqoritm birləşməsi müəyyən

444
00:20:09,110 --> 00:20:11,870
sort qədər çalışır ki,
sürətli vaxt və həqiqətən,

445
00:20:11,870 --> 00:20:16,560
ki, niyə, bu həftə, zaman var
Biz bubble arasında müsabiqə gördüm

446
00:20:16,560 --> 00:20:20,750
sort, seçim sort və birləşməsi
sort, sort, həqiqətən, həqiqətən qalib birləşməsi.

447
00:20:20,750 --> 00:20:23,660
Həqiqətən, biz hətta gözləmədi
bubble sırala və seçim sort üçün

448
00:20:23,660 --> 00:20:24,790
bitirmək.

449
00:20:24,790 --> 00:20:27,410
>> İndi başqa bir keçid almaq imkan
bu, bir az daha çox

450
00:20:27,410 --> 00:20:31,030
formal perspektiv, yalnız
halda, bu daha yaxşı resonates

451
00:20:31,030 --> 00:20:33,380
ki, yüksək səviyyədə müzakirə çox.

452
00:20:33,380 --> 00:20:34,880
Belə ki, burada alqoritm yenidən var.

453
00:20:34,880 --> 00:20:36,770
Nin özümüz xahiş edək,
nə çalışan zaman

454
00:20:36,770 --> 00:20:39,287
bu müxtəlif addımlar alqoritmlər edir?

455
00:20:39,287 --> 00:20:41,620
Ilk onu bölmək edək
hal ikinci halda.

456
00:20:41,620 --> 00:20:46,280
IF halda IF başqa,
N 2-dən az olarsa, yalnız qayıtmaq.

457
00:20:46,280 --> 00:20:47,580
Daimi vaxt kimi hiss edir.

458
00:20:47,580 --> 00:20:50,970
Bu iki addımlar kimi, cür, var,
N 2-dən az olarsa, onda qayıtmaq.

459
00:20:50,970 --> 00:20:54,580
Amma biz bazar ertəsi dediyi kimi,
daimi vaxt, və ya 1 o böyük,

460
00:20:54,580 --> 00:20:57,130
iki addım, üç ola bilər
addımlar, hətta 1000 addımlar.

461
00:20:57,130 --> 00:20:59,870
Hansı məsələ bu ki,
addımlar daimi nömrəsi.

462
00:20:59,870 --> 00:21:03,240
Belə ki, sarı pseudocode qeyd
Burada biz zəng edəcəyik, çalışır

463
00:21:03,240 --> 00:21:04,490
daimi vaxt.

464
00:21:04,490 --> 00:21:06,780
Belə ki, daha formal və
bu to-- olacaq

465
00:21:06,780 --> 00:21:09,910
dərəcədə olacaq olan biz
n T indi bu hüququ rəsmiləşdirmək,

466
00:21:09,910 --> 00:21:15,030
bir problem çalışan zaman
ki, giriş kimi n somethings edir

467
00:21:15,030 --> 00:21:19,150
, bir o böyük bərabərdir
N 2-dən az olarsa.

468
00:21:19,150 --> 00:21:20,640
Belə ki, ki, şərti var.

469
00:21:20,640 --> 00:21:24,150
N az olduqda, belə ki, aydın olmaq
2, biz sonra, çox qısa bir siyahısı var

470
00:21:24,150 --> 00:21:29,151
n çalışan zaman n, T,
1 və ya 0, bu çox xüsusi halda,

471
00:21:29,151 --> 00:21:30,650
Bu yalnız daimi vaxt olacaq.

472
00:21:30,650 --> 00:21:32,691
Bu bir almaq olacaq
, nə olursa olsun, iki addımlar addım.

473
00:21:32,691 --> 00:21:33,950
Bu addımlar sabit sayı var.

474
00:21:33,950 --> 00:21:38,840
>> Belə ki, şirəli hissəsi şübhəsiz ki, olmalıdır
pseudocode digər halda.

475
00:21:38,840 --> 00:21:40,220
Başqa halda.

476
00:21:40,220 --> 00:21:44,870
Elementlərin Sort sol yarısı, sort sağ
elementlərin yarım, sorted yarıya indirir daxil.

477
00:21:44,870 --> 00:21:46,800
Bu addımlar hər necə sürer?

478
00:21:46,800 --> 00:21:49,780
Yaxşı, əgər çalışan
n elementləri düzmək üçün vaxt

479
00:21:49,780 --> 00:21:53,010
ki, onu çox zəng edək
generically, T n,

480
00:21:53,010 --> 00:21:55,500
sonra sol çeşidlənməsi
elementlərin yarım

481
00:21:55,500 --> 00:21:59,720
ki, növ, deyən kimi,
2 bölünür n T,

482
00:21:59,720 --> 00:22:03,000
və eyni sağ yarım çeşidlənməsi
elementləri var, mehriban, deyən kimi,

483
00:22:03,000 --> 00:22:06,974
N T 2 bölünür və sonra
sıralanır yarıya indirir birləşməsi.

484
00:22:06,974 --> 00:22:08,890
Yaxşı mən var, əgər bəzi
burada elementlərin sayı,

485
00:22:08,890 --> 00:22:11,230
dörd və bəzi sayı kimi
Burada elementləri, dörd kimi,

486
00:22:11,230 --> 00:22:14,650
və mən bu dörd hər birləşməsi var
, və bu dörd hər biri ilə

487
00:22:14,650 --> 00:22:17,160
digər sonra, belə ki,
nəticədə Mən səkkiz elementləri var.

488
00:22:17,160 --> 00:22:20,230
Bu n addımlar o böyük var kimi hiss?

489
00:22:20,230 --> 00:22:23,500
Mən barmaqlarını və hər bir n varsa
Onlara yerə birləşdi var,

490
00:22:23,500 --> 00:22:25,270
başqa n addımlar kimi.

491
00:22:25,270 --> 00:22:27,360
>> Belə ki, həqiqətən formulaically,
biz bu ifadə edə

492
00:22:27,360 --> 00:22:29,960
ilk bir az scarily olsa
nəzər, ancaq bir şey deyil

493
00:22:29,960 --> 00:22:31,600
ki, məhz məntiq gösterir.

494
00:22:31,600 --> 00:22:35,710
çalışan zaman, T n, IF n
və ya daha çox 2 bərabərdir.

495
00:22:35,710 --> 00:22:42,500
Bu halda, başqa halda, n T
2 bölünür n, plus T 2 bölünür,

496
00:22:42,500 --> 00:22:45,320
plus n o böyük, bəzi
addımlar xətti sayı

497
00:22:45,320 --> 00:22:51,630
bəlkə dəqiq n, bəlkə 2 dəfə
n, ancaq təxminən n qaydası var.

498
00:22:51,630 --> 00:22:54,060
Belə ki, çox, necə biz var
formulaically bu bildirirəm.

499
00:22:54,060 --> 00:22:56,809
İndi halda bu bilmək deyil
Siz fikrinizi onu qeyd etdik

500
00:22:56,809 --> 00:22:58,710
və ya bu qədər baxmaq
geri dərslik ki,

501
00:22:58,710 --> 00:23:00,501
bir az ola bilər
sonunda istifadə etmək hesabatı,

502
00:23:00,501 --> 00:23:03,940
lakin bu, həqiqətən, gedir
n log n o böyük bizə vermək,

503
00:23:03,940 --> 00:23:06,620
təkrarlanma çünki
Siz ekranda burada gördükdə

504
00:23:06,620 --> 00:23:09,550
Siz, həqiqətən, ilə, onu əgər
nümunələri sonsuz sayda,

505
00:23:09,550 --> 00:23:13,000
və ya formulaically bunu, siz ki
Bu ki, görəcəksiniz bu formula, çünki

506
00:23:13,000 --> 00:23:17,100
özü t, recursive edir
n sağ şey üzərində,

507
00:23:17,100 --> 00:23:21,680
sol üzərində N t və bu edə bilərsiniz
həqiqətən ifadə edilə, nəticədə,

508
00:23:21,680 --> 00:23:24,339
n log n kimi böyük go.

509
00:23:24,339 --> 00:23:26,130
Razı deyilsə, ki
indi üçün gözəl yalnız

510
00:23:26,130 --> 00:23:28,960
həqiqətən ki, var ki, iman etmək,
ki təkrarlanma səbəb nə

511
00:23:28,960 --> 00:23:31,780
lakin bu yalnız bir az daha
axtarır riyazi yanaşma

512
00:23:31,780 --> 00:23:36,520
birləşməsi növ çalışan zamanda
tək onun pseudocode əsaslanır.

513
00:23:36,520 --> 00:23:39,030
>> İndi bir bir az qoy
ki, bütün breather,

514
00:23:39,030 --> 00:23:41,710
və nəzər
müəyyən keçmiş senator, kim

515
00:23:41,710 --> 00:23:44,260
bir az tanış ola bilər,
olan Google Eric ilə oturdu

516
00:23:44,260 --> 00:23:48,410
Müsahibə üçün bir müddət əvvəl Schmidt,
səhnədə, bütün dəstə qarşısında

517
00:23:48,410 --> 00:23:53,710
insanların, nəticədə söhbət
bir mövzu, olduqca indi tanış var.

518
00:23:53,710 --> 00:23:54,575
Bir nəzər salaq.

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

520
00:24:01,020 --> 00:24:03,890
>> ERIC SCHMIDT: İndi Senator,
Siz Google buradayıq

521
00:24:03,890 --> 00:24:09,490
və mən düşünmək istəyirəm
Bir iş müsahibə kimi başçılığı.

522
00:24:09,490 --> 00:24:11,712
İndi prezident kimi bir iş almaq çətindir.

523
00:24:11,712 --> 00:24:12,670
PREZİDENT OBAMA: Sağ.

524
00:24:12,670 --> 00:24:13,940
ERIC SCHMIDT: Və istəyirik
İndi [işitilemez] edəcəyik.

525
00:24:13,940 --> 00:24:15,523
Google bir iş üçün də çətindir.

526
00:24:15,523 --> 00:24:17,700
PREZİDENT OBAMA: Sağ.

527
00:24:17,700 --> 00:24:21,330
>> ERIC SCHMIDT: Biz suallarınız varsa,
və biz namizədlər sual,

528
00:24:21,330 --> 00:24:24,310
və bu bir Larry Şvimmer edir.

529
00:24:24,310 --> 00:24:25,890
>> PREZİDENT OBAMA: OK.

530
00:24:25,890 --> 00:24:27,005
>> ERIC SCHMIDT: Nə?

531
00:24:27,005 --> 00:24:28,130
Siz uşaqlar I söylüyorum edirəm?

532
00:24:28,130 --> 00:24:30,590
Bu hüququ burada.

533
00:24:30,590 --> 00:24:33,490
Ən səmərəli yolu nədir
bir milyon 32 bit integers düzmək?

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

535
00:24:37,560 --> 00:24:38,979
>> PREZİDENT OBAMA: Well--

536
00:24:38,979 --> 00:24:41,020
ERIC SCHMIDT: Bəzən
bəlkə mən üzüldüm, maybe--

537
00:24:41,020 --> 00:24:42,750
PREZİDENT OBAMA: Yox, yox,
Yox, yox, yox, mən Sizcə

538
00:24:42,750 --> 00:24:43,240
ERIC SCHMIDT: Bu pseudocode deyil

539
00:24:43,240 --> 00:24:45,430
PREZİDENT OBAMA: Mən
hesab edirəm ki, mən hesab edirəm ki, bubble

540
00:24:45,430 --> 00:24:46,875
sort getmək üçün yanlış yol ola bilər.

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

542
00:24:49,619 --> 00:24:50,535
ERIC SCHMIDT: Hadi.

543
00:24:50,535 --> 00:24:52,200
Kim ona bildirib?

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

545
00:24:54,020 --> 00:24:55,590
Mən kompüter elm vermədi Us

546
00:24:55,590 --> 00:24:58,986
>> PREZİDENT OBAMA: Biz var
orada bizim casusları var.

547
00:24:58,986 --> 00:24:59,860
PROFESSOR: Bütün hüququ.

548
00:24:59,860 --> 00:25:03,370
İndi arxamızda buraxsınlar
alqoritmləri nəzəri dünya

549
00:25:03,370 --> 00:25:06,520
asimptotik təhlili
onların və bəzi mövzularda qayıtmaq

550
00:25:06,520 --> 00:25:09,940
həftə sıfır və bir, və başlanğıc
Bəzi təlim təkərlər aradan qaldırılması üçün,

551
00:25:09,940 --> 00:25:10,450
Siz əgər.

552
00:25:10,450 --> 00:25:13,241
Siz, həqiqətən, başa düşürük ki,
nəticədə yerdən, nə

553
00:25:13,241 --> 00:25:16,805
, zaman başlıq altında gedir
yazmaq tərtib və proqramları icra.

554
00:25:16,805 --> 00:25:19,680
Bu idi ki, xüsusilə Xatırladaq
biz baxdı ilk C proqramı,

555
00:25:19,680 --> 00:25:22,840
bir canonical, sadə proqram
növ, nisbətən desək,

556
00:25:22,840 --> 00:25:24,620
orada, o, Hello World görüntüler.

557
00:25:24,620 --> 00:25:27,610
Mən prosesi bildirib Xatırladaq ki,
ki, mənbə kodu keçir

558
00:25:27,610 --> 00:25:28,430
məhz bu.

559
00:25:28,430 --> 00:25:31,180
Siz mənbə kodu almaq keçmək
bir compiler vasitəsilə cingilti kimi,

560
00:25:31,180 --> 00:25:34,650
və ki, obyekt kodunu gəlir
Bu, adet sıfır və olanları kimi baxmaq bilər

561
00:25:34,650 --> 00:25:37,880
kompüter CPU, mərkəzi ki,
processing unit və ya beyin,

562
00:25:37,880 --> 00:25:39,760
nəticədə anlayır.

563
00:25:39,760 --> 00:25:42,460
>> Bu ki, bir var ki, həyata çevirir
bir oversimplification bit,

564
00:25:42,460 --> 00:25:44,480
biz indi istəyirik ki,
mövqe ayrı tease

565
00:25:44,480 --> 00:25:46,720
həqiqətən oldu nə anlamaq üçün
başlıq altında gedir

566
00:25:46,720 --> 00:25:48,600
siz run hər dəfə
Cingilti və ya daha çox, ümumiyyətlə,

567
00:25:48,600 --> 00:25:53,040
hər zaman, bir proqram etmək
etmək və CF 50 IDE istifadə edərək.

568
00:25:53,040 --> 00:25:56,760
Xüsusilə, stuff kimi
Bu ilk yaradılan,

569
00:25:56,760 --> 00:25:58,684
zaman ilk proqram tərtib.

570
00:25:58,684 --> 00:26:00,600
Başqa sözlə, zaman
mənbə kodu almaq

571
00:26:00,600 --> 00:26:04,390
və nə ilk, onu tərtib
cingilti ilə outputted olunur

572
00:26:04,390 --> 00:26:06,370
toplaşmaq kodu kimi tanınan bir şeydir.

573
00:26:06,370 --> 00:26:08,990
Və əslində, məhz bu kimi görünür.

574
00:26:08,990 --> 00:26:11,170
>> Mən bir komanda qaçdı
əvvəllər command line.

575
00:26:11,170 --> 00:26:16,260
Cingilti dash Paytaxtın s hello.c,
bu bir fayl saxla

576
00:26:16,260 --> 00:26:19,490
Mənə deyilən hello.s üçün,
olan daxili dəqiq idi

577
00:26:19,490 --> 00:26:22,290
bu məzmunu, və bir az daha
yuxarıda və daha aşağıda bir az,

578
00:26:22,290 --> 00:26:25,080
amma juiciest gətirdik
burada ekranda məlumat.

579
00:26:25,080 --> 00:26:29,190
Əgər yaxından baxmaq əgər, siz görürsünüz
ən azı bir neçə tanış açar sözlər.

580
00:26:29,190 --> 00:26:31,330
Biz üst əsas var.

581
00:26:31,330 --> 00:26:35,140
Biz ortasında aşağı printf var.

582
00:26:35,140 --> 00:26:38,670
Və biz də dünya salam var
aşağı quotes backslash n.

583
00:26:38,670 --> 00:26:42,450
>> Burada başqa hər şey
çox aşağı səviyyədə təlimatlar

584
00:26:42,450 --> 00:26:45,500
kompüter CPU başa düşür ki,.

585
00:26:45,500 --> 00:26:50,090
Yaddaş hərəkət CPU təlimatları
ətrafında yaddaş yük olduğunu strings,

586
00:26:50,090 --> 00:26:52,750
və nəticədə, çap
ekranda şeylər.

587
00:26:52,750 --> 00:26:56,780
İndi nə sonra, baxmayaraq baş verir
Bu akt code yaradılan?

588
00:26:56,780 --> 00:26:59,964
Nəhayət, siz həqiqətən, etmək,
hələ obyekt kodu yaratmaq.

589
00:26:59,964 --> 00:27:02,630
Amma addımlar həqiqətən var ki,
başlıq altında gedir

590
00:27:02,630 --> 00:27:04,180
bu kimi bir az daha baxmaq.

591
00:27:04,180 --> 00:27:08,390
Source kodu, montaj kodu olur
daha sonra obyekt kodu olur,

592
00:27:08,390 --> 00:27:11,930
və operativ sözlər ki,
Siz mənbə kodu tərtib edərkən,

593
00:27:11,930 --> 00:27:16,300
həyata sonra toplaşmaq kodu və gəlir
Siz toplaşmaq kodu toplaşmaq zaman,

594
00:27:16,300 --> 00:27:17,800
həyata obyekt kodunu gəlir.

595
00:27:17,800 --> 00:27:20,360
>> İndi cingilti, super inkişaf etmiş
derleyiciler bir çox kimi,

596
00:27:20,360 --> 00:27:23,151
və bütün bu addımlar yoxdur
birlikdə və bu mütləq deyil

597
00:27:23,151 --> 00:27:25,360
çıxış hər hansı aralıq
Siz hətta bilərsiniz faylları.

598
00:27:25,360 --> 00:27:28,400
Bu şeyi tərtib,
olan ümumi anlayışdır ki,

599
00:27:28,400 --> 00:27:30,000
Bütün bu prosesi təsvir edir.

600
00:27:30,000 --> 00:27:32,000
Amma həqiqətən istəyirsinizsə
xüsusi olmaq, var

601
00:27:32,000 --> 00:27:34,330
daha çox, eləcə də orada gedir.

602
00:27:34,330 --> 00:27:38,860
>> Amma də hətta indi nəzərdən keçirək
ki, super sadə proqram, hello.c,

603
00:27:38,860 --> 00:27:40,540
bir funksiyası adlanır.

604
00:27:40,540 --> 00:27:41,870
Bu printf çağırıb.

605
00:27:41,870 --> 00:27:46,900
Amma, həqiqətən, printf yazmadım
ki, danışmaq, c ilə gəlir.

606
00:27:46,900 --> 00:27:51,139
Bu bir funksiyası geri var
standart io.h, elan edən

607
00:27:51,139 --> 00:27:53,180
bir mövzu fayl olan
bir mövzu biz, həqiqətən lazımdır deyil

608
00:27:53,180 --> 00:27:55,780
uzun əvvəl daha dərin dalış.

609
00:27:55,780 --> 00:27:58,000
Amma bir mövzu fayl
adətən müşayiət

610
00:27:58,000 --> 00:28:02,920
bir kod fayl, mənbə kodu fayl, belə ki, çox
Standart io.h. mövcuddur çox kimi

611
00:28:02,920 --> 00:28:05,930
>> Zaman əvvəl, kimsə,
və ya kiminsə də yazdı

612
00:28:05,930 --> 00:28:11,040
, standart io.c adlı bir fayl
olan faktiki anlayışlar,

613
00:28:11,040 --> 00:28:15,220
və ya printf tətbiq,
və digər funksiyaları dəstələri,

614
00:28:15,220 --> 00:28:16,870
həqiqətən yazılır.

615
00:28:16,870 --> 00:28:22,140
Biz olan hesab Belə ki, nəzərə alsaq ki,
Burada sol, hello.c haqqında, zaman

616
00:28:22,140 --> 00:28:26,250
tərtib belə, hello.s bizə verir
Cingilti bir yerdə qənaət narahat etmir

617
00:28:26,250 --> 00:28:31,360
biz bunu görürük ki, sərbəst toplaşmaq kodu bilər
hello.o daxil yığılmış olur

618
00:28:31,360 --> 00:28:34,630
, həqiqətən, default adı
Siz mənbə tərtib zaman verildi

619
00:28:34,630 --> 00:28:39,350
object kodu daxil kod, lakin deyil
Hələ bunu icra etmək üçün kifayət qədər hazır,

620
00:28:39,350 --> 00:28:41,460
bir addım, çünki
baş var və var

621
00:28:41,460 --> 00:28:44,440
Son bir neçə üçün hadisə oldu
həftə, sizə bəlkə unbeknownst.

622
00:28:44,440 --> 00:28:47,290
>> Xüsusilə haradasa
CS50 IDE və bu,

623
00:28:47,290 --> 00:28:49,870
də bir bir az olacaq
bir an oversimplification,

624
00:28:49,870 --> 00:28:54,670
var, və ya bir zamanlar idi,
standart io.c adlı bir fayl,

625
00:28:54,670 --> 00:28:58,440
Kimsə tərtib ki,
standart io.s və ya ekvivalent,

626
00:28:58,440 --> 00:29:02,010
Kimsə sonra yığılmış ki,
Standart io.o daxil,

627
00:29:02,010 --> 00:29:04,600
və ya bir daxil çıxır
qədər müxtəlif fayl

628
00:29:04,600 --> 00:29:07,220
fərqli ola bilər format
cəmi uzadılması fayl,

629
00:29:07,220 --> 00:29:11,720
nəzəri və konseptual, dəqiq lakin
bu addımlar hansı formada baş idi.

630
00:29:11,720 --> 00:29:14,060
Demək indi üçün olan
Mən bir proqram yazıram ki,

631
00:29:14,060 --> 00:29:17,870
hello.c, yalnız deyir ki, salam dünya,
və mən başqasının kodu istifadə edirəm

632
00:29:17,870 --> 00:29:22,480
bir sonra bir dəfə printf kimi
vaxt, standart io.c adlı bir fayl,

633
00:29:22,480 --> 00:29:26,390
sonra elə mən mənim Anlık var
obyekt kodu, mənim adet sıfır və olanları,

634
00:29:26,390 --> 00:29:29,260
ki, şəxsin obyekt
kodu və ya adet sıfır və olanları,

635
00:29:29,260 --> 00:29:34,970
və elə onları birlikdə keçid
ki, salam adlı bir final fayl,

636
00:29:34,970 --> 00:29:38,070
var adet sıfır bütün və
mənim əsas funksiyası isə,

637
00:29:38,070 --> 00:29:40,830
və adet sıfır bütün
və printf üçün olanları.

638
00:29:40,830 --> 00:29:44,900
>> And olsun ki, son prosesdir
adlı obyekt kodu birləşdirən.

639
00:29:44,900 --> 00:29:47,490
çıxış edən
bir yürütülebilir fayl.

640
00:29:47,490 --> 00:29:49,780
Belə ki, ədalət, at
gün, heç bir şey sonu

641
00:29:49,780 --> 00:29:52,660
həftə bir ildən dəyişib, biz
ilk proqramları tərtib başladı.

642
00:29:52,660 --> 00:29:55,200
Həqiqətən, bütün bu olmuşdur
başlıq altında baş,

643
00:29:55,200 --> 00:29:57,241
lakin indi biz bir mövqedə deyilik
biz həqiqətən bilərsiniz

644
00:29:57,241 --> 00:29:58,794
bu müxtəlif addımlar ayrı tease.

645
00:29:58,794 --> 00:30:00,710
Həqiqətən, sonunda
gün, biz hələ də istəyirik

646
00:30:00,710 --> 00:30:04,480
adet sıfır və olanları ilə tərk edən
böyük Segue indi əslində

647
00:30:04,480 --> 00:30:08,620
C bir qabiliyyəti ilə, ki,
biz çox güman ki, leverage idi etdik

648
00:30:08,620 --> 00:30:11,250
günə, bitwise operatorları kimi tanınır.

649
00:30:11,250 --> 00:30:15,220
Başqa sözlə, bu günə qədər, zaman biz
C C və ya dəyişənlərin məlumatların ələ,

650
00:30:15,220 --> 00:30:17,660
biz kimi şeylər etdik
chars və üzüb gedirdi və ins

651
00:30:17,660 --> 00:30:21,990
və longs və çiftler və kimi, ancaq
o bütün ən azı səkkiz bit var.

652
00:30:21,990 --> 00:30:25,550
Biz hələ edə heç etdik
fərdi bit manipulyasiya,

653
00:30:25,550 --> 00:30:28,970
hətta fərdi bit olsa, biz
bir 0 və 1 təmsil edə bilər bilirik.

654
00:30:28,970 --> 00:30:32,640
İndi C çıxır ki, siz
fərdi bit əldə edə bilərsiniz,

655
00:30:32,640 --> 00:30:35,530
Siz sintaksis bilirsinizsə,
olan onlara almaq üçün.

656
00:30:35,530 --> 00:30:38,010
>> Belə ki, bir nəzər salaq
bitwise operatorları da.

657
00:30:38,010 --> 00:30:41,700
Belə ki, burada təsvir bir neçə simvol var ki,
biz, mehriban, sort, əvvəl gördüm.

658
00:30:41,700 --> 00:30:45,580
Mən bir şaquli bir işareti görmək
bar, və həmçinin bəzi digər

659
00:30:45,580 --> 00:30:49,430
ki işareti işareti geri
biz əvvəl görmüş bir şey deyil.

660
00:30:49,430 --> 00:30:54,060
siz məntiqi və operator,
Onlar birlikdə, və ya məntiqi OR

661
00:30:54,060 --> 00:30:56,300
operator, harada
iki şaquli barlar var.

662
00:30:56,300 --> 00:31:00,550
Bitwise operatorları alacağıq
fərdi bit fəaliyyət görmək

663
00:31:00,550 --> 00:31:03,810
yalnız bir işareti istifadə edin
bir şaquli bar, caret simvolu

664
00:31:03,810 --> 00:31:06,620
növbəti az gəlir
tilde, və sonra sol

665
00:31:06,620 --> 00:31:08,990
bracket bracket sol, və ya
sağ bracket sağ bracket.

666
00:31:08,990 --> 00:31:10,770
Onların hər biri müxtəlif mənaları var.

667
00:31:10,770 --> 00:31:11,950
>> Əslində, bir nəzər salaq.

668
00:31:11,950 --> 00:31:16,560
Köhnə məktəb bu gün və istifadə gedək
yesteryear bir sensor ekran,

669
00:31:16,560 --> 00:31:18,002
ağ board kimi tanınır.

670
00:31:18,002 --> 00:31:19,710
Və bu ağ board
bizə imkan gedir

671
00:31:19,710 --> 00:31:27,360
Bəzi kifayət qədər sadə rəmzləri ifadə etmək,
daha doğrusu bəzi olduqca sadə düsturlar,

672
00:31:27,360 --> 00:31:29,560
ki, biz son nəticədə sonra bilər
leverage, üçün

673
00:31:29,560 --> 00:31:33,230
fərdi daxil olmaq
C proqramı çərçivəsində bit.

674
00:31:33,230 --> 00:31:34,480
Başqa sözlə, bunu edək.

675
00:31:34,480 --> 00:31:37,080
Bir üçün edək ilk müzakirəsi
işareti haqqında an,

676
00:31:37,080 --> 00:31:39,560
olan bitwise VƏ operatorudur.

677
00:31:39,560 --> 00:31:42,130
Başqa sözlə, bu
imkan verir ki, operator

678
00:31:42,130 --> 00:31:45,930
Mənə bir sol əl dəyişən var
adətən və sağ dəyişən,

679
00:31:45,930 --> 00:31:50,640
və ya fərdi dəyər ki, əgər biz VƏ
birlikdə onlara, mənə bir final nəticə verir.

680
00:31:50,640 --> 00:31:51,560
Belə ki, nə deməkdir?

681
00:31:51,560 --> 00:31:54,840
Bir proqram, bir dəyişən varsa
bu dəyərlərin mağazalar var,

682
00:31:54,840 --> 00:31:58,000
və ya sadə saxlamaq və yalnız imkan
fərdi adet sıfır və olanları yazmaq,

683
00:31:58,000 --> 00:32:00,940
işareti operator işləri necə burada.

684
00:32:00,940 --> 00:32:06,400
0 işareti 0 0 bərabər gedir.

685
00:32:06,400 --> 00:32:07,210
İndi niyə ki?

686
00:32:07,210 --> 00:32:09,291
>> Bu çox oxşar
Boolean ifadələr,

687
00:32:09,291 --> 00:32:10,540
ki, biz bu günə qədər müzakirə etdik.

688
00:32:10,540 --> 00:32:15,800
Bütün sonra düşünüyorsanız, 0
yalan, 0, saxta saxta və yalan

689
00:32:15,800 --> 00:32:18,720
biz müzakirə etdik kimi,
məntiqi də səhv.

690
00:32:18,720 --> 00:32:20,270
Beləliklə, biz də burada 0 almaq.

691
00:32:20,270 --> 00:32:24,390
Siz 0 işareti alsaq
1, yaxşı ki, bu da,

692
00:32:24,390 --> 00:32:29,890
çünki bu, 0 olacaq
sol ifadə, doğru və ya 1 olmaq üçün

693
00:32:29,890 --> 00:32:32,360
Bu doğru və doğru olmaq lazımdır.

694
00:32:32,360 --> 00:32:36,320
Amma burada biz yalan var
və doğru, və ya 0 və 1.

695
00:32:36,320 --> 00:32:42,000
İndi yenə biz 1 işareti varsa
0, çox, 0 olacaq ki,

696
00:32:42,000 --> 00:32:47,240
və biz 1 işareti 1 varsa,
nəhayət, biz 1 az var.

697
00:32:47,240 --> 00:32:50,340
Başqa sözlə, belə ki, biz bunu deyilik
Bu operator ilə maraqlı bir şey

698
00:32:50,340 --> 00:32:51,850
yalnız hələ bu ampersand operator.

699
00:32:51,850 --> 00:32:53,780
Bu bitwise VƏ operator var.

700
00:32:53,780 --> 00:32:57,290
Lakin bu maddələr
olan vasitəsilə biz nə edə

701
00:32:57,290 --> 00:32:59,240
biz tezliklə görəcəksiniz kimi maraqlı şeylər.

702
00:32:59,240 --> 00:33:02,790
>> İndi yalnız bir baxaq
Burada sağ üzərində şaquli bar.

703
00:33:02,790 --> 00:33:06,710
Mən bir az 0 və mən varsa
Və ya bu, bitwise

704
00:33:06,710 --> 00:33:11,030
OR operator, başqa 0 bit,
mənə 0 vermək olacaq.

705
00:33:11,030 --> 00:33:17,540
Mən 0 az və ya onunla əgər
1 bit, sonra 1 almaq üçün gedirəm.

706
00:33:17,540 --> 00:33:19,830
Və əslində, yalnız
aydınlıq, mənə geri gedək

707
00:33:19,830 --> 00:33:23,380
ki, mənim şaquli barlar
1-in üçün səhv deyil.

708
00:33:23,380 --> 00:33:26,560
Mənə bütün yeniden yazmaq edək
mənim 1 bir az daha var

709
00:33:26,560 --> 00:33:32,700
Mən əgər aydın, belə ki, biz növbəti bax
1 və ya 0, ki, 1 olacaq ki,

710
00:33:32,700 --> 00:33:39,060
Mən 1 və ya 1 bir varsa,
də 1 olacaq.

711
00:33:39,060 --> 00:33:42,900
Belə ki, məntiqi və ya ki, bilər
operator çox fərqli davranır.

712
00:33:42,900 --> 00:33:48,070
Bu 0 mənə verir və ya 0 mənə 0 verir, lakin
hər birləşməsi mənə 1 verir.

713
00:33:48,070 --> 00:33:52,480
Belə ki, uzun Mən bir 1 kimi
formula nəticə 1 olacaq.

714
00:33:52,480 --> 00:33:55,580
>> Və əksinə
operator, işareti,

715
00:33:55,580 --> 00:34:00,940
Mən iki 1-nin yalnız əgər
tənlik, Mən, həqiqətən, 1 çıxmaq yoxdur.

716
00:34:00,940 --> 00:34:02,850
İndi bir neçə digər var
operatorları həmçinin.

717
00:34:02,850 --> 00:34:04,810
Onlardan biri bir az daha iştirak edir.

718
00:34:04,810 --> 00:34:07,980
Mənə davam və silmək imkan
bu bir yer azad.

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

720
00:34:13,020 --> 00:34:16,460
Və bir nəzər salaq
yalnız bir an üçün caret simvolu.

721
00:34:16,460 --> 00:34:18,210
Bu adətən var
xarakter siz yazın

722
00:34:18,210 --> 00:34:21,420
klaviatura keçirilməsi Shift və
Sizin ABŞ üstün nömrələri sonra bir

723
00:34:21,420 --> 00:34:22,250
klaviatura.

724
00:34:22,250 --> 00:34:26,190
>> Belə ki, bu eksklüziv
OR operator, xüsusi OR.

725
00:34:26,190 --> 00:34:27,790
Beləliklə, biz yalnız və ya operator gördüm.

726
00:34:27,790 --> 00:34:29,348
Bu xüsusi OR operatorudur.

727
00:34:29,348 --> 00:34:30,639
Həqiqətən fərq nədir?

728
00:34:30,639 --> 00:34:34,570
Yaxşı, yalnız formula baxaq,
və nəticədə maddələr kimi istifadə.

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

730
00:34:37,690 --> 00:34:39,650
Mən demək gedirəm həmişə 0.

731
00:34:39,650 --> 00:34:41,400
Ki, XOR müəyyən edir.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 1 olacaq.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0, 1 olacaq
1 XOR 1 olacaq?

734
00:34:58,810 --> 00:34:59,890
Səhv?

735
00:34:59,890 --> 00:35:00,520
Və ya sağ?

736
00:35:00,520 --> 00:35:01,860
Bilmirəm.

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

738
00:35:02,810 --> 00:35:04,700
İndi nə burada gedir?

739
00:35:04,700 --> 00:35:06,630
Yaxşı düşünmək
Bu operator adı.

740
00:35:06,630 --> 00:35:09,980
Exclusive OR, belə ki,
adı, növü, təklif

741
00:35:09,980 --> 00:35:13,940
cavab yalnız olacaq
1 giriş eksklüziv əgər,

742
00:35:13,940 --> 00:35:15,560
yalnız fərqli.

743
00:35:15,560 --> 00:35:18,170
Belə ki, burada giriş var
Eyni zamanda, belə çıxış 0.

744
00:35:18,170 --> 00:35:20,700
Burada giriş var
Eyni zamanda, belə çıxış 0.

745
00:35:20,700 --> 00:35:25,640
Burada çıxış onlar müxtəlif var
xüsusi və belə çıxış 1.

746
00:35:25,640 --> 00:35:28,190
Belə ki, çox oxşar
AND, bu, çox oxşar

747
00:35:28,190 --> 00:35:32,760
daha doğrusu, bu çox oxşar
OR, lakin yalnız müstəsna şəkildə.

748
00:35:32,760 --> 00:35:36,210
Bu, artıq 1
biz iki 1-nin, çünki,

749
00:35:36,210 --> 00:35:38,621
və yalnız, onlardan yalnız biri.

750
00:35:38,621 --> 00:35:39,120
Oldu.

751
00:35:39,120 --> 00:35:40,080
Nə başqaları haqqında?

752
00:35:40,080 --> 00:35:44,220
Yaxşı tilde, eyni zamanda, var
həqiqətən gözəl və sadə, təşəkkürlə.

753
00:35:44,220 --> 00:35:46,410
Və bu unary deyil
deməkdir operator,

754
00:35:46,410 --> 00:35:50,400
Bu, yalnız bir giriş tətbiq edilir
bir operand, belə danışmaq.

755
00:35:50,400 --> 00:35:51,800
Not sol və sağ.

756
00:35:51,800 --> 00:35:56,050
Başqa sözlə, siz tilde əgər
0 cavab qarşı olacaq.

757
00:35:56,050 --> 00:35:59,710
Və 1 tilde əgər,
Cavab qarşı olacaq.

758
00:35:59,710 --> 00:36:02,570
Belə ki, tilde operator
bir az inkar yolu,

759
00:36:02,570 --> 00:36:06,000
və ya bir az Flipping
0 1 və ya 0 1.

760
00:36:06,000 --> 00:36:09,820
>> Və nəhayət qalırıq
yalnız iki final operatorları ilə,

761
00:36:09,820 --> 00:36:13,840
sol shift sözdə və
sağ shift operator qondarma.

762
00:36:13,840 --> 00:36:16,620
Nin necə bu iş bir nəzər salaq.

763
00:36:16,620 --> 00:36:20,780
yazılı sol shift operator,
ki, kimi iki bucaq mötərizədə ilə,

764
00:36:20,780 --> 00:36:22,110
Aşağıdakı kimi fəaliyyət göstərir.

765
00:36:22,110 --> 00:36:27,390
Əgər sol mənim giriş, və ya operand,
shift operator sadəcə bir 1.

766
00:36:27,390 --> 00:36:33,750
Mən sonra kompüter demək
1, yeddi yerlərdə deyirlər ki, shift sol,

767
00:36:33,750 --> 00:36:37,150
Nəticədə mən sanki var
ki 1 almaq və hərəkət

768
00:36:37,150 --> 00:36:40,160
üzərində yeddi yerlər
sol və ismarıcları,

769
00:36:40,160 --> 00:36:42,270
Biz güman olacaq
sağ space

770
00:36:42,270 --> 00:36:44,080
adet sıfır ilə padded olacaq.

771
00:36:44,080 --> 00:36:50,316
Başqa sözlə, 1 shift 7 gedir sol
təqib, 1 ki, mənə vermək 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 adet sıfır.

773
00:36:54,060 --> 00:36:57,380
Bir şəkildə, belə ki, sizə imkan verir
1 kimi az sayda almaq,

774
00:36:57,380 --> 00:37:00,740
və aydın çox bunu etmək
bu şəkildə çox böyük, çox,

775
00:37:00,740 --> 00:37:06,460
lakin biz, həqiqətən, görmək olacaq
bunun üçün daha ağıllı yanaşmalar

776
00:37:06,460 --> 00:37:08,080
əvəzinə, eləcə də,

777
00:37:08,080 --> 00:37:08,720
>> Oldu.

778
00:37:08,720 --> 00:37:10,060
Bu həftə üç üçün var.

779
00:37:10,060 --> 00:37:11,400
Biz sizə növbəti dəfə görəcəksiniz.

780
00:37:11,400 --> 00:37:12,770
Bu CS50 idi.

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

782
00:37:17,270 --> 00:37:22,243
>> [MUSIC PLAYING]

783
00:37:22,243 --> 00:37:25,766
>> HOPARLÖR 1: O qəlyanaltı idi
isti yalan sundae yemək bar.

784
00:37:25,766 --> 00:37:28,090
O, üzünə bütün idi.

785
00:37:28,090 --> 00:37:30,506
O, bir saqqal kimi ki, şokolad qalıcı

786
00:37:30,506 --> 00:37:31,756
HOPARLÖR 2: Nə edirsən?

787
00:37:31,756 --> 00:37:32,422
HOPARLÖR 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Nə?

789
00:37:33,500 --> 00:37:36,800
>> HOPARLÖR 2: yalnız ikiqat dip mi?

790
00:37:36,800 --> 00:37:38,585
Siz ikiqat chip daldırma.

791
00:37:38,585 --> 00:37:39,460
HOPARLÖR 3: Pardon.

792
00:37:39,460 --> 00:37:44,440
HOPARLÖR 2: Siz, çip daldırma
bir bite etdi və bir daha daldırma.

793
00:37:44,440 --> 00:37:44,940
HOPARLÖR 3:

794
00:37:44,940 --> 00:37:48,440
HOPARLÖR 2: ki qoyulması kimi So
dip sizin bütün ağız hüququ.

795
00:37:48,440 --> 00:37:52,400
Növbəti dəfə, bir chip almaq
yalnız bir dəfə dip, və son.

796
00:37:52,400 --> 00:37:53,890
>> HOPARLÖR 3: Siz, Dan nə bilirik?

797
00:37:53,890 --> 00:37:58,006
Siz dip istədiyiniz dip.

798
00:37:58,006 --> 00:38:01,900
Mən dip istədiyiniz yol dip lazımdır.

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