1
00:00:00,000 --> 00:00:04,419
>> [Bermain muzik]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, jadi merge yang
jenis lagi algoritma lain

4
00:00:08,460 --> 00:00:11,200
yang boleh kita gunakan untuk menyelesaikan
elemen array.

5
00:00:11,200 --> 00:00:14,480
Tetapi seperti yang kita akan lihat, ia mendapat
perbezaan yang sangat asas

6
00:00:14,480 --> 00:00:17,850
dari jenis pemilihan, gelembung
jenis, dan sisipan jenis

7
00:00:17,850 --> 00:00:20,280
yang membuat ia benar-benar cantik pandai.

8
00:00:20,280 --> 00:00:24,290
>> Idea asas di sebalik merge
jenis adalah untuk menyusun tatasusunan yang lebih kecil

9
00:00:24,290 --> 00:00:27,430
dan kemudian menggabungkan mereka tatasusunan
bersama-sama, atau bergabung mereka, kelak

10
00:00:27,430 --> 00:00:31,440
oleh itu name-- dalam usaha disusun.

11
00:00:31,440 --> 00:00:34,230
Cara yang bergabung apapun tidak
ini adalah dengan menggunakan alat yang

12
00:00:34,230 --> 00:00:37,290
dipanggil rekursi, iaitu apa yang
kita akan bercakap tentang tidak lama lagi,

13
00:00:37,290 --> 00:00:39,720
tetapi kita tidak benar-benar bercakap tentang lagi.

14
00:00:39,720 --> 00:00:43,010
>> Berikut adalah idea asas di sebalik jenis merge.

15
00:00:43,010 --> 00:00:46,320
Susun separuh kiri array,
dengan andaian n lebih besar daripada 1.

16
00:00:46,320 --> 00:00:49,980
Dan apa yang saya maksudkan apabila saya mengatakan
dengan andaian n lebih besar daripada 1 adalah,

17
00:00:49,980 --> 00:00:53,970
Saya rasa kita boleh bersetuju bahawa jika array
hanya terdiri daripada satu unsur,

18
00:00:53,970 --> 00:00:54,680
ia disusun.

19
00:00:54,680 --> 00:00:56,560
Kita sebenarnya tidak perlu
berbuat apa-apa kepadanya.

20
00:00:56,560 --> 00:00:58,059
Kami hanya dapat memberi diselesaikan.

21
00:00:58,059 --> 00:01:00,110
Ia hanya satu unsur.

22
00:01:00,110 --> 00:01:03,610
>> Jadi pseudokod, sekali lagi,
menyusun separuh meninggalkan array,

23
00:01:03,610 --> 00:01:08,590
kemudian menyusun separuh kanan array,
kemudian menggabungkan kedua-dua bahagian bersama-sama.

24
00:01:08,590 --> 00:01:11,040
Sekarang, sudah anda mungkin
berfikir, ia jenis hanya

25
00:01:11,040 --> 00:01:14,080
bunyi seperti anda meletakkan off the--
anda sebenarnya tidak melakukan apa-apa.

26
00:01:14,080 --> 00:01:16,330
Anda katakan menyusun kiri
separuh, menyusun separuh yang betul,

27
00:01:16,330 --> 00:01:19,335
tetapi anda tidak memberitahu
saya bagaimana anda melakukannya.

28
00:01:19,335 --> 00:01:22,220
>> Tetapi ingat bahawa selagi
array adalah elemen tunggal,

29
00:01:22,220 --> 00:01:23,705
kita boleh mengisytiharkan ia disusun.

30
00:01:23,705 --> 00:01:25,330
Maka kita hanya boleh menggabungkan mereka bersama-sama.

31
00:01:25,330 --> 00:01:27,788
Dan itulah sebenarnya
idea asas di sebalik jenis merge,

32
00:01:27,788 --> 00:01:31,150
adalah untuk memecahkan ia ke bawah supaya
tatasusunan anda mempunyai saiz satu.

33
00:01:31,150 --> 00:01:33,430
Dan kemudian anda membina semula dari sana.

34
00:01:33,430 --> 00:01:35,910
>> Bergabung apapun pasti
algoritma rumit.

35
00:01:35,910 --> 00:01:38,210
Dan ia juga sedikit
rumit untuk menggambarkan.

