1
00:00:00,000 --> 00:00:02,892
>> [MUSIC CHƠI]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
tìm kiếm là một thuật toán chúng tôi

4
00:00:07,180 --> 00:00:09,840
có thể sử dụng để tìm một phần tử trong một mảng.

5
00:00:09,840 --> 00:00:11,990
Một thuật toán thu hồi
là một tập hợp các bước theo các bước

6
00:00:11,990 --> 00:00:15,030
các hướng dẫn để hoàn thành một nhiệm vụ.

7
00:00:15,030 --> 00:00:17,480
>> Các tìm kiếm tuyến tính
thuật toán hoạt động như sau.

8
00:00:17,480 --> 00:00:22,200
Lặp qua mảng từ trái sang
bên phải, tìm kiếm một yếu tố quy định.

9
00:00:22,200 --> 00:00:26,380
>> Trong giả, đó là một nhiều hơn
phiên bản cất của câu này,

10
00:00:26,380 --> 00:00:29,840
nếu các yếu tố đầu tiên là những gì
bạn đang tìm kiếm, bạn có thể dừng lại.

11
00:00:29,840 --> 00:00:33,930
Nếu không, di chuyển đến phần tử tiếp theo và
tiếp tục đi qua và hơn cho đến khi bạn tìm thấy

12
00:00:33,930 --> 00:00:36,389
phần tử, hoặc bạn không.

13
00:00:36,389 --> 00:00:38,680
Vì vậy, chúng ta có thể sử dụng tuyến tính
thuật toán tìm kiếm, ví dụ,

14
00:00:38,680 --> 00:00:42,330
để tìm giá trị mục tiêu
chín trong mảng này.

15
00:00:42,330 --> 00:00:43,870
Vâng, chúng tôi bắt đầu từ đầu.

16
00:00:43,870 --> 00:00:45,970
Nếu đó là những gì chúng tôi
tìm kiếm, chúng ta có thể dừng lại.

17
00:00:45,970 --> 00:00:47,890
Nó không, chúng ta không tìm kiếm 11.

18
00:00:47,890 --> 00:00:50,220
Vì vậy, nếu không, di chuyển đến phần tử tiếp theo.

19
00:00:50,220 --> 00:00:51,510
>> Vì vậy, chúng ta nhìn vào 23.

20
00:00:51,510 --> 00:00:52,730
23 điều chúng ta đang tìm kiếm?

21
00:00:52,730 --> 00:00:55,614
Cũng không có, vì vậy chúng tôi chuyển sang tiếp theo
phần tử, và các phần tử tiếp theo,

22
00:00:55,614 --> 00:00:57,780
và chúng tôi tiếp tục đi qua
quá trình này hơn và hơn

23
00:00:57,780 --> 00:01:01,030
và hơn, cho đến khi chúng tôi hạ cánh
vào một tình huống như thế này.

24
00:01:01,030 --> 00:01:03,910
>> Chín là những gì chúng tôi đang tìm kiếm,
và yếu tố này của mảng

25
00:01:03,910 --> 00:01:05,787
là, nó giá trị là chín.

26
00:01:05,787 --> 00:01:08,120
Và như vậy, chúng tôi tìm thấy những gì chúng tôi
tìm kiếm, và chúng ta có thể dừng lại.

27
00:01:08,120 --> 00:01:11,910
Các tìm kiếm tuyến tính có
hoàn thành, thành công.

28
00:01:11,910 --> 00:01:15,370
>> Nhưng những gì về nếu chúng tôi đang tìm kiếm
một yếu tố mà không có trong mảng của chúng tôi.

29
00:01:15,370 --> 00:01:17,040
Sao tìm kiếm tuyến tính vẫn làm việc?

30
00:01:17,040 --> 00:01:17,540
Vâng chắc chắn.

31
00:01:17,540 --> 00:01:19,947
Vì vậy, chúng ta lặp lại quá trình này
bắt đầu từ phần tử đầu tiên.

32
00:01:19,947 --> 00:01:21,780
Nếu đó là những gì chúng tôi
tìm kiếm, chúng ta có thể dừng lại.

33
00:01:21,780 --> 00:01:22,800
Nó không phải.

