1
00:00:00,000 --> 00:00:11,904
>> [Bermain muzik]

2
00:00:11,904 --> 00:00:12,910
>> PROFESOR: Baiklah.

3
00:00:12,910 --> 00:00:16,730
Ini adalah CS50 dan ini adalah
hujung minggu tiga.

4
00:00:16,730 --> 00:00:20,230
Oleh itu, kita berada di sini hari ini, tidak dalam Sanders
Teater, dan bukannya di Perpustakaan Weidner.

5
00:00:20,230 --> 00:00:23,170
Di dalam yang merupakan studio
dikenali sebagai Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
atau yang akan kita katakan Studio H, atau hendaklah
kita iaitu- jika anda menikmati jenaka itu,

7
00:00:28,310 --> 00:00:30,540
ia sebenarnya dari
rakan sekelas, Mark, dalam talian,

8
00:00:30,540 --> 00:00:32,420
yang mencadangkan sebanyak melalui Twitter.

9
00:00:32,420 --> 00:00:34,270
Sekarang apa yang sejuk kira-kira
berada di sini dalam studio

10
00:00:34,270 --> 00:00:38,410
adalah bahawa saya dikelilingi oleh hijau ini
dinding, skrin hijau atau chromakey,

11
00:00:38,410 --> 00:00:43,290
boleh dikatakan, yang bermaksud bahawa ini CS50
pasukan pengeluaran, tanpa pengetahuan saya

12
00:00:43,290 --> 00:00:47,380
sekarang, boleh meletakkan
saya yang paling mana-mana sahaja di dunia,

13
00:00:47,380 --> 00:00:48,660
untuk lebih baik atau untuk lebih teruk.

14
00:00:48,660 --> 00:00:51,800
>> Sekarang apa yang akan berlaku, masalah set
dua adalah di tangan anda untuk minggu ini,

15
00:00:51,800 --> 00:00:53,830
tetapi dengan masalah set
tiga minggu akan datang,

16
00:00:53,830 --> 00:00:56,600
anda akan dicabar dengan
permainan yang dipanggil 15 tahun,

17
00:00:56,600 --> 00:00:58,960
pihak memihak lama yang
anda mungkin ingat menerima

18
00:00:58,960 --> 00:01:02,030
sebagai kanak-kanak yang mempunyai sejumlah
nombor yang boleh slaid ke atas, ke bawah,

19
00:01:02,030 --> 00:01:05,790
kiri dan kanan, dan ada satu jurang
dalam teka-teki, di mana anda

20
00:01:05,790 --> 00:01:07,840
sebenarnya boleh slaid orang-orang keping teka-teki.

21
00:01:07,840 --> 00:01:11,150
Akhirnya anda menerima ini
teka-teki dalam beberapa perintah semi rawak,

22
00:01:11,150 --> 00:01:12,940
dan matlamatnya adalah untuk
menyelesaikannya, atas ke bawah,

23
00:01:12,940 --> 00:01:16,310
kiri ke kanan, dari satu
sepanjang jalan sehingga melalui 15.

24
00:01:16,310 --> 00:01:19,360
>> Malangnya, pelaksanaan
anda akan mempunyai di tangan

25
00:01:19,360 --> 00:01:21,590
akan menjadi perisian
berdasarkan, bukan fizikal.

26
00:01:21,590 --> 00:01:25,280
Anda sebenarnya akan perlu untuk menulis
kod dengan mana seorang pelajar atau pengguna boleh

27
00:01:25,280 --> 00:01:26,760
bermain permainan 15.

28
00:01:26,760 --> 00:01:29,030
Dan sebenarnya, di penggodam
edisi permainan 15 tahun,

29
00:01:29,030 --> 00:01:32,155
anda akan menjadi satu cabaran untuk melaksanakan,
bukan hanya bermain sekolah lama ini

30
00:01:32,155 --> 00:01:35,010
permainan, tetapi penyelesaian yang
daripadanya, melaksanakan mod tuhan,

31
00:01:35,010 --> 00:01:38,280
boleh dikatakan, yang benar-benar
menyelesaikan teka-teki untuk manusia,

32
00:01:38,280 --> 00:01:41,080
dengan menyediakan mereka dengan tanda-tanda,
selepas tanda-tanda, selepas tanda-tanda.

33
00:01:41,080 --> 00:01:42,280
Jadi lebih pada minggu depan.

34
00:01:42,280 --> 00:01:43,720
Tetapi itulah apa yang akan berlaku.

35
00:01:43,720 --> 00:01:47,610
>> Buat masa ini masih ingat bahawa pada awal minggu ini
kita mempunyai cliffhanger ini, jika anda akan,

36
00:01:47,610 --> 00:01:52,560
mana yang terbaik yang kami lakukan menyusun
bijak adalah had atas daripada besar o n

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

38
00:01:53,210 --> 00:01:56,520
Dalam erti kata lain, jenis gelembung,
jenis pemilihan, jenis kemasukan,

39
00:01:56,520 --> 00:01:59,120
semua daripada mereka, manakala yang berbeza
dalam pelaksanaannya,

40
00:01:59,120 --> 00:02:03,480
diturunkan ke dalam n kuasa berjalan
masa dalam kes yang paling teruk.

41
00:02:03,480 --> 00:02:06,010
Dan kita biasanya menganggap bahawa
kes yang paling teruk untuk menyusun

42
00:02:06,010 --> 00:02:08,814
adalah salah satu yang input anda
benar-benar ke belakang.

43
00:02:08,814 --> 00:02:11,980
Dan sesungguhnya, ia mengambil masa agak beberapa langkah
untuk melaksanakan setiap mereka algoritma.

44
00:02:11,980 --> 00:02:15,110
>> Kini pada akhir sangat kelas
ingat, kita berbanding jenis gelembung

45
00:02:15,110 --> 00:02:19,390
terhadap jenis pemilihan terhadap seorang lain
yang kita dipanggil merge pada masa itu,

46
00:02:19,390 --> 00:02:22,120
dan saya mencadangkan supaya ia mengambil
kesempatan daripada pengajaran dari minggu

47
00:02:22,120 --> 00:02:24,060
sifar, membahagi dan menakluk.

48
00:02:24,060 --> 00:02:28,810
Dan entah bagaimana mencapai beberapa jenis
logaritma masa berjalan akhirnya,

49
00:02:28,810 --> 00:02:31,024
bukan sesuatu
itu semata-mata kuadratik.

50
00:02:31,024 --> 00:02:33,440
Dan ia tidak cukup logaritma,
ia agak lebih daripada itu.

51
00:02:33,440 --> 00:02:36,520
Tetapi jika anda ingat dari kelas,
ia adalah banyak, lebih cepat.

52
00:02:36,520 --> 00:02:38,210
Mari kita lihat di mana kita berhenti.

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

54
00:02:41,880 --> 00:02:45,370
>> Jenis Bubble berbanding pilihan
semacam berbanding jenis merge.

55
00:02:45,370 --> 00:02:47,700
Sekarang mereka semua berjalan, dalam
teori, pada masa yang sama.

56
00:02:47,700 --> 00:02:50,510
CPU sedang berjalan pada kelajuan yang sama.

57
00:02:50,510 --> 00:02:54,990
Tetapi, anda boleh merasakan bagaimana membosankan ini
sangat cepat akan menjadi,

58
00:02:54,990 --> 00:02:58,790
dan betapa cepat, apabila kita menyuntik
sedikit algoritma minggu sifar,

59
00:02:58,790 --> 00:03:00,080
kita boleh mempercepatkan perkara.

60
00:03:00,080 --> 00:03:01,630
>> Jadi semacam tanda kelihatan menakjubkan.

61
00:03:01,630 --> 00:03:05,220
Bagaimana kita boleh memanfaatkan, dalam usaha
untuk menyusun nombor dengan lebih cepat.

62
00:03:05,220 --> 00:03:07,140
Nah mari kita berfikir kembali
untuk ramuan yang kita

63
00:03:07,140 --> 00:03:10,380
mempunyai kembali pada minggu sifar, iaitu
mencari seseorang dalam buku telefon,

64
00:03:10,380 --> 00:03:12,380
dan ingat bahawa
pseudokod yang kita dicadangkan,

65
00:03:12,380 --> 00:03:14,560
melalui mana kita boleh mencari
seseorang seperti Mike Smith,

66
00:03:14,560 --> 00:03:16,310
melihat sesuatu yang kecil seperti ini.

67
00:03:16,310 --> 00:03:20,820
>> Sekarang kita lihat khususnya
di garisan 7 dan 8, dan 10 dan 11,

68
00:03:20,820 --> 00:03:25,240
yang mendorong gelung yang, di mana kami terus
kembali ke garisan 3 lagi, dan sekali lagi,

69
00:03:25,240 --> 00:03:26,520
dan lagi.

70
00:03:26,520 --> 00:03:31,790
Tetapi ternyata bahawa kita boleh melihat
algoritma ini, di sini dalam kod pseudo,

71
00:03:31,790 --> 00:03:33,620
sedikit lebih holistik.

72
00:03:33,620 --> 00:03:35,960
Malah, apa yang saya cari
di sini pada skrin,

73
00:03:35,960 --> 00:03:41,180
adalah satu algoritma untuk mencari
Mike Smith di antara beberapa set halaman.

74
00:03:41,180 --> 00:03:45,520
Dan sesungguhnya, kita boleh memudahkan ini
algoritma mereka garis 7 dan 8,

75
00:03:45,520 --> 00:03:49,860
dan 10 dan 11 untuk hanya mengatakan ini,
yang saya telah dibentangkan di sini dalam kuning.

76
00:03:49,860 --> 00:03:52,210
Dalam erti kata lain, jika Mike
Smith yang lebih awal dalam buku ini,

77
00:03:52,210 --> 00:03:55,004
kita tidak perlu untuk menentukan langkah
demi langkah sekarang bagaimana untuk pergi mencari dia.

78
00:03:55,004 --> 00:03:56,920
Kami tidak perlu nyatakan
untuk kembali ke baris 3,

79
00:03:56,920 --> 00:03:58,960
mengapa tidak kita sebaliknya,
katakan, secara umum,

80
00:03:58,960 --> 00:04:01,500
mencari Mike dalam
separuh kiri buku ini.

81
00:04:01,500 --> 00:04:03,960
>> Sebaliknya, jika Mike
sebenarnya kemudian dalam buku ini,

82
00:04:03,960 --> 00:04:07,540
mengapa tidak kita hanya memetik carian unquote
untuk Mike dalam separuh kanan buku ini.

83
00:04:07,540 --> 00:04:11,030
Dalam erti kata lain, mengapa tidak kita hanya
semacam menyepak bola kepada diri kita sendiri dan berkata:

84
00:04:11,030 --> 00:04:13,130
mencari Mike dalam ini
subset buku ini,

85
00:04:13,130 --> 00:04:16,279
dan menyerahkan kepada kami yang sedia ada
algoritma untuk memberitahu kami

86
00:04:16,279 --> 00:04:18,750
bagaimana untuk mencari Mike dalam
bahawa separuh kiri buku ini.

87
00:04:18,750 --> 00:04:20,750
Dengan kata lain, kita
algoritma berfungsi sama ada

88
00:04:20,750 --> 00:04:24,670
buku telefon tebal ini, ini
ketebalan, atau mana-mana ketebalan sekalipun.

89
00:04:24,670 --> 00:04:27,826
Oleh itu, kita boleh secara rekursif
menentukan algoritma ini.

90
00:04:27,826 --> 00:04:29,950
Dalam erti kata lain, pada
skrin di sini, adalah algoritma

91
00:04:29,950 --> 00:04:33,130
untuk mencari Mike Smith
antara muka surat buku telefon.

92
00:04:33,130 --> 00:04:37,410
Jadi dalam talian 7 dan 10, mari kita
hanya mengatakan perkara tersebut.

93
00:04:37,410 --> 00:04:40,250
Dan saya menggunakan istilah ini seketika
lalu, dan sesungguhnya, rekursi

94
00:04:40,250 --> 00:04:42,450
adalah topik yang hangat diperkatakan sekarang,
dan ia adalah proses ini

