1
00:00:00,000 --> 00:00:11,904
>> [음악 재생]

2
00:00:11,904 --> 00:00:12,910
>> 교수 : 좋습니다.

3
00:00:12,910 --> 00:00:16,730
이것은 CS50이고이다
일주일에 세 말.

4
00:00:16,730 --> 00:00:20,230
그래서 우리는 오늘 여기있어,하지 샌더스에
대신 WEIDNER 도서관 극장.

5
00:00:20,230 --> 00:00:23,170
그 중 내부 스튜디오입니다
하우저 스튜디오로 알려진,

6
00:00:23,170 --> 00:00:28,310
또는 우리는 스튜디오 H 말, 또는 하리라
당신이 농담을 즐길 경우, 우리는 say--,

7
00:00:28,310 --> 00:00:30,540
그것에서 실제로입니다
동급생, 마크, 온라인,

8
00:00:30,540 --> 00:00:32,420
사람들은 트위터를 통해 많은 제안했다.

9
00:00:32,420 --> 00:00:34,270
지금에 대한 멋진거야
스튜디오에서 여기에있는

10
00:00:34,270 --> 00:00:38,410
나는이 녹색으로 둘러싸여있어된다
벽, 녹색 화면 또는 크로 마키,

11
00:00:38,410 --> 00:00:43,290
그래서 CS50의 즉, 말하자면
나에게 알려지지 생산 팀,

12
00:00:43,290 --> 00:00:47,380
지금, 퍼팅 수
나를 가장 세계 어디서나,

13
00:00:47,380 --> 00:00:48,660
더 나은 또는 악화에 대한.

14
00:00:48,660 --> 00:00:51,800
>> 이제 어떻게 앞서, 문제 설정있다
두 사람은, 이번 주 당신의 손에

15
00:00:51,800 --> 00:00:53,830
하지만 문제 설정
세이 다음 주,

16
00:00:53,830 --> 00:00:56,600
당신은에 도전한다
(15)의 소위 게임

17
00:00:56,600 --> 00:00:58,960
오래된 파티 호의 그
당신은 수신 호출 수

18
00:00:58,960 --> 00:01:02,030
전체 무리가있는 아이로
아래, 슬라이드 수있는 숫자,

19
00:01:02,030 --> 00:01:05,790
왼쪽과 오른쪽, 한 차이가있다
퍼즐, 내의되는 당신

20
00:01:05,790 --> 00:01:07,840
실제로 그 퍼즐 조각을 밀어 수 있습니다.

21
00:01:07,840 --> 00:01:11,150
궁극적으로이 나타납니다
일부 반 임의의 순서로 퍼즐,

22
00:01:11,150 --> 00:01:12,940
그리고 목표이다
하단, 상단을 정렬

23
00:01:12,940 --> 00:01:16,310
하나에서, 왼쪽에서 오른쪽으로
15를 통해 모든 방법.

24
00:01:16,310 --> 00:01:19,360
>> 불행하게도, 구현
당신은 손에있을 것이다

25
00:01:19,360 --> 00:01:21,590
소프트웨어가 될 것입니다
기반이 아닌 물리적.

26
00:01:21,590 --> 00:01:25,280
당신은 실제로 작성해야 할거야
코드가있는 학생 또는 사용자 캔과

27
00:01:25,280 --> 00:01:26,760
15 게임을 재생할 수 있습니다.

28
00:01:26,760 --> 00:01:29,030
실제로, 해커에
15 게임의 판,

29
00:01:29,030 --> 00:01:32,155
당신은 도전 구현할 수있을 것입니다,
이 오래된 학교의 단지 재생

30
00:01:32,155 --> 00:01:35,010
게임, 오히려 해결
그것의, 신 모드를 구현,

31
00:01:35,010 --> 00:01:38,280
그래서, 말하자면 실제로
인간에 ​​대한 퍼즐을 해결,

32
00:01:38,280 --> 00:01:41,080
힌트를 제공함으로써,
힌트 후, 힌트 후.

33
00:01:41,080 --> 00:01:42,280
그 다음 주에 그래서 더.

34
00:01:42,280 --> 00:01:43,720
하지만 그 앞에 놓여거야.

35
00:01:43,720 --> 00:01:47,610
>> 지금은 기억이 이번 주 초
당신이 경우 우리는이 클리프 행어했다

36
00:01:47,610 --> 00:01:52,560
이에 우리는 정렬하고 있었다 최고
현명한는 N의 O 큰의 상한했다

37
00:01:52,560 --> 00:01:53,210
제곱.

38
00:01:53,210 --> 00:01:56,520
즉, 거품 정렬,
선택 정렬, 삽입 정렬,

39
00:01:56,520 --> 00:01:59,120
모두 상이한 반면
구현에있어서,

40
00:01:59,120 --> 00:02:03,480
실행 제곱 N에 양도
아주 최악의 경우 시간.

41
00:02:03,480 --> 00:02:06,010
그리고 우리는 일반적으로 가정
정렬 아주 최악의 경우

42
00:02:06,010 --> 00:02:08,814
한 당신의 입력입니다
완전히 거꾸로입니다.

43
00:02:08,814 --> 00:02:11,980
그리고 사실, 꽤 몇 가지 조치를 취했다
이들 각각의 알고리즘을 구현하는 방법.

44
00:02:11,980 --> 00:02:15,110
>> 이제 클래스의 끝에서
리콜, 우리는 거품 정렬을 비교

45
00:02:15,110 --> 00:02:19,390
다른 하나에 대한 선택의 종류에 대하여
것을 우리는 시간에 병합 정렬라고

46
00:02:19,390 --> 00:02:22,120
나는 그것을 복용하는 것이 제안
주에서 수업의 장점

47
00:02:22,120 --> 00:02:24,060
제로, 분할 및 정복.

48
00:02:24,060 --> 00:02:28,810
그리고 어떻게 든 어떤 종류의 달성
로그 궁극적으로 시간을 실행,

49
00:02:28,810 --> 00:02:31,024
대신 무엇인가
즉 순수하게 차있다.

50
00:02:31,024 --> 00:02:33,440
그리고 그것은 매우 로그 아니다
그것보다 조금 더.

51
00:02:33,440 --> 00:02:36,520
하지만이 클래스에서 호출하면,
그것은 훨씬 더 빨리, 훨씬이었다.

52
00:02:36,520 --> 00:02:38,210
의 우리가 중단 된 부분을 살펴 보자.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> 선택 대 버블 정렬
정렬 병합 정렬 대.

55
00:02:45,370 --> 00:02:47,700
이제 그들은 모두, 실행중인
이론 동시에.

56
00:02:47,700 --> 00:02:50,510
CPU는 동일한 속도로 실행된다.

57
00:02:50,510 --> 00:02:54,990
하지만 당신은 어떻게 지루한이 느낄 수
매우 빠르게 될 것입니다,

58
00:02:54,990 --> 00:02:58,790
다만 얼마나 빨리, 우리는 때를 주입
주 제로의 알고리즘의 비트,

59
00:02:58,790 --> 00:03:00,080
우리는 일을 속도를 높일 수 있습니다.

60
00:03:00,080 --> 00:03:01,630
>> 그래서 마크 종류 놀랍다.

61
00:03:01,630 --> 00:03:05,220
우리는 어떻게 순서를 활용할 수
더 빨리 숫자를 정렬합니다.

62
00:03:05,220 --> 00:03:07,140
음의 다시 생각하자
성분에 그 우리

63
00:03:07,140 --> 00:03:10,380
의는 주 제로에서 다시했다
전화 번호부에있는 사람을 찾고,

64
00:03:10,380 --> 00:03:12,380
및 리콜
우리가 제안 의사,

65
00:03:12,380 --> 00:03:14,560
어떤을 통해 우리가 찾을 수 있습니다
마이크 스미스 같은 사람,

66
00:03:14,560 --> 00:03:16,310
이 같은 작은 선물을 보였다.

67
00:03:16,310 --> 00:03:20,820
>> 지금 특히 봐
라인에서도 7 및도 8, 10, 11,

68
00:03:20,820 --> 00:03:25,240
우리가 유지된다하는 그 루프를 유도
다시, 그리고 다시 3 행에 가고,

69
00:03:25,240 --> 00:03:26,520
다시.

70
00:03:26,520 --> 00:03:31,790
하지만 우리가 볼 수있는 것으로 나타났다
이 알고리즘, 여기에 의사에,

71
00:03:31,790 --> 00:03:33,620
보다 전체적으로 약간.

72
00:03:33,620 --> 00:03:35,960
사실, 내가 무엇을 찾고 있어요
여기에 화면에서,

73
00:03:35,960 --> 00:03:41,180
검색하기위한 알고리즘은
일부 페이지 세트 중 마이크 스미스.

74
00:03:41,180 --> 00:03:45,520
그리고 실제로, 우리는이 문제를 단순화 할 수
그 선 (7, 8)에서 알고리즘

75
00:03:45,520 --> 00:03:49,860
10, 11는, 이런 말을
어느 나는 노란색으로 여기에 제시했습니다.

76
00:03:49,860 --> 00:03:52,210
즉, 만약 마이크
스미스는 이전 책에

77
00:03:52,210 --> 00:03:55,004
우리는 단계를 지정할 필요가 없습니다
단계가 지금 어떻게 그를 찾아 이동합니다.

78
00:03:55,004 --> 00:03:56,920
우리는 지정할 필요가 없습니다
3 행으로 돌아갑니다,

79
00:03:56,920 --> 00:03:58,960
왜 우리가 대신하지 않습니다,
말하자면,보다 일반적으로,

80
00:03:58,960 --> 00:04:01,500
에 마이크를 검색
책의 왼쪽 절반.

81
00:04:01,500 --> 00:04:03,960
>> 반대로, 마이크인지
실제로 나중에 책,

82
00:04:03,960 --> 00:04:07,540
왜 우리는 인용을 끝내 검색을 인용하지 않습니다
이 책의 오른쪽 절반에 마이크합니다.

83
00:04:07,540 --> 00:04:11,030
즉, 왜 우리는하지 않습니다
일종의 자신이 말에 펀트,

84
00:04:11,030 --> 00:04:13,130
이에 마이크를 검색
책의 부분 집합,

85
00:04:13,130 --> 00:04:16,279
우리가 기존에두고
알고리즘은 우리에게 얘기를

86
00:04:16,279 --> 00:04:18,750
에 마이크를 검색하는 방법
책의 왼쪽 절반.

87
00:04:18,750 --> 00:04:20,750
즉, 우리
알고리즘은 작동 여부

88
00:04:20,750 --> 00:04:24,670
이의이 두께의 전화 번호부,
두께, 또는 어떠한 두께.

89
00:04:24,670 --> 00:04:27,826
그래서 우리는 반복적으로 수
이 알고리즘을 정의합니다.

90
00:04:27,826 --> 00:04:29,950
즉,에
여기에 화면이, 알고리즘

91
00:04:29,950 --> 00:04:33,130
마이크 스미스를 검색
전화 번호부의 페이지 중.

92
00:04:33,130 --> 00:04:37,410
그래서 라인 7, 10,의하자
바로 정확히 그런 말을.

93
00:04:37,410 --> 00:04:40,250
그리고 나는이 용어 잠시 사용
전, 실제로, 재귀

94
00:04:40,250 --> 00:04:42,450
화두는 지금이다
그리고이 프로세스의

95
00:04:42,450 --> 00:04:47,210
어떻게 든 의해 순환 일을의
이미이 코드를 사용하여,

96
00:04:47,210 --> 00:04:49,722
그리고, 다시 호출
다시, 다시.

97
00:04:49,722 --> 00:04:51,930
지금은 중요 할 것
우리는 어떻게 든 아래 그

98
00:04:51,930 --> 00:04:53,821
밖으로, 그리고 무한히 긴 그렇게하지 ​​않습니다.