36
00:01:38,210 --> 00:01:41,870
Jadi diharapkan, visualisasi yang saya
ada di sini akan membantu anda mengikuti bersama-sama.

37
00:01:41,870 --> 00:01:45,640
Dan saya akan cuba yang terbaik untuk menceritakan perkara
dan meneruskan melalui ini lebih sedikit

38
00:01:45,640 --> 00:01:49,180
perlahan-lahan daripada yang lain
hanya untuk mudah-mudahan mendapatkan kepala anda

39
00:01:49,180 --> 00:01:51,800
sekitar idea di sebalik jenis merge.

40
00:01:51,800 --> 00:01:54,680
>> Jadi kita mempunyai pelbagai yang sama dengan
lain menyusun video algoritma

41
00:01:54,680 --> 00:01:57,120
jika anda telah melihat mereka, kelak
pelbagai enam unsur.

42
00:01:57,120 --> 00:02:02,110
Dan kod pseudo kami di sini adalah jenis
separuh kiri, menyusun separuh yang betul,

43
00:02:02,110 --> 00:02:03,890
menggabungkan kedua-dua bahagian bersama-sama.

44
00:02:03,890 --> 00:02:09,770
Jadi mari kita ini bata merah sangat gelap
lokasi dan menyusun separuh meninggalkan daripadanya.

45
00:02:09,770 --> 00:02:13,380
>> Jadi buat masa ini, kita akan
untuk mengabaikan hal-hal yang di sebelah kanan.

46
00:02:13,380 --> 00:02:15,740
Ia berada di sana, tetapi kami
tidak pada langkah lagi.

47
00:02:15,740 --> 00:02:18,220
Kami tidak sama jenis yang
separuh betul array.

48
00:02:18,220 --> 00:02:21,037
Kami pada jenis kiri
separuh daripada array.

49
00:02:21,037 --> 00:02:22,870
Dan hanya demi
menjadi lebih sedikit

50
00:02:22,870 --> 00:02:26,480
jelas, maka saya boleh merujuk
apa langkah kita berada di,

51
00:02:26,480 --> 00:02:29,800
Saya akan menukar
warna set ini kepada oren.

52
00:02:29,800 --> 00:02:33,190
Sekarang, kami masih bercakap tentang
separuh kiri yang sama array asal.

53
00:02:33,190 --> 00:02:38,520
Tetapi saya berharap bahawa dengan mampu
merujuk kepada warna-warna pelbagai barangan,

54
00:02:38,520 --> 00:02:40,900
ia akan membuat ia lebih sedikit
jelas apa yang berlaku di sini.

55
00:02:40,900 --> 00:02:43,270
>> OK, jadi sekarang kita mempunyai
tiga elemen tatasusunan.

56
00:02:43,270 --> 00:02:46,420
Bagaimana kita menyusun separuh kiri ini
pelbagai, yang masih langkah ini?

57
00:02:46,420 --> 00:02:49,400
Kami cuba untuk menyusun kiri
separuh daripada bata array-- merah

58
00:02:49,400 --> 00:02:52,410
separuh kiri yang
Saya kini telah berwarna oren.

59
00:02:52,410 --> 00:02:54,840
>> Nah, kita boleh cuba dan
mengulangi proses ini lagi.

60
00:02:54,840 --> 00:02:56,756
Oleh itu, kita masih dalam
tengah cuba untuk menyelesaikan

61
00:02:56,756 --> 00:02:58,700
separuh kiri array penuh.

62
00:02:58,700 --> 00:03:00,450
Separuh kiri
pelbagai, saya hanya akan

63
00:03:00,450 --> 00:03:03,910
sewenang-wenangnya membuat keputusan bahawa separuh kiri
akan menjadi lebih kecil daripada separuh yang betul,

64
00:03:03,910 --> 00:03:06,550
kerana ini berlaku kepada
terdiri daripada tiga elemen.

65
00:03:06,550 --> 00:03:11,260
>> Dan jadi saya akan mengatakan bahawa
separuh kiri separuh kiri array

66
00:03:11,260 --> 00:03:14,050
hanya elemen lima.

67
00:03:14,050 --> 00:03:18,360
Lima, yang merupakan suatu elemen tunggal
pelbagai, kita tahu bagaimana untuk menyelesaikannya.

