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
DOUG 로이드 : 선형
검색 알고리즘 우리입니다

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
그리고 그것은 아에서 실행
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