1
00:00:00,000 --> 00:00:02,892
>> [Daqq tal-mużika]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
Doug LLOYD: Linear
tfittxija hija algoritmu aħna

4
00:00:07,180 --> 00:00:09,840
jistgħu jużaw biex isibu element fil-firxa.

5
00:00:09,840 --> 00:00:11,990
An irtirar algoritmu
huwa sett pass-pass

6
00:00:11,990 --> 00:00:15,030
ta 'struzzjonijiet għal kompletar ta' dmir.

7
00:00:15,030 --> 00:00:17,480
>> It-tfittxija lineari
algoritmu xogħlijiet kif ġej.

8
00:00:17,480 --> 00:00:22,200
Jtenni madwar l-array mix-xellug għal
dritt, tfittex għal element speċifikat.

9
00:00:22,200 --> 00:00:26,380
>> Fil pseudocode, li hija aktar
Verżjoni distillat ta 'din is-sentenza,

10
00:00:26,380 --> 00:00:29,840
jekk l-ewwel element huwa dak
inti qed tfittex, inti tista 'twaqqaf.

11
00:00:29,840 --> 00:00:33,930
Inkella, jimxu lejn l-element li jmiss u
jibqgħu għaddejjin fuq u aktar sakemm issib

12
00:00:33,930 --> 00:00:36,389
l-element, jew inti ma.

13
00:00:36,389 --> 00:00:38,680
Allura nistgħu nużaw l lineari
tfittxija algoritmu, per eżempju,

14
00:00:38,680 --> 00:00:42,330
biex isibu l-valur immirat
disa f'dan array.

15
00:00:42,330 --> 00:00:43,870
Well we tibda fil-bidu.

16
00:00:43,870 --> 00:00:45,970
Jekk huwa dak li aħna qed
tfittex, nistgħu stop.

17
00:00:45,970 --> 00:00:47,890
Mhuwiex, aħna mhux qed infittxu 11.

18
00:00:47,890 --> 00:00:50,220
Allura mod ieħor, jimxu lejn l-element li jmiss.

19
00:00:50,220 --> 00:00:51,510
>> Allura aħna nħarsu lejn 23.

20
00:00:51,510 --> 00:00:52,730
Hija ta '23 dak li aħna qed tfittex?

21
00:00:52,730 --> 00:00:55,614
Ukoll ebda, hekk aħna jimxu fuq il-li jmiss
element, u l-element li jmiss,

22
00:00:55,614 --> 00:00:57,780
u aħna jibqgħu għaddejjin permezz
dan il-proċess aktar u aktar

23
00:00:57,780 --> 00:01:01,030
u aktar, sakemm aħna art
fuq sitwazzjoni bħal din.

24
00:01:01,030 --> 00:01:03,910
>> Disa huwa dak li aħna qed tfittex,
u dan l-element ta 'l-array

25
00:01:03,910 --> 00:01:05,787
huwa, il-valur huwa huwa disgħa.

26
00:01:05,787 --> 00:01:08,120
U hekk sibna dak li aħna qed
tfittex għal, u nistgħu tieqaf.

27
00:01:08,120 --> 00:01:11,910
It-tfittxija lineari għandha
mimlija, b'suċċess.

28
00:01:11,910 --> 00:01:15,370
>> Imma xi ngħidu dwar jekk aħna qed infittxu
element li mhux fil-firxa tagħna.

29
00:01:15,370 --> 00:01:17,040
Does tfittxija lineari għadhom jaħdmu?

30
00:01:17,040 --> 00:01:17,540
Well żgur.

31
00:01:17,540 --> 00:01:19,947
Allura aħna irrepeti dan il-proċess
jibda mill-ewwel element.

32
00:01:19,947 --> 00:01:21,780
Jekk huwa dak li aħna qed
tfittex, nistgħu stop.

33
00:01:21,780 --> 00:01:22,800
Mhuwiex.