99
00:04:53,821 --> 00:04:56,070
그렇지 않으면 우리는 갈거야
참으로 무한 루프가 있습니다.

100
00:04:56,070 --> 00:04:59,810
그러나 우리는이 아이디어를 빌릴 수 있는지 보자
재귀, 다시 일을하고

101
00:04:59,810 --> 00:05:03,600
다시 다시, 해결하기 위해
병합을 통해 정렬 문제

102
00:05:03,600 --> 00:05:05,900
정렬, 더욱 효율적으로.

103
00:05:05,900 --> 00:05:06,970
>> 그래서 나는 당신이 일종의 병합 제공합니다.

104
00:05:06,970 --> 00:05:07,920
이제 살펴 보자.

105
00:05:07,920 --> 00:05:10,850
그래서 여기에 의사가 함께한다
우리가 정렬을 구현할 수있는,

106
00:05:10,850 --> 00:05:12,640
병합 정렬이라는 알고리즘을 사용하여.

107
00:05:12,640 --> 00:05:13,880
그리고 그것은 아주 간단하게이있다.

108
00:05:13,880 --> 00:05:15,940
N 개의 요소의 입력에,
즉, 당신이 있다면

109
00:05:15,940 --> 00:05:18,830
주어진 n 개의 요소와 번호
입력되는 문자이든,

110
00:05:18,830 --> 00:05:22,430
당신은 n 개의 요소, 만약 주어진다면
n이 2 미만이며, 단지 반환한다.

111
00:05:22,430 --> 00:05:22,930
권리?

112
00:05:22,930 --> 00:05:26,430
N은 2보다 작은 경우이므로
즉, 요소​​의 마이리스트

113
00:05:26,430 --> 00:05:30,446
크기는 0 또는 1 중 하나이고,
이러한 사소한 경우 모두,

114
00:05:30,446 --> 00:05:31,570
목록이 이미 정렬됩니다.

115
00:05:31,570 --> 00:05:32,810
더리스트가없는 경우, 분류하다.

116
00:05:32,810 --> 00:05:35,185
그리고 길이의 목록이 있다면
도 1에서, 이것은 명백히 분류하다.

117
00:05:35,185 --> 00:05:38,280
그래서 알고리즘은 필요
정말 흥미로운 일을,

118
00:05:38,280 --> 00:05:40,870
우리는 두 개 이상이 있으면
요소는 우리에게 주어진.

119
00:05:40,870 --> 00:05:42,440
그럼 다음 마법을 살펴 보자.

120
00:05:42,440 --> 00:05:47,500
다른 원소의 좌측 절반을 정렬,
다음 요소의 오른쪽 절반을 정렬

121
00:05:47,500 --> 00:05:49,640
다음 정렬 절반을 병합합니다.

122
00:05:49,640 --> 00:05:52,440
그리고 굽힘 마음의 종류는 무엇입니까
여기에, 난 정말 없다는 것입니다

123
00:05:52,440 --> 00:05:56,190
당신을 말한 것 같다
아직 아무것도, 오른쪽?

124
00:05:56,190 --> 00:05:59,560
모든 I의 목록을 주어 말한
N 요소는 왼쪽 절반을 정렬

125
00:05:59,560 --> 00:06:01,800
다음 오른쪽 절반, 다음
정렬 절반을 병합,

126
00:06:01,800 --> 00:06:03,840
하지만 여기서 실제 비밀 소스는?

127
00:06:03,840 --> 00:06:05,260
이 알고리즘은 어디에 있습니까?

128
00:06:05,260 --> 00:06:09,150
그럼이 두 라인 밝혀
먼저, 요소의 종류 왼쪽 절반,

129
00:06:09,150 --> 00:06:13,970
및 요소의 종류 오른쪽 절반,
재귀 호출은, 말하자면.

130
00:06:13,970 --> 00:06:16,120
>> 결국,이에
시간에 점, 내가해야합니까

131
00:06:16,120 --> 00:06:18,950
있는하는 알고리즘
요소의 전체 무리를 정렬?

132
00:06:18,950 --> 00:06:19,450
네.

133
00:06:19,450 --> 00:06:20,620
그것은 바로 여기입니다.

134
00:06:20,620 --> 00:06:25,180
그것은 화면에 바로 여기, 그리고
그래서 나는 단계의 동일한 세트를 사용할 수 있습니다

135
00:06:25,180 --> 00:06:28,500
왼쪽 절반을 정렬하려면,
오른쪽 절반은 내가 할 수있는.

136
00:06:28,500 --> 00:06:30,420
그리고 실제로, 다시, 다시.

137
00:06:30,420 --> 00:06:34,210
그래서 어떻게 든 또는 다른, 우리는 곧거야
병합 정렬의 마법을이 참조

138
00:06:34,210 --> 00:06:37,967
바로 그 마지막에 포함
라인, 정렬 절반을 병합.

139
00:06:37,967 --> 00:06:39,300
그리고 그것은 매우 직관적 인 것 같다.

140
00:06:39,300 --> 00:06:41,050
당신은, 당신을 두 부분을 가지고 가고,
어떻게 든, 함께 병합,

141
00:06:41,050 --> 00:06:43,260
우리는이를 볼 수 있습니다
구체적으로 잠시.

142
00:06:43,260 --> 00:06:45,080
>> 그러나 이것은 전체 알고리즘이다.

143
00:06:45,080 --> 00:06:46,640
그리고의는 이유를 정확하게 볼 수 있습니다.

144
00:06:46,640 --> 00:06:50,912
그런데 우리는이 같은를 부여하고 있다고 가정
화면에 여기에 여덟 요소, 하나

145
00:06:50,912 --> 00:06:53,120
팔을 통해,하지만 그들은있어
겉으로는 임의의 순서로.

146
00:06:53,120 --> 00:06:55,320
그리고 손의 목표는
이러한 요소를 정렬합니다.

147
00:06:55,320 --> 00:06:58,280
그럼 난에 대해 어떻게 갈 수
다시 사용하여 그 일을,

148
00:06:58,280 --> 00:07:00,407
이 의사에 따라 정렬 병합?

149
00:07:00,407 --> 00:07:02,740
그리고 또,이를 물들인
당신의 마음, 단지 잠시 동안.

150
00:07:02,740 --> 00:07:05,270
첫 번째 경우는 꽤입니다
사소한,이 2 미만의 경우,

151
00:07:05,270 --> 00:07:07,060
단지 할 수 할 일이 없다, 돌아갑니다.

152
00:07:07,060 --> 00:07:09,290
그래서 정말 세 가지있다
단계는 정말 마음에 유지합니다.

153
00:07:09,290 --> 00:07:11,081
다시, 다시, 나는 해요
가지고 싶은 것

154
00:07:11,081 --> 00:07:13,980
왼쪽 절반을 정렬하려면,
오른쪽 절반을 정렬

155
00:07:13,980 --> 00:07:15,890
다음 번에 ​​그
두 부분은, 분류되어 있습니다

156
00:07:15,890 --> 00:07:18,710
나는 그들을 함께 병합 할
하나의 정렬 된 목록에.

157
00:07:18,710 --> 00:07:19,940
그래서 명심.

158
00:07:19,940 --> 00:07:21,310
>> 그래서 여기에 원래 목록입니다.

159
00:07:21,310 --> 00:07:23,510
그럼으로이 치료하자
배열, 우리가되면서

160
00:07:23,510 --> 00:07:25,800
일주일에 두, 이는입니다
메모리의 연속 블록.

161
00:07:25,800 --> 00:07:28,480
이 경우, 팔을 포함
번호는 다시 다시 다시한다.

162
00:07:28,480 --> 00:07:30,700
그리고의 지금 병합 정렬을 적용 할 수 있습니다.

163
00:07:30,700 --> 00:07:33,300
그래서 내가 먼저 정렬 할
이리스트의 좌측 절반

164
00:07:33,300 --> 00:07:37,370
그리고, 따라서하자
4, 8, 6 및 2에 초점.

165
00:07:37,370 --> 00:07:41,000
>> 지금은에 대해 어떻게 가야합니까
크기 4의리스트를 정렬?

166
00:07:41,000 --> 00:07:45,990
그럼 지금 고려해야
좌측 절반의 좌측 정렬.

167
00:07:45,990 --> 00:07:47,720
다시 말하지만, 그냥 잠시 뒤로하자.

168
00:07:47,720 --> 00:07:51,010
의사는이 경우,
나는 여덟 요소를 제공하고있어,

169
00:07:51,010 --> 00:07:53,230
8 분명히 큰
이상 또는 2와 동일.

170
00:07:53,230 --> 00:07:54,980
와 그래서 첫 번째 경우는 적용되지 않습니다.

171
00:07:54,980 --> 00:07:58,120
그래서 여덟 요소를 정렬, 내가 먼저하기
요소의 좌측 절반을 정렬

172
00:07:58,120 --> 00:08:01,930
그때 그때 병합, 오른쪽 절반을 정렬
두 개의 정렬 된 반쪽 크기 4의 각.

173
00:08:01,930 --> 00:08:02,470
그래.

174
00:08:02,470 --> 00:08:07,480
>> 당신은 그냥 나에게 이야기 한 경우에,를 정렬
지금 크기 4입니다 왼쪽 절반,

175
00:08:07,480 --> 00:08:09,350
어떻게 왼쪽 절반을 정렬합니까?

176
00:08:09,350 --> 00:08:11,430
그럼 난이있는 경우
네 가지 요소의 입력,

177
00:08:11,430 --> 00:08:14,590
내가 먼저 왼쪽으로 정렬
두, 다음 오른쪽 두,

178
00:08:14,590 --> 00:08:16,210
그리고, 나는 그들을 함께 병합합니다.

179
00:08:16,210 --> 00:08:18,700
그래서 다시, 그것은 비트가된다
마음을 여기에 게임을 굽힘

180
00:08:18,700 --> 00:08:21,450
당신 때문에, 가지,해야
당신이 이야기에 위치를 기억,

181
00:08:21,450 --> 00:08:23,620
그러나 일의 마지막
임의의 개수의 요소를 주어진

182
00:08:23,620 --> 00:08:25,620
먼저를 정렬 할
왼쪽 절반 다음 오른쪽 절반,

183
00:08:25,620 --> 00:08:26,661
다음 그들을 함께 병합합니다.

184
00:08:26,661 --> 00:08:28,630
의 정확히 그렇게 시작하자.

185
00:08:28,630 --> 00:08:30,170
여기서 여덟 요소의 입력이다.

186
00:08:30,170 --> 00:08:31,910
이제 우리는 여기에 왼쪽 절반 찾고 있습니다.

187
00:08:31,910 --> 00:08:33,720
어떻게 네 가지 요소를 정렬 할 수 있습니까?

188
00:08:33,720 --> 00:08:35,610
그럼 내가 먼저 왼쪽 절반을 정렬 할 수 있습니다.

189
00:08:35,610 --> 00:08:37,720
이제 어떻게 왼쪽 절반을 정렬합니까?

190
00:08:37,720 --> 00:08:39,419
잘 나는 두 가지 요소를 부여했습니다.

191
00:08:39,419 --> 00:08:41,240
그래서이 두 요소를 정렬 할 수 있습니다.

192
00:08:41,240 --> 00:08:44,540
2 인 이상의
2와 같은, 물론.

193
00:08:44,540 --> 00:08:46,170
그래서 첫 번째 경우는 적용되지 않습니다.

194
00:08:46,170 --> 00:08:49,010
>> 그래서 지금은 왼쪽으로 정렬해야
이 두 요소의 절반입니다.

195
00:08:49,010 --> 00:08:50,870
좌측 절반은, 물론, 단지 4이다.

196
00:08:50,870 --> 00:08:54,020
그래서 내가 어떻게 하나의 요소의 목록을 정렬 할 수 있습니까?

197
00:08:54,020 --> 00:08:57,960
글쎄 지금은, 특별한 기본 케이스
상단까지, 말하자면, 적용됩니다.