34
00:01:22,800 --> 00:01:25,020
Nếu không, chúng tôi di chuyển đến phần tử tiếp theo.

35
00:01:25,020 --> 00:01:29,050
>> Nhưng chúng ta có thể tiếp tục lặp lại quá trình này,
kiểm tra mỗi phần tử lần lượt,

36
00:01:29,050 --> 00:01:31,720
hy vọng rằng chúng ta tìm số 50.

37
00:01:31,720 --> 00:01:33,750
Nhưng chúng ta sẽ không biết nếu
chúng tôi đã tìm thấy các số 50

38
00:01:33,750 --> 00:01:38,290
hoặc nếu chúng ta không làm, cho đến khi chúng ta đã bước
trên mỗi phần tử của mảng.

39
00:01:38,290 --> 00:01:40,440
>> Chỉ khi chúng tôi đã thực hiện
đó và đi lên ngắn,

40
00:01:40,440 --> 00:01:43,040
chúng ta có thể kết luận rằng
50 không có trong mảng.

41
00:01:43,040 --> 00:01:46,410
Và do đó, tìm kiếm tuyến tính
thuật toán, cũng không thành công, mỗi se.

42
00:01:46,410 --> 00:01:49,181
Nhưng không phải trong ý nghĩa rằng nó
đã không thành công trong việc làm những gì

43
00:01:49,181 --> 00:01:49,930
chúng tôi hỏi nó làm.

44
00:01:49,930 --> 00:01:52,390
>> Nó đã không thành công trong khi
nhiều khi nó không tìm thấy 50,

45
00:01:52,390 --> 00:01:54,070
nhưng 50 không phải là trong mảng.

46
00:01:54,070 --> 00:01:57,310
Nhưng chúng tôi đã triệt tìm kiếm
qua mọi yếu tố duy nhất

47
00:01:57,310 --> 00:02:00,550
và như vậy, trong khi chúng tôi không tìm thấy
bất cứ điều gì, tìm kiếm tuyến tính vẫn

48
00:02:00,550 --> 00:02:05,230
thành công ngay cả khi
yếu tố không có trong mảng.

49
00:02:05,230 --> 00:02:07,507
>> Vì vậy, trường hợp xấu nhất là gì
kịch bản với tìm kiếm tuyến tính?

50
00:02:07,507 --> 00:02:09,590
Vâng, chúng ta phải xem xét thông qua
mỗi yếu tố duy nhất,

51
00:02:09,590 --> 00:02:14,590
hoặc vì các yếu tố mục tiêu
là yếu tố cuối cùng của mảng,

52
00:02:14,590 --> 00:02:18,510
hoặc các yếu tố chúng tôi đang tìm kiếm không
thực sự tồn tại trong mảng ở tất cả.

53
00:02:18,510 --> 00:02:19,760
Trường hợp kịch bản tốt nhất là gì?

54
00:02:19,760 --> 00:02:22,430
Vâng, chúng tôi có thể tìm thấy
phần tử ngay.

55
00:02:22,430 --> 00:02:24,360
Và bao nhiêu yếu tố
Chúng ta sau đó phải tìm

56
00:02:24,360 --> 00:02:26,859
ở trong trường hợp tốt nhất,
nếu chúng ta đang tìm kiếm nó

57
00:02:26,859 --> 00:02:28,400
và chúng tôi tìm thấy nó ngay từ đầu?

58
00:02:28,400 --> 00:02:29,850
Chúng ta có thể dừng lại ngay lập tức.

59
00:02:29,850 --> 00:02:32,984
>> Điều này không nói về
phức tạp của tìm kiếm tuyến tính?

60
00:02:32,984 --> 00:02:35,650
Cũng trong trường hợp xấu nhất, chúng tôi có
nhìn vào từng yếu tố duy nhất.

61
00:02:35,650 --> 00:02:38,930
Và do đó, nó chạy trong O
n, trong trường hợp xấu nhất.

62
00:02:38,930 --> 00:02:41,540
>> Trong trường hợp tốt nhất, chúng tôi đang gonna
tìm phần tử ngay lập tức.

63
00:02:41,540 --> 00:02:44,750
Và như vậy chạy trong omega của 1.

64
00:02:44,750 --> 00:02:45,780
>> Tôi Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Đây là CS50.

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