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

2
00:00:05,830 --> 00:00:07,910
>> Dritt kollox, hekk, kumplessità komputazzjoni.

3
00:00:07,910 --> 00:00:10,430
Just daqsxejn ta 'twissija
qabel we adsa wisq far--

4
00:00:10,430 --> 00:00:13,070
dan ser probabbilment tkun fost
l-affarijiet aktar matematika heavy

5
00:00:13,070 --> 00:00:14,200
nitkellmu dwar fil CS50.

6
00:00:14,200 --> 00:00:16,950
Nisperaw li mhux se jkun wisq kbira
u aħna ser nippruvaw u niggwidawk

7
00:00:16,950 --> 00:00:19,200
permezz tal-proċess, iżda
biss daqsxejn ta 'twissija leali.

8
00:00:19,200 --> 00:00:21,282
Hemm ftit
tal-matematika involuti hawnhekk.

9
00:00:21,282 --> 00:00:23,990
Kull dritt, hekk sabiex
użu tar-riżorsi komputazzjonali tagħna

10
00:00:23,990 --> 00:00:28,170
fil-world-- reali huwa tassew
importanti li wieħed jifhem algoritmi

11
00:00:28,170 --> 00:00:30,750
u kif huma jipproċessaw data.

12
00:00:30,750 --> 00:00:32,810
Jekk għandna verament
algoritmu effiċjenti, aħna

13
00:00:32,810 --> 00:00:36,292
jistgħu jimminimizzaw l-ammont ta 'riżorsi
għandna disponibbli biex jittrattaw dan.

14
00:00:36,292 --> 00:00:38,750
Jekk għandna algoritmu li
se jieħu ħafna xogħol

15
00:00:38,750 --> 00:00:41,210
għall-proċess verament
sett kbir ta 'data, huwa

16
00:00:41,210 --> 00:00:44,030
se jeħtieġu aktar
u aktar riżorsi, li

17
00:00:44,030 --> 00:00:47,980
huwa flus, RAM, dak kollu li tip ta 'għalf.

18
00:00:47,980 --> 00:00:52,090
>> Allura, tkun tista 'tanalizza l
algoritmu tuża dan is-sett għodda,

19
00:00:52,090 --> 00:00:56,110
bażikament, jitlob lill-question--
kif ma din l-iskala algoritmu

20
00:00:56,110 --> 00:00:59,020
kif aħna tarmi data aktar u aktar fuq dan?

21
00:00:59,020 --> 00:01:02,220
Fil CS50, l-ammont ta 'data nkunu
ħidma ma huwa pjuttost żgħir.

22
00:01:02,220 --> 00:01:05,140
Ġeneralment, il-programmi tagħna ser
jiddekorri fit-tieni jew less--

23
00:01:05,140 --> 00:01:07,830
probabbilment ħafna inqas
speċjalment kmieni fuq.

24
00:01:07,830 --> 00:01:12,250
>> Imma naħseb dwar kumpannija li jittratta
ma 'mijiet ta' miljuni ta 'klijenti.

25
00:01:12,250 --> 00:01:14,970
U jeħtieġ li jipproċessaw
li d-data tal-klijent.

26
00:01:14,970 --> 00:01:18,260
Billi n-numru ta 'klijenti li
jkollhom gets akbar u akbar,

27
00:01:18,260 --> 00:01:21,230
li għaddej biex bżonn
aktar u aktar riżorsi.

28
00:01:21,230 --> 00:01:22,926
Kemm aktar riżorsi?

29
00:01:22,926 --> 00:01:25,050
Ukoll, li jiddependi fuq kif
aħna tanalizza l-algoritmu,

30
00:01:25,050 --> 00:01:28,097
jużaw l-għodod f'dan toolbox.

31
00:01:28,097 --> 00:01:31,180
Meta nitkellmu dwar il-kumplessità tal
l algorithm-- li xi kultant tkun taf

32
00:01:31,180 --> 00:01:34,040
tismagħha imsejħa ħin
kumplessità jew spazju kumplessità

33
00:01:34,040 --> 00:01:36,190
imma aħna qed biss jmorru
sejħa complexity--

