1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Həftə, 3 davamı]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Harvard Universiteti]

3
00:00:04,110 --> 00:00:07,130
>> [Bu CS50 edir. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Bütün hüquqlar. Geri gəlmisiniz. Bu CS50 və bu həftə 3 sonu.

5
00:00:11,010 --> 00:00:14,680
>> Belə ki, o tanımadığı, keçən il Harvard, İnnovasiya Lab deyirlər nə başlayıb

6
00:00:14,680 --> 00:00:18,530
EBM-nin kampus çayı arasında bir gözəl bina olan və ya i-laboratoriya,

7
00:00:18,530 --> 00:00:22,640
ki, kollec tələbələr, GSAS tələbələr, bütün daxilində kampus tələbələr, açıq

8
00:00:22,640 --> 00:00:27,000
fakültə, o cümlədən və yenilikçi şeyi işləmək üçün bir araya gəlib bir yer var,

9
00:00:27,000 --> 00:00:29,180
xüsusilə sahibkarlıq şeylər

10
00:00:29,180 --> 00:00:33,410
Siz və 0 və ya daha dost sahibkarlıq bir şey bunu düşünür əgər

11
00:00:33,410 --> 00:00:37,080
Bu sinif zamanı bu sinif sonra, və ya kənarda da.

12
00:00:37,080 --> 00:00:41,540
>> Belə ki, onlar J müddət ərzində nə etdiklərindən biri, bu səfərlər edir

13
00:00:41,540 --> 00:00:44,510
New York, Silicon Valley üçün olan biri olan biri.

14
00:00:44,510 --> 00:00:47,530
Space çox məhduddur, lakin MBAs ilə təmasda imkan var

15
00:00:47,530 --> 00:00:52,200
və kampus üzrə və faktiki aspirant bu müvafiq sahələrdə vaxt sərf

16
00:00:52,200 --> 00:00:55,500
, startups qədər söhbət sahibkarlar qədər söhbət və s.

17
00:00:55,500 --> 00:00:57,870
Maraqlı Belə ki, bu URL burada oldu.

18
00:00:57,870 --> 00:01:01,220
O, həmçinin, online slaydlar mövcuddur.

19
00:01:01,220 --> 00:01:04,610
>> Biz ton aşağı ev audio yalnız bir az Ola bilərmi?

20
00:01:04,610 --> 00:01:08,640
Bu cümə nahar üçün bizə qoşulmaq istəyirsinizsə, Fire & Ice ilə 1:15 pm, orada rəhbərlik edin.

21
00:01:08,640 --> 00:01:11,390
Əgər üzr şəklində artıq orada almaq zaman doldurulur.

22
00:01:11,390 --> 00:01:13,750
Amma biz bu ənənə irəli davam edəcəyik.

23
00:01:13,750 --> 00:01:17,350
>> Bu gün biz həll edə bilər ki, müxtəlif problemlərin daha yüksək səviyyədə müzakirəsi davam

24
00:01:17,350 --> 00:01:21,330
ən azı, kodu və daha çox ideyaları bu gün çox az diqqət.

25
00:01:21,330 --> 00:01:24,720
Belə ki, yarım bir telefon kitab cırdı zaman geri həftə 0 edirəm

26
00:01:24,720 --> 00:01:28,260
olan obyektiv, bir şey etmək etiraf bir az dramatik oldu

27
00:01:28,260 --> 00:01:32,360
lakin axtarış mütləq olmalıdır deyil nöqtəsinə göndərmək üçün

28
00:01:32,360 --> 00:01:35,100
Sizcə bilər kimi ilk baxışda kimi Aşkar.

29
00:01:35,100 --> 00:01:40,200
Ümumiyyətlə problem mütləq həmişə yaxşı ola bilər -

30
00:01:40,200 --> 00:01:44,130
Ən bariz həll mütləq yaxşı ola bilər.

31
00:01:44,130 --> 00:01:47,300
Belə ki, bu otaq bizim bütün instinktləri idi, səmimi, bu telefon kitab idi və

32
00:01:47,300 --> 00:01:51,470
çox güman ki, sonra Mike Smith axtarır zaman ortada başlamaq və sol və ya sağ getmək

33
00:01:51,470 --> 00:01:54,280
biz başa baş əlifbasının nə məktub əsaslanır.

34
00:01:54,280 --> 00:01:57,560
>> Amma biz insanlar üçün qəbul ki, sadə ideya uzun verilir

35
00:01:57,560 --> 00:02:00,670
həqiqətən fikrinizi önündə gəlməyə başlamaq lazımdır

36
00:02:00,670 --> 00:02:03,900
problemlərin daha kompleks bir telefon kitab çox almaq kimi, çünki

37
00:02:03,900 --> 00:02:07,420
həmin sadə, parlaq anlayışlar bizə imkan gedir nə

38
00:02:07,420 --> 00:02:10,259
daha mürəkkəb və daha maraqlı problemləri həll etmək,

39
00:02:10,259 --> 00:02:12,930
Bu gün artıq təmin üçün onların arasında bəzi şeyləri biz alırıq.

40
00:02:12,930 --> 00:02:15,720
Hələ web orada pages, və Google və Bing və kimi milyardlarla

41
00:02:15,720 --> 00:02:17,660
kimi, bizim üçün hər şeyi tapa bilərlər.

42
00:02:17,660 --> 00:02:22,300
Yəni bütün mümkün web pages axtarış xətti axtarış istifadə edərək, baş deyil.

43
00:02:22,300 --> 00:02:25,290
Facebook, bütün arkadaşlarınızla dost dost və ya kim sizə edə

44
00:02:25,290 --> 00:02:28,250
və çox bu gün anında zahirən edilə bilər

45
00:02:28,250 --> 00:02:30,820
onlar istifadəçilər milyonlarla olsa da.

46
00:02:30,820 --> 00:02:34,250
>> Və biz, həqiqətən, o miqyaslı problemləri həll necə nəticədə azaldacaq

47
00:02:34,250 --> 00:02:37,830
ideyalarına, biz bu gün bir az daha həftə 0 baxdı və.

48
00:02:37,830 --> 00:02:42,320
Biz bu alqoritm yenidən həyata, lakin geri deyil biz də həftə 0 Bu exercise etdi

49
00:02:42,320 --> 00:02:44,780
biz hər kəs ayağa olduğu, 1 nömrəli almaq

50
00:02:44,780 --> 00:02:48,720
və biz birlikdə nömrələri əlavə, off cütləşmə ilə hər kəs özünü sayı olmuşdur

51
00:02:48,720 --> 00:02:51,930
sonra dəstənin yarısı hər iteration haqqında oturdu.

52
00:02:51,930 --> 00:02:56,750
Beləliklə, biz 500 tələbə 250 125 getdi və s.

53
00:02:56,750 --> 00:03:00,080
Amma biz orada deyib kimi, güclü fikir

54
00:03:00,080 --> 00:03:02,460
idi ki, biz bu problem həcmi iki dəfə əgər

55
00:03:02,460 --> 00:03:06,480
Ədliyyə və ya ec 10 bütün uşaq otağa geri gəlib bizə qoşuldu

56
00:03:06,480 --> 00:03:09,510
yaxşı, biz yəqin ki, bütün ümumi qrup saymaq bilər

57
00:03:09,510 --> 00:03:13,380
loop yalnız 1 daha böyük iteration ilə yalnız bəlkə həcmini ikiqat çünki

58
00:03:13,380 --> 00:03:15,630
və ya ikiqat ölçüdə bir az daha EC 10 işində.

59
00:03:15,630 --> 00:03:18,440
Və biz bir az daha çox vaxt sərf etmək olardı

60
00:03:18,440 --> 00:03:22,000
lakin biz 400 və ya 700 daha addımlar sərf olmazdı.

61
00:03:22,000 --> 00:03:26,550
>> Bir az abstrakt ki, bir yol bu şəkil boya, gəlin hər kəs ayağa deyil bildirin.

62
00:03:26,550 --> 00:03:31,100
Amma bu gün orkestr oturub seçən siz bu ağla olmasaydı, dayanan

63
00:03:31,100 --> 00:03:34,580
biz yüksək şəxs olmayan, aranızda anlamaq bilər edək bax

64
00:03:34,580 --> 00:03:36,730
müqayisəli alqoritm eyni cür etməklə.

65
00:03:36,730 --> 00:03:41,830
Siz orkestr, mənim üzr istəyir, lakin addım 1 oturan etdiyiniz əgər, durmaq;

66
00:03:41,830 --> 00:03:44,650
2 adımda, yaxın siz hər off cüt,

67
00:03:44,650 --> 00:03:49,360
taller olan həyata rəqəm və siz qısa əgər oturub.

68
00:03:49,360 --> 00:03:51,360
Sonra deyirəm.

69
00:03:51,360 --> 00:03:56,280
[Tələbələri murmuring]

70
00:04:13,450 --> 00:04:15,320
>> Okay.

71
00:04:15,320 --> 00:04:19,010
Okay. Bir ayaqda qalıb. Sizin adınız nədir? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, siz orkestr hissəsində hündür şəxs bu gün.

73
00:04:21,959 --> 00:04:28,100
>> Tebrik edirik. [Alqış və təzahürat] Okay. Bir oturacaq var. Beləliklə, biz Andrew tapılmadı.

74
00:04:28,100 --> 00:04:30,870
Amma nə qədər mənə etmişlər ki, məsələn, Andrew tapmaq

75
00:04:30,870 --> 00:04:33,740
50 + və ya belə insanların bu orkestr bölməsində?

76
00:04:33,740 --> 00:04:36,900
Mən kifayət qədər sadə yanaşma qəbul və burada başlamaq ola bilər.

77
00:04:36,900 --> 00:04:39,270
Və mən 2 nəfər qalxmaq və yalnız müqayisə

78
00:04:39,270 --> 00:04:42,120
və sonra mən bir az qısa kim demək, "Okay, siz aşağı oturmaq"

79
00:04:42,120 --> 00:04:44,380
Mən taller şəxs olan yadda gedirəm.

80
00:04:44,380 --> 00:04:49,030
Sonra təkrar təkrar təkrar, mən uzun adam üçün asmaq

81
00:04:49,030 --> 00:04:51,920
Mən nöqtədə onlardan daha kimsə az taller tapmaq qədər

82
00:04:51,920 --> 00:04:54,950
bu qədər qısa şəxs sonra oturub var.

83
00:04:54,950 --> 00:04:57,690
Amma bu orkestr bölməsində ki, alqoritm, əgər, siz n var

84
00:04:57,690 --> 00:05:00,480
etmək üçün gedən alqoritm neçə addımlar var? >> [Tələbə] N.

85
00:05:00,480 --> 00:05:03,580
>> Bu, ən pis halda, belə danışmaq, çünki doğru, n almaq olacaq

86
00:05:03,580 --> 00:05:09,090
Ən yüksək şəxs yalnız təsadüfi pis luck ilə almaq son şəxsdir.

87
00:05:09,090 --> 00:05:14,260
Belə ki, ən pis halda ki, alqoritm çalışan zaman xətti, o, n var

88
00:05:14,260 --> 00:05:18,070
n kosmik insanların ümumi sayı, problemin ölçüsü yerləşir.

89
00:05:18,070 --> 00:05:19,600
Bu alqoritm haqqında nə?

90
00:05:19,600 --> 00:05:22,080
Bütün siz yenə yarım sonra qalxıb ki, oturdu

91
00:05:22,080 --> 00:05:23,950
Siz yarım oturdu, siz yarım oturdu.

92
00:05:23,950 --> 00:05:26,070
Siz n burada var ki, əgər neçə addımlar lazımdır?

93
00:05:26,070 --> 00:05:30,200
[Tələbə] N log n. Pis olardı. >> N olun.

94
00:05:30,200 --> 00:05:32,930
>> Belə ki, çox logarithm nə xatırlamıram belə, daxil n

95
00:05:32,930 --> 00:05:38,410
İndi, yalnız bu halving və halving və halving üçün elə bağlıdır ki, yüksək qiymətləndiririk.

96
00:05:38,410 --> 00:05:41,000
2 bir amil yoxdur. Bu 3 amil ola bilər.

97
00:05:41,000 --> 00:05:46,560
Amma bu problem ölçüsü burada başlayır ki, bu amil eyni cür bu təkrar var

98
00:05:46,560 --> 00:05:49,620
lakin sonra dərhal sonra burada, burada, sonra sonra burada, burada gedir.

99
00:05:49,620 --> 00:05:53,580
Siz problem kiçik sokması həyata alaraq deyilik, həqiqətən, ona üz Doğrama edirik

100
00:05:53,580 --> 00:05:56,160
bir böyük ilə swoop hər dəfə azalıb.

101
00:05:56,160 --> 00:06:00,810
Belə ki, biz, 12 ½ və ya 13 nəfər daimi, sonra sonra 25, 50 adam var idi

102
00:06:00,810 --> 00:06:05,370
sonra nəhayət yalnız Andrew qaldı daimi qədər irəli 6 ½ və.

103
00:06:05,370 --> 00:06:08,710
Beləliklə, biz n ki, log zəng olacaq, və bu aşağıdakı kimi görüntüləmək bilər.

104
00:06:08,710 --> 00:06:12,570
Xətti alqoritm var qırmızı xətt kimi yerləşir, burada bu şəkil Xatırladaq

105
00:06:12,570 --> 00:06:17,520
sarı xətt biz hesablanması tələbələr üçün istifadə 2s alqoritm tərəfindən hesablanması idi

106
00:06:17,520 --> 00:06:22,300
keçmişdə, bu gün müqəddəs grail bu yaşıl xətt qalmağa davam edir

107
00:06:22,300 --> 00:06:25,470
biz orkestr bölməsində insanların sayı iki dəfə və ya yalnız söylədi,

108
00:06:25,470 --> 00:06:29,170
cəhənnəm, belə bir böyük iş, ayaq-nin bütün otaqda hər kəs yoxdur bildirin

109
00:06:29,170 --> 00:06:31,560
biz təxminən burada necə bir çox insanlar ikiqat, çünki

110
00:06:31,560 --> 00:06:33,500
1 daha iteration, bir problem.

111
00:06:33,500 --> 00:06:36,200
>> Biz Andrew ya kim Andrew çox taller olmaq olur gördük

112
00:06:36,200 --> 00:06:38,770
bu mezzanine və ya balkon edir.

113
00:06:38,770 --> 00:06:42,140
Bir telefon kitab verilmiş biz çox etdi ki, bu sadə fikri Beləliklə,

114
00:06:42,140 --> 00:06:46,170
biz bunu tətbiq edə bilər ki, bir çox müxtəlif yerlər var ki, bilirik.

115
00:06:46,170 --> 00:06:50,810
Ilk həqiqətən çox jarqon - Just bəzi jarqon sillə üçün

116
00:06:50,810 --> 00:06:52,750
Bu şəkil üçün bura gedək.

117
00:06:52,750 --> 00:06:56,970
Hal-hazırda biz, n və n / 2 danışdı və sonra n daxil

118
00:06:56,970 --> 00:07:00,500
biz dövr ərzində olacaq kimi deyil, biz, şübhəsiz ki, ilə gəlmək olar

119
00:07:00,500 --> 00:07:05,130
riyazi düsturlar digər növ vaxt çalışan bu ümumi anlayışı təsvir etmək.

120
00:07:05,130 --> 00:07:07,580
Uzun əvvəl biz görəcəksiniz çünki bu artıq kontekstində həyata

121
00:07:07,580 --> 00:07:09,900
Bu həqiqətən təmsil alqoritmləri.

122
00:07:09,900 --> 00:07:17,990
>> Amma burada qeyd xətti line n, düz xətt, hazırda işarə həqiqətən çox aşağıdır.

123
00:07:17,990 --> 00:07:22,950
Yəni biz yalnız x axis təmsil nə dəyişdirmək ki, optik illüziya növ var

124
00:07:22,950 --> 00:07:26,130
və y ox və biz istədiyiniz istiqamətdə bir düz xətt nöqtə edə bilərsiniz.

125
00:07:26,130 --> 00:07:30,350
Amma indi zahirən düz olan səbəb

126
00:07:30,350 --> 00:07:35,690
biz çox yavaş çalışan dəfə bu graph haqqında otaq etmək üçün lazım çünki edir.

127
00:07:35,690 --> 00:07:39,030
İndi, həyat bəzi olduqca pis alqoritmlər var bilirik ki,

128
00:07:39,030 --> 00:07:43,790
n addımlar daha çox daxil hələ yaxşı, n addımlar və ya olmayan bəziləri.

129
00:07:43,790 --> 00:07:48,820
Belə ki, xətt yuxarıda n burada alt müddətdə n n dəfə log var

130
00:07:48,820 --> 00:07:51,410
və biz bu əvvəl nə deməkdir görəcəksiniz.

131
00:07:51,410 --> 00:07:56,010
Ki, yuxarıda kvadrat n, biz hələ heç n kvadrat alqoritmlər görmədim amma biz üzeresiniz.

132
00:07:56,010 --> 00:07:57,660
Və həqiqətən, pis görünür.

133
00:07:57,660 --> 00:08:01,610
2 da pis hiss edən exponential bir şey ki, n var.

134
00:08:01,610 --> 00:08:05,760
Və hələ, maraqla, sonra irəlidə düşüncə cür edirsinizsə hansı n Cubed, var

135
00:08:05,760 --> 00:08:10,000
Siz tipli n riyaziyyat, 2 əgər həqiqətən, çox straighter olur

136
00:08:10,000 --> 00:08:15,930
siz uzaq kifayət qədər həyata baltalar baxsaq n çox qədər daha yüksək Cubed.

137
00:08:15,930 --> 00:08:19,890
Belə ki, bu baltalar özbaşına x oxunda 2 10 indi görürük.

138
00:08:19,890 --> 00:08:21,770
>> Və nə deməkdir?

139
00:08:21,770 --> 00:08:23,890
Bu otaqda 2 nəfər üçün 10 nəfər deməkdir.

140
00:08:23,890 --> 00:08:27,200
Problem ölçüsü, kontekstində nə ki: bütün x vasitələri var.

141
00:08:27,200 --> 00:08:30,420
Və şaquli ox hazırda saniyə və ya addımlar sayı sayı -

142
00:08:30,420 --> 00:08:31,840
vaxt bəzi vahid.

143
00:08:31,840 --> 00:08:34,740
Lakin 0 60 0 10 olduğunu görürük.

144
00:08:34,740 --> 00:08:38,549
Lakin əgər Excel və ya bir charting proqram güc kimi, zoom həyata biz növ

145
00:08:38,549 --> 00:08:43,370
və biz bildiriş 200,000 qədər getmək ki, 2 kimi n bir şey

146
00:08:43,370 --> 00:08:47,520
tamamilə kvadrat n çalışan dəfə qorxudaraq gedir

147
00:08:47,520 --> 00:08:50,960
n Cubed, n log n - biz bu günə qədər haqqında söhbət etdik hər şey.

148
00:08:50,960 --> 00:08:54,190
Facebook kimi şeylər haqqında danışmağa başlamaq zaman hələ tutmaq deyil

149
00:08:54,190 --> 00:08:57,150
bir çox, bir çox, bir çox insanların bütün qarşılıqlı olduğu,

150
00:08:57,150 --> 00:09:00,650
insanların n hər kimə n dost kimi çox ola bilər

151
00:09:00,650 --> 00:09:02,860
hər kəs dünyada dost-dost növ edir, əgər

152
00:09:02,860 --> 00:09:08,100
yaxşı ki, n dəfə var n artıq, belə kvadrat mümkün dostluq n ki,

153
00:09:08,100 --> 00:09:10,950
ən azı 1 istiqamət, n kvadrat mümkün dostluq edir.

154
00:09:10,950 --> 00:09:15,330
Belə ki, artıq belə danışmaq, Facebook sosial graph axtarış ki,

155
00:09:15,330 --> 00:09:18,090
düsturlar bu cür ifadə etmək başlaya bilərsiniz.

156
00:09:18,090 --> 00:09:19,820
>> Biz geri qayıtmaq və bu, daha konkret edəcəyik

157
00:09:19,820 --> 00:09:23,280
növbəti çox həftə indi üçün, obyektiv

158
00:09:23,280 --> 00:09:27,170
həyata alqoritmlər və kodu haqqında getmək üçün əmin olacaq

159
00:09:27,170 --> 00:09:29,870
bu kimi bir şey kimi daha çox vaxt ayırdığınız qədər sonu.

160
00:09:29,870 --> 00:09:33,110
Ancaq kompüter haqqında maraqlı şey bu sahədə davam əgər

161
00:09:33,110 --> 00:09:38,320
, CS121, CS124 kimi dərsləri nəzəriyyə kursları edilir və bu alaraq,

162
00:09:38,320 --> 00:09:41,300
Bu dünyada mövcud olan bəzi problemlər həqiqətən var ki

163
00:09:41,300 --> 00:09:45,710
əsaslı qədər Bildiyimiz kimi, hər hansı bir sürətli həll edilə bilməz

164
00:09:45,710 --> 00:09:48,880
Bu qrafik ən pis həqiqətən daha göstərir.

165
00:09:48,880 --> 00:09:53,660
Belə insanlar indiyədək var daha yaxşı etmək üçün bu dünyada açıq problemlər bir çox var.

166
00:09:53,660 --> 00:09:56,130
>> Beləliklə, bu nümunə sonra başlamaq edək.

167
00:09:56,130 --> 00:09:59,650
Biz bütün çox yöndəmsiz video haqqında bu kamera ilə Sean mübarizə gördüm.

168
00:09:59,650 --> 00:10:05,270
Sean bu sayı 7 kimi bir board tapmaq həvalə edilmişdir Lakin reallıq idi

169
00:10:05,270 --> 00:10:10,300
Mən "bu kağız parçaları və ya ağ qapılar arxasında yerdə var, bildirib ki, geri

170
00:10:10,300 --> 00:10:12,570
"Sayı 7. Sean, bizim üçün tapa bilərsiniz."

171
00:10:12,570 --> 00:10:14,200
Və izləmək gözəl yöndəmsiz idi

172
00:10:14,200 --> 00:10:15,790
o, həqiqətən bu problem ilə mübarizə idi.

173
00:10:15,790 --> 00:10:19,720
Lakin reallıq Sean otaqda hər kəs həyata bilər kimi də etdilər idi.

174
00:10:19,720 --> 00:10:21,890
O, ola bilər bir az artıq tipik şəxs-dən aldı

175
00:10:21,890 --> 00:10:24,760
lakin o, bəzi oyun bu problem var idi ki, qəbul

176
00:10:24,760 --> 00:10:26,590
o bir şey itkin ehtimal.

177
00:10:26,590 --> 00:10:29,320
Və gözləri yüzlərlə ona aşağı daşıyan ki, kömək etmədi.

178
00:10:29,320 --> 00:10:34,250
>> Problemin giriş təsadüfi ədəd bir dəstə əgər Lakin reallıq idi

179
00:10:34,250 --> 00:10:37,120
və, 1 belə sıra tapmaq üçün xahiş edirik

180
00:10:37,120 --> 00:10:39,770
Bunu ən yaxşı xətti axtarış edir.

181
00:10:39,770 --> 00:10:44,060
Sol başlayın sağa hərəkət və ya sola hərəkət hüququ da başlanır.

182
00:10:44,060 --> 00:10:48,300
Retroaktiv, biz düşünür ola bilər "Sean, niyə yalnız başqa sonunda başlamaq etmədi?"

183
00:10:48,300 --> 00:10:52,120
Yaxşı, 7 kimi asanlıqla təsadüfi burada ola bilərdi

184
00:10:52,120 --> 00:10:54,980
Mən o sonunda başlamaq niyyətindəyik deyil fiqurlu çünki mən qəsdən orada qoyun.

185
00:10:54,980 --> 00:10:59,320
Mən cür vəziyyəti manipulyasiya, lakin təsadüfi şansı 7 yerdə ola bilərdi.

186
00:10:59,320 --> 00:11:02,380
Belə ki, sağ sonundan başlayaraq, sonra daha yaxşı ola bilər

187
00:11:02,380 --> 00:11:04,320
lakin nə, mən başqa yerlərdə 7 hərəkət gələn il?

188
00:11:04,320 --> 00:11:06,830
Bu problem bir əsaslı yeni həll deyil -

189
00:11:06,830 --> 00:11:10,520
1 sonunda və ya digər başlayaraq - Siz heç bir digər fərziyyələr verilmiş etdiyiniz zaman.

190
00:11:10,520 --> 00:11:13,620
Belə Sean nömrələri vasitəsilə axtarır başladı və dedi "5. Yəni burada deyil."

191
00:11:13,620 --> 00:11:17,280
Sonra o, burada getdi və 19 gördü, o, təxminən 20 saniyə üçün durdurulmuş

192
00:11:17,280 --> 00:11:22,330
sonra 13 Bu açdı və o, müəyyən oldu

193
00:11:22,330 --> 00:11:24,270
burada bir model olması üçün görünür deyil.

194
00:11:24,270 --> 00:11:28,090
Bu 1, 2, 3, 4 və ya kimi deyil. Kömək olmayan sayda boşluqlar var idi.

195
00:11:28,090 --> 00:11:32,320
Və çox, mən kağız bu ucuz ədəd istifadə etməsi nömrələri qədər əhatə

196
00:11:32,320 --> 00:11:35,270
Çünki kağız bütün bu ədəd çıxarıldığı halda, faktiki olaraq qəsdən edir

197
00:11:35,270 --> 00:11:38,760
Bizi ən çox, Sean daxil yəqin ki, sort macroscopically ilə baxırdılar olardı

198
00:11:38,760 --> 00:11:43,410
bu yazı taxtası və "Oh, 7 orada açıq-aydın deyil." dedi Biz dərhal bunu etdi.

199
00:11:43,410 --> 00:11:46,460
>> Və ki, insan beyninin müəyyən dərəcədə çalışır yolu ola bilər

200
00:11:46,460 --> 00:11:50,730
lakin əslində, gözləri və ya ağıl, sağdan skimming nömrələri yəqin idi

201
00:11:50,730 --> 00:11:55,190
həyata sağ, orta tərk - bir fizioloji davam edildi

202
00:11:55,190 --> 00:11:57,640
dərhal baş verən kimi hiss ki, bu cür

203
00:11:57,640 --> 00:12:01,360
lakin odds məcburi 7 tapmaq üçün metodologiya bir növ var idi hətta var.

204
00:12:01,360 --> 00:12:05,160
And olsun ki, indi biz seriallarda və data strukturları söhbət edirik ki,

205
00:12:05,160 --> 00:12:08,780
və kompüter yaddaş daxilində, biz insanlar yalnız şey edə

206
00:12:08,780 --> 00:12:13,070
bir zamanda fərdi yaddaş yerlərdə 1 baxmaq edir.

207
00:12:13,070 --> 00:12:16,600
>> Belə ki, hər yeri, habelə kağız bəzi parça ilə əhatə oluna bilər

208
00:12:16,600 --> 00:12:21,170
biz hər halda bunu görmək bilməz. Biz yalnız bir zamanda 1 şey edə bilərsiniz.

209
00:12:21,170 --> 00:12:25,030
Belə ki, bu halda, Sean işində, biz burada getdi və sonra biz burada getdi

210
00:12:25,030 --> 00:12:31,040
və sonra biz burada getdi, burada, burada, burada sonunda ağıllı var

211
00:12:31,040 --> 00:12:34,450
və yalnız cür özbaşına bu atlandı və 7 tapılmadı.

212
00:12:34,450 --> 00:12:37,470
Bu xüsusilə deyildi. Bu çox üçün həyata idi.

213
00:12:37,470 --> 00:12:39,530
Lakin o, nəhayət 7 tapılmadı.

214
00:12:39,530 --> 00:12:45,360
Amma indi paket həqiqətən edə bilərsiniz ən yaxşı heç bir məlumat verilmişdir zaman ki,

215
00:12:45,360 --> 00:12:50,400
təsadüfi sıralanır nömrələri başqa sol başlamaq və ya sağdan başlamaq üçün.

216
00:12:50,400 --> 00:12:54,950
Və ya heck, siz təsadüfi qapılarını aça bilər, hətta sonra nə təsadüfi olmaq deməkdir?

217
00:12:54,950 --> 00:12:57,220
Yaxşı, biz elə burada başlamaq üçün nə deməkdir rəsmiləşdirilməsi istiyorum

218
00:12:57,220 --> 00:13:01,150
sonra burada getmək, sonra bura gedin. Sean böyük idi və bu izləmək üçün yalnız əyləncə idi.

219
00:13:01,150 --> 00:13:06,340
Biz problem bir az dəyişdirmək və Siz bu il Sean yetişdirmək nə əvəzinə, əgər?

220
00:13:06,340 --> 00:13:09,460
Hər kəs səhnəyə gələn və bir az fərqli problemin həlli rahat olacaq

221
00:13:09,460 --> 00:13:12,330
və kamera görünmesini?

222
00:13:12,330 --> 00:13:15,720
>> Uşaqlar olduqca bu gün artıq cəlb edilmişdir, çünki bu və orkestr kənara edək.

223
00:13:15,720 --> 00:13:21,430
Necə haqqında çəhrayı, bu papaq mi? Aşağı Hadi. Sizin adınız nədir? >> Alex. >> Alex. Okay.

224
00:13:21,430 --> 00:13:24,580
Belə ki, Alex bu il Sean olacaq və növbəti bir neçə il görünür

225
00:13:24,580 --> 00:13:27,770
CS50 mühazirələr dəyər.

226
00:13:27,770 --> 00:13:30,340
Alex, siz cavab gözəl. >> Çox cavab Nice.

227
00:13:30,340 --> 00:13:33,470
Sizin üçün əl çağırış siz bir az daha asan var ki

228
00:13:33,470 --> 00:13:38,950
ki, burada eyni nömrələr olunur deyirəm, amma indi sıralanır.

229
00:13:38,950 --> 00:13:41,800
Belə ki, indi sizin məqsədi sayı 7 tapmaqdır.

230
00:13:41,800 --> 00:13:45,370
Və həqiqətən, biz, həqiqətən bu olmalıdır - aldadıcı you're cür kompüter kimi ki, deyil,

231
00:13:45,370 --> 00:13:47,990
nə baxaraq nömrələri bir an əvvəl idi.

232
00:13:47,990 --> 00:13:50,360
Təbaşir bu əslində, bütün çox kömək etmək niyyətində deyil

233
00:13:50,360 --> 00:13:52,810
ancaq orijinal array nə bilmirəm ki, iddia edək.

234
00:13:52,810 --> 00:13:56,600
İndi bilirik Bütün sıralanır ədəd bir sıra var ki

235
00:13:56,600 --> 00:14:00,360
onların arasında boşluqlar ola bilər və qol sayı 7 tapmaqdır.

236
00:14:00,360 --> 00:14:05,080
Necə olan bir ağlabatan insan sayı 7 tapmağa getmək istəyirsiniz?

237
00:14:05,080 --> 00:14:07,770
>> Yüksək aşağı getmək? Okay. >> Yüksək aşağı gedin.

238
00:14:07,770 --> 00:14:10,990
Onların qoparmaq yoxdur. Biz onları yenidən istifadə edə bilərsiniz belə yalnız onlara ucaltmaq edək.

239
00:14:10,990 --> 00:14:14,730
OK, belə 1. Gözləyin. Siz davam əvvəl, aydın yanlış 1 idi.

240
00:14:14,730 --> 00:14:17,270
Belə ki, nə gələn fikrinizi keçir var? Növbəti addım nədir?

241
00:14:17,270 --> 00:14:23,250
Növbəti biridir. Okay. >> Növbəti biridir. Yaxşı. Belə yanlış 3. Növbəti addım nədir?

242
00:14:23,250 --> 00:14:27,670
Davam edin. >> Bütün hüququ. Davam edin. 5.

243
00:14:27,670 --> 00:14:31,110
Belə davam saxlamaq və mənə posterity üçün bu əl bildirin.

244
00:14:31,110 --> 00:14:35,720
7. >> Əla. Çox yaxşı. Sayı 7 tapıldı. [Alqış]

245
00:14:35,720 --> 00:14:39,720
Belə ki, yaxşı idi, lakin Sean çox sayı 7 tapılmadı.

246
00:14:39,720 --> 00:14:44,490
Mən, həqiqətən, məlumat bu əlavə parça istismar yoxdur ki, mübahisə

247
00:14:44,490 --> 00:14:47,780
bu nömrələr sıralanır edir.

248
00:14:47,780 --> 00:14:51,520
Belə ki, biz daha yaxşı edə bilər? Burada hər hansı təkliflər? Bəli, geri.

249
00:14:51,520 --> 00:14:54,710
[Tələbə] Binary axtarış. >> Mən binar axtarış nə heç bir fikrim yoxdur.

250
00:14:54,710 --> 00:14:58,030
>> [Tələbə] ortasında başlayın. >> Ortasında başlayın. Okay. Belə ki, biz orada edə bilərsiniz nin görək.

251
00:14:58,030 --> 00:15:02,580
Siz ortalarından start duyum əvəzinə Belə ki, davam və orta qapı açır.

252
00:15:02,580 --> 00:15:04,580
Onlardan 8 deyil, belə ki, özbaşına bir seçmək üçün olacaq

253
00:15:04,580 --> 00:15:09,800
az sola və ya sağa. Okay. 7! [Alqış] Çox gözəl.

254
00:15:09,800 --> 00:15:11,410
OK, lakin biz bu yerləşir gedirdi?

255
00:15:11,410 --> 00:15:14,990
Gəlin yalnız burada başladı tie break Güman

256
00:15:14,990 --> 00:15:16,670
eyni dərəcədə həm baş bilərdi çünki.

257
00:15:16,670 --> 00:15:19,540
Biz yalnız 7 olduğunu bilmək oldu. Beləliklə, bu 13.

258
00:15:19,540 --> 00:15:21,980
Onlar çeşidlənir və əgər Beləliklə, biz yalnız orta başlayıb

259
00:15:21,980 --> 00:15:24,600
optimal növbəti addım nə olardı?

260
00:15:24,600 --> 00:15:27,740
Sol gedin. Və burada yenə telefon kitab Məsələn gəlir.

261
00:15:27,740 --> 00:15:30,130
13 buradadır və biz siyahısına çeşidlənir bilirsinizsə,

262
00:15:30,130 --> 00:15:33,900
sonra kağız bu ədəd bütün indi bizim üçün maraqsız edir

263
00:15:33,900 --> 00:15:37,400
Biz artıq 7-sol olmalıdır bilirik ki, çünki

264
00:15:37,400 --> 00:15:39,510
bu rəqəmlər sıralanır və biz 13 aşkar edildikdə.

265
00:15:39,510 --> 00:15:42,500
>> Belə ki, burada sizin növbəti hərəkət nədir? >> Sola dön. >> Okay yaxşı.

266
00:15:42,500 --> 00:15:45,080
Hey, hey, hey, gözləmək - Belə sola getmək, və. Bu aldadıcı edir.

267
00:15:47,140 --> 00:15:51,350
Belə ki, 7 aşkar, lakin biz yalnız tətbiq alqoritm nə idi?

268
00:15:51,350 --> 00:15:56,450
Ortada başlayın. >> Yaxşı. Belə ki, eyni fikri məntiqi məsləhət var?

269
00:15:56,450 --> 00:15:58,970
Oh, yalnız bu üçün. Məhz >>. >> Mən burada başlayır. >> Yaxşı.

270
00:15:58,970 --> 00:16:02,020
Belə ki, indi biz daha sola qədər getdi. 3 var.

271
00:16:02,020 --> 00:16:05,310
Lakin maraqlı paket indi sizin qayğı var olmayan var?

272
00:16:05,310 --> 00:16:08,040
Bu 2. >> Bu 2. Belə ki, indi bu bir getmək bilər, bu getmək bilər.

273
00:16:08,040 --> 00:16:12,330
İndi 8 idi ki, problem ölçüsü 4 indi ölçüsü 2 edilib.

274
00:16:12,330 --> 00:16:16,430
Biz olduqca yaxın əldə edirik. Yenə bu 2 elementləri orta gedin.

275
00:16:16,430 --> 00:16:20,430
>> Okay. Belə ki, biz aşağı yuvarlaqlaşdırma istəyirik, çünki indi biz həmişə sol olacaq ki, növ uğursuz var.

276
00:16:20,430 --> 00:16:25,150
İndi biz yalnız 7 bizə tərk, üz və başqa hər şey bu atmaq çünki Lakin gözəl var.

277
00:16:25,150 --> 00:16:30,490
Nin alqış dəyirmi verim. Biz 7 tapılmadı. [Alqış] Okay. Əmin olun.

278
00:16:30,490 --> 00:16:32,220
Yalnız 1 daha ikinci Bekle.

279
00:16:32,220 --> 00:16:36,630
Ki, növbəti proses cür biz bu ki, hiss bir az uzun çəkdi, baxmayaraq

280
00:16:36,630 --> 00:16:40,150
səmimi, ilk instinktlərdən doğru, ən yaxşı idi? Biz dərhal 7 tapılmadı.

281
00:16:40,150 --> 00:16:46,740
Amma biz daha sürətli, daha bu qarşı olursa bu misal nə, 7 aşkar olardı

282
00:16:46,740 --> 00:16:50,100
nömrələr bütün sıralanır əgər çünki çox bir telefon kitab pages kimi,

283
00:16:50,100 --> 00:16:54,580
siz həqiqətən təkrar və yenidən problem yarısında həyata doğramaq bilər.

284
00:16:54,580 --> 00:16:56,740
Və yalnız 8 nömrələri ilə görmək olduqca kimi asan deyil

285
00:16:56,740 --> 00:17:00,100
kimi həqiqətən əyani görmək bir 1000-səhifə telefon kitab qarşı,

286
00:17:00,100 --> 00:17:03,120
amma burada bu halda Sean, 7 üçün axtarış zaman

287
00:17:03,120 --> 00:17:06,020
necə çox pis halda addımlar onu qəbul edərdiniz? >> [Tələbə] 7.

288
00:17:06,020 --> 00:17:11,670
Ən pis halda 7. Yaxşı, ən pis halda heç 7 8 qapı burada var əgər.

289
00:17:11,670 --> 00:17:13,440
Onun 8 addımlar olardı.

290
00:17:13,440 --> 00:17:18,170
>> Belə ki, var n qapılar, əgər bir neçə il əvvəl n addımlar Sean qəbul ola bilər.

291
00:17:18,170 --> 00:17:21,520
İndi halda, bu rəqəmlər ayrılır ki, Alex, verilmiş -

292
00:17:21,520 --> 00:17:25,130
və biz bu hekayə belə uzaq olduğunuz yerdən çıxarmaq bu cür edə bilər -

293
00:17:25,130 --> 00:17:28,300
Alex daha ağıllı alqoritm çalışan zaman nə

294
00:17:28,300 --> 00:17:30,770
ortalarından başlayan və sonra təkrar?

295
00:17:30,770 --> 00:17:36,490
[Tələbə] 3. >> Belə ki, siz 2-1-8-4-dən getmək əgər, təxminən, 3 olacaq.

296
00:17:36,490 --> 00:17:40,660
3 addımlar Belə və ya, ümumiyyətlə, o log n daha var.

297
00:17:40,660 --> 00:17:43,380
Siz halving və halving və halving və halving etdiyiniz istənilən vaxt,

298
00:17:43,380 --> 00:17:45,290
ki, log n bu fikir bir ifadə var.

299
00:17:45,290 --> 00:17:48,140
Və belə ki, yalnız 3 addımlar ki, həqiqətən bunu

300
00:17:48,140 --> 00:17:50,890
bir dəfə biz qapıları halving və halving açıldı

301
00:17:50,890 --> 00:17:53,770
bu Sean təqribən 7 və ya 8 addımlar olardı halbuki.

302
00:17:53,770 --> 00:17:56,330
Belə ki, bizə bu il olan üçün təşəkkür edirik. >> Təşəkkür edirik. Görüşdə siz gözəl.

303
00:17:56,330 --> 00:18:00,170
Alex təşəkkür edirik. >> Eynilə. [Alqış]

304
00:18:00,170 --> 00:18:02,150
>> Hansı sonra bu real dolayısı var?

305
00:18:02,150 --> 00:18:06,050
İndi səmimi, bizim bütün bir şey tapmaq mümkün olan, 8 qapı, deyil ki, təsəvvür

306
00:18:06,050 --> 00:18:10,430
yalnız kağız parçaları qoparmaq və instinktləri ilə gedən olduqca tez arxasında 8 qapı.

307
00:18:10,430 --> 00:18:14,430
Amma bir milyon qapılar nə olur? Ne 4 milyard qapı olur?

308
00:18:14,430 --> 00:18:19,630
4 milyard Qapı halda, siz, həqiqətən, Alex alqoritmi ilə getmək istəyirəm olacaq

309
00:18:19,630 --> 00:18:23,150
biz bu zəng başlamaq və ya daha çox, ümumiyyətlə, bölmək və fəth olacaq kimi ikili axtarış

310
00:18:23,150 --> 00:18:25,220
Siz problem halving və halving saxlamaq yerləşir,

311
00:18:25,220 --> 00:18:30,510
siz 4 milyard qapı varsa, neçə dəfə yarım ildə 4 milyard doğramaq bilər, çünki?

312
00:18:30,510 --> 00:18:33,870
[Tələbə] 32. >> Bu, faktiki 32 var. Siz bir kağız parçası və ya baş bu həyata işləyə bilər.

313
00:18:33,870 --> 00:18:38,490
Siz 250 milyon, nöqtə, nöqtə, nöqtə üçün 4 milyard 2 milyard 1 milyard yarım milyard gedin.

314
00:18:38,490 --> 00:18:41,620
Siz riyaziyyat həyata nə varsa, həqiqətən, 32 almaq olacaq

315
00:18:41,620 --> 00:18:44,950
biz adətən 2 səlahiyyətlərinə saymaq çünki əslində kompüter aiddir.

316
00:18:44,950 --> 00:18:47,600
2, 32, 4 milyard olur.

317
00:18:47,600 --> 00:18:51,440
Belə ki, informatika 2 səlahiyyətləri bu cür uyğun bir çox var.

318
00:18:51,440 --> 00:18:55,120
>> Amma nə 8 milyard haqqında? 8 milyard qapı olduqda neçə addımlar ki, iştirak edir?

319
00:18:55,120 --> 00:19:00,350
[Tələbə] 33. Belə ki, 33 >>. Nə 16 milyard qapı var əgər? Neçə addımlar ki, iştirak edir?

320
00:19:00,350 --> 00:19:05,020
[Tələbə] 34. >> 34. Biz növ bu reklamdan nauseam davam edə bilər. Amma güclü bir şey var.

321
00:19:05,020 --> 00:19:09,430
Siz problem daha çox vəsait milyardlarla təqdim, lakin heç bir böyük olar

322
00:19:09,430 --> 00:19:14,140
yalnız 1 əlavə bite çıxarmaq və beləliklə, bizə ikili axtarış kimi bir şey verir

323
00:19:14,140 --> 00:19:15,920
və ya ümumiyyətlə, bölmək və qalib.

324
00:19:15,920 --> 00:19:17,990
Amma hüququ, burada aldadıcı növü Ben?

325
00:19:17,990 --> 00:19:22,410
Alex alqoritm halda, o, Sean üzərində bir üstünlüyü var idi.

326
00:19:22,410 --> 00:19:27,780
O, bu rəqəmlər sıralanır ki, bilirdi, amma Alex onlara özü sıralama yoxdur.

327
00:19:27,780 --> 00:19:30,520
Əvvəlcədən mən əmin və yazı taxtası və cür gəldi

328
00:19:30,520 --> 00:19:33,670
Mən sıralanır üçün onlara bütün çəkdi, sonra kağız ilə əhatə etmişdir.

329
00:19:33,670 --> 00:19:35,850
Amma ki, mənə nə qədər iş almaq idi?

330
00:19:35,850 --> 00:19:40,110
Bəzi zahirən təsadüfi üçün bu nömrələri ilə off başladı varsa -

331
00:19:40,110 --> 00:19:43,320
Bu halda bu sadə nömrələri, burada 8 vasitəsilə 1 -

332
00:19:43,320 --> 00:19:46,090
biz bu dəyərlərə çeşidlənməsi haqqında necə getmək yoxdur?

333
00:19:46,090 --> 00:19:52,530
Bu tapşırıq verilən insan olsaydı, intuitiv yanaşma nə cür siz edəcək

334
00:19:52,530 --> 00:19:54,800
ədəd bütöv bir dəstə çeşidlənməsi üçün?

335
00:19:54,800 --> 00:19:57,050
Bunlar puzzle ədəd kimi qoyulub. Bəli.

336
00:19:57,050 --> 00:19:59,950
>> [Tələbə] Mən hər bir nömrə almaq və hər bir müqayisə ki,

337
00:19:59,950 --> 00:20:03,180
və sola davam. >> Okay yaxşı.

338
00:20:03,180 --> 00:20:05,720
Belə ki, yanındakı bir müqayisə, hər bir nömrə almaq

339
00:20:05,720 --> 00:20:09,610
və sonra yalnız siz getmək kimi şeylər rejiggering vətəndaşların siyahısı cür boyunca hərəkət saxlamaq.

340
00:20:09,610 --> 00:20:13,800
Belə ki, burada biz cəlb almaq üçün daha çox bəlkə bir neçə insanlar üçün bir şans var.

341
00:20:13,800 --> 00:20:16,290
Biz gəlmək üçün sevgi istəyən 8 çox könüllü var?

342
00:20:16,290 --> 00:20:23,950
Siz ildən bir az daha az təzyiq tək deyilik. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Aşağı Hadi. Siz uşaqlar 8 vasitəsilə ədəd 1 olacaq.

344
00:20:28,190 --> 00:20:36,050
Biz əvvəlcədən bunu eyni şəkildə çox Alex bu çeşidlənməsi edə bilməz əgər in nəzər salaq.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Durmayın, siz ki, əgər burada musiqi stand və mənə arasında mərhələdə xətti

347
00:20:40,760 --> 00:20:44,960
ekranda Slayd kimi eyni qaydada.

348
00:20:47,910 --> 00:20:49,680
Ah-oh.

349
00:20:50,370 --> 00:20:53,230
Biz növbəti misal sizi işləmək lazımdır. Oh, gözləyin, gözləyin. Burada getmək. Gözləyin.

350
00:20:53,230 --> 00:20:57,570
Növbəti Məsələn indi. Burada getmək. Sayı 8. Qədər Hadi.

351
00:20:57,570 --> 00:21:00,270
Bütün hüquqlar. Sort Buna görə özünüzü.

352
00:21:00,270 --> 00:21:03,620
Musiqi tərəfində yalnız bir az sürüşdürərək burada durmaq.

353
00:21:03,620 --> 00:21:12,310
Belə ki, 4, 2, 6 var - orada, burada, orada almaq - 3.

354
00:21:12,310 --> 00:21:17,570
Bəli. Okay. Siz buraya gedin. Xeyr, siz orada qalmaq.

355
00:21:17,570 --> 00:21:21,840
Bəli, doğru var. No səhv edirəm. Hüququ var. OK, çox yaxşı. Okay.

356
00:21:21,840 --> 00:21:24,930
Belə ki, indi-nin artan qaydada onlara sort imkan verir.

357
00:21:24,930 --> 00:21:26,210
>> Mən bunu edə bilərsiniz?

358
00:21:26,210 --> 00:21:28,630
Bir an əvvəl təklif edilmişdir ki, alqoritm niyə biz yalnız müqayisə etməyin idi

359
00:21:28,630 --> 00:21:31,970
sonra bir-birinin yanında növ və olan insanlar, hər hansı bir səhv fix

360
00:21:31,970 --> 00:21:33,540
soldan sağa hərəkət.

361
00:21:33,540 --> 00:21:36,580
Belə ki, burada biz açıq-aydın qırıq, 4 və 2 var. Sizə dəyişdirmək edək. Okay.

362
00:21:36,580 --> 00:21:40,760
Belə ki, indi mən xətt aşağı hərəkət etmək üçün gedirəm. 4 və 6, nope. [Gülüş]

363
00:21:40,760 --> 00:21:45,010
6 və 8, olduqca yaxşı. 8 və 1, mənə uşaqlar dəyişdirmək imkan verir. Bütün hüquqlar.

364
00:21:45,010 --> 00:21:48,030
8 və 3 Beləliklə, uşaqlar dəyişdirmək.

365
00:21:48,030 --> 00:21:52,280
8 və 7, mənə uşaqlar dəyişdirmək imkan verir. 5 və əla 8,.

366
00:21:52,280 --> 00:21:54,820
Mən sizə bir sıralaması siyahısını göstərir.

367
00:21:54,820 --> 00:21:56,860
Bütün hüquqlar. Belə ki, tamamilə.

368
00:21:56,860 --> 00:22:01,180
Amma yaxşı çünki daha böyük nömrələr - hal nöqtəsi 8-ci ildə -

369
00:22:01,180 --> 00:22:04,030
cür sağa sola ərzində bubbled var.

370
00:22:04,030 --> 00:22:08,010
Mən sağ Onlardan 1 var, lakin kifayət qədər problemi həll etməyib bu kimi hiss edir.

371
00:22:08,010 --> 00:22:11,150
>> Biz növbəti bunu nə təklif edərdiniz? >> [Tələbə] bunu edin. >> Biz bunu saxlamaq.

372
00:22:11,150 --> 00:22:13,740
Və yenə reallaşdırmaq, biz yalnız bütün insanların malik şeyi qurmaq

373
00:22:13,740 --> 00:22:17,180
növ ağıllı ki, şəkil əsasında özləri təşkil

374
00:22:17,180 --> 00:22:19,040
indi biz daha çox metodiki olmalıdır.

375
00:22:19,040 --> 00:22:21,510
Biz kodu yazıyoruz sanki bu barədə alqoritmik olmalıdır -

376
00:22:21,510 --> 00:22:23,520
Bu halda şifahi pseudocode edir.

377
00:22:23,520 --> 00:22:26,040
Mənə yalnız bir daha cəhd edək. Bu olduqca yaxşı işləyib. Bu həll etmədi.

378
00:22:26,040 --> 00:22:30,400
Lakin şübhə zaman yalnız cəhd və yenidən cəhd edin. Belə ki, 2 və 4, artıq kömək etmədi.

379
00:22:30,400 --> 00:22:33,200
4 və 6. Ah! Biraz daha yaxşı indi 6 və 1.

380
00:22:33,200 --> 00:22:39,740
6 və yaxşı 3. 6 və 7, 7 və 5, 7 və 8 yaxşı.

381
00:22:39,740 --> 00:22:44,060
O siyahısının sonunda deyil, çünki bilirsiniz, yəqin ki, artıq 8 iqnor edə bilər.

382
00:22:44,060 --> 00:22:47,250
Bəlkə kimsə ona keçmiş gedən narahat yoxdur.

383
00:22:47,250 --> 00:22:49,240
Amma bir təhlükəsiz ehtimal varsa nin görək.

384
00:22:49,240 --> 00:22:52,340
İndi siyahısı - lənətləmək - sıralanır deyil. Nin daha cəhd edək.

385
00:22:52,340 --> 00:22:56,440
2 Belə ki, 4, 4 və 1, 4 və 3.

386
00:22:56,440 --> 00:22:59,230
4 və 6, yaxşı. 6 və 5, yaxşı.

387
00:22:59,230 --> 00:23:04,890
6, 7, 8, yaxşı. Ancaq xəbərdarlıq, mən yalnız indi burada dayandırmaq və indi burada dayandırmaq olar?

388
00:23:04,890 --> 00:23:07,770
[Tələbə] Bəli. >> Evet?

389
00:23:07,770 --> 00:23:11,160
Nə biri orada bütün yol sayı 9 olsaydı?

390
00:23:11,160 --> 00:23:13,640
Bu sıralanır olardı. >> Yaxşı. Bu ətrafında ilk dəfə sıralanır olardı.

391
00:23:13,640 --> 00:23:16,050
Yaxşı. Beləliklə nin yenidən gedək. Biz demək olar ki, orada edirik.

392
00:23:16,050 --> 00:23:22,800
1 və 2, 2 və 3, 3 və 4, 4, 5, 5, 6, 6 və 7, 7 və 8.

393
00:23:22,800 --> 00:23:26,640
>> Indi görülən edirəm amma yenə Mən yalnız bunu deyib alıram nə edə bilər ki, bir kompüter deyiləm

394
00:23:26,640 --> 00:23:30,120
və yalnız xatirə indi faktiki olaraq yalnız iş bir az idi ki.

395
00:23:30,120 --> 00:23:31,700
Something burada dəyişdi.

396
00:23:31,700 --> 00:23:37,100
Mən texniki vizual və ya algorithmically bu siyahı həqiqətən çeşidlənir təsdiq deyil.

397
00:23:37,100 --> 00:23:40,720
Yalnız yaxşı tədbir üçün Belə ki, yalnız bu barədə anal olmaq, bu 1 dəfə daha nə edək.

398
00:23:40,720 --> 00:23:44,040
1 Beləliklə, 2, 2 və 3, 3 və 4. Və nə bilirik?

399
00:23:44,040 --> 00:23:46,190
Yalnız yaxşı tədbir üçün, mən tərəfdən bu dəfə takip gedirəm

400
00:23:46,190 --> 00:23:51,110
Mən iş nə qədər yalnız, belə ki etmək neçə svopları Mən, həqiqətən etdik.

401
00:23:51,110 --> 00:23:56,930
3 və 4, 4, 5, 5, 6, 6 və 7, 7 və 8. No svopları.

402
00:23:56,930 --> 00:24:00,800
Belə ki, indi qanunla yenə bunu bir axmaq olardı

403
00:24:00,800 --> 00:24:03,330
Çünki insanların bu keçid vasitəsilə heç bir iş əgər,

404
00:24:03,330 --> 00:24:06,710
onların heç cür təsadüfi deyil, əgər aydın yenidən baş verəcək ki,

405
00:24:06,710 --> 00:24:10,410
adversarially öz ətrafında hərəkət. Belə ki, indi mən dayandıra bilər.

406
00:24:10,410 --> 00:24:15,120
İndi sual edək, bu, həqiqətən, mənə nə qədər iş almaq idi?

407
00:24:15,120 --> 00:24:18,260
Necə bir çox addımlar idi? >> N kare.

408
00:24:18,260 --> 00:24:20,400
Bəli, belə n kare. Siz haradan kvadrat almaq n var?

409
00:24:20,400 --> 00:24:22,660
Siz hər num yoxlamaq var -

410
00:24:22,660 --> 00:24:26,530
Yoxdur n nömrələri, və digər n nömrələri ilə hər sayı yoxlamaq lazımdır.

411
00:24:26,530 --> 00:24:29,030
Yaxşı. >> Belə ki, kvadrat n edir. >> Yaxşı.

412
00:24:29,030 --> 00:24:31,060
>> Belə ki, çox yaxşı, sağ kvadrat ola n bilər kimi hiss edir?

413
00:24:31,060 --> 00:24:33,820
8 Bu halda, xüsusilə bu uşaqlar var n ki,

414
00:24:33,820 --> 00:24:37,590
amma bu siyahı ilə getdi hər dəfə mən, ikinci qarşı ilk şəxs müqayisə edilmişdir

415
00:24:37,590 --> 00:24:39,650
, təkrar yenidən üçüncü qarşı ikinci və

416
00:24:39,650 --> 00:24:42,450
və mən sonunda əldə zaman, mən nə idi? Mən bunu redid.

417
00:24:42,450 --> 00:24:46,280
Biz bu izahat ümumiləşdirmək Belə ki, biz insanların n

418
00:24:46,280 --> 00:24:51,090
və mən, əlbəttə ki, 8 addımlar n addımlar, bu alqoritm vasitəsilə getmək hər zaman qəbul edirəm.

419
00:24:51,090 --> 00:24:56,070
Amma necə çox pis halda dəfə Mən bu siyahı ilə getmək lazımdır?

420
00:24:56,070 --> 00:24:59,370
[Tələbə] N dəfə. >> Yəqin ki, n, sağa, çünki ən pis halda,

421
00:24:59,370 --> 00:25:03,410
nə yəqin ki, get-getmək bu uşaqlar ən pis halda razılaşma var?

422
00:25:03,410 --> 00:25:06,520
Onlar tamamilə qaydada ləğv edirsinizsə

423
00:25:06,520 --> 00:25:09,310
çünki yalnız əqli let's Güman - adın nədir? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Okay. Belə ki, yalnız bir an üçün artıq burada gəlib Bowen.

425
00:25:12,510 --> 00:25:16,150
>> , Bowen alqoritmi əvvəlində burada olduğunu düşünək

426
00:25:16,150 --> 00:25:19,790
və biz bu alqoritmi görə, burada hər kəs nə bilirik, lakin Bowen yoxdur -

427
00:25:19,790 --> 00:25:23,820
və yalnız mənə cövlan etmək istəyirsinizsə - o ətrafında ilk dəfə olduğu kimi, bubble qədər gedir,

428
00:25:23,820 --> 00:25:25,740
sonuna bütün yol.

429
00:25:25,740 --> 00:25:29,400
Amma Bowen yanındakı adam sayı 7 idi ki, nəzərdə tutur.

430
00:25:29,400 --> 00:25:33,450
Mən geri getmək və geri burada bütün yol getmək deməkdir sayı 7, almaq lazımdır.

431
00:25:33,450 --> 00:25:36,980
İndi sayı 7 olan şəxs ilə həmin stroll var.

432
00:25:36,980 --> 00:25:40,140
Ancaq 6 saylı həmçinin onun yanında idi sonra əgər nə?

433
00:25:40,140 --> 00:25:42,180
Sonra geri getmək və 6 almaq lazımdır.

434
00:25:42,180 --> 00:25:46,490
Belə ki, yenə bu loop hər iteration haqqında Mən n insanların hər söhbət alıram

435
00:25:46,490 --> 00:25:50,090
və mən çəkərək alıram əmin olun bu students N etmək ola bilər

436
00:25:50,090 --> 00:25:53,760
geri geri geri siyahısı çox sonunda ən böyük bütün öğeleri.

437
00:25:53,760 --> 00:25:58,230
Belə n şeyi n dəfə yalnız n dəfə n və ya n kvadrat edir.

438
00:25:58,230 --> 00:26:02,050
>> Belə ki, burada artıq biz artıq log n ki, artıq ki, bir alqoritm n, var,

439
00:26:02,050 --> 00:26:04,820
biz əvvəl etdiyiniz şey, həqiqətən, pis.

440
00:26:04,820 --> 00:26:09,840
Belə Alex cür, mən iş onun üçün yəqin qədər ön bütün etdilər ki, xoşbəxt var

441
00:26:09,840 --> 00:26:14,690
bu ikili axtarış alqoritmi ilə zövq bilər ki, bahalı bütün işləri,

442
00:26:14,690 --> 00:26:16,420
n log olan.

443
00:26:16,420 --> 00:26:18,240
Amma bu ertəsi mövzusu ilə uyğundur.

444
00:26:18,240 --> 00:26:23,260
Biz çalışan zaman sürətləndirmək üçün daha çox bit istifadə, bir az daha çox yer verdi.

445
00:26:23,260 --> 00:26:26,170
Belə ki, çox zaman və məkan arasında ticarət-off var kimi,

446
00:26:26,170 --> 00:26:31,060
vaxt getmək şeyi hazır əldə qarşısında cür işlərin arasında yalnız kompromislər ola bilər

447
00:26:31,060 --> 00:26:35,000
və həqiqətən axtarış kimi bir alqoritm həyata. Nin başqa bir cəhd edək.

448
00:26:35,000 --> 00:26:39,050
Uşaqlar yalnız tez rearranging ağla Əgər özünüzü daha uyğun

449
00:26:39,050 --> 00:26:42,240
olduqca sadə kimi olduğu qədər fərqli bir cəhd edək

450
00:26:42,240 --> 00:26:45,760
super intuitiv olan bütün pairwise səhvlər, yalnız düzeltmek kimi.

451
00:26:45,760 --> 00:26:48,150
Nin yerinə bir az daha qəsdən və bunu edək.

452
00:26:48,150 --> 00:26:51,010
Çox mən təklif edirəm Bu yəqin ki, olduqca asan.

453
00:26:51,010 --> 00:26:55,070
>> Təkrar siyahıdan kiçik adam seçin edək. Belə ki, burada biz gedin.

454
00:26:55,070 --> 00:26:57,350
4, mən bununla belə uzaq gördüm kiçik adam var

455
00:26:57,350 --> 00:27:00,520
mən ruhi yalnız indi sizə işarə edərək, unutmayın ki, gedirəm.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Sayı 4 Unut. Mən yalnız bu siyahıda yeni kiçik element tapılmadı.

457
00:27:05,020 --> 00:27:07,410
I növ unutmayın gedirəm. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Goodbye. Belə ki, indi sayı 1 yadda gedirəm.

459
00:27:11,190 --> 00:27:14,790
Biz 1 kiçik olduğunu bilirik, lakin mən kompüter edirəm. Nə 0 varsa?

460
00:27:14,790 --> 00:27:17,140
Nə -1 var əgər? Mən davam etmək lazımdır.

461
00:27:17,140 --> 00:27:20,990
Belə ki, 3, 7, 5, nope. Okay. Belə ki, 1 saylı kiçik idi.

462
00:27:20,990 --> 00:27:23,640
Mənə siyahıdan seçdiyiniz edək - we'll bu yolla getmək -

463
00:27:23,640 --> 00:27:27,760
və siyahıdan əvvəlində özbaşına sizi.

464
00:27:27,760 --> 00:27:29,740
İndi, bir dəqiqə gözləyin. Cheated I növ.

465
00:27:29,740 --> 00:27:34,010
Bu uşaqlar deyil 8 nəfər bir siyahısını lakin bir sıra təmsil varsa,

466
00:27:34,010 --> 00:27:37,050
Bitişik yaddaş 8 chunks - yalnız bir an geri gücləndirməklə ağla edirsiniz?

467
00:27:37,050 --> 00:27:39,060
Burada sizin üçün heç bir yer həqiqətən var.

468
00:27:39,060 --> 00:27:41,840
Belə ki, necə biz kosmik edə bilərəm - adın nədir? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Necə Sammy üçün yer edə bilərəm?

470
00:27:43,710 --> 00:27:46,760
>> Biz məndən əvvəl olan n hərəkət. Okay. >>

471
00:27:46,760 --> 00:27:48,850
Beləliklə, biz ondan əvvəl olan n insanların hərəkət edə

472
00:27:48,850 --> 00:27:52,400
uşaqlar sola 1 qəsdən, dramatik addım istəyirəm əgər.

473
00:27:52,400 --> 00:27:57,000
Onlar bütün uyum etdi, lakin son dəfə bir neçə kodu yazdı

474
00:27:57,000 --> 00:27:59,740
Bütün bir dəfə bir çox şeyi hərəkət və sort bilməz.

475
00:27:59,740 --> 00:28:02,450
Biz bir dəfə bir dəfə hər kəs hərəkət, bir loop bunu bilər.

476
00:28:02,450 --> 00:28:04,340
Uşaqlar, sağ geri gücləndirməklə ağla deyil ki, əgər

477
00:28:04,340 --> 00:28:07,230
və Sammy, sizin üçün heç bir otaq var, çünki siz geri addım bilər,

478
00:28:07,230 --> 00:28:11,420
indi bunu edək. Harada Sammy bir an əvvəl idi? Hüququ var.

479
00:28:11,420 --> 00:28:16,140
Belə ki, orada bir boşluq var. Belə ki, Sammy nin spot hərəkət edə bilər.

480
00:28:16,140 --> 00:28:20,580
İndi növbəti şəxsə və indi artıq gələn şəxs, növbəti şəxs. İndi Sammy üçün otaq var.

481
00:28:20,580 --> 00:28:23,490
Tamaşaçılar indi, bəziləri - yaxşı idi ki, düzgün idi ki,

482
00:28:23,490 --> 00:28:27,070
bunu hiss vaxt aparan bir az - nə sürətli var? Bəli.

483
00:28:27,070 --> 00:28:29,440
[Tələbə] yeni array? >> Nədir ki? >> [Tələbə] yeni array? >> Okay yaxşı.

484
00:28:29,440 --> 00:28:33,200
>> Yalnız ticarət-off bu mövzu ilə Beləliklə, ardıcıl, niyə yalnız bir yeni array yoxdur

485
00:28:33,200 --> 00:28:36,570
 və sonra Sammy Məsələn, bu insanlar qarşısında yer üzgüçülük olunacaq

486
00:28:36,570 --> 00:28:39,600
və biz yalnız tamamilə yeni bir sıra yanacaqdoldurma başlaya bilərsiniz. Bu çox iş olardı.

487
00:28:39,600 --> 00:28:42,450
Ancaq mən bu gün daha çox yer sərf maraqlı deyiləm. Başqa yanaşma nədir?

488
00:28:42,450 --> 00:28:46,630
[Tələbə] Swap. Okay. >> Biz yalnız bu 2 uşaqlar dəyişdirmək bilər. Sizin adınız nədir?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Mario Belə ki, hal-hazırda burada idi.

490
00:28:49,390 --> 00:28:52,480
Sammy, yalnız bir an geri edə bilər? Mario burada idi.

491
00:28:52,480 --> 00:28:55,830
Siz Sammy olduğu gedən ağla deyil ki, əgər biz, artıq sizin üçün otaq yoxdur

492
00:28:55,830 --> 00:29:02,430
biz burada Sammy qoymaq lazımdır və indi Sammy nin dəyişdirmə əməliyyatı çox daha sürətli idi ki, mübahisə ediyorum.

493
00:29:02,430 --> 00:29:06,370
Biz bu uşaqlar dəyişdirmək, və ya bəlkə 2 Bu uşaqlar dəyişdirmək üçün 1 əməliyyat etdi

494
00:29:06,370 --> 00:29:11,210
lakin daha yaxşı hiss edir ki, 1, 2, 3, 4 etmədi. İndi, bir dəqiqə gözləyin.

495
00:29:11,210 --> 00:29:14,660
Sayı 4 əvvəlinə yaxın cür idi, çünki mən cür problem pis etdi.

496
00:29:14,660 --> 00:29:19,470
İndi sayı 4 Bu məqsədlə bir az daha yaxın, lakin mən, həqiqətən bilmək və ya qayğı etməyib.

497
00:29:19,470 --> 00:29:23,330
Beləliklə, bu sayı 4 bir az uzaq onun nəzərdə yer edir ki, yalnız pis şans deyil.

498
00:29:23,330 --> 00:29:25,110
Beləliklə, bu alqoritm təkrar indi edək.

499
00:29:25,110 --> 00:29:28,410
>> Kimi uzun o hekayə idi, recap üçün bütün biz siyahısına vasitəsilə gəzmək oldu

500
00:29:28,410 --> 00:29:31,130
kiçik saylı şəxs axtarır.

501
00:29:31,130 --> 00:29:34,530
İndi yenə bunu edək. Biz artıq Sammy narahat yoxdur.

502
00:29:34,530 --> 00:29:37,590
Biz yalnız burada edə bilərsiniz. Ooh! Sayı 2. Olduqca az sayda var.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. OK, yaxşı.

504
00:29:41,180 --> 00:29:43,770
Və təşəkkürlə, təsadüf ilə mən hərəkət yoxdur - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie o indi sağ yer var çünki.

506
00:29:45,910 --> 00:29:48,110
Yenə bunu edək və bu 2 uşaqlar bilməz.

507
00:29:48,110 --> 00:29:50,460
6. Olduqca az sayda var. Ooh! 8 mütləq böyükdür.

508
00:29:50,460 --> 00:29:53,410
4. 4 diqqət edək. Ooh! 3 hətta yaxşıdır.

509
00:29:53,410 --> 00:29:58,290
7 və 5. Beləliklə, biz indi nə etməliyəm - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Nin 6 saylı onu dəyişdirmək edək.

511
00:30:00,250 --> 00:30:03,570
Belə ki, 6 və 3 dəyişdirmək istəyirsinizsə,

512
00:30:03,570 --> 00:30:07,320
İndi cür, o olmalıdır yerləşir yaxın olduğunu 6 uğurlu kazanılmış etdik

513
00:30:07,320 --> 00:30:10,300
lakin burada yalnız təsadüf edir. Belə ki, indi burada gedək.

514
00:30:10,300 --> 00:30:13,430
8 olduqca kiçik rəqəmdir. Ooh! 4 kiçik.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. İndi nə etməliyəm? >> Swap. Məhz >>.

516
00:30:17,130 --> 00:30:19,010
Belə ki, indi daha sürətli bu cür etmək edək.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. 5 hara edir? Yaxşı. Okay.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 o harada qalmaq olur. Sizin adınız nədir? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie o harada qalmaq olur. 7 olur - Bakalým. 7, 8. Okay.

520
00:30:31,770 --> 00:30:35,100
Belə ki, 7 o harada qalmaq olur. Sizin adınız nədir? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Belə ki, Amna o harada qalmaq olur və o, indi harada sayı 8 olunur.

522
00:30:39,670 --> 00:30:43,960
OK, yaxşı. Biz yalnız baxmayaraq, burada özümüz üçün iş oluşturuyorsanız kimi hiss edir.

523
00:30:43,960 --> 00:30:47,440
Hansı nəticədə bu alqoritm çalışan vaxt var?

524
00:30:47,440 --> 00:30:51,900
Biz 8 lakin n bu insanlar haqqında düşünüyorsanız? >> Bu n var.

525
00:30:51,900 --> 00:30:55,440
Bu addımlar n edir, lakin biz hər bir zaman kontrol edirik.

526
00:30:55,440 --> 00:30:57,570
Okay. N lakin hər dəfə kontrol edirik?

527
00:30:57,570 --> 00:31:03,450
Bu addımlar n varsa OK, lakin, yalnız 1, 2, 3, 4 giderek size sort edə bilməzdi?

528
00:31:03,450 --> 00:31:05,590
Oh! OK, böyük bir fərq var.

529
00:31:05,590 --> 00:31:08,050
Belə n niyə kvadrat? Həqiqətən nə olub?

530
00:31:08,050 --> 00:31:12,130
Bu siyahıda n insanlar, lakin siyahıda ən kiçik adam tapmaq

531
00:31:12,130 --> 00:31:16,200
ən pis halda, nə qədər addımlar mənim üçün? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, doğru, ən pis halda, sayı 1, orada bütün yol, çünki

533
00:31:19,160 --> 00:31:20,990
Mən onu almaq və ya onun getmək üçün var.

534
00:31:20,990 --> 00:31:25,500
Və sonra nəhayət 1 kiçik idi həyata zaman, onları dəyişdirmək olduqca sürətli deyil.

535
00:31:25,500 --> 00:31:28,450
Amma indi başdan başlamaq və kim axtarmaq lazımdır?

536
00:31:28,450 --> 00:31:31,980
2 olan növbəti kiçik adam. Ən pis halda 2 harada?

537
00:31:31,980 --> 00:31:34,320
Aman Allah. Sonda onu da burada bütün yoludur.

538
00:31:34,320 --> 00:31:37,000
İndi mən yalnız başqa n addımlar, bir n addımlar etdik.

539
00:31:37,000 --> 00:31:41,200
Və biz n insanlar var və ən pis halda kiçik adam üz n addımlar varsa,

540
00:31:41,200 --> 00:31:45,230
daha n dəfə n, və biz yenə kvadrat n.

541
00:31:45,230 --> 00:31:47,280
Bu yaxşı hiss deyil.

542
00:31:47,280 --> 00:31:52,150
Və əslində, hətta ən yaxşı halda - onlar off sıralanır başlamaq Güman -

543
00:31:52,150 --> 00:31:59,080
Mənə bu n insanlar düzmək üçün bu alqoritmi istifadə üçün neçə addımlar edir?

544
00:31:59,080 --> 00:32:01,010
N kare. >> Eşitdim n kare. N kare Niyə?

545
00:32:01,010 --> 00:32:05,240
Siz hələ hər bir dəfə yoxlamaq var. >> Bəli.

546
00:32:05,240 --> 00:32:08,060
Və onları dəyişdirmək lazımdır. Biz insanlar ələmə növü var >> baxmayaraq

547
00:32:08,060 --> 00:32:10,770
mənada vizual biz bu çeşidlənir ki yalnız cür edə bilər ki,

548
00:32:10,770 --> 00:32:12,140
kompüter ki, ağıllı deyil.

549
00:32:12,140 --> 00:32:14,040
O, burada və burada və burada baxmaq olacaq

550
00:32:14,040 --> 00:32:16,610
lakin nə axtaran kiçik element olarsa,

551
00:32:16,610 --> 00:32:22,110
yalnız nə nöqtə ilə ən kiçik element aşkar bilirəm ki? Bir sonunda istəyirik.

552
00:32:22,110 --> 00:32:25,880
Amma bu nöqtədə yalnız hazırda kiçik element gördük.

553
00:32:25,880 --> 00:32:28,810
Siz mütləq dünya haqqında başqa bir şey bilmirəm.

554
00:32:28,810 --> 00:32:30,880
Belə ki, təkrar və yenidən getmək üçün var.

555
00:32:30,880 --> 00:32:34,880
>> Mən, tamam, 2 yoxlanılması edirəm, çünki mən həqiqətən bu dəfə lal baxmaq Belə ki, ən kiçik istəyirik,

556
00:32:34,880 --> 00:32:37,530
lakin mən hələ ümumi ki, bilmirəm.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. OK, yaxşı. 2 həqiqətən kiçik idi.

558
00:32:41,090 --> 00:32:43,150
İndi növbəti kiçik görər. Okay.

559
00:32:43,150 --> 00:32:48,350
3, hazırda kiçik istəyirik. Bakalým. 4, 5, 6, 7, 8. OK, daha uğurlu var.

560
00:32:48,350 --> 00:32:53,170
3 doğru yerdə həqiqətən idi. Amma yenə bunu və təkrar saxlamaq üçün gedirəm.

561
00:32:53,170 --> 00:32:55,990
Necə heç belə biraz daha yaxşı edə bilər?

562
00:32:55,990 --> 00:33:00,120
Əvəzində qədər pairwise kiçik olan böyük insanların bubble olan

563
00:33:00,120 --> 00:33:04,350
əvəzinə, sonra kiçik adam seçilməsi siyahısını geri və irəli gedən,

564
00:33:04,350 --> 00:33:09,780
niyə biz əvəzinə addım yeni siyahısını addım bu insanlar daxil deyil?

565
00:33:09,780 --> 00:33:13,080
Bu cəhd edək. İndi mənə bu şey durub sırala zəng edək.

566
00:33:13,080 --> 00:33:17,250
Belə ki, burada biz burada. Sayı 1. Mən bu siyahıda hər kəsdən qayğı yoxdur.

567
00:33:17,250 --> 00:33:21,310
Mənim məqsədi hazırda bir sorted siyahısı əvvəlində sayı 1 qoymaq üçün.

568
00:33:21,310 --> 00:33:23,910
Mən yalnız yaddaş 8 chunks çünki Mən təklif gedirəm

569
00:33:23,910 --> 00:33:28,670
özbaşına İndi, mənim guya çeşidlənməmiş siyahısı arasında divar am

570
00:33:28,670 --> 00:33:32,740
və mən iddia gedirəm mənə arxasında olan hər kəs çeşidlənir.

571
00:33:32,740 --> 00:33:34,680
Belə ki, indi biz sayı 1 var.

572
00:33:34,680 --> 00:33:39,240
Mən sıralanır siyahısı onu əlavə etmək istəyirəm, mən yalnız burada mənim divar hərəkət etmək gidiyorum belə

573
00:33:39,240 --> 00:33:43,930
və indi bu siyahıya çeşidlənir iddia, bu siyahı çeşidlənməmiş edir - ən azı indiyə qədər mən bildiyiniz kimi.

574
00:33:43,930 --> 00:33:46,070
Mən bir dəfə bütün nömrələri görmək bilməz.

575
00:33:46,070 --> 00:33:49,000
>> İndi sayı 2 qarşılaşma baş verir. Mən onunla nə etməliyəm?

576
00:33:49,000 --> 00:33:54,380
Mən sıralanır siyahısına İndi daxil edin. Amma ki, nə qədər asan bilərsiniz.

577
00:33:54,380 --> 00:33:59,650
Mən sadəcə baxmaq lazımdır. Sayı 1 var. Oh, açıq-aydın 2 ədəd 1-yan gedir.

578
00:33:59,650 --> 00:34:03,700
İndi 3-nə etməliyəm? Mən sıralanır siyahısına daxil etməzdən. Amma bu super asan idi.

579
00:34:03,700 --> 00:34:07,250
Bu asan super, bu super asan, bu super asan, super asan, super asandır.

580
00:34:07,250 --> 00:34:12,790
İndi hər şey mənə arxasında çeşidlənir və neçə addımlar idi?

581
00:34:12,790 --> 00:34:15,620
[Tələbələri] N. >> Belə ki, yalnız n edir. Biz uğurlu var.

582
00:34:15,620 --> 00:34:18,860
Yalnız n niyə oldu? >> [Tələbə] siyahısını sıralanır Çünki.

583
00:34:18,860 --> 00:34:21,630
Siyahısı artıq çeşidlənir. Beləliklə, biz xoşbəxt var.

584
00:34:21,630 --> 00:34:25,639
Amma biz bir alqoritm uğurlar belə çalışmalarını sürdürür ki, bu zaman nəzərdə

585
00:34:25,639 --> 00:34:29,420
lazımsız vaxt israf deyil ki, ən yaxşı ssenari.

586
00:34:29,420 --> 00:34:31,750
Beləliklə, biz indi bubble növ zəng lazımdır nə

587
00:34:31,750 --> 00:34:33,949
Ü pairwise qədər bubble insanlar cür.

588
00:34:33,949 --> 00:34:38,100
Biz təkrar kiçik adam yoluşdurmaq Biz indi seçim sort var.

589
00:34:38,100 --> 00:34:42,350
Onların mənsub olduğu biz növ fəal insanlar qoymaq harada və indi biz durub sırala var

590
00:34:42,350 --> 00:34:45,000
getdikcə sıralanır siyahısı.

591
00:34:45,000 --> 00:34:49,679
Biz bilər, burada bu uşaqlar üçün alqış bir tur. [Alqış]

592
00:34:49,679 --> 00:34:52,310
Nin Burada 5 dəqiqə fasilə etmək edək.

593
00:34:52,310 --> 00:34:55,139
Və biz geri gələndə, biz su bu alqoritmlərin bütün əsəcək

594
00:34:55,139 --> 00:35:00,260
yaxşı bir şey. Bütün hüquqlar. Çox təşəkkür edirik. Siz suvenirlər kimi bu davam edə bilərsiniz.

595
00:35:01,710 --> 00:35:04,330
Bütün hüquqlar. Biz geri.

596
00:35:04,330 --> 00:35:08,420
>> Və real sürətli recap, biz, çeşidlənməsi bu 3 müxtəlif yanaşmalar var idi

597
00:35:08,420 --> 00:35:13,000
olan bütün point nöqtəsinə almaq üçün olduğu Alex kimi kimsə

598
00:35:13,000 --> 00:35:16,930
Sean bilər kimi kimsə daha sürətli nömrə bir siyahısı axtarmaq bilər.

599
00:35:16,930 --> 00:35:19,830
Biz 8 ədəd belə sadə nümunələri olsa da,

600
00:35:19,830 --> 00:35:24,000
asanlıqla 8 web pages, 8 milyard web pages, extrapolate bilər

601
00:35:24,000 --> 00:35:26,680
Facebook və ya 800 milyon dostlar.

602
00:35:26,680 --> 00:35:30,090
Belə ki, bu alqoritmlərin əlbəttə, dəyərlər bu cür miqyaslı bilər

603
00:35:30,090 --> 00:35:32,300
və fikir etibarilə eynidir.

604
00:35:32,300 --> 00:35:36,140
Belə ki, bubble sırala biz cür böyük adam qədər bubbled olduğu ilk

605
00:35:36,140 --> 00:35:39,110
pairwise insanların dəyişdirmə hüququ bütün yol.

606
00:35:39,110 --> 00:35:42,040
Sonra yerləşir Mən bir az daha şüurlu biz seleksiya sort arayacaðým nə idi

607
00:35:42,040 --> 00:35:46,480
yenə siyahısını axtarır təkrar kiçik sayı seçilməsi və saxlanılır

608
00:35:46,480 --> 00:35:49,530
olan məntiqi nəticə siyahısını nəhayət sıralanır olunur.

609
00:35:49,530 --> 00:35:53,780
Sonra üçüncü, mən, onların müvafiq yer insanları daxil

610
00:35:53,780 --> 00:35:57,720
və biz siyahısına artıq sıralanır ki, bir çox göstərdi Məsələn etdi

611
00:35:57,720 --> 00:36:01,100
ancaq mesaj göndərmək idi ki, durub sırala işində,

612
00:36:01,100 --> 00:36:02,670
siz þanslý bilər.

613
00:36:02,670 --> 00:36:07,930
Nömrələri artıq ayrılır, bu, yalnız daha çox təsdiq siz n addımlar olacaq

614
00:36:07,930 --> 00:36:10,870
seleksiya sort isə bir az daha tunel görmə edirik

615
00:36:10,870 --> 00:36:14,360
və siz heç siyahı artıq sıralanır ki, dərk etmirlər.

616
00:36:14,360 --> 00:36:16,830
Belə ki, burada fəaliyyət bubble sırala bax edək.

617
00:36:16,830 --> 00:36:19,590
Aşağıdakı Məsələn, biz şaquli bar görmək üzeresiniz

618
00:36:19,590 --> 00:36:23,030
biz görüntüləmək baş çeşidlənməsi üzrə çeşidləyə bilərsiniz, belə ki, onun yüksəkliklərdə ədəd təşkil edir.

619
00:36:23,030 --> 00:36:26,630
Bu kiçik bar, sayı kiçik; böyük bar, böyük sayı.

620
00:36:26,630 --> 00:36:28,860
>> Və biz bu default sürətli oynamaq lazımdır.

621
00:36:28,860 --> 00:36:33,460
İndi bir az sürətli hərəkət edəcək, ancaq qırmızı 2 bar göstərən nə edir

622
00:36:33,460 --> 00:36:35,480
yan-yana müqayisədə olunur.

623
00:36:35,480 --> 00:36:39,520
Siz yaxından izləmək varsa, nə olar ki, barlar üçün həyata, əgər

624
00:36:39,520 --> 00:36:42,300
bir kiçik, sol sağ üçün böyük bir köçürülüb olur

625
00:36:42,300 --> 00:36:44,360
və sonra irəli saxlamaq.

626
00:36:44,360 --> 00:36:48,520
Biz təkrar bunu Belə ki, qeyd edir ki, kiçik bar

627
00:36:48,520 --> 00:36:51,090
sol yol inching saxlamaq gedir

628
00:36:51,090 --> 00:36:54,130
və ən böyük bar sağ yol inching saxlamaq niyyətindəyik.

629
00:36:54,130 --> 00:36:58,490
And olsun ki, biz bir model sağ tərəfində bütün yol bax başlayaraq edirik

630
00:36:58,490 --> 00:37:04,790
kimi biz 8 gördüm və sonra 7 nəticədə bizim insan siyahısı uzaq sonuna qədər burda.

631
00:37:04,790 --> 00:37:08,750
Belə ki, bu çox tez bir az yorucu olacaq, belə ki, məni bir an bu dayandırmaq bildirin.

632
00:37:08,750 --> 00:37:10,980
Mənə çox daha sürətli olmaq üçün sürətli dəyişiklik edək.

633
00:37:10,980 --> 00:37:15,380
Mən alqoritm dəyişən deyiləm, mən yalnız animasiya sürətli baş qəbul edirəm.

634
00:37:15,380 --> 00:37:18,410
Hələ bubble sırala eyni alqoritmi,

635
00:37:18,410 --> 00:37:21,910
indi siz bizim şifahi nümayiş daha sürətli edə bilərsiniz

636
00:37:21,910 --> 00:37:25,900
ən böyük elementləri həqiqətən üst qədər burda olunur.

637
00:37:25,900 --> 00:37:29,860
>> Bir kənara, bu az aşağı sol meydan və sağ alt

638
00:37:29,860 --> 00:37:33,520
siz yapýyorsun nə qədər müqayisə üçün yalnız az xatırlatmaları var.

639
00:37:33,520 --> 00:37:37,620
Amma indi, biz forma alaraq ki, piramidanın diqqət və orada gedir.

640
00:37:37,620 --> 00:37:41,510
Kiçik element sol, sağ ən böyük və başqa arasında hər şeyi edir.

641
00:37:41,510 --> 00:37:44,470
İndi əvəzinə seçim cür nəzər salaq.

642
00:37:44,470 --> 00:37:47,260
Mən irəli getmək və Stop edib gedirəm. Biz barlar yeni bir təsadüfi toplusunu olacaq.

643
00:37:47,260 --> 00:37:50,930
Seçim növ geri, təkrar-təkrar siyahısını keçir

644
00:37:50,930 --> 00:37:54,900
kiçik element həyata Yolma. Belə ki, burada seçim sortudur.

645
00:37:54,900 --> 00:37:58,390
Biz pairwise müqayisə deyilik, çünki indi baş var az iş kimi görünür

646
00:37:58,390 --> 00:38:02,590
lakin biz yalnız sol sağ kiçik elementləri albalı toplama və sort edirik.

647
00:38:02,590 --> 00:38:06,890
Ki, çox az vaxt bir dichotomy artıq var belə.

648
00:38:06,890 --> 00:38:11,820
Alqoritm bubble sırala kimi, n kvadrat vaxt deyilir Məhz

649
00:38:11,820 --> 00:38:16,100
və seçim sort kimi, bu ən pis halda çalışan dəfə həqiqətən.

650
00:38:16,100 --> 00:38:21,790
Məsələn, halda, demək seçim cür imkan

651
00:38:21,790 --> 00:38:27,240
Mən, həqiqətən, kiçik adam seçilməsi edirəm və burada ona verilməsi

652
00:38:27,240 --> 00:38:29,620
sonra təkrar edirəm, sonra, təkrar edirəm

653
00:38:29,620 --> 00:38:32,070
amma edə bilər yüngül optimallaşdırma var idi.

654
00:38:32,070 --> 00:38:35,040
>> Bu halda Sammy - Mən sayı burada 1 köçürülüb kimi -

655
00:38:35,040 --> 00:38:38,630
Mən bundan sonra onunla nə ehtiyac idi? >> [Tələbə] onu buraxın.

656
00:38:38,630 --> 00:38:40,140
Sağ, onu tərk edirsiniz? Heç bir şey.

657
00:38:40,140 --> 00:38:44,310
Mən kiçik element seçilmiş əgər çünki Mən heç Sammy danışmaq lazım deyil

658
00:38:44,310 --> 00:38:48,580
və burada onu qoymaq, niyə tullantıların zaman mənim bütün siyahısını sonuna gedir?

659
00:38:48,580 --> 00:38:54,590
Növbəti iteration məni həqiqətən yalnız sayı 3, 2 nömrəli yalnız hərəkət etsinlər.

660
00:38:54,590 --> 00:38:57,640
Belə ki, əslində, mən n şeyi n dəfə bunu deyil.

661
00:38:57,640 --> 00:39:05,380
1 əşyalar, sonra n - - 2 əşyalar, sonra n - 3 şey, mən sonra n şeyi, n edirdi

662
00:39:05,380 --> 00:39:07,080
sonra n - 4, nöqtə, nöqtə, nöqtə.

663
00:39:07,080 --> 00:39:09,470
Biz yalnız deməkdir ki, həndəsi silsilə bir az var

664
00:39:09,470 --> 00:39:11,450
siz tədricən kiçik nömrələri qədər əlavə edirik.

665
00:39:11,450 --> 00:39:17,940
Not n + n + n + n lakin n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Və ümumiyyətlə olmaq nə işləyir -

667
00:39:21,380 --> 00:39:24,280
Mən yalnız bir an üçün burada board qədər mess gedirəm -

668
00:39:24,280 --> 00:39:28,990
/ 2 - o n kimi bir şey (1 n) olmaq üçün iş olacaq

669
00:39:28,990 --> 00:39:31,930
bütün istifadə etmək vərəqələri olduğu bir riyaziyyat kitabının geri baxmaq əgər biz yalnız cür

670
00:39:31,930 --> 00:39:33,410
düsturlar üçün.

671
00:39:33,410 --> 00:39:37,760
Yalnız bir şey ekliyorsanız n + n - 1 + n - 2, bu kimi bir şey ola işləyir.

672
00:39:37,760 --> 00:39:42,320
Biz yalnız bu cür həyata çoxaltmaq varsa ki, 2 kvadrat minus n / n oldu.

673
00:39:42,320 --> 00:39:46,400
Mən də, deyərək n kvadrat saxlanılır və mən ruhi qısa alaraq cür idi ki

674
00:39:46,400 --> 00:39:51,950
Əslində, n minus kvadrat N 2 bölünür həqiqətən addımlar doğru sıra çünki

675
00:39:51,950 --> 00:39:55,510
biz həqiqətən hesablanmışdır əgər seçim sort kimi alqoritm edəcək

676
00:39:55,510 --> 00:39:58,800
o müqayisələr bütün və biz bunu idi az məşğul bütün iş.

677
00:39:58,800 --> 00:40:03,210
Ancaq səmimi bir n heck qayğıları olan bir milyon və ya bir milyard kimi olur

678
00:40:03,210 --> 00:40:07,160
2 bölünür milyard kvadrat minus bir milyard edirik, əgər?

679
00:40:07,160 --> 00:40:09,320
Kare A milyard böyük bir sayı.

680
00:40:09,320 --> 00:40:13,580
Siz ilə bir milyard off bilər - n. Belə bir böyük deyil.

681
00:40:13,580 --> 00:40:18,770
Belə ki, daha böyük nömrələr almaq, az əhəmiyyətli bu aşağı sifarişli şərtləri var.

682
00:40:18,770 --> 00:40:24,230
Siz addımlar nömrələri quadrillions bəhs edirsinizsə, siz 2 bölmək əgər kim qayğıları?

683
00:40:24,230 --> 00:40:29,710
>> Belə ki, ümumiyyətlə, kompüter alimləri, hər şey amma ən böyük müddətli tullamaq edirlər

684
00:40:29,710 --> 00:40:33,140
və biz yalnız növ dünya sadələşdirmək və demək ki, alqoritm

685
00:40:33,140 --> 00:40:38,130
təxminən n kvadrat addımlar atmışdır. Yəni alqoritm çalışan zaman.

686
00:40:38,130 --> 00:40:40,760
Belə ki, biz bəzi konkret nümunələr yalnız bir anda bu qayıda bilərsiniz

687
00:40:40,760 --> 00:40:45,940
amma indi ki, intuitiv motivasiya sort yalnız bizim dünya sadələşdirilməsi arxasında var

688
00:40:45,940 --> 00:40:51,170
və daha bütün bu xülya düsturlar nəzərə almaq çox ən mühüm şərtləri haqqında söhbət.

689
00:40:51,170 --> 00:40:53,540
Belə ki, seçim cür idi və biz bir az uğurlu var.

690
00:40:53,540 --> 00:40:57,360
Nin durub sırala baxaq. Mənə davam və bu həmçinin başlamaq edək.

691
00:40:57,360 --> 00:41:00,330
İndi baş verən model qeyd, bir az fərqli

692
00:41:00,330 --> 00:41:03,410
və biz, təsadüfi nömrələri ilə açılmış

693
00:41:03,410 --> 00:41:06,890
lakin biz, həqiqətən, pis halda addımların sayı saymaq olarsa,

694
00:41:06,890 --> 00:41:11,070
siyahısı sağ üçün tamamilə açılmış, əgər

695
00:41:11,070 --> 00:41:13,380
biz yalnız daha çox həyata n addımlar olacaq.

696
00:41:13,380 --> 00:41:18,240
>> Lakin siyahı geri həqiqətən olsaydı - məsələn, burada bu halda -

697
00:41:18,240 --> 00:41:23,860
biz, həqiqətən, bu halda bir çox iş var sonra bildiriş.

698
00:41:23,860 --> 00:41:27,080
Bu bir daha iş növü kimi və bu cür siz hiss etməlidir

699
00:41:27,080 --> 00:41:30,900
sol bu kiçik elementləri almaq və biz uğursuz var, çünki ki etmək.

700
00:41:30,900 --> 00:41:34,210
Siyahısı əks təsadüfən sıralanır edilib.

701
00:41:34,210 --> 00:41:38,110
Əksinə, durub sırala biz burada biz insanlar ilə nə taklit əgər

702
00:41:38,110 --> 00:41:42,670
başlamaq sıralanır hər kəs ilə başlayan və sonra, burada, olduqca yaxşı alqoritm var?

703
00:41:42,670 --> 00:41:45,010
Artıq, əslində, sıralanır edir.

704
00:41:45,010 --> 00:41:48,670
Belə ki, bu şeyi bizə alaraq dəqiq nə qədər vaxt ümumiləşdirilməsi cəhd edək

705
00:41:48,670 --> 00:41:52,360
əslində çox sadə olan bir jargon və bit və ya notation təqdim

706
00:41:52,360 --> 00:41:54,320
və fanciness cür təklif edir.

707
00:41:54,320 --> 00:41:59,030
Burada Bu şey, bu böyük O ekranda, kompüter alim ümumiyyətlə istifadə edəcəyik

708
00:41:59,030 --> 00:42:03,640
alqoritm və ən pis halda çalışan zaman təsvir etmək.

709
00:42:03,640 --> 00:42:07,360
>> Yenə, ən pis halda, bu tamamilə kontekstində asılı deyil.

710
00:42:07,360 --> 00:42:10,890
Biz ən pis halda ilə nə demək tamamilə söhbət sorun əsasında dəyişir.

711
00:42:10,890 --> 00:42:14,550
Amma çeşidlənməsi halda, nə pis mümkün ssenari var?

712
00:42:14,550 --> 00:42:17,860
Yalnız bizim üçün çox iş deməkdir kimi hiss çünki hər şey geri edir.

713
00:42:17,860 --> 00:42:21,330
Düşünürəm ki, biz bu günə qədər gördüm ki, alqoritmlər bir neçə aşağı jotted etdik:

714
00:42:21,330 --> 00:42:24,930
xətti axtarış, telefon kitab və ya kağız parçaları kimi ikili axtarış

715
00:42:24,930 --> 00:42:28,960
sonra bubble sırala seçim sort və durub sort kimi biz insanlar gördüm

716
00:42:28,960 --> 00:42:31,770
və sonra 1 digər nəticədə növ daxil adlanan olacaq ki.

717
00:42:31,770 --> 00:42:37,710
Belə ki, ən pis halda xətti axtarış, neçə addımlar bu sayı 7 tapmaq sürer

718
00:42:37,710 --> 00:42:40,690
Sean üzlü kimi n qapı var əgər? >> [Tələbə] N.

719
00:42:40,690 --> 00:42:44,180
N. Biz n böyük O yazmaq olacaq.

720
00:42:44,180 --> 00:42:47,010
Mən yalnız bir blanklara doldurmaq üçün gedirəm. Bu blanklarının bir grid edir.

721
00:42:47,010 --> 00:42:52,990
Lakin xətti axtarış ən yaxşı halda, 7, siyahı çox əvvəlində ola

722
00:42:52,990 --> 00:42:55,520
və Sean siyahısı əvvəlində axtarır açılmış ola bilər.

723
00:42:55,520 --> 00:42:58,940
Siz xətti axtarış istifadə edərək, yalnız sağ və ya sol bəlkə sağ kontrol edirik əgər -

724
00:42:58,940 --> 00:43:02,650
onlar ekvivalent edirik - ən yaxşı halda necə bir çox addımlar güc xətti axtarış

725
00:43:02,650 --> 00:43:05,550
Sean nin alqoritmi kimi, almaq? Sadəcə 1 addım.

726
00:43:05,550 --> 00:43:09,450
>> Mən omega notation var ki, gedirəm.

727
00:43:09,450 --> 00:43:11,570
Bu kapital omega edir.

728
00:43:11,570 --> 00:43:15,000
Omega yalnız ən yaxşı halda zaman çalışan deyərək sexy yoldur.

729
00:43:15,000 --> 00:43:18,900
Belə ki, ən yaxşı halda çalışan zaman bir addım və ya daimi sayı addımlar -

730
00:43:18,900 --> 00:43:24,270
Bu halda 1 - amma ən pis halda, böyük O, həqiqətən n addımlar var.

731
00:43:24,270 --> 00:43:28,110
Və burada bu, teta, biz, həqiqətən, indi baxmaq fikrində deyilik.

732
00:43:28,110 --> 00:43:30,090
Bu xüsusi misal üçün müvafiq deyil.

733
00:43:30,090 --> 00:43:31,990
Amma indi ikili axtarış edək.

734
00:43:31,990 --> 00:43:35,990
Binar axtarış ilə ən pis halda, nə qədər addımlar bu sayı 7 tapmaq üçün almaq niyyətindədir

735
00:43:35,990 --> 00:43:38,340
və ya biz aradığınız nə? >> [Tələbə] Giriş n.

736
00:43:38,340 --> 00:43:40,980
Hələ Alex uğursuz var kimi çünki log n almaq niyyətindədir

737
00:43:40,980 --> 00:43:44,030
biz həqiqətən şəkildə problemi ilə işləyərkən

738
00:43:44,030 --> 00:43:48,220
və o, o baxdı son qapı qədər sayı 7 tapmadı

739
00:43:48,220 --> 00:43:51,720
baxmayaraq, ədalət də, o, yol boyunca müəyyən qapılar tullamaq var

740
00:43:51,720 --> 00:43:56,920
ən pis halda ikili axtarış log n çalışan zaman var.

741
00:43:56,920 --> 00:43:59,230
Və yenə bu ayırıcı və fəth danışır.

742
00:43:59,230 --> 00:44:01,140
Amma nə yaxşı halda haqqında?

743
00:44:01,140 --> 00:44:04,790
O mərhələyə qədər gəlib və Alex həqiqətən doğru olduğunu ən yaxşı halda yaşadı.

744
00:44:04,790 --> 00:44:07,290
Olan ikili axtarış neçə addımlar idi? >> [Tələbə] 1.

745
00:44:07,290 --> 00:44:09,380
1, yalnız o uğurlu var, çünki.

746
00:44:09,380 --> 00:44:12,520
Omega ən yaxşı halda ssenariləri aiddir, çünki ki, gözəl var

747
00:44:12,520 --> 00:44:15,770
yalnız təsadüfi lal uğurlar belə ən yaxşı halda giriş.

748
00:44:15,770 --> 00:44:18,900
>> İndi, bu da indi izin boş yalnız cür olacaq.

749
00:44:18,900 --> 00:44:21,010
Bubble sırala haqqında indi?

750
00:44:21,010 --> 00:44:24,290
Bubble sırala ilə ən pis halda, hər kəs sırayla edir

751
00:44:24,290 --> 00:44:26,380
biz bubbling bir çox var.

752
00:44:26,380 --> 00:44:30,190
Amma nə qədər addımlar pis halda etmək niyyətindədir ki? >> Kare [tələbə] N.

753
00:44:30,190 --> 00:44:32,550
Bu barədə düşünüyorsanız, çünki bu, n kare olub

754
00:44:32,550 --> 00:44:36,410
siyahısını tamamilə geri olduqda - 8 buraya, 1 burada artıq -

755
00:44:36,410 --> 00:44:40,530
şey bubble başlamaq kimi, 8 nömrəli bu yol, bu şəkildə hərəkət edir

756
00:44:40,530 --> 00:44:44,540
Bu yol, bu yol, lakin burada pis halda sayı 7 edir?

757
00:44:44,540 --> 00:44:47,720
Burada o, orada hələ də. Belə ki, biz təkrar etmək lazımdır.

758
00:44:47,720 --> 00:44:53,190
1 addımlar, sonra n - - 2 addımları biz sonra n addımlar n aldığı ki var.

759
00:44:53,190 --> 00:44:55,960
Və bunun üçün mənim söz əgər - siz cür ki, həyata çoxaltmaq əgər

760
00:44:55,960 --> 00:45:00,110
o təxminən biz yalnız indi üçün ignore lazımdır ki, bəzi digər şərtlərinə sonunda kvadrat n oldu -

761
00:45:00,110 --> 00:45:06,890
sonra ən pis halda bubble cür kvadrat n, vermək və ya almaq.

762
00:45:06,890 --> 00:45:09,490
Amma bubble sırala ilə ən yaxşı halda haqqında nə?

763
00:45:09,490 --> 00:45:13,050
Nə yaxşı ssenari deyil? Nömrələr Bütün artıq sıralanır.

764
00:45:13,050 --> 00:45:15,920
Mən istifadə Heuristic, mən istifadə hilesi nə idi

765
00:45:15,920 --> 00:45:20,110
Mən heç bir iş idi və buna görə də erkən dayandırmaq ki, həyata keçirilməsi üçün?

766
00:45:20,110 --> 00:45:23,590
[Tələbə] bir dəfə yoxlayın. >> Dəfə yoxlayın. Amma yol boyu nə edirdi?

767
00:45:23,590 --> 00:45:26,130
Mən qəbul neçə svopları takip saxlanılması edilib.

768
00:45:26,130 --> 00:45:30,650
Və mən barmaqları hər hansı svopları sayılır əgər, sonra heç bir iş etdik həyata keçirilir.

769
00:45:30,650 --> 00:45:34,300
Mən, əlbəttə, daha heç bir iş etmək üçün cəhd deyil, mən yalnız dayandıra bilər.

770
00:45:34,300 --> 00:45:37,830
>> Belə ki, bubble sırala ən yaxşı halda siyahı artıq sıralaması zaman,

771
00:45:37,830 --> 00:45:41,530
Siz ən yaxşı halda zaman çalışan ki, omega notation nə demək istərdiniz?

772
00:45:41,530 --> 00:45:48,040
Bu, sadəcə n edir. Biz bəzi işlər var, amma biz yalnız iş 1 stroll yetmeyecek var.

773
00:45:48,040 --> 00:45:50,490
Və burada da mən bu hissəsi boş buraxın gedirəm.

774
00:45:50,490 --> 00:45:52,430
İndi seçim sort.

775
00:45:52,430 --> 00:45:56,010
Seçim sort mənim təkrar kiçik adam Yolma idi.

776
00:45:56,010 --> 00:45:58,380
Və biz idi çalışan zaman nə demək idi?

777
00:45:58,380 --> 00:46:00,590
Idi n pis halda kare.

778
00:46:00,590 --> 00:46:05,220
Və təəssüf ki, ən yaxşı halda da kvadrat n oldu

779
00:46:05,220 --> 00:46:08,840
Mən bütün dünya ələmə baxış sort yoxdur çünki;

780
00:46:08,840 --> 00:46:13,140
Mən yalnız həqiqətən kiçik adam gördük tam iteration sonra bilirik.

781
00:46:13,140 --> 00:46:15,860
Belə seçim sort cür ki, mənada gücünü zaptetti

782
00:46:15,860 --> 00:46:17,920
lakin alt intuitiv və bu növüdür.

783
00:46:17,920 --> 00:46:21,470
Siz bütün loops üçün nested bir neçə yazmaq çünki qədər kod olduqca asan

784
00:46:21,470 --> 00:46:24,620
adətən, bu kiçik element axtarır keçir

785
00:46:24,620 --> 00:46:27,840
və o, siyahının sonunda yer aldığı kiçik element qoyur.

786
00:46:27,840 --> 00:46:29,900
Belə ki, burada çox ticarət-off olmalıdır olacaq.

787
00:46:29,900 --> 00:46:34,440
Siz düşünmək və həqiqətən kodu yazmaqla bir şey inkişaf edir, vaxt məbləği

788
00:46:34,440 --> 00:46:39,460
Bir alqoritm daha yaxşı və daha sürətli performans istəyirsinizsə çox yaxşı çox vaxt bilər.

789
00:46:39,460 --> 00:46:41,780
>> Ancaq kodu şey həqiqətən yalnız cür əgər sürətli və çirkli

790
00:46:41,780 --> 00:46:45,000
və yalnız növ, siz hesab edə bilərsiniz stupidest mümkün fikir almaq

791
00:46:45,000 --> 00:46:47,580
kodu bir neçə dəqiqə çəkə bilər, amma böyük data dəsti ilə

792
00:46:47,580 --> 00:46:49,580
Sizin alqoritm run saat bilər.

793
00:46:49,580 --> 00:46:51,690
Və hətta mən məzunu məktəb bəzən bu ticarət-off edəcək.

794
00:46:51,690 --> 00:46:55,660
Bu 3am olardı, mən çox böyük data set təhlil etməyə çalışırdı

795
00:46:55,660 --> 00:46:59,650
Mən edirdi təhlükəsizlik araşdırma ilə bağlı və ya 5 dəqiqə sərf edilib

796
00:46:59,650 --> 00:47:03,210
tweaking məlumatları təhlil və yatmaq mənim proqram

797
00:47:03,210 --> 00:47:08,420
dərhal çalışır və yatmaq deyil, və ya yalnız sağ əldə 8 saat sərf edirlər.

798
00:47:08,420 --> 00:47:10,530
Və orada da şüurlu qərar növü var.

799
00:47:10,530 --> 00:47:12,740
Az inkişaf zaman, daha çox yuxu.

800
00:47:12,740 --> 00:47:14,780
Retrospect, mən yəqin ki, həvəsləndirmək lazımdır ki,

801
00:47:14,780 --> 00:47:19,120
Burada məqsəd kodu keyfiyyət optimize zaman,

802
00:47:19,120 --> 00:47:21,280
lakin çox real dünyanın bir çox ağlabatan ticarət-off edir.

803
00:47:21,280 --> 00:47:25,130
Az vaxt az, performans və ya əksinə.

804
00:47:25,130 --> 00:47:28,110
Belə ki, burada biz nəhayət teta haqqında danışmaq imkanı.

805
00:47:28,110 --> 00:47:32,830
Theta notation kompüter elm söhbət yetişdirmək bilərsiniz bir şeydir

806
00:47:32,830 --> 00:47:36,160
böyük O və omega eyni olmalıdır nə zaman.

807
00:47:36,160 --> 00:47:40,160
Siz teta həqiqətən bu sıx bağlı cür ki, mesaj göndərmək üçün deyirəm.

808
00:47:40,160 --> 00:47:43,340
Ssenari yaxşı və ya pis asılı olmayaraq, bu kvadrat n edir.

809
00:47:43,340 --> 00:47:46,510
Belə ki, burada bu hekayələr yalnız müvafiq deyil.

810
00:47:46,510 --> 00:47:48,560
Insertion sort, biz baxdı son bir

811
00:47:48,560 --> 00:47:50,830
harada yalnız sağ yer hər kəs daxil edilib.

812
00:47:50,830 --> 00:47:54,930
Biz burada gördüyümüz kimi ən yaxşı halda nə durub növ çalışan zaman idi?

813
00:47:54,930 --> 00:47:57,250
[Tələbə] ən yaxşı halda? >> Ən yaxşı halda.

814
00:47:57,250 --> 00:48:00,100
>> Ən yaxşı halda hər kəs sıralanır çünki, N edilib

815
00:48:00,100 --> 00:48:02,580
və Sammy və başqa heç bir həqiqətən bütün hərəkət idi.

816
00:48:02,580 --> 00:48:04,610
Onlar doğru yerdə artıq idi.

817
00:48:04,610 --> 00:48:08,570
Ən yaxşı halda belə durub sort, bu halda, n.

818
00:48:08,570 --> 00:48:12,770
Amma ən pis halda kvadrat N növü var. Niyə?

819
00:48:12,770 --> 00:48:16,230
Insanlar mənim siyahısı əks qaydada deyil,

820
00:48:16,230 --> 00:48:21,260
Mən ilk sayı 8 ilə başlamaq və mən burada olan sağ mövqeyi, onu daxil və ya öz.

821
00:48:21,260 --> 00:48:25,270
Yan hərəkət I növ. Bu uşaqlar, o, çeşidlənməmiş ya o çeşidlənir.

822
00:48:25,270 --> 00:48:28,970
Amma indi kim növbəti tapmaq üçün nə? >> [Tələbə] 7.

823
00:48:28,970 --> 00:48:31,250
Ən pis halda 7 bu əks qaydada çünki.

824
00:48:31,250 --> 00:48:34,920
>> Belə ki, burada 7 deyil. 7 harada aid deyil? Əlbəttə, məni arxasında.

825
00:48:34,920 --> 00:48:39,460
Amma indi 7 faktiki olaraq, dərhal məni arxasında lakin sayı 8 arxasında deyil məxsusdur

826
00:48:39,460 --> 00:48:41,880
Mən "deyə Pardon, 8 nömrəli var ki, bu yol hərəkət edin bilər

827
00:48:41,880 --> 00:48:44,640
"7 yer açmaq üçün?" İndi 6 üzləşir.

828
00:48:44,640 --> 00:48:48,530
"Oh, sayı 8 və 7 saylı pardon, siz 6 otaq etmək üçün hərəkət edə bilər?"

829
00:48:48,530 --> 00:48:52,360
Belə ki, başqa sözlə, durub sırala ilə, mən çox hərəkət etdiklərini deyiləm, baxmayaraq ki,

830
00:48:52,360 --> 00:48:56,330
arxamda insanların daha çox iş və kimsə zaman dəyəri var ki.

831
00:48:56,330 --> 00:48:58,000
Bu kompüter vaxt başa olacaq.

832
00:48:58,000 --> 00:49:01,450
Belə ki, durub sırala halda, biz hələ də əziyyət çəkirlər.

833
00:49:01,450 --> 00:49:06,260
Siz addımlar ümumi sayı əlavə başlamaq, biz təxminən n kvadrat vuruş son

834
00:49:06,260 --> 00:49:11,160
Bu uşaqlar ki siyahısına geri daxil etmək insan üçün otaq etmək lazımdır, çünki.

835
00:49:11,160 --> 00:49:15,960
Və bu halda teta yalnız əl-da xüsusi hekayə tətbiq deyil.

836
00:49:15,960 --> 00:49:21,100
Bu gözəl və yaxşı bütün var. Biz çalışan zaman söhbət bu 3 müxtəlif yolları var.

837
00:49:21,100 --> 00:49:26,370
Biz həqiqətən bir alqoritm qədər kod cəhd Amma bu həqiqətən real olaraq nə deməkdir?

838
00:49:26,370 --> 00:49:31,620
>> Orada daha yaxşı alqoritm var ki, mənə təklif edək

839
00:49:31,620 --> 00:49:33,740
özü bəzi ticarət-off var.

840
00:49:33,740 --> 00:49:36,890
Biz bu cür daxil zəng olacaq, və bu sehirli alqoritm növ var

841
00:49:36,890 --> 00:49:42,840
yalnız daha sürətli birtəhər işləyir, və ən azı pseudocode ilə ifadə etmək üçün asandır.

842
00:49:42,840 --> 00:49:46,900
Bu alqoritm birləşmə sort həyata keçirilməsi aşağıdakı kimi olacaq.

843
00:49:46,900 --> 00:49:50,860
Bir ağlı başında olma çek var birinci - nə n nömrələri, n insanlar, - siz n elementləri verilmiş olduğunuzda.

844
00:49:50,860 --> 00:49:56,340
N 2-dən az olarsa, sort yalnız dayanır daxil. Bu danışmaq, geri qaytarır.

845
00:49:56,340 --> 00:50:00,830
N 2-dən az olduğu halda niyə dayandırmaq olar? >> [Işitilemez tələbə cavab]

846
00:50:00,830 --> 00:50:04,480
Sağ. Və yenə n siyahısında sayı deyil, n siyahı ölçüsü.

847
00:50:04,480 --> 00:50:07,660
N 2-dən az olarsa, o, listenizi ya 1 deməkdir

848
00:50:07,660 --> 00:50:09,640
1 sıra əgər burada açıq-aydın, sıralanır edirsinizsə

849
00:50:09,640 --> 00:50:11,710
və ya düzmək üçün heç bir şey yoxdur bu halda 0,

850
00:50:11,710 --> 00:50:13,570
biz baza halda bu cür lazımdır.

851
00:50:13,570 --> 00:50:20,350
Siyahısı əlaqəsi yalnız var ki, qısa deyil, sanki bir şey yoxdur. Qayıt.

852
00:50:20,350 --> 00:50:25,090
Əks halda elementləri sol yarım sort, sonra elementləri hüququ yarım sort

853
00:50:25,090 --> 00:50:27,410
sonra 2 sıralanır yarıya indirir daxil.

854
00:50:27,410 --> 00:50:32,130
>> Mən necə elementləri sort isteyen edirəm elə bu cür bir az etmək kimi görünür

855
00:50:32,130 --> 00:50:34,900
və "sağ yarım sort, sol yarım Sırala." mənə izah edirik

856
00:50:34,900 --> 00:50:37,240
Mən kimi oldum "Bütün hüququ. Necə sol yarım sort yoxdur?"

857
00:50:37,240 --> 00:50:40,670
"Işlər, sonra sol yarısının, sol yarım sırala sol yarım hüququ yarım sort və".

858
00:50:40,670 --> 00:50:44,060
Siz cyclically bu sort nə deməkdir müəyyən cür etdiyiniz

859
00:50:44,060 --> 00:50:46,790
lakin bu halda həqiqətən parlaq olduğunu çıxır.

860
00:50:46,790 --> 00:50:50,230
Bu həqiqətən başa heç vaxt bu sonsuz dövrü deyil

861
00:50:50,230 --> 00:50:52,550
zaman son deyil, çünki? >> [Tələbə] siz 1 şey çatmaq zaman.

862
00:50:52,550 --> 00:50:54,220
Siz 1 şey çatdıqda.

863
00:50:54,220 --> 00:50:57,850
8 xalqı ilə başlamaq bilər və demək baxmayaraq Belə ki, "bu insanların sol yarım sırala

864
00:50:57,850 --> 00:51:00,480
Bu 4 nəfər, "sonra demək," necə sol yarım sort yoxdur? "

865
00:51:00,480 --> 00:51:03,450
"Yaxşı, burada 2 nəfər sort". Və sonra, gibisin "Bütün hüququ, gözəl."

866
00:51:03,450 --> 00:51:05,520
"Necə bu insanların sol yarım sort yoxdur?"

867
00:51:05,520 --> 00:51:09,040
"Yalnız burada 1 nəfər sort". İndi parlaq nazil nədir?

868
00:51:09,040 --> 00:51:13,050
Mən 1 nəfər düzmək lazımdır. Done. Mən heç bir işi yoxdur.

869
00:51:13,050 --> 00:51:16,580
Ancaq indi bu şəxs düzmək üçün var, lakin onlar bir şəxsin, heç bir istəyirik.

870
00:51:16,580 --> 00:51:21,490
>> Belə ki, sehrli yəqin bu üçüncü addım var: sıralanır yarıya indirir daxil.

871
00:51:21,490 --> 00:51:25,770
Belə ki, daxil sort bu parlaq fikir edir ki, bir böyük problem qırmaq əgər

872
00:51:25,770 --> 00:51:28,650
2 kiçik, eyni ölçülü problemlərini

873
00:51:28,650 --> 00:51:32,710
və sonra sonunda kiçik həllər birlikdə yapışqan yalnız növ

874
00:51:32,710 --> 00:51:34,720
Mən ki, biz daha yaxşı [tıqqıltı səs] çox edə bilərsiniz ki, təklif

875
00:51:34,720 --> 00:51:38,050
seleksiya sort və ya durub sırala dən.

876
00:51:38,050 --> 00:51:40,690
Mən, həqiqətən, yarım saat üçün məhəl olduğunuz, lakin mən, həqiqətən neler bilmirəm

877
00:51:40,690 --> 00:51:45,040
Bu gün xaricində. [Whirring səs] [gülüş]

878
00:51:45,040 --> 00:51:49,660
Belə ki, biz dost Rob Bowden bir az köməyi ilə bu edə bilərsiniz əgər in görək.

879
00:51:49,660 --> 00:51:52,810
Birləşmə sort prosesində 2 böyük addımlar var.

880
00:51:52,810 --> 00:51:56,400
Birincisi, davamlı yarıya indirir daxil fincanların siyahısı split

881
00:51:56,400 --> 00:51:59,610
biz onlara yalnız 1 fincan ilə siyahıları bir dəstə qədər.

882
00:51:59,610 --> 00:52:02,150
Siyahısını tək sayda varsa, narahat olmayın

883
00:52:02,150 --> 00:52:04,830
və onların arasında mükəmməl təmiz cut edə bilməz.

884
00:52:04,830 --> 00:52:08,740
Yalnız özbaşına əlavə kubok daxil daxil olan siyahısı seçin

885
00:52:08,740 --> 00:52:11,320
Belə nin bu siyahıları split imkan verir.

886
00:52:12,420 --> 00:52:14,570
İndi 2 siyahıları var.

887
00:52:18,930 --> 00:52:20,930
İndi biz 4 siyahıları var.

888
00:52:25,730 --> 00:52:28,740
İndi biz hər siyahısında bir fincan 8 siyahıları var.

889
00:52:28,740 --> 00:52:31,520
Belə ki, 1 adım üçün deyil.

890
00:52:31,520 --> 00:52:37,280
Addım 2 biz dəfələrlə biz əvvəl öyrənildi birləşmə alqoritmi istifadə siyahıları cüt birləşməsi.

891
00:52:37,280 --> 00:52:44,320
108 və 15 Birləşdirən biz siyahısına 15, 108 ilə qədər.

892
00:52:45,240 --> 00:52:51,330
50 və 4 birləşmə biz 4, 50 ilə qədər.

893
00:52:51,330 --> 00:52:56,950
8 və 42 Birləşdirən biz 8, 42 ilə qədər.

894
00:52:57,790 --> 00:53:04,360
Və 23 və 16 birləşmə biz, 16 ilə 23 qədər.

895
00:53:04,360 --> 00:53:08,030
İndi bütün siyahıları ölçüsü 2 daşıyır.

896
00:53:08,030 --> 00:53:10,980
4 siyahıları hər çeşidlənir edək ki,

897
00:53:10,980 --> 00:53:14,230
biz yenə siyahıları cüt birləşməsi başlaya bilərsiniz.

898
00:53:14,230 --> 00:53:22,150
15 və 108, 4 və 50 Birləşdirən biz ilk, sonra 15, 4 almaq

899
00:53:22,150 --> 00:53:26,250
sonra 50, sonra 108.

900
00:53:26,250 --> 00:53:33,020
8, 42 və 16, 23 Birləşdirən biz ilk sonra 8, 16, almaq

901
00:53:33,020 --> 00:53:37,170
sonra 23, sonra 42.

902
00:53:37,170 --> 00:53:42,490
Belə ki, indi biz size 4 yalnız 2 siyahıları ki, hər biri çeşidlənir.

903
00:53:42,490 --> 00:53:45,940
Belə ki, indi biz bu 2 siyahıları daxil.

904
00:53:45,940 --> 00:53:54,230
İlk 4 almaq, sonra 8 almaq, onda biz 15 almaq

905
00:53:54,230 --> 00:54:05,280
və 16 və 23, 42 və 50 və 108.

906
00:54:05,280 --> 00:54:09,020
Və biz tamamlayın. İndi sıralanır siyahısı var.

907
00:54:09,020 --> 00:54:13,740
>> Rob biz hələ həyata deyil ki, bir şey istifadə edərək cür idi.

908
00:54:13,740 --> 00:54:16,540
Bu təklif edilib, ancaq həqiqətən bunu etmədi.

909
00:54:16,540 --> 00:54:19,230
O, təklif edir ki, fincan ilə fiziki bir şey edirdi

910
00:54:19,230 --> 00:54:23,680
o zaman başqa bir resurs sərf edilib. >> [Tələbə] Space. >> Bu yer idi.

911
00:54:23,680 --> 00:54:27,360
Burada yer olduğu o bi səviyyədə masa bu cür idi ki,

912
00:54:27,360 --> 00:54:31,960
və burada yer əslində o iki dəfə çox yer istifadə edir eyham edilmişdir

913
00:54:31,960 --> 00:54:36,390
daxil sort, bubble sırala və ya seçimi sırala - - İndiyədək bizim alqoritmlərin heç kimi

914
00:54:36,390 --> 00:54:40,780
lakin o, geri və irəli hərəkət şeyi cür bu əlavə yer yararlanarak edilib

915
00:54:40,780 --> 00:54:42,600
üçün hər şeyi tutarken.

916
00:54:42,600 --> 00:54:47,540
Biz bir sorted siyahısı var kimi hiss baxmayaraq bir müddət etmişdir kimi, bu hiss.

917
00:54:47,540 --> 00:54:51,060
Əslində, nə Rob edirdi məhz bu alqoritm idi.

918
00:54:51,060 --> 00:54:56,780
O, ilk, ölçüsü n problemi etdi sol yarısı və sağ yarım onu ​​bölünür.

919
00:54:56,780 --> 00:54:59,380
O fincan köçürülüb zaman var. Sonra prosesi təkrar.

920
00:54:59,380 --> 00:55:03,390
O, burada artıq burada 2 2 dəstləri daxil 4 bölünür.

921
00:55:03,390 --> 00:55:08,520
Sonra prosesi təkrar və o müxtəlif fincan hər 1 2 dəst daxil 2 bölünür.

922
00:55:08,520 --> 00:55:11,000
Parlaq imkan yaranır yerləşir ki var.

923
00:55:11,000 --> 00:55:15,840
Hekayə ki nöqtədə Rob, ölçüsü 1, 8 siyahıları idi

924
00:55:15,840 --> 00:55:18,860
olan bütün artıq sıralanır idi.

925
00:55:18,860 --> 00:55:20,630
>> Belə ki, nə o, nə davam etdi?

926
00:55:20,630 --> 00:55:25,260
Pairwise bu sorted siyahısı və bu sorted siyahısı etmiş və onlara birləşdi.

927
00:55:25,260 --> 00:55:28,200
Sonra o, bu etmiş və onlara birləşdi, bu bir və onlara birləşdi

928
00:55:28,200 --> 00:55:30,670
bu bir və onlara birləşdi.

929
00:55:30,670 --> 00:55:32,390
Və o, nə gələcək mi?

930
00:55:32,390 --> 00:55:36,580
O böyük siyahıları yenidən birləşdi və sonra böyük siyahıları yenidən birləşdi.

931
00:55:36,580 --> 00:55:41,170
İndi yalnız daxilən bu barədə düşünmək Əgər, o, həqiqətən nə idi?

932
00:55:41,170 --> 00:55:45,450
O yarısında yarısında yarısında yarısında problem ayırıcı edilib

933
00:55:45,450 --> 00:55:47,600
bu super kiçik siyahıları almaq üçün.

934
00:55:47,600 --> 00:55:51,290
Sonra o, ikiqat, cüt cüt cüt birləşdirən cür idi.

935
00:55:51,290 --> 00:55:54,120
O, biz belə uzaq gördüm kimi çox iş kimi iki dəfə edirdi

936
00:55:54,120 --> 00:55:56,930
parçala və fəth, lakin böyük cəlb bir şey ilə.

937
00:55:56,930 --> 00:55:59,630
Iki dəfə çox iş belə böyük deyil. Bu yalnız daimi amil var.

938
00:55:59,630 --> 00:56:03,920
Və daha əvvəl hesab ifadə kimi, yalnız daimi amillər həyata keçməyə gedirəm

939
00:56:03,920 --> 00:56:10,170
dəfə 2 kimi. Kim qayğıları? Hələ addımlar çox olan dəfə 2, 2 milyard varsa.

940
00:56:10,170 --> 00:56:13,160
Belə ki, bu birləşmə addım əsas fikir görünür.

941
00:56:13,160 --> 00:56:17,000
Nin qarşısında yalnız sayca bu vasitəsilə gəzmək edək - Oh ki, hələ davam deyil.

942
00:56:17,000 --> 00:56:22,890
Bu sayı yalnız həqiqətən bunu oynayır necə vasitəsilə gəzmək edək.

943
00:56:22,890 --> 00:56:25,940
Bu əsasən yalnız bir az yoxsul adam animasiya edir.

944
00:56:25,940 --> 00:56:27,750
Bu təklif edək.

945
00:56:27,750 --> 00:56:31,480
Birləşmə növ çalışan zaman - biz yalnız bu söhbət bir yol lazımdır.

946
00:56:31,480 --> 00:56:34,380
Bu riyaziyyat deyil, bu özümüzü ifadə yığcam şəkildə yalnız növüdür.

947
00:56:34,380 --> 00:56:39,080
Beləliklə T dəfə təmsil n nə təmsil? >> [Tələbə] Bu həcmi -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] problemin həcmi, insanların sayı.