198
00:08:57,960 --> 00:09:01,470
1 미만이며, 내
목록은 참으로 크기 1입니다.

199
00:09:01,470 --> 00:09:02,747
그래서 난 그냥 돌아갑니다.

200
00:09:02,747 --> 00:09:03,580
난 아무것도하지 않습니다.

201
00:09:03,580 --> 00:09:06,770
그리고 사실, 내가했습니다 무엇을보고
일, 4는 이미 정렬됩니다.

202
00:09:06,770 --> 00:09:09,220
마찬가지로 나는 이미 해요
여기에 부분적으로 성공.

203
00:09:09,220 --> 00:09:11,750
>> 이제 그 종류의 바보 같다
주장하지만, 그것은 사실입니다.

204
00:09:11,750 --> 00:09:13,700
4 크기 1의 목록입니다.

205
00:09:13,700 --> 00:09:15,090
그것은 이미 정렬입니다.

206
00:09:15,090 --> 00:09:16,270
즉, 왼쪽 절반입니다.

207
00:09:16,270 --> 00:09:18,010
지금은 오른쪽 절반을 정렬 할 수 있습니다.

208
00:09:18,010 --> 00:09:22,310
제 8 입력, 하나의 원소이며
유사하게, 이미 정렬.

209
00:09:22,310 --> 00:09:25,170
바보, 너무, 그러나 다시,
이 기본 원칙

210
00:09:25,170 --> 00:09:28,310
우리가 지금 구축 할 수 있도록하는 것입니다
이 꼭대기에 성공적으로.

211
00:09:28,310 --> 00:09:32,260
(4)는 현재, 8 정렬, 분류
마지막 단계는 무엇인가?

212
00:09:32,260 --> 00:09:35,330
그래서 세 번째이자 마지막 단계, 어떤
시간은 당신이, 목록, 리콜을 정렬하고

213
00:09:35,330 --> 00:09:38,310
두 반쪽을 병합하는 것이 었습니다
왼쪽 및 오른쪽.

214
00:09:38,310 --> 00:09:39,900
그럼 정확히 할 수 있습니다.

215
00:09:39,900 --> 00:09:41,940
내 좌측 절반은, 물론, 4이다.

216
00:09:41,940 --> 00:09:43,310
내 오른쪽 절반은 8입니다.

217
00:09:43,310 --> 00:09:44,100
>> 그래서이 작업을 수행 할 수 있습니다.

218
00:09:44,100 --> 00:09:46,410
우선은 할당 할거야
일부 추가 메모리,

219
00:09:46,410 --> 00:09:48,680
, 내가 여기에 표현 것이다 그
단지 차 배열로,

220
00:09:48,680 --> 00:09:49,660
즉,이 들어갈만큼 크다.

221
00:09:49,660 --> 00:09:52,243
하지만 당신은 연장 상상할 수
그 사각형 전체 길이,

222
00:09:52,243 --> 00:09:53,290
우리는 더 이상 필요합니다.

223
00:09:53,290 --> 00:09:58,440
나는 4 받아 8 및 병합 어떻게
함께 크기 1의 두리스트?

224
00:09:58,440 --> 00:10:00,270
여기, 너무, 아주 간단합니다.

225
00:10:00,270 --> 00:10:03,300
4는, 먼저 8 온다.

226
00:10:03,300 --> 00:10:07,130
나는를 정렬 할 경우 때문에
왼쪽 절반 다음 오른쪽 절반,

227
00:10:07,130 --> 00:10:09,900
다음 두 반쪽을 병합
함께 정렬 된 순서로,

228
00:10:09,900 --> 00:10:11,940
4는, 먼저 8 온다.

229
00:10:11,940 --> 00:10:15,810
>> 그래서 우리는 심지어, 진전 될 것으로 보인다
나는 어떤 실제 작업을 수행하지 않은 있지만.

230
00:10:15,810 --> 00:10:17,800
우리는 이야기를 어디하지만 기억.

231
00:10:17,800 --> 00:10:19,360
우리는 원래 여덟 요소를했다.

232
00:10:19,360 --> 00:10:21,480
우리는 4 왼쪽 절반을, 분류.

233
00:10:21,480 --> 00:10:24,450
그 다음 우리는 왼쪽 절반을 정렬
2이었다 좌측 절반의.

234
00:10:24,450 --> 00:10:25,270
그리고 여기 우리는 간다.

235
00:10:25,270 --> 00:10:26,920
우리는 그 단계를 완료.

236
00:10:26,920 --> 00:10:29,930
>> 우리가 분류 한 경우에 따라서
우리는 지금, 2의 절반 왼쪽

237
00:10:29,930 --> 00:10:32,130
2의 오른쪽 절반을 정렬 할 수 있습니다.

238
00:10:32,130 --> 00:10:35,710
따라서 (2)의 오른쪽 절반은
여기에이 두 값, 6, 2.

239
00:10:35,710 --> 00:10:40,620
그래서 지금 크기의 입력을 할 수
(2) 다음의 왼쪽 절반을 정렬하고,

240
00:10:40,620 --> 00:10:42,610
우측 절반하고
함께 병합.

241
00:10:42,610 --> 00:10:45,722
그럼 어떻게 크기의 목록을 정렬 할
1, 단지 숫자 6을 포함?

242
00:10:45,722 --> 00:10:46,430
난 이미 끝났어요.

243
00:10:46,430 --> 00:10:48,680
크기 1의 목록이 정렬됩니다.

244
00:10:48,680 --> 00:10:52,140
>> 나는 또 다른 목록을 정렬하려면 어떻게
크기 1, 소위 오른쪽 절반.

245
00:10:52,140 --> 00:10:54,690
글쎄 그것은, 너무, 이미​​ 정렬됩니다.

246
00:10:54,690 --> 00:10:56,190
숫자 2는 단독이다.

247
00:10:56,190 --> 00:11:00,160
그래서 지금은 두 부분이, 왼쪽
좋아, 함께 병합 할 필요가있다.

248
00:11:00,160 --> 00:11:01,800
나 자신에게 약간의 여분의 공간을 제공 할 수 있습니다.

249
00:11:01,800 --> 00:11:05,580
그리고, 거기에 2를 넣어
다음 6 거기하여

250
00:11:05,580 --> 00:11:10,740
그 목록을 정렬, 좌우
궁극적으로, 함께 병합.

251
00:11:10,740 --> 00:11:12,160
그래서 나는 약간 더 나은 모양입니다.

252
00:11:12,160 --> 00:11:16,250
나는이 일 때문에 아니에요 분명히 4, 8, 2,
6 내가 원하는 마지막 순서가 아닙니다.

253
00:11:16,250 --> 00:11:20,640
하지만 지금은, 그 크기 2의 두 목록을
양쪽에 각각 정렬되어있다.

254
00:11:20,640 --> 00:11:24,580
그래서 지금 당신은 당신의 마음의에서 되감기 경우
눈이 곳은 우리를 떠나지 않았다?

255
00:11:24,580 --> 00:11:28,520
그때, 여덟 요소 시작 나는
, (4)의 좌측 절반으로 줄였다 아래

256
00:11:28,520 --> 00:11:31,386
다음 (2)의 왼쪽 절반 및
다음 (2)의 오른쪽 절반

257
00:11:31,386 --> 00:11:34,510
나는 왼쪽 정렬, 따라서 완료
(2)의 절반, 및 (2)의 오른쪽 절반

258
00:11:34,510 --> 00:11:37,800
그래서 세 번째와 마지막 단계는 여기에 무엇입니까?

259
00:11:37,800 --> 00:11:41,290
나는 함께 병합해야
크기 2의 두 목록.

260
00:11:41,290 --> 00:11:42,040
그래서 앞서 가자.

261
00:11:42,040 --> 00:11:43,940
그리고 여기에 화면에 제공
나 일부 추가 메모리,

262
00:11:43,940 --> 00:11:47,170
기술적으로하지만, 내가했는지 알
빈 공간까지 상단의 모두를 가지고

263
00:11:47,170 --> 00:11:47,670
가.

264
00:11:47,670 --> 00:11:50,044
나는 특히 싶은 경우
효율적인 공간 현명한,

265
00:11:50,044 --> 00:11:52,960
난 그냥 요소를 이동 시작할 수
앞뒤로, 상단과 하단.

266
00:11:52,960 --> 00:11:55,460
그러나 단지 시각적 명확성을 위해,
나는 아래를 내려 놓고거야

267
00:11:55,460 --> 00:11:56,800
친절하고 깨끗한 물건을 유지합니다.

268
00:11:56,800 --> 00:11:58,150
>> 그래서 크기 2의 두 가지 목록을 가지고있다.

269
00:11:58,150 --> 00:11:59,770
첫 번째 목록은 4와 8이 있습니다.

270
00:11:59,770 --> 00:12:01,500
두 번째 목록 2와 6이있다.

271
00:12:01,500 --> 00:12:03,950
의 그 병합하자
함께 정렬 된 순서로.

272
00:12:03,950 --> 00:12:09,910
도 2는 물론, 먼저
다음 4, 다음 (6), 다음 (8).

273
00:12:09,910 --> 00:12:12,560
그리고 지금 우리는 점점 것 같습니다
어딘가에 재미.

274
00:12:12,560 --> 00:12:15,720
의 지금은 분류 한 반
목록과 일치하여, 그건

275
00:12:15,720 --> 00:12:18,650
모든 짝수 있지만,
실제로, 단지 우연의 일치입니다.

276
00:12:18,650 --> 00:12:22,220
그리고 지금은 왼쪽 정렬 한
절반은 2, 4, 6 및 8이다되도록.

277
00:12:22,220 --> 00:12:23,430
아무것도 순서가 없습니다.

278
00:12:23,430 --> 00:12:24,620
즉 진보 것 같은 느낌이 든다.

279
00:12:24,620 --> 00:12:26,650
>> 나는 것 같은 지금은 느낌
이제 영원히 얘기,

280
00:12:26,650 --> 00:12:29,850
그래서이 경우 볼 일이다
알고리즘은 참으로, 더 효율적이다.

281
00:12:29,850 --> 00:12:31,766
그러나 우리는을 통해거야
그것은 슈퍼 질서.

282
00:12:31,766 --> 00:12:34,060
컴퓨터는 물론,
그런 식으로 할 것.

283
00:12:34,060 --> 00:12:34,840
그래서 우리는 어디인가?

284
00:12:34,840 --> 00:12:36,180
우리는 여덟 요소 시작했다.

285
00:12:36,180 --> 00:12:37,840
나는 4의 왼쪽 절반을 분류.

286
00:12:37,840 --> 00:12:39,290
나는 그와 함께 할 것 같다.

287
00:12:39,290 --> 00:12:42,535
이제 다음 단계에있다
4의 오른쪽 절반을 정렬 할 수 있습니다.

288
00:12:42,535 --> 00:12:44,410
그리고이 부분은 우리가 갈 수
좀 더를 통해

289
00:12:44,410 --> 00:12:47,140
빨리, 당신이있어 있지만
다만, 되감기 또는 일시 중지에 오신 것을 환영합니다

290
00:12:47,140 --> 00:12:49,910
그것을 통해 생각
자신의 페이스, 그러나

291
00:12:49,910 --> 00:12:53,290
우리는 지금 기회가있다
사에 동일한 알고리즘을

292
00:12:53,290 --> 00:12:54,380
다른 번호.

293
00:12:54,380 --> 00:12:57,740
>> 그래서 앞서 가자, 및 초점
우리가 여기에 오른쪽 절반,.

294
00:12:57,740 --> 00:13:01,260
그의 왼쪽 절반
오른쪽 절반, 그리고 지금

295
00:13:01,260 --> 00:13:04,560
왼쪽의 왼쪽 절반
그 오른쪽 절반의 절반,

296
00:13:04,560 --> 00:13:08,030
나는 크기의 목록을 정렬 어떻게
단지 하나의 숫자를 포함?