95
00:04:42,450 --> 00:04:47,210
melakukan sesuatu kitaran oleh entah bagaimana
menggunakan kod yang anda sudah mempunyai,

96
00:04:47,210 --> 00:04:49,722
dan memanggil sekali lagi,
dan sekali lagi, dan lagi.

97
00:04:49,722 --> 00:04:51,930
Kini ia akan menjadi penting
yang kita entah bagaimana bawah

98
00:04:51,930 --> 00:04:53,821
keluar, dan tidak berbuat demikian panjang tak terhingga.

99
00:04:53,821 --> 00:04:56,070
Jika tidak kita akan
mempunyai sesungguhnya gelung tak terhingga.

100
00:04:56,070 --> 00:04:59,810
Tetapi mari kita lihat jika kita boleh meminjam idea ini
rekursi, melakukan sesuatu lagi

101
00:04:59,810 --> 00:05:03,600
dan lagi dan lagi, untuk menyelesaikan
masalah sorting melalui merge

102
00:05:03,600 --> 00:05:05,900
jenis, lebih-lebih cekap.

103
00:05:05,900 --> 00:05:06,970
>> Oleh itu, saya memberikan anda bergabung apapun.

104
00:05:06,970 --> 00:05:07,920
Mari kita lihat.

105
00:05:07,920 --> 00:05:10,850
Jadi di sini adalah kod pseudo, dengan
yang kita boleh melaksanakan menyusun,

106
00:05:10,850 --> 00:05:12,640
menggunakan algoritma ini dipanggil jenis merge.

107
00:05:12,640 --> 00:05:13,880
Dan ia cukup sekadar ini.

108
00:05:13,880 --> 00:05:15,940
Dalam input n elemen,
dalam erti kata lain, jika anda

109
00:05:15,940 --> 00:05:18,830
diberikan n elemen dan nombor dan
huruf atau apa-apa input adalah,

110
00:05:18,830 --> 00:05:22,430
jika anda diberi n unsur, jika
n adalah kurang daripada 2, hanya kembali.

111
00:05:22,430 --> 00:05:22,930
Betul?

112
00:05:22,930 --> 00:05:26,430
Kerana jika n adalah kurang daripada 2, yang
bermakna bahawa senarai saya unsur-unsur

113
00:05:26,430 --> 00:05:30,446
sama ada saiz 0 atau 1, dan
dalam kedua-dua kes-kes remeh,

114
00:05:30,446 --> 00:05:31,570
senarai tersebut sudah disusun.

115
00:05:31,570 --> 00:05:32,810
Jika tidak ada senarai, ia disusun.

116
00:05:32,810 --> 00:05:35,185
Dan jika ada senarai panjang
1, ia jelas disusun.

117
00:05:35,185 --> 00:05:38,280
Jadi algoritma hanya perlu
benar-benar melakukan sesuatu yang menarik,

118
00:05:38,280 --> 00:05:40,870
jika kita mempunyai dua atau lebih
unsur-unsur yang diberikan kepada kita.

119
00:05:40,870 --> 00:05:42,440
Jadi mari kita lihat keajaiban itu.

120
00:05:42,440 --> 00:05:47,500
Yang lain menyusun separuh kiri unsur-unsur,
kemudian menyusun separuh yang betul unsur-unsur,

121
00:05:47,500 --> 00:05:49,640
kemudian menggabungkan bahagian disusun.

122
00:05:49,640 --> 00:05:52,440
Dan apa jenis minda lentur
di sini, adalah bahawa saya tidak benar-benar

123
00:05:52,440 --> 00:05:56,190
seolah-olah telah memberitahu anda
apa-apa sahaja lagi, bukan?

124
00:05:56,190 --> 00:05:59,560
Apa yang saya katakan adalah, diberikan senarai
n unsur, menyusun separuh kiri,

125
00:05:59,560 --> 00:06:01,800
daripada setengah yang betul, maka
menggabungkan bahagian disusun,

126
00:06:01,800 --> 00:06:03,840
tetapi di mana sos rahsia sebenar?

127
00:06:03,840 --> 00:06:05,260
Di mana algoritma?

128
00:06:05,260 --> 00:06:09,150
Nah ternyata bahawa kedua-dua baris
pertama, separuh semacam meninggalkan unsur-unsur,

129
00:06:09,150 --> 00:06:13,970
dan jenis kerja separuh daripada unsur-unsur,
adalah panggilan rekursif, jadi untuk bercakap.

130
00:06:13,970 --> 00:06:16,120
>> Lagipun, pada ini
bila masa, saya perlu

131
00:06:16,120 --> 00:06:18,950
algoritma yang boleh digunakan untuk
menyusun sejumlah besar unsur?

132
00:06:18,950 --> 00:06:19,450
Ya.

133
00:06:19,450 --> 00:06:20,620
Ia adalah di sini.

134
00:06:20,620 --> 00:06:25,180
Ia adalah di sini pada skrin, dan
jadi saya boleh menggunakan set yang sama langkah-langkah

135
00:06:25,180 --> 00:06:28,500
untuk menyusun separuh kiri,
yang saya boleh separuh betul.

136
00:06:28,500 --> 00:06:30,420
Dan sesungguhnya, sekali lagi, dan lagi.

137
00:06:30,420 --> 00:06:34,210
Jadi entah bagaimana atau lain-lain, dan kita akan tidak lama lagi
melihat ini, keajaiban merge

138
00:06:34,210 --> 00:06:37,967
tertanam dalam yang sangat akhir
line, menggabungkan bahagian disusun.

139
00:06:37,967 --> 00:06:39,300
Dan yang seolah-olah agak intuitif.

140
00:06:39,300 --> 00:06:41,050
Anda mengambil dua bahagian, dan anda,
entah bagaimana, menggabungkan mereka bersama-sama,

141
00:06:41,050 --> 00:06:43,260
dan kita akan melihat ini
secara kukuh dalam seketika.

142
00:06:43,260 --> 00:06:45,080
>> Tetapi ini adalah algoritma yang lengkap.

143
00:06:45,080 --> 00:06:46,640
Dan mari kita melihat dengan jelas mengapa.

144
00:06:46,640 --> 00:06:50,912
Well andaikan bahawa kita diberikan ini sama
lapan elemen sini pada skrin, satu

145
00:06:50,912 --> 00:06:53,120
melalui lapan, tetapi ia
agar seolah-olah rawak.

146
00:06:53,120 --> 00:06:55,320
Dan matlamat yang di tangan adalah
untuk menyusun elemen-elemen ini.

147
00:06:55,320 --> 00:06:58,280
Nah bagaimana saya boleh pergi tentang
melakukannya menggunakan, sekali lagi,

148
00:06:58,280 --> 00:07:00,407
bergabung apapun, seperti kod pseudo ini?

149
00:07:00,407 --> 00:07:02,740
Dan sekali lagi, dicat di dlm wol ini dalam
fikiran anda, hanya untuk seketika.

150
00:07:02,740 --> 00:07:05,270
Kes pertama adalah cukup
remeh, jika ia adalah kurang daripada 2,

151
00:07:05,270 --> 00:07:07,060
hanya kembali, tidak ada kerja yang perlu dilakukan.

152
00:07:07,060 --> 00:07:09,290
Jadi benar-benar ada hanya tiga
langkah-langkah untuk benar-benar perlu diingat.

153
00:07:09,290 --> 00:07:11,081
Sekali lagi, dan sekali lagi, Saya
akan mahu mempunyai

154
00:07:11,081 --> 00:07:13,980
untuk menyusun separuh kiri,
menyusun separuh yang betul,

155
00:07:13,980 --> 00:07:15,890
dan kemudian sekali mereka
dua bahagian yang disusun,

156
00:07:15,890 --> 00:07:18,710
Saya mahu bergabung mereka bersama-sama
ke dalam satu senarai yang disusun.

157
00:07:18,710 --> 00:07:19,940
Jadi menyimpan bahawa dalam fikiran.

158
00:07:19,940 --> 00:07:21,310
>> Jadi di sini adalah senarai asal.

159
00:07:21,310 --> 00:07:23,510
Mari kita merawat ini sebagai
pelbagai, seperti yang kita mula

160
00:07:23,510 --> 00:07:25,800
dalam seminggu dua, yang merupakan
blok berdampingan memori.

161
00:07:25,800 --> 00:07:28,480
Dalam kes ini, yang mengandungi lapan
nombor, kembali ke belakang untuk kembali.

162
00:07:28,480 --> 00:07:30,700
Dan mari kita kini memohon merge.

163
00:07:30,700 --> 00:07:33,300
Jadi saya mula-mula mahu untuk menyusun
separuh kiri senarai ini,

164
00:07:33,300 --> 00:07:37,370
dan mari kita, oleh itu,
memberi tumpuan kepada 4, 8, 6, dan 2.

165
00:07:37,370 --> 00:07:41,000
>> Sekarang bagaimana saya boleh pergi tentang
menyusun senarai saiz 4?

166
00:07:41,000 --> 00:07:45,990
Well, saya perlu kini menganggap
menyusun sebelah kiri separuh kiri.

167
00:07:45,990 --> 00:07:47,720
Sekali lagi, mari kita putar balik hanya untuk seketika.

168
00:07:47,720 --> 00:07:51,010
Jika kod pseudo adalah ini,
dan saya diberi lapan elemen,

169
00:07:51,010 --> 00:07:53,230
8 adalah jelas lebih besar
daripada atau sama dengan 2.

170
00:07:53,230 --> 00:07:54,980
Jadi dengan kes pertama tidak terpakai.

171
00:07:54,980 --> 00:07:58,120
Jadi untuk menyelesaikan lapan elemen, aku
menyusun separuh kiri unsur-unsur,

172
00:07:58,120 --> 00:08:01,930
maka saya menyusun separuh yang betul, maka saya bergabung
kedua-dua bahagian yang disusun, setiap saiz 4.

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

174
00:08:02,470 --> 00:08:07,480
>> Tetapi jika anda baru sahaja memberitahu saya, menyusun
separuh kiri, yang kini saiz 4,

175
00:08:07,480 --> 00:08:09,350
bagaimana saya menyusun separuh kiri?

176
00:08:09,350 --> 00:08:11,430
Baik jika saya mempunyai
input daripada empat unsur,

177
00:08:11,430 --> 00:08:14,590
Saya mula-mula menyusun kiri
dua, maka dua yang betul,

178
00:08:14,590 --> 00:08:16,210
dan kemudian saya menggabungkan mereka bersama-sama.

179
00:08:16,210 --> 00:08:18,700
Jadi sekali lagi, ia menjadi agak
fikiran yang lentur permainan di sini,

180
00:08:18,700 --> 00:08:21,450
kerana anda, jenis, perlu
ingat di mana anda berada di dalam cerita,

181
00:08:21,450 --> 00:08:23,620
tetapi pada akhir hari,
diberikan apa-apa bilangan elemen,

182
00:08:23,620 --> 00:08:25,620
anda mula-mula mahu menyusun
separuh kiri, kemudian separuh yang betul,

183
00:08:25,620 --> 00:08:26,661
kemudian menggabungkan mereka bersama-sama.

184
00:08:26,661 --> 00:08:28,630
Mari kita mulakan untuk melakukan perkara tersebut.

185
00:08:28,630 --> 00:08:30,170
Berikut adalah input daripada lapan elemen.

186
00:08:30,170 --> 00:08:31,910
Sekarang kita sedang melihat separuh kiri di sini.

187
00:08:31,910 --> 00:08:33,720
Bagaimana saya menyusun empat elemen?

188
00:08:33,720 --> 00:08:35,610
Well, saya pertama menyusun separuh kiri.

189
00:08:35,610 --> 00:08:37,720
Sekarang bagaimana saya menyusun separuh kiri?

190
00:08:37,720 --> 00:08:39,419
Well, saya telah diberi dua elemen.

191
00:08:39,419 --> 00:08:41,240
Jadi mari kita menyelesaikan kedua-dua elemen.

192
00:08:41,240 --> 00:08:44,540
2 adalah lebih besar atau
sama dengan 2, sudah tentu.

