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

2
00:00:05,830 --> 00:00:07,910
>> Baiklah, jadi, kerumitan pengiraan.

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

4
00:00:10,430 --> 00:00:13,070
ini mungkin akan menjadi antara
perkara yang paling matematik-berat

5
00:00:13,070 --> 00:00:14,200
kita bercakap kira-kira dalam CS50.

6
00:00:14,200 --> 00:00:16,950
Mudah-mudahan ia tidak akan menjadi terlalu besar
dan kami akan cuba dan membimbing anda

7
00:00:16,950 --> 00:00:19,200
melalui proses itu, tetapi
hanya sedikit amaran yang adil.

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

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

10
00:00:23,990 --> 00:00:28,170
dalam world-- sebenar ia 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 mempunyai benar-benar
algoritma yang cekap,

13
00:00:32,810 --> 00:00:36,292
boleh mengurangkan jumlah sumber
kita ada untuk menanganinya.

14
00:00:36,292 --> 00:00:38,750
Jika kita mempunyai algoritma yang
akan mengambil banyak kerja

15
00:00:38,750 --> 00:00:41,210
memproses benar-benar
set data yang besar, ia adalah

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

17
00:00:44,030 --> 00:00:47,980
adalah wang, RAM, semua jenis barangan.

18
00:00:47,980 --> 00:00:52,090
>> Jadi, dapat menganalisis satu
algoritma menggunakan set alat ini,

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

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

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

22
00:01:02,220 --> 00:01:05,140
Secara umumnya, program kami akan
berjalan di kedua atau less--

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

24
00:01:07,830 --> 00:01:12,250
>> Tetapi berfikir tentang sebuah syarikat yang tawaran
dengan beratus-ratus berjuta-juta pelanggan.

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

26
00:01:14,970 --> 00:01:18,260
Oleh kerana bilangan pelanggan mereka
ada mendapat lebih besar dan lebih besar,

27
00:01:18,260 --> 00:01:21,230
ia akan memerlukan
lebih dan lebih banyak sumber.

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

29
00:01:22,926 --> 00:01:25,050
Nah, itu bergantung kepada 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
Apabila kita bercakap mengenai kerumitan
algorithm-- yang yang kadang-kadang anda akan

32
00:01:31,180 --> 00:01:34,040
mendengar ia disebut sebagai masa
kerumitan atau ruang kerumitan

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

34
00:01:36,190 --> 00:01:38,770
kita secara umumnya bercakap tentang
senario kes terburuk.

35
00:01:38,770 --> 00:01:42,640
Memandangkan timbunan terburuk mutlak
data yang kita boleh membuang ia,

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 biasanya memanggil kes terburuk yang
runtime daripada algoritma besar-O.

38
00:01:51,450 --> 00:01:56,770
Jadi algoritma mungkin dikatakan
berjalan di O n atau O n kuasa dua.

39
00:01:56,770 --> 00:01:59,110
Dan lebih lanjut mengenai apa yang
yang bermakna dalam satu saat.

40
00:01:59,110 --> 00:02:01,620
>> Kadang-kadang, walaupun, kita mengambil berat
tentang senario kes terbaik.

41
00:02:01,620 --> 00:02:05,400
Jika data adalah segala-galanya yang kita mahu
ia menjadi dan ia adalah benar-benar sempurna

42
00:02:05,400 --> 00:02:09,630
dan kami telah menghantar ini sempurna
set data melalui algoritma kami.

43
00:02:09,630 --> 00:02:11,470
Bagaimana ia akan mengendalikan dalam keadaan itu?

44
00:02:11,470 --> 00:02:15,050
Kita kadang-kadang merujuk kepada bahawa sebagai
besar Omega, supaya berbeza dengan besar-O,

45
00:02:15,050 --> 00:02:16,530
kami mempunyai besar Omega.

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

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

48
00:02:21,319 --> 00:02:23,860
Secara umumnya, apabila kita bercakap mengenai
kerumitan algoritma,

49
00:02:23,860 --> 00:02:26,370
kita bercakap tentang
senario kes terburuk.

50
00:02:26,370 --> 00:02:28,100
Jadi menyimpan bahawa dalam fikiran.

51
00:02:28,100 --> 00:02:31,510
>> Dan di dalam kelas ini, kita biasanya akan
untuk meninggalkan analisis yang ketat diketepikan.

52
00:02:31,510 --> 00:02:35,350
Terdapat sains dan bidang-bidang
ditumpukan kepada jenis barangan.

