1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Baiklah, jadi, kompleksitas komputasi.

3
00:00:07,910 --> 00:00:10,430
Hanya sedikit peringatan
sebelum kita menyelam terlalu far--

4
00:00:10,430 --> 00:00:13,070
ini mungkin akan menjadi salah
hal yang paling matematika-berat

5
00:00:13,070 --> 00:00:14,200
kita berbicara tentang di CS50.

6
00:00:14,200 --> 00:00:16,950
Mudah-mudahan itu tidak akan terlalu besar
dan kami akan mencoba dan membimbing Anda

7
00:00:16,950 --> 00:00:19,200
melalui proses, tapi
hanya sedikit peringatan yang adil.

8
00:00:19,200 --> 00:00:21,282
Ada sedikit
matematika terlibat di sini.

9
00:00:21,282 --> 00:00:23,990
Baiklah, jadi untuk membuat
penggunaan sumber daya komputasi kami

10
00:00:23,990 --> 00:00:28,170
di dunia-- nyata itu benar-benar
penting untuk memahami algoritma

11
00:00:28,170 --> 00:00:30,750
dan bagaimana mereka memproses data.

12
00:00:30,750 --> 00:00:32,810
Jika kita benar-benar memiliki
algoritma yang efisien, kami

13
00:00:32,810 --> 00:00:36,292
dapat meminimalkan jumlah sumber daya
kita harus tersedia untuk menghadapinya.

14
00:00:36,292 --> 00:00:38,750
Jika kita memiliki sebuah algoritma yang
akan mengambil banyak pekerjaan

15
00:00:38,750 --> 00:00:41,210
memproses benar
set besar data, itu

16
00:00:41,210 --> 00:00:44,030
akan memerlukan lebih banyak
dan lebih banyak sumber daya, yang

17
00:00:44,030 --> 00:00:47,980
adalah uang, RAM, semua hal semacam itu.

18
00:00:47,980 --> 00:00:52,090
>> Jadi, bisa menganalisis sebuah
algoritma menggunakan tool set ini,

19
00:00:52,090 --> 00:00:56,110
pada dasarnya, meminta question-- yang
bagaimana skala algoritma ini

20
00:00:56,110 --> 00:00:59,020
seperti yang kita membuang lebih banyak dan lebih banyak data itu?

21
00:00:59,020 --> 00:01:02,220
Dalam CS50, jumlah data kami
bekerja dengan cukup kecil.

22
00:01:02,220 --> 00:01:05,140
Umumnya, program kami akan
untuk menjalankan dalam kedua atau less--

23
00:01:05,140 --> 00:01:07,830
mungkin banyak kurang
terutama sejak dini.

24
00:01:07,830 --> 00:01:12,250
>> Tetapi berpikir tentang sebuah perusahaan yang penawaran
dengan ratusan juta pelanggan.

25
00:01:12,250 --> 00:01:14,970
Dan mereka perlu proses
bahwa data pelanggan.

26
00:01:14,970 --> 00:01:18,260
Karena jumlah pelanggan mereka
memiliki akan lebih besar dan lebih besar,

27
00:01:18,260 --> 00:01:21,230
itu akan membutuhkan
lebih dan lebih banyak sumber daya.

28
00:01:21,230 --> 00:01:22,926
Berapa banyak sumber?

29
00:01:22,926 --> 00:01:25,050
Yah, itu tergantung pada bagaimana
kita menganalisis algoritma,

30
00:01:25,050 --> 00:01:28,097
menggunakan alat-alat dalam toolbox ini.

31
00:01:28,097 --> 00:01:31,180
Ketika kita berbicara tentang kompleksitas
sebuah algorithm-- yang kadang-kadang Anda akan

32
00:01:31,180 --> 00:01:34,040
mendengarnya disebut sebagai waktu
kompleksitas atau ruang kompleksitas

33
00:01:34,040 --> 00:01:36,190
tapi kami hanya akan
untuk memanggil complexity--