68
00:03:18,360 --> 00:03:21,615
Dan sebagainya lima disusun.

69
00:03:21,615 --> 00:03:22,990
Kami hanya akan mengisytiharkan itu.

70
00:03:22,990 --> 00:03:24,890
Ia adalah pelbagai elemen.

71
00:03:24,890 --> 00:03:29,015
>> Jadi, sekarang kita telah disusun yang
separuh kiri half-- sebelah kiri

72
00:03:29,015 --> 00:03:33,190
atau sebaliknya, kami telah disusun yang
separuh kiri oren.

73
00:03:33,190 --> 00:03:37,970
Oleh sebab itu, untuk masih lengkap
separuh kiri pelbagai keseluruhan ini,

74
00:03:37,970 --> 00:03:43,481
kita perlu menyusun separuh kanan
oren, atau barangan ini.

75
00:03:43,481 --> 00:03:44,230
Bagaimana kita berbuat demikian?

76
00:03:44,230 --> 00:03:45,930
Nah, kita mempunyai pelbagai dua unsur.

77
00:03:45,930 --> 00:03:50,470
Oleh itu, kita boleh menyusun separuh sebelah kiri
array, yang dua.

78
00:03:50,470 --> 00:03:52,090
Dua adalah elemen tunggal.

79
00:03:52,090 --> 00:03:55,890
Jadi ia disusun secara lalai.
Kemudian kita boleh menyusun separuh kanan

80
00:03:55,890 --> 00:03:58,530
dengan bahagian array, satu.

81
00:03:58,530 --> 00:04:00,210
Itulah jenis secara lalai.

82
00:04:00,210 --> 00:04:03,610
>> Ketika ini merupakan kali pertama
kita telah mencapai satu langkah merge.

83
00:04:03,610 --> 00:04:06,135
Kami telah menyiapkan, walaupun
kami kini jenis bersarang down--

84
00:04:06,135 --> 00:04:08,420
dan itulah jenis yang agak rumit
perkara dengan rekursi adalah,

85
00:04:08,420 --> 00:04:10,930
anda perlu menyimpan anda
mengetuai kira-kira di mana kita berada.

86
00:04:10,930 --> 00:04:15,560
Jadi kita ada semacam kiri
separuh daripada bahagian oren.

87
00:04:15,560 --> 00:04:21,280
>> Dan sekarang, kita berada di tengah-tengah sorting
separuh kanan bahagian oren.

88
00:04:21,280 --> 00:04:25,320
Dan dalam proses itu, kami
kini kira-kira untuk berada di langkah,

89
00:04:25,320 --> 00:04:27,850
menggabungkan kedua-dua bahagian bersama-sama.

90
00:04:27,850 --> 00:04:31,700
Apabila kita melihat kedua-dua bahagian
array, kita melihat dua dan satu.

91
00:04:31,700 --> 00:04:33,880
Unsur yang lebih kecil?

92
00:04:33,880 --> 00:04:35,160
One.

93
00:04:35,160 --> 00:04:36,760
>> Maka yang mana unsur yang lebih kecil?

94
00:04:36,760 --> 00:04:38,300
Nah, ia adalah dua atau apa-apa.

95
00:04:38,300 --> 00:04:39,910
Jadi ia adalah dua.

96
00:04:39,910 --> 00:04:43,690
Oleh sebab itu, hanya untuk sekali lagi bingkai
di mana kita berada dalam konteks,

97
00:04:43,690 --> 00:04:48,230
kami telah disusun yang
separuh kiri oren

98
00:04:48,230 --> 00:04:49,886
dan separuh kanan asalan.

99
00:04:49,886 --> 00:04:52,510
Saya tahu saya telah berubah warna
sekali lagi, tetapi itulah di mana kita berada.

100
00:04:52,510 --> 00:04:54,676
Dan sebab itu saya melakukan ini
adalah kerana proses ini adalah

101
00:04:54,676 --> 00:04:57,870
akan terus pergi, iterating ke bawah.

102
00:04:57,870 --> 00:05:00,500
Kami telah disusun kiri
separuh daripada bekas oren

103
00:05:00,500 --> 00:05:02,590
dan separuh kanan bekas oren.