53
00:02:35,350 --> 00:02:37,610
Apabila kita bercakap mengenai penaakulan
melalui algoritma,

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

55
00:02:41,822 --> 00:02:44,780
Kami benar-benar hanya bercakap tentang
pemikiran melaluinya dengan akal,

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

57
00:02:47,070 --> 00:02:51,600
Jadi jangan bimbang, Kami tidak akan
bertukar menjadi kelas matematik besar.

58
00:02:51,600 --> 00:02:55,920
>> Jadi, saya berkata kita mengambil berat tentang kerumitan
kerana bertanya soalan, bagaimana

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

60
00:03:00,160 --> 00:03:01,960
Nah, apa adalah satu set data?

61
00:03:01,960 --> 00:03:03,910
Apa yang saya maksudkan apabila saya berkata demikian?

62
00:03:03,910 --> 00:03:07,600
Ini bermakna apa sahaja yang membuat paling
rasa dalam konteks, untuk bersikap jujur.

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

64
00:03:11,160 --> 00:03:13,440
bercakap tentang saiz tali.

65
00:03:13,440 --> 00:03:15,190
Itulah data set--
saiz, bilangan

66
00:03:15,190 --> 00:03:17,050
watak-watak yang membentuk tali.

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

68
00:03:20,090 --> 00:03:23,930
kita mungkin bercakap tentang bagaimana
banyak kilobait terdiri daripada fail itu.

69
00:03:23,930 --> 00:03:25,710
Dan itu set data.

70
00:03:25,710 --> 00:03:28,870
Jika kita berbicara tentang algoritma
yang mengendalikan tatasusunan lebih umum,

71
00:03:28,870 --> 00:03:31,510
seperti menyusun algoritma
atau mencari algoritma,

72
00:03:31,510 --> 00:03:36,690
kita mungkin bercakap mengenai bilangan
unsur-unsur yang terdiri daripada pelbagai.

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

74
00:03:39,272 --> 00:03:40,980
apabila saya mengatakan kita boleh
mengukur algoritma, saya

75
00:03:40,980 --> 00:03:43,840
bermakna kita boleh mengukur berapa
banyak sumber ia mengambil masa sehingga.

76
00:03:43,840 --> 00:03:48,990
Sama ada sumber-sumber, bagaimana banyak
bait RAM-- atau megabait RAM

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

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

79
00:03:52,320 --> 00:03:56,200
Dan kita boleh memanggil ini
mengukur, sewenang-wenangnya, f n.

80
00:03:56,200 --> 00:03:59,420
Di mana n adalah bilangan
unsur-unsur dalam set data.

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

82
00:04:02,640 --> 00:04:07,530
Berapa unit sumber tidak
ia memerlukan untuk memproses data tersebut.

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

84
00:04:10,030 --> 00:04:13,700
Malah, kita jarang sekali will--
pasti ia tidak akan di I class-- ini

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

86
00:04:18,709 --> 00:04:23,510
Kami hanya akan bercakap tentang apa f daripada
n adalah lebih kurang atau apa yang ia cenderung untuk.

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

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

89
00:04:29,440 --> 00:04:31,910
yang melihat contoh yang lebih konkrit.

90
00:04:31,910 --> 00:04:34,620
>> Jadi mari kita mengatakan bahawa kita mempunyai
tiga algoritma yang berbeza.

91
00:04:34,620 --> 00:04:39,350
Pertama yang mengambil n
cubed, beberapa unit sumber

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

93
00:04:42,880 --> 00:04:47,000
Kami mempunyai algoritma kedua yang mengambil
n cubed ditambah sumber n kuasa

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

95
00:04:49,350 --> 00:04:52,030
Dan kita mempunyai satu pertiga
algoritma yang berjalan dalam- yang

96
00:04:52,030 --> 00:04:58,300
mengambil n tolak cubed 8n kuasa dua
ditambah 20 n unit sumber

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

98
00:05:02,370 --> 00:05:05,594
>> Kini sekali lagi, kita benar-benar tidak akan
untuk masuk ke tahap ini terperinci.

99
00:05:05,594 --> 00:05:08,260
Saya benar-benar hanya mempunyai ini sehingga
di sini sebagai contoh tauladan mata

100
00:05:08,260 --> 00:05:10,176
bahawa saya akan menjadi
membuat dalam satu saat, yang

101
00:05:10,176 --> 00:05:12,980
adalah bahawa kita hanya peduli
tentang kecenderungan perkara

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