34
00:01:36,190 --> 00:01:38,770
kita umumnya berbicara tentang
skenario terburuk.

35
00:01:38,770 --> 00:01:42,640
Mengingat tumpukan terburuk mutlak
Data yang kita dapat melemparkan di itu,

36
00:01:42,640 --> 00:01:46,440
bagaimana algoritma ini akan
memproses atau berurusan dengan data itu?

37
00:01:46,440 --> 00:01:51,450
Kita umumnya memanggil-kasus terburuk
runtime dari suatu algoritma besar-O.

38
00:01:51,450 --> 00:01:56,770
Jadi algoritma bisa dikatakan
berjalan dalam O n O atau n kuadrat.

39
00:01:56,770 --> 00:01:59,110
Dan lebih lanjut tentang apa yang
mereka berarti dalam satu detik.

40
00:01:59,110 --> 00:02:01,620
>> Kadang-kadang, meskipun, kita lakukan perawatan
tentang skenario kasus terbaik.

41
00:02:01,620 --> 00:02:05,400
Jika data apapun yang kami inginkan
hal itu terjadi dan itu benar-benar sempurna

42
00:02:05,400 --> 00:02:09,630
dan kami mengirimkan ini sempurna
mengatur data melalui algoritma kami.

43
00:02:09,630 --> 00:02:11,470
Bagaimana hal itu akan menangani dalam situasi itu?

44
00:02:11,470 --> 00:02:15,050
Kita kadang-kadang menyebut bahwa sebagai
besar-Omega, sehingga kontras dengan besar-O,

45
00:02:15,050 --> 00:02:16,530
kita memiliki besar-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega untuk skenario kasus terbaik.

47
00:02:18,880 --> 00:02:21,319
Big-O untuk skenario terburuk.

48
00:02:21,319 --> 00:02:23,860
Umumnya, ketika kita berbicara tentang
kompleksitas algoritma,

49
00:02:23,860 --> 00:02:26,370
kita berbicara tentang
skenario terburuk.

50
00:02:26,370 --> 00:02:28,100
Jadi ingatlah bahwa dalam pikiran.

51
00:02:28,100 --> 00:02:31,510
>> Dan di kelas ini, kita umumnya akan
meninggalkan analisis ketat samping.

52
00:02:31,510 --> 00:02:35,350
Ada ilmu dan bidang
dikhususkan untuk hal semacam ini.

53
00:02:35,350 --> 00:02:37,610
Ketika kita berbicara tentang penalaran
melalui algoritma,

54
00:02:37,610 --> 00:02:41,822
yang akan kita lakukan sepotong demi sepotong untuk banyak
algoritma kita berbicara tentang di kelas.

55
00:02:41,822 --> 00:02:44,780
Kami benar-benar hanya berbicara tentang
penalaran melalui itu dengan akal sehat,

56
00:02:44,780 --> 00:02:47,070
tidak dengan formula, atau bukti,
atau sesuatu seperti itu.

57
00:02:47,070 --> 00:02:51,600
Jadi jangan khawatir, kami tidak akan
berubah menjadi kelas matematika besar.

58
00:02:51,600 --> 00:02:55,920
>> Jadi aku berkata kita peduli kompleksitas
karena mengajukan pertanyaan, bagaimana

59
00:02:55,920 --> 00:03:00,160
jangan algoritma kami menangani lebih besar dan
set data yang lebih besar yang dilemparkan pada mereka.

60
00:03:00,160 --> 00:03:01,960
Nah, apa yang merupakan kumpulan data?

61
00:03:01,960 --> 00:03:03,910
Apa yang saya maksud ketika saya mengatakan bahwa?

62
00:03:03,910 --> 00:03:07,600
Artinya apa pun yang membuat paling
akal dalam konteks, jujur.

63
00:03:07,600 --> 00:03:11,160
Jika kita memiliki sebuah algoritma, yang
Proses Strings-- kami mungkin

