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
Ітэрацыі па масіву злева
Права, гледзячы на ​​паказаным элеменце.

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
І так ён працуе ў 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