1
00:00:00,000 --> 00:00:04,419
>> [MUSIC PLAYING]

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

3
00:00:05,401 --> 00:00:08,460
>> Doug LLOYD: OK, jadi penggabungan
semacam belum algoritma lain

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

5
00:00:11,200 --> 00:00:14,480
Tapi seperti yang kita akan lihat, itu punya
perbedaan yang sangat mendasar

6
00:00:14,480 --> 00:00:17,850
dari pemilihan semacam, bubble
macam, dan insertion sort

7
00:00:17,850 --> 00:00:20,280
yang membuatnya benar-benar cukup pintar.

8
00:00:20,280 --> 00:00:24,290
>> Ide dasar di balik merge
semacam ini untuk mengurutkan array yang lebih kecil

9
00:00:24,290 --> 00:00:27,430
dan kemudian menggabungkan mereka array
bersama-sama, atau menggabungkan them--

10
00:00:27,430 --> 00:00:31,440
maka name-- untuk disortir.

11
00:00:31,440 --> 00:00:34,230
Cara menggabungkan semacam tidak
ini adalah dengan memanfaatkan alat

12
00:00:34,230 --> 00:00:37,290
disebut rekursi, yang adalah apa yang
kita akan berbicara tentang segera,

13
00:00:37,290 --> 00:00:39,720
tapi kita belum benar-benar berbicara tentang belum.

14
00:00:39,720 --> 00:00:43,010
>> Berikut ide dasar di balik merge sort.

15
00:00:43,010 --> 00:00:46,320
Urutkan kiri setengah dari array,
asumsi n lebih besar dari 1.

16
00:00:46,320 --> 00:00:49,980
Dan apa yang saya maksud ketika saya mengatakan
asumsi n lebih besar dari 1 adalah,

17
00:00:49,980 --> 00:00:53,970
Saya pikir kita bisa setuju bahwa jika sebuah array
hanya terdiri dari satu elemen,

18
00:00:53,970 --> 00:00:54,680
itu diurutkan.

19
00:00:54,680 --> 00:00:56,560
Kami tidak benar-benar perlu
melakukan apapun untuk itu.

20
00:00:56,560 --> 00:00:58,059
Kami hanya dapat mendeklarasikan akan diurutkan.

21
00:00:58,059 --> 00:01:00,110
Ini hanya satu elemen.

22
00:01:00,110 --> 00:01:03,610
>> Jadi pseudocode, sekali lagi, adalah
mengurutkan setengah kiri dari array,

23
00:01:03,610 --> 00:01:08,590
kemudian mengurutkan bagian kanan array,
kemudian menggabungkan dua bagian bersama-sama.

24
00:01:08,590 --> 00:01:11,040
Sekarang, Anda mungkin sudah
berpikir, itu jenis hanya

25
00:01:11,040 --> 00:01:14,080
Kedengarannya seperti Anda menunda the--
Anda tidak benar-benar melakukan apa-apa.

26
00:01:14,080 --> 00:01:16,330
Anda mengatakan menyortir kiri
setengah, mengurutkan bagian kanan,

27
00:01:16,330 --> 00:01:19,335
tapi kau tidak mengatakan
saya bagaimana Anda melakukannya.

28
00:01:19,335 --> 00:01:22,220
>> Tapi ingat bahwa selama
array adalah elemen tunggal,

29
00:01:22,220 --> 00:01:23,705
kita dapat mendeklarasikan diurutkan.

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

31
00:01:25,330 --> 00:01:27,788
Dan itulah sebenarnya
Ide dasar di balik semacam penggabungan,

32
00:01:27,788 --> 00:01:31,150
adalah untuk memecahnya sehingga
array Anda adalah ukuran satu.

33
00:01:31,150 --> 00:01:33,430
Dan kemudian Anda kembali dari sana.

34
00:01:33,430 --> 00:01:35,910
>> Menggabungkan semacam pasti
algoritma yang rumit.

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