193
00:08:44,540 --> 00:08:46,170
Supaya kes pertama tidak terpakai.

194
00:08:46,170 --> 00:08:49,010
>> Oleh itu, saya kini mempunyai untuk menyelesaikan kiri
separuh daripada dua unsur.

195
00:08:49,010 --> 00:08:50,870
Separuh kiri, sudah tentu, adalah hanya 4.

196
00:08:50,870 --> 00:08:54,020
Jadi bagaimana saya menyusun senarai satu elemen?

197
00:08:54,020 --> 00:08:57,960
Sekarang, yang kes asas khas
sehingga atas, boleh dikatakan, terpakai.

198
00:08:57,960 --> 00:09:01,470
1 adalah kurang daripada 2, dan saya
senarai memang saiz 1.

199
00:09:01,470 --> 00:09:02,747
Jadi saya hanya kembali.

200
00:09:02,747 --> 00:09:03,580
Saya tidak melakukan apa-apa.

201
00:09:03,580 --> 00:09:06,770
Dan sesungguhnya, melihat apa yang saya telah
dilakukan, 4 sudah disusun.

202
00:09:06,770 --> 00:09:09,220
Seperti saya sudah
sebahagiannya berjaya di sini.

203
00:09:09,220 --> 00:09:11,750
>> Sekarang seolah-olah jenis bodoh
untuk menuntut, tetapi ia adalah benar.

204
00:09:11,750 --> 00:09:13,700
4 adalah senarai saiz 1.

205
00:09:13,700 --> 00:09:15,090
Ia sudah disusun.

206
00:09:15,090 --> 00:09:16,270
Itulah separuh kiri.

207
00:09:16,270 --> 00:09:18,010
Sekarang saya menyusun separuh betul.

208
00:09:18,010 --> 00:09:22,310
Input saya adalah salah satu elemen, 8
begitu juga, sudah disusun.

209
00:09:22,310 --> 00:09:25,170
Bodoh, juga, tetapi sekali lagi,
prinsip asas ini

210
00:09:25,170 --> 00:09:28,310
akan membolehkan kita kini membina
di atas ini dengan jayanya.

211
00:09:28,310 --> 00:09:32,260
4 disusun, 8 disusun, kini
apakah langkah terakhir?

212
00:09:32,260 --> 00:09:35,330
Jadi langkah ketiga dan terakhir, apa-apa
kali anda menyusun senarai, ingat,

213
00:09:35,330 --> 00:09:38,310
adalah untuk menggabungkan kedua-dua bahagian,
kiri dan kanan.

214
00:09:38,310 --> 00:09:39,900
Jadi mari kita melakukan perkara tersebut.

215
00:09:39,900 --> 00:09:41,940
Separuh kiri saya adalah, sudah tentu, 4.

216
00:09:41,940 --> 00:09:43,310
Separuh betul saya ialah 8.

217
00:09:43,310 --> 00:09:44,100
>> Jadi mari kita buat ini.

218
00:09:44,100 --> 00:09:46,410
Pertama saya akan memperuntukkan
beberapa memori tambahan,

219
00:09:46,410 --> 00:09:48,680
bahawa saya akan mewakili sini,
sebagai hanya pelbagai menengah,

220
00:09:48,680 --> 00:09:49,660
itu sudah cukup besar untuk memuatkan ini.

221
00:09:49,660 --> 00:09:52,243
Tetapi anda boleh bayangkan melanjutkan
yang segi empat panjang keseluruhan,

222
00:09:52,243 --> 00:09:53,290
jika memerlukan lebih banyak kemudian.

223
00:09:53,290 --> 00:09:58,440
Bagaimana saya mengambil 4 dan 8, dan bergabung
kedua-dua senarai saiz 1 bersama-sama?

224
00:09:58,440 --> 00:10:00,270
Di sini juga, agak mudah.

225
00:10:00,270 --> 00:10:03,300
4 diutamakan, kemudian datang 8.

226
00:10:03,300 --> 00:10:07,130
Kerana jika saya ingin menyusun
separuh kiri, kemudian separuh yang betul,

227
00:10:07,130 --> 00:10:09,900
dan kemudian menggabungkan kedua-dua bahagian
bersama-sama, untuk disusun,

228
00:10:09,900 --> 00:10:11,940
4 diutamakan, kemudian datang 8.

229
00:10:11,940 --> 00:10:15,810
>> Oleh itu, kita seolah-olah membuat kemajuan, walaupun
walaupun saya tidak melakukan apa-apa kerja yang sebenar.

230
00:10:15,810 --> 00:10:17,800
Tetapi ingat di mana kita berada dalam cerita.

231
00:10:17,800 --> 00:10:19,360
Kami asalnya mengambil lapan elemen.

232
00:10:19,360 --> 00:10:21,480
Kami disusun separuh kiri, yang 4.

233
00:10:21,480 --> 00:10:24,450
Kemudian kami disusun separuh kiri
separuh kiri, iaitu 2.

234
00:10:24,450 --> 00:10:25,270
Dan di sini kita pergi.

235
00:10:25,270 --> 00:10:26,920
Kita sudah selesai dengan langkah itu.

236
00:10:26,920 --> 00:10:29,930
>> Jadi, jika kita telah disusun yang
separuh daripada 2 kiri, sekarang kita

237
00:10:29,930 --> 00:10:32,130
perlu menyelesaikan separuh kanan 2.

238
00:10:32,130 --> 00:10:35,710
Jadi separuh kanan 2 adalah
kedua-dua nilai di sini, 6 dan 2.

239
00:10:35,710 --> 00:10:40,620
Jadi mari kita kini mengambil input saiz
2, dan menyusun separuh kiri, dan kemudian

240
00:10:40,620 --> 00:10:42,610
separuh yang betul, dan kemudian
menggabungkan mereka bersama-sama.

241
00:10:42,610 --> 00:10:45,722
Nah bagaimana saya menyusun senarai saiz
1, yang mengandungi hanya nombor 6?

242
00:10:45,722 --> 00:10:46,430
Saya sudah selesai.

243
00:10:46,430 --> 00:10:48,680
Itu senarai saiz 1 disusun.

244
00:10:48,680 --> 00:10:52,140
>> Bagaimana saya menyusun lain senarai
saiz 1, separuh kanan kononnya.

245
00:10:52,140 --> 00:10:54,690
Dan ia juga sudah disusun.

246
00:10:54,690 --> 00:10:56,190
Bilangan 2 adalah semata-mata.

247
00:10:56,190 --> 00:11:00,160
Jadi sekarang saya mempunyai dua bahagian, kiri dan
betul, saya perlu menggabungkan mereka bersama-sama.

248
00:11:00,160 --> 00:11:01,800
Izinkan saya memberikan diri saya sedikit ruang tambahan.

249
00:11:01,800 --> 00:11:05,580
Dan dimasukkan ke 2 di sana,
kemudian 6 di sana, dengan itu

250
00:11:05,580 --> 00:11:10,740
menyusun senarai itu, kiri dan kanan,
dan penggabungan bersama-sama, akhirnya.

251
00:11:10,740 --> 00:11:12,160
Oleh itu, saya dalam keadaan yang lebih baik sedikit.

252
00:11:12,160 --> 00:11:16,250
Saya tidak dilakukan, kerana jelas 4, 8, 2,
6 tidak pesanan terakhir yang saya mahu.

253
00:11:16,250 --> 00:11:20,640
Tetapi saya kini mempunyai dua senarai saiz 2, yang
telah kedua-duanya, masing-masing, telah disusun.

254
00:11:20,640 --> 00:11:24,580
Jadi sekarang jika anda putar balik dalam fikiran anda
mata, di mana yang yang meninggalkan kami?

255
00:11:24,580 --> 00:11:28,520
Saya bermula dengan lapan elemen, maka saya
dikecutkan ia ke separuh kiri 4,

256
00:11:28,520 --> 00:11:31,386
kemudian separuh kiri 2, dan
kemudian separuh kanan 2,

257
00:11:31,386 --> 00:11:34,510
Saya selesai, oleh itu, menyusun kiri
separuh daripada 2, dan separuh kanan 2,

258
00:11:34,510 --> 00:11:37,800
jadi apa langkah ketiga dan terakhir di sini?

259
00:11:37,800 --> 00:11:41,290
Saya mempunyai untuk bergabung bersama-sama
dua senarai saiz 2.

260
00:11:41,290 --> 00:11:42,040
Oleh itu, marilah kita pergi ke hadapan.

261
00:11:42,040 --> 00:11:43,940
Dan pada skrin di sini, memberi
saya beberapa memori tambahan,

262
00:11:43,940 --> 00:11:47,170
walaupun secara teknikal, notis bahawa saya telah
mendapat sejumlah besar ruang kosong sehingga bahagian

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

264
00:11:47,670 --> 00:11:50,044
Jika saya mahu menjadi sangat
ruang yang cekap bijak,

265
00:11:50,044 --> 00:11:52,960
Saya hanya boleh mula bergerak unsur-unsur
dan ke belakang, atas dan bawah.

266
00:11:52,960 --> 00:11:55,460
Tetapi hanya untuk kejelasan visual,
Saya akan meletakkan ia ke bawah di bawah,

267
00:11:55,460 --> 00:11:56,800
untuk menjaga perkara yang baik dan bersih.

268
00:11:56,800 --> 00:11:58,150
>> Jadi saya telah mendapat dua senarai saiz 2.

269
00:11:58,150 --> 00:11:59,770
Senarai pertama mempunyai 4 dan 8.

270
00:11:59,770 --> 00:12:01,500
Senarai kedua mempunyai 2 dan 6.

271
00:12:01,500 --> 00:12:03,950
Mari bergabung mereka
bersama-sama untuk disusun.

272
00:12:03,950 --> 00:12:09,910
2, sudah tentu, yang terdahulu,
kemudian 4, kemudian 6, maka 8.

273
00:12:09,910 --> 00:12:12,560
Dan sekarang kita seolah-olah mendapat
di suatu tempat yang menarik.

274
00:12:12,560 --> 00:12:15,720
Separuh Sekarang saya telah disusun daripada
senarai, dan secara kebetulan, ia adalah

275
00:12:15,720 --> 00:12:18,650
semua nombor genap, tetapi itu
adalah, sememangnya, hanya kebetulan.

276
00:12:18,650 --> 00:12:22,220
Dan saya kini telah disusun kiri
separuh, supaya ia 2, 4, 6, dan 8.

277
00:12:22,220 --> 00:12:23,430
Tiada apa-apa yang keluar perintah.

278
00:12:23,430 --> 00:12:24,620
Yang berasa seperti kemajuan.

279
00:12:24,620 --> 00:12:26,650
>> Kini ia berasa seperti saya telah
telah bercakap selama-lamanya kini,

280
00:12:26,650 --> 00:12:29,850
jadi apa yang masih belum dapat dilihat jika ini
algoritma adalah, sememangnya, lebih cekap.

281
00:12:29,850 --> 00:12:31,766
Tetapi kita akan melalui
ia sangat teratur.

282
00:12:31,766 --> 00:12:34,060
Komputer, sudah tentu,
akan melakukannya seperti itu.

283
00:12:34,060 --> 00:12:34,840
Jadi di mana kita?

284
00:12:34,840 --> 00:12:36,180
Kami bermula dengan lapan elemen.

285
00:12:36,180 --> 00:12:37,840
Saya disusun separuh kiri 4.

286
00:12:37,840 --> 00:12:39,290
Saya seolah-olah dilakukan dengan itu.

287
00:12:39,290 --> 00:12:42,535
Oleh sebab itu langkah seterusnya adalah untuk
menyusun separuh kanan 4.

288
00:12:42,535 --> 00:12:44,410
Dan bahagian ini kita boleh pergi
melalui lebih sedikit

289
00:12:44,410 --> 00:12:47,140
dengan cepat, walaupun anda
selamat datang ke putar balik atau berhenti seketika, hanya

290
00:12:47,140 --> 00:12:49,910
berfikir melaluinya di
kelajuan anda sendiri, tetapi apa yang