34
00:01:36,190 --> 00:01:38,770
aħna qed ġeneralment jitkellem dwar
l-agħar xenarju.

35
00:01:38,770 --> 00:01:42,640
Minħabba l-pile assoluta agħar ta '
data li nistgħu jkunu jitfg lejn dan,

36
00:01:42,640 --> 00:01:46,440
kif dan algoritmu se
jipproċessaw jew tittratta dik id-data?

37
00:01:46,440 --> 00:01:51,450
Aħna ġeneralment sejħa tal-agħar każ
runtime ta 'algoriżmu big-O.

38
00:01:51,450 --> 00:01:56,770
Allura algoriżmu jista 'jingħad li
run fil O ta 'n jew O ta' n kwadrat.

39
00:01:56,770 --> 00:01:59,110
U aktar dwar dak
dawk jfissru fit-tieni.

40
00:01:59,110 --> 00:02:01,620
>> Kultant, għalkemm, nagħmlu kura
dwar l aħjar xenarju possibbli.

41
00:02:01,620 --> 00:02:05,400
Jekk id-data huwa kollox ridna
li jkun u kien assolutament perfetta

42
00:02:05,400 --> 00:02:09,630
u konna tibgħat din perfetta
sett ta 'data permezz algoritmu tagħna.

43
00:02:09,630 --> 00:02:11,470
Kif ikun jidher jimmaniġġjaw f'dik is-sitwazzjoni?

44
00:02:11,470 --> 00:02:15,050
Aħna kultant jirreferu għal dak li
big-Omega, hekk b'kuntrast ma big-O,

45
00:02:15,050 --> 00:02:16,530
għandna big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega għall-aħjar xenarju possibbli.

47
00:02:18,880 --> 00:02:21,319
Big-O għall-agħar xenarju.

48
00:02:21,319 --> 00:02:23,860
Ġeneralment, meta nitkellmu dwar
il-kumplessità ta 'algoriżmu,

49
00:02:23,860 --> 00:02:26,370
aħna qed jitkellem dwar il-
agħar xenarju.

50
00:02:26,370 --> 00:02:28,100
Sabiex iżommu dan f'moħħhom.

51
00:02:28,100 --> 00:02:31,510
>> U f'din il-klassi, aħna qed tmur ġeneralment
li jħallu l-analiżi rigoruża aside.

52
00:02:31,510 --> 00:02:35,350
Hemm xjenzi u l-oqsma
iddedikat għal dan it-tip ta 'għalf.

53
00:02:35,350 --> 00:02:37,610
Meta nitkellmu dwar ir-raġunament
permezz ta 'algoritmi,

54
00:02:37,610 --> 00:02:41,822
li aħna ser nagħmlu biċċa-by-biċċa għal ħafna
algoritmi nitkellmu dwar fil-klassi.

55
00:02:41,822 --> 00:02:44,780
Aħna verament biss jitkellem dwar
raġunament permezz ta 'dan ma' sens komun,

56
00:02:44,780 --> 00:02:47,070
mhux mal formuli, jew provi,
jew xi ħaġa bħal dik.

57
00:02:47,070 --> 00:02:51,600
Għalhekk tinkwetax, Aħna mhux se tkun
dawran għal ġol klassi matematika big.

58
00:02:51,600 --> 00:02:55,920
>> So I qal we care about kumplessità
minħabba li tqajjem il-mistoqsija, kif

59
00:02:55,920 --> 00:03:00,160
do algoritmi tagħna jimmaniġġjaw akbar u
settijiet ta 'data kbar jintefgħu fil minnhom.

60
00:03:00,160 --> 00:03:01,960
Ukoll, dak li huwa sett ta 'data?

61
00:03:01,960 --> 00:03:03,910
What did I jfisser meta I qal li?

62
00:03:03,910 --> 00:03:07,600
Dan ifisser kwalunkwe jagħmilhom l-aktar
sens kuntest, li tkun onest.

63
00:03:07,600 --> 00:03:11,160
Jekk għandna algoritmu, il
Proċessi Strings-- aħna qed probabbilment