36
00:01:38,210 --> 00:01:41,870
Jadi mudah-mudahan, visualisasi yang saya
miliki di sini akan membantu Anda mengikuti bersama.

37
00:01:41,870 --> 00:01:45,640
Dan aku akan mencoba yang terbaik untuk menceritakan hal-hal
dan melanjutkan melalui ini lebih sedikit

38
00:01:45,640 --> 00:01:49,180
lambat dari yang lain
hanya untuk mudah-mudahan mendapatkan kepala Anda

39
00:01:49,180 --> 00:01:51,800
sekitar ide dibalik merge sort.

40
00:01:51,800 --> 00:01:54,680
>> Jadi kita memiliki array sama dengan
video algoritma sorting lainnya

41
00:01:54,680 --> 00:01:57,120
jika Anda pernah melihat them--
array enam elemen.

42
00:01:57,120 --> 00:02:02,110
Dan kode pseudo kami di sini adalah semacam
kiri setengah, mengurutkan bagian kanan,

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

44
00:02:03,890 --> 00:02:09,770
Jadi mari kita bata merah ini sangat gelap
array dan mengurutkan setengah kiri itu.

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

46
00:02:13,380 --> 00:02:15,740
Itu ada, tapi kami
tidak pada langkah belum.

47
00:02:15,740 --> 00:02:18,220
Kami tidak di semacam itu
kanan setengah dari array.

48
00:02:18,220 --> 00:02:21,037
Kami berada di semacam kiri
setengah dari array.

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

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

51
00:02:26,480 --> 00:02:29,800
Aku akan mengganti
warna set ini untuk oranye.

52
00:02:29,800 --> 00:02:33,190
Sekarang, kita masih berbicara tentang
kiri setengah sama array asli.

53
00:02:33,190 --> 00:02:38,520
Tapi aku berharap bahwa dengan mampu
mengacu pada warna dari berbagai item,

54
00:02:38,520 --> 00:02:40,900
itu akan membuatnya sedikit lebih
jelas apa yang terjadi di sini.

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

56
00:02:43,270 --> 00:02:46,420
Bagaimana kita mengurutkan setengah kiri ini
array, yang masih langkah ini?

57
00:02:46,420 --> 00:02:49,400
Kami mencoba untuk memilah kiri
setengah dari bata merah array--

58
00:02:49,400 --> 00:02:52,410
kiri setengah dari yang
Saya sekarang sudah berwarna oranye.

59
00:02:52,410 --> 00:02:54,840
>> Nah, kita bisa mencoba dan
ulangi proses ini lagi.

60
00:02:54,840 --> 00:02:56,756
Jadi kita masih di
tengah berusaha untuk menyortir

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

62
00:02:58,700 --> 00:03:00,450
Kiri setengah dari
array, aku hanya akan

63
00:03:00,450 --> 00:03:03,910
untuk sewenang-wenang memutuskan bahwa setengah kiri
akan lebih kecil dari bagian kanan,

64
00:03:03,910 --> 00:03:06,550
karena hal ini terjadi pada
terdiri dari tiga elemen.

65
00:03:06,550 --> 00:03:11,260
>> Dan jadi saya akan mengatakan bahwa
kiri setengah dari kiri setengah array

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

67
00:03:14,050 --> 00:03:18,360
Lima, menjadi satu elemen
array, kita tahu bagaimana mengatasinya.

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

69
00:03:21,615 --> 00:03:22,990
Kami hanya akan menyatakan bahwa.

70
00:03:22,990 --> 00:03:24,890
Ini array elemen tunggal.

71
00:03:24,890 --> 00:03:29,015
>> Jadi sekarang kami telah diurutkan
kiri setengah dari half-- kiri

72
00:03:29,015 --> 00:03:33,190
atau lebih tepatnya, kami telah diurutkan
kiri setengah dari jeruk.