949
00:56:41,400 --> 00:56:45,470
Mən n insanlar düzmək üçün çalışan zaman zaman 0 məbləği olacaq iddia edirəm

950
00:56:45,470 --> 00:56:50,290
N 1 stəkan və ya fincan varsa, düzmək üçün heç bir şey yoxdur, çünki 2-dən azdır. əgər

951
00:56:50,290 --> 00:56:55,160
Amma ümumiyyətlə, mən çalışan zaman n elementləri düzmək üçün təklif gedirəm

952
00:56:55,160 --> 00:56:59,350
bu sol yarım sort üçün lazım vaxt plus sağ yarım olacaq

953
00:56:59,350 --> 00:57:03,110
plus - bu əlavə + n var? >> [Tələbə] Merge sort.

954
00:57:03,110 --> 00:57:07,260
[Malan] Burada n / 2 elementlər varsa, çünki həqiqətən, birləşmə var

955
00:57:07,260 --> 00:57:11,500
və burada n / 2 elementlər var, onları daxil etmək üçün nə qədər vaxt lazımdır?

956
00:57:11,500 --> 00:57:15,050
Just Rob kimi, burada artıq bu qırpmaq üçün, bəlkə, buraya dərmək

957
00:57:15,050 --> 00:57:17,120
burada dərmək, buraya dərmək, buraya qırpmaq.

