1
00:00:00,000 --> 00:00:04,419
>> [음악 재생]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG 로이드 : 좋아, 그럼 병합
종류는 또 다른 알고리즘

4
00:00:08,460 --> 00:00:11,200
우리는 밖으로 정렬하는 데 사용할 수있는
배열 요소.

5
00:00:11,200 --> 00:00:14,480
우리가 볼 수 그러나, 그것은있어
아주 근본적인 차이

6
00:00:14,480 --> 00:00:17,850
선택 정렬, 버블에서
정렬 및 삽입 정렬

7
00:00:17,850 --> 00:00:20,280
그게 정말 꽤 영리합니다.

8
00:00:20,280 --> 00:00:24,290
>> 병합의 기본 개념
일종의 작은 배열을 정렬하는 것입니다

9
00:00:24,290 --> 00:00:27,430
다음 그 배열을 결합
함께, 또는 them-- 병합

10
00:00:27,430 --> 00:00:31,440
따라서 정렬 된 순서로 name--.

11
00:00:31,440 --> 00:00:34,230
종류 않습니다 병합 방법
이 도구를 활용하는 것입니다

12
00:00:34,230 --> 00:00:37,290
무엇이다, 재귀 호출
우리는 곧에 대해 이야기 할거야

13
00:00:37,290 --> 00:00:39,720
하지만 우리가 정말 아직 이야기하지 않았습니다.

14
00:00:39,720 --> 00:00:43,010
>> 여기에 병합 정렬의 기본 생각이다.

15
00:00:43,010 --> 00:00:46,320
어레이의 좌측 절반을 정렬
N을 가정하면 1보다 크다.

16
00:00:46,320 --> 00:00:49,980
그리고 내가 말할 때 무엇을 의미
N을 가정하면, 1은보다 큰

17
00:00:49,980 --> 00:00:53,970
나는 우리가 동의 할 수 있다고 생각 배열하는 경우
단 하나의 요소로 구성되어,

18
00:00:53,970 --> 00:00:54,680
그것은 분류입니다.

19
00:00:54,680 --> 00:00:56,560
우리는 실제로 필요하지 않습니다
여기에 아무것도 할 수 있습니다.

20
00:00:56,560 --> 00:00:58,059
우리는 단지 그것을 정렬 할 선언 할 수 있습니다.

21
00:00:58,059 --> 00:01:00,110
그것은 오직 하나의 요소이다.

22
00:01:00,110 --> 00:01:03,610
>> 그래서 의사는 다시이며,
어레이의 좌측 절반을 정렬

23
00:01:03,610 --> 00:01:08,590
다음 오른쪽 절반 배열 정렬
다음 함께 두 부분을 병합합니다.

24
00:01:08,590 --> 00:01:11,040
지금, 이미 당신은 수 있습니다
생각, 그것은 종류의 단지

25
00:01:11,040 --> 00:01:14,080
짓이야 당신이 연기하고있는 것처럼 소리
당신은 실제로 아무것도 아닙니다.

26
00:01:14,080 --> 00:01:16,330
당신은 왼쪽으로 정렬 말을하는지
절반은 오른쪽 절반을 정렬

27
00:01:16,330 --> 00:01:19,335
하지만 당신은 이야기하지 않을
내가 어떻게 그 일을하고 있습니다.

28
00:01:19,335 --> 00:01:22,220
>> 그러나만큼 기억
배열은 하나의 요소이다,

29
00:01:22,220 --> 00:01:23,705
우리는 분류 선언 할 수 있습니다.

30
00:01:23,705 --> 00:01:25,330
그런 다음 우리는 단지 그들을 함께 결합 할 수 있습니다.

31
00:01:25,330 --> 00:01:27,788
그리고 그 사실이다
병합 정렬 뒤에 기본적인 아이디어,

32
00:01:27,788 --> 00:01:31,150
그래서 그것을 파괴하는 것입니다
당신의 배열의 크기는 하나입니다.

33
00:01:31,150 --> 00:01:33,430
그리고 당신은 거기에서 다시.

34
00:01:33,430 --> 00:01:35,910
>> 일종의 확실히 병합
복잡한 알고리즘.

35
00:01:35,910 --> 00:01:38,210
그리고 또한 리틀
시각화 복잡한.