297
00:13:08,030 --> 00:13:09,030
그것은 이미 이루어집니다.

298
00:13:09,030 --> 00:13:11,830
나는 목록에 대한 동일한 작업을 수행하려면 어떻게
단 7을 포함하는 크기 1?

299
00:13:11,830 --> 00:13:12,840
그것은 이미 이루어집니다.

300
00:13:12,840 --> 00:13:16,790
다음이 절반 단계 세
이 두 가지 요소를 병합하는 것입니다

301
00:13:16,790 --> 00:13:20,889
크기 2, 1, 7의 새 목록에.

302
00:13:20,889 --> 00:13:23,180
모든 짓을하지 않는 것
그 많은 흥미로운 작품.

303
00:13:23,180 --> 00:13:24,346
의 다음에 어떻게되는지 보자.

304
00:13:24,346 --> 00:13:29,210
나는 단지의 왼쪽 절반을 정렬
내 원래의 입력의 오른쪽 절반.

305
00:13:29,210 --> 00:13:32,360
이제 오른쪽으로 정렬 할 수
(5)와 (3)을 포함 절반.

306
00:13:32,360 --> 00:13:35,740
의 다시 왼쪽을 살펴 보자
반, 분류, 오른쪽 절반, 분류,

307
00:13:35,740 --> 00:13:39,120
과 함께 두 병합
추가 공간으로,

308
00:13:39,120 --> 00:13:41,670
(3) 다음, 먼저 5 온다.

309
00:13:41,670 --> 00:13:46,190
그리고 지금, 우리가 분류 한
오른쪽 절반의 왼쪽 절반

310
00:13:46,190 --> 00:13:49,420
원래의 문제, 그리고
오른쪽 절반의 오른쪽 절반

311
00:13:49,420 --> 00:13:50,800
원래 문제.

312
00:13:50,800 --> 00:13:52,480
세 번째와 마지막 단계는 무엇입니까?

313
00:13:52,480 --> 00:13:54,854
그럼 함께 두 반쪽을 병합합니다.

314
00:13:54,854 --> 00:13:57,020
그래서 나 자신에게 약간의하자
다시 여분의 공간,하지만, 내가

315
00:13:57,020 --> 00:13:58,699
그 여분의 공간 구성 Top을 사용 될 수 있습니다.

316
00:13:58,699 --> 00:14:00,490
그러나 우리는 계속거야
시각적으로는 간단합니다.

317
00:14:00,490 --> 00:14:07,070
내가 지금 1에 병합하자,과
다음, (3), (5) 다음, 다음 7.

318
00:14:07,070 --> 00:14:10,740
이것으로 지금 날 떠나
원래 문제의 오른쪽 절반

319
00:14:10,740 --> 00:14:12,840
즉 완벽하게 정렬합니다.

320
00:14:12,840 --> 00:14:13,662
>> 그래서 남아?

321
00:14:13,662 --> 00:14:16,120
내가 자꾸 같은 느낌
또 다시 동일한 것들

322
00:14:16,120 --> 00:14:18,700
하지만 그 반영이다
우리는 재귀를 사용하고 있다는 사실.

323
00:14:18,700 --> 00:14:21,050
을 사용하는 과정
또 다시 알고리즘

324
00:14:21,050 --> 00:14:23,940
작은 부분 집합에
원래 문제.

325
00:14:23,940 --> 00:14:27,580
그래서 지금은 왼쪽 정렬 한
원래 문제의 절반입니다.

326
00:14:27,580 --> 00:14:30,847
나는 오른쪽 정렬 반이
원래 문제.

327
00:14:30,847 --> 00:14:32,180
세 번째와 마지막 단계는 무엇입니까?

328
00:14:32,180 --> 00:14:33,590
아, 병합입니다.

329
00:14:33,590 --> 00:14:34,480
그럼 그렇게하자.

330
00:14:34,480 --> 00:14:36,420
의 몇 가지 추가 할당하자
메모리, 그러나 나의 하나님, 우리

331
00:14:36,420 --> 00:14:37,503
지금 어디를 둘 수 있었다.

332
00:14:37,503 --> 00:14:40,356
우리는 너무 많은 공간을 사용할 수있다
우리에게, 그러나 우리는 간단하게 할 것이다.

333
00:14:40,356 --> 00:14:42,730
대신에 다시가는 및
앞으로 우리의 기존 메모리와,

334
00:14:42,730 --> 00:14:44,480
그냥 해하자
시각적으로 여기 아래에 아래로,

335
00:14:44,480 --> 00:14:47,240
합병 마무리합니다
왼쪽 절반과 오른쪽 절반.

336
00:14:47,240 --> 00:14:49,279
>> 병합하여 그래서, 어떻게해야합니까?

337
00:14:49,279 --> 00:14:50,820
나는 위해 요소를 먹고 싶어.

338
00:14:50,820 --> 00:14:53,230
그래서 왼쪽 절반을보고,
나는 첫 번째 숫자는 2 참조하십시오.

339
00:14:53,230 --> 00:14:55,230
나는 오른쪽 절반 보면,
나는 첫 번째 숫자를 참조

340
00:14:55,230 --> 00:14:58,290
그래서 당연히, 1 인
수는 내가 뽑아 싶어

341
00:14:58,290 --> 00:15:00,430
내 최종 목록에서 첫 번째 넣어?

342
00:15:00,430 --> 00:15:01,449
물론, 1.

343
00:15:01,449 --> 00:15:02,990
지금은 그 같은 질문을 할 수 있습니다.

344
00:15:02,990 --> 00:15:05,040
왼쪽 절반에, 나는했습니다
여전히 숫자 2를 얻었다.

345
00:15:05,040 --> 00:15:07,490
오른쪽 절반에,
나는 숫자 3을 가지고있다.

346
00:15:07,490 --> 00:15:08,930
어느 내가 선택 하시겠습니까?

347
00:15:08,930 --> 00:15:11,760
물론, 숫자 2와
이제 후보를 통지

348
00:15:11,760 --> 00:15:13,620
오른쪽에서 왼쪽으로, 3 상 4이다.

349
00:15:13,620 --> 00:15:15,020
의는 물론, 3을 선택할 수 있습니다.

350
00:15:15,020 --> 00:15:18,020
이제 후보는 4에있다
오른쪽에서 왼쪽으로, 5.

351
00:15:18,020 --> 00:15:19,460
우리는 물론, 4를 선택합니다.

352
00:15:19,460 --> 00:15:21,240
오른쪽에서 왼쪽으로, 5 6.

353
00:15:21,240 --> 00:15:22,730
우리는 물론, 5를 선택합니다.

354
00:15:22,730 --> 00:15:25,020
오른쪽에서 왼쪽으로, 7 (6).

355
00:15:25,020 --> 00:15:29,320
우리는 6을 선택한 다음 우리를
(7)를 선택한 다음, 우리는 (8)를 선택합니다.

356
00:15:29,320 --> 00:15:30,100
짜잔.

357
00:15:30,100 --> 00:15:34,370
>> 단어 그래서 엄청난 수의 후에, 우리
여덟 요소의 목록을 분류 한

358
00:15:34,370 --> 00:15:38,450
팔을 통해 하나의 목록으로,
즉, 각 단계에 따라 증가 있어요

359
00:15:38,450 --> 00:15:40,850
하지만 얼마나 많은 시간이했다
그것은 그렇게 우리를 데려.

360
00:15:40,850 --> 00:15:43,190
잘 나는 일부러했습니다
그림으로 누워 것들을 밖으로

361
00:15:43,190 --> 00:15:46,330
여기에, 그래서 우리가 할 수있는 종류의
참조하거나 분할을 주셔서 감사합니다

362
00:15:46,330 --> 00:15:49,060
정복에 그 일이 됐어요.

363
00:15:49,060 --> 00:15:52,830
>> 당신이 이후에 다시 보면 참으로 경우,
나는이 점선을 모두 떠 났어요

364
00:15:52,830 --> 00:15:55,660
장소 홀더에, 당신이 할 수있는,
종류의 역순으로, 참조

365
00:15:55,660 --> 00:15:58,800
당신은 가지에 다시 보면
역사 지금, 내 원래의 목록

366
00:15:58,800 --> 00:16:00,250
크기 8의 물론이다.

367
00:16:00,250 --> 00:16:03,480
그리고 이전에, 내가했다
크기 4의 두 목록을 처리,

368
00:16:03,480 --> 00:16:08,400
다음 크기 2의 네 개의 목록,
다음 크기 1의 여덟 목록.

369
00:16:08,400 --> 00:16:10,151
>> 그래서이 무엇을하는지,
종류의, 당신을 생각 나게?

370
00:16:10,151 --> 00:16:11,858
의 자, 참으로, 어떤
우리가했습니다 알고리즘

371
00:16:11,858 --> 00:16:14,430
지금까지 바라 보았다 우리가 어디
분할하고, 분할 및 분할,

372
00:16:14,430 --> 00:16:19,500
다시 일을 가지고 유지하고,
다시,이 일반적인 생각을 초래한다.

373
00:16:19,500 --> 00:16:23,100
그래서 뭔가있다
로그 여기에 무슨.

374
00:16:23,100 --> 00:16:26,790
그리고 그것은 N 꽤 로그, 아니지만
로그 구성 요소가있다

375
00:16:26,790 --> 00:16:28,280
우리가 무슨 짓을했는지에.

376
00:16:28,280 --> 00:16:31,570
>> 이제이 실제로 어떻게 생각해 보자.

377
00:16:31,570 --> 00:16:34,481
그래서 다시, N의 기록이었다
좋은 실행 시간,

378
00:16:34,481 --> 00:16:36,980
우리는 같은 것을했을 때
이진 검색, 우리가 지금 전화로,

379
00:16:36,980 --> 00:16:40,090
분할 및 정복 전략
어떤 통해 우리는 마이크 스미스를 발견했다.

380
00:16:40,090 --> 00:16:41,020
지금 기술적으로.

381
00:16:41,020 --> 00:16:43,640
즉, 심지어 N의 로그베이스 2의
대부분의 수학 수업을하지만,

382
00:16:43,640 --> 00:16:45,770
(10)는 일반적으로 가정 기지입니다.

383
00:16:45,770 --> 00:16:48,940
그러나 컴퓨터 과학자 거의 항상
생각하고베이스 2의 관점에서 이야기

384
00:16:48,940 --> 00:16:52,569
그래서 우리는 일반적으로 단지의 로그를 말한다
N, N 대신 로그베이스 (2)의,

385
00:16:52,569 --> 00:16:55,110
그러나 정확히 하나있어
컴퓨터의 세계에서 같은

386
00:16:55,110 --> 00:16:57,234
과학, 옆으로,
일정한 요인이있다

387
00:16:57,234 --> 00:17:01,070
둘 사이의 차이가 너무 재
더 공식적인 이유로, 어쨌든 논쟁.

388
00:17:01,070 --> 00:17:04,520
>> 하지만 지금, 우리는 무엇을 걱정
약이 예이다.

389
00:17:04,520 --> 00:17:08,520
그럼 예에 의해 증명하지 말고 오직에서
최소 수의 예를 사용하여

390
00:17:08,520 --> 00:17:10,730
손 전성 검사로, 경우에 당신은 것입니다.

391
00:17:10,730 --> 00:17:14,510
그래서 이전에 공식 로그 기본이었다
N 2,하지만이 경우 N은 무엇인가.

392
00:17:14,510 --> 00:17:18,526
나는 N 원래의 번호를 가지고, 또는 8
원래 숫자의 구체적.

393
00:17:18,526 --> 00:17:20,359
지금은 조금이었다
동안,하지만 난 꽤

394
00:17:20,359 --> 00:17:25,300
반드시 해당 로그베이스 2
(8)가 3의 값,

395
00:17:25,300 --> 00:17:29,630
실제로 무슨 일이 즉 약 좋네요
3 것이이 시대의 정확히 번호

