1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Anda mungkin pernah mendengar orang berbicara tentang algoritma cepat atau efisien

2
00:00:10,950 --> 00:00:13,090
untuk melaksanakan tugas tertentu Anda,

3
00:00:13,090 --> 00:00:16,110
tapi apa sebenarnya artinya untuk algoritma untuk menjadi cepat atau efisien?

4
00:00:16,110 --> 00:00:18,580
Nah, itu tidak berbicara tentang pengukuran secara real time,

5
00:00:18,580 --> 00:00:20,500
seperti detik atau menit.

6
00:00:20,500 --> 00:00:22,220
Hal ini karena perangkat keras komputer

7
00:00:22,220 --> 00:00:24,260
dan perangkat lunak bervariasi secara drastis.

8
00:00:24,260 --> 00:00:26,020
Program saya bisa berjalan lebih lambat dari Anda,

9
00:00:26,020 --> 00:00:28,000
karena aku menjalankannya pada komputer yang lebih tua,

10
00:00:28,000 --> 00:00:30,110
atau karena saya kebetulan bermain game video online

11
00:00:30,110 --> 00:00:32,670
pada saat yang sama, yang memonopoli semua memori saya,

12
00:00:32,670 --> 00:00:35,400
atau aku mungkin menjalankan program saya melalui perangkat lunak yang berbeda

13
00:00:35,400 --> 00:00:37,550
yang berkomunikasi dengan mesin berbeda pada tingkat yang rendah.

14
00:00:37,550 --> 00:00:39,650
Ini seperti membandingkan apel dan jeruk.

15
00:00:39,650 --> 00:00:41,940
Hanya karena komputer saya lambat memakan waktu lebih lama

16
00:00:41,940 --> 00:00:43,410
dari Anda untuk memberikan kembali jawaban

17
00:00:43,410 --> 00:00:45,510
tidak berarti Anda memiliki algoritma yang lebih efisien.

18
00:00:45,510 --> 00:00:48,830
>> Jadi, karena kita tidak bisa langsung membandingkan runtimes program

19
00:00:48,830 --> 00:00:50,140
dalam hitungan detik atau menit,

20
00:00:50,140 --> 00:00:52,310
bagaimana kita membandingkan 2 algoritma yang berbeda

21
00:00:52,310 --> 00:00:55,030
terlepas dari hardware atau lingkungan perangkat lunak?

22
00:00:55,030 --> 00:00:58,000
Untuk membuat cara yang lebih seragam untuk mengukur efisiensi algoritmik,

23
00:00:58,000 --> 00:01:00,360
ilmuwan komputer dan matematika telah menyusun

24
00:01:00,360 --> 00:01:03,830
konsep untuk mengukur kompleksitas asimtotik dari program

25
00:01:03,830 --> 00:01:06,110
dan notasi yang disebut 'Ohnotation Big'

26
00:01:06,110 --> 00:01:08,320
untuk menggambarkan hal ini.

27
00:01:08,320 --> 00:01:10,820
Definisi formal adalah bahwa fungsi f (x)

28
00:01:10,820 --> 00:01:13,390
berjalan pada urutan g (x)

29
00:01:13,390 --> 00:01:15,140
jika ada beberapa nilai (x), x dan ₀

30
00:01:15,140 --> 00:01:17,630
beberapa konstan, C, yang

31
00:01:17,630 --> 00:01:19,340
f (x) adalah kurang dari atau sama dengan

32
00:01:19,340 --> 00:01:21,230
bahwa kali konstanta g (x)

33
00:01:21,230 --> 00:01:23,190
untuk semua x lebih besar daripada x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Tapi jangan takut pergi oleh definisi formal.

35
00:01:25,290 --> 00:01:28,020
Apakah ini benar-benar berarti dalam waktu kurang istilah teoritis?

36
00:01:28,020 --> 00:01:30,580
Yah, itu pada dasarnya cara menganalisis

37
00:01:30,580 --> 00:01:33,580
seberapa cepat runtime program ini tumbuh asimtotik.