36
00:01:38,210 --> 00:01:41,870
그래서 희망, 시각화가 나는
당신이 함께 따라 도움이 여기에 있습니다.

37
00:01:41,870 --> 00:01:45,640
그리고 나는 일을 서술하기 위해 최선을 다할 것입니다
이 조금 더를 진행

38
00:01:45,640 --> 00:01:49,180
천천히 다른 것보다
다만 희망이 당신의 머리를 얻을 수 있습니다

39
00:01:49,180 --> 00:01:51,800
병합 정렬 뒤에 아이디어 주변.

40
00:01:51,800 --> 00:01:54,680
>> 그래서 우리는 같은 배열이
다른 정렬 알고리즘 비디오

41
00:01:54,680 --> 00:01:57,120
당신이 본 한 경우 them--
여섯 요소 배열.

42
00:01:57,120 --> 00:02:02,110
그리고 여기에 우리의 의사 코드는 일종의
왼쪽 절반은 오른쪽 절반을 정렬

43
00:02:02,110 --> 00:02:03,890
함께 두 부분을 병합합니다.

44
00:02:03,890 --> 00:02:09,770
그럼이 매우 어두운 벽돌 빨간색 보자
배열과 그것의 왼쪽 절반을 정렬 할 수 있습니다.

45
00:02:09,770 --> 00:02:13,380
>> 당분간 그래서, 우리는거야
오른쪽에있는 물건을 무시합니다.

46
00:02:13,380 --> 00:02:15,740
그것은이있다, 그러나 우리는있어
아직 그 단계에서.

47
00:02:15,740 --> 00:02:18,220
우리 아니에요의 종류
배열의 오른쪽 절반.

48
00:02:18,220 --> 00:02:21,037
우리는 종류의 왼쪽에있어
배열의 절반입니다.

49
00:02:21,037 --> 00:02:22,870
그리고 바로 위하여
조금 더 인

50
00:02:22,870 --> 00:02:26,480
분명, 그래서 참조 할 수 있습니다
어떤 단계로 우리가있어,

51
00:02:26,480 --> 00:02:29,800
나는 전환거야
오렌지에이 세트의 색상.

52
00:02:29,800 --> 00:02:33,190
이제, 우리는 여전히 대해 얘기
원래 배열의 같은 왼쪽 절반.

53
00:02:33,190 --> 00:02:38,520
하지만 내가 할 수있는 의해 그 바라고 있어요
다양한 항목의 색상을 참조하십시오

54
00:02:38,520 --> 00:02:40,900
그것은 좀 더 만들어 줄게
여기에 무슨 일이 일어나고 있는지 취소합니다.

55
00:02:40,900 --> 00:02:43,270
>> 좋아, 그럼 지금 우리가
세 가지 요소의 배열.

56
00:02:43,270 --> 00:02:46,420
우리는이의 왼쪽 절반을 정렬하려면 어떻게
아직이 단계 배열?

57
00:02:46,420 --> 00:02:49,400
우리는 왼쪽으로 정렬하려는
벽돌 빨간색 array--의 절반

58
00:02:49,400 --> 00:02:52,410
왼쪽 절반의
지금은 오렌지 색깔했습니다.

59
00:02:52,410 --> 00:02:54,840
>> 음, 우리는 시도 할 수
다시이 과정을 반복합니다.

60
00:02:54,840 --> 00:02:56,756
그래서 우리는 여전히있어
정렬 노력의 중간

61
00:02:56,756 --> 00:02:58,700
전체 배열의 왼쪽 절반.

62
00:02:58,700 --> 00:03:00,450
의 좌측 절반
배열, 난 그냥 갈거야

63
00:03:00,450 --> 00:03:03,910
임의로 결정하는 그 왼쪽 절반
오른쪽 절반보다 작은 것입니다,

64
00:03:03,910 --> 00:03:06,550
이 일이 있기 때문에
세 가지 요소로 구성되어 있습니다.

65
00:03:06,550 --> 00:03:11,260
>> 그래서 나는 그 말을거야
좌측 절반 어레이의 좌측 절반

66
00:03:11,260 --> 00:03:14,050
단지 요소 다섯 가지입니다.