64
00:03:11,160 --> 00:03:13,440
berbicara tentang ukuran string.

65
00:03:13,440 --> 00:03:15,190
Itu data set--
ukuran, jumlah

66
00:03:15,190 --> 00:03:17,050
karakter yang membentuk string.

67
00:03:17,050 --> 00:03:20,090
Jika kita berbicara tentang
algoritma yang memproses file,

68
00:03:20,090 --> 00:03:23,930
kita mungkin akan berbicara tentang bagaimana
banyak kilobyte terdiri file itu.

69
00:03:23,930 --> 00:03:25,710
Dan itulah kumpulan data.

70
00:03:25,710 --> 00:03:28,870
Jika kita berbicara tentang sebuah algoritma
yang menangani array lebih umum,

71
00:03:28,870 --> 00:03:31,510
seperti algoritma pengurutan
atau algoritma pencarian,

72
00:03:31,510 --> 00:03:36,690
kita mungkin berbicara tentang jumlah
elemen yang terdiri dari array.

73
00:03:36,690 --> 00:03:39,272
>> Sekarang, kita dapat mengukur
algorithm-- khususnya,

74
00:03:39,272 --> 00:03:40,980
ketika saya mengatakan kita bisa
mengukur suatu algoritma, saya

75
00:03:40,980 --> 00:03:43,840
berarti kita dapat mengukur seberapa
banyak sumber daya tidak memakan.

76
00:03:43,840 --> 00:03:48,990
Apakah sumber daya, berapa banyak
byte RAM-- atau megabyte RAM

77
00:03:48,990 --> 00:03:49,790
menggunakan.

78
00:03:49,790 --> 00:03:52,320
Atau berapa banyak waktu yang diperlukan untuk menjalankan.

79
00:03:52,320 --> 00:03:56,200
Dan kita bisa menyebutnya
mengukur, sewenang-wenang, f n.

80
00:03:56,200 --> 00:03:59,420
Di mana n adalah jumlah
elemen dalam kumpulan data.

81
00:03:59,420 --> 00:04:02,640
Dan f n adalah berapa banyak somethings.

82
00:04:02,640 --> 00:04:07,530
Berapa banyak unit sumberdaya melakukan
itu perlu memproses data tersebut.

83
00:04:07,530 --> 00:04:10,030
>> Sekarang, kita benar-benar tidak peduli
tentang apa f n adalah persis.

84
00:04:10,030 --> 00:04:13,700
Bahkan, kami sangat jarang will--
tentu tidak akan pernah di saya class-- ini

85
00:04:13,700 --> 00:04:18,709
menyelam ke setiap benar-benar mendalam
analisis apa yang f n adalah.

86
00:04:18,709 --> 00:04:23,510
Kami hanya akan berbicara tentang apa yang f
n adalah sekitar atau apa itu cenderung.

87
00:04:23,510 --> 00:04:27,600
Dan kecenderungan algoritma adalah
didikte oleh jangka tertinggi order.

88
00:04:27,600 --> 00:04:29,440
Dan kita bisa melihat apa yang saya
maksud dengan itu dengan mengambil

89
00:04:29,440 --> 00:04:31,910
a lihat contoh yang lebih konkret.

90
00:04:31,910 --> 00:04:34,620
>> Jadi mari kita mengatakan bahwa kita memiliki
tiga algoritma yang berbeda.

91
00:04:34,620 --> 00:04:39,350
Yang pertama mengambil n
potong dadu, beberapa unit sumberdaya

92
00:04:39,350 --> 00:04:42,880
untuk memproses set data berukuran n.

93
00:04:42,880 --> 00:04:47,000
Kami memiliki algoritma kedua yang mengambil
n potong dadu ditambah sumber n kuadrat

94
00:04:47,000 --> 00:04:49,350
untuk memproses set data berukuran n.

95
00:04:49,350 --> 00:04:52,030
Dan kami memiliki sepertiga
algoritma yang berjalan in-- yang