103
00:05:14,870 --> 00:05:18,220
Jadi, jika set data adalah kecil, ada
sebenarnya perbezaan 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
mengambil 13 kali lebih lama,

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

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

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

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

110
00:05:36,620 --> 00:05:40,120
Ia kira-kira sebenarnya 40% -
atau 60% lebih cekap.

111
00:05:40,120 --> 00:05:41,580
Ia mengambil masa 40% jumlah masa.

112
00:05:41,580 --> 00:05:45,250
Ia boleh run-- ia boleh mengambil
400 unit sumber

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

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

115
00:05:49,410 --> 00:05:54,520
mengambil 1,000 unit sumber
untuk memproses satu set data saiz 10.

116
00:05:54,520 --> 00:05:57,240
Tetapi melihat apa yang berlaku sebagai
nombor kami mendapatkan lebih besar.

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

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

119
00:06:01,420 --> 00:06:04,560
Dan hakikat bahawa terdapat
lebih rendah pesanan terms-- atau sebaliknya,

120
00:06:04,560 --> 00:06:09,390
terma dengan exponents-- lebih rendah
mula menjadi tidak relevan.

121
00:06:09,390 --> 00:06:12,290
Jika set data adalah saiz
1000 dan algoritma pertama

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

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

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

125
00:06:20,870 --> 00:06:22,620
Ia cukup banyak satu bilion langkah.

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

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

128
00:06:27,390 --> 00:06:31,240
jika input data adalah saiz yang
million-- ketiga-tiga ini cukup banyak

129
00:06:31,240 --> 00:06:34,960
mengambil satu quintillion-- jika
matematik saya hanya beberapa langkah correct--

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

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

132
00:06:38,250 --> 00:06:42,092
Dan hakikat bahawa salah seorang daripada mereka mungkin
mengambil masa beberapa 100,000, atau pasangan 100

133
00:06:42,092 --> 00:06:44,650
juta lebih sedikit apabila
kita berbicara tentang sebilangan

134
00:06:44,650 --> 00:06:46,990
yang big-- ia adalah jenis yang tidak relevan.

135
00:06:46,990 --> 00:06:50,006
Mereka semua cenderung untuk mengambil
kira-kira n cubed,

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

137
00:06:52,380 --> 00:06:59,520
sebagai atas perintah n
cubed atau besar O-n cubed.

138
00:06:59,520 --> 00:07:03,220
>> Berikut adalah senarai beberapa yang lebih
biasa kelas kerumitan pengiraan

139
00:07:03,220 --> 00:07:05,820
yang kita akan hadapi dalam
algoritma, amnya.

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

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

142
00:07:11,410 --> 00:07:13,940
untuk secara amnya paling perlahan di bahagian bawah.

143
00:07:13,940 --> 00:07:16,920
Jadi algoritma masa yang berterusan cenderung
menjadi yang paling cepat, tidak kira

144
00:07:16,920 --> 00:07:19,110
daripada saiz
input data yang anda lulus.

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

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

147
00:07:25,730 --> 00:07:26,910
Tetapi ia adalah satu jumlah yang tetap.

148
00:07:26,910 --> 00:07:28,400
Ia tidak berbeza-beza.

149
00:07:28,400 --> 00:07:31,390
>> Algoritma masa logaritma
adalah lebih baik sedikit.

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

151
00:07:33,950 --> 00:07:37,420
anda pasti dilihat sekarang ialah
mengoyak selain buku telefon

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

153
00:07:39,480 --> 00:07:40,980
Kami memotong masalah pada separuh.

154
00:07:40,980 --> 00:07:43,580
Dan supaya n mendapat yang lebih besar
dan lebih besar dan larger--

155
00:07:43,580 --> 00:07:47,290
sebenarnya, setiap kali anda dua kali ganda
n, ia hanya mengambil satu lagi langkah.

156
00:07:47,290 --> 00:07:49,770
Jadi, itu lebih baik
daripada, katakan, masa linear.

157
00:07:49,770 --> 00:07:53,030
Iaitu jika anda menggandakan n, ia
mengambil dua kali ganda bilangan langkah.

158
00:07:53,030 --> 00:07:55,980
Jika anda tiga kali ganda n, ia mengambil masa
tiga kali ganda bilangan langkah.

159
00:07:55,980 --> 00:07:58,580
Satu langkah seunit.

160
00:07:58,580 --> 00:08:01,790
>> Kemudian perkara mendapatkan sedikit more--
sedikit kurang hebat di sana.

