1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG 로이드 : 그래서 CS50에 우리는 약 배웠다
정렬 및 검색의 다양한

3
00:00:08,900 --> 00:00:09,442
알고리즘.

4
00:00:09,442 --> 00:00:11,400
그리고 때때로이 될 수 있습니다
유지하기 조금 까다로운

5
00:00:11,400 --> 00:00:14,161
어떤 알고리즘의 트랙은 어떤 작업을 수행합니다.

6
00:00:14,161 --> 00:00:15,910
우리는 정말 만했습니다
너무 표면을 미끄러 져

7
00:00:15,910 --> 00:00:18,740
다른 많은 검색이 있습니다
및 정렬 알고리즘.

8
00:00:18,740 --> 00:00:21,780
그래서이 비디오의하자
몇 분 정도 걸릴

9
00:00:21,780 --> 00:00:24,980
시도하고 각 알고리즘을 증류
핵심 요소 아래로

10
00:00:24,980 --> 00:00:27,810
그래서 당신은 대부분의 기억
그들에 대한 중요한 정보

11
00:00:27,810 --> 00:00:31,970
및을 명확하게 설명 할 수 있어야한다
차이가 필요한 경우.

12
00:00:31,970 --> 00:00:34,220
>> 첫 번째는 선택의 일종이다.

13
00:00:34,220 --> 00:00:38,210
선택 정렬의 기본 개념
최소 정렬되지 않은 요소를 찾기

14
00:00:38,210 --> 00:00:42,890
및 배열로 교체
그 배열의 첫 번째 정렬되지 않은 요소입니다.

15
00:00:42,890 --> 00:00:46,620
우리는 최악의 경우라고 말했다
그것의 실행 시간은 N 제곱했다.

16
00:00:46,620 --> 00:00:50,060
그리고 당신은 왜 기억하려는 경우, 취
선택 정렬 비디오를 봐주세요.

17
00:00:50,060 --> 00:00:54,560
가장 좋은 경우의 실행 시간
또한 N 제곱된다.

18
00:00:54,560 --> 00:00:58,910
>> 버블 정렬, 그 뒤에 생각
하나는 인접 쌍을 교환하는 것이다.

19
00:00:58,910 --> 00:01:01,730
그래서 당신을 도와줍니다 키입니다
여기에 차이를 기억한다.

20
00:01:01,730 --> 00:01:04,920
선택 일종이다, 지금까지,
smallest-- 거품을 찾을 수

21
00:01:04,920 --> 00:01:06,790
일종의 인접 쌍을 교환합니다.

22
00:01:06,790 --> 00:01:08,710
우리는 인접 쌍을 교체
요소들은 경우

23
00:01:08,710 --> 00:01:12,530
이는 효과적으로 순서가
오른쪽에 큰 요소 거품

24
00:01:12,530 --> 00:01:17,060
동시에 또한 시작
왼쪽에 작은 요소를 이동합니다.

25
00:01:17,060 --> 00:01:20,180
최악의 경우 런타임
거품 정렬의 N 제곱.

26
00:01:20,180 --> 00:01:23,476
가장 좋은 경우의 실행 시간
거품의 종류는 N이다.

27
00:01:23,476 --> 00:01:25,350
때문에 그 상황에서
우리는 ... 사실상 없습니다

28
00:01:25,350 --> 00:01:27,141
우리는 필요하지 않을 수도 있습니다
전혀 스왑을합니다.

29
00:01:27,141 --> 00:01:31,026
우리는 하나만을해야
모든 N 요소를 통해 전달합니다.

30
00:01:31,026 --> 00:01:34,600
>> 삽입 정렬에서,
여기서 기본 개념은 시프트된다.

31
00:01:34,600 --> 00:01:36,630
즉, 삽입 정렬의 키워드입니다.

32
00:01:36,630 --> 00:01:39,630
우리는을 통해 한 번 단계거야
의 배열은 왼쪽에서 오른쪽으로.

33
00:01:39,630 --> 00:01:41,670
우리가하는 것처럼, 우리는있어
요소를 이동하는 것

34
00:01:41,670 --> 00:01:46,260
우리는 이미 공간을 만들어 봤어요
쯤에 해당 할 필요가 작은 것들

35
00:01:46,260 --> 00:01:48,080
다시 그 정렬 된 부분.

36
00:01:48,080 --> 00:01:51,600
그래서 우리는 정렬 된 배열을 구축 한
왼쪽에서 오른쪽으로 한 번에 요소,

37
00:01:51,600 --> 00:01:54,740
우리는 공간을 마련하는 일을 이동.

38
00:01:54,740 --> 00:01:58,650
의 최악의 실행 시간
삽입 정렬은 N 제곱된다.

39
00:01:58,650 --> 00:02:02,380
가장 좋은 경우의 실행 시간은 N이다.

40
00:02:02,380 --> 00:02:05,380
>> 키워드 sort-- 병합
여기 분할 및 병합된다.

41
00:02:05,380 --> 00:02:08,949
우리는 여부, 전체 배열을 분할
그것은 여섯 요소, 여덟 요소이다,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- 우리는 그것을 분할
아래로 반으로 반으로 반으로,

43
00:02:13,790 --> 00:02:17,720
우리는 배열에서있을 때까지
N 개의 원소 어레이.

44
00:02:17,720 --> 00:02:19,470
N 하나의 요소 배열의 집합입니다.

45
00:02:19,470 --> 00:02:22,640
그래서 우리는 하나의 시작
1000 요소의 배열,