96
00:04:52,030 --> 00:04:58,300
mengambil n dikurangi potong dadu 8N kuadrat
ditambah 20 n unit sumberdaya

97
00:04:58,300 --> 00:05:02,370
untuk memproses algoritma
dengan data set ukuran n.

98
00:05:02,370 --> 00:05:05,594
>> Sekarang lagi, kami benar-benar tidak akan
untuk masuk ke tingkat detail.

99
00:05:05,594 --> 00:05:08,260
Aku benar-benar hanya memiliki ini up
di sini sebagai ilustrasi titik

100
00:05:08,260 --> 00:05:10,176
bahwa aku akan menjadi
membuat dalam satu detik, yang

101
00:05:10,176 --> 00:05:12,980
adalah bahwa kita hanya benar-benar peduli
tentang kecenderungan hal

102
00:05:12,980 --> 00:05:14,870
sebagai data set menjadi lebih besar.

103
00:05:14,870 --> 00:05:18,220
Jadi jika kumpulan data kecil, ada
sebenarnya perbedaan yang cukup besar

104
00:05:18,220 --> 00:05:19,870
dalam algoritma ini.

105
00:05:19,870 --> 00:05:23,000
Algoritma ketiga ada
Dibutuhkan 13 kali lebih lama,

106
00:05:23,000 --> 00:05:27,980
13 kali jumlah sumber daya
untuk menjalankan relatif terhadap yang pertama.

107
00:05:27,980 --> 00:05:31,659
>> Jika set data kami adalah ukuran 10, yang
lebih besar, tetapi tidak harus besar,

108
00:05:31,659 --> 00:05:33,950
kita dapat melihat bahwa ada
sebenarnya sedikit perbedaan.

109
00:05:33,950 --> 00:05:36,620
Algoritma ketiga
menjadi lebih efisien.

110
00:05:36,620 --> 00:05:40,120
Ini tentang sebenarnya 40% -
atau 60% lebih efisien.

111
00:05:40,120 --> 00:05:41,580
Dibutuhkan 40% jumlah waktu.

112
00:05:41,580 --> 00:05:45,250
Hal ini dapat run-- dapat mengambil
400 unit sumberdaya

113
00:05:45,250 --> 00:05:47,570
untuk memproses data set ukuran 10.

114
00:05:47,570 --> 00:05:49,410
Sedangkan yang pertama
algoritma, sebaliknya,

115
00:05:49,410 --> 00:05:54,520
Dibutuhkan 1.000 unit sumberdaya
untuk memproses data set ukuran 10.

116
00:05:54,520 --> 00:05:57,240
Tapi lihat apa yang terjadi sebagai
nomor kami mendapatkan bahkan lebih besar.

117
00:05:57,240 --> 00:05:59,500
>> Sekarang, perbedaan
antara algoritma ini

118
00:05:59,500 --> 00:06:01,420
mulai menjadi sedikit kurang jelas.

119
00:06:01,420 --> 00:06:04,560
Dan fakta bahwa ada
rendah-order terms-- atau lebih tepatnya,

120
00:06:04,560 --> 00:06:09,390
berdamai dengan exponents-- rendah
mulai menjadi tidak relevan.

121
00:06:09,390 --> 00:06:12,290
Jika satu set data ukuran
1.000 dan algoritma pertama

122
00:06:12,290 --> 00:06:14,170
berjalan dalam satu miliar langkah.

123
00:06:14,170 --> 00:06:17,880
Dan algoritma kedua berjalan dalam
satu miliar dan satu juta langkah.

124
00:06:17,880 --> 00:06:20,870
Dan algoritma ketiga berjalan
hanya malu dari satu miliar langkah.

125
00:06:20,870 --> 00:06:22,620
Hal ini cukup banyak satu miliar langkah.

126
00:06:22,620 --> 00:06:25,640
Istilah-istilah yang lebih rendah-order mulai
untuk menjadi benar-benar tidak relevan.