67
00:03:14,050 --> 00:03:18,360
다섯, 하나의 요소 인
배열, 우리는 그것을 정렬하는 방법을 알고있다.

68
00:03:18,360 --> 00:03:21,615
그리고 다섯은 정렬됩니다.

69
00:03:21,615 --> 00:03:22,990
우리는 단지 그것을 선언 할 것입니다.

70
00:03:22,990 --> 00:03:24,890
그것은 하나의 요소 배열입니다.

71
00:03:24,890 --> 00:03:29,015
>> 그래서 지금 우리가 분류 한
왼쪽 반쪽은 왼쪽 절반

72
00:03:29,015 --> 00:03:33,190
또는 오히려, 우리가 분류 한
오렌지의 왼쪽 절반.

73
00:03:33,190 --> 00:03:37,970
그래서 지금, 순서에 아직 완료
전체 배열의 왼쪽 절반,

74
00:03:37,970 --> 00:03:43,481
우리는 오른쪽 절반을 정렬 할 필요가
오렌지, 또는이 물건.

75
00:03:43,481 --> 00:03:44,230
우리는 어떻게해야합니까?

76
00:03:44,230 --> 00:03:45,930
음, 우리는 두 요소 배열을 가지고있다.

77
00:03:45,930 --> 00:03:50,470
그래서 우리는 왼쪽 절반을 정렬 할 수 있습니다
두 인 배열의.

78
00:03:50,470 --> 00:03:52,090
두 사람은 하나의 요소이다.

79
00:03:52,090 --> 00:03:55,890
그래서 기본적으로 분류합니다.
그 다음 우리는 오른쪽 절반을 정렬 할 수 있습니다

80
00:03:55,890 --> 00:03:58,530
배열, 하나의 부분.

81
00:03:58,530 --> 00:04:00,210
즉, 기본적으로 일종의이다.

82
00:04:00,210 --> 00:04:03,610
>> 이것은 이제 처음
우리는 병합 단계에 도달했습니다.

83
00:04:03,610 --> 00:04:06,135
우리는 있지만, 완료
우리는 지금 가지 down-- 내포하고

84
00:04:06,135 --> 00:04:08,420
그것은 까다로운의 일종
재귀와 일이며,

85
00:04:08,420 --> 00:04:10,930
당신은 당신을 유지할 필요
우리가 어디에 대해 머리.

86
00:04:10,930 --> 00:04:15,560
그래서 우리는 왼쪽으로 정렬했습니다
주황색 부분의 절반.

87
00:04:15,560 --> 00:04:21,280
>> 그리고 지금, 우리는 정렬의 중간에있어
주황색 부분의 오른쪽 절반.

88
00:04:21,280 --> 00:04:25,320
그리고 그 과정에서 우리는
단계에있을 지금에 대한,

89
00:04:25,320 --> 00:04:27,850
함께 두 부분을 병합합니다.

90
00:04:27,850 --> 00:04:31,700
우리는 두 부분을 볼 때
배열, 우리는 둘 중 하나를 참조하십시오.

91
00:04:31,700 --> 00:04:33,880
어떤 요소는 작은?

92
00:04:33,880 --> 00:04:35,160
하나.

93
00:04:35,160 --> 00:04:36,760
>> 그리고 어떤 요소가 작다?

94
00:04:36,760 --> 00:04:38,300
음, 두 개 또는 아무것도입니다.

95
00:04:38,300 --> 00:04:39,910
그래서 두 가지입니다.

96
00:04:39,910 --> 00:04:43,690
그래서 지금, 그냥 다시 프레임합니다
우리가 상황에있는 경우,

97
00:04:43,690 --> 00:04:48,230
우리가 분류 한
오렌지의 왼쪽 절반

98
00:04:48,230 --> 00:04:49,886
원점의 오른쪽 절반.

99
00:04:49,886 --> 00:04:52,510
나는 색상을 변경했습니다 알고
우리가 어디 다시,하지만입니다.

100
00:04:52,510 --> 00:04:54,676
그리고 그 이유는 내가 이런 짓을
이 프로세스이기 때문이다

101
00:04:54,676 --> 00:04:57,870
아래로 반복, 계속 것.

102
00:04:57,870 --> 00:05:00,500
우리는 왼쪽으로 정렬했습니다
전 오렌지의 절반