46
00:02:22,640 --> 00:02:26,550
우리는 지점에 도착 우리가 어디
1000 한 요소 배열을 가지고있다.

47
00:02:26,550 --> 00:02:30,990
그리고 우리는 그 하위 배열을 병합 시작
다시 함께 올바른 순서.

48
00:02:30,990 --> 00:02:34,860
그래서 우리는이 하나의 요소 배열을
그리고 두 요소의 배열을 만들 수 있습니다.

49
00:02:34,860 --> 00:02:38,180
우리는이 두 요소의 배열을
및 네 개의 소자 어레이를 만들

50
00:02:38,180 --> 00:02:43,900
등등 등등 우리가 때까지
다시 한 N 소자 어레이를 재건.

51
00:02:43,900 --> 00:02:48,410
>> 의 최악의 실행 시간
일종의 병합 N 시간은 N 로그인합니다.

52
00:02:48,410 --> 00:02:52,390
우리는 N의 요소를 가지고 있지만
이 재결합 과정

53
00:02:52,390 --> 00:02:56,960
로그인 걸립니다 N 단계를 얻기 위해
전체 배열에 백업합니다.

54
00:02:56,960 --> 00:03:01,160
시간을 실행하는 가장 좋은 경우는 N 로그입니다
N이 과정은 정말하지 않기 때문에

55
00:03:01,160 --> 00:03:04,090
배열 여부 관심
분류 여부와 함께 시작합니다.

56
00:03:04,090 --> 00:03:07,590
프로세스는 거기, 동일
단락 회로 일 수있는 방법이 없습니다.

57
00:03:07,590 --> 00:03:11,610
그래서 N 최악의 경우 N 로그
n은 최상의 경우에 로그 n.

58
00:03:11,610 --> 00:03:13,960
>> 우리는 두 가지에 대해 이야기
알고리즘 찾고.

59
00:03:13,960 --> 00:03:16,230
그래서 선형 검색을 반복하는에 관한 것입니다.

60
00:03:16,230 --> 00:03:19,500
우리는 배열에 걸쳐 진행
한 번, 왼쪽에서 오른쪽으로,

61
00:03:19,500 --> 00:03:21,950
수를 찾기 위해 노력
것을 우리는 찾고 있습니다.

62
00:03:21,950 --> 00:03:24,550
최악의 실행 시간은 N의 큰 O입니다.

63
00:03:24,550 --> 00:03:27,610
그것은 반복 우리가 걸릴 수 있습니다
모든 단일 요소를 통해

64
00:03:27,610 --> 00:03:30,660
우리가 찾고있는 요소를 찾을 수
대, 중 마지막 위치에서,

65
00:03:30,660 --> 00:03:31,630
또는 전혀.

66
00:03:31,630 --> 00:03:34,720
그러나 우리는 때까지 확신 할 수 없습니다
우리는 모든 것을 살펴 보았다.

67
00:03:34,720 --> 00:03:36,730
최선의 경우를 M, 우리는 즉시 찾을 수 있습니다.

68
00:03:36,730 --> 00:03:41,060
가장 좋은 경우의 실행 시간
선형 검색 1의 오메가입니다.

69
00:03:41,060 --> 00:03:43,689
>> 마지막으로, 이진 검색은 있었다
이는 모듬 배열이 필요합니다.

70
00:03:43,689 --> 00:03:45,605
즉 아주의 기억
중요한 고려 사항

71
00:03:45,605 --> 00:03:47,155
이진 검색 작업을 할 때.

72
00:03:47,155 --> 00:03:50,180
그것은 그건 ...를 사용하는 전제 조건이다
당신을 찾고있는 배열

73
00:03:50,180 --> 00:03:52,160
분류해야합니다.

74
00:03:52,160 --> 00:03:54,500
그렇지 않으면, 키워드
분할 및 정복이다.

75
00:03:54,500 --> 00:03:58,310
절반에 배열을 분할하고
요소의 절반을 제거

76
00:03:58,310 --> 00:04:00,780
때마다 당신은을 통해 진행으로.

77
00:04:00,780 --> 00:04:04,330
이 때문에 분할과 정복의
반 접근 방식에서 분할 것들

78
00:04:04,330 --> 00:04:07,450
최악의 실행 시간
이진 검색입니다

79
00:04:07,450 --> 00:04:11,730
실질적으로, 이는 N 로그
선형 검색의 n보다 더 나은.

80
00:04:11,730 --> 00:04:13,570
가장 좋은 경우의 실행 시간은 여전히​​ 하나입니다.

81
00:04:13,570 --> 00:04:17,010
>> 우리는 즉시 그것을 찾을 수 있습니다
처음으로 우리는 분열을 만들지 만,

82
00:04:17,010 --> 00:04:19,339
다시, 그 기억
이진 검색은 있지만

83
00:04:19,339 --> 00:04:24,030
선형 검색보다 훨씬 더
로그 인의 미덕에 의해 N N 대,

84
00:04:24,030 --> 00:04:27,110
당신은 일을 통해 이동해야 할 수도 있습니다
먼저 배열을 정렬한다

85
00:04:27,110 --> 00:04:32,010
따라서 덜 효과​​적 만들 수도 있습니다
분류 반복하는의 크기에.

86
00:04:32,010 --> 00:04:35,250
>> 내가 더그 로이드 해요,이 CS50입니다.

87
00:04:35,250 --> 00:04:36,757