38
00:01:33,580 --> 00:01:37,170
Artinya, sebagai ukuran masukan Anda meningkat menuju tak terhingga,

39
00:01:37,170 --> 00:01:41,390
mengatakan, Anda sedang menyortir sebuah array ukuran 1.000 dibandingkan dengan array ukuran 10.

40
00:01:41,390 --> 00:01:44,950
Bagaimana runtime program Anda tumbuh?

41
00:01:44,950 --> 00:01:47,390
Sebagai contoh, bayangkan menghitung jumlah karakter

42
00:01:47,390 --> 00:01:49,350
dalam sebuah string cara paling sederhana

43
00:01:49,350 --> 00:01:51,620
 dengan berjalan melalui seluruh string

44
00:01:51,620 --> 00:01:54,790
Surat-by-surat dan menambahkan 1 ke counter untuk setiap karakter.

45
00:01:55,700 --> 00:01:58,420
Algoritma ini dikatakan berjalan dalam waktu linear

46
00:01:58,420 --> 00:02:00,460
sehubungan dengan jumlah karakter,

47
00:02:00,460 --> 00:02:02,670
'N' dalam string.

48
00:02:02,670 --> 00:02:04,910
Singkatnya, berjalan di O (n).

49
00:02:05,570 --> 00:02:07,290
Mengapa ini?

50
00:02:07,290 --> 00:02:09,539
Nah, dengan menggunakan pendekatan ini, waktu yang diperlukan

51
00:02:09,539 --> 00:02:11,300
untuk melintasi seluruh string

52
00:02:11,300 --> 00:02:13,920
sebanding dengan jumlah karakter.

53
00:02:13,920 --> 00:02:16,480
Menghitung jumlah karakter dalam string 20-karakter

54
00:02:16,480 --> 00:02:18,580
akan mengambil dua kali lebih lama yang dibutuhkan

55
00:02:18,580 --> 00:02:20,330
untuk menghitung karakter dalam string 10-karakter,

56
00:02:20,330 --> 00:02:23,000
karena Anda harus melihat semua karakter

57
00:02:23,000 --> 00:02:25,740
dan karakter masing-masing mengambil jumlah waktu yang sama untuk melihat.

58
00:02:25,740 --> 00:02:28,050
Seperti Anda meningkatkan jumlah karakter,

59
00:02:28,050 --> 00:02:30,950
runtime akan meningkat secara linear dengan panjang input.

60
00:02:30,950 --> 00:02:33,500
>> Sekarang, bayangkan jika Anda memutuskan bahwa waktu linier,

61
00:02:33,500 --> 00:02:36,390
O (n), hanya tidak cukup cepat untuk Anda?

62
00:02:36,390 --> 00:02:38,750
Mungkin Anda menyimpan string besar,

63
00:02:38,750 --> 00:02:40,450
dan Anda tidak dapat membayar waktu tambahan itu akan mengambil

64
00:02:40,450 --> 00:02:44,000
untuk melintasi semua karakter mereka menghitung satu-per-satu.

65
00:02:44,000 --> 00:02:46,650
Jadi, Anda memutuskan untuk mencoba sesuatu yang berbeda.

66
00:02:46,650 --> 00:02:49,270
Bagaimana jika Anda akan terjadi sudah menyimpan jumlah karakter

67
00:02:49,270 --> 00:02:52,690
dalam string, misalnya, dalam sebuah variabel yang disebut 'len,'

68
00:02:52,690 --> 00:02:54,210
pada awal program,

69
00:02:54,210 --> 00:02:57,800
bahkan sebelum Anda menyimpan karakter pertama dalam string Anda?

70
00:02:57,800 --> 00:02:59,980
Kemudian, semua yang Anda harus lakukan sekarang untuk mengetahui panjang string,

71
00:02:59,980 --> 00:03:02,570
adalah memeriksa apa nilai variabel tersebut.

72
00:03:02,570 --> 00:03:05,530
Anda tidak perlu melihat string itu sendiri sama sekali,

73
00:03:05,530 --> 00:03:08,160
dan mengakses nilai dari variabel seperti len dianggap

