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
Даг Ллоид: Пуни
Претрага је алгоритам смо

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
Посматрајте преко низа са лева на
Добро, у потрази за одређени елемент.

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

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
И тако ради у Ø
н у најгорем случају.

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
Ово је ЦС50.

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