958
00:57:17,120 --> 00:57:19,400
Siz bir fincan hər toxunmaq lazımdır.

959
00:57:19,400 --> 00:57:22,030
4 fincan müsbət 4 fincan var, əgər ki, 8 stəkan deyil

960
00:57:22,030 --> 00:57:25,200
və ya ümumiyyətlə, 8 n fincan.

961
00:57:25,200 --> 00:57:28,470
Belə ki, birləşmə addım biz, n kimi ifadə edə bilər

962
00:57:28,470 --> 00:57:31,330
və sanki neçə dəfə fiziki toxunub Rob daxildir

963
00:57:31,330 --> 00:57:33,410
o Styrofoam fincan biri.

964
00:57:33,410 --> 00:57:35,850
Belə ki, indi bir ixtiyari Məsələn nə edək.

965
00:57:35,850 --> 00:57:41,850
16 stəkan varsa, nə Rob-nin alqoritm, 16 stəkan istifadə edərək, çeşidlənməsi ilə çalışan zaman?

966
00:57:41,850 --> 00:57:44,710
8 stəkan düzmək üçün edir zaman 2 dəfə tutar

967
00:57:44,710 --> 00:57:46,920
burada biz burada 8 stəkan, çünki, 8 stəkan.

968
00:57:46,920 --> 00:57:51,520
Mən belə biz bu an üçün T kimi ümumiləşdirmək edirik, edir ki, nə qədər bilmirəm.