127
00:06:25,640 --> 00:06:27,390
Dan hanya untuk benar-benar
palu rumah point-- yang

128
00:06:27,390 --> 00:06:31,240
jika input data dari ukuran
million-- ketiga ini cukup banyak

129
00:06:31,240 --> 00:06:34,960
mengambil satu quintillion-- jika
matematika saya adalah langkah correct--

130
00:06:34,960 --> 00:06:37,260
untuk memproses data input
ukuran satu juta.

131
00:06:37,260 --> 00:06:38,250
Itu banyak langkah-langkah.

132
00:06:38,250 --> 00:06:42,092
Dan fakta bahwa salah satu dari mereka mungkin
mengambil beberapa 100.000, atau beberapa 100

133
00:06:42,092 --> 00:06:44,650
juta bahkan kurang ketika
kita sedang berbicara tentang angka

134
00:06:44,650 --> 00:06:46,990
bahwa big-- itu semacam tidak relevan.

135
00:06:46,990 --> 00:06:50,006
Mereka semua cenderung untuk mengambil
sekitar n potong dadu,

136
00:06:50,006 --> 00:06:52,380
dan jadi kita benar-benar akan merujuk
untuk semua algoritma ini

137
00:06:52,380 --> 00:06:59,520
sebagai pada urutan n
potong dadu atau besar-O dari n potong dadu.

138
00:06:59,520 --> 00:07:03,220
>> Berikut adalah daftar dari beberapa yang lebih
umum kelas kompleksitas komputasi

139
00:07:03,220 --> 00:07:05,820
bahwa kita akan menemukan di
algoritma, umumnya.

140
00:07:05,820 --> 00:07:07,970
Dan juga secara khusus di CS50.

141
00:07:07,970 --> 00:07:11,410
Ini dipesan dari
umumnya tercepat di atas,

142
00:07:11,410 --> 00:07:13,940
untuk umum paling lambat di bagian bawah.

143
00:07:13,940 --> 00:07:16,920
Jadi algoritma waktu yang konstan cenderung
menjadi yang tercepat, terlepas

144
00:07:16,920 --> 00:07:19,110
dari ukuran
masukan data yang lulus dalam.

145
00:07:19,110 --> 00:07:23,760
Mereka selalu mengambil satu operasi atau
satu unit sumber daya untuk menangani.

146
00:07:23,760 --> 00:07:25,730
Mungkin 2, itu mungkin
menjadi 3, mungkin 4.

147
00:07:25,730 --> 00:07:26,910
Tapi itu sejumlah konstan.

148
00:07:26,910 --> 00:07:28,400
Itu tidak bervariasi.

149
00:07:28,400 --> 00:07:31,390
>> Algoritma waktu logaritmik
yang sedikit lebih baik.

150
00:07:31,390 --> 00:07:33,950
Dan contoh yang benar-benar baik
algoritma waktu logaritmik

151
00:07:33,950 --> 00:07:37,420
Anda sudah pasti melihat sekarang adalah
merobek dari buku telepon

152
00:07:37,420 --> 00:07:39,480
untuk menemukan Mike Smith dalam buku telepon.

153
00:07:39,480 --> 00:07:40,980
Kami memotong masalah di setengah.

154
00:07:40,980 --> 00:07:43,580
Dan sehingga n akan lebih besar
dan lebih besar dan larger--

155
00:07:43,580 --> 00:07:47,290
pada kenyataannya, setiap kali Anda dua kali lipat
n, hanya membutuhkan satu langkah lagi.

156
00:07:47,290 --> 00:07:49,770
Jadi itu jauh lebih baik
dari, katakanlah, waktu linier.

157
00:07:49,770 --> 00:07:53,030
Yang jika Anda dua kali lipat n, itu
mengambil dua kali lipat jumlah langkah.

158
00:07:53,030 --> 00:07:55,980
Jika Anda tiga kali lipat n, dibutuhkan
tiga kali lipat jumlah langkah.