73
00:03:33,190 --> 00:03:37,970
Jadi sekarang, untuk masih lengkap
kiri setengah array keseluruhan itu,

74
00:03:37,970 --> 00:03:43,481
kita perlu memilah bagian kanan
dari jeruk, atau hal-hal ini.

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

76
00:03:44,230 --> 00:03:45,930
Nah, kita memiliki array dua elemen.

77
00:03:45,930 --> 00:03:50,470
Jadi kita dapat menyusun setengah kiri
dari array, yang merupakan dua.

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

79
00:03:52,090 --> 00:03:55,890
Jadi itu diurutkan secara default.
Kemudian kita bisa memilah bagian kanan

80
00:03:55,890 --> 00:03:58,530
yang bagian dari array, satu.

81
00:03:58,530 --> 00:04:00,210
Itu semacam secara default.

82
00:04:00,210 --> 00:04:03,610
>> Ini adalah pertama kalinya sekarang
kami telah mencapai langkah penggabungan.

83
00:04:03,610 --> 00:04:06,135
Kami telah selesai, meskipun
kita sekarang jenis bersarang down--

84
00:04:06,135 --> 00:04:08,420
dan itu semacam rumit
Hal dengan rekursi adalah,

85
00:04:08,420 --> 00:04:10,930
Anda perlu menjaga Anda
kepala tentang di mana kita berada.

86
00:04:10,930 --> 00:04:15,560
Jadi kita sudah semacam kiri
setengah dari porsi jeruk.

87
00:04:15,560 --> 00:04:21,280
>> Dan sekarang, kita berada di tengah-tengah menyortir
kanan setengah dari porsi jeruk.

88
00:04:21,280 --> 00:04:25,320
Dan dalam proses itu, kita
sekarang akan berada di langkah,

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

90
00:04:27,850 --> 00:04:31,700
Ketika kita melihat dua bagian
dari array, kita melihat dua dan satu.

91
00:04:31,700 --> 00:04:33,880
Yang elemen lebih kecil?

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

93
00:04:35,160 --> 00:04:36,760
>> Kemudian yang elemen lebih kecil?

94
00:04:36,760 --> 00:04:38,300
Nah, itu dua atau tidak.

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

96
00:04:39,910 --> 00:04:43,690
Jadi sekarang, hanya untuk membingkai lagi
di mana kita berada dalam konteks,

97
00:04:43,690 --> 00:04:48,230
kami telah diurutkan
kiri setengah dari jeruk

98
00:04:48,230 --> 00:04:49,886
dan bagian kanan asal.

99
00:04:49,886 --> 00:04:52,510
Aku tahu aku sudah berubah warna
lagi, tapi itu di mana kita berada.

100
00:04:52,510 --> 00:04:54,676
Dan alasan saya melakukan ini
karena proses ini

101
00:04:54,676 --> 00:04:57,870
akan terus, iterasi turun.

102
00:04:57,870 --> 00:05:00,500
Kami telah diurutkan kiri
setengah dari mantan orange

103
00:05:00,500 --> 00:05:02,590
dan kanan setengah dari mantan oranye.

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

105
00:05:05,620 --> 00:05:07,730
Itulah langkah kami di.

106
00:05:07,730 --> 00:05:11,440
Jadi kita mempertimbangkan semua
elemen yang sekarang hijau,

107
00:05:11,440 --> 00:05:12,972
kiri setengah dari array asli.

108
00:05:12,972 --> 00:05:14,680
Dan kami gabungkan
menggunakan proses yang sama

109
00:05:14,680 --> 00:05:18,660
kami lakukan untuk penggabungan dua
dan satu hanya beberapa saat yang lalu.

110
00:05:18,660 --> 00:05:23,080
>> Kiri setengah, yang terkecil
elemen pada kiri setengah lima.

111
00:05:23,080 --> 00:05:25,620
Elemen terkecil pada
bagian kanan adalah salah satu.