969
00:57:51,520 --> 00:57:53,320
Kim nə bilir?

970
00:57:53,320 --> 00:57:58,990
Amma indi recursively ya təkrar-təkrar eyni sual və sıralayabilirsiniz.

971
00:57:58,990 --> 00:58:01,920
8 stəkan düzmək üçün nə qədər vaxt lazımdır?

972
00:58:01,920 --> 00:58:07,030
Demək gedirəm 8 stəkan, 4 stəkan müsbət 4 fincan düzmək üçün edir müddəti edir

973
00:58:07,030 --> 00:58:08,880
sonra onları birlikdə birləşdirilməsi.

974
00:58:08,880 --> 00:58:13,080
Fine. Biz artıq bir dövrü nəzərə alırıq. 4 fincan düzmək üçün necə sürer?

975
00:58:13,080 --> 00:58:19,150
4 fincan sort üçün lazım vaxt 2 fincan plus 2 fincan çeşidlənməsi üstəgəl birləşmə prosesdir.

976
00:58:19,150 --> 00:58:21,440
Fine. 2 fincan düzmək üçün necə sürer?

977
00:58:21,440 --> 00:58:26,290
2 fincan 1 fincan düzmək üçün edir müddəti plus başqa bir fincan sort edir zaman

978
00:58:26,290 --> 00:58:29,040
üstəgəl bu daxil edir müddəti olan yalnız 2-dir.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Son sual. 1 fincan düzmək üçün necə sürer?