103
00:05:00,500 --> 00:05:02,590
과 전 오렌지의 오른쪽 절반.

104
00:05:02,590 --> 00:05:05,620
>> 이제, 우리는 사람들을 병합해야
함께 너무 두 반쪽.

105
00:05:05,620 --> 00:05:07,730
그것은 우리가에있어 단계입니다.

106
00:05:07,730 --> 00:05:11,440
그래서 우리는 모두를 고려
지금 녹색 요소,

107
00:05:11,440 --> 00:05:12,972
원래 배열의 왼쪽 절반.

108
00:05:12,972 --> 00:05:14,680
그리고 우리는 그 병합
동일한 공정을 사용하여

109
00:05:14,680 --> 00:05:18,660
우리는 두 가지를 병합했다
하나 잠시 전.

110
00:05:18,660 --> 00:05:23,080
>> 좌측 절반, 작은
왼쪽 절반 요소는 다섯 가지입니다.

111
00:05:23,080 --> 00:05:25,620
가장 작은 요소에
오른쪽 절반은 하나입니다.

112
00:05:25,620 --> 00:05:27,370
그 중 어느 작은?

113
00:05:27,370 --> 00:05:29,260
하나.

114
00:05:29,260 --> 00:05:32,250
>> 가장 작은 요소에
왼쪽 절반은 다섯이다.

115
00:05:32,250 --> 00:05:35,540
가장 작은 요소에
오른쪽 절반은 두개이다.

116
00:05:35,540 --> 00:05:36,970
작은은 무엇입니까?

117
00:05:36,970 --> 00:05:38,160
두.

118
00:05:38,160 --> 00:05:41,540
그리고 마지막으로 다섯
아무것도, 우리는 다섯 가지를 말할 수있다.

119
00:05:41,540 --> 00:05:43,935
>> 좋아, 그럼 큰 그림,하자
잠시 휴식을 취할

120
00:05:43,935 --> 00:05:46,080
우리가 어디에서 알아.

121
00:05:46,080 --> 00:05:48,580
우리는에서 시작하는 경우
맨 처음, 우리

122
00:05:48,580 --> 00:05:51,640
지금은 완료
전체 배열 단지

123
00:05:51,640 --> 00:05:53,810
여기 의사 코드의 한 단계.

124
00:05:53,810 --> 00:05:56,645
우리는 분류 한
배열의 왼쪽 절반.

125
00:05:56,645 --> 00:05:59,490
>> 원래 리콜
순서는 다섯, 둘, 하나.

126
00:05:59,490 --> 00:06:02,570
이 과정을 통해 이동하여
아래 중첩과 반복,

127
00:06:02,570 --> 00:06:05,990
분해 문제를 계속
아래로 더 작은 부분으로,

128
00:06:05,990 --> 00:06:09,670
우리는 지금 완료
의사 코드들 중 하나는 단계

129
00:06:09,670 --> 00:06:13,940
전체 시작 배열.

130
00:06:13,940 --> 00:06:16,670
우리는 그것의 왼쪽 절반을 분류했다.

131
00:06:16,670 --> 00:06:18,670
>> 그래서 지금의이 정지 할 수 있습니다.

132
00:06:18,670 --> 00:06:23,087
그리고 지금의 오른쪽을 정렬 할 수 있습니다
원래 배열의 절반입니다.

133
00:06:23,087 --> 00:06:25,670
그리고 우리가 그렇게 할거야
같은 반복을 통해 진행

134
00:06:25,670 --> 00:06:30,630
물건을 분해의 과정
다음 그들을 함께 병합.

135
00:06:30,630 --> 00:06:34,290
>> 그래서 왼쪽 절반
적색, 혹은 좌측 절반

136
00:06:34,290 --> 00:06:38,830
원래의 오른쪽 절반
배열, 내가 말할거야 세 가지입니다.

137
00:06:38,830 --> 00:06:40,312
다시 말하지만, 나는 여기에 일관되고 있어요.

138
00:06:40,312 --> 00:06:42,020
당신은 홀수가있는 경우
요소 수, 그것을

139
00:06:42,020 --> 00:06:44,478
정말인지는 중요하지 않습니다
당신은 왼쪽으로 한 작게

