1
00:00:00,000 --> 00:00:02,892
 [SKAN MŪZIKA]

2
00:00:05,347 --> 00:00:07,593
DAGS LOIDS: Lineārā meklēšana ir
algoritms, ko varam izmantot, lai 

3
00:00:07,593 --> 00:00:09,840
atrastu elementu masīvā. 

4
00:00:09,840 --> 00:00:12,435
Algoritma atsaukšana ir norādījumu
kopums uzdevuma izpildei soli pa 

5
00:00:12,435 --> 00:00:15,030
solim. 

6
00:00:15,030 --> 00:00:17,480
 Lineārās meklēšanas algoritms
darbojas šādi.

7
00:00:17,480 --> 00:00:19,840
Atkārtojiet masīvu no kreisās puses
uz labo, meklējot noteiktu 

8
00:00:19,840 --> 00:00:22,200
elementu. 

9
00:00:22,200 --> 00:00:26,020
Pseidokodā, kas ir šī izteikuma
detalizētāka versija, varat 

10
00:00:26,020 --> 00:00:29,840
apstāties, ja pirmais elements ir
tas, ko meklējat. 

11
00:00:29,840 --> 00:00:33,114
Pretējā gadījumā pārejiet uz nākamo
elementu un turpiniet to atkal un 

12
00:00:33,114 --> 00:00:36,389
atkal, līdz atrodat vai neatrodat
elementu. 

13
00:00:36,389 --> 00:00:39,359
Tātad mēs varam izmantot lineāro
meklēšanas algoritmu, piemēram, lai 

14
00:00:39,359 --> 00:00:42,330
šajā masīvā atrastu mērķa vērtību
deviņi. 

15
00:00:42,330 --> 00:00:43,870
Tad mēs sākam no sākuma.

16
00:00:43,870 --> 00:00:45,970
Ja tas ir tas, ko mēs meklējam, mēs
varam apstāties.

17
00:00:45,970 --> 00:00:47,890
Tā nav, mēs nemeklējam 11.

18
00:00:47,890 --> 00:00:50,220
Tad pārejiet uz nākamo elementu.

19
00:00:50,220 --> 00:00:51,510
 Tātad mēs skatāmies uz 23.

20
00:00:51,510 --> 00:00:52,730
Vai 23 ir tas, ko mēs meklējam?

21
00:00:52,730 --> 00:00:55,496
Nu nav tas, tāpēc mēs pārejam pie
nākamā elementa un nākamā elementa, 

22
00:00:55,496 --> 00:00:58,263
un mēs turpinām iet cauri šim
procesam atkal un atkal, līdz nonākam 

23
00:00:58,263 --> 00:01:01,030
līdz šādai situācijai. 

24
00:01:01,030 --> 00:01:03,408
Deviņi ir tas, ko mēs meklējam, un
šis masīva elements ir, tā vērtība 

25
00:01:03,408 --> 00:01:05,787
ir deviņi. 

26
00:01:05,787 --> 00:01:08,120
Un tā mēs atradām to, ko meklējam,
un varam apstāties.

27
00:01:08,120 --> 00:01:11,910
Lineārā meklēšana ir veiksmīgi
pabeigta.

28
00:01:11,910 --> 00:01:15,370
 Bet ko darīt, ja mēs meklējam
elementu, kas nav mūsu masīvā.

29
00:01:15,370 --> 00:01:17,040
Vai lineārā meklēšana joprojām
darbosies?

30
00:01:17,040 --> 00:01:17,540
Noteikti.

31
00:01:17,540 --> 00:01:19,947
Tātad mēs atkārtojam šo procesu,
sākot ar pirmo elementu.

32
00:01:19,947 --> 00:01:21,780
Ja tas ir tas, ko mēs meklējam, mēs
varam apstāties.

33
00:01:21,780 --> 00:01:22,800
Tā nav.

34
00:01:22,800 --> 00:01:25,020
Tad mēs pārejam uz nākamo elementu.

35
00:01:25,020 --> 00:01:28,370
Bet mēs varam turpināt atkārtot šo
procesu, pārbaudot katru elementu 

36
00:01:28,370 --> 00:01:31,720
pēc kārtas, cerot, ka atradīsim
skaitli 50. 

37
00:01:31,720 --> 00:01:35,005
Bet mēs neuzzināsim, vai esam
atraduši skaitli 50 vai neesam 

38
00:01:35,005 --> 00:01:38,290
atraduši, kamēr nebūsim izgājuši
cauri katram masīva elementam. 

39
00:01:38,290 --> 00:01:40,665
Tikai tad, kad esam to paveikuši un
panākuši rezultātu, mēs varam 

40
00:01:40,665 --> 00:01:43,040
secināt, ka 50 nav iekļauts masīvā.


41
00:01:43,040 --> 00:01:46,410
Un tāpēc lineārās meklēšanas
algoritms , kā tāds,neizdevās.

42
00:01:46,410 --> 00:01:49,930
Bet ne tādā nozīmē, ka tam
neizdevās izdarīt to, ko mēs tam prasījām.

43
00:01:49,930 --> 00:01:54,070
 Tam neizdevās, jo neatrada 50, bet
50 nebija masīvā.

44
00:01:54,070 --> 00:01:57,790
Bet mēs esam izsmeļoši izmeklējuši
katru elementu, un tāpēc, lai gan 

45
00:01:57,790 --> 00:02:01,510
mēs neko neatradām, lineārā
meklēšana joprojām izdodas, pat ja 

46
00:02:01,510 --> 00:02:05,230
elements nav masīvā. 

47
00:02:05,230 --> 00:02:07,507
 Tātad, kāds ir sliktākais
scenārijs ar lineāro meklēšanu?

48
00:02:07,507 --> 00:02:11,174
Mums ir jāizskata katrs atsevišķais
elements vai nu tāpēc, ka mērķa 

49
00:02:11,174 --> 00:02:14,842
elements ir pēdējais masīva
elements, vai arī elements, kuru mēs 

50
00:02:14,842 --> 00:02:18,510
meklējam, patiesībā nemaz nepastāv
masīvā. 

51
00:02:18,510 --> 00:02:19,760
Kāds ir labākais scenārijs?

52
00:02:19,760 --> 00:02:22,430
Nu, mēs varētu nekavējoties atrast
elementu.

53
00:02:22,430 --> 00:02:25,415
Un cik daudz elementu mums labākajā
gadījumā ir jāapskata, ja mēs to 

54
00:02:25,415 --> 00:02:28,400
meklējam un atrodam pašā sākumā? 

55
00:02:28,400 --> 00:02:29,850
Mēs varam nekavējoties apstāties.

56
00:02:29,850 --> 00:02:32,984
 Ko tas saka par lineārās
meklēšanas sarežģītību?

57
00:02:32,984 --> 00:02:35,650
Sliktākajā gadījumā mums ir
jāaplūko katrs elements.

58
00:02:35,650 --> 00:02:38,930
Un tā tas darbojas n skaitļa O,
sliktākajā gadījumā.

59
00:02:38,930 --> 00:02:41,540
 Labākajā gadījumā mēs nekavējoties
atradīsim elementu.

60
00:02:41,540 --> 00:02:44,750
Un tā darbojas omega 1 skaitlī.

61
00:02:44,750 --> 00:02:45,780
 Es esmu Dags Loids.

62
00:02:45,780 --> 00:02:48,020
Šis ir CS50.