396
00:17:29,630 --> 00:17:33,320
당신은 목록을 나눌 수 있음
다시, 다시 길이 8,

397
00:17:33,320 --> 00:17:36,160
다시, 당신은 남겨까지
단지 크기 1의 목록과.

398
00:17:36,160 --> 00:17:36,660
권리?

399
00:17:36,660 --> 00:17:40,790
8, 4로 이동 2로 이동,
1로 진행하고, 그건

400
00:17:40,790 --> 00:17:43,470
정확하게 반영
사진 우리는 잠시 전했다.

401
00:17:43,470 --> 00:17:47,160
그래서 조금 정신이 곳으로 확인
로그는 실제로 참여하고있다.

402
00:17:47,160 --> 00:17:50,180
>> 그래서 지금, 그 밖의 무엇을 여기에 포함된다? N.

403
00:17:50,180 --> 00:17:53,440
그래서 모든 것을 알 수
시간 나는 목록을 분할

404
00:17:53,440 --> 00:17:58,260
역사의 역순이기는하지만
여기에, 나는 아직도 n 개의 일을했다.

405
00:17:58,260 --> 00:18:02,320
즉, 병합 단계는 필요
나는, 숫자 하나 하나를 터치

406
00:18:02,320 --> 00:18:05,060
로 밀어 넣하기 위해
그것의 적절한 위치.

407
00:18:05,060 --> 00:18:10,760
순간에도이의 높이
도면, n 또는 (3)의 크기 n의 로그 인

408
00:18:10,760 --> 00:18:13,860
구체적으로 말하면,
여기 3 개 부문을했다.

409
00:18:13,860 --> 00:18:18,800
얼마나 많은 일을 내가 가로 했는가
이 차트마다 따라?

410
00:18:18,800 --> 00:18:21,110
>> 글쎄, 난의 N 단계를했다
내가했습니다 경우 때문에, 작업

411
00:18:21,110 --> 00:18:24,080
네 개의 요소 네 가지 요소를 가지고
나는 함께 병합 할 필요가있다.

412
00:18:24,080 --> 00:18:26,040
난을 통해 갈 필요가
이 네와이 네,

413
00:18:26,040 --> 00:18:28,123
궁극적으로 병합하기
다시 여덟 요소로.

414
00:18:28,123 --> 00:18:32,182
반대로 경우에 나는 여덟 손가락을 가지고
내가하지 않는, 여기, 8

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- 내가 한 경우
, 여기에 4 개의 손가락을 가지고

416
00:18:34,390 --> 00:18:37,380
나는, 네 손가락 않는
여기에, 내가하는,

417
00:18:37,380 --> 00:18:40,590
그 동일한의
예를 들어 이전에, 나는 할 경우

418
00:18:40,590 --> 00:18:44,010
에서 비록 여덟 손가락을
나는, 가지, 할 수있는 총.

419
00:18:44,010 --> 00:18:47,950
나는 정확히, 여기에 수행 할 수 있습니다
나는 확실히 할 수

420
00:18:47,950 --> 00:18:50,370
이 목록을 모두 병합
함께 크기 (1).

421
00:18:50,370 --> 00:18:54,050
그러나 나는 확실히보고있다
각 요소에서 정확히 한 번만.

422
00:18:54,050 --> 00:18:59,640
따라서이 과정의 높이는, n은 로그
이 프로세스의 폭이 있으므로, 말하자면

423
00:18:59,640 --> 00:19:02,490
그래서 우리는 무엇을 보인다, n은
궁극적으로,이다,이합니다

424
00:19:02,490 --> 00:19:06,470
크기 n 번의 실행 시간은 N 로그인합니다.

425
00:19:06,470 --> 00:19:08,977
>> 즉, 우리는 분할
목록, 로그 n 번,

426
00:19:08,977 --> 00:19:11,810
그러나 우리는 그것을했다 때마다, 우리는 있었다
요소 하나 하나를 터치합니다

427
00:19:11,810 --> 00:19:13,560
병합하기 위해
모두 함께하는

428
00:19:13,560 --> 00:19:18,120
단계를 N, 그래서 우리는이 n 번 n을 기록했다,
또는 컴퓨터 과학자가 말하는 것처럼,

429
00:19:18,120 --> 00:19:20,380
점근 적으로, 어떤
큰 말 것

430
00:19:20,380 --> 00:19:22,810
상부를 설명하는 데
실행 시간에 바인딩,

431
00:19:22,810 --> 00:19:28,010
우리는 큰 O를 실행하는
로그 N 시간, 말하자면.

432
00:19:28,010 --> 00:19:31,510
>> 지금이 있기 때문에 중요하다
실행 시간이 무엇인지 기억

433
00:19:31,510 --> 00:19:34,120
버블 정렬 및 선택과
정렬 및 삽입 정렬,

434
00:19:34,120 --> 00:19:38,200
와 존재조차 몇 가지 다른,
N은 우리가 있었던 곳이었다 제곱.

435
00:19:38,200 --> 00:19:39,990
그리고 당신은, 가지, 여기를 볼 수 있습니다.

436
00:19:39,990 --> 00:19:45,720
n은 제곱하면 분명히 n 번입니다
N, 그러나 여기에서 우리가 n 번이 N 로그

437
00:19:45,720 --> 00:19:48,770
우리는 이미 주부터 알고
제로, 그 로그 N, 대수,

438
00:19:48,770 --> 00:19:50,550
뭔가 선형보다 낫다.

439
00:19:50,550 --> 00:19:52,930
결국, 화상을 기억
빨간색과 노란색

440
00:19:52,930 --> 00:19:56,500
우리는 그린과 그린 라인,
녹색 로그 라인이 훨씬 낮았다.

441
00:19:56,500 --> 00:20:00,920
그러므로, 훨씬 더 빠르게
직선 노란색과 빨간색 선 이상,

442
00:20:00,920 --> 00:20:05,900
n 번 참이고, n은 로그, 더 나은
N 회보다 N 또는 N 제곱.

443
00:20:05,900 --> 00:20:09,110
>> 그래서 우리는 갖고있는 것 같다
알고리즘 병합을 확인

444
00:20:09,110 --> 00:20:11,870
종류 훨씬에서 실행
빠른 시간, 참으로,

445
00:20:11,870 --> 00:20:16,560
그 이유는, 이번 주 초, 때이다
우리는 거품 사이의 경쟁을 보았다

446
00:20:16,560 --> 00:20:20,750
정렬, 선택 정렬 및 병합
종류, 종류 정말, 정말 원 병합합니다.

447
00:20:20,750 --> 00:20:23,660
그리고 실제로, 우리는 심지어 기다리지 않았다
거품 정렬 및 선택 정렬에 대한

448
00:20:23,660 --> 00:20:24,790
마칩니다.

449
00:20:24,790 --> 00:20:27,410
>> 이제 다른 하나의 패스를 보자
이에, 조금 더에서

450
00:20:27,410 --> 00:20:31,030
형식적인 관점, 그냥
경우에, 이것은 더 공진

451
00:20:31,030 --> 00:20:33,380
그 높은 수준의 토론보다.

452
00:20:33,380 --> 00:20:34,880
그래서 여기 알고리즘은 다시입니다.

453
00:20:34,880 --> 00:20:36,770
의 자신을 물어 보자,
어떤 실행 시간

454
00:20:36,770 --> 00:20:39,287
이 여러 단계를 알고리즘인가?

455
00:20:39,287 --> 00:20:41,620
이제 처음으로 나뉘게
경우와 두번째 경우.

456
00:20:41,620 --> 00:20:46,280
IF 케이스와 ELSE IF,
n이 2 미만이면, 단지 반환한다.

457
00:20:46,280 --> 00:20:47,580
일정 시간 같은 느낌.

458
00:20:47,580 --> 00:20:50,970
이 두 단계와 같은 종류의,이다,
n이 2 미만이면, 리턴한다.

459
00:20:50,970 --> 00:20:54,580
그러나 우리는 월요일에 말했듯이,
일정 시간, 또는 1의 O 큰,

460
00:20:54,580 --> 00:20:57,130
두 단계, 세 수 있습니다
단계, 심지어 1,000 단계.

461
00:20:57,130 --> 00:20:59,870
중요한 것은이 점이다
단계의 상수.

462
00:20:59,870 --> 00:21:03,240
그래서 노란색 의사를 강조
여기, 우리가 전화 할게에서 실행

463
00:21:03,240 --> 00:21:04,490
일정 시간.

464
00:21:04,490 --> 00:21:06,780
그래서 더 공식적으로, 그리고
우리는이 이러시면거야

465
00:21:06,780 --> 00:21:09,910
정도 될 것입니다있는 우리
N의 T들을 당장이 권리를 공식화,

466
00:21:09,910 --> 00:21:15,030
문제의 실행 시간
즉, 입력으로 n 개의 일도 소요

467
00:21:15,030 --> 00:21:19,150
하나의 O 큰 동일
N이 2보다 작을 경우.

468
00:21:19,150 --> 00:21:20,640
그래서 그 조건으로합니다.

469
00:21:20,640 --> 00:21:24,150
n은보다 작은 경우 그래서, 명확하게하기
(2) 그리고 나서, 매우 짧은 목록을 가지고

470
00:21:24,150 --> 00:21:29,151
n은 실행 시간의 N, T,
1 또는 0이 매우 구체적인 경우에,

471
00:21:29,151 --> 00:21:30,650
그냥 일정 시간이 될 것.

472
00:21:30,650 --> 00:21:32,691
그것은 하나를 걸릴 거예요
무엇이든, 두 단계를 단계.

473
00:21:32,691 --> 00:21:33,950
이 단계의 고정 된 수이다.

474
00:21:33,950 --> 00:21:38,840
>> 따라서 수분이 많은 부분은 반드시 있어야합니다
의사 코드에서 다른 경우.

475
00:21:38,840 --> 00:21:40,220
ELSE 케이스.

476
00:21:40,220 --> 00:21:44,870
요소의 정렬 왼쪽 절반, 일종의 권리
요소의 절반, 정렬 절반을 병합합니다.

477
00:21:44,870 --> 00:21:46,800
이들 각 단계는 얼마나 걸립니까?

478
00:21:46,800 --> 00:21:49,780
음, 만약 실행
N 요소를 정렬하는 시간

479
00:21:49,780 --> 00:21:53,010
이며, 현실을 매우 부르 자
일반적으로, T, N의,

480
00:21:53,010 --> 00:21:55,500
다음 왼쪽 정렬
요소의 절반

481
00:21:55,500 --> 00:21:59,720
이다, 가지, 말처럼,
2로 나눈 N의 T,

482
00:21:59,720 --> 00:22:03,000
마찬가지로 우측 절반 정렬
요소이며, 가지, 말처럼,

483
00:22:03,000 --> 00:22:06,974
N의 T는 2 분할 한 다음
정렬 절반을 병합.

484
00:22:06,974 --> 00:22:08,890
그럼 내가 가지고있는 경우에 어떤
여기에 요소 수,

485
00:22:08,890 --> 00:22:11,230
네, 어떤 수를 같은
여기 요소, 네처럼,

486
00:22:11,230 --> 00:22:14,650
나는이 네 가지의 각각을 병합해야
에서, 이들 네 개의 각각 하나의

487
00:22:14,650 --> 00:22:17,160
다른 후, 그래서
궁극적으로 나는 여덟 요소를 가지고있다.

488
00:22:17,160 --> 00:22:20,230
그것은 즉, n 개의 단계의 오 크다 같은 느낌?

489
00:22:20,230 --> 00:22:23,500
나는 손가락과 각각의 N을 가지고 있다면
그들 대신에 병합하는,

490
00:22:23,500 --> 00:22:25,270
그것은 또 다른 N 단계처럼.

491
00:22:25,270 --> 00:22:27,360
>> 그래서 참으로 공식을 통해 (formulaically),
우리는이를 표현할 수

