1
00:00:00,000 --> 00:00:02,892
>> [Музички]

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

3
00:00:05,347 --> 00:00:07,180
Даг LLOYD: Линеарна
пребарување е алгоритам ние

4
00:00:07,180 --> 00:00:09,840
можат да го користат за да се најде елемент во низата.

5
00:00:09,840 --> 00:00:11,990
Една потсетиме алгоритам
е збир чекор-по-чекор

6
00:00:11,990 --> 00:00:15,030
упатства за завршување на задачата.

7
00:00:15,030 --> 00:00:17,480
>> Линеарниот пребарување
алгоритам работи како што следува.

8
00:00:17,480 --> 00:00:22,200
Iterate низ низа од лево кон
право, во потрага по одреден елемент.

9
00:00:22,200 --> 00:00:26,380
>> Во pseudocode, што е повеќе
дестилирана верзија на оваа реченица,

10
00:00:26,380 --> 00:00:29,840
ако првиот елемент е тоа што
што го барате, можете да престанете.

11
00:00:29,840 --> 00:00:33,930
Во спротивно, се движи кон следниот елемент и
Продолжувам да одам одново и одново додека не најдете

12
00:00:33,930 --> 00:00:36,389
елемент, или не.

13
00:00:36,389 --> 00:00:38,680
За да можеме да го користите линеарниот
пребарување алгоритам, на пример,

14
00:00:38,680 --> 00:00:42,330
да се најде на целната вредност
девет во оваа низа.

15
00:00:42,330 --> 00:00:43,870
Па да почнеме од почеток.

16
00:00:43,870 --> 00:00:45,970
Ако тоа е она што ние сме
барате, ние може да го запре.

17
00:00:45,970 --> 00:00:47,890
Тоа не е, ние не сме во потрага по 11.

18
00:00:47,890 --> 00:00:50,220
Па на друг начин, се движи кон следниот елемент.

19
00:00:50,220 --> 00:00:51,510
>> Значи ние се погледне во 23.

20
00:00:51,510 --> 00:00:52,730
23 е она што го барате?

21
00:00:52,730 --> 00:00:55,614
Па не, за да можеме да се движи кон следниот
елемент, и на следниот елемент,

22
00:00:55,614 --> 00:00:57,780
а ние продолжуваме да оди преку
овој процес одново и одново

23
00:00:57,780 --> 00:01:01,030
и одново, додека не се приземји
во ваква ситуација.

24
00:01:01,030 --> 00:01:03,910
>> Девет е она што го барате,
и овој елемент на низата

25
00:01:03,910 --> 00:01:05,787
е, тоа е вредност е девет.

26
00:01:05,787 --> 00:01:08,120
И така ние се најде она што ние сме
во потрага по, а ние може да го запре.

27
00:01:08,120 --> 00:01:11,910
Линеарниот пребарување има
завршен, успешно.

28
00:01:11,910 --> 00:01:15,370
>> Но, што е, ако ние сме во потрага по
елемент кој не е во нашата низа.

29
00:01:15,370 --> 00:01:17,040
Се линеарно пребарување се уште работат?

30
00:01:17,040 --> 00:01:17,540
И сигурен.

31
00:01:17,540 --> 00:01:19,947
Па ние го повторите овој процес
почнувајќи од првиот елемент.

32
00:01:19,947 --> 00:01:21,780
Ако тоа е она што ние сме
барате, ние може да го запре.

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

34
00:01:22,800 --> 00:01:25,020
Инаку, ние се движи кон следниот елемент.

35
00:01:25,020 --> 00:01:29,050
>> Но, можеме да ги повторува овој процес,
испитување на секој елемент од своја страна,

36
00:01:29,050 --> 00:01:31,720
со надеж дека ќе најдеме бројот 50.

37
00:01:31,720 --> 00:01:33,750
Но, ние не ќе се знае дали
Наидовме на бројот 50

38
00:01:33,750 --> 00:01:38,290
или ако не, се додека ние сме зачекори
во текот на секој елемент од низата.

39
00:01:38,290 --> 00:01:40,440
>> Само еднаш, ние го направивме
кој и да дојде до краток,

40
00:01:40,440 --> 00:01:43,040
можеме да заклучиме дека
50 не е во низа.

41
00:01:43,040 --> 00:01:46,410
И така на линеарно пребарување
алгоритам, и тоа не успеа, само по себе.

42
00:01:46,410 --> 00:01:49,181
Но не во смисла дека тоа
бил неуспешен во тоа што

43
00:01:49,181 --> 00:01:49,930
ние тоа треба да го стори.

44
00:01:49,930 --> 00:01:52,390
>> Тоа беше неуспешен во што
колку што тоа не се најде на 50,

45
00:01:52,390 --> 00:01:54,070
50 но не беше во низа.

46
00:01:54,070 --> 00:01:57,310
Но, ние се исцрпно претрес
преку секој елемент

47
00:01:57,310 --> 00:02:00,550
И така, додека ние не најдете
ништо, линеарно пребарување сеуште

48
00:02:00,550 --> 00:02:05,230
успева дури и ако
елемент не е во низа.

49
00:02:05,230 --> 00:02:07,507
>> Значи, што е најлош случај
сценариото со линеарно пребарување?

50
00:02:07,507 --> 00:02:09,590
И ние треба да се погледне преку
секој елемент,

51
00:02:09,590 --> 00:02:14,590
или поради тоа што цел елемент
е последниот елемент на низата,

52
00:02:14,590 --> 00:02:18,510
или елемент ние сме во потрага по не
навистина постојат во низа на сите.

53
00:02:18,510 --> 00:02:19,760
Што е најдоброто сценарио?

54
00:02:19,760 --> 00:02:22,430
И ние би можеле да се најдат на
елемент веднаш.

55
00:02:22,430 --> 00:02:24,360
И колку елементи
И така, треба да се погледне

56
00:02:24,360 --> 00:02:26,859
на во најдобар случај,
ако ние сме во потрага по него

57
00:02:26,859 --> 00:02:28,400
и ние го најдете на самиот почеток?

58
00:02:28,400 --> 00:02:29,850
Можеме да престанат веднаш.

59
00:02:29,850 --> 00:02:32,984
>> Што ни кажува тоа за
Комплексноста на линеарно пребарување?

60
00:02:32,984 --> 00:02:35,650
И во најлош случај, имаме
да се погледне во секој елемент.

61
00:02:35,650 --> 00:02:38,930
И така таа работи во о на
n, во најлош случај.

62
00:02:38,930 --> 00:02:41,540
>> Во најдобар случај, ние ќе отидеме
најдете елемент веднаш.

63
00:02:41,540 --> 00:02:44,750
И така работи во омега на 1.

64
00:02:44,750 --> 00:02:45,780
>> Јас сум Даг Лојд.

65
00:02:45,780 --> 00:02:48,020
Ова е CS50.

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