980
00:58:33,340 --> 00:58:37,260
Burada biz əvvəllər edib istədiyiniz proqnozlaşdırılır ki, baza haldır.

981
00:58:37,260 --> 00:58:42,250
Bu problemlərin kiçik düzmək üçün heç bir iş görür ki,

982
00:58:42,250 --> 00:58:44,120
vasitəsilə indi ki, dərəcəli məktəb stil növ,

983
00:58:44,120 --> 00:58:46,460
biz yalnız da geri bu rəqəmlər sayede başlamaq bilərsiniz

984
00:58:46,460 --> 00:58:50,630
Biz indi 1 T nə, mən 1-T 0 plug bilər.

985
00:58:50,630 --> 00:58:54,420
Mən ali qədər plug bilər 2 T, mənə cavab verəcək.

986
00:58:54,420 --> 00:58:56,930
Bu mənə daha yüksək qədər plug bilər 4 T, verəcək.

987
00:58:56,930 --> 00:58:58,920
Bu mənə daha yüksək qədər plug bilər 8 T, verəcək.

988
00:58:58,920 --> 00:59:04,330
Mən, həqiqətən, bu cavab sayede ki, riyaziyyat həyata əgər,

989
00:59:04,330 --> 00:59:08,590
Mən 16 T 64 deyil almaq.