492
00:22:27,360 --> 00:22:29,960
처음에는 조금 무섭게이기는하지만
눈,하지만 뭔가

493
00:22:29,960 --> 00:22:31,600
즉, 정확히 논리를 캡처합니다.

494
00:22:31,600 --> 00:22:35,710
실행 시간, T, N의, IF N
2 이상이다.

495
00:22:35,710 --> 00:22:42,500
이 경우, ELSE 경우에서, N의 T이고
2로 나눈 값 (N)의 플러스 T 2로 나눈

496
00:22:42,500 --> 00:22:45,320
플러스 N의 O 큰 일부
단계의 선형 수,

497
00:22:45,320 --> 00:22:51,630
어쩌면 정확히 N, 어쩌면 2 회
N이지만, 대략 N의 순서이다.

498
00:22:51,630 --> 00:22:54,060
있도록, 너무, 어떻게 우리가 할 수있는 것입니다
공식을 통해 (formulaically)이를 표현한다.

499
00:22:54,060 --> 00:22:56,809
지금 당신은 않는 한이 모르는 것
당신은, 당신의 마음에 그것을 녹음 한

500
00:22:56,809 --> 00:22:58,710
또는 그것을 찾아
다시 교과서, 그

501
00:22:58,710 --> 00:23:00,501
조금있을 수 있습니다
마지막에 시트를 사기,

502
00:23:00,501 --> 00:23:03,940
그러나 이것은, 실제로 것입니다
N 로그 n의 O 큰 우리에게주고,

503
00:23:03,940 --> 00:23:06,620
재발 그 때문에
당신은 화면에 현재보고있는

504
00:23:06,620 --> 00:23:09,550
실제로, 그것은을 한 경우
예 무한한 수,

505
00:23:09,550 --> 00:23:13,000
또는 당신이 공식을 통해 (formulaically)을했다, 당신은 것
이 볼이 공식 때문에

506
00:23:13,000 --> 00:23:17,100
자체의 T로, 재귀
N 오른쪽에 뭔가 이상,

507
00:23:17,100 --> 00:23:21,680
왼쪽에 이상 (N)의 T와,이 수
실제로 표현 될 궁극적

508
00:23:21,680 --> 00:23:24,339
N 로그 n의로 큰 이동합니다.

509
00:23:24,339 --> 00:23:26,130
확신하지 않으면, 그건
, 지금은 잘 단지

510
00:23:26,130 --> 00:23:28,960
참, 그건 있다는 믿음에 걸릴,
그 재발에 이르게 무엇을,

511
00:23:28,960 --> 00:23:31,780
그러나 이것은 단지 조금 더
보고 수학적 접근

512
00:23:31,780 --> 00:23:36,520
병합 정렬의 실행 시간
혼자의 의사에 기초.

513
00:23:36,520 --> 00:23:39,030
>> 이제 조금 보자
이 모든에서 숨,

514
00:23:39,030 --> 00:23:41,710
과를 살펴
특정 전 상원 의원, 사람들

515
00:23:41,710 --> 00:23:44,260
조금 익숙해를 보일 수 있습니다,
누가 구글의 에릭과 함께 앉아

516
00:23:44,260 --> 00:23:48,410
인터뷰 얼마 전에 슈미트,
무대에서, 전체 무리의 앞에

517
00:23:48,410 --> 00:23:53,710
사람들의 궁극적에 대한 이야기
주제, 즉 꽤 이제 익숙하다.

518
00:23:53,710 --> 00:23:54,575
이제 살펴 보자.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> 에릭 슈미트 (Eric Sc​​hmidt) : 이제 상원 의원,
당신이 구글에서 여기

521
00:24:03,890 --> 00:24:09,490
내가 생각하기 좋아
면접으로 대통령.

522
00:24:09,490 --> 00:24:11,712
지금은 대통령으로 취업을하기 어렵다.

523
00:24:11,712 --> 00:24:12,670
오바마 대통령 : 오른쪽.

524
00:24:12,670 --> 00:24:13,940
에릭 슈미트 (Eric Sc​​hmidt) : 그리고 당신이있어
이제 [들림] 할 것.

525
00:24:13,940 --> 00:24:15,523
그것은 구글에 취직하는 것도 어렵다.

526
00:24:15,523 --> 00:24:17,700
오바마 대통령 : 오른쪽.

527
00:24:17,700 --> 00:24:21,330
>> 에릭 슈미트 : 우리는 질문이,
우리는 우리의 후보의 질문을,

528
00:24:21,330 --> 00:24:24,310
이 사람은 래리 쉬머에서입니다.

529
00:24:24,310 --> 00:24:25,890
>> 오바마 대통령 : OK.

530
00:24:25,890 --> 00:24:27,005
>> 에릭 슈미트 (Eric Sc​​hmidt) : 무엇?

531
00:24:27,005 --> 00:24:28,130
너희들은 내가 농담하는 것 같아?

532
00:24:28,130 --> 00:24:30,590
그것은 바로 여기입니다.

533
00:24:30,590 --> 00:24:33,490
가장 효율적인 방식은 무엇입니까
만 32 비트 정수를 정렬?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> 오바마 대통령 : 저기 ...

536
00:24:38,979 --> 00:24:41,020
에릭 슈미트 : 때때로,
어쩌면 내가 미안 해요, 봐 주길

537
00:24:41,020 --> 00:24:42,750
오바마 대통령 : 아니, 아니,
아니, 아니, 아니, 나는 think--

538
00:24:42,750 --> 00:24:43,240
에릭 슈미트 : 그건 그건 ... 아니다

539
00:24:43,240 --> 00:24:45,430
오바마 대통령 : 나는
생각 나는 거품을 생각

540
00:24:45,430 --> 00:24:46,875
종류의 갈 길을 잘못 될 것입니다.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
에릭 슈미트는 : 자.

543
00:24:50,535 --> 00:24:52,200
누가 그에게이 말?

544
00:24:52,200 --> 00:24:54,020
그래.

545
00:24:54,020 --> 00:24:55,590
나는 컴퓨터 과학하지 않았다 on--

546
00:24:55,590 --> 00:24:58,986
>> 오바마 대통령 : 우리는했습니다
거기에 우리의 스파이를 얻었다.

547
00:24:58,986 --> 00:24:59,860
교수 : 좋습니다.

548
00:24:59,860 --> 00:25:03,370
의 이제 우리 뒤에 남겨 두자
알고리즘의 이론적 세계

549
00:25:03,370 --> 00:25:06,520
점근 적 분석
이들의 일부 항목을 반환

550
00:25:06,520 --> 00:25:09,940
주 0과 1, 그리고 처음부터
일부 훈련 바퀴를 제거하려면

551
00:25:09,940 --> 00:25:10,450
당신이됩니다.

552
00:25:10,450 --> 00:25:13,241
당신이 정말로 이해할 수 있도록
결국 처음부터, 무엇이다

553
00:25:13,241 --> 00:25:16,805
, 때를 후드 아래에가는
프로그램의 작성, 컴파일 및 실행.

554
00:25:16,805 --> 00:25:19,680
이 것을, 특히 기억
우리가 바라 보았다 첫 번째 C 프로그램,

555
00:25:19,680 --> 00:25:22,840
표준, 간단한 프로그램
종류의, 상대적으로 말하기,

556
00:25:22,840 --> 00:25:24,620
특징으로는, 안녕하세요 세계를 인쇄합니다.

557
00:25:24,620 --> 00:25:27,610
그리고이 과정 말했다 리콜 것을
그 소스 코드를 통과

558
00:25:27,610 --> 00:25:28,430
바로 이것이다.

559
00:25:28,430 --> 00:25:31,180
당신은 당신의 소스 코드를 받아 통과
그것은 컴파일러를 통해, 연타 등,

560
00:25:31,180 --> 00:25:34,650
아웃은, 오브젝트 코드를 제공
이, 0과 같을 수 있습니다

561
00:25:34,650 --> 00:25:37,880
컴퓨터의 CPU, 중앙이
프로세싱 유닛 또는 뇌

562
00:25:37,880 --> 00:25:39,760
궁극적으로 이해하고 있습니다.

563
00:25:39,760 --> 00:25:42,460
>> 그것은 그가 있다고 밝혀
지나친 단순화의 비트,

564
00:25:42,460 --> 00:25:44,480
우리가 지금하고 있는지
위치 떨어져 애타게

565
00:25:44,480 --> 00:25:46,720
정말하고 있는지 이해하기
후드 아래에가는

566
00:25:46,720 --> 00:25:48,600
당신이 실행할 때마다
연타, 또는 더 일반적으로,

567
00:25:48,600 --> 00:25:53,040
때마다 당신은 프로그램을
확인하고 CF (50) IDE 사용.

568
00:25:53,040 --> 00:25:56,760
특히, 재료 등
이 먼저 생성됩니다

569
00:25:56,760 --> 00:25:58,684
때 처음 프로그램을 컴파일합니다.

570
00:25:58,684 --> 00:26:00,600
즉, 때를
소스 코드를 가지고

571
00:26:00,600 --> 00:26:04,390
무엇을 먼저, 그것은 컴파일
연타에 의해 출력되는

572
00:26:04,390 --> 00:26:06,370
어셈블리 코드로 알려진 무언가이다.

573
00:26:06,370 --> 00:26:08,990
그리고 사실, 정확히 다음과 같습니다.

574
00:26:08,990 --> 00:26:11,170
>> 나는에서 명령을 실행
이전 명령 행.

575
00:26:11,170 --> 00:26:16,260
연타 대시 자본의에서는 hello.c,
이것은 파일을 만든

576
00:26:16,260 --> 00:26:19,490
저라는 hello.s를 들어,
이는 내부에 정확하게 있었다

577
00:26:19,490 --> 00:26:22,290
이러한 내용과 조금 더
위보다 약간 아래,

578
00:26:22,290 --> 00:26:25,080
하지만 수분이를 넣었습니다
여기에 화면에 정보를 표시합니다.

579
00:26:25,080 --> 00:26:29,190
당신이 자세히 보면, 당신은 볼 수 있습니다
최소한 몇 친숙한 키워드.

580
00:26:29,190 --> 00:26:31,330
우리는 정상에 주요 있습니다.

581
00:26:31,330 --> 00:26:35,140
우리는 중간에서 아래로는 printf있다.

582
00:26:35,140 --> 00:26:38,670
그리고 우리는 또한 세계 안녕하세요이
아래로 아래 따옴표로 백 슬래시 명.

583
00:26:38,670 --> 00:26:42,450
>> 여기에 다른 모든 것을
매우 낮은 수준의 지침입니다

584
00:26:42,450 --> 00:26:45,500
컴퓨터의 CPU는 이해하고있다.

585
00:26:45,500 --> 00:26:50,090
메모리를 이동 CPU 지시
주위에, 메모리에서로드하는 문자열,

586
00:26:50,090 --> 00:26:52,750
궁극적으로, 인쇄
화면에 것들.

587
00:26:52,750 --> 00:26:56,780
지금 무슨 일이 후 비록 발생
이 어셈블리 코드가 생성된다?

588
00:26:56,780 --> 00:26:59,964
궁극적으로, 당신은 참으로 수행,
여전히 오브젝트 코드를 생성한다.

589
00:26:59,964 --> 00:27:02,630
그러나 단계는 정말이 그
후드 아래 진행되고

590
00:27:02,630 --> 00:27:04,180
이 같은 좀 더 봐.

591
00:27:04,180 --> 00:27:08,390
소스 코드, 어셈블리 코드가된다
이는 다음 오브젝트 코드가된다,

592
00:27:08,390 --> 00:27:11,930
여기에 수술 단어는, 그
당신이 당신의 소스 코드를 컴파일 할 때,

593
00:27:11,930 --> 00:27:16,300
아웃 후, 어셈블리 코드, 온다
당신이 당신의 어셈블리 코드를 조합 할 때,

594
00:27:16,300 --> 00:27:17,800
아웃 오브젝트 코드를 제공됩니다.