161
00:08:01,790 --> 00:08:06,622
Anda mempunyai masa berirama linear, kadang-kadang
dipanggil log masa linear atau hanya n log n.

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

163
00:08:08,330 --> 00:08:13,370
berjalan dalam n log n, yang masih lebih baik
daripada time-- kuadratik n kuasa dua.

164
00:08:13,370 --> 00:08:17,320
Atau masa polinomial, n dua
mana-mana nombor yang lebih besar daripada dua orang.

165
00:08:17,320 --> 00:08:20,810
Atau masa eksponen, yang
adalah lebih worse-- C hingga n.

166
00:08:20,810 --> 00:08:24,670
Jadi beberapa angka tetap dinaikkan kepada
kuasa saiz input.

167
00:08:24,670 --> 00:08:28,990
Jadi, jika ada 1,000-- jika
input data adalah saiz 1,000,

168
00:08:28,990 --> 00:08:31,310
ia akan mengambil C kepada kuasa 1000.

169
00:08:31,310 --> 00:08:33,559
Ia lebih buruk daripada masa polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Masa faktorial adalah lebih buruk lagi.

171
00:08:35,030 --> 00:08:37,760
Dan sebenarnya, ada benar-benar melakukan
wujud algoritma masa terhingga,

172
00:08:37,760 --> 00:08:43,740
seperti sort-- kerana, apa yang dipanggil bodoh yang
tugasnya adalah untuk rawak shuffle array

173
00:08:43,740 --> 00:08:45,490
dan kemudian semak untuk melihat
sama ada ia disusun.

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

175
00:08:47,589 --> 00:08:49,130
dan memeriksa untuk melihat sama ada ia disusun.

176
00:08:49,130 --> 00:08:51,671
Dan seperti yang anda mungkin boleh imagine--
anda boleh bayangkan keadaan

177
00:08:51,671 --> 00:08:55,200
di mana dalam kes terburuk, kehendak yang
pernah benar-benar bermula dengan array.

178
00:08:55,200 --> 00:08:57,150
Algoritma yang akan berlangsung selama-lamanya.

179
00:08:57,150 --> 00:08:59,349
Dan sebagainya yang akan menjadi
algoritma masa tak terhingga.

180
00:08:59,349 --> 00:09:01,890
Mudah-mudahan anda tidak akan menulis
bila-bila masa faktorial atau tak terhingga

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

182
00:09:04,510 --> 00:09:09,150
>> Jadi, mari kita mengambil lebih sedikit
rupa konkrit di beberapa lebih mudah

183
00:09:09,150 --> 00:09:11,154
kelas kerumitan pengiraan.

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

185
00:09:13,070 --> 00:09:15,590
algoritma masa yang berterusan,
yang sentiasa mengambil

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

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

188
00:09:20,050 --> 00:09:23,952
dipanggil 4 untuk anda, yang
mengambil pelbagai saiz 1,000.

189
00:09:23,952 --> 00:09:25,660
Tetapi nampaknya
sebenarnya tidak melihat

190
00:09:25,660 --> 00:09:29,000
pada kitab itu tidak benar-benar mengambil berat apa yang
di dalamnya, array itu.

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

192
00:09:30,820 --> 00:09:32,940
Jadi, algoritma yang,
walaupun pada hakikatnya ia

193
00:09:32,940 --> 00:09:35,840
mengambil 1000 unsur-unsur tidak
berbuat 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
Ia sentiasa satu langkah.

196
00:09:38,240 --> 00:09:41,600
>> Malah, tambah 2 nums-- yang
kita lihat sebelum ini sebagai well--

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

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

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

200
00:09:45,900 --> 00:09:50,780
Daftar untuk kadar terkini, anda akan mendapat b, anda menambah mereka
bersama-sama, dan anda output keputusan.

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

202
00:09:53,270 --> 00:09:55,510
Tetapi ia sentiasa berterusan,
tanpa mengira atau b.

203
00:09:55,510 --> 00:09:59,240
Anda perlu mendapatkan, mendapatkan b, tambah
mereka bersama-sama, output keputusan.

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

205
00:10:02,900 --> 00:10:05,170
>> Berikut adalah satu contoh
masa algorithm-- linear

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 input anda tumbuh dengan 1.

208
00:10:10,740 --> 00:10:14,190
Jadi, katakan kita cari
di dalam nombor 5 array.

209
00:10:14,190 --> 00:10:16,774
Anda mungkin mempunyai situasi di mana
anda boleh merasa agak awal.