74
00:03:08,160 --> 00:03:11,100
operasi asimtotik konstan waktu,

75
00:03:11,100 --> 00:03:13,070
atau O (1).

76
00:03:13,070 --> 00:03:17,110
Mengapa ini? Nah, mengingat apa kompleksitas asimtotik berarti.

77
00:03:17,110 --> 00:03:19,100
Bagaimana perubahan runtime sebagai ukuran

78
00:03:19,100 --> 00:03:21,400
masukan dari Anda tumbuh?

79
00:03:21,400 --> 00:03:24,630
>> Katakanlah Anda sedang mencoba untuk mendapatkan jumlah karakter dalam string yang lebih besar.

80
00:03:24,630 --> 00:03:26,960
Yah, itu tidak akan peduli seberapa besar Anda membuat string,

81
00:03:26,960 --> 00:03:28,690
bahkan satu juta karakter,

82
00:03:28,690 --> 00:03:31,150
semua yang Anda harus lakukan untuk menemukan panjang string dengan pendekatan ini,

83
00:03:31,150 --> 00:03:33,790
adalah untuk membaca nilai dari variabel len,

84
00:03:33,790 --> 00:03:35,440
Anda yang sudah dibuat.

85
00:03:35,440 --> 00:03:38,200
Panjang masukan, yaitu panjang string Anda mencoba untuk menemukan,

86
00:03:38,200 --> 00:03:41,510
tidak mempengaruhi sama sekali seberapa cepat program Anda berjalan.

87
00:03:41,510 --> 00:03:44,550
Ini bagian dari program anda akan berjalan sama cepat pada tali satu karakter

88
00:03:44,550 --> 00:03:46,170
dan string seribu karakter,

89
00:03:46,170 --> 00:03:49,140
dan itulah mengapa program ini akan disebut sebagai berjalan dalam waktu yang konstan

90
00:03:49,140 --> 00:03:51,520
sehubungan dengan ukuran input.

91
00:03:51,520 --> 00:03:53,920
>> Tentu saja, ada kelemahan.

92
00:03:53,920 --> 00:03:55,710
Anda menghabiskan ruang memori tambahan pada komputer Anda

93
00:03:55,710 --> 00:03:57,380
menyimpan variabel

94
00:03:57,380 --> 00:03:59,270
dan waktu tambahan yang diperlukan Anda

95
00:03:59,270 --> 00:04:01,490
untuk melakukan penyimpanan sebenarnya dari variabel,

96
00:04:01,490 --> 00:04:03,390
tapi intinya masih berdiri,

97
00:04:03,390 --> 00:04:05,060
mencari tahu berapa lama string Anda adalah

98
00:04:05,060 --> 00:04:07,600
tidak tergantung pada panjang dari string sama sekali.

99
00:04:07,600 --> 00:04:10,720
Jadi, itu berjalan dalam O (1) atau waktu konstan.

100
00:04:10,720 --> 00:04:13,070
Hal ini tentu tidak harus berarti

101
00:04:13,070 --> 00:04:15,610
bahwa kode Anda berjalan dalam 1 langkah,

102
00:04:15,610 --> 00:04:17,470
tetapi tidak peduli berapa banyak langkah itu,

103
00:04:17,470 --> 00:04:20,019
jika tidak berubah dengan ukuran input,

104
00:04:20,019 --> 00:04:23,420
itu masih asimtotik konstan yang kami hadirkan sebagai O (1).

105
00:04:23,420 --> 00:04:25,120
>> Seperti yang Anda mungkin bisa menebak,

106
00:04:25,120 --> 00:04:27,940
ada banyak yang berbeda runtimes O besar untuk mengukur algoritma dengan.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritma asimtotik lebih lambat dari O (n) algoritma.

108
00:04:32,980 --> 00:04:35,910
Artinya, sebagai jumlah elemen (n) tumbuh,

109
00:04:35,910 --> 00:04:39,280
akhirnya O (n) ² algoritma akan memakan waktu lebih