291
00:12:49,910 --> 00:12:53,290
kita ada sekarang adalah satu peluang untuk
melakukan algoritma yang tepat sama kepada empat

292
00:12:53,290 --> 00:12:54,380
nombor yang berlainan.

293
00:12:54,380 --> 00:12:57,740
>> Jadi mari kita pergi ke hadapan, dan menumpukan kepada
separuh yang betul, yang kita berada di sini.

294
00:12:57,740 --> 00:13:01,260
Separuh kiri yang
separuh betul, dan kini

295
00:13:01,260 --> 00:13:04,560
separuh kiri kiri
separuh daripada separuh hak itu,

296
00:13:04,560 --> 00:13:08,030
dan bagaimana saya menyusun senarai saiz
1 yang mengandungi hanya nombor 1?

297
00:13:08,030 --> 00:13:09,030
Ia sudah selesai.

298
00:13:09,030 --> 00:13:11,830
Bagaimana saya melakukan perkara yang sama untuk senarai
saiz 1 mengandungi hanya 7?

299
00:13:11,830 --> 00:13:12,840
Ia sudah selesai.

300
00:13:12,840 --> 00:13:16,790
Langkah tiga setengah ini maka
adalah untuk menggabungkan kedua-dua elemen

301
00:13:16,790 --> 00:13:20,889
ke dalam satu senarai baru saiz 2, 1 dan 7.

302
00:13:20,889 --> 00:13:23,180
Seolah-olah tidak melakukan semua
kerja yang menarik yang banyak.

303
00:13:23,180 --> 00:13:24,346
Mari kita lihat apa yang berlaku seterusnya.

304
00:13:24,346 --> 00:13:29,210
Saya hanya disusun separuh kiri
separuh betul input asal saya.

305
00:13:29,210 --> 00:13:32,360
Sekarang mari kita menyusun kanan
separuh, yang mengandungi 5 dan 3.

306
00:13:32,360 --> 00:13:35,740
Mari kita sekali lagi melihat kiri
separuh, disusun, separuh betul, disusun,

307
00:13:35,740 --> 00:13:39,120
dan bergabung kedua-dua bersama-sama,
ke dalam beberapa ruang tambahan,

308
00:13:39,120 --> 00:13:41,670
3 diutamakan, kemudian datang 5.

309
00:13:41,670 --> 00:13:46,190
Dan sehingga kini, kami telah disusun yang
separuh kiri separuh kanan

310
00:13:46,190 --> 00:13:49,420
masalah asal, dan
separuh kanan separuh kanan

311
00:13:49,420 --> 00:13:50,800
masalah asal.

312
00:13:50,800 --> 00:13:52,480
Apakah Langkah ketiga dan terakhir?

313
00:13:52,480 --> 00:13:54,854
Yang baik untuk menggabungkan kedua-dua bahagian sekali.

314
00:13:54,854 --> 00:13:57,020
Jadi biarlah saya mendapatkan diri beberapa
ruang tambahan, tetapi, sekali lagi, saya

315
00:13:57,020 --> 00:13:58,699
boleh menggunakan ruang sehingga lapang atas.

316
00:13:58,699 --> 00:14:00,490
Tetapi kita akan terus
ia mudah secara visual.

317
00:14:00,490 --> 00:14:07,070
Biar saya bergabung dalam sekarang 1, dan
kemudian 3, dan kemudian 5, dan kemudian 7.

318
00:14:07,070 --> 00:14:10,740
Dengan itu meninggalkan saya sekarang dengan
separuh kanan masalah asal

319
00:14:10,740 --> 00:14:12,840
yang yang sempurna disusun.

320
00:14:12,840 --> 00:14:13,662
>> Jadi apa yang tinggal?

321
00:14:13,662 --> 00:14:16,120
Saya rasa seperti saya terus mengatakan
perkara yang sama sekali lagi, dan sekali lagi,

322
00:14:16,120 --> 00:14:18,700
tetapi itu mencerminkan
Hakikat bahawa kita menggunakan rekursi.

323
00:14:18,700 --> 00:14:21,050
Proses menggunakan
algoritma lagi, dan sekali lagi,

324
00:14:21,050 --> 00:14:23,940
pada subset yang lebih kecil
masalah asal.

325
00:14:23,940 --> 00:14:27,580
Jadi saya kini telah kiri yang disusun
separuh daripada masalah asal.

326
00:14:27,580 --> 00:14:30,847
Saya mempunyai separuh disusun hak
masalah asal.

327
00:14:30,847 --> 00:14:32,180
Apakah langkah ketiga dan terakhir?

328
00:14:32,180 --> 00:14:33,590
Oh, ia bergabung.

329
00:14:33,590 --> 00:14:34,480
Jadi mari kita buat itu.

330
00:14:34,480 --> 00:14:36,420
Mari kita memperuntukkan beberapa tambahan
memori, tetapi tuhan saya, kami

331
00:14:36,420 --> 00:14:37,503
boleh meletakkan mana-mana sahaja sekarang.

332
00:14:37,503 --> 00:14:40,356
Kami mempunyai ruang yang begitu banyak boleh didapati
kepada kami, tetapi kami akan memastikan ia mudah.

333
00:14:40,356 --> 00:14:42,730
Daripada pergi ke belakang dan
sebagainya dengan memori asal kami,

334
00:14:42,730 --> 00:14:44,480
mari kita hanya melakukannya
visual turun di sini di bawah,

335
00:14:44,480 --> 00:14:47,240
selesaikan menggabungkan
separuh kiri dan separuh betul.

336
00:14:47,240 --> 00:14:49,279
>> Jadi dengan menggabungkan, apa yang perlu saya lakukan?

337
00:14:49,279 --> 00:14:50,820
Saya ingin mengambil unsur-unsur yang teratur.

338
00:14:50,820 --> 00:14:53,230
Jadi melihat separuh kiri,
Saya melihat nombor pertama adalah 2.

339
00:14:53,230 --> 00:14:55,230
Saya melihat separuh yang betul,
Saya melihat nombor pertama

340
00:14:55,230 --> 00:14:58,290
adalah 1, jadi jelas yang
nombor yang saya mahu untuk cabut,

341
00:14:58,290 --> 00:15:00,430
dan meletakkan pertama dalam senarai terakhir saya?

342
00:15:00,430 --> 00:15:01,449
Sudah tentu, 1.

343
00:15:01,449 --> 00:15:02,990
Sekarang saya ingin bertanya soalan yang sama.

344
00:15:02,990 --> 00:15:05,040
Pada separuh kiri, saya telah
masih mendapat nombor 2.

345
00:15:05,040 --> 00:15:07,490
Pada separuh yang betul,
Saya telah mendapat nombor 3.

346
00:15:07,490 --> 00:15:08,930
Yang mana satu yang saya mahu untuk memilih?

347
00:15:08,930 --> 00:15:11,760
Sudah tentu, nombor 2
kini melihat calon-calon

348
00:15:11,760 --> 00:15:13,620
4 di sebelah kiri, 3 di sebelah kanan.

349
00:15:13,620 --> 00:15:15,020
Mari kita, sudah tentu, pilih 3.

350
00:15:15,020 --> 00:15:18,020
Sekarang calon 4 pada
kiri, 5 di sebelah kanan.

351
00:15:18,020 --> 00:15:19,460
Kami, sudah tentu, memilih 4.

352
00:15:19,460 --> 00:15:21,240
6 di sebelah kiri, 5 di sebelah kanan.

353
00:15:21,240 --> 00:15:22,730
Kami, sudah tentu, memilih 5.

354
00:15:22,730 --> 00:15:25,020
6 di sebelah kiri, 7 di sebelah kanan.

355
00:15:25,020 --> 00:15:29,320
Kami memilih 6, dan kemudian kita
pilih 7, dan kemudian kita memilih 8.

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

357
00:15:30,100 --> 00:15:34,370
>> Jadi besar kata-kata kemudian, kami
telah disusun senarai ini lapan elemen

358
00:15:34,370 --> 00:15:38,450
ke dalam senarai satu melalui lapan,
yang yang semakin meningkat dengan setiap langkah,

359
00:15:38,450 --> 00:15:40,850
tetapi berapa banyak masa melakukan
ia membawa kita untuk berbuat demikian.

360
00:15:40,850 --> 00:15:43,190
Well, saya telah sengaja
perkara yang dibentangkan di bergambar

361
00:15:43,190 --> 00:15:46,330
di sini, supaya kita boleh jenis
melihat atau menghargai bahagian ini

362
00:15:46,330 --> 00:15:49,060
dalam penaklukan yang sudah berlaku.

363
00:15:49,060 --> 00:15:52,830
>> Malah jika anda melihat kembali bangun,
Saya telah meninggalkan semua ini garisan bertitik

364
00:15:52,830 --> 00:15:55,660
dalam pemegang tempat, anda boleh,
jenis, lihat, secara terbalik,

365
00:15:55,660 --> 00:15:58,800
jika anda jenis melihat kembali dalam
Sejarah kini, senarai asal saya

366
00:15:58,800 --> 00:16:00,250
adalah, sudah tentu, saiz 8.

367
00:16:00,250 --> 00:16:03,480
Dan kemudian sebelum ini, saya
berhadapan dengan dua senarai saiz 4,

368
00:16:03,480 --> 00:16:08,400
dan kemudian empat senarai saiz 2,
dan kemudian lapan senarai saiz 1.

369
00:16:08,400 --> 00:16:10,151
>> Jadi apakah ini,
jenis, mengingatkan anda?

370
00:16:10,151 --> 00:16:11,858
Well, memang, mana-mana
algoritma kami telah

371
00:16:11,858 --> 00:16:14,430
melihat setakat mana kita
jurang, dan bahagi, dan bahagi,

372
00:16:14,430 --> 00:16:19,500
menyimpan mempunyai perkara-perkara lagi, dan
sekali lagi, menyebabkan ini idea umum.

373
00:16:19,500 --> 00:16:23,100
Dan supaya ada sesuatu
logaritma berlaku di sini.

374
00:16:23,100 --> 00:16:26,790
Dan ia tidak cukup log n, tetapi
ada komponen logaritma

375
00:16:26,790 --> 00:16:28,280
dengan apa yang kita baru sahaja selesai.

376
00:16:28,280 --> 00:16:31,570
>> Sekarang mari kita memikirkan bagaimana yang sebenarnya.

377
00:16:31,570 --> 00:16:34,481
Jadi log n, lagi adalah
masa berjalan yang hebat,

378
00:16:34,481 --> 00:16:36,980
apabila kita melakukan sesuatu seperti
carian binari, seperti yang kita memanggilnya,

379
00:16:36,980 --> 00:16:40,090
membahagi dan menakluk strategi yang
melalui yang kami dapati Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Sekarang dari segi teknikal.

381
00:16:41,020 --> 00:16:43,640
Itulah log asas 2 n, walaupun
walaupun dalam kelas matematik yang paling,

382
00:16:43,640 --> 00:16:45,770
10 biasanya asas yang mengambil alih.

383
00:16:45,770 --> 00:16:48,940
Tetapi ahli-ahli sains komputer hampir selalu
berfikir dan bercakap dari segi asas 2,

384
00:16:48,940 --> 00:16:52,569
supaya kita biasanya hanya mengatakan log
n, bukannya log asas 2 n,

385
00:16:52,569 --> 00:16:55,110
tetapi ia sebenarnya satu dan
sama dalam dunia komputer

386
00:16:55,110 --> 00:16:57,234
sains, dan sebagai diketepikan,
ada faktor yang tetap

387
00:16:57,234 --> 00:17:01,070
Perbezaan antara kedua-dua, maka ia adalah
mengusulkan pula, lebih sebab-sebab rasmi.

388
00:17:01,070 --> 00:17:04,520
>> Tetapi buat masa ini, apa yang kita mengambil berat
tentang adalah contoh ini.

389
00:17:04,520 --> 00:17:08,520
Jadi mari kita tidak membuktikan melalui teladan, tetapi pada
kurangnya menggunakan satu contoh nombor

390
00:17:08,520 --> 00:17:10,730
di tangan sebagai cek kewarasan, jika anda akan.