104
00:05:02,590 --> 00:05:05,620
>> Sekarang, kita perlu untuk menggabungkan mereka
dua bahagian bersama-sama juga.

105
00:05:05,620 --> 00:05:07,730
Itulah langkah yang kita berada di.

106
00:05:07,730 --> 00:05:11,440
Oleh itu, kita mempertimbangkan semua
unsur-unsur yang kini hijau,

107
00:05:11,440 --> 00:05:12,972
separuh kiri lokasi asal.

108
00:05:12,972 --> 00:05:14,680
Dan kita bergabung mereka
menggunakan proses yang sama

109
00:05:14,680 --> 00:05:18,660
kita lakukan untuk menggabungkan dua
dan satu hanya sebentar tadi.

110
00:05:18,660 --> 00:05:23,080
>> Separuh kiri, yang paling kecil
elemen pada separuh kiri ialah lima.

111
00:05:23,080 --> 00:05:25,620
Elemen paling kecil pada
separuh yang betul adalah satu.

112
00:05:25,620 --> 00:05:27,370
Yang mana satu adalah lebih kecil?

113
00:05:27,370 --> 00:05:29,260
One.

114
00:05:29,260 --> 00:05:32,250
>> Elemen paling kecil pada
separuh kiri ialah lima.

115
00:05:32,250 --> 00:05:35,540
Elemen paling kecil pada
separuh yang betul adalah dua.

116
00:05:35,540 --> 00:05:36,970
Apa yang paling kecil?

117
00:05:36,970 --> 00:05:38,160
Dua.

118
00:05:38,160 --> 00:05:41,540
Dan kemudian akhir sekali lima dan
apa-apa, kita boleh mengatakan lima.

119
00:05:41,540 --> 00:05:43,935
>> OK, gambar begitu besar, mari kita
berehat sebentar

120
00:05:43,935 --> 00:05:46,080
dan memikirkan di mana kita berada.

121
00:05:46,080 --> 00:05:48,580
Jika kita bermula dari
awal-awal lagi, kita

122
00:05:48,580 --> 00:05:51,640
kini telah siap untuk
array keseluruhan hanya

123
00:05:51,640 --> 00:05:53,810
satu langkah kod pseudo di sini.

124
00:05:53,810 --> 00:05:56,645
Kami yang disusun
separuh kiri array.

125
00:05:56,645 --> 00:05:59,490
>> Ingat bahawa asal
perintah berusia lima tahun, dua, satu.

126
00:05:59,490 --> 00:06:02,570
Dengan pergi melalui proses ini
dan bersarang ke bawah dan mengulangi,

127
00:06:02,570 --> 00:06:05,990
berterusan untuk memecahkan masalah
turun ke dalam bahagian yang lebih kecil dan lebih kecil,

128
00:06:05,990 --> 00:06:09,670
kita kini telah siap
melangkah salah satu pseudokod

129
00:06:09,670 --> 00:06:13,940
kerana susunan permulaan keseluruhan.

130
00:06:13,940 --> 00:06:16,670
Kami disusun separuh kirinya.

131
00:06:16,670 --> 00:06:18,670
>> Jadi sekarang mari kita membekukan sana.

132
00:06:18,670 --> 00:06:23,087
Dan sekarang mari kita menyusun kanan
separuh daripada lokasi asal.

133
00:06:23,087 --> 00:06:25,670
Dan kita akan berbuat demikian dengan
melalui lelaran sama

134
00:06:25,670 --> 00:06:30,630
proses memecahkan perkara turun
dan kemudian menggabungkan mereka bersama-sama.

135
00:06:30,630 --> 00:06:34,290
>> Jadi separuh kiri
merah, atau separuh kiri

136
00:06:34,290 --> 00:06:38,830
daripada separuh kanan asal
pelbagai, saya akan katakan adalah tiga.

137
00:06:38,830 --> 00:06:40,312
Sekali lagi, saya yang konsisten di sini.

138
00:06:40,312 --> 00:06:42,020
Jika anda mempunyai ganjil
beberapa elemen, ia

139
00:06:42,020 --> 00:06:44,478
tidak benar-benar kira sama ada
anda membuat satu kiri lebih kecil

140
00:06:44,478 --> 00:06:45,620
atau yang betul yang lebih kecil.