159
00:07:55,980 --> 00:07:58,580
Salah satu langkah per unit.

160
00:07:58,580 --> 00:08:01,790
>> Maka hal-hal mendapatkan sedikit more--
sedikit kurang bagus dari sana.

161
00:08:01,790 --> 00:08:06,622
Anda punya waktu berirama linier, kadang-kadang
disebut log waktu linier atau hanya n log n.

162
00:08:06,622 --> 00:08:08,330
Dan kita akan sebuah contoh
dari suatu algoritma yang

163
00:08:08,330 --> 00:08:13,370
berjalan di n log n, yang masih lebih baik
dari kuadrat time-- n kuadrat.

164
00:08:13,370 --> 00:08:17,320
Atau waktu polinomial, n dua
sejumlah besar dari dua.

165
00:08:17,320 --> 00:08:20,810
Atau waktu eksponensial, yang
bahkan worse-- C untuk n.

166
00:08:20,810 --> 00:08:24,670
Jadi beberapa nomor konstan diangkat ke
kekuatan ukuran input.

167
00:08:24,670 --> 00:08:28,990
Jadi jika ada 1,000-- jika
masukan data dari ukuran 1.000,

168
00:08:28,990 --> 00:08:31,310
itu akan mengambil C dengan daya 1000.

169
00:08:31,310 --> 00:08:33,559
Ini jauh lebih buruk dari waktu polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Waktu faktorial bahkan lebih buruk.

171
00:08:35,030 --> 00:08:37,760
Dan pada kenyataannya, ada benar-benar melakukan
ada algoritma waktu yang tak terbatas,

172
00:08:37,760 --> 00:08:43,740
seperti, disebut sort-- bodoh yang
pekerjaan adalah untuk secara acak mengocok array

173
00:08:43,740 --> 00:08:45,490
dan kemudian memeriksa untuk melihat
apakah itu diurutkan.

174
00:08:45,490 --> 00:08:47,589
Dan jika tidak, secara acak
mengocok array lagi

175
00:08:47,589 --> 00:08:49,130
dan memeriksa untuk melihat apakah itu diurutkan.

176
00:08:49,130 --> 00:08:51,671
Dan karena Anda mungkin dapat imagine--
Anda bisa membayangkan situasi

177
00:08:51,671 --> 00:08:55,200
di mana dalam kasus terburuk, akan yang
pernah benar-benar mulai dengan array.

178
00:08:55,200 --> 00:08:57,150
Algoritma yang akan menjalankan selamanya.

179
00:08:57,150 --> 00:08:59,349
Dan sehingga akan menjadi
algoritma waktu yang tak terbatas.

180
00:08:59,349 --> 00:09:01,890
Mudah-mudahan Anda tidak akan menulis
setiap saat faktorial atau tak terbatas

181
00:09:01,890 --> 00:09:04,510
algoritma di CS50.

182
00:09:04,510 --> 00:09:09,150
>> Jadi, mari kita sedikit lebih
Penampilan beton di beberapa sederhana

183
00:09:09,150 --> 00:09:11,154
kelas kompleksitas komputasi.

184
00:09:11,154 --> 00:09:13,070
Jadi kita memiliki example--
atau dua contoh di sini-

185
00:09:13,070 --> 00:09:15,590
algoritma waktu yang konstan,
yang selalu mengambil

186
00:09:15,590 --> 00:09:17,980
satu operasi dalam kasus terburuk.

187
00:09:17,980 --> 00:09:20,050
Jadi example-- pertama
kita memiliki fungsi

188
00:09:20,050 --> 00:09:23,952
disebut 4 untuk Anda, yang
mengambil array ukuran 1.000.

189
00:09:23,952 --> 00:09:25,660
Tapi kemudian ternyata
tidak benar-benar melihat

190
00:09:25,660 --> 00:09:29,000
di itu-- tidak benar-benar peduli apa
di dalamnya, array itu.