140
00:06:44,478 --> 00:06:45,620
또는 오른쪽으로 한 작은.

141
00:06:45,620 --> 00:06:49,230
>> 중요한 것은 때마다 당신을 그
수행에서이 문제가 발생

142
00:06:49,230 --> 00:06:51,422
병합, 당신은 일치해야합니다.

143
00:06:51,422 --> 00:06:53,505
당신도 항상 필요
왼쪽 작게

144
00:06:53,505 --> 00:06:55,421
또는 항상 확인해야합니다
우측 작다.

145
00:06:55,421 --> 00:06:57,720
여기에, 나는 항상로 선택했습니다
왼쪽 작게

146
00:06:57,720 --> 00:07:04,380
때 내 배열 또는 내
서브 어레이는 홀수 크기이다.

147
00:07:04,380 --> 00:07:07,420
>> 세 가지가 하나의 요소이다,
그래서 그것은 정렬됩니다.

148
00:07:07,420 --> 00:07:10,860
우리는 가정을 활용 한
우리의 전 과정에 걸쳐 지금까지.

149
00:07:10,860 --> 00:07:15,020
그래서 지금의 오른쪽을 정렬 할 수 있습니다
우측 절반의 반,

150
00:07:15,020 --> 00:07:18,210
또는 적색의 오른쪽 절반.

151
00:07:18,210 --> 00:07:20,390
>> 다시 말하지만, 우리는이를 분리해야합니다.

152
00:07:20,390 --> 00:07:21,910
이것은 단일 소자 어레이 아니다.

153
00:07:21,910 --> 00:07:23,970
우리는 분류 선언 할 수 없습니다.

154
00:07:23,970 --> 00:07:27,060
그래서 첫째, 우리는거야
왼쪽 절반을 정렬합니다.

155
00:07:27,060 --> 00:07:31,620
>> 좌측 절반은 하나의 원소이며,
그래서 기본적으로 일종의이다.

156
00:07:31,620 --> 00:07:34,840
그 다음 우리는 권리를 정렬 할거야
하나의 요소이다 절반.

157
00:07:34,840 --> 00:07:41,250
그것은 기본적으로 분류합니다. 그리고 지금,
우리는 함께 그 두 가지를 병합 할 수 있습니다.

158
00:07:41,250 --> 00:07:45,820
포는 작고,
다음 여섯 작다.

159
00:07:45,820 --> 00:07:48,870
>> 다시, 무엇을 우리는이 시점에서 짓을 한거야?

160
00:07:48,870 --> 00:07:52,512
우리는 왼쪽으로 정렬했습니다
오른쪽 절반의 절반입니다.

161
00:07:52,512 --> 00:07:54,720
아니면 원래로 돌아 가지
거기 색상,

162
00:07:54,720 --> 00:07:57,875
우리는 왼쪽으로 정렬했습니다
부드러운 빨간색의 절반입니다.

163
00:07:57,875 --> 00:08:00,416
그것은 원래 어두운 벽돌했다
빨간색과 지금은 부드러운 빨간색이다,

164
00:08:00,416 --> 00:08:02,350
아니면 부드러운 빨간색이었다.

165
00:08:02,350 --> 00:08:05,145
>> 그리고 우리가 분류 한
부드러운 빨간색의 오른쪽 절반.

166
00:08:05,145 --> 00:08:08,270
지금은, 글쎄, 그들은 단지, 다시 녹색있어
우리는 과정을 통해려고하고 있기 때문이다.

167
00:08:08,270 --> 00:08:10,720
그리고 우리는 반복해야
이 반복해서.

168
00:08:10,720 --> 00:08:14,695
>> 그래서 지금 우리는 사람들을 병합 할 수 있습니다
두 개의 반쪽.

169
00:08:14,695 --> 00:08:15,820
그리고 우리가 여기서 할거야.

170
00:08:15,820 --> 00:08:17,653
검은 선 그러니
좌측 절반을 나누어

171
00:08:17,653 --> 00:08:19,690
이 정렬 부의 우측 절반.

172
00:08:19,690 --> 00:08:24,310
>> 우리는 작은 값을 비교
array-- 왼쪽

173
00:08:24,310 --> 00:08:26,710
또는 실례합니다, 작은
좌측 절반의 값