595
00:27:17,800 --> 00:27:20,360
>> 이제 연타, 슈퍼 정교
컴파일러의 많은 것,

596
00:27:20,360 --> 00:27:23,151
그리고 이러한 모든 단계를 수행합니다
동시에, 그것은 반드시 수행

597
00:27:23,151 --> 00:27:25,360
출력 중간을
당신도 볼 수있는 파일입니다.

598
00:27:25,360 --> 00:27:28,400
그냥 물건을 컴파일,
이는 일반적인 용어입니다

599
00:27:28,400 --> 00:27:30,000
이 전체 과정을 설명합니다.

600
00:27:30,000 --> 00:27:32,000
하지만 당신이 정말로 원하는 경우
특히 수,있다

601
00:27:32,000 --> 00:27:34,330
많은 더뿐만 아니라이 진행.

602
00:27:34,330 --> 00:27:38,860
>> 그러나의는 또한 지금도 생각해 보자
그 슈퍼 간단한 프로그램에서는 hello.c,

603
00:27:38,860 --> 00:27:40,540
기능이라고.

604
00:27:40,540 --> 00:27:41,870
그것은 printf의를했다.

605
00:27:41,870 --> 00:27:46,900
하지만, 참으로, printf와 쓰기하지 않았다
즉 말하자면, C와 함께 제공됩니다.

606
00:27:46,900 --> 00:27:51,139
그것은의 기능 리콜의
표준 io.h에 선언하는

607
00:27:51,139 --> 00:27:53,180
헤더 파일 인
주제는 우리가 실제로 것입니다

608
00:27:53,180 --> 00:27:55,780
오래 전에 더 깊이로 잠수.

609
00:27:55,780 --> 00:27:58,000
그러나 헤더 파일입니다
일반적으로 동반

610
00:27:58,000 --> 00:28:02,920
코드 파일, 소스 코드 파일, 그렇게함으로써
표준 io.h.이 존재 많은처럼

611
00:28:02,920 --> 00:28:05,930
>> 얼마 전, 사람,
또는 누군가도 썼다

612
00:28:05,930 --> 00:28:11,040
에, 표준 io.c라는 파일
이는 실제 정의,

613
00:28:11,040 --> 00:28:15,220
또는 printf의 구현,
및 기타 기능의 움큼,

614
00:28:15,220 --> 00:28:16,870
실제로 기록됩니다.

615
00:28:16,870 --> 00:28:22,140
우리가 가진 생각한다면, 주어진
여기에 왼쪽에서는 hello.c에, 때

616
00:28:22,140 --> 00:28:26,250
컴파일 된 경우에도, hello.s 우리에게 제공
연타는 장소에 저장 귀찮게하지 않습니다

617
00:28:26,250 --> 00:28:31,360
우리는 그것을보고, 그 어셈블리 코드 수
hello.o로 조립 도착하는

618
00:28:31,360 --> 00:28:34,630
실제로, 기본 이름입니다
당신이 소스를 컴파일 할 때마다 주어진

619
00:28:34,630 --> 00:28:39,350
오브젝트 코드로 코딩되지만 아니다
아직 그것을 실행하는 것은 매우 준비,

620
00:28:39,350 --> 00:28:41,460
또 다른 단계 때문에
일이 있으며,이

621
00:28:41,460 --> 00:28:44,440
지난 몇 위해 일어나고
주, 당신에게 아마 모르는.

622
00:28:44,440 --> 00:28:47,290
>> 특히 어딘가에
CS50 IDE에서,이,

623
00:28:47,290 --> 00:28:49,870
도 조금있을 것입니다
잠시 단순화,

624
00:28:49,870 --> 00:28:54,670
이, 또는 시간에했다,
표준 io.c라는 파일,

625
00:28:54,670 --> 00:28:58,440
누군가로 컴파일하는 것이
표준 io.s 또는 동등한,

626
00:28:58,440 --> 00:29:02,010
누군가는 조립 된 것을
표준 io.o에,

627
00:29:02,010 --> 00:29:04,600
또는 그것으로 밝혀
약간 다른 파일

628
00:29:04,600 --> 00:29:07,220
다른를 가질 수 있습니다 형식
모두 확장 파일,

629
00:29:07,220 --> 00:29:11,720
이론 및 개념적으로 정확히하지만
그 단계는 어떤 형태로 발생했다.

630
00:29:11,720 --> 00:29:14,060
말을 지금하는 것입니다 어떤
내가 프로그램을 작성하고있을 때,

631
00:29:14,060 --> 00:29:17,870
에서는 hello.c, 단지 말한다 것을, 안녕하세요,
나는 누군가 다른 사람의 코드를 사용하고 있습니다

632
00:29:17,870 --> 00:29:22,480
에 한때 printf와 같은
시간, 표준 io.c라는 파일에,

633
00:29:22,480 --> 00:29:26,390
다음 어떻게 든 내을해야
오브젝트 코드, 제 0과 1,

634
00:29:26,390 --> 00:29:29,260
그 사람의 목적
코드, 또는 0과 1,

635
00:29:29,260 --> 00:29:34,970
어떻게 든으로 그들을 함께 연결
것을, 안녕하세요라는 하나의 최종 파일,

636
00:29:34,970 --> 00:29:38,070
이 제로의 모든과
내 주요 기능에서 사람,

637
00:29:38,070 --> 00:29:40,830
그리고 제로의 모든
과의 printf에 대한 것.

638
00:29:40,830 --> 00:29:44,900
>> 그리고 실제로, 마지막 과정이다
라는 개체 코드를 연결.

639
00:29:44,900 --> 00:29:47,490
출력 중 어느
실행 파일이다.

640
00:29:47,490 --> 00:29:49,780
그래서 공정성에,에
일, 아무것도 끝

641
00:29:49,780 --> 00:29:52,660
주 한 이후 변경된, 때
처음 프로그램을 컴파일하기 시작했다.

642
00:29:52,660 --> 00:29:55,200
실제로,이 모든왔다
후드 아래에 일어나고,

643
00:29:55,200 --> 00:29:57,241
그러나 지금 우리는 위치에있어
여기서 우리가 실제로 할 수있는

644
00:29:57,241 --> 00:29:58,794
이러한 여러 단계 떨어져 애타게.

645
00:29:58,794 --> 00:30:00,710
그리고 실제로, 말
오늘, 우리는 여전히있어

646
00:30:00,710 --> 00:30:04,480
0과 1, 왼쪽있는
좋은 SEGUE 지금 실제로

647
00:30:04,480 --> 00:30:08,620
C의 또 다른 기능에, 그
우리는 대부분 활용할 수 없었습니다

648
00:30:08,620 --> 00:30:11,250
현재까지, 비트 연산자라고도합니다.

649
00:30:11,250 --> 00:30:15,220
즉, 지금까지, 우리는 언제했습니다
C에서 C 또는 변수의 데이터 처리,

650
00:30:15,220 --> 00:30:17,660
우리는 같은 일을 했어
문자와 수레와 기능

651
00:30:17,660 --> 00:30:21,990
및 정수 (Long)과 복식 등을하지만,
그 모두는 적어도 8 비트이다.

652
00:30:21,990 --> 00:30:25,550
우리는 아직 본 적​​이 없습니다
개별 비트를 조작,

653
00:30:25,550 --> 00:30:28,970
심지어 개별 비트하지만, 우리
, 0과 1을 표현 할 수 있습니다 알고 있습니다.

654
00:30:28,970 --> 00:30:32,640
지금은 C에 그 밝혀, 당신
개별 비트에 대한 액세스를 얻을 수있다,

655
00:30:32,640 --> 00:30:35,530
당신은 구문을 알고있는 경우,
있는 그들을 얻을 수 있습니다.

656
00:30:35,530 --> 00:30:38,010
>> 그럼 살펴 보자
비트 연산자에서.

657
00:30:38,010 --> 00:30:41,700
그래서 여기에 사진 몇 가지 기호는 그
우리는 종류의, 일종의 전에 봤어요.

658
00:30:41,700 --> 00:30:45,580
나는, 수직을 앰퍼샌드 참조
바,뿐만 아니라 일부 다른,

659
00:30:45,580 --> 00:30:49,430
그 앰퍼샌드 앰퍼샌드 리콜
우리가 전에 본 무언가이다.

660
00:30:49,430 --> 00:30:54,060
당신이 가지고있는 논리 AND 연산자,
이들 둘이 또는 논리 OR

661
00:30:54,060 --> 00:30:56,300
연산자, 어디를
두 개의 수직 바있다.

662
00:30:56,300 --> 00:31:00,550
비트 연산자, 우리는거야
개별적으로 비트에서 작동 참조

663
00:31:00,550 --> 00:31:03,810
단지 하나의 앰퍼샌드를 사용,
하나의 수직 바, 캐럿 기호

664
00:31:03,810 --> 00:31:06,620
다음, 작은 온다
물결, 다음 왼쪽

665
00:31:06,620 --> 00:31:08,990
브래킷 브래킷을 왼쪽,
오른쪽 대괄호 오른쪽 대괄호.

666
00:31:08,990 --> 00:31:10,770
이들 각각은 서로 다른 의미를 갖는다.

667
00:31:10,770 --> 00:31:11,950
>> 사실, 이제 살펴 보자.

668
00:31:11,950 --> 00:31:16,560
의 오래된 학교 오늘, 사용 가자
근년에서 터치 스크린

669
00:31:16,560 --> 00:31:18,002
화이트 보드라고도합니다.

670
00:31:18,002 --> 00:31:19,710
그리고이 화이트 보드
우리를 허용하는 것입니다

671
00:31:19,710 --> 00:31:27,360
몇 가지 아주 간단한 기호를 표현하는,
또는 오히려 몇 가지 아주 간단한 공식,

672
00:31:27,360 --> 00:31:29,560
즉, 우리는 궁극적으로 다음 수
활용, 순서

673
00:31:29,560 --> 00:31:33,230
개인에 액세스 할 수
C 프로그램 내에서 비​​트.

674
00:31:33,230 --> 00:31:34,480
즉,이 해 보자.

675
00:31:34,480 --> 00:31:37,080
대한하자 첫 번째 이야기
앰퍼샌드에 대한 순간,

676
00:31:37,080 --> 00:31:39,560
이는 비트 AND 연산자입니다.

677
00:31:39,560 --> 00:31:42,130
즉,이다
수있는 연산자

678
00:31:42,130 --> 00:31:45,930
나 왼손 변수가하는
전형적으로, 그리고 우측 변수

679
00:31:45,930 --> 00:31:50,640
또는 개별 값, 그 경우 우리와
함께 그들에게, 나에게 최종 결과를 제공합니다.

680
00:31:50,640 --> 00:31:51,560
그래서 나는 무엇을 의미합니까?

681
00:31:51,560 --> 00:31:54,840
프로그램에서, 당신은 변수가있는 경우
이 값을 저장 한 그,

682
00:31:54,840 --> 00:31:58,000
또는 이제 간단하게, 그냥하자
개별적으로 0과 1을 기록,

683
00:31:58,000 --> 00:32:00,940
앰퍼샌드 연산자가 어떻게 작동하는지 여기.

684
00:32:00,940 --> 00:32:06,400
0 앰퍼샌드 0 0과 동일 할 것입니다.

685
00:32:06,400 --> 00:32:07,210
이제 그 이유는 무엇입니까?

686
00:32:07,210 --> 00:32:09,291
>> 그것은 매우 유사
부울 식,

687
00:32:09,291 --> 00:32:10,540
것을 우리는 지금까지 논의했습니다.

688
00:32:10,540 --> 00:32:15,800
모든 후 생각한다면, 0이됩니다
거짓, 0, 거짓 거짓과 거짓

689
00:32:15,800 --> 00:32:18,720
우리가 언급 한 바와 같이, 인
논리적으로, 또한 거짓.