191
00:09:29,000 --> 00:09:30,820
Selalu hanya mengembalikan empat.

192
00:09:30,820 --> 00:09:32,940
Jadi, algoritma yang,
meskipun fakta bahwa itu

193
00:09:32,940 --> 00:09:35,840
Dibutuhkan 1.000 elemen tidak
melakukan apa-apa dengan mereka.

194
00:09:35,840 --> 00:09:36,590
Hanya mengembalikan empat.

195
00:09:36,590 --> 00:09:38,240
Itu selalu satu langkah.

196
00:09:38,240 --> 00:09:41,600
>> Bahkan, tambahkan 2 nums-- yang
kita lihat sebelumnya seperti baik

197
00:09:41,600 --> 00:09:43,680
hanya memproses dua bilangan bulat.

198
00:09:43,680 --> 00:09:44,692
Ini bukan satu langkah.

199
00:09:44,692 --> 00:09:45,900
Ini sebenarnya beberapa langkah.

200
00:09:45,900 --> 00:09:50,780
Anda mendapatkan, Anda mendapatkan b, Anda menambahkannya
bersama-sama, dan Anda output hasil.

201
00:09:50,780 --> 00:09:53,270
Jadi 84 langkah.

202
00:09:53,270 --> 00:09:55,510
Tapi selalu konstan,
terlepas dari atau b.

203
00:09:55,510 --> 00:09:59,240
Anda harus mendapatkan, dapatkan b, tambahkan
mereka bersama-sama, output hasil.

204
00:09:59,240 --> 00:10:02,900
Jadi itulah algoritma waktu yang konstan.

205
00:10:02,900 --> 00:10:05,170
>> Berikut ini adalah contoh dari
linear waktu algorithm--

206
00:10:05,170 --> 00:10:08,740
algoritma yang gets-- yang mengambil
satu langkah tambahan, mungkin,

207
00:10:08,740 --> 00:10:10,740
sebagai masukan Anda tumbuh dengan 1.

208
00:10:10,740 --> 00:10:14,190
Jadi, katakanlah kita sedang mencari
jumlah 5 dalam sebuah array.

209
00:10:14,190 --> 00:10:16,774
Anda mungkin memiliki situasi di mana
Anda dapat menemukannya cukup awal.

210
00:10:16,774 --> 00:10:18,606
Tapi Anda juga bisa memiliki
situasi di mana

211
00:10:18,606 --> 00:10:20,450
mungkin elemen terakhir dari array.

212
00:10:20,450 --> 00:10:23,780
Dalam berbagai ukuran 5, jika
kami sedang mencari nomor 5.

213
00:10:23,780 --> 00:10:25,930
Ini akan mengambil 5 langkah.

214
00:10:25,930 --> 00:10:29,180
Dan pada kenyataannya, bayangkan bahwa ada
tidak 5 di mana saja di array ini.

215
00:10:29,180 --> 00:10:32,820
Kami masih benar-benar harus melihat
setiap elemen dari array

216
00:10:32,820 --> 00:10:35,550
untuk menentukan
apakah 5 ada.

217
00:10:35,550 --> 00:10:39,840
>> Jadi dalam kasus terburuk, yaitu bahwa
Unsur adalah terakhir dalam array

218
00:10:39,840 --> 00:10:41,700
atau tidak ada sama sekali.

219
00:10:41,700 --> 00:10:44,690
Kami masih harus melihat
semua elemen n.

220
00:10:44,690 --> 00:10:47,120
Dan algoritma ini
berjalan dalam waktu linier.

221
00:10:47,120 --> 00:10:50,340
Anda dapat mengkonfirmasi bahwa dengan
ekstrapolasi sedikit dengan mengatakan,

222
00:10:50,340 --> 00:10:53,080
jika kita memiliki array 6-elemen dan
kita cari nomor 5,

223
00:10:53,080 --> 00:10:54,890
mungkin butuh 6 langkah.

