1
00:00:00,000 --> 00:00:02,892
>> [MUZYKI]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: normalny
Wyszukiwarka jest to algorytm

4
00:00:07,180 --> 00:00:09,840
można użyć, aby znaleźć element w tablicy.

5
00:00:09,840 --> 00:00:11,990
Przypomnieć algorytm
to zestaw krok po kroku

6
00:00:11,990 --> 00:00:15,030
instrukcji do wykonania zadania.

7
00:00:15,030 --> 00:00:17,480
>> Wyszukiwanie liniowe
Algorytm działa w następujący sposób.

8
00:00:17,480 --> 00:00:22,200
Iteracji całej tablicy, od lewej do
prawo, szukając określonego elementu.

9
00:00:22,200 --> 00:00:26,380
>> W pseudokodzie, który jest bardziej
Wersja destylowana tego zdania,

10
00:00:26,380 --> 00:00:29,840
Jeśli pierwszy element jest tym, co
szukasz, możesz przestać.

11
00:00:29,840 --> 00:00:33,930
W przeciwnym razie przejdź do następnego elementu i
nie poddawać się w kółko, aż znajdziesz

12
00:00:33,930 --> 00:00:36,389
element, albo nie.

13
00:00:36,389 --> 00:00:38,680
Tak więc możemy użyć liniowy
Algorytm poszukiwania np

14
00:00:38,680 --> 00:00:42,330
znaleźć wartość docelową
dziewięć w tej tablicy.

15
00:00:42,330 --> 00:00:43,870
Dobrze zacząć od początku.

16
00:00:43,870 --> 00:00:45,970
Jeśli to, co jesteśmy
szukamy, możemy zatrzymać.

17
00:00:45,970 --> 00:00:47,890
To nie, my nie szukamy 11.

18
00:00:47,890 --> 00:00:50,220
Więc inaczej, przejście do następnego elementu.

19
00:00:50,220 --> 00:00:51,510
>> Więc patrzymy na 23.

20
00:00:51,510 --> 00:00:52,730
Jest 23, co szukasz?

21
00:00:52,730 --> 00:00:55,614
No nie, więc przechodzimy do następnego
elementem, a kolejnym elementem,

22
00:00:55,614 --> 00:00:57,780
A my wciąż przechodzi
ten proces w kółko

23
00:00:57,780 --> 00:01:01,030
kółko, aż wylądujemy
o takiej sytuacji.

24
00:01:01,030 --> 00:01:03,910
>> Dziewięć jest to, czego szukasz,
i ten element macierzy

25
00:01:03,910 --> 00:01:05,787
jest, to jest wartość nie jest dziewięć.

26
00:01:05,787 --> 00:01:08,120
I tak okazało się to, co jesteśmy
szuka, a my możemy się zatrzymać.

27
00:01:08,120 --> 00:01:11,910
Wyszukiwanie liniowe ma
zakończone powodzeniem.

28
00:01:11,910 --> 00:01:15,370
>> Ale co, jeśli szukamy
element, który nie jest w naszej tablicy.

29
00:01:15,370 --> 00:01:17,040
Czy przeszukiwanie liniowe wciąż działa?

30
00:01:17,040 --> 00:01:17,540
No pewnie.

31
00:01:17,540 --> 00:01:19,947
Więc powtórzyć ten proces
począwszy od pierwszego elementu.

32
00:01:19,947 --> 00:01:21,780
Jeśli to, co jesteśmy
szukamy, możemy zatrzymać.

33
00:01:21,780 --> 00:01:22,800
To nie jest.

34
00:01:22,800 --> 00:01:25,020
W przeciwnym razie, możemy przejść do następnego elementu.

35
00:01:25,020 --> 00:01:29,050
>> Ale możemy powtarzać ten proces,
badając każdy element z kolei

36
00:01:29,050 --> 00:01:31,720
mając nadzieję, że znajdziemy numer 50.

37
00:01:31,720 --> 00:01:33,750
Ale nie wiem, czy
Odkryliśmy numer 50

38
00:01:33,750 --> 00:01:38,290
lub jeśli nie, dopóki nie wszedł
na każdym elemencie tablicy.

39
00:01:38,290 --> 00:01:40,440
>> Tylko raz zrobiliśmy
że i wymyślić krótkie,

40
00:01:40,440 --> 00:01:43,040
możemy stwierdzić, że
50 nie znajduje się w tablicy.

41
00:01:43,040 --> 00:01:46,410
I tak przeszukiwanie liniowe
Algorytm, dobrze, że nie udało, per se.

42
00:01:46,410 --> 00:01:49,181
Ale w tym sensie, że
nie powiodło się w tym, co

43
00:01:49,181 --> 00:01:49,930
Poprosiliśmy go zrobić.

44
00:01:49,930 --> 00:01:52,390
>> To nie powiodła się, jak
podobnie jak nie znaleźliśmy 50,

45
00:01:52,390 --> 00:01:54,070
ale 50 nie był w tablicy.

46
00:01:54,070 --> 00:01:57,310
Ale my wyczerpująco wyszukiwane
przez każdego elementu

47
00:01:57,310 --> 00:02:00,550
i tak, a nie znaleźliśmy
coś, przeszukiwanie liniowe wciąż

48
00:02:00,550 --> 00:02:05,230
powiedzie się, nawet jeśli
element ten nie istnieje w tablicy.

49
00:02:05,230 --> 00:02:07,507
>> Więc co jest najgorszym przypadku
Scenariusz z wyszukiwania liniowego?

50
00:02:07,507 --> 00:02:09,590
Cóż musimy patrzeć przez
każdy pojedynczy element,

51
00:02:09,590 --> 00:02:14,590
albo dlatego, że element docelowy
jest to ostatni element tablicy,

52
00:02:14,590 --> 00:02:18,510
lub element szukamy nie
faktycznie istnieje w tablicy w ogóle.

53
00:02:18,510 --> 00:02:19,760
Jaki jest najlepszy scenariusz?

54
00:02:19,760 --> 00:02:22,430
Cóż możemy znaleźć
Element natychmiast.

55
00:02:22,430 --> 00:02:24,360
I jak wiele elementów
Czy więc trzeba szukać

56
00:02:24,360 --> 00:02:26,859
co w najlepszym przypadku,
jeśli szukamy dla niego

57
00:02:26,859 --> 00:02:28,400
i znajdujemy go na samym początku?

58
00:02:28,400 --> 00:02:29,850
Możemy natychmiast zatrzymać.

59
00:02:29,850 --> 00:02:32,984
>> Co nam to mówi o
Złożoność wyszukiwania liniowego?

60
00:02:32,984 --> 00:02:35,650
Cóż, w najgorszym przypadku, mamy
patrzeć na każdego elementu.

61
00:02:35,650 --> 00:02:38,930
I tak to działa w O.
n, w najgorszym przypadku.

62
00:02:38,930 --> 00:02:41,540
>> W najlepszym przypadku, zrobimy
natychmiast znaleźć element.

63
00:02:41,540 --> 00:02:44,750
I tak trwa w omega 1.

64
00:02:44,750 --> 00:02:45,780
>> Jestem Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
To CS50.

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