64
00:03:11,160 --> 00:03:13,440
jitkellem dwar id-daqs tas-sekwenza.

65
00:03:13,440 --> 00:03:15,190
Dik hija d-data set--
id-daqs, in-numru

66
00:03:15,190 --> 00:03:17,050
ta 'karattri li jiffurmaw il-sekwenza.

67
00:03:17,050 --> 00:03:20,090
Jekk aħna qed jitkellem dwar
algoritmu li l-proċessi fajls,

68
00:03:20,090 --> 00:03:23,930
nistgħu jkun jitkellem dwar kif
ħafna kilobytes jinkludu dan il-fajl.

69
00:03:23,930 --> 00:03:25,710
U dak l-sett tad-dejta.

70
00:03:25,710 --> 00:03:28,870
Jekk aħna qed jitkellem dwar algoritmu
li mankijiet arrays b'mod aktar ġenerali,

71
00:03:28,870 --> 00:03:31,510
bħal algoritmi issortjar
jew tiftix algoritmi,

72
00:03:31,510 --> 00:03:36,690
aħna qed probabbilment jitkellem dwar in-numru
ta 'elementi li jinkludu firxa.

73
00:03:36,690 --> 00:03:39,272
>> Issa, nistgħu jkejjel
algorithm-- b'mod partikolari,

74
00:03:39,272 --> 00:03:40,980
meta ngħid li nistgħu
ikejlu algoritmu, I

75
00:03:40,980 --> 00:03:43,840
tfisser nistgħu miżura kif
ħafna riżorsi li tieħu up.

76
00:03:43,840 --> 00:03:48,990
Jekk dawk ir-riżorsi huma, kemm
bytes ta RAM-- jew megabytes RAM

77
00:03:48,990 --> 00:03:49,790
hija tuża.

78
00:03:49,790 --> 00:03:52,320
Jew kemm ħin li tieħu biex imexxu.

79
00:03:52,320 --> 00:03:56,200
U nistgħu sejħa dan
ikejlu, b'mod arbitrarju, f tar n.

80
00:03:56,200 --> 00:03:59,420
Fejn n huwa n-numru ta '
elementi fis-sett tad-dejta.

81
00:03:59,420 --> 00:04:02,640
U f 'n huwa kemm somethings.

82
00:04:02,640 --> 00:04:07,530
Kemm unitajiet ta 'riżorsi ma
jirrikjedi li jipproċessaw dik id-data.

83
00:04:07,530 --> 00:04:10,030
>> Issa, aħna fil-fatt ma 'kura
dwar dak f 'n huwa eżattament.

84
00:04:10,030 --> 00:04:13,700
Fil-fatt, aħna rari ħafna will--
ċertament se qatt f'dan I class--

85
00:04:13,700 --> 00:04:18,709
adsa fis xi verament fil-fond
analiżi ta 'dak li f' n huwa.

86
00:04:18,709 --> 00:04:23,510
Aħna biss ser jitkellmu dwar dak f ta
n huwa ta 'madwar jew dak li għandha tendenza li.

87
00:04:23,510 --> 00:04:27,600
U t-tendenza ta 'algoriżmu huwa
dettata minn terminu tagħha ordni ogħla.

88
00:04:27,600 --> 00:04:29,440
U nistgħu naraw dak I
tfisser li billi tieħu

89
00:04:29,440 --> 00:04:31,910
ħarsa lejn eżempju aktar konkreta.

90
00:04:31,910 --> 00:04:34,620
>> Mela ejja ngħidu li għandna
tliet algoritmi differenti.

91
00:04:34,620 --> 00:04:39,350
L-ewwel wieħed minnhom jieħu n
kubiku, xi unitajiet ta 'riżorsi

92
00:04:39,350 --> 00:04:42,880
biex jipproċessaw sett ta 'dejta ta' daqs n.

93
00:04:42,880 --> 00:04:47,000
Għandna tieni algoritmu li jieħu
n kubiku flimkien ma 'riżorsi n kwadri

94
00:04:47,000 --> 00:04:49,350
biex jipproċessaw sett ta 'dejta ta' daqs n.

