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: Linear
търсене е алгоритъм, ние

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
>> Nine е това, което търсим,
и този елемент на масива

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
И така, той работи в O на
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