690
00:32:18,720 --> 00:32:20,270
그래서 우리는뿐만 아니라 여기에 0을 얻는다.

691
00:32:20,270 --> 00:32:24,390
당신은 0 앰퍼샌드을 경우
1, 우물, 너무,

692
00:32:24,390 --> 00:32:29,890
이 때문에 들어, 0이 될 것입니다
왼쪽 표현은, true 또는 1이어야합니다

693
00:32:29,890 --> 00:32:32,360
그것은 사실과 진실해야합니다.

694
00:32:32,360 --> 00:32:36,320
그러나 여기에서 우리는 거짓이
참, 또는 0과 1.

695
00:32:36,320 --> 00:32:42,000
이제 다시, 우리는 1 앰퍼샌드가있는 경우
0, 역시 0이 될 것입니다 것을,

696
00:32:42,000 --> 00:32:47,240
우리는 1 앰퍼샌드 (1)이있는 경우,
마지막으로 우리는 1 비트가 않습니다.

697
00:32:47,240 --> 00:32:50,340
즉 그래서 우리는 일을하지 않을
이 연산자와 흥미로운 아무것도

698
00:32:50,340 --> 00:32:51,850
아직,이 앰퍼샌드 연산자.

699
00:32:51,850 --> 00:32:53,780
그것은 비트 AND 연산자입니다.

700
00:32:53,780 --> 00:32:57,290
그러나 이러한 성분은
어떤을 통해 우리가 할 수있는

701
00:32:57,290 --> 00:32:59,240
우리가 곧 보 겠지만 흥미로운 것들.

702
00:32:59,240 --> 00:33:02,790
>> 이제 그냥 하나를 살펴 보자
여기에 오른쪽 위에 수직 막대.

703
00:33:02,790 --> 00:33:06,710
나는 0 비트와 내가있는 경우
아니면와, 비트

704
00:33:06,710 --> 00:33:11,030
OR 연산자, 다른 0 비트,
그 날 0을 제공하는 것입니다.

705
00:33:11,030 --> 00:33:17,540
나는 0 비트 또는 그것으로 걸릴 경우
1 비트, 나는 1을 얻을거야.

706
00:33:17,540 --> 00:33:19,830
그리고 사실, 단지에 대한
선명도, 나를 돌아 가자

707
00:33:19,830 --> 00:33:23,380
그래서 내 수직 막대
1의 착각되지 않습니다.

708
00:33:23,380 --> 00:33:26,560
나를 모두 다시 보자
제 1 좀 더있어

709
00:33:26,560 --> 00:33:32,700
내가하면 명확하게, 그래서 우리는 다음을 참조하십시오
1 또는 0, 즉 1이 될 것있다,

710
00:33:32,700 --> 00:33:39,060
내가 1 또는 1이있는 경우,
도 1이 될 것입니다.

711
00:33:39,060 --> 00:33:42,900
그래서 당신은 논리적으로 볼 또는 수
운영자는 매우 다르게 동작합니다.

712
00:33:42,900 --> 00:33:48,070
이 0 나에게 제공 또는 0 날 0을 제공하지만,
다른 모든 조합은 나에게 1을 제공합니다.

713
00:33:48,070 --> 00:33:52,480
너무 오래 내가 한 일을 가지고
수식 결과는 1이 될 예정이다.

714
00:33:52,480 --> 00:33:55,580
>> 과와 대조적으로
연산자, 앰퍼샌드,

715
00:33:55,580 --> 00:34:00,940
나는 두 개의 1의 경우에만
방정식, 사실은 1 아웃을받을 수 있나요.

716
00:34:00,940 --> 00:34:02,850
이제 몇 가지 다른있다
사업자뿐만 아니라.

717
00:34:02,850 --> 00:34:04,810
그 중 하나는 조금 더 복잡하다.

718
00:34:04,810 --> 00:34:07,980
그래서 내가 가서 삭제하자
이 공간을 확보합니다.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
그리고 이제 살펴 보자
단지 잠시 캐럿 기호.

721
00:34:16,460 --> 00:34:18,210
이는 통상적 인
문자는 입력 할 수 있습니다

722
00:34:18,210 --> 00:34:21,420
키보드를 들고 이동에와
당신의 미국 꼭대기 숫자 다음 하나

723
00:34:21,420 --> 00:34:22,250
키보드.

724
00:34:22,250 --> 00:34:26,190
>> 그래서이 독점
OR 연산자, 배타적 논리합.

725
00:34:26,190 --> 00:34:27,790
그래서 우리는 단지 또는 연산자를 보았다.

726
00:34:27,790 --> 00:34:29,348
이것은 배타적 논리합 연산자입니다.

727
00:34:29,348 --> 00:34:30,639
실제로 차이가 무엇입니까?

728
00:34:30,639 --> 00:34:34,570
그럼 그냥 공식을 살펴 보자,
궁극적으로 재료로 사용.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
내가 말할거야 항상 0입니다.

731
00:34:39,650 --> 00:34:41,400
즉, XOR의 정의입니다.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1은 1이 될 것입니다.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0, 1이 될 것입니다
1 XOR 1은 될 것입니다?

734
00:34:58,810 --> 00:34:59,890
잘못?

735
00:34:59,890 --> 00:35:00,520
아니면 오른쪽?

736
00:35:00,520 --> 00:35:01,860
모르겠어요.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
지금 무슨 일이 일어나고 있는가?

739
00:35:04,700 --> 00:35:06,630
잘 생각
이 연산자의 이름입니다.

740
00:35:06,630 --> 00:35:09,980
배타적 OR, 그래서
이름, 종류, 제안

741
00:35:09,980 --> 00:35:13,940
답은 될 것입니다
(1) 입력이 독점하는 경우,

742
00:35:13,940 --> 00:35:15,560
독점적으로 다른.

743
00:35:15,560 --> 00:35:18,170
그래서 여기에 입력은
동일하므로 출력은 0이다.

744
00:35:18,170 --> 00:35:20,700
여기서 입력이
동일하므로 출력은 0이다.

745
00:35:20,700 --> 00:35:25,640
여기서 출력들은 다르다 아르
배타적이고, 그래서 출력은 1이다.

746
00:35:25,640 --> 00:35:28,190
그래서 매우 유사
AND, 그것은 매우 유사

747
00:35:28,190 --> 00:35:32,760
또는 오히려 그것과 매우 유사
또는, 만 독점 방식으로.

748
00:35:32,760 --> 00:35:36,210
이것은 더 이상 1 없다
우리가이 일의이 있기 때문에,

749
00:35:36,210 --> 00:35:38,621
하지 독점적으로, 그 중 하나.

750
00:35:38,621 --> 00:35:39,120
괜찮아.

751
00:35:39,120 --> 00:35:40,080
어떤 사람들은 어떻습니까?

752
00:35:40,080 --> 00:35:44,220
그럼 물결 한편,이다
실제로 좋은 간단한, 고맙게도.

753
00:35:44,220 --> 00:35:46,410
그리고 이것은 단항입니다
의미 운영자,

754
00:35:46,410 --> 00:35:50,400
또, 하나의 입력에인가있어
하나의 피연산자, 말하자면.

755
00:35:50,400 --> 00:35:51,800
아니 왼쪽과 오른쪽으로.

756
00:35:51,800 --> 00:35:56,050
즉,의 물결을 경우
0, 대답은 반대 할 것이다.

757
00:35:56,050 --> 00:35:59,710
그리고 당신은 하나의 물결이 걸릴 경우,
대답은 반대가있을 것입니다.

758
00:35:59,710 --> 00:36:02,570
그래서 물결 운영자입니다
비트를 부정하는 방법,

759
00:36:02,570 --> 00:36:06,000
또는에서 비트를 뒤집기
0-1, 또는 1-0.

760
00:36:06,000 --> 00:36:09,820
>> 그리고 마침내 우리를 잎
두 최종 사업자와,

761
00:36:09,820 --> 00:36:13,840
은 왼쪽 Shift 소위, 그리고
오른쪽 시프트 연산자 소위.

762
00:36:13,840 --> 00:36:16,620
의 어떻게 그 일을 살펴 보자.

763
00:36:16,620 --> 00:36:20,780
서면 왼쪽 시프트 연산자,
그런 두 각도 브래킷,

764
00:36:20,780 --> 00:36:22,110
다음과 같이 작동합니다.

765
00:36:22,110 --> 00:36:27,390
만약 왼쪽으로 내 입력, 또는 내 피연산자,
시프트 연산자는 아주 간단하게 1입니다.

766
00:36:27,390 --> 00:36:33,750
그리고 난 다음 컴퓨터를 말해
1, 일곱 곳이 말하는 것을 변화를 왼쪽,

767
00:36:33,750 --> 00:36:37,150
결과는 내가 것처럼입니다
그 일을하고 이동

768
00:36:37,150 --> 00:36:40,160
에 걸쳐 일곱 곳
왼쪽, 그리고 기본적으로,

769
00:36:40,160 --> 00:36:42,270
우리는 가정거야
우측 공간

770
00:36:42,270 --> 00:36:44,080
0으로 채워 될 것입니다.

771
00:36:44,080 --> 00:36:50,316
즉, 1 시프트 7 가고 왼쪽
이어서, 1 말해 수득하여 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 제로.

773
00:36:54,060 --> 00:36:57,380
방법 그래서, 그것은을 수행 할 수 있습니다
1과 같은 소수를 타고

774
00:36:57,380 --> 00:37:00,740
명확하게 많이 만들
이 방식으로 훨씬 더 큰, 더,

775
00:37:00,740 --> 00:37:06,460
그러나 우리가 실제로 보게 될 것입니다
그것은 더 영리한 방법

776
00:37:06,460 --> 00:37:08,080
대신에,뿐만 아니라,

777
00:37:08,080 --> 00:37:08,720
>> 괜찮아.

778
00:37:08,720 --> 00:37:10,060
즉 주일을 위해 그것을이다.

779
00:37:10,060 --> 00:37:11,400
우리는 당신이 다음 번에 ​​볼 수 있습니다.

780
00:37:11,400 --> 00:37:12,770
이 CS50했다.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [음악 재생]

783
00:37:22,243 --> 00:37:25,766
>> 스피커 1 : 그는 간식에 있었다
핫 초콜릿 아이스크림을 먹는 바.

784
00:37:25,766 --> 00:37:28,090
그는 자신의 얼굴에 모든 것을 가지고 있었다.

785
00:37:28,090 --> 00:37:30,506
그는 수염처럼 그 초콜릿을 입고

786
00:37:30,506 --> 00:37:31,756
스피커 2 : 뭐하시는 거예요?

787
00:37:31,756 --> 00:37:32,422
스피커 3 : 흠?

788
00:37:32,422 --> 00:37:33,500
뭐?

789
00:37:33,500 --> 00:37:36,800
>> 스피커 2 : 당신은 그냥 더블 딥습니까?

790
00:37:36,800 --> 00:37:38,585
당신은 더블 칩을 감소했다.

791
00:37:38,585 --> 00:37:39,460
스피커 3 : 실례합니다.

792
00:37:39,460 --> 00:37:44,440
스피커 2 : 당신은 칩을 담근
물린했다, 당신은 다시 감소했다.

793
00:37:44,440 --> 00:37:44,940
스피커 3 :

794
00:37:44,940 --> 00:37:48,440
스피커 2 : 그 퍼팅처럼 그래서
딥의 전체 입 오른쪽.

795
00:37:48,440 --> 00:37:52,400
다음 시간 당신은 칩을
그냥 한 번 찍어, 그것을 끝낸다.

796
00:37:52,400 --> 00:37:53,890
>> 스피커 3 : 당신은, 댄 무엇을 알아?

797
00:37:53,890 --> 00:37:58,006
당신은 당신이 찍어 원하는대로 찍어.

798
00:37:58,006 --> 00:38:01,900
내가 찍어 원하는 방식으로 찍어 것이다.

799
00:38:01,900 --> 00:38:03,194