95
00:04:49,350 --> 00:04:52,030
U aħna għandna terz
algoritmu li tmur in-- li

96
00:04:52,030 --> 00:04:58,300
jieħu n 8N minus kubiku kwadrat
miżjuda b'20 n unitajiet ta 'riżorsi

97
00:04:58,300 --> 00:05:02,370
li tipproċessa algoritmu
bl stabbiliti mid-daqs n data.

98
00:05:02,370 --> 00:05:05,594
>> Issa darb'oħra, aħna verament ma jkunux sejrin
li jsibu rwieħhom dan il-livell ta 'dettall.

99
00:05:05,594 --> 00:05:08,260
Ninsab verament biss għandhom dawn il-up
hawn bħala eżempju ta 'punt

100
00:05:08,260 --> 00:05:10,176
li jien ser tkun
tagħmel fit-tieni, li

101
00:05:10,176 --> 00:05:12,980
hija li aħna biss verament kura
dwar it-tendenza ta 'affarijiet

102
00:05:12,980 --> 00:05:14,870
bħala l-settijiet ta 'data tikber.

103
00:05:14,870 --> 00:05:18,220
Mela jekk is-sett tad-data huwa żgħir, hemm
attwalment differenza pretty big

104
00:05:18,220 --> 00:05:19,870
f'dawn algoritmi.

105
00:05:19,870 --> 00:05:23,000
It-tielet algoritmu hemm
jieħu 13-il darba aktar,

106
00:05:23,000 --> 00:05:27,980
13-il darba l-ammont ta 'riżorsi
biex imexxu relattiv għall-ewwel waħda.

107
00:05:27,980 --> 00:05:31,659
>> Jekk sett tad-dejta tagħna huwa daqs 10, li
hija akbar, iżda mhux neċessarjament enormi,

108
00:05:31,659 --> 00:05:33,950
nistgħu naraw li hemm
fil-fatt daqsxejn ta 'differenza.

109
00:05:33,950 --> 00:05:36,620
It-tielet algoritmu
isir aktar effiċjenti.

110
00:05:36,620 --> 00:05:40,120
Huwa dwar attwalment 40% -
jew 60% aktar effiċjenti.

111
00:05:40,120 --> 00:05:41,580
Huwa jieħu 40% tal-ammont ta 'ħin.

112
00:05:41,580 --> 00:05:45,250
Hija tista 'run-- tkun tista' tieħu
400 unità ta 'riżorsi

113
00:05:45,250 --> 00:05:47,570
biex jipproċessaw sett ta 'dejta ta' daqs 10.

114
00:05:47,570 --> 00:05:49,410
Billi l-ewwel
algoritmu, għall-kuntrarju,

115
00:05:49,410 --> 00:05:54,520
jieħu 1,000 unità ta 'riżorsi
biex jipproċessaw sett ta 'dejta ta' daqs 10.

116
00:05:54,520 --> 00:05:57,240
Iżda tfittex dak li jiġri bħala
numri tagħna jiksbu saħansitra akbar.

117
00:05:57,240 --> 00:05:59,500
>> Issa, id-differenza
bejn dawn algoritmi

118
00:05:59,500 --> 00:06:01,420
jibdew isiru ftit inqas apparenti.

119
00:06:01,420 --> 00:06:04,560
U l-fatt li hemm
-ordni aktar baxxa terms-- jew minflok,

120
00:06:04,560 --> 00:06:09,390
termini ma exponents-- aktar baxx
jibdew isiru irrilevanti.

121
00:06:09,390 --> 00:06:12,290
Jekk sett ta 'dejta hija ta' daqs
1000 u l-ewwel algoritmu

122
00:06:12,290 --> 00:06:14,170
jibda fl biljun passi.

123
00:06:14,170 --> 00:06:17,880
U t-tieni algoritmu runs fil
biljun u miljun passi.

124
00:06:17,880 --> 00:06:20,870
U t-tielet algoritmu runs
fi ftit jitmeżmżu ta biljun passi.

125
00:06:20,870 --> 00:06:22,620
Huwa pretty ħafna biljun passi.