391
00:17:10,730 --> 00:17:14,510
Jadi sebelum formula adalah asas log
2 n, tetapi apa yang n dalam kes ini.

392
00:17:14,510 --> 00:17:18,526
Saya mempunyai nombor n asal, atau 8
bilangan asal secara khusus.

393
00:17:18,526 --> 00:17:20,359
Kini ia telah sedikit
manakala, tetapi saya cukup

394
00:17:20,359 --> 00:17:25,300
memastikan bahawa log asas 2
daripada nilai 8 adalah 3,

395
00:17:25,300 --> 00:17:29,630
dan sesungguhnya, apa yang baik tentang yang
bahawa 3 adalah betul-betul beberapa kali

396
00:17:29,630 --> 00:17:33,320
bahawa anda boleh membahagikan senarai
panjang 8 lagi, dan sekali lagi,

397
00:17:33,320 --> 00:17:36,160
dan lagi, sehingga anda meninggalkan
dengan senarai hanya saiz 1.

398
00:17:36,160 --> 00:17:36,660
Betul?

399
00:17:36,660 --> 00:17:40,790
8 pergi ke 4, pergi ke 2,
pergi ke 1, dan itulah

400
00:17:40,790 --> 00:17:43,470
reflektif yang betul-betul
gambar kita baru sahaja sebentar tadi.

401
00:17:43,470 --> 00:17:47,160
Jadi kewarasan sedikit menyemak ke mana
logaritma sebenarnya terlibat.

402
00:17:47,160 --> 00:17:50,180
>> Oleh sebab itu, apa lagi yang terlibat di sini? n.

403
00:17:50,180 --> 00:17:53,440
Jadi notis bahawa setiap
kali saya berpecah senarai,

404
00:17:53,440 --> 00:17:58,260
walaupun secara terbalik dalam sejarah
di sini, saya masih melakukan n sesuatu.

405
00:17:58,260 --> 00:18:02,320
Langkah penggabungan mewajibkan
Saya menyentuh setiap satu daripada nombor,

406
00:18:02,320 --> 00:18:05,060
untuk masukkan ke dalam
lokasi yang sesuai.

407
00:18:05,060 --> 00:18:10,760
Jadi, walaupun ketinggian ini
rajah adalah saiz log n n atau 3,

408
00:18:10,760 --> 00:18:13,860
secara khusus, dengan kata lain,
Saya melakukan tiga bahagian di sini.

409
00:18:13,860 --> 00:18:18,800
Berapa banyak kerja yang saya buat secara mendatar
bersama-sama carta ini setiap masa?

410
00:18:18,800 --> 00:18:21,110
>> Well, saya lakukan n langkah-langkah
bekerja, kerana jika saya telah

411
00:18:21,110 --> 00:18:24,080
ada empat unsur-unsur dan empat elemen,
dan saya perlu menggabungkan mereka bersama-sama.

412
00:18:24,080 --> 00:18:26,040
Saya perlu melalui
empat dan empat,

413
00:18:26,040 --> 00:18:28,123
akhirnya untuk menggabungkan mereka
kembali ke dalam lapan elemen.

414
00:18:28,123 --> 00:18:32,182
Jika sebaliknya saya telah mendapat lapan jari
di sini, yang saya tidak lakukan, dan lapan

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Jika saya telah
mendapat empat jari di sini,

416
00:18:34,390 --> 00:18:37,380
yang saya lakukan, empat jari
di sini, yang saya lakukan,

417
00:18:37,380 --> 00:18:40,590
maka itulah yang sama
contohnya seperti sebelum ini, jika saya lakukan

418
00:18:40,590 --> 00:18:44,010
mempunyai lapan jari walaupun dalam
jumlah, yang saya boleh, jenis, lakukan.

419
00:18:44,010 --> 00:18:47,950
Saya betul-betul boleh lakukan di sini,
maka saya boleh pasti

420
00:18:47,950 --> 00:18:50,370
menggabungkan semua senarai ini
saiz 1 bersama-sama.

421
00:18:50,370 --> 00:18:54,050
Tetapi saya pasti perlu melihat
di setiap elemen hanya sekali.

422
00:18:54,050 --> 00:18:59,640
Jadi ketinggian proses ini adalah log n,
lebar proses ini, boleh dikatakan,

423
00:18:59,640 --> 00:19:02,490
adalah n, jadi apa yang kita seolah-olah
untuk mempunyai, akhirnya, adalah

424
00:19:02,490 --> 00:19:06,470
masa berjalan bersaiz n kali log n.

425
00:19:06,470 --> 00:19:08,977
>> Dalam erti kata lain, kami dibahagikan
senarai, log n kali,

426
00:19:08,977 --> 00:19:11,810
tetapi setiap kali kita lakukan itu, kita mempunyai
menyentuh setiap satu daripada unsur-unsur

427
00:19:11,810 --> 00:19:13,560
untuk menggabungkan mereka
semua bersama-sama, yang

428
00:19:13,560 --> 00:19:18,120
telah bila n langkah, jadi kita perlu n kali log n,
atau sebagai seorang saintis komputer akan berkata,

429
00:19:18,120 --> 00:19:20,380
asimptot, yang
adalah perkataan besar

430
00:19:20,380 --> 00:19:22,810
untuk menggambarkan atas
terikat pada masa yang berjalan,

431
00:19:22,810 --> 00:19:28,010
kita berjalan dalam o besar
log n masa, jadi untuk bercakap.

432
00:19:28,010 --> 00:19:31,510
>> Sekarang ini adalah penting, kerana
ingat apa yang masa berjalan adalah

433
00:19:31,510 --> 00:19:34,120
dengan seperti gelembung, dan pemilihan
jenis, dan sisipan jenis,

434
00:19:34,120 --> 00:19:38,200
dan juga beberapa orang lain yang wujud,
n kuasa adalah di mana kita berada di.

435
00:19:38,200 --> 00:19:39,990
Dan anda boleh, jenis, lihat ini di sini.

436
00:19:39,990 --> 00:19:45,720
Jika n kuasa jelas n kali
n, tetapi di sini kita mempunyai n kali log n,

437
00:19:45,720 --> 00:19:48,770
dan kita sudah tahu dari minggu
sifar, bahawa log n, logaritma,

438
00:19:48,770 --> 00:19:50,550
adalah lebih baik daripada sesuatu yang linear.

439
00:19:50,550 --> 00:19:52,930
Lagipun, masih ingat gambar
dengan merah dan kuning

440
00:19:52,930 --> 00:19:56,500
dan garis hijau yang kita menarik, yang
garis logaritma hijau adalah lebih rendah.

441
00:19:56,500 --> 00:20:00,920
Oleh itu, lebih baik dan lebih cepat
daripada garisan kuning dan merah,

442
00:20:00,920 --> 00:20:05,900
n kali log n iaitu, sesungguhnya lebih baik,
daripada n kali n, atau n kuasa dua.

443
00:20:05,900 --> 00:20:09,110
>> Oleh itu, kita seolah-olah mempunyai
mengenal pasti merge algoritma

444
00:20:09,110 --> 00:20:11,870
jenis yang berjalan di banyak
masa yang lebih pantas, dan sesungguhnya,

445
00:20:11,870 --> 00:20:16,560
itulah sebabnya, awal minggu ini, apabila
kita lihat pertandingan yang antara gelembung

446
00:20:16,560 --> 00:20:20,750
jenis, jenis pemilihan, dan menggabungkan
jenis, bergabung jenis benar-benar, benar-benar menang.

447
00:20:20,750 --> 00:20:23,660
Dan sesungguhnya kami tidak menunggu
untuk jenis gelembung dan jenis pemilihan

448
00:20:23,660 --> 00:20:24,790
untuk menamatkan.

449
00:20:24,790 --> 00:20:27,410
>> Sekarang mari kita satu laluan lain
pada ini, daripada yang lebih sedikit

450
00:20:27,410 --> 00:20:31,030
perspektif formal, hanya dalam
kes, ini bergema lebih baik

451
00:20:31,030 --> 00:20:33,380
daripada perbincangan peringkat yang lebih tinggi.

452
00:20:33,380 --> 00:20:34,880
Jadi di sini adalah algoritma lagi.

453
00:20:34,880 --> 00:20:36,770
Mari kita bertanya kepada diri sendiri,
apa masa yang berjalan

454
00:20:36,770 --> 00:20:39,287
adalah ini algoritma pelbagai langkah?

455
00:20:39,287 --> 00:20:41,620
Mari kita berkongsi pengalaman menjadi yang pertama
kes dan kes kedua.

456
00:20:41,620 --> 00:20:46,280
IF dan ELSE Dalam kes IF,
JIKA n adalah kurang daripada 2, hanya kembali.

457
00:20:46,280 --> 00:20:47,580
Terasa seperti masa yang berterusan.

458
00:20:47,580 --> 00:20:50,970
Ia, jenis, seperti dua langkah,
JIKA n adalah kurang daripada 2, akan terus pulang.

459
00:20:50,970 --> 00:20:54,580
Tetapi seperti yang kita katakan pada hari Isnin,
masa yang berterusan, atau besar o 1,

460
00:20:54,580 --> 00:20:57,130
boleh dua langkah, tiga
langkah-langkah, walaupun 1000 langkah.

461
00:20:57,130 --> 00:20:59,870
Apa yang penting ialah bahawa itu
angka tetap langkah.

462
00:20:59,870 --> 00:21:03,240
Jadi kuning yang diserlahkan pseudokod
di sini berharga, kami akan memanggilnya,

463
00:21:03,240 --> 00:21:04,490
masa yang berterusan.

464
00:21:04,490 --> 00:21:06,780
Jadi lebih secara rasmi, dan
kita akan supaya- ini

465
00:21:06,780 --> 00:21:09,910
akan sejauh mana kita
merasmikan hak ini sekarang-- T n,

466
00:21:09,910 --> 00:21:15,030
masa berjalan masalah
yang mengambil n somethings sebagai input,

467
00:21:15,030 --> 00:21:19,150
sama besar o satu,
JIKA n adalah kurang daripada 2.

468
00:21:19,150 --> 00:21:20,640
Jadi ia adalah bersyarat pada itu.

469
00:21:20,640 --> 00:21:24,150
Jadi untuk menjadi jelas, JIKA n adalah kurang daripada
2, kami mempunyai senarai yang sangat pendek, maka

470
00:21:24,150 --> 00:21:29,151
masa berjalan, T n, di mana n adalah
1 atau 0, dalam kes ini sangat khusus,

471
00:21:29,151 --> 00:21:30,650
ia hanya akan menjadi masa yang berterusan.

472
00:21:30,650 --> 00:21:32,691
Ia akan mengambil satu
melangkah, dua langkah, apa sahaja.

473
00:21:32,691 --> 00:21:33,950
Ia adalah nombor tetap langkah.

474
00:21:33,950 --> 00:21:38,840
>> Jadi bahagian berair pasti mesti dalam
kes yang lain dalam pseudokod.

475
00:21:38,840 --> 00:21:40,220
Kes ELSE.

476
00:21:40,220 --> 00:21:44,870
Susun separuh kiri elemen, jenis hak
separuh daripada unsur-unsur, bergabung bahagian disusun.

477
00:21:44,870 --> 00:21:46,800
Berapa lama setiap langkah-langkah diambil?

478
00:21:46,800 --> 00:21:49,780
Nah, jika berjalan
masa untuk menyelesaikan n unsur

479
00:21:49,780 --> 00:21:53,010
adalah, mari kita memanggilnya sangat
secara umum, T n,

480
00:21:53,010 --> 00:21:55,500
kemudian menyusun kiri
separuh daripada unsur-unsur

481
00:21:55,500 --> 00:21:59,720
adalah, jenis, seperti mengatakan,
T n dibahagikan dengan 2,

482
00:21:59,720 --> 00:22:03,000
dan begitu juga menyusun separuh kanan
unsur-unsur adalah, jenis, seperti mengatakan,

483
00:22:03,000 --> 00:22:06,974
T n dibahagikan 2, dan kemudian
menggabungkan bahagian disusun.