141
00:06:45,620 --> 00:06:49,230
>> Apa yang penting ialah bahawa setiap kali anda
menghadapi masalah ini dalam menjalankan

142
00:06:49,230 --> 00:06:51,422
merge, anda perlu konsisten.

143
00:06:51,422 --> 00:06:53,505
Samada anda sentiasa perlu
membuat pasukan yang ditinggalkan lebih kecil

144
00:06:53,505 --> 00:06:55,421
atau sentiasa perlu membuat
sebelah kanan lebih kecil.

145
00:06:55,421 --> 00:06:57,720
Di sini, saya telah memilih untuk sentiasa
membuat bahagian kiri lebih kecil

146
00:06:57,720 --> 00:07:04,380
apabila pelbagai saya, atau saya
sub-pelbagai, adalah saiz ganjil.

147
00:07:04,380 --> 00:07:07,420
>> Tiga adalah elemen tunggal,
dan oleh itu adalah disusun.

148
00:07:07,420 --> 00:07:10,860
Kami telah dimanfaatkan andaian bahawa
sepanjang proses keseluruhan kami setakat ini.

149
00:07:10,860 --> 00:07:15,020
Jadi sekarang mari kita menyusun kanan
separuh daripada separuh yang betul,

150
00:07:15,020 --> 00:07:18,210
atau separuh kanan merah.

151
00:07:18,210 --> 00:07:20,390
>> Sekali lagi, kita perlu berpecah ini ke bawah.

152
00:07:20,390 --> 00:07:21,910
Ini bukan satu pelbagai elemen.

153
00:07:21,910 --> 00:07:23,970
Kami tidak dapat memberi disusun.

154
00:07:23,970 --> 00:07:27,060
Dan jadi pertama, kita akan
untuk menyusun separuh kiri.

155
00:07:27,060 --> 00:07:31,620
>> Separuh kiri adalah elemen tunggal,
supaya ia semacam secara lalai.

156
00:07:31,620 --> 00:07:34,840
Kemudian kita akan menyusun kanan
separuh, yang merupakan elemen tunggal.

157
00:07:34,840 --> 00:07:41,250
Ia disusun secara lalai. Dan sekarang,
kita boleh menggabungkan kedua-dua bersama-sama.

158
00:07:41,250 --> 00:07:45,820
Empat adalah lebih kecil, dan
maka enam adalah lebih kecil.

159
00:07:45,820 --> 00:07:48,870
>> Sekali lagi, apa yang telah kita lakukan pada ketika ini?

160
00:07:48,870 --> 00:07:52,512
Kami telah disusun kiri
separuh daripada separuh betul.

161
00:07:52,512 --> 00:07:54,720
Atau akan kembali kepada asal
warna yang berada di sana,

162
00:07:54,720 --> 00:07:57,875
kami telah disusun kiri
separuh daripada merah lembut.

163
00:07:57,875 --> 00:08:00,416
Ia pada asalnya bata yang gelap
merah dan kini ia merah yang lebih lembut,

164
00:08:00,416 --> 00:08:02,350
atau ia adalah merah yang lebih lembut.

165
00:08:02,350 --> 00:08:05,145
>> Dan kemudian kami telah disusun yang
separuh kanan merah lembut.

166
00:08:05,145 --> 00:08:08,270
Sekarang, dengan baik, mereka hijau lagi, hanya
kerana kita akan melalui satu proses.

167
00:08:08,270 --> 00:08:10,720
Dan kita perlu mengulangi
lebih ini dan ke atas.

168
00:08:10,720 --> 00:08:14,695
>> Jadi sekarang kita boleh menggabungkan mereka
dua bahagian bersama-sama.

169
00:08:14,695 --> 00:08:15,820
Dan itulah apa yang kita lakukan di sini.

170
00:08:15,820 --> 00:08:17,653
Jadi garis hitam hanya
dibahagikan separuh kiri

171
00:08:17,653 --> 00:08:19,690
dan separuh kanan bahagian seperti ini.

172
00:08:19,690 --> 00:08:24,310
>> Kami membandingkan nilai terkecil
di sebelah kiri array-- yang

173
00:08:24,310 --> 00:08:26,710
atau maafkan saya, yang paling kecil
nilai separuh kiri

174
00:08:26,710 --> 00:08:30,790
kepada nilai yang paling kecil dari kanan
separuh dan mendapati bahawa tiga adalah lebih kecil.