126
00:06:22,620 --> 00:06:25,640
Dawk it-termini ordni aktar baxxa tibda
biex isiru verament irrilevanti.

127
00:06:25,640 --> 00:06:27,390
U biss li verament
martell dar il point--

128
00:06:27,390 --> 00:06:31,240
jekk id-data mdaħħla tkun ta 'daqs ta'
million-- kollha pretty ħafna tlieta minn dawn

129
00:06:31,240 --> 00:06:34,960
jieħu quintillion-- wieħed jekk
matematika tiegħi huwa passi correct--

130
00:06:34,960 --> 00:06:37,260
li jipproċessaw data mdaħħla
ta 'daqs miljun.

131
00:06:37,260 --> 00:06:38,250
Li l-lott ta 'passi.

132
00:06:38,250 --> 00:06:42,092
U l-fatt li wieħed minnhom jista
jieħu ftit 100,000, jew koppja 100

133
00:06:42,092 --> 00:06:44,650
miljun, anki jekk inqas meta
aħna qed jitkellem dwar numru

134
00:06:44,650 --> 00:06:46,990
li big-- huwa tip ta 'irrilevanti.

135
00:06:46,990 --> 00:06:50,006
Huma kollha għandhom tendenza li jieħdu
madwar kubiku n,

136
00:06:50,006 --> 00:06:52,380
u hekk aħna fil-fatt tirreferi
kollha ta 'dawn algoritmi

137
00:06:52,380 --> 00:06:59,520
bħala li qegħdin fuq l-ordni ta 'n
kubiku jew big-O tal kubiku n.

138
00:06:59,520 --> 00:07:03,220
>> Hawnhekk hawn lista ta 'xi wħud mill-aktar
klassijiet komuni kumplessità komputazzjoni

139
00:07:03,220 --> 00:07:05,820
li aħna ser tiltaqa fil
algoritmi, ġeneralment.

140
00:07:05,820 --> 00:07:07,970
U wkoll speċifikament fil CS50.

141
00:07:07,970 --> 00:07:11,410
Dawn huma ordnati minn
ġeneralment aktar mgħaġġla fil-quċċata,

142
00:07:11,410 --> 00:07:13,940
li ġeneralment iżgħar rata fil-qiegħ.

143
00:07:13,940 --> 00:07:16,920
Allura algoritmi ħin kostanti tendenza
li jkun l-iktar mgħaġġla, irrispettivament

144
00:07:16,920 --> 00:07:19,110
tad-daqs tal-
input tad-data inti tgħaddi fil.

145
00:07:19,110 --> 00:07:23,760
Huma dejjem jieħdu operazzjoni waħda jew
unità waħda ta 'riżorsi biex jittrattaw.

146
00:07:23,760 --> 00:07:25,730
Jista 'jkun 2, dan jista' jkun
jkun ta '3, jista' jkun 4.

147
00:07:25,730 --> 00:07:26,910
Imma hija numru kostanti.

148
00:07:26,910 --> 00:07:28,400
Hija ma jvarjax.

149
00:07:28,400 --> 00:07:31,390
>> Algoritmi ħin logaritmika
huma ftit aħjar.

150
00:07:31,390 --> 00:07:33,950
U eżempju tassew tajjeb ta '
algoritmu żmien logaritmiku

151
00:07:33,950 --> 00:07:37,420
inti ħadthom żgur tidher minn issa huwa l-
dmugħ apparti tal-ktieb tat-telefon

152
00:07:37,420 --> 00:07:39,480
biex isibu Mike Smith fil-ktieb tat-telefon.

153
00:07:39,480 --> 00:07:40,980
Aħna maqtugħin-problema min-nofs.

154
00:07:40,980 --> 00:07:43,580
U hekk kif n gets akbar
u akbar u larger--

155
00:07:43,580 --> 00:07:47,290
fil-fatt, kull darba li inti doppju
n, hija tieħu biss pass aktar.

156
00:07:47,290 --> 00:07:49,770
Allura dak ħafna aħjar
minn, ngħidu aħna, il-ħin lineari.