484
00:22:06,974 --> 00:22:08,890
Baik jika saya telah mendapat beberapa
beberapa elemen sini,

485
00:22:08,890 --> 00:22:11,230
seperti empat dan beberapa nombor
unsur-unsur di sini, seperti empat,

486
00:22:11,230 --> 00:22:14,650
dan saya perlu menggabungkan setiap satu daripada empat
dalam, dan masing-masing empat, satu

487
00:22:14,650 --> 00:22:17,160
selepas yang lain, supaya
akhirnya saya mempunyai lapan elemen.

488
00:22:17,160 --> 00:22:20,230
Rasanya seperti itulah besar o n langkah?

489
00:22:20,230 --> 00:22:23,500
Jika saya ada n jari dan setiap
mereka perlu digabungkan ke dalam tempat,

490
00:22:23,500 --> 00:22:25,270
itu seperti yang lain n langkah.

491
00:22:25,270 --> 00:22:27,360
>> Maka sesungguhnya formulaically,
kita boleh menyatakan ini,

492
00:22:27,360 --> 00:22:29,960
walaupun yang Scarily sedikit pada mulanya
pandang, tetapi ia adalah sesuatu yang

493
00:22:29,960 --> 00:22:31,600
yang menangkap tepat logik itu.

494
00:22:31,600 --> 00:22:35,710
Masa berjalan, T n, JIKA n
adalah lebih besar daripada atau sama dengan 2.

495
00:22:35,710 --> 00:22:42,500
Dalam kes ini, kes ELSE, adalah T n
dibahagikan dengan 2, ditambah T N dibahagikan dengan 2,

496
00:22:42,500 --> 00:22:45,320
tambah besar o n, beberapa
nombor linear langkah,

497
00:22:45,320 --> 00:22:51,630
mungkin betul-betul n, mungkin 2 kali
n, tetapi ia adalah secara kasar, tertib n.

498
00:22:51,630 --> 00:22:54,060
Supaya, juga, adalah bagaimana kita boleh
daftar ini formulaically.

499
00:22:54,060 --> 00:22:56,809
Sekarang anda tidak akan tahu ini melainkan
anda telah merakamkannya dalam fikiran anda,

500
00:22:56,809 --> 00:22:58,710
atau melihat ia dalam
belakang buku teks, yang

501
00:22:58,710 --> 00:23:00,501
mungkin mempunyai sedikit
menipu kunci pada akhirnya,

502
00:23:00,501 --> 00:23:03,940
tetapi ini, sesungguhnya, akan
memberikan kita besar o n log n,

503
00:23:03,940 --> 00:23:06,620
kerana berulang yang
anda lihat di sini pada skrin,

504
00:23:06,620 --> 00:23:09,550
jika anda benar-benar yang berlaku di luar, dengan
nombor terhingga contoh,

505
00:23:09,550 --> 00:23:13,000
atau kamu lakukan formulaically, anda akan
melihat bahawa ini, kerana formula ini

506
00:23:13,000 --> 00:23:17,100
sendiri adalah rekursi, dengan t
n atas sesuatu di sebelah kanan,

507
00:23:17,100 --> 00:23:21,680
dan t bila n lebih di sebelah kiri, ini boleh
sebenarnya dinyatakan, akhirnya,

508
00:23:21,680 --> 00:23:24,339
go sebesar n log n.

509
00:23:24,339 --> 00:23:26,130
Jika tidak yakin, itu
denda untuk sekarang, hanya

510
00:23:26,130 --> 00:23:28,960
mengambil iman, yang itu, sesungguhnya,
apa yang berulang yang membawa kepada,

511
00:23:28,960 --> 00:23:31,780
tetapi ini adalah hanya sedikit lebih daripada satu
pendekatan matematik untuk mencari

512
00:23:31,780 --> 00:23:36,520
pada masa yang berjalan merge
berdasarkan kod pseudo saja.

513
00:23:36,520 --> 00:23:39,030
>> Sekarang mari kita sedikit
seketika dari semua itu,

514
00:23:39,030 --> 00:23:41,710
dan mengambil lihat pada
bekas senator tertentu, yang

515
00:23:41,710 --> 00:23:44,260
mungkin kelihatan biasa sedikit,
yang duduk dengan Eric Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, sedikit masa lalu, untuk temuduga
di atas pentas, di hadapan sejumlah

517
00:23:48,410 --> 00:23:53,710
orang, bercakap tentang akhirnya
topik, yang cukup kini biasa.

518
00:23:53,710 --> 00:23:54,575
Mari kita lihat.

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

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Sekarang Senator,
anda di sini di Google,

521
00:24:03,890 --> 00:24:09,490
dan saya suka untuk berfikir
Presiden sebagai temu duga kerja.

522
00:24:09,490 --> 00:24:11,712
Sekarang ia sukar untuk mendapatkan pekerjaan sebagai presiden.

523
00:24:11,712 --> 00:24:12,670
PRESIDEN OBAMA: Betul.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Dan anda
akan melakukan [didengar] sekarang.

525
00:24:13,940 --> 00:24:15,523
Ia juga sukar untuk mendapatkan pekerjaan di Google.

526
00:24:15,523 --> 00:24:17,700
PRESIDEN OBAMA: Betul.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Kami mempunyai soalan,
dan kami meminta calon soalan kami,

528
00:24:21,330 --> 00:24:24,310
dan yang satu ini adalah dari Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PRESIDEN Belong: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Apa?

531
00:24:27,005 --> 00:24:28,130
Kalian fikir saya bergurau?

532
00:24:28,130 --> 00:24:30,590
Ia adalah di sini.

533
00:24:30,590 --> 00:24:33,490
Apakah cara yang paling berkesan untuk
menyusun satu juta 32 bit integer?

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

535
00:24:37,560 --> 00:24:38,979
>> PRESIDEN Belong: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Kadang-kadang,
mungkin saya minta maaf, maybe--

537
00:24:41,020 --> 00:24:42,750
PRESIDEN Belong: Tidak, tidak,
tidak, tidak, tidak, saya think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Itu bukan kitab itu

539
00:24:43,240 --> 00:24:45,430
PRESIDEN Belong: Saya
berfikir, saya rasa gelembung

540
00:24:45,430 --> 00:24:46,875
jenis yang akan menjadi cara yang salah untuk pergi.

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

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Ayuh.

543
00:24:50,535 --> 00:24:52,200
Siapakah yang telah memberitahukan kepadanya?

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

545
00:24:54,020 --> 00:24:55,590
Saya tidak sains komputer pada--

546
00:24:55,590 --> 00:24:58,986
>> PRESIDEN OBAMA: Kami telah
mendapat mata-mata kami di sana.

547
00:24:58,986 --> 00:24:59,860
PROFESOR: Baiklah.

548
00:24:59,860 --> 00:25:03,370
Marilah kita pergi di belakang kita sekarang
dunia teori algoritma

549
00:25:03,370 --> 00:25:06,520
dalam analisis asimptot
daripadanya, dan kembali kepada beberapa topik

550
00:25:06,520 --> 00:25:09,940
dari minggu sifar dan satu, dan permulaan
untuk menghapuskan beberapa roda latihan,

551
00:25:09,940 --> 00:25:10,450
jika anda akan.

552
00:25:10,450 --> 00:25:13,241
Supaya anda benar-benar memahami
akhirnya dari bawah ke atas, apa yang

553
00:25:13,241 --> 00:25:16,805
berlaku di bawah hood, apabila anda
menulis, menyusun, dan melaksanakan program.

554
00:25:16,805 --> 00:25:19,680
Ingat khususnya, bahawa ini adalah
program C yang pertama kita melihat,

555
00:25:19,680 --> 00:25:22,840
, program mudah berkanun
pelbagai, secara relatif,

556
00:25:22,840 --> 00:25:24,620
di mana, ia mencetak, Hello World.

557
00:25:24,620 --> 00:25:27,610
Dan ingat bahawa saya berkata, proses
kod sumber akan melalui

558
00:25:27,610 --> 00:25:28,430
betul-betul ini.

559
00:25:28,430 --> 00:25:31,180
Anda mengambil kod sumber anda, meluluskan
melalui pengkompil, seperti dilafaz,

560
00:25:31,180 --> 00:25:34,650
dan keluar datang kod objek, yang
mungkin kelihatan seperti ini, sifar dan satu

561
00:25:34,650 --> 00:25:37,880
bahawa CPU komputer, pusat
unit pemprosesan atau otak,

562
00:25:37,880 --> 00:25:39,760
akhirnya memahami.

563
00:25:39,760 --> 00:25:42,460
>> Ia ternyata bahawa itu adalah satu
sedikit melampaui batas,

564
00:25:42,460 --> 00:25:44,480
bahawa kami kini dalam
kedudukan untuk mengusik selain

565
00:25:44,480 --> 00:25:46,720
untuk memahami apa yang benar-benar telah
berlaku di bawah hud

566
00:25:46,720 --> 00:25:48,600
setiap kali anda menjalankan
Dilafaz, atau lebih umum,

567
00:25:48,600 --> 00:25:53,040
setiap kali anda membuat program,
menggunakan Membuat dan CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
Khususnya, barangan seperti
ini buat kali pertama,

569
00:25:56,760 --> 00:25:58,684
apabila anda mula-mula menyusun program anda.

570
00:25:58,684 --> 00:26:00,600
Dalam erti kata lain, apabila anda
mengambil kod sumber anda

571
00:26:00,600 --> 00:26:04,390
dan menyusun, apa yang pertama
sedang outputted oleh dilafaz

572
00:26:04,390 --> 00:26:06,370
adalah sesuatu yang dikenali sebagai kod pemasangan.

573
00:26:06,370 --> 00:26:08,990
Dan sebenarnya, ia kelihatan betul-betul seperti ini.

574
00:26:08,990 --> 00:26:11,170
>> Saya berlari arahan di
baris arahan sebelum ini.

575
00:26:11,170 --> 00:26:16,260
Hello.c dilafaz modal dash s,
dan ini menjadi satu fail

576
00:26:16,260 --> 00:26:19,490
bagi saya dipanggil hello.s,
di dalam yang betul-betul

577
00:26:19,490 --> 00:26:22,290
kandungan ini, dan lebih sedikit
di atas dan sedikit lagi di bawah,

578
00:26:22,290 --> 00:26:25,080
tetapi saya telah meletakkan juiciest
maklumat di sini pada skrin.

579
00:26:25,080 --> 00:26:29,190
Dan jika anda melihat dengan teliti, anda akan melihat
sekurang-kurangnya beberapa kata kunci biasa.

580
00:26:29,190 --> 00:26:31,330
Kami mempunyai utama di atas.

581
00:26:31,330 --> 00:26:35,140
Kami printf turun di tengah-tengah.

582
00:26:35,140 --> 00:26:38,670
Dan kami juga mempunyai hello dunia
garis miring balik n dalam petikan turun di bawah.

583
00:26:38,670 --> 00:26:42,450
>> Dan segala-galanya di sini
adalah arahan tahap yang sangat rendah

584
00:26:42,450 --> 00:26:45,500
bahawa CPU komputer memahami.

585
00:26:45,500 --> 00:26:50,090
Arahan CPU yang bergerak memori
sekitar, bahawa rentetan beban dari ingatan,

586
00:26:50,090 --> 00:26:52,750
dan akhirnya, cetak
perkara yang pada skrin.

587
00:26:52,750 --> 00:26:56,780
Sekarang apa yang berlaku walaupun selepas
kod perhimpunan ini dihasilkan?

588
00:26:56,780 --> 00:26:59,964
Akhirnya, anda lakukan, sesungguhnya,
masih menjana kod objek.

589
00:26:59,964 --> 00:27:02,630
Tetapi langkah-langkah yang telah benar-benar
telah berlaku di bawah hud

590
00:27:02,630 --> 00:27:04,180
melihat lebih kecil seperti ini.

591
00:27:04,180 --> 00:27:08,390
Kod sumber menjadi kod perhimpunan,
yang kemudiannya menjadi kod objek,

592
00:27:08,390 --> 00:27:11,930
dan perkataan pembedahan tersebut adalah,
apabila anda menyusun kod sumber anda,