112
00:05:25,620 --> 00:05:27,370
Mana yang lebih kecil?

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

114
00:05:29,260 --> 00:05:32,250
>> Elemen terkecil pada
kiri setengah lima.

115
00:05:32,250 --> 00:05:35,540
Elemen terkecil pada
kanan setengah dua.

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

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

118
00:05:38,160 --> 00:05:41,540
Dan kemudian terakhir lima dan
apa-apa, kita dapat mengatakan lima.

119
00:05:41,540 --> 00:05:43,935
>> OK, gambar begitu besar, mari kita
istirahat untuk kedua

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

121
00:05:46,080 --> 00:05:48,580
Jika kita mulai dari
awal, kami

122
00:05:48,580 --> 00:05:51,640
sekarang telah diselesaikan untuk
array secara keseluruhan hanya

123
00:05:51,640 --> 00:05:53,810
satu langkah dari kode pseudocode sini.

124
00:05:53,810 --> 00:05:56,645
Kami telah diurutkan
kiri setengah dari array.

125
00:05:56,645 --> 00:05:59,490
>> Ingat bahwa asli
Agar lima, 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
terus memecahkan masalah
ke dalam bagian yang lebih kecil dan lebih kecil,

128
00:06:05,990 --> 00:06:09,670
kita sekarang telah menyelesaikan
langkah salah pseudocode

129
00:06:09,670 --> 00:06:13,940
untuk seluruh array awal.

130
00:06:13,940 --> 00:06:16,670
Kami telah diurutkan setengah kiri.

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

132
00:06:18,670 --> 00:06:23,087
Dan sekarang mari kita mengurutkan kanan
setengah dari array asli.

133
00:06:23,087 --> 00:06:25,670
Dan kita akan melakukannya dengan
akan melalui iterasi yang sama

134
00:06:25,670 --> 00:06:30,630
Proses melanggar segalanya
dan kemudian menggabungkan mereka bersama-sama.

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

136
00:06:34,290 --> 00:06:38,830
dari kanan setengah dari aslinya
array, saya akan katakan adalah tiga.

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

138
00:06:40,312 --> 00:06:42,020
Jika Anda memiliki aneh
jumlah elemen, itu

139
00:06:42,020 --> 00:06:44,478
tidak benar-benar peduli apakah
Anda membuat satu kiri lebih kecil

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

141
00:06:45,620 --> 00:06:49,230
>> Yang penting adalah bahwa setiap kali Anda
menghadapi masalah ini dalam melakukan

142
00:06:49,230 --> 00:06:51,422
gabungan, Anda harus konsisten.

143
00:06:51,422 --> 00:06:53,505
Anda juga harus selalu
membuat sisi kiri lebih kecil

144
00:06:53,505 --> 00:06:55,421
atau selalu perlu membuat
sisi kanan yang lebih kecil.

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

146
00:06:57,720 --> 00:07:04,380
ketika array saya, atau saya
sub-array, adalah ukuran yang aneh.

147
00:07:04,380 --> 00:07:07,420
>> Tiga adalah satu elemen,
dan karena itu diurutkan.

148
00:07:07,420 --> 00:07:10,860
Kami telah memanfaatkan asumsi bahwa
sepanjang seluruh proses kami sejauh ini.

149
00:07:10,860 --> 00:07:15,020
Jadi sekarang mari kita mengurutkan kanan
setengah dari setengah benar,

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

151
00:07:18,210 --> 00:07:20,390
>> Sekali lagi, kita perlu untuk membagi ini turun.

152
00:07:20,390 --> 00:07:21,910
Ini bukan array elemen tunggal.

153
00:07:21,910 --> 00:07:23,970
Kita tidak bisa menyatakan itu diurutkan.

154
00:07:23,970 --> 00:07:27,060
Dan jadi pertama, kita akan
memilah kiri setengah.