157
00:07:49,770 --> 00:07:53,030
Liema hija jekk inti doppja n, huwa
jieħu doppju tal-għadd ta 'passi.

158
00:07:53,030 --> 00:07:55,980
Jekk inti triple n, hija tieħu
triplu l-għadd ta 'passi.

159
00:07:55,980 --> 00:07:58,580
Pass wieħed għal kull unità.

160
00:07:58,580 --> 00:08:01,790
>> Imbagħad l-affarijiet jiksbu ftit more--
ftit inqas kbir minn hemm.

161
00:08:01,790 --> 00:08:06,622
Ikollok ħin rhythmic lineari, xi kultant
imsejħa log ħin lineari jew biss n log n.

162
00:08:06,622 --> 00:08:08,330
U aħna ser eżempju
ta 'algoriżmu li

163
00:08:08,330 --> 00:08:13,370
runs fil n log n, li għadu aħjar
minn time-- n kwadratiċi kwadrat.

164
00:08:13,370 --> 00:08:17,320
Jew il-ħin polynomial, n tnejn
kwalunkwe numru akbar minn tnejn.

165
00:08:17,320 --> 00:08:20,810
Jew il-ħin esponenzjali, li
huwa saħansitra worse-- C għall-n.

166
00:08:20,810 --> 00:08:24,670
Allura xi numru kostanti jiżdied għal
il-qawwa tad-daqs tal-input.

167
00:08:24,670 --> 00:08:28,990
Mela jekk hemm 1,000-- jekk il
input tad-data hija ta 'daqs 1000,

168
00:08:28,990 --> 00:08:31,310
hija kienet ser tieħu C għall-qawwa 1000.

169
00:08:31,310 --> 00:08:33,559
Huwa ħafna agħar minn żmien polinomjali.

170
00:08:33,559 --> 00:08:35,030
>> Ħin fattorjali hija saħansitra agħar.

171
00:08:35,030 --> 00:08:37,760
U fil-fatt, hemm verament
jeżistu algoritmi ħin infinita,

172
00:08:37,760 --> 00:08:43,740
bħal, hekk imsejħa sort-- stupid li
xogħolhom huwa li saltwarjament shuffle firxa

173
00:08:43,740 --> 00:08:45,490
u mbagħad tikkontrolla biex tara
kemm jekk huwa magħżula.

174
00:08:45,490 --> 00:08:47,589
U jekk mhuwiex, każwalment
shuffle l-array mill-ġdid

175
00:08:47,589 --> 00:08:49,130
u tikkontrolla biex tara jekk huwa magħżula.

176
00:08:49,130 --> 00:08:51,671
U kif inti tista 'probabbilment imagine--
tista 'timmaġina sitwazzjoni

177
00:08:51,671 --> 00:08:55,200
fejn fil-agħar każ, li se
fatt qatt ma tibda bil-firxa.

178
00:08:55,200 --> 00:08:57,150
Din l-algorithm imur għal dejjem.

179
00:08:57,150 --> 00:08:59,349
U għalhekk li jkun
algoritmu ħin infinita.

180
00:08:59,349 --> 00:09:01,890
Nisperaw li int mhux se jkun miktub
kwalunkwe ħin fattorjali jew infinita

181
00:09:01,890 --> 00:09:04,510
algoritmi fil CS50.

182
00:09:04,510 --> 00:09:09,150
>> Allura, ejja tagħti ftit aktar
ħarsa konkreta lejn uħud sempliċi

183
00:09:09,150 --> 00:09:11,154
klassijiet kumplessità komputazzjoni.

184
00:09:11,154 --> 00:09:13,070
Allura għandna example--
jew żewġ eżempji here--

185
00:09:13,070 --> 00:09:15,590
ta 'algoritmi ħin kostanti,
li dejjem jieħdu

186
00:09:15,590 --> 00:09:17,980
operazzjoni waħda fl-agħar każ.

187
00:09:17,980 --> 00:09:20,050
Allura l-ewwel example--
għandna funzjoni

188
00:09:20,050 --> 00:09:23,952
sejjaħ 4 għalik, liema
jieħu firxa ta 'daqs 1000.