175
00:08:30,790 --> 00:08:32,530
Dan kini sedikit pengoptimuman, bukan?

176
00:08:32,530 --> 00:08:35,175
Ada sebenarnya apa-apa
ditinggalkan di sebelah kiri.

177
00:08:35,175 --> 00:08:37,440
>> Tiada apa-apa baki
di sebelah kiri,

178
00:08:37,440 --> 00:08:40,877
supaya kita boleh cekap
hanya move-- kita boleh mengisytiharkan

179
00:08:40,877 --> 00:08:42,960
sepanjang ia sebenarnya
disusun dan hanya jelujur ia

180
00:08:42,960 --> 00:08:45,126
pada, kerana tiada apa-apa
lain untuk membandingkan terhadap.

181
00:08:45,126 --> 00:08:49,140
Dan kita tahu bahawa sebelah kanan
sebelah kanan disusun.

182
00:08:49,140 --> 00:08:52,770
>> OK, jadi sekarang mari kita membekukan lagi dan
memikirkan di mana kita berada dalam cerita.

183
00:08:52,770 --> 00:08:56,120
Dalam array secara keseluruhan,
apa yang telah dicapai?

184
00:08:56,120 --> 00:08:58,790
Kami benar-benar telah mencapai
kini beberapa langkah satu dan langkah dua.

185
00:08:58,790 --> 00:09:03,300
Kami disusun separuh kiri, dan
kita disusun separuh betul.

186
00:09:03,300 --> 00:09:08,210
>> Oleh sebab itu, apa yang tinggal untuk kita
untuk menggabungkan kedua-dua bahagian sekali.

187
00:09:08,210 --> 00:09:11,670
Oleh itu, kita bandingkan paling bernilai
unsur setiap babak array

188
00:09:11,670 --> 00:09:13,510
seterusnya dan teruskan.

189
00:09:13,510 --> 00:09:16,535
Satu adalah kurang daripada tiga, jadi satu pergi.

190
00:09:16,535 --> 00:09:19,770
>> Dua adalah kurang daripada tiga, jadi dua pergi.

191
00:09:19,770 --> 00:09:22,740
Tiga adalah kurang daripada 5, jadi tiga pergi.

192
00:09:22,740 --> 00:09:25,820
Empat adalah kurang daripada 5, jadi empat pergi.

193
00:09:25,820 --> 00:09:30,210
Kemudian lima adalah kurang daripada enam,
dan enam sahaja yang masih kekal.

194
00:09:30,210 --> 00:09:31,820
>> Sekarang, saya tahu, itu adalah banyak langkah-langkah.

195
00:09:31,820 --> 00:09:33,636
Dan kita telah meninggalkan banyak
memori di belakangnya kami.

196
00:09:33,636 --> 00:09:35,260
Dan itulah apa yang mereka dataran kelabu.

197
00:09:35,260 --> 00:09:40,540
Dan ia mungkin merasa seperti itu mengambil
banyak lebih lama daripada jenis kemasukan, gelembung

198
00:09:40,540 --> 00:09:42,660
jenis, atau jenis pemilihan.

199
00:09:42,660 --> 00:09:45,330
>> Tetapi sebenarnya, kerana
banyak proses ini

200
00:09:45,330 --> 00:09:48,260
yang berlaku di time-- yang sama
yang adalah sesuatu yang kita akan, sekali lagi,

201
00:09:48,260 --> 00:09:51,100
bercakap tentang apabila kita bercakap mengenai
rekursi di masa depan yang video--

202
00:09:51,100 --> 00:09:53,799
algoritma ini sebenarnya
jelas asasnya

203
00:09:53,799 --> 00:09:55,590
yang berbeza daripada apa-apa
kita lihat sebelum

204
00:09:55,590 --> 00:09:58,820
tetapi juga ketara
lebih cekap.

205
00:09:58,820 --> 00:09:59,532
>> Kenapa begitu?

206
00:09:59,532 --> 00:10:01,240
Nah, dalam yang paling teruk
senario kes, kami mempunyai

207
00:10:01,240 --> 00:10:04,830
untuk berpecah n unsur sehingga
dan kemudian bergabung semula mereka.