155
00:07:27,060 --> 00:07:31,620
>> Setengah kiri adalah elemen tunggal,
jadi semacam secara default.

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

157
00:07:34,840 --> 00:07:41,250
Ini diurutkan secara default. Dan sekarang,
kita bisa menggabungkan dua bersama-sama.

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

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

160
00:07:48,870 --> 00:07:52,512
Kami telah diurutkan kiri
setengah dari setengah benar.

161
00:07:52,512 --> 00:07:54,720
Atau akan kembali ke aslinya
warna yang ada,

162
00:07:54,720 --> 00:07:57,875
kami telah diurutkan kiri
setengah dari merah lembut.

163
00:07:57,875 --> 00:08:00,416
Awalnya batu bata gelap
merah dan sekarang itu lebih lembut merah,

164
00:08:00,416 --> 00:08:02,350
atau itu merah lembut.

165
00:08:02,350 --> 00:08:05,145
>> Dan kemudian kami telah diurutkan
setengah kanan merah lembut.

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

167
00:08:08,270 --> 00:08:10,720
Dan kita harus mengulang
ini berulang.

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

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

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

171
00:08:17,653 --> 00:08:19,690
dan kanan setengah dari semacam bagian ini.

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

173
00:08:24,310 --> 00:08:26,710
atau permisi, terkecil
nilai kiri setengah

174
00:08:26,710 --> 00:08:30,790
dengan nilai terkecil dari kanan
setengah dan menemukan bahwa tiga lebih kecil.

175
00:08:30,790 --> 00:08:32,530
Dan sekarang sedikit optimasi, kan?

176
00:08:32,530 --> 00:08:35,175
Sebenarnya ada apa-apa
kiri di sisi kiri.

177
00:08:35,175 --> 00:08:37,440
>> Tidak ada yang tersisa
di sisi kiri,

178
00:08:37,440 --> 00:08:40,877
sehingga kita bisa efisien
hanya move-- kita dapat mendeklarasikan

179
00:08:40,877 --> 00:08:42,960
sisanya sebenarnya
diurutkan dan hanya taktik itu

180
00:08:42,960 --> 00:08:45,126
pada, karena tidak ada
lain untuk membandingkan terhadap.

181
00:08:45,126 --> 00:08:49,140
Dan kita tahu bahwa sisi kanan
dari sisi kanan diurutkan.

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

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

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

185
00:08:58,790 --> 00:09:03,300
Kami diurutkan kiri setengah, dan
kami diurutkan kanan setengah.

186
00:09:03,300 --> 00:09:08,210
>> Jadi sekarang, semua yang tersisa adalah bagi kita
untuk menggabungkan dua bagian bersama-sama.

187
00:09:08,210 --> 00:09:11,670
Jadi kita membandingkan termurah dihargai
unsur masing-masing setengah dari array

188
00:09:11,670 --> 00:09:13,510
pada gilirannya dan melanjutkan.

189
00:09:13,510 --> 00:09:16,535
Salah satunya adalah kurang dari tiga, jadi satu pergi.

190
00:09:16,535 --> 00:09:19,770
>> Dua kurang dari tiga, sehingga dua pergi.

191
00:09:19,770 --> 00:09:22,740
Tiga kurang dari 5, sehingga tiga pergi.

192
00:09:22,740 --> 00:09:25,820
Empat kurang dari 5, sehingga empat pergi.

193
00:09:25,820 --> 00:09:30,210
Kemudian lima kurang dari enam,
dan enam adalah semua yang tersisa.

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

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

196
00:09:33,636 --> 00:09:35,260
Dan itulah yang mereka kotak abu-abu.

197
00:09:35,260 --> 00:09:40,540
Dan mungkin merasa seperti itu mengambil
banyak lebih lama dari insertion sort, bubble

198
00:09:40,540 --> 00:09:42,660
semacam, atau semacam seleksi.