174
00:08:26,710 --> 00:08:30,790
오른쪽의 가장 작은 값
절반은 세 가지가 작은 것을 찾을 수 있습니다.

175
00:08:30,790 --> 00:08:32,530
그리고 지금 최적화의 비트, 오른쪽?

176
00:08:32,530 --> 00:08:35,175
아무것도 실제로 없습니다
왼쪽에 왼쪽.

177
00:08:35,175 --> 00:08:37,440
>> 나머지 아무것도
왼쪽,

178
00:08:37,440 --> 00:08:40,877
그래서 우리는 효율적으로 할 수 있습니다
단지 우리가 선언 할 수 있습니다 난 그러고

179
00:08:40,877 --> 00:08:42,960
그 나머지는 실제로
정렬 그냥 압정

180
00:08:42,960 --> 00:08:45,126
아무것도 없기 때문에,에
에 대해 비교하는 다른.

181
00:08:45,126 --> 00:08:49,140
그리고 우리가 알고있는 오른쪽은
오른쪽으로 정렬됩니다.

182
00:08:49,140 --> 00:08:52,770
>> 좋아, 그럼 이제 다시 동결하자
우리가 이야기에있는 곳을 파악.

183
00:08:52,770 --> 00:08:56,120
전체 배열에서,
우리는 무엇을 성취 했는가?

184
00:08:56,120 --> 00:08:58,790
우리는 실제로 달성 한
이제 한 단계 두 단계를 반복합니다.

185
00:08:58,790 --> 00:09:03,300
우리는 왼쪽 절반을 분류하고,
우리는 오른쪽 절반을 분류.

186
00:09:03,300 --> 00:09:08,210
>> 그래서 지금, 남아있는 모든 우리를 위해입니다
함께 두 반쪽을 병합합니다.

187
00:09:08,210 --> 00:09:11,670
그래서 우리는 가장 낮은 값 비교
배열의 각 절반의 요소

188
00:09:11,670 --> 00:09:13,510
차례로 진행합니다.

189
00:09:13,510 --> 00:09:16,535
하나는 세 미만이므로 하나 간다.

190
00:09:16,535 --> 00:09:19,770
>> 두 세 미만이므로 두 간다.

191
00:09:19,770 --> 00:09:22,740
5 세 미만이므로, 세 간다.

192
00:09:22,740 --> 00:09:25,820
네 5 이하이므로, 네 간다.

193
00:09:25,820 --> 00:09:30,210
이어서 다섯, 여섯 미만인
여섯이 모두 남아 있습니다.

194
00:09:30,210 --> 00:09:31,820
>> 지금, 나는 알고있다, 그 많은 단계이었다.

195
00:09:31,820 --> 00:09:33,636
그리고 우리는 많이 떠 났어요
우리의 여파로 메모리.

196
00:09:33,636 --> 00:09:35,260
그리고 그 회색 사각형이 무엇인지입니다.

197
00:09:35,260 --> 00:09:40,540
그했다처럼 그리고 그것은 아마 느꼈다
삽입 정렬 이상 많은 거품

198
00:09:40,540 --> 00:09:42,660
종류, 또는 선택 정렬.

199
00:09:42,660 --> 00:09:45,330
>> 그러나 실제로 때문에
이러한 프로세스의 많은

200
00:09:45,330 --> 00:09:48,260
같은 time--에서 일어나고있는
이는 다시, 우리는거야 뭔가

201
00:09:48,260 --> 00:09:51,100
우리가 이야기 할 때 이야기
미래에 재귀 video--

202
00:09:51,100 --> 00:09:53,799
실제로이 알고리즘
분명히 근본적

203
00:09:53,799 --> 00:09:55,590
무엇보다 다른
우리는 전에 본

204
00:09:55,590 --> 00:09:58,820
하지만 크게도
더 효율적입니다.

205
00:09:58,820 --> 00:09:59,532
>> 그 이유는 무엇입니까?

206
00:09:59,532 --> 00:10:01,240
음, 최악의
시나리오, 우리가

207
00:10:01,240 --> 00:10:04,830
N 요소를 분할하려면
다음을 재결합.

208
00:10:04,830 --> 00:10:06,680
그러나 우리는 재결합 할 때
그들은 우리가하고있는