208
00:10:04,830 --> 00:10:06,680
Tetapi apabila kita bergabung semula
mereka, apa yang kita lakukan

209
00:10:06,680 --> 00:10:11,110
pada dasarnya dua kali ganda
Saiz tatasusunan yang lebih kecil.

210
00:10:11,110 --> 00:10:14,260
Kami mempunyai sekumpulan satu elemen
tatasusunan yang kita berkesan

211
00:10:14,260 --> 00:10:16,290
bergabung ke dalam dua tatasusunan unsur.

212
00:10:16,290 --> 00:10:18,590
Dan kemudian kita mengambil orang-orang
dua tatasusunan elemen

213
00:10:18,590 --> 00:10:21,890
dan menggabungkan mereka bersama-sama ke
empat tatasusunan elemen, dan sebagainya,

214
00:10:21,890 --> 00:10:26,130
dan sebagainya, dan sebagainya, sehingga kita
mempunyai pelbagai n elemen tunggal.

215
00:10:26,130 --> 00:10:29,910
>> Tetapi berapa ramai doublings
masa yang diambil untuk sampai ke n?

216
00:10:29,910 --> 00:10:31,460
Fikirkan kembali kepada contoh buku telefon.

217
00:10:31,460 --> 00:10:34,490
Berapa kali kita perlu air mata
buku telefon pada separuh, berapa banyak lagi

218
00:10:34,490 --> 00:10:38,370
kali kita perlu air mata buku telefon
pada separuh, jika saiz buku telefon

219
00:10:38,370 --> 00:10:39,680
dua kali ganda?

220
00:10:39,680 --> 00:10:41,960
Terdapat hanya satu, bukan?

221
00:10:41,960 --> 00:10:45,360
>> Jadi ada beberapa jenis
unsur logaritma di sini.

222
00:10:45,360 --> 00:10:48,590
Tetapi kita juga masih perlu sekurang-kurangnya
melihat semua n unsur-unsur.

223
00:10:48,590 --> 00:10:53,860
Jadi, dalam kes yang teruk,
bergabung apapun berjalan dalam n log n.

224
00:10:53,860 --> 00:10:56,160
Kita perlu melihat
semua n elemen,

225
00:10:56,160 --> 00:11:02,915
dan kita perlu menggabungkan mereka
bersama-sama dalam log n set langkah-langkah.

226
00:11:02,915 --> 00:11:05,290
Dalam kes senario yang terbaik,
array sempurna disusun.

227
00:11:05,290 --> 00:11:06,300
Itu yang besar.

228
00:11:06,300 --> 00:11:09,980
Tetapi berdasarkan algoritma yang kita ada di sini,
kita masih perlu berpecah dan bergabung semula.

229
00:11:09,980 --> 00:11:13,290
Walaupun dalam kes ini,
recombining adalah jenis tidak berkesan.

230
00:11:13,290 --> 00:11:14,720
Ia tidak diperlukan.

231
00:11:14,720 --> 00:11:17,580
Tetapi kita masih melalui
keseluruhan proses juga.

232
00:11:17,580 --> 00:11:21,290
>> Jadi dalam kes ini,
dan dalam kes paling teruk,

233
00:11:21,290 --> 00:11:24,970
algoritma ini berjalan dalam n log n masa.

234
00:11:24,970 --> 00:11:29,130
Bergabung apapun pasti agak lebih sukar
daripada yang lain algoritma isihan utama

235
00:11:29,130 --> 00:11:33,470
kita telah bercakap tentang CS50 tetapi
ketara lebih kuat.

236
00:11:33,470 --> 00:11:35,400
>> Dan jadi jika anda pernah mendapati
kesempatan untuk memerlukannya

237
00:11:35,400 --> 00:11:38,480
atau menggunakannya untuk menyusun
set data yang besar, mendapat

238
00:11:38,480 --> 00:11:41,940
kepala anda sekitar idea rekursi
akan menjadi benar-benar kuat.

239
00:11:41,940 --> 00:11:45,270
Dan ia akan membuat anda
program benar-benar jauh lebih efisien

240
00:11:45,270 --> 00:11:48,700
menggunakan bergabung apapun berbanding yang lain.

241
00:11:48,700 --> 00:11:49,640
Saya Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Ini adalah CS50.

243
00:11:51,970 --> 00:11:53,826