990
00:59:08,590 --> 00:59:12,090
Və 64 nə təmsil edir?

991
00:59:12,090 --> 00:59:15,700
T 16 deyil, Bəli, o, 16 dəfə 4 var.

992
00:59:15,700 --> 00:59:20,120
Mən bu şey çalışan zaman sort daxil adlı indi iddia -

993
00:59:20,120 --> 00:59:22,590
və biz belə uzaq gördüm olanları fanciest olacaq -

994
00:59:22,590 --> 00:59:26,160
adlı olacaq n log n edilir

995
00:59:26,160 --> 00:59:31,140
neçə dəfə yarım stəkan bütün dəstə split Rob bilər, çünki? N olun.

996
00:59:31,140 --> 00:59:34,370
Bu telefon kitab misal kimi eyni, bu öz-özünə hesablanması misal kimi eyni.

997
00:59:34,370 --> 00:59:36,380
>> Neçə dəfə yarısında bir şey bölmək olar?

998
00:59:36,380 --> 00:59:38,410
Lakin, bu birləşmə addım var.

999
00:59:38,410 --> 00:59:42,920
Siz təkrar və yenidən yarısı daxil fincan bölmək ola bilər

1000
00:59:42,920 --> 00:59:45,640
ancaq olacaq hər dəfə daxil etmək.