199
00:09:42,660 --> 00:09:45,330
>> Tapi sebenarnya, karena
banyak proses ini

200
00:09:45,330 --> 00:09:48,260
yang terjadi di time-- sama
yang merupakan sesuatu yang kita akan, lagi,

201
00:09:48,260 --> 00:09:51,100
berbicara tentang ketika kita berbicara tentang
rekursi di masa depan video--

202
00:09:51,100 --> 00:09:53,799
algoritma ini benar-benar
jelas adalah fundamental

203
00:09:53,799 --> 00:09:55,590
yang berbeda dari apa pun
kita telah melihat sebelumnya

204
00:09:55,590 --> 00:09:58,820
tetapi juga secara signifikan
lebih hemat.

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

206
00:09:59,532 --> 00:10:01,240
Nah, di terburuk
skenario, kita memiliki

207
00:10:01,240 --> 00:10:04,830
untuk membagi n elemen up
dan kemudian bergabung kembali mereka.

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

209
00:10:06,680 --> 00:10:11,110
pada dasarnya menggandakan
ukuran array yang lebih kecil.

210
00:10:11,110 --> 00:10:14,260
Kami memiliki sekelompok satu elemen
array yang kita efektif

211
00:10:14,260 --> 00:10:16,290
menggabungkan ke dua array elemen.

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

213
00:10:18,590 --> 00:10:21,890
dan menggabungkannya ke
empat elemen array, dan sebagainya,

214
00:10:21,890 --> 00:10:26,130
dan seterusnya, dan seterusnya, sampai kita
memiliki array elemen n tunggal.

215
00:10:26,130 --> 00:10:29,910
>> Tapi berapa banyak doubling
yang dibutuhkan untuk sampai ke n?

216
00:10:29,910 --> 00:10:31,460
Pikirkan kembali ke contoh buku telepon.

217
00:10:31,460 --> 00:10:34,490
Berapa kali kita harus merobek
buku telepon di setengah, berapa banyak lagi

218
00:10:34,490 --> 00:10:38,370
kali kita harus merobek buku telepon
dalam setengah, jika ukuran buku telepon

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

220
00:10:39,680 --> 00:10:41,960
Hanya ada satu, kan?

221
00:10:41,960 --> 00:10:45,360
>> Jadi ada semacam
elemen logaritmik sini.

222
00:10:45,360 --> 00:10:48,590
Tapi kami juga masih harus setidaknya
melihat semua elemen n.

223
00:10:48,590 --> 00:10:53,860
Jadi dalam skenario terburuk,
menggabungkan semacam berjalan di n log n.

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

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

226
00:11:02,915 --> 00:11:05,290
Dalam skenario kasus terbaik,
array sempurna diurutkan.

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

228
00:11:06,300 --> 00:11:09,980
Tetapi berdasarkan algoritma yang kita miliki di sini,
kita masih harus membagi dan bergabung kembali.

229
00:11:09,980 --> 00:11:13,290
Meskipun dalam hal ini,
recombining adalah jenis yang tidak efektif.

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

231
00:11:14,720 --> 00:11:17,580
Tapi kami masih pergi melalui
seluruh proses pula.

232
00:11:17,580 --> 00:11:21,290
>> Jadi dalam kasus terbaik
dan dalam kasus terburuk,

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

234
00:11:24,970 --> 00:11:29,130
Menggabungkan semacam pasti sedikit lebih sulit
dari algoritma pemilahan utama lainnya

235
00:11:29,130 --> 00:11:33,470
kita bicarakan CS50 tetapi
substansial lebih kuat.

236
00:11:33,470 --> 00:11:35,400
>> Dan jadi jika Anda pernah menemukan
kesempatan untuk membutuhkannya

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

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

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

240
00:11:45,270 --> 00:11:48,700
menggunakan menggabungkan semacam dibandingkan apa pun.

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

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

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