593
00:27:11,930 --> 00:27:16,300
keluar datang kod pemasangan, dan kemudian
apabila anda memasang kod pemasangan anda,

594
00:27:16,300 --> 00:27:17,800
keluar datang kod objek.

595
00:27:17,800 --> 00:27:20,360
>> Sekarang dilafaz adalah super canggih,
seperti banyak penyusun,

596
00:27:20,360 --> 00:27:23,151
dan ia semua langkah-langkah
bersama-sama, dan ia tidak semestinya

597
00:27:23,151 --> 00:27:25,360
mengeluarkan apa-apa perantaraan
fail yang anda juga boleh melihat.

598
00:27:25,360 --> 00:27:28,400
Ia hanya menyusun perkara-perkara,
yang merupakan istilah umum yang

599
00:27:28,400 --> 00:27:30,000
menerangkan keseluruhan proses ini.

600
00:27:30,000 --> 00:27:32,000
Tetapi jika anda benar-benar mahu
menjadi tertentu, ada

601
00:27:32,000 --> 00:27:34,330
lebih banyak berlaku di sana juga.

602
00:27:34,330 --> 00:27:38,860
>> Tetapi mari kita juga mempertimbangkan sekarang bahawa walaupun
bahawa program super mudah, hello.c,

603
00:27:38,860 --> 00:27:40,540
dipanggil fungsi.

604
00:27:40,540 --> 00:27:41,870
Ia dipanggil printf.

605
00:27:41,870 --> 00:27:46,900
Tetapi saya tidak menulis printf, sesungguhnya,
yang datang dengan c, jadi untuk bercakap.

606
00:27:46,900 --> 00:27:51,139
Ia adalah satu panggilan semula fungsi itu
diisytiharkan dalam io.h standard, yang

607
00:27:51,139 --> 00:27:53,180
Fail header, yang
adalah topik yang kami akan benar-benar

608
00:27:53,180 --> 00:27:55,780
menyelam ke dalam lebih mendalam tidak lama lagi.

609
00:27:55,780 --> 00:27:58,000
Tetapi fail header adalah
biasanya disertai

610
00:27:58,000 --> 00:28:02,920
oleh fail kod, sumber fail kod, jadi
sama seperti wujud io.h. standard

611
00:28:02,920 --> 00:28:05,930
>> Satu ketika dulu, seseorang,
atau someones, juga menulis

612
00:28:05,930 --> 00:28:11,040
fail yang dipanggil io.c standard, dalam
mana definisi sebenar,

613
00:28:11,040 --> 00:28:15,220
atau perlaksanaan printf,
dan tandan fungsi lain,

614
00:28:15,220 --> 00:28:16,870
sebenarnya bertulis.

615
00:28:16,870 --> 00:28:22,140
Jadi memandangkan, jika kita mempertimbangkan mempunyai
di sini di sebelah kiri, hello.c, bahawa apabila

616
00:28:22,140 --> 00:28:26,250
disusun, memberikan kita hello.s, walaupun
Dilafaz tidak mengganggu penjimatan di tempat yang

617
00:28:26,250 --> 00:28:31,360
kita dapat melihat, dan bahawa kod pemasangan
mendapat dipasang ke hello.o, yang

618
00:28:31,360 --> 00:28:34,630
adalah, sememangnya, nama lalai
diberikan setiap kali anda menyusun sumber

619
00:28:34,630 --> 00:28:39,350
memberi kod kepada kod objek, tetapi tidak
cukup bersedia untuk melaksanakannya lagi,

620
00:28:39,350 --> 00:28:41,460
kerana langkah lain
telah berlaku, dan mempunyai

621
00:28:41,460 --> 00:28:44,440
telah berlaku sejak beberapa lalu
minggu, mungkin tanpa pengetahuan anda.

622
00:28:44,440 --> 00:28:47,290
>> Secara khusus di suatu tempat
dalam CS50 IDE, dan ini,

623
00:28:47,290 --> 00:28:49,870
juga akan menjadi sedikit yang
melampaui batas untuk seketika,

624
00:28:49,870 --> 00:28:54,670
terdapat, atau pernah suatu masa dahulu,
fail yang dipanggil io.c standard,

625
00:28:54,670 --> 00:28:58,440
bahawa seseorang yang dikumpulkan ke dalam
io.s standard atau yang setara dengannya,

626
00:28:58,440 --> 00:29:02,010
bahawa seseorang kemudian dipasang
ke dalam io.o standard,

627
00:29:02,010 --> 00:29:04,600
atau ia ternyata menjadi
file sedikit berbeza

628
00:29:04,600 --> 00:29:07,220
format yang boleh memberi yang berbeza
memfailkan lanjutan sama sekali,

629
00:29:07,220 --> 00:29:11,720
tetapi dalam teori dan konsep, betul-betul
langkah-langkah telah berlaku dalam bentuk tertentu.

630
00:29:11,720 --> 00:29:14,060
Yang mengatakan, yang kini
apabila saya menulis program,

631
00:29:14,060 --> 00:29:17,870
hello.c, yang hanya berkata, hello dunia,
dan saya menggunakan kod orang lain

632
00:29:17,870 --> 00:29:22,480
seperti printf, yang pada suatu
masa, dalam fail yang dipanggil io.c standard,

633
00:29:22,480 --> 00:29:26,390
kemudian entah bagaimana saya perlu mengambil saya
kod objek, sifar dan satu saya,

634
00:29:26,390 --> 00:29:29,260
dan objek orang itu
kod, atau sifar dan satu,

635
00:29:29,260 --> 00:29:34,970
dan entah bagaimana menghubungkan mereka bersama-sama ke
satu fail akhir, dipanggil hello, yang

636
00:29:34,970 --> 00:29:38,070
mempunyai semua sifar dan
orang-orang dari fungsi utama saya,

637
00:29:38,070 --> 00:29:40,830
dan semua sifar
dan orang-orang untuk printf.

638
00:29:40,830 --> 00:29:44,900
>> Dan sesungguhnya, bahawa proses terakhir ialah
dipanggil, menghubungkan kod objek anda.

639
00:29:44,900 --> 00:29:47,490
Yang mana outputnya
adalah fail boleh laku.

640
00:29:47,490 --> 00:29:49,780
Jadi dalam keadilan, di
akhir hari, tiada apa

641
00:29:49,780 --> 00:29:52,660
telah berubah sejak minggu satu, apabila kita
mula menyusun program.

642
00:29:52,660 --> 00:29:55,200
Sesungguhnya, semua ini telah
berlaku di bawah hood,

643
00:29:55,200 --> 00:29:57,241
tetapi sekarang kita berada dalam kedudukan yang
di mana kita boleh sebenarnya

644
00:29:57,241 --> 00:29:58,794
mengusik selain ini pelbagai langkah.

645
00:29:58,794 --> 00:30:00,710
Dan sesungguhnya, pada akhir
hari ini, kami masih

646
00:30:00,710 --> 00:30:04,480
ditinggalkan dengan sifar dan satu, yang
sebenarnya adalah Shalawat besar sekarang

647
00:30:04,480 --> 00:30:08,620
yang lain keupayaan C, yang
kami telah tidak mempunyai untuk memanfaatkan kemungkinan besar

648
00:30:08,620 --> 00:30:11,250
setakat ini, yang dikenali sebagai pengendali bitwise.

649
00:30:11,250 --> 00:30:15,220
Dengan kata lain, setakat ini, bila-bila masa yang kita ada
diuruskan data dalam C atau pembolehubah dalam C,

650
00:30:15,220 --> 00:30:17,660
kita mempunyai perkara-perkara seperti
aksara dan terapung dan ins

651
00:30:17,660 --> 00:30:21,990
dan Roh meronta-ronta dan beregu dan seperti itu, tetapi
semua mereka adalah sekurang-kurangnya lapan bit.

652
00:30:21,990 --> 00:30:25,550
Kami tidak pernah lagi dapat
memanipulasi bit individu,

653
00:30:25,550 --> 00:30:28,970
walaupun bit individu, kami
tahu, boleh mewakili 0 dan 1.

654
00:30:28,970 --> 00:30:32,640
Kini ia ternyata bahawa dalam C, anda
boleh mendapatkan akses kepada bit individu,

655
00:30:32,640 --> 00:30:35,530
jika anda tahu sintaks,
yang boleh digunakan untuk mendapatkan mereka.

656
00:30:35,530 --> 00:30:38,010
>> Jadi mari kita lihat
dan pengusaha-pengusaha bitwise.

657
00:30:38,010 --> 00:30:41,700
Jadi digambarkan di sini adalah beberapa simbol yang
kami telah, jenis, jenis, dilihat sebelum ini.

658
00:30:41,700 --> 00:30:45,580
Saya melihat Ampersand, satu menegak
bar, dan beberapa orang lain juga,

659
00:30:45,580 --> 00:30:49,430
dan ingat bahawa Ampersand Ampersand
adalah sesuatu yang kita lihat sebelum ini.

660
00:30:49,430 --> 00:30:54,060
Pengendali logik DAN, di mana anda perlu
kedua-dua mereka bersama-sama, atau logik ATAU

661
00:30:54,060 --> 00:30:56,300
operator, di mana anda
mempunyai dua bar menegak.

662
00:30:56,300 --> 00:31:00,550
Pengendali Bitwise, yang kita akan
melihat beroperasi pada bit secara berasingan,

663
00:31:00,550 --> 00:31:03,810
hanya menggunakan Ampersand tunggal,
bar menegak satu, simbol karet

664
00:31:03,810 --> 00:31:06,620
yang akan datang, kecil
tilde, dan kemudian meninggalkan

665
00:31:06,620 --> 00:31:08,990
kurung kiri kurungan, atau
tanda kurung kanan tanda kurung kanan.

666
00:31:08,990 --> 00:31:10,770
Masing-masing mempunyai makna yang berbeza.

667
00:31:10,770 --> 00:31:11,950
>> Malah, mari kita lihat.

668
00:31:11,950 --> 00:31:16,560
Mari kita pergi sekolah lama hari ini, dan penggunaan
skrin sentuh dari tadi,

669
00:31:16,560 --> 00:31:18,002
dikenali sebagai papan putih.

670
00:31:18,002 --> 00:31:19,710
Dan ini papan putih
akan membolehkan kita

671
00:31:19,710 --> 00:31:27,360
untuk menyatakan beberapa simbol-simbol yang agak mudah,
atau sebaliknya beberapa formula yang agak mudah,

672
00:31:27,360 --> 00:31:29,560
yang kita boleh kemudian akhirnya
leverage, untuk

673
00:31:29,560 --> 00:31:33,230
untuk mengakses individu
bit dalam program C.

674
00:31:33,230 --> 00:31:34,480
Dalam erti kata lain, mari kita buat ini.

675
00:31:34,480 --> 00:31:37,080
Mari kita bercakap pertama bagi
masa kira-kira Ampersand,

676
00:31:37,080 --> 00:31:39,560
yang bitwise DAN operator.

677
00:31:39,560 --> 00:31:42,130
Dalam erti kata lain, ini adalah
pengendali yang membolehkan

678
00:31:42,130 --> 00:31:45,930
saya mempunyai pembolehubah kiri tangan
biasanya, dan pembolehubah kanan,

679
00:31:45,930 --> 00:31:50,640
atau nilai individu, bahawa jika kita DAN
mereka bersama-sama, memberikan saya hasil akhir.

680
00:31:50,640 --> 00:31:51,560
Jadi, apa yang saya maksudkan?

681
00:31:51,560 --> 00:31:54,840
Jika dalam program, anda mempunyai pembolehubah
yang menyimpan salah satu daripada nilai-nilai ini,

682
00:31:54,840 --> 00:31:58,000
atau mari kita memastikan ia mudah, dan hanya
menulis sifar dan satu secara berasingan,

683
00:31:58,000 --> 00:32:00,940
di sini adalah cara pengendali Ampersand berfungsi.

684
00:32:00,940 --> 00:32:06,400
0 0 Ampersand akan menyamai 0.

685
00:32:06,400 --> 00:32:07,210
Sekarang mengapa?