189
00:09:23,952 --> 00:09:25,660
Imma mbagħad apparentement
ma fil-fatt tfittex

190
00:09:25,660 --> 00:09:29,000
fil it-- ma verament kura x'hemm
ġewwa ta 'dan, ta' dak array.

191
00:09:29,000 --> 00:09:30,820
Dejjem jirritorna erbgħa.

192
00:09:30,820 --> 00:09:32,940
Allura, din l-algorithm,
minkejja l-fatt li

193
00:09:32,940 --> 00:09:35,840
jieħu 1,000 elementi ma
tagħmel xejn magħhom.

194
00:09:35,840 --> 00:09:36,590
Jirritorna erbgħa.

195
00:09:36,590 --> 00:09:38,240
Huwa dejjem pass wieħed.

196
00:09:38,240 --> 00:09:41,600
>> Fil-fatt, żid 2 nums-- li
Rajna qabel bħala well--

197
00:09:41,600 --> 00:09:43,680
biss proċessi żewġ numri interi.

198
00:09:43,680 --> 00:09:44,692
Mhuwiex pass wieħed.

199
00:09:44,692 --> 00:09:45,900
Huwa fil-fatt passi koppja.

200
00:09:45,900 --> 00:09:50,780
Ikollok, ikollok b, inti żidhom
flimkien, u inti output r-riżultati.

201
00:09:50,780 --> 00:09:53,270
Allura huwa 84 passi.

202
00:09:53,270 --> 00:09:55,510
Imma hija dejjem kostanti,
irrispettivament ta 'jew b.

203
00:09:55,510 --> 00:09:59,240
Inti għandek tikseb, nikseb b, żid
flimkien, il-produzzjoni ir-riżultat.

204
00:09:59,240 --> 00:10:02,900
Allura li l-algoritmu żmien kostanti.

205
00:10:02,900 --> 00:10:05,170
>> Hawn eżempju ta '
algorithm-- ħin lineari

206
00:10:05,170 --> 00:10:08,740
algoritmu li gets-- li jieħu
pass addizzjonali wieħed, possibbilment,

207
00:10:08,740 --> 00:10:10,740
bħala input tiegħek tikber b'1.

208
00:10:10,740 --> 00:10:14,190
Allura, ejja ngħidu aħna qed infittxu
in-numru 5 ġewwa ta 'firxa.

209
00:10:14,190 --> 00:10:16,774
Inti jista 'jkollok sitwazzjoni fejn
inti tista 'ssib pjuttost kmieni.

210
00:10:16,774 --> 00:10:18,606
Iżda int tista 'wkoll ikollha
f'sitwazzjoni fejn

211
00:10:18,606 --> 00:10:20,450
jista 'jkun l-aħħar element tal-firxa.

212
00:10:20,450 --> 00:10:23,780
Fil-firxa ta 'daqs 5, jekk
aħna qed tfittex għan-numru 5.

213
00:10:23,780 --> 00:10:25,930
Huwa se jieħu 5 passi.

214
00:10:25,930 --> 00:10:29,180
U fil-fatt, jimmaġina li hemm
mhux 5 kullimkien f'dan array.

215
00:10:29,180 --> 00:10:32,820
Aħna xorta attwalment ikollhom ħarsa lejn
kull element wieħed ta 'l-array

216
00:10:32,820 --> 00:10:35,550
sabiex jiġi determinat
jekk 5. hemm.

217
00:10:35,550 --> 00:10:39,840
>> Allura fil-agħar każ, li huwa li
l-element huwa aħħar fil-firxa

218
00:10:39,840 --> 00:10:41,700
jew ma jeżistix għal kollox.

219
00:10:41,700 --> 00:10:44,690
Għad għandna nħarsu lejn
l-elementi kollha n.

220
00:10:44,690 --> 00:10:47,120
U hekk dan algoritmu
tmur fil-ħin lineari.

221
00:10:47,120 --> 00:10:50,340
Inti tista 'tikkonferma li minn
estrapolazzjoni ftit billi qal,

222
00:10:50,340 --> 00:10:53,080
jekk kellna firxa 6-element u
aħna kienu qed ifittxu l-numru 5,

