1
00:00:00,000 --> 00:00:02,892
>> [Zenelejátszási]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Lineáris
keresés egy algoritmus

4
00:00:07,180 --> 00:00:09,840
Használhatja találni egy elem a tömbben.

5
00:00:09,840 --> 00:00:11,990
Egy algoritmus visszahívás
egy lépésről-lépésre sor

6
00:00:11,990 --> 00:00:15,030
Az utasítások egy feladat elvégzéséhez.

7
00:00:15,030 --> 00:00:17,480
>> A lineáris keresés
algoritmus a következőképpen működik.

8
00:00:17,480 --> 00:00:22,200
Ismételget az egész tömb balról
Rendben, keres egy megadott elem.

9
00:00:22,200 --> 00:00:26,380
>> A pszeudokód, amely egy több
desztillált változata ez a mondat,

10
00:00:26,380 --> 00:00:29,840
ha az első elem az, amit
keres, akkor megáll.

11
00:00:29,840 --> 00:00:33,930
Ellenkező esetben, lépjen a következő elem és
folyamatosan megy újra és újra, amíg meg nem találja

12
00:00:33,930 --> 00:00:36,389
az elem, vagy nem.

13
00:00:36,389 --> 00:00:38,680
Így tudjuk használni a lineáris
keresési algoritmus, például,

14
00:00:38,680 --> 00:00:42,330
hogy megtalálják a célérték
Kilenc ebben a tömbben.

15
00:00:42,330 --> 00:00:43,870
Hát kezdjük az elején.

16
00:00:43,870 --> 00:00:45,970
Ha ez az, amit mi
keresnek, meg tudjuk állítani.

17
00:00:45,970 --> 00:00:47,890
Ez nem, mi nem keres 11.

18
00:00:47,890 --> 00:00:50,220
Szóval különben lépjen a következő elem.

19
00:00:50,220 --> 00:00:51,510
>> Szóval nézzük 23.

20
00:00:51,510 --> 00:00:52,730
23 amit keresett?

21
00:00:52,730 --> 00:00:55,614
Hát nem, így haladunk tovább a következő
elemet, és a következő elem,

22
00:00:55,614 --> 00:00:57,780
és mi folyamatosan megy keresztül
ezt a folyamatot újra és újra

23
00:00:57,780 --> 00:01:01,030
és újra, amíg leszállunk
egy ilyen helyzetben.

24
00:01:01,030 --> 00:01:03,910
>> Kilenc, amit keresünk,
és ez az elem a tömb

25
00:01:03,910 --> 00:01:05,787
az, hogy ez az érték kilenc.

26
00:01:05,787 --> 00:01:08,120
És így találtunk mi vagyunk
keresnek, és meg tudjuk állítani.

27
00:01:08,120 --> 00:01:11,910
A lineáris keresés rendelkezik
befejezett, sikeresen.

28
00:01:11,910 --> 00:01:15,370
>> De mi a helyzet, ha keresünk
olyan elem, amely nem a tömbben.

29
00:01:15,370 --> 00:01:17,040
Vajon lineáris keresés mindig működik?

30
00:01:17,040 --> 00:01:17,540
Nos, az biztos.

31
00:01:17,540 --> 00:01:19,947
Tehát megismételni ezt a folyamatot
kezdve az első elemet.

32
00:01:19,947 --> 00:01:21,780
Ha ez az, amit mi
keresnek, meg tudjuk állítani.

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

34
00:01:22,800 --> 00:01:25,020
Ellenkező esetben, lépjen a következő elem.

35
00:01:25,020 --> 00:01:29,050
>> De mi is folyamatosan ismétlődő ezt a folyamatot,
vizsgálata minden elem viszont,

36
00:01:29,050 --> 00:01:31,720
remélve, hogy megtaláljuk a szám 50.

37
00:01:31,720 --> 00:01:33,750
De nem fogunk tudni, ha
találtunk száma 50

38
00:01:33,750 --> 00:01:38,290
vagy ha nem, amíg meg nem lépett
alatt minden egyes eleme a tömb.

39
00:01:38,290 --> 00:01:40,440
>> Csak egyszer tettünk
ezt, és jön létre, rövid,

40
00:01:40,440 --> 00:01:43,040
tudjuk következtetni, hogy
50 nem a tömbben.

41
00:01:43,040 --> 00:01:46,410
És így a lineáris keresés
algoritmust, valamint elmulasztotta, önmagában.

42
00:01:46,410 --> 00:01:49,181
De nem abban az értelemben, hogy ez
sikertelen volt mit csinál

43
00:01:49,181 --> 00:01:49,930
kértük, hogy igen.

44
00:01:49,930 --> 00:01:52,390
>> Ez sikertelen volt, mint
sokat, mert nem találtam 50,

45
00:01:52,390 --> 00:01:54,070
de 50 nem volt a tömbben.

46
00:01:54,070 --> 00:01:57,310
De mi kimerítően keresett
keresztül minden egyes elem

47
00:01:57,310 --> 00:02:00,550
és így, míg nem találtunk
semmit, lineáris keresés mindig

48
00:02:00,550 --> 00:02:05,230
sikerül is, ha a
elem nincs a tömbben.

49
00:02:05,230 --> 00:02:07,507
>> Szóval mi a legrosszabb esetben
forgatókönyv lineáris keresést?

50
00:02:07,507 --> 00:02:09,590
Nos, át kell néznünk
Minden egyes eleme,

51
00:02:09,590 --> 00:02:14,590
vagy azért, mert a cél elem
az utolsó elem a tömb,

52
00:02:14,590 --> 00:02:18,510
vagy az elem keresünk nem
valóban létezik a tömb egyáltalán.

53
00:02:18,510 --> 00:02:19,760
Mi a legjobb esetben?

54
00:02:19,760 --> 00:02:22,430
Hát talán megtaláljuk a
elem azonnal.

55
00:02:22,430 --> 00:02:24,360
És hány elem
teszünk utána kell nézni

56
00:02:24,360 --> 00:02:26,859
A legjobb esetben,
ha keresünk meg

57
00:02:26,859 --> 00:02:28,400
és azt látjuk, hogy a kezdet kezdetén?

58
00:02:28,400 --> 00:02:29,850
Mi lehet azonnal leáll.

59
00:02:29,850 --> 00:02:32,984
>> Mit mond ez a
komplexitása lineáris keresés?

60
00:02:32,984 --> 00:02:35,650
Nos, a legrosszabb esetben van
nézni minden egyes elem.

61
00:02:35,650 --> 00:02:38,930
És ez így fut O
N, a legrosszabb esetben.

62
00:02:38,930 --> 00:02:41,540
>> A legjobb esetben, fogunk
megtalálni az elem azonnal.

63
00:02:41,540 --> 00:02:44,750
És így fut omegája 1.

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

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

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