110
00:04:39,280 --> 00:04:41,000
dari O (n) algoritma untuk menjalankan.

111
00:04:41,000 --> 00:04:43,960
Ini tidak berarti O (n) algoritma selalu berjalan lebih cepat

112
00:04:43,960 --> 00:04:46,410
dari O (n) algoritma ², bahkan di lingkungan yang sama,

113
00:04:46,410 --> 00:04:48,080
pada hardware yang sama.

114
00:04:48,080 --> 00:04:50,180
Mungkin untuk ukuran masukan kecil,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritma mungkin benar-benar bekerja lebih cepat,

116
00:04:52,900 --> 00:04:55,450
namun, pada akhirnya, sebagai ukuran input meningkat

117
00:04:55,450 --> 00:04:58,760
menuju tak terhingga, O (n) runtime ² algoritma

118
00:04:58,760 --> 00:05:02,000
akhirnya akan gerhana runtime dari algoritma (n) O.

119
00:05:02,000 --> 00:05:04,230
Sama seperti fungsi matematika kuadrat

120
00:05:04,230 --> 00:05:06,510
 akhirnya akan menyalip setiap fungsi linear,

121
00:05:06,510 --> 00:05:09,200
tidak peduli berapa banyak kepala mulai fungsi linear dimulai dengan.

122
00:05:10,010 --> 00:05:12,000
Jika Anda bekerja dengan data dalam jumlah besar,

123
00:05:12,000 --> 00:05:15,510
algoritma yang berjalan di O (n) ² waktu benar-benar dapat berakhir memperlambat program Anda,

124
00:05:15,510 --> 00:05:17,770
tapi untuk ukuran masukan kecil,

125
00:05:17,770 --> 00:05:19,420
Anda mungkin tidak akan menyadarinya.

126
00:05:19,420 --> 00:05:21,280
>> Lain kompleksitas asimtotik adalah,

127
00:05:21,280 --> 00:05:24,420
waktu logaritmik, O (log n).

128
00:05:24,420 --> 00:05:26,340
Sebuah contoh dari suatu algoritma yang berjalan cepat ini

129
00:05:26,340 --> 00:05:29,060
adalah algoritma biner klasik pencarian,

130
00:05:29,060 --> 00:05:31,850
untuk menemukan elemen dalam daftar yang sudah diurutkan elemen.

131
00:05:31,850 --> 00:05:33,400
>> Jika Anda tidak tahu apa pencarian biner tidak,

132
00:05:33,400 --> 00:05:35,170
Saya akan menjelaskannya untuk Anda benar-benar cepat.

133
00:05:35,170 --> 00:05:37,020
Katakanlah Anda sedang mencari nomor 3

134
00:05:37,020 --> 00:05:40,200
dalam array bilangan bulat.

135
00:05:40,200 --> 00:05:42,140
Ini terlihat pada elemen tengah dari array

136
00:05:42,140 --> 00:05:46,830
dan bertanya, "Apakah unsur saya ingin lebih besar dari, sama dengan, atau kurang dari ini?"

137
00:05:46,830 --> 00:05:49,150
Jika itu sama, maka besar. Anda menemukan elemen, dan Anda sudah selesai.

138
00:05:49,150 --> 00:05:51,300
Jika itu lebih besar, maka Anda tahu elemen

139
00:05:51,300 --> 00:05:53,440
harus berada di sisi kanan dari array,

140
00:05:53,440 --> 00:05:55,200
dan Anda hanya bisa melihat bahwa di masa depan,

141
00:05:55,200 --> 00:05:57,690
dan jika lebih kecil, maka Anda tahu itu harus berada di sisi kiri.

142
00:05:57,690 --> 00:06:00,980
Proses ini kemudian diulang dengan array yang lebih kecil ukuran

143
00:06:00,980 --> 00:06:02,870
sampai elemen yang benar ditemukan.

144
00:06:08,080 --> 00:06:11,670
>> Ini algoritma yang kuat memotong ukuran array dalam setengah dengan setiap operasi.