1001
00:59:45,640 --> 00:59:48,270
Və biz n fincan birləşmə n addımlar atır ki, əvvəllər bildirib

1002
00:59:48,270 --> 00:59:52,060
bir fincan yoluşdurmaq var, çünki bir fincan yoluşdurmaq və siz bir dəfə hər bir fincan toxunmaq var

1003
00:59:52,060 --> 00:59:53,510
yalnız Rob kimi etdi.

1004
00:59:53,510 --> 00:59:59,430
Biz bir şey log n dəfə edirik və biz bu tekrarlamalar hər n şeyi edirik Beləliklə, əgər,

1005
00:59:59,430 --> 01:00:03,090
o halvings hər biz n dəfə log n var.

1006
01:00:03,090 --> 01:00:07,220
Biz bu misalda 16-plug Belə ki, əgər 16 dəfə, 16 giriş -

1007
01:00:07,220 --> 01:00:10,600
Mən baza tərtib deyil etdik, çünki bu artıq işə görə narahat deyil -

1008
01:00:10,600 --> 01:00:16,100
lakin 16 baza 2 günlük dəfə 4 64 16 4.

1009
01:00:16,100 --> 01:00:22,350
Amma əksinə, biz 16 nömrələri ilə bubble sırala ya seçilməsi sort və ya durub sırala istifadə əgər,

