1
00:00:00,000 --> 00:00:02,892
>> [MUZIKO Ludante]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
serĉo estas algoritmo ni

4
00:00:07,180 --> 00:00:09,840
povas uzi por trovi elementon en tabelo.

5
00:00:09,840 --> 00:00:11,990
Algoritmo revokon
Estas paŝo-de-paŝo aro

6
00:00:11,990 --> 00:00:15,030
de instrukcioj por kompletigado de tasko.

7
00:00:15,030 --> 00:00:17,480
>> La lineara serĉo
algoritmo laboras kiel sekvas.

8
00:00:17,480 --> 00:00:22,200
Persisti trans la tabelo de maldekstre
dekstra, rigardante por specifa elemento.

9
00:00:22,200 --> 00:00:26,380
>> En _pseudocode_, kiu estas pli
distilita versio de tiu frazo,

10
00:00:26,380 --> 00:00:29,840
se la unua elemento estas kio
vi serĉas, vi povas halti.

11
00:00:29,840 --> 00:00:33,930
Alie, movi al la sekva elemento kaj
plu iri super kaj trans ĝis vi trovos

12
00:00:33,930 --> 00:00:36,389
la elemento, aŭ vi ne faras.

13
00:00:36,389 --> 00:00:38,680
Do ni povas uzi linian
serĉo algoritmo, ekzemple,

14
00:00:38,680 --> 00:00:42,330
trovi la celon valoro
naŭ en ĉi tabelo.

15
00:00:42,330 --> 00:00:43,870
Nu ni starti je la komenco.

16
00:00:43,870 --> 00:00:45,970
Se ĝi estas kio ni estas
serĉas, ni povas halti.

17
00:00:45,970 --> 00:00:47,890
Ĝi ne estas, ni ne serĉas 11.

18
00:00:47,890 --> 00:00:50,220
Do alie, movi al la sekva elemento.

19
00:00:50,220 --> 00:00:51,510
>> Do ni rigardu 23.

20
00:00:51,510 --> 00:00:52,730
Estas 23 kion ni serĉas?

21
00:00:52,730 --> 00:00:55,614
Nu ne, do ni pluiru al la venonta
elemento, kaj la sekva elemento,

22
00:00:55,614 --> 00:00:57,780
kaj ni plu iri tra
ĉi procezo denove kaj denove

23
00:00:57,780 --> 00:01:01,030
kaj super, ĝis ni surteriĝi
sur tia situacio.

24
00:01:01,030 --> 00:01:03,910
>> Naŭ estas kion ni serĉas,
kaj ĉi elemento de la tabelo

25
00:01:03,910 --> 00:01:05,787
estas, ĝia valoro estas naŭ.

26
00:01:05,787 --> 00:01:08,120
Kaj tiel ni trovas kion ni estas
serĉas, kaj ni povos halti.

27
00:01:08,120 --> 00:01:11,910
La lineara serĉo havas
kompletigita, sukcese.

28
00:01:11,910 --> 00:01:15,370
>> Sed kio pri se ni serĉas
elemento kiu ne estas en nia tabelo.

29
00:01:15,370 --> 00:01:17,040
Ĉu lineara serĉo ankoraŭ funkcias?

30
00:01:17,040 --> 00:01:17,540
Nu certas.

31
00:01:17,540 --> 00:01:19,947
Do ni ripetas ĉi procezo
ekde la unua elemento.

32
00:01:19,947 --> 00:01:21,780
Se ĝi estas kio ni estas
serĉas, ni povas halti.

33
00:01:21,780 --> 00:01:22,800
Ĝi ne estas.

34
00:01:22,800 --> 00:01:25,020
Alie, ni movi al la sekva elemento.

35
00:01:25,020 --> 00:01:29,050
>> Sed ni povas daŭre ripetas ĉi procezo,
ekzamenante ĉiu elemento laŭvice,

36
00:01:29,050 --> 00:01:31,720
esperante ke ni trovas la numero 50.

37
00:01:31,720 --> 00:01:33,750
Sed ni ne scios se
ni trovis la nombro 50

38
00:01:33,750 --> 00:01:38,290
aŭ se ni ne faris tion, ĝis ni paŝis
super ĉiu unuopa elemento de la tabelo.

39
00:01:38,290 --> 00:01:40,440
>> Nur unufoje ni faris
tio kaj venis supren mallonga,

40
00:01:40,440 --> 00:01:43,040
ni povas konkludi ke
50 Ne en la tabelo.

41
00:01:43,040 --> 00:01:46,410
Kaj tial la lineara serĉo
algoritmo, bone ĝi malsukcesis, por se.

42
00:01:46,410 --> 00:01:49,181
Sed ne en la senco ke ĝi
estis malsukcesa en fari kio

43
00:01:49,181 --> 00:01:49,930
Ni demandis lin fari.

44
00:01:49,930 --> 00:01:52,390
>> Ĝi estis malsukcesa en kiel
kiom ĝi ne trovis 50,

45
00:01:52,390 --> 00:01:54,070
sed 50 ne estis en la tabelo.

46
00:01:54,070 --> 00:01:57,310
Sed ni ĝisfunde traserĉis
tra ĉiu ununura ero

47
00:01:57,310 --> 00:02:00,550
kaj tial, dum ni ne trovis
io, lineara serĉo ankoraŭ

48
00:02:00,550 --> 00:02:05,230
sukcesas eĉ se la
elemento ne estas en la tabelo.

49
00:02:05,230 --> 00:02:07,507
>> Do kio estas la plej malbona kazo
scenaro kun lineara serĉo?

50
00:02:07,507 --> 00:02:09,590
Nu ni devas rigardi tra
ĉiu ununura ero,

51
00:02:09,590 --> 00:02:14,590
ĉu ĉar la celo elemento
estas la lasta ero de la tabelo,

52
00:02:14,590 --> 00:02:18,510
aŭ la elemento ni serĉas ne
reale ekzistas en la tabelo ajn.

53
00:02:18,510 --> 00:02:19,760
Kio estas la plej bona kazo scenaro?

54
00:02:19,760 --> 00:02:22,430
Nu ni povus trovi la
elemento tuj.

55
00:02:22,430 --> 00:02:24,360
Kaj kiom da elementoj
ni tiam devas rigardi

56
00:02:24,360 --> 00:02:26,859
ĉe en la plej bona kazo,
se ni serĉas ŝin

57
00:02:26,859 --> 00:02:28,400
kaj ni trovos ĉe la komenco?

58
00:02:28,400 --> 00:02:29,850
Ni povas ĉesi tuj.

59
00:02:29,850 --> 00:02:32,984
>> Kion tio diras pri la
komplekseco de lineara serĉo?

60
00:02:32,984 --> 00:02:35,650
Nu en la plej malbona kazo, ni havas
rigardi ĉiu ununura ero.

61
00:02:35,650 --> 00:02:38,930
Kaj tiel ĝi kuras en O de
n, en la plej malbona kazo.

62
00:02:38,930 --> 00:02:41,540
>> En la plej bona kazo, ni estas gonna
trovi la elemento tuj.

63
00:02:41,540 --> 00:02:44,750
Kaj tiel kuras en omega de 1.

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

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

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