210
00:10:16,774 --> 00:10:18,606
Tetapi anda juga boleh mempunyai
keadaan di mana ia

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

212
00:10:20,450 --> 00:10:23,780
Dalam pelbagai saiz 5, jika
yang kami cari nombor 5.

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

214
00:10:25,930 --> 00:10:29,180
Dan sebenarnya, bayangkan bahawa ada
tidak 5 mana-mana sahaja dalam pelbagai ini.

215
00:10:29,180 --> 00:10:32,820
Kita masih sebenarnya perlu melihat
setiap elemen tunggal array

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

217
00:10:35,550 --> 00:10:39,840
>> Jadi dalam kes terburuk, iaitu bahawa
elemen adalah yang terakhir dalam array

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

219
00:10:41,700 --> 00:10:44,690
Kita masih perlu melihat
semua n unsur-unsur.

220
00:10:44,690 --> 00:10:47,120
Dan sebagainya algoritma ini
berjalan dalam masa linear.

221
00:10:47,120 --> 00:10:50,340
Anda boleh mengesahkan dengan
menentuluar sedikit dengan berkata,

222
00:10:50,340 --> 00:10:53,080
jika kita mempunyai pelbagai 6-elemen dan
kita cari nombor 5,

223
00:10:53,080 --> 00:10:54,890
ia mungkin mengambil masa 6 langkah.

224
00:10:54,890 --> 00:10:57,620
Jika kita mempunyai pelbagai 7-unsur dan
yang kami cari nombor 5.

225
00:10:57,620 --> 00:10:59,160
Ia mungkin mengambil masa 7 langkah.

226
00:10:59,160 --> 00:11:02,920
Seperti yang kita menambah satu elemen yang lebih kepada kami
pelbagai, ia mengambil satu lagi langkah.

227
00:11:02,920 --> 00:11:06,750
Itulah algoritma yang linear
dalam kes terburuk itu.

228
00:11:06,750 --> 00:11:08,270
>> Pasangan soalan pantas untuk anda.

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

230
00:11:11,170 --> 00:11:13,700
ini coretan tertentu kod?

231
00:11:13,700 --> 00:11:17,420
Jadi saya mempunyai gelung 4 di sini yang berjalan
dari j sama dengan 0, sepanjang jalan sehingga m.

232
00:11:17,420 --> 00:11:21,980
Dan apa yang saya lihat di sini, adalah bahawa
badan gelung berjalan dalam masa yang berterusan.

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

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

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

236
00:11:31,050 --> 00:11:34,270
Bahagian dalam gelung
berjalan dalam masa yang berterusan.

237
00:11:34,270 --> 00:11:37,510
Dan yang luar daripada
gelung akan berjalan m kali.

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

239
00:11:40,260 --> 00:11:43,210
Adakah anda rasa besar O-m?

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

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

242
00:11:46,230 --> 00:11:48,590
Kali ini kita mempunyai
gelung di dalam gelung.

243
00:11:48,590 --> 00:11:50,905
Kami mempunyai gelung luar
yang berjalan dari sifar hingga h.

244
00:11:50,905 --> 00:11:54,630
Dan kita mempunyai gelung dalaman yang berjalan
dari sifar hingga p, dan di dalam itu,

245
00:11:54,630 --> 00:11:57,890
Saya menyatakan bahawa badan itu
gelung berjalan dalam masa yang berterusan.

246
00:11:57,890 --> 00:12:02,330
Jadi apa yang runtime kes terburuk
ini coretan tertentu kod?

247
00:12:02,330 --> 00:12:06,140
Nah, sekali lagi, kita mempunyai
gelung luar yang berjalan p masa.

248
00:12:06,140 --> 00:12:09,660
Dan setiap lelaran time--
gelung itu, agak.

249
00:12:09,660 --> 00:12:13,170
Kami mempunyai gelung dalaman
yang juga menjalankan p masa.

250
00:12:13,170 --> 00:12:16,900
Dan kemudian di dalam itu, ada yang
berterusan coretan sedikit time-- sana.

251
00:12:16,900 --> 00:12:19,890
>> Jadi, jika kita mempunyai gelung luar yang
berjalan p kali di dalam yang adalah

252
00:12:19,890 --> 00:12:22,880
gelung dalaman yang
berjalan p times-- apa yang

253
00:12:22,880 --> 00:12:26,480
yang terburuk runtime
coretan kod ini?

254
00:12:26,480 --> 00:12:30,730
Adakah anda rasa besar O-p kuasa dua?

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

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

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