686
00:32:07,210 --> 00:32:09,291
>> Ia hampir sama dengan
Ungkapan Boolean,

687
00:32:09,291 --> 00:32:10,540
yang kita telah dibincangkan setakat ini.

688
00:32:10,540 --> 00:32:15,800
Jika anda rasa selepas semua, 0 adalah
palsu, 0 adalah palsu, palsu dan palsu

689
00:32:15,800 --> 00:32:18,720
, seperti yang kita telah dibincangkan
secara logik, juga palsu.

690
00:32:18,720 --> 00:32:20,270
Oleh itu, kita mendapat 0 di sini juga.

691
00:32:20,270 --> 00:32:24,390
Jika anda mengambil 0 Ampersand
1, baik itu juga,

692
00:32:24,390 --> 00:32:29,890
akan menjadi 0, kerana bagi ini
ungkapan kiri adalah benar atau 1,

693
00:32:29,890 --> 00:32:32,360
ia perlu benar dan benar.

694
00:32:32,360 --> 00:32:36,320
Tetapi di sini kita mempunyai palsu
dan benar, atau 0 dan 1.

695
00:32:36,320 --> 00:32:42,000
Kini sekali lagi, jika kita mempunyai 1 Ampersand
0, yang juga akan menjadi 0,

696
00:32:42,000 --> 00:32:47,240
dan jika kita mempunyai 1 Ampersand 1,
akhirnya kita mempunyai sedikit 1.

697
00:32:47,240 --> 00:32:50,340
Jadi dalam erti kata lain, kita tidak melakukan
apa-apa yang menarik dengan pengendali ini

698
00:32:50,340 --> 00:32:51,850
sahaja lagi, pengendali Ampersand ini.

699
00:32:51,850 --> 00:32:53,780
Ia bitwise DAN operator.

700
00:32:53,780 --> 00:32:57,290
Tetapi ini adalah bahan-bahan
melalui yang boleh kita lakukan

701
00:32:57,290 --> 00:32:59,240
perkara yang menarik, kerana kita tidak lama lagi akan melihat.

702
00:32:59,240 --> 00:33:02,790
>> Sekarang mari kita lihat hanya tunggal
bar menegak di sini di sebelah kanan.

703
00:33:02,790 --> 00:33:06,710
Jika saya mempunyai bit 0 dan saya
ATAU dengan, bitwise

704
00:33:06,710 --> 00:33:11,030
ATAU operator, 0 bit lain,
yang akan memberi saya 0.

705
00:33:11,030 --> 00:33:17,540
Jika saya mengambil sedikit 0 dan OR dengan
sedikit 1, maka saya akan dapatkan 1.

706
00:33:17,540 --> 00:33:19,830
Dan sebenarnya, hanya untuk
kejelasan, biarlah saya kembali,

707
00:33:19,830 --> 00:33:23,380
supaya bar menegak saya
tidak disalah anggap sebagai 1.

708
00:33:23,380 --> 00:33:26,560
Biar saya menulis semula semua
saya 1 lebih sedikit

709
00:33:26,560 --> 00:33:32,700
jelas, supaya kita berikut lihat, jika saya
telah 1 ATAU 0, yang akan menjadi 1,

710
00:33:32,700 --> 00:33:39,060
dan jika saya mempunyai 1 ATAU 1 itu,
juga, akan menjadi 1.

711
00:33:39,060 --> 00:33:42,900
Jadi, anda boleh melihat secara logik bahawa ATAU
pengendali berkelakuan sangat berbeza.

712
00:33:42,900 --> 00:33:48,070
Ini memberikan saya 0 0 ATAU memberikan saya 0, tetapi
setiap gabungan lain memberikan saya 1.

713
00:33:48,070 --> 00:33:52,480
Selagi saya mempunyai satu 1 dalam
formula, hasilnya akan menjadi 1.

714
00:33:52,480 --> 00:33:55,580
>> Sebaliknya dengan AND
operator, Ampersand,

715
00:33:55,580 --> 00:34:00,940
hanya jika saya mempunyai dua 1. dalam
persamaan, adakah saya benar-benar mendapatkan 1 keluar.

716
00:34:00,940 --> 00:34:02,850
Sekarang ada yang lain beberapa
Pengendali juga.

717
00:34:02,850 --> 00:34:04,810
Salah seorang daripada mereka adalah sedikit lebih terlibat.

718
00:34:04,810 --> 00:34:07,980
Jadi biarlah saya pergi ke hadapan dan memadamkan
ini untuk membebaskan sedikit ruang.

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

720
00:34:13,020 --> 00:34:16,460
Dan mari kita lihat pada
simbol karet, hanya untuk seketika.

721
00:34:16,460 --> 00:34:18,210
Ini biasanya yang
watak anda boleh menaip

722
00:34:18,210 --> 00:34:21,420
pada papan kekunci Shift pegangan anda dan
kemudian salah satu nombor di atas AS anda

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

724
00:34:22,250 --> 00:34:26,190
>> Jadi ini adalah eksklusif
ATAU operator, eksklusif OR.

725
00:34:26,190 --> 00:34:27,790
Oleh itu, kita hanya melihat operator OR itu.

726
00:34:27,790 --> 00:34:29,348
Ini adalah eksklusif ATAU operator.

727
00:34:29,348 --> 00:34:30,639
Apa sebenarnya perbezaan?

728
00:34:30,639 --> 00:34:34,570
Nah mari kita hanya melihat formula,
dan menggunakan ini sebagai bahan akhirnya.

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

730
00:34:37,690 --> 00:34:39,650
Saya akan katakan adalah sentiasa 0.

731
00:34:39,650 --> 00:34:41,400
Itulah definisi XOR.

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

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 akan menjadi 1,
dan 1 XOR 1 akan menjadi?

734
00:34:58,810 --> 00:34:59,890
Salah?

735
00:34:59,890 --> 00:35:00,520
Atau bukan?

736
00:35:00,520 --> 00:35:01,860
Saya tidak tahu.

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

738
00:35:02,810 --> 00:35:04,700
Sekarang apa yang sedang berlaku di sini?

739
00:35:04,700 --> 00:35:06,630
Juga berfikir tentang
menamakan pengendali ini.

740
00:35:06,630 --> 00:35:09,980
ATAU eksklusif, jadi sebagai
nama, jenis, mencadangkan,

741
00:35:09,980 --> 00:35:13,940
jawapannya hanya akan menjadi
1 jika input adalah eksklusif,

742
00:35:13,940 --> 00:35:15,560
semata-mata yang berbeza.

743
00:35:15,560 --> 00:35:18,170
Jadi di sini input adalah
sama, maka keluaran adalah 0.

744
00:35:18,170 --> 00:35:20,700
Di sini input adalah
sama, maka keluaran adalah 0.

745
00:35:20,700 --> 00:35:25,640
Berikut adalah output yang berbeza, mereka
adalah eksklusif, dan keluaran adalah 1.

746
00:35:25,640 --> 00:35:28,190
Jadi ia adalah hampir sama dengan
DAN, ia adalah hampir sama,

747
00:35:28,190 --> 00:35:32,760
atau sebaliknya ia hampir sama dengan
ATAU, tetapi hanya dengan cara yang eksklusif.

748
00:35:32,760 --> 00:35:36,210
Yang ini tidak lagi menjadi 1,
kerana kita mempunyai dua 1-kanak,

749
00:35:36,210 --> 00:35:38,621
dan tidak semata-mata, hanya satu daripada mereka.

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

751
00:35:39,120 --> 00:35:40,080
Bagaimana pula dengan yang lain?

752
00:35:40,080 --> 00:35:44,220
Well tilde, sementara itu, adalah
sebenarnya yang bagus dan mudah, bersyukur.

753
00:35:44,220 --> 00:35:46,410
Dan ini adalah satu unari
pengendali, yang bermaksud

754
00:35:46,410 --> 00:35:50,400
ia digunakan untuk hanya satu input,
satu operan, jadi untuk bercakap.

755
00:35:50,400 --> 00:35:51,800
Belum kiri dan kanan.

756
00:35:51,800 --> 00:35:56,050
Dalam erti kata lain, jika anda mengambil tilde daripada
0, jawapannya akan menjadi sebaliknya.

757
00:35:56,050 --> 00:35:59,710
Dan jika anda mengambil tilde daripada 1,
jawapan akan ada sebaliknya.

758
00:35:59,710 --> 00:36:02,570
Jadi pengendali tilde adalah
satu cara untuk menidakkan sedikit,

759
00:36:02,570 --> 00:36:06,000
atau Melibas sedikit dari
0-1, atau 1-0.

760
00:36:06,000 --> 00:36:09,820
>> Dan yang meninggalkan kita akhirnya
dengan hanya dua pengendali akhir,

761
00:36:09,820 --> 00:36:13,840
apa yang dikenali sebagai anjakan kiri, dan
apa yang dikenali sebagai pengendali peralihan betul.

762
00:36:13,840 --> 00:36:16,620
Mari kita lihat bagaimana mereka bekerja.

763
00:36:16,620 --> 00:36:20,780
Pengendali shift kiri, bertulis
dengan dua tanda kurung sudut seperti itu,

764
00:36:20,780 --> 00:36:22,110
beroperasi seperti berikut.

765
00:36:22,110 --> 00:36:27,390
Jika input saya, atau operan saya, ke kiri
pengendali peralihan cukup sekadar 1.

766
00:36:27,390 --> 00:36:33,750
Dan saya kemudian memberitahu komputer untuk
anjakan lagi yang 1, berkata tujuh tempat,

767
00:36:33,750 --> 00:36:37,150
hasilnya adalah seolah-olah saya
mengambil bahawa 1, dan bergerak

768
00:36:37,150 --> 00:36:40,160
tujuh tempat pula ke dalam
kiri, dan secara lalai,

769
00:36:40,160 --> 00:36:42,270
kita akan menganggap bahawa
ruang ke kanan

770
00:36:42,270 --> 00:36:44,080
akan dapat empuk dengan sifar.

771
00:36:44,080 --> 00:36:50,316
Dengan kata lain, 1 meninggalkan anjakan 7 akan
untuk memberi saya bahawa 1, diikuti dengan 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 sifar.

773
00:36:54,060 --> 00:36:57,380
Jadi dalam erti kata lain, ia membolehkan anda untuk
mengambil sebilangan kecil seperti 1,

774
00:36:57,380 --> 00:37:00,740
dan jelas membuat ia lebih
banyak, lebih besar dengan cara ini,

775
00:37:00,740 --> 00:37:06,460
tetapi kita sebenarnya akan melihat
pendekatan yang lebih bijak untuk itu

776
00:37:06,460 --> 00:37:08,080
sebaliknya, dan juga,

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

778
00:37:08,720 --> 00:37:10,060
Itu sahaja untuk minggu tiga.

779
00:37:10,060 --> 00:37:11,400
Kita akan lihat masa depan.

780
00:37:11,400 --> 00:37:12,770
Ini adalah CS50.

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

782
00:37:17,270 --> 00:37:22,243
>> [Bermain muzik]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: Beliau adalah di snek
melarang makan fudge sundae panas.

784
00:37:25,766 --> 00:37:28,090
Beliau mempunyai seluruh muka beliau.

785
00:37:28,090 --> 00:37:30,506
Dia memakai coklat yang seperti janggut

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Apa yang anda buat?

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

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

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Adakah anda hanya berenang dua kali?

790
00:37:36,800 --> 00:37:38,585
Anda dua kali turun cip.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: Maafkan saya.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Anda dicelup cip, anda
mengambil santapan anda, dan anda menurun lagi.

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

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Jadi itu seperti meletakkan
betul mulut semua hak dalam sos.

795
00:37:48,440 --> 00:37:52,400
Lain kali anda mengambil cip,
hanya mencelupkannya sekali, dan mengakhirinya.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: Anda tahu apa, Dan?

797
00:37:53,890 --> 00:37:58,006
Anda mencelupkan cara yang anda mahu jatuh.

798
00:37:58,006 --> 00:38:01,900
Saya akan mencelupkan cara yang saya mahu jatuh.

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