1010
01:00:22,350 --> 01:00:26,420
n 16 Əgər çalışan zaman nə olardı?

1011
01:00:26,420 --> 01:00:33,310
Bu 256 olan 16 kvadrat ola bilər, siz olduqca bütün riyaziyyat əməl etməyib, hətta, ki,

1012
01:00:33,310 --> 01:00:38,390
256 64 böyükdür. Bu həqiqətən burada sehrli paket var.

1013
01:00:38,390 --> 01:00:41,990
Və pset sizi iradə kimi kiçik nümunələri bu ilə iş ki, həyata

1014
01:00:41,990 --> 01:00:44,260
daha intuitiv bütün edir.

1015
01:00:44,260 --> 01:00:49,070
Amma həqiqətən bu alqoritm hissi baxımından deməkdir ki, nə bu:

1016
01:00:49,070 --> 01:00:54,520
Biz, həqiqətən, burada birləşmə sort baxsaq - mənim burada bu pəncərə onu qoparmaq imkan -

1017
01:00:54,520 --> 01:00:58,560
bu bu alqoritmlərin bütün 3. qovuşdurmağımız bir az fərqli nümunəsidir -

1018
01:00:58,560 --> 01:01:01,440
bubble, seçilməsi, və birləşməsi - yan yalnız yan.

1019
01:01:01,440 --> 01:01:03,740
>> Onlar təsadüfi bar ilə başladı və yaxşı.

1020
01:01:03,740 --> 01:01:06,240
Heç bir başqa bir əsas üstünlüyə malikdir.

1021
01:01:06,240 --> 01:01:09,500
Mən bir anda gedirəm bu animasiyalar hər basın - Start Start Start -

1022
01:01:09,500 --> 01:01:13,270
Mən kimi sürətli kimi, belə ki, eyni zamanda təxminən, onlar bütün başlanğıc,

1023
01:01:13,270 --> 01:01:17,450
və vaxt çalışan bubble sırala nin pis halda nə ki, hesab edək? >> Kare [tələbə] N.

1024
01:01:17,450 --> 01:01:21,560
N kare. Vaxt çalışan seçimi sort ən pis halda? N kare.

1025
01:01:21,560 --> 01:01:25,150
Və birləşmə cür aydın deyil - siz kifayət qədər bütün riyaziyyat əməl etməmişlər, hətta indi,

1026
01:01:25,150 --> 01:01:30,610
daha intuitiv zamanla olmaq lazımdır - biz iddia, n dəfə log n.

1027
01:01:30,610 --> 01:01:35,210
Və log n çox ciddi az n sonra biz böyük nömrələri var, çünki

1028
01:01:35,210 --> 01:01:40,230
n dəfə log n n dəfə daha kiçik n və ya n kvadrat edir.

1029
01:01:40,230 --> 01:01:44,410
Belə ki, nə o, həqiqətən çalışan zaman baxımından daha yaxşı alqoritm olmaq hiss etmir

1030
01:01:44,410 --> 01:01:50,380
n dəfə log n kimi kare n fərqli? Burada getmək. Basın, basın basın.

1031
01:01:55,690 --> 01:01:58,650
>> Bu birləşmə sort kimi bir şey istifadə etmək nə deməkdir var.

1032
01:01:58,650 --> 01:02:01,680
Biz bir an var. Burada nə görmək edək.

1033
01:02:09,440 --> 01:02:12,440
Kimin pul bubble sırala edir [chuckles]?

1034
01:02:14,960 --> 01:02:16,730
Bu olduqca bəzən daxil asılıdır.

1035
01:02:16,730 --> 01:02:18,120
Bakalým.

1036
01:02:18,120 --> 01:02:23,320
Hadi. O qədər alıcı var kimi hiss edir. >> [Tələbə] bubble sırala Go!

1037
01:02:23,320 --> 01:02:27,370
[Tələbələri murmuring]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Bəli, Bəli.

1039
01:02:29,120 --> 01:02:34,520
[Murmuring tələbələr] getmək, getmək, Go!

1040
01:02:37,210 --> 01:02:40,450
[Alqış] [bütün təzahürat]

1041
01:02:40,450 --> 01:02:46,240
Belə ki, indi 1 son final demo ilə, əgər riyaziyyat ətrafında fikrinizi kesmek üçün bir az çətin deyil

1042
01:02:46,240 --> 01:02:49,280
və ya orada vizual növ, siz həqiqətən sürətlə eşitmək bilər

1043
01:02:49,280 --> 01:02:51,000
fərqli müxtəlif alqoritmləri.

1044
01:02:51,000 --> 01:02:53,900
Bu, həqiqətən, asılı səslənir ki, hazırlanmış animasiya kimsə

1045
01:02:53,900 --> 01:02:56,980
dəyişdirmə prosesi və bar hündürlüyü.

1046
01:02:56,980 --> 01:03:00,440
Biz burada görürsünüz ki, bir neçə çeşidlənməsi alqoritmlərin insanlar fikir ki, orada var.

1047
01:03:00,440 --> 01:03:03,660
Bu ilk bir durub sırala olacaq və bu yolu gedəcək

1048
01:03:03,660 --> 01:03:07,090
və necə bu müxtəlif alqoritmləri iş səsli hissi verir.

1049
01:03:07,090 --> 01:03:09,080
Burada durub sortudur.

1050
01:03:09,080 --> 01:03:18,410
[Elektron səs siqnalı]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Elektron səs siqnalı sürətli]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Seçim sort.

1054
01:03:48,950 --> 01:04:03,580
[Elektron səs siqnalı sürətli]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge sort.

1056
01:04:05,770 --> 01:04:17,270
[Elektron səs siqnalı]

1057
01:04:17,270 --> 01:04:20,180
[Gülüş] [səs siqnalı aşağı yavaşlatır]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome sort.

1059
01:04:22,590 --> 01:04:38,580
[Elektron səs siqnalı]

1060
01:04:39,740 --> 01:04:46,150
>> Bu CS50 edir. Gələn həftə görəcəksiniz. [Alqış və təzahürat]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]