224
00:10:54,890 --> 00:10:57,620
Jika kita memiliki array 7-elemen dan
kami sedang mencari nomor 5.

225
00:10:57,620 --> 00:10:59,160
Mungkin butuh 7 langkah.

226
00:10:59,160 --> 00:11:02,920
Seperti kita menambahkan satu elemen lebih untuk kami
array, dibutuhkan satu langkah lagi.

227
00:11:02,920 --> 00:11:06,750
Itu algoritma linear
dalam kasus terburuk.

228
00:11:06,750 --> 00:11:08,270
>> Pasangan pertanyaan cepat untuk Anda.

229
00:11:08,270 --> 00:11:11,170
Apa runtime-- apa
terburuk-kasus runtime

230
00:11:11,170 --> 00:11:13,700
dari potongan tertentu dari kode?

231
00:11:13,700 --> 00:11:17,420
Jadi saya memiliki 4 lingkaran di sini yang berjalan
dari j sama dengan 0, semua jalan sampai ke m.

232
00:11:17,420 --> 00:11:21,980
Dan apa yang saya lihat di sini, adalah bahwa
tubuh loop berjalan dalam waktu yang konstan.

233
00:11:21,980 --> 00:11:24,730
Jadi menggunakan terminologi yang
kita sudah bicara about-- apa

234
00:11:24,730 --> 00:11:29,390
akan menjadi kasus terburuk
runtime dari algoritma ini?

235
00:11:29,390 --> 00:11:31,050
Mengambil kedua.

236
00:11:31,050 --> 00:11:34,270
Bagian dalam loop
berjalan dalam waktu yang konstan.

237
00:11:34,270 --> 00:11:37,510
Dan bagian luar dari
loop akan dijalankan m kali.

238
00:11:37,510 --> 00:11:40,260
Jadi apa runtime terburuk di sini?

239
00:11:40,260 --> 00:11:43,210
Apakah Anda menebak besar-O dari m?

240
00:11:43,210 --> 00:11:44,686
Anda akan benar.

241
00:11:44,686 --> 00:11:46,230
>> Bagaimana tentang satu sama lain?

242
00:11:46,230 --> 00:11:48,590
Kali ini kami memiliki
lingkaran dalam lingkaran.

243
00:11:48,590 --> 00:11:50,905
Kami memiliki loop luar
yang berjalan dari nol sampai p.

244
00:11:50,905 --> 00:11:54,630
Dan kami memiliki loop batin yang berjalan
dari nol sampai p, dan di dalam itu,

245
00:11:54,630 --> 00:11:57,890
Saya menyatakan bahwa tubuh yang
loop berjalan dalam waktu yang konstan.

246
00:11:57,890 --> 00:12:02,330
Jadi apa runtime terburuk
dari potongan tertentu dari kode?

247
00:12:02,330 --> 00:12:06,140
Nah, sekali lagi, kita memiliki
lingkaran luar yang berjalan p kali.

248
00:12:06,140 --> 00:12:09,660
Dan setiap iterasi time--
loop itu, bukan.

249
00:12:09,660 --> 00:12:13,170
Kami memiliki loop batin
yang juga menjalankan p kali.

250
00:12:13,170 --> 00:12:16,900
Dan kemudian di dalam itu, ada
konstan time-- potongan kecil di sana.

251
00:12:16,900 --> 00:12:19,890
>> Jadi jika kita memiliki lingkaran luar yang
menjalankan p kali dalam yang

252
00:12:19,890 --> 00:12:22,880
loop batin yang
menjalankan p times-- apa

253
00:12:22,880 --> 00:12:26,480
terburuk-kasus runtime
dari potongan kode ini?

254
00:12:26,480 --> 00:12:30,730
Apakah Anda menebak besar-O dari p kuadrat?

255
00:12:30,730 --> 00:12:31,690
>> Aku Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Ini adalah CS50.

257
00:12:33,880 --> 00:12:35,622