145
00:06:11,670 --> 00:06:14,080
Jadi, untuk menemukan elemen dalam array diurutkan dari ukuran 8,

146
00:06:14,080 --> 00:06:16,170
paling (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
atau 3 dari operasi ini,

148
00:06:18,450 --> 00:06:22,260
memeriksa elemen tengah, kemudian memotong array di setengah akan diperlukan,

149
00:06:22,260 --> 00:06:25,670
sedangkan array ukuran 16 mengambil (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
atau 4 operasi.

151
00:06:27,480 --> 00:06:30,570
Itu hanya 1 operasi lebih untuk array dua kali lipat ukuran.

152
00:06:30,570 --> 00:06:32,220
Menggandakan ukuran array

153
00:06:32,220 --> 00:06:35,160
meningkatkan runtime dengan hanya 1 sepotong kode ini.

154
00:06:35,160 --> 00:06:37,770
Sekali lagi, memeriksa elemen tengah daftar, kemudian membelah.

155
00:06:37,770 --> 00:06:40,440
Jadi, itu dikatakan beroperasi dalam waktu logaritmik,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Tapi tunggu, Anda katakan,

158
00:06:44,270 --> 00:06:47,510
tidak ini tergantung pada di mana dalam daftar elemen yang Anda cari adalah?

159
00:06:47,510 --> 00:06:50,090
Bagaimana jika elemen pertama Anda melihat kebetulan yang benar?

160
00:06:50,090 --> 00:06:52,040
Kemudian, hanya membutuhkan waktu 1 operasi,

161
00:06:52,040 --> 00:06:54,310
tidak peduli seberapa besar daftar ini.

162
00:06:54,310 --> 00:06:56,310
>> Nah, itu sebabnya ilmuwan komputer memiliki istilah yang lebih

163
00:06:56,310 --> 00:06:58,770
untuk kompleksitas asimtotik yang mencerminkan kasus terbaik

164
00:06:58,770 --> 00:07:01,050
dan kasus terburuk kinerja dari algoritma.

165
00:07:01,050 --> 00:07:03,320
Lebih baik, atas dan batas bawah

166
00:07:03,320 --> 00:07:05,090
pada runtime.

167
00:07:05,090 --> 00:07:07,660
Dalam kasus terbaik untuk pencarian biner, elemen kita

168
00:07:07,660 --> 00:07:09,330
tepat di tengah,

169
00:07:09,330 --> 00:07:11,770
dan Anda mendapatkannya dalam waktu yang konstan,

170
00:07:11,770 --> 00:07:14,240
tidak peduli seberapa besar sisa array.

171
00:07:15,360 --> 00:07:17,650
Simbol yang digunakan untuk ini adalah Ω.

172
00:07:17,650 --> 00:07:19,930
Jadi, algoritma ini dikatakan berjalan dalam Ω (1).

173
00:07:19,930 --> 00:07:21,990
Dalam kasus terbaik, ia menemukan unsur dengan cepat,

174
00:07:21,990 --> 00:07:24,200
tidak peduli seberapa besar array adalah,

175
00:07:24,200 --> 00:07:26,050
namun dalam kasus terburuk,

176
00:07:26,050 --> 00:07:28,690
itu harus melakukan (log n) cek perpecahan

177
00:07:28,690 --> 00:07:31,030
dari array untuk menemukan elemen yang tepat.

178
00:07:31,030 --> 00:07:34,270
Terburuk batas-huruf besar yang disebut dengan big "O" yang Anda sudah tahu.

179
00:07:34,270 --> 00:07:38,080
Jadi, itu O (log n), namun Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Sebuah pencarian linier, sebaliknya,

181
00:07:40,680 --> 00:07:43,220
di mana Anda berjalan melalui setiap elemen dari array

182
00:07:43,220 --> 00:07:45,170
untuk menemukan yang Anda inginkan,

183
00:07:45,170 --> 00:07:47,420
adalah pada Ω terbaik (1).

184
00:07:47,420 --> 00:07:49,430
Sekali lagi, elemen pertama Anda inginkan.

185
00:07:49,430 --> 00:07:51,930
Jadi, tidak peduli seberapa besar array.

186
00:07:51,930 --> 00:07:54,840
Dalam kasus terburuk, itu adalah elemen terakhir dalam array.

187
00:07:54,840 --> 00:07:58,560
Jadi, Anda harus berjalan melalui semua elemen n dalam array untuk menemukan itu,

188
00:07:58,560 --> 00:08:02,170
seperti jika Anda sedang mencari 3 a.

189
00:08:04,320 --> 00:08:06,030
Jadi, itu berjalan dalam O (n) waktu

190
00:08:06,030 --> 00:08:09,330
karena itu sebanding dengan jumlah elemen dalam array.

191
00:08:10,800 --> 00:08:12,830
>> Satu simbol yang lebih digunakan adalah Θ.

192
00:08:12,830 --> 00:08:15,820
Hal ini dapat digunakan untuk menggambarkan algoritma di mana kasus-kasus terbaik dan terburuk

193
00:08:15,820 --> 00:08:17,440
adalah sama.

194
00:08:17,440 --> 00:08:20,390
Ini adalah kasus dalam string-panjang algoritma kita bicarakan sebelumnya.

195
00:08:20,390 --> 00:08:22,780
Artinya, jika kita menyimpannya dalam variabel sebelum

196
00:08:22,780 --> 00:08:25,160
kita menyimpan string dan mengaksesnya kemudian dalam waktu yang konstan.

197
00:08:25,160 --> 00:08:27,920
Tidak peduli apa nomor

198
00:08:27,920 --> 00:08:30,130
kita menyimpan dalam variabel itu, kita harus melihatnya.

199
00:08:33,110 --> 00:08:35,110
Kasus terbaik adalah, kita melihat hal itu

200
00:08:35,110 --> 00:08:37,120
dan menemukan panjang string.

201
00:08:37,120 --> 00:08:39,799
Jadi Ω (1) atau terbaik-kasus waktu konstan.

202
00:08:39,799 --> 00:08:41,059
Kasus terburuk adalah,

203
00:08:41,059 --> 00:08:43,400
kita melihat dan menemukan panjang string.

204
00:08:43,400 --> 00:08:47,300
Jadi, O (1) atau waktu konstan dalam kasus terburuk.

205
00:08:47,300 --> 00:08:49,180
Jadi, sejak kasus terbaik dan kasus terburuk adalah sama,

206
00:08:49,180 --> 00:08:52,520
ini dapat dikatakan berjalan dalam Θ (1) waktu.

207
00:08:54,550 --> 00:08:57,010
>> Singkatnya, kita memiliki cara yang baik untuk alasan tentang efisiensi kode

208
00:08:57,010 --> 00:09:00,110
tanpa mengetahui apa-apa tentang waktu dunia nyata mereka diperlukan untuk menjalankan,

209
00:09:00,110 --> 00:09:02,270
yang dipengaruhi oleh banyak faktor luar,

210
00:09:02,270 --> 00:09:04,190
termasuk hardware yang berbeda, perangkat lunak,

211
00:09:04,190 --> 00:09:06,040
atau spesifik dari kode Anda.

212
00:09:06,040 --> 00:09:08,380
Juga, memungkinkan kita untuk berfikir dengan baik tentang apa yang akan terjadi

213
00:09:08,380 --> 00:09:10,180
ketika ukuran dari kenaikan input.

214
00:09:10,180 --> 00:09:12,490
>> Jika Anda berjalan di algoritma O (n) ²,

215
00:09:12,490 --> 00:09:15,240
atau lebih buruk lagi, O (2 ⁿ) algoritma,

216
00:09:15,240 --> 00:09:17,170
salah satu jenis yang paling cepat berkembang,

217
00:09:17,170 --> 00:09:19,140
Anda benar-benar akan mulai melihat perlambatan

218
00:09:19,140 --> 00:09:21,220
ketika Anda mulai bekerja dengan sejumlah besar data.

219
00:09:21,220 --> 00:09:23,590
>> Itu kompleksitas asimtotik. Terima kasih.