209
00:10:06,680 --> 00:10:11,110
기본적으로 두 배로 증가
작은 배열의 크기입니다.

210
00:10:11,110 --> 00:10:14,260
우리는 하나의 요소의 무리가
배열이 우리 효과적으로

211
00:10:14,260 --> 00:10:16,290
두 요소의 배열로 결합한다.

212
00:10:16,290 --> 00:10:18,590
그리고 우리는 그을
두 소자 어레이

213
00:10:18,590 --> 00:10:21,890
과에 함께 그들을 결합
그래서 네 소자 어레이 및,

214
00:10:21,890 --> 00:10:26,130
등, 등, 우리까지
단일 N 소자 어레이를 가지고있다.

215
00:10:26,130 --> 00:10:29,910
>> 그러나 얼마나 많은 분열
이 n으로 얻을 걸리나요?

216
00:10:29,910 --> 00:10:31,460
다시 전화 번호부 예를 생각합니다.

217
00:10:31,460 --> 00:10:34,490
얼마나 많은 시간을 우리가 눈물을해야합니까
반에있는 전화 번호부, 얼마나 더 많은

218
00:10:34,490 --> 00:10:38,370
시간은 우리가 전화 번호부를 찢어해야합니까
반, 만약 전화 번호부의 크기

219
00:10:38,370 --> 00:10:39,680
두 배?

220
00:10:39,680 --> 00:10:41,960
단 하나, 바로 거기에?

221
00:10:41,960 --> 00:10:45,360
>> 그래서 어떤 종류의있다
여기 대수 요소입니다.

222
00:10:45,360 --> 00:10:48,590
그러나 우리는 여전히해야 할 최소
n 개의 모든 요소를​​ 살펴 보자.

223
00:10:48,590 --> 00:10:53,860
최악의 경우의 시나리오에 따라서
종류 N 로그 N에서 실행 병합합니다.

224
00:10:53,860 --> 00:10:56,160
우리는 봐야
N 개의 요소 모두,

225
00:10:56,160 --> 00:11:02,915
우리는 그것들을 결합해야
함께 로그 N 단계의 세트에서.

226
00:11:02,915 --> 00:11:05,290
최선의 시나리오에서,
배열이 완벽하게 정렬됩니다.

227
00:11:05,290 --> 00:11:06,300
잘 됐네요.

228
00:11:06,300 --> 00:11:09,980
그러나 알고리즘을 기반으로 우리는 여기에있다
우리는 여전히 분할과 재결합해야합니다.

229
00:11:09,980 --> 00:11:13,290
이 경우 비록
재결합은 비효율적 가지입니다.

230
00:11:13,290 --> 00:11:14,720
그것은 필요하지 않습니다.

231
00:11:14,720 --> 00:11:17,580
그러나 우리는 여전히 통과
어쨌든 전체 과정.

232
00:11:17,580 --> 00:11:21,290
>> 최상의 경우에 따라서
최악의 경우에,

233
00:11:21,290 --> 00:11:24,970
이 알고리즘은 N 로그 N 시간에 실행됩니다.

234
00:11:24,970 --> 00:11:29,130
일종의 병합 확실히 조금 까다 롭습니다
다른 주요 정렬 알고리즘보다

235
00:11:29,130 --> 00:11:33,470
우리는 CS50에 대해 이야기 일 뿐이다했습니다
실질적으로 더 강력한.

236
00:11:33,470 --> 00:11:35,400
>> 만약 그렇다면 당신은 이제까지 발견
기회는 그것을 필요로하는

237
00:11:35,400 --> 00:11:38,480
또는 정렬을 사용하는
대용량 데이터 세트, 점점

238
00:11:38,480 --> 00:11:41,940
재귀의 아이디어의 주위에 당신의 머리
정말 강력한 될 것입니다.

239
00:11:41,940 --> 00:11:45,270
그리고 그것은 만들 것 당신의
프로그램 정말 훨씬 더 효율적

240
00:11:45,270 --> 00:11:48,700
아무것도 대 정렬 병합 사용.

241
00:11:48,700 --> 00:11:49,640
나는 더그 로이드입니다.

242
00:11:49,640 --> 00:11:51,970
이 CS50입니다.

243
00:11:51,970 --> 00:11:53,826