223
00:10:53,080 --> 00:10:54,890
jista 'jieħu 6 passi.

224
00:10:54,890 --> 00:10:57,620
Jekk għandna firxa 7-element u
aħna qed tfittex għan-numru 5.

225
00:10:57,620 --> 00:10:59,160
Jista 'jieħu 7 passi.

226
00:10:59,160 --> 00:11:02,920
Kif aħna żid wieħed element aktar tagħna
firxa, hija tieħu pass aktar.

227
00:11:02,920 --> 00:11:06,750
Li l-algoritmu lineari
fl-agħar każ.

228
00:11:06,750 --> 00:11:08,270
>> Koppja mistoqsijiet malajr għalik.

229
00:11:08,270 --> 00:11:11,170
X'hemm-runtime-- x'hemm
l-agħar każ 'runtime

230
00:11:11,170 --> 00:11:13,700
ta 'dan snippet partikolari ta' kodiċi?

231
00:11:13,700 --> 00:11:17,420
So I jkollhom loop 4 hawn li timxi
minn j ugwali 0, it-triq kollha sa m.

232
00:11:17,420 --> 00:11:21,980
U dak li jien jaraw hawnhekk, huwa li l-
korp tal-linja jibda fil-ħin kostanti.

233
00:11:21,980 --> 00:11:24,730
Hekk billi tuża t-terminoloġija li
konna diġà tkellem about-- dak

234
00:11:24,730 --> 00:11:29,390
ikun il-agħar każ
runtime ta 'dan algoritmu?

235
00:11:29,390 --> 00:11:31,050
Tieħu t-tieni.

236
00:11:31,050 --> 00:11:34,270
Il-parti ta 'ġewwa tal-linja
tmur fil-ħin kostanti.

237
00:11:34,270 --> 00:11:37,510
U l-parti ta 'barra tal-
loop se jimxu ħinijiet m.

238
00:11:37,510 --> 00:11:40,260
Allura x'inhu l-agħar każ runtime hawn?

239
00:11:40,260 --> 00:11:43,210
Ridt raden big-O ta 'm?

240
00:11:43,210 --> 00:11:44,686
Youd tkun id-dritt.

241
00:11:44,686 --> 00:11:46,230
>> Kif dwar xulxin?

242
00:11:46,230 --> 00:11:48,590
Din id-darba għandna
loop ġewwa ta 'loop.

243
00:11:48,590 --> 00:11:50,905
Għandna linja ta 'barra
li tmur minn żero għal p.

244
00:11:50,905 --> 00:11:54,630
U għandna loop ġewwa li timxi
minn żero għal p, u ġewwa minn dan,

245
00:11:54,630 --> 00:11:57,890
I istat li l-korp l-
loop runs fil-ħin kostanti.

246
00:11:57,890 --> 00:12:02,330
Allura x'inhu l-agħar każ runtime
ta 'dan snippet partikolari ta' kodiċi?

247
00:12:02,330 --> 00:12:06,140
Ukoll, għal darb'oħra, għandna
loop barra li timxi żminijiet p.

248
00:12:06,140 --> 00:12:09,660
U kull iterazzjoni time--
ta 'dak loop, pjuttost.

249
00:12:09,660 --> 00:12:13,170
Għandna linja ta 'ġewwa
li timxi ukoll ħinijiet p.

250
00:12:13,170 --> 00:12:16,900
U allura ġewwa minn dan, hemm il-
snippet ftit time-- kostanti hemmhekk.

251
00:12:16,900 --> 00:12:19,890
>> Mela jekk għandna loop barra li
runs drabi p ġewwa tagħhom ikun

252
00:12:19,890 --> 00:12:22,880
loop ġewwa li
runs p times-- dak li hu

253
00:12:22,880 --> 00:12:26,480
l-agħar każ 'runtime
ta 'dan snippet ta' kodiċi?

254
00:12:26,480 --> 00:12:30,730
Ridt raden big-O ta 'p kwadrat?

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

256
00:12:31,690 --> 00:12:33,880
Dan huwa CS50.

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