34
00:01:22,800 --> 00:01:25,020
Inkella, nimxu għall-element li jmiss.

35
00:01:25,020 --> 00:01:29,050
>> Iżda aħna nkunu nistgħu nżommu tirrepeti dan il-proċess,
jeżamina kull element min-naħa,

36
00:01:29,050 --> 00:01:31,720
bit-tama li nsibu n-numru 50.

37
00:01:31,720 --> 00:01:33,750
Iżda aħna mhux se tkun taf jekk
aħna ħadthom misjuba-numru 50

38
00:01:33,750 --> 00:01:38,290
jew jekk aħna ma, sakemm konna intensifikati
fuq kull element wieħed ta 'l-array.

39
00:01:38,290 --> 00:01:40,440
>> Biss ladarba aħna ghamilt
li u toħroġ qasir,

40
00:01:40,440 --> 00:01:43,040
nistgħu nikkonkludu li
50 ma tkunx fil-firxa.

41
00:01:43,040 --> 00:01:46,410
U għalhekk l-tfittxija lineari
algoritmu, sew hija naqset, per se.

42
00:01:46,410 --> 00:01:49,181
Iżda mhux fis-sens li
ma rnexxiex fil tagħmel dak

43
00:01:49,181 --> 00:01:49,930
staqsejna li tagħmel.

44
00:01:49,930 --> 00:01:52,390
>> Li ma rnexxilhiex bħala
kemm hija ma ssib 50,

45
00:01:52,390 --> 00:01:54,070
iżda 50 ma kienx fil-firxa.

46
00:01:54,070 --> 00:01:57,310
Iżda aħna mfittxija b'mod eżawrjenti
permezz ta 'kull element wieħed

47
00:01:57,310 --> 00:02:00,550
u għalhekk, filwaqt li aħna ma sabx
xejn, tfittxija lineari xorta

48
00:02:00,550 --> 00:02:05,230
jirnexxilu anki jekk il-
element mhuwiex fil-firxa.

49
00:02:05,230 --> 00:02:07,507
>> Allura x'inhu l-agħar każ
Sitwazzjoni ta 'tfittxija lineari?

50
00:02:07,507 --> 00:02:09,590
Well irridu nħarsu permezz
kull element wieħed,

51
00:02:09,590 --> 00:02:14,590
jew għaliex l-element mira
hija l-aħħar element tal-firxa,

52
00:02:14,590 --> 00:02:18,510
jew l-element aħna qed tfittex ma
attwalment jeżistu fl-array fil-livelli kollha.

53
00:02:18,510 --> 00:02:19,760
X'inhu l-aħjar xenarju?

54
00:02:19,760 --> 00:02:22,430
Well we tista 'ssib l-
element immedjatament.

55
00:02:22,430 --> 00:02:24,360
U kemm elementi
għandna mbagħad nħarsu

56
00:02:24,360 --> 00:02:26,859
fil fl-aħjar każ,
jekk aħna qed tfittex għaliha

57
00:02:26,859 --> 00:02:28,400
u aħna jsibuha fil-bidu nett?

58
00:02:28,400 --> 00:02:29,850
Aħna tista 'twaqqaf immedjatament.

59
00:02:29,850 --> 00:02:32,984
>> Xi jfisser dan jgħidu dwar il-
kumplessità tat-tfittxija lineari?

60
00:02:32,984 --> 00:02:35,650
Ukoll fl-agħar każ, għandna
li tħares lejn kull element wieħed.

61
00:02:35,650 --> 00:02:38,930
U għalhekk tmur fil O ta
n, fl-agħar każ.

62
00:02:38,930 --> 00:02:41,540
>> Fl-aħjar każ, aħna qed gonna
isibu l-element immedjatament.

63
00:02:41,540 --> 00:02:44,750
U hekk tmur fil omega-1 ta '.

64
00:02:44,750 --> 00:02:45,780
>> Jien Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Dan huwa CS50.

66
00:02:48,020 --> 00:02:49,876