1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [음악 재생]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> 데이비드 J. 마란 :이 CS50입니다.

5
00:00:12,550 --> 00:00:14,612
그리고이 주일의 시작이다.

6
00:00:14,612 --> 00:00:16,820
그래서 우리는 흥분을 많이 가지고
일이 오늘 커버하는.

7
00:00:16,820 --> 00:00:20,160
많은 기회에 대한
무대에서까지 자원 봉사.

8
00:00:20,160 --> 00:00:22,780
그리고 궁극적으로, 오늘은
되지 않는 코드에 대한 모든.

9
00:00:22,780 --> 00:00:24,820
하지만, 아이디어 그리고
이 알고리즘에 관하여,

10
00:00:24,820 --> 00:00:28,420
실제로 일부를 다시 가져
주 제로에서 배운 교훈,

11
00:00:28,420 --> 00:00:31,910
특징 리콜, 우리
이 괴물을 소개했다.

12
00:00:31,910 --> 00:00:33,880
그리고 차입 영감
그에서 시작

13
00:00:33,880 --> 00:00:36,879
더욱 정교한 해결하기 위해
알고리즘 문제.

14
00:00:36,879 --> 00:00:38,420
하지만 먼저, 공지 사항의 커플.

15
00:00:38,420 --> 00:00:42,020
그래서 하나, 당신은 가입하고자하는 경우
점심 시간에 CS50의 직원과 친구들

16
00:00:42,020 --> 00:00:44,670
금요일, 모두 여기에
캠브리지, 및 뉴 헤이븐에서,

17
00:00:44,670 --> 00:00:48,060
코스의 방문하시기 바랍니다
URL은 웹 사이트를 찾아 볼 수있다.

18
00:00:48,060 --> 00:00:50,390
이 수요일 것이다 강의
샌더스 여기 수 없습니다.

19
00:00:50,390 --> 00:00:53,610
너무, 온라인으로 만 할 것이다
CS50의 웹 사이트에서의 조정,

20
00:00:53,610 --> 00:00:55,850
여기 캠브리지 여부
또는 뉴 헤이븐뿐만 아니라.

21
00:00:55,850 --> 00:00:58,110
>> 그리고 문제는 두 설정
당신의 손에 이미 있습니다.

22
00:00:58,110 --> 00:01:03,067
당신이 아직 아래쪽에서 날아하지 않은 경우에, 저를 허용
강하게 말로 제안을 제공합니다

23
00:01:03,067 --> 00:01:05,150
특히 지금과 같은, 그
문제는, 미리 설정을

24
00:01:05,150 --> 00:01:08,669
당신은 정말, 지금이 아니라면 시작 하시겠습니까
주말 또는 이전에 조금 손 대고

25
00:01:08,669 --> 00:01:10,710
그들은 처음에 외출 할 때
금요일, 당신이 것이기 때문에

26
00:01:10,710 --> 00:01:14,380
그들이 필요하지 않은 것을 발견
더 이상의 도전 당지고

27
00:01:14,380 --> 00:01:14,950
그 자체.

28
00:01:14,950 --> 00:01:17,575
나는, 당신은 그것을 찾을 수있을 거라 생각
일반적으로, 그들은 거의 가지고하는 경향이

29
00:01:17,575 --> 00:01:18,892
시간의 같은 양의 주위에.

30
00:01:18,892 --> 00:01:20,850
그러나 그것은 확실히 따라
학생, 그것에

31
00:01:20,850 --> 00:01:22,880
사고 방식에 따라 달라집니다
있는 당신은 그것을 접근.

32
00:01:22,880 --> 00:01:24,910
하지만 변함없이, 당신은거야
일부 벽에 실행하려면

33
00:01:24,910 --> 00:01:26,350
당신은 칠거야
일부 버그, 그리고 당신이있어 단지

34
00:01:26,350 --> 00:01:27,950
수 될 수 없습니다
어떤 시점에서 그것을 극복.

35
00:01:27,950 --> 00:01:31,380
그리고 할 수있는 엄청난 가치의
멀리 단계 다음날 다시 와서,

36
00:01:31,380 --> 00:01:35,286
근무 시간에 가서, CS50에 게시물 토론
등이, 실제로 차단 해제 얻을 수 있습니다.

37
00:01:35,286 --> 00:01:36,160
그래서 명심.

38
00:01:36,160 --> 00:01:40,830
가능한 한 빠른 시작
당신이 할 수있는 가장 좋은 방법입니다.

39
00:01:40,830 --> 00:01:44,160
우리가 시작했던 곳 그래서 여기에
주 제로에 걸쳐 클래스.

40
00:01:44,160 --> 00:01:47,441
그리고 우리는 자원 봉사를 얻을 수 있습니다
여기에 내가 마이크를 찾을 수 있도록하는 방법?

41
00:01:47,441 --> 00:01:47,940
그래.

42
00:01:47,940 --> 00:01:48,900
이미 서.

43
00:01:48,900 --> 00:01:50,080
최대 어서.

44
00:01:50,080 --> 00:01:53,707
그게 효과가 있을까 얼마나 같아요.

45
00:01:53,707 --> 00:01:54,415
당신의 이름은 무엇입니까?

46
00:01:54,415 --> 00:01:55,570
인영 에스트라다 : 앨런 에스트라다.

47
00:01:55,570 --> 00:01:56,778
데이비드 J. 마란 : 앨런 에스트라다.

48
00:01:56,778 --> 00:01:57,910
최대 어서.

49
00:01:57,910 --> 00:01:58,619
만나서 반갑습니다.

50
00:01:58,619 --> 00:01:59,910
인영 에스트라다 : 만나서 반가워요.

51
00:01:59,910 --> 00:02:02,772
데이비드 J. 마란 : 그리고 당신은 여기에 있었다
우리 주 제로에, 물론 함께.

52
00:02:02,772 --> 00:02:03,028
인영 에스트라다 : 나는이었다.

53
00:02:03,028 --> 00:02:03,160
나는였다.

54
00:02:03,160 --> 00:02:05,868
>> 데이비드 J. 마란 : 그래서 당신은 갈 수있다
앞서 마이크 스미스 우리를 찾아

55
00:02:05,868 --> 00:02:08,639
당신이 할 수있는 한 빨리?

56
00:02:08,639 --> 00:02:10,639
당신이 할 수있는만큼 빨리.

57
00:02:10,639 --> 00:02:13,756
말 그대로 문제를 찢어
반에서 당신이 필요로.

58
00:02:13,756 --> 00:02:15,130
>> 인영 에스트라다 : 음.

59
00:02:15,130 --> 00:02:17,380
데이비드 J. 마란 : 말 그대로
반 문제 찢어.

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> 인영 에스트라다 : 오.

62
00:02:22,083 --> 00:02:22,583
음.

63
00:02:22,583 --> 00:02:23,300
아주 좋아.

64
00:02:23,300 --> 00:02:23,700
>> 데이비드 J. 마란 : OK.

65
00:02:23,700 --> 00:02:24,200
좋다.

66
00:02:24,200 --> 00:02:24,701
고맙습니다.

67
00:02:24,701 --> 00:02:25,700
인영 에스트라다 : 아주 좋아요.

68
00:02:25,700 --> 00:02:26,210
그래.

69
00:02:26,210 --> 00:02:27,610
>> 데이비드 J. 마란 : 그래서 지금,
당신은 그것을 아래로 깍습니다

70
00:02:27,610 --> 00:02:29,320
문제의 절반 크기이다.

71
00:02:29,320 --> 00:02:31,267
이제, 우리는 분기까지입니다.

72
00:02:31,267 --> 00:02:33,475
당신이주의를 지불하고
우리는 유지하고 어느 쪽?

73
00:02:33,475 --> 00:02:34,405
>> [하하]

74
00:02:34,405 --> 00:02:35,970
>> 인영 에스트라다 : 네, think--

75
00:02:35,970 --> 00:02:37,594
>> 데이비드 J. 마란 : 어떤 부분 우리는에?

76
00:02:37,594 --> 00:02:39,150
인영 에스트라다 : 머플러, 그래서.

77
00:02:39,150 --> 00:02:39,941
>> 데이비드 J. 마란 : OK.

78
00:02:39,941 --> 00:02:42,810
그러나 마이크 스미스는 것입니다
머플러 이후 여야합니다.

79
00:02:42,810 --> 00:02:44,130
그러니까 ...

80
00:02:44,130 --> 00:02:48,180
>> [하하]

81
00:02:48,180 --> 00:02:48,742
>> 괜찮아.

82
00:02:48,742 --> 00:02:50,200
인영 에스트라다 : 우리는 어디에서 찾고 계십니까?

83
00:02:50,200 --> 00:02:52,049
데이비드 J. 마란 : 마이크 스미스.

84
00:02:52,049 --> 00:02:53,090
인영 에스트라다 : 마이크 스미스.

85
00:02:53,090 --> 00:02:54,760
데이비드 J. 마란 : 이제, 우리는 수술에있어.

86
00:02:54,760 --> 00:02:57,840
이제, 의사.

87
00:02:57,840 --> 00:02:58,340
들을 당장

88
00:02:58,340 --> 00:02:59,856
>> 인영 에스트라다 :의 실제와 가자 Let's-.

89
00:02:59,856 --> 00:03:00,370
진짜.

90
00:03:00,370 --> 00:03:00,970
>> 데이비드 J. 마란 : 진짜.

91
00:03:00,970 --> 00:03:01,470
그래.

92
00:03:01,470 --> 00:03:03,700
당신은 진짜 필요합니다.

93
00:03:03,700 --> 00:03:05,250
이제, 마이크 스미스는 어떤 방법이 있나요?

94
00:03:05,250 --> 00:03:06,250
>> 인영 에스트라다 :이 방법.

95
00:03:06,250 --> 00:03:07,333
>> 데이비드 J. 마란 : 방법은?

96
00:03:07,333 --> 00:03:08,240
인영 에스트라다 : 잠깐.

97
00:03:08,240 --> 00:03:08,790
M is-- 맞죠?

98
00:03:08,790 --> 00:03:09,110
우리는 일 해요 시작

99
00:03:09,110 --> 00:03:10,090
>> 데이비드 J. 마란 : 그래.

100
00:03:10,090 --> 00:03:10,650
그들은 왼쪽으로하고 있습니다.

101
00:03:10,650 --> 00:03:11,430
당신의 권리.

102
00:03:11,430 --> 00:03:11,710
>> 인영 에스트라다 : 네.

103
00:03:11,710 --> 00:03:13,126
>> 데이비드 J. 마란 : 그래서 마이크 여기에.

104
00:03:13,126 --> 00:03:13,990
인영 에스트라다 : 무엇?

105
00:03:13,990 --> 00:03:14,665
>> [하하]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> 나쁜 예, 사람.

108
00:03:18,330 --> 00:03:18,830
죄송합니다.

109
00:03:18,830 --> 00:03:21,610
데이비드 J. 마란 :이 가르 칠 것
당신은 당신의 의자에서 뛰어.

110
00:03:21,610 --> 00:03:22,318
>> 인영 에스트라다 : 오.

111
00:03:22,318 --> 00:03:22,890
오.

112
00:03:22,890 --> 00:03:23,390
나는 당신을 얻었다.

113
00:03:23,390 --> 00:03:24,670
나는 당신을 얻었다.

114
00:03:24,670 --> 00:03:25,170
오.

115
00:03:25,170 --> 00:03:25,669
오.

116
00:03:25,669 --> 00:03:26,812
이 확인을 is--, 나는 당신을 얻었다.

117
00:03:26,812 --> 00:03:27,520
여기 스미스?

118
00:03:27,520 --> 00:03:28,894
>> 데이비드 J. 마란 : 스미스, 감사합니다.

119
00:03:28,894 --> 00:03:30,535
그래서 나는 스미스를 계속 찾고 있습니다?

120
00:03:30,535 --> 00:03:30,790
>> 인영 에스트라다 : 오, 그래.

121
00:03:30,790 --> 00:03:31,340
아니, 아니.

122
00:03:31,340 --> 00:03:31,600
아니, 오.

123
00:03:31,600 --> 00:03:31,940
이 내 꺼야.

124
00:03:31,940 --> 00:03:32,580
>> 데이비드 J. 마란 : 오, 당신이 스미스를 얻었다.

125
00:03:32,580 --> 00:03:33,415
그래.

126
00:03:33,415 --> 00:03:34,040
>> 인영 에스트라다 : 네,
여기 스미스를 얻었다.

127
00:03:34,040 --> 00:03:34,700
죄송합니다, 여러분.

128
00:03:34,700 --> 00:03:35,860
나는 Michael-- 생각 우리
마이클를 찾고 있었다.

129
00:03:35,860 --> 00:03:36,550
죄송합니다.

130
00:03:36,550 --> 00:03:37,550
>> 데이비드 J. 마란 : 그것은 확인을합니다.

131
00:03:37,550 --> 00:03:39,950
자, 이제 우리는있어
Paccini와 아들에.

132
00:03:39,950 --> 00:03:41,242
>> 인영 에스트라다 : Paccini와 아들.

133
00:03:41,242 --> 00:03:43,158
데이비드 J. 마란 : 당신 만
나는이에에 있습니다.

134
00:03:43,158 --> 00:03:44,050
그래.

135
00:03:44,050 --> 00:03:45,130
우리에게 마이크 스미스를 찾아보십시오.

136
00:03:45,130 --> 00:03:45,830
스미스.

137
00:03:45,830 --> 00:03:46,310
>> 인영 에스트라다 : 스미스.

138
00:03:46,310 --> 00:03:46,750
>> 데이비드 J. 마란 : 스미스.

139
00:03:46,750 --> 00:03:47,728
우리는 쓰레기에 대한 연구에있어.

140
00:03:47,728 --> 00:03:48,644
인영 에스트라다 : 쓰레기.

141
00:03:48,644 --> 00:03:50,096
오.

142
00:03:50,096 --> 00:03:52,480
이 시간이 걸릴 것입니다.

143
00:03:52,480 --> 00:03:54,340
>> [하하]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
데이비드 J. 마란 : 신발.

146
00:03:56,720 --> 00:03:58,080
우리는 신발에있어.

147
00:03:58,080 --> 00:04:00,210
>> 인영 에스트라다 : 이제 우리는 gonna--있어

148
00:04:00,210 --> 00:04:01,105
>> 데이비드 J. 마란 : 반갑습니다.

149
00:04:01,105 --> 00:04:01,980
인영 에스트라다 : Which--

150
00:04:01,980 --> 00:04:03,620
[하하]

151
00:04:03,620 --> 00:04:05,440
아,이 중대하다.

152
00:04:05,440 --> 00:04:06,910
[하하]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> 데이비드 J. 마란 : 그것은 확인을합니다.

155
00:04:09,390 --> 00:04:11,365
>> 인영 에스트라다 : 아,이 좋은 것입니다.

156
00:04:11,365 --> 00:04:14,425
내가 갈거야 생각하지 않습니다
이 후 PSAT 친구가 있습니다.

157
00:04:14,425 --> 00:04:15,300
데이비드 J. 마란 : 좋은.

158
00:04:15,300 --> 00:04:16,078
스포츠.

159
00:04:16,078 --> 00:04:17,036
인영 에스트라다 : 스포츠.

160
00:04:17,036 --> 00:04:18,668
음, L, M, N, O, P.

161
00:04:18,668 --> 00:04:19,459
데이비드 J. 마란 : OK.

162
00:04:19,459 --> 00:04:21,600
그럼 반이 찢어 보자.

163
00:04:21,600 --> 00:04:22,270
괜찮아요.

164
00:04:22,270 --> 00:04:25,606
이것은, 어쨌든 제대로 종료 마이크 때문에
스미스는 옐로우 페이지에되지 않습니다.

165
00:04:25,606 --> 00:04:26,430
>> 인영 에스트라다 : 아.

166
00:04:26,430 --> 00:04:27,140
>> 데이비드 J. 마란 : 아니, 괜찮아요.

167
00:04:27,140 --> 00:04:28,930
그러나 이제 척하자
그는이 페이지에 있습니다.

168
00:04:28,930 --> 00:04:33,260
그래서 지금, 당신은 아래로 문제를 깍습니다
한 페이지에, 우리는 마이크 스미스를 발견했다.

169
00:04:33,260 --> 00:04:35,180
>> [환호]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
확인, 감사합니다.

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
그래.

174
00:04:41,200 --> 00:04:43,646
즉, 특별한했다.

175
00:04:43,646 --> 00:04:45,954
하지만 여전히 빨랐다
선형 검색보다,

176
00:04:45,954 --> 00:04:47,870
에있어서 우리가 시작
책의 시작,

177
00:04:47,870 --> 00:04:51,210
왼쪽에서 오른쪽으로 우리는 우리의 길을 이동,
결국 마이크 스미스를 찾고.

178
00:04:51,210 --> 00:04:53,540
그래서, 만약 전화 번호부
아마 1,000 페이지를했습니다

179
00:04:53,540 --> 00:04:56,300
아마 촬영 한 것
우리 10 정도 페이지의 눈물.

180
00:04:56,300 --> 00:04:59,380
>> 하지만 당신은 활용했을 수 있습니다
가정을 감동

181
00:04:59,380 --> 00:05:03,602
이 모든 동안, 어떤 말을하는 것입니다
사전에 전화 번호부는 무엇이라고?

182
00:05:03,602 --> 00:05:04,310
청중 : 정렬.

183
00:05:04,310 --> 00:05:05,000
데이비드 J. 마란 : 그것은 분류입니다.

184
00:05:05,000 --> 00:05:05,160
권리?

185
00:05:05,160 --> 00:05:07,909
너무, 알파벳 순으로 정렬있어
그 이름과 전화 번호의 모든

186
00:05:07,909 --> 00:05:11,230
의에로 분류되어 있습니다
Z, 그리고 알파벳 사이.

187
00:05:11,230 --> 00:05:13,100
그러나 오늘, 우리는 지금 물어보세요
질문은 물론,

188
00:05:13,100 --> 00:05:16,170
어떻게 버라이존 또는 전화했다
회사는 그 상태로 그것을 얻을?

189
00:05:16,170 --> 00:05:19,560
>> 그것은 한 가지이기 때문에 활용하기
그 전제로, 따라서,

190
00:05:19,560 --> 00:05:22,570
문제를 해결
알고리즘보다 효율적으로.

191
00:05:22,570 --> 00:05:24,900
그러나 우리는 결코 정말
주 제로에 요청, 잘,

192
00:05:24,900 --> 00:05:27,790
비용 그것을 어떻게 많은
버라이존 또는 다른 사람

193
00:05:27,790 --> 00:05:29,620
정렬 된 순서로 그 전화 번호부를 얻을 수 있습니까?

194
00:05:29,620 --> 00:05:29,780
>> 권리?

195
00:05:29,780 --> 00:05:31,529
이 경우 문제가되지 않습니다
마이크 스미스를 찾고

196
00:05:31,529 --> 00:05:35,190
그것은 당신이 걸리는 경우, 슈퍼 빠른
올해는 처음에 페이지를 정렬합니다.

197
00:05:35,190 --> 00:05:35,690
권리?

198
00:05:35,690 --> 00:05:38,620
당신은뿐만 아니라 그냥 가려 낼 수 있습니다
무작위로 전화 번호부를 통해,

199
00:05:38,620 --> 00:05:40,690
그것은 슈퍼 영웅이 될 것 경우
그것을 정렬 할 비용.

200
00:05:40,690 --> 00:05:42,350
그래서 만약 우리가 또 다른 자원 봉사를 할 수 있습니다.

201
00:05:42,350 --> 00:05:46,350
의이 걸릴 여기까지 살펴 보자
우리는 어떻게 up-- 어서 might-- 방법

202
00:05:46,350 --> 00:05:48,100
우리는 이러한 분류에 대해 갈 수 있습니다.

203
00:05:48,100 --> 00:05:51,990
>> 그리고 만약 요르단 실제로 수
무대에 여기에 우리를 가입 할 수 있습니다.

204
00:05:51,990 --> 00:05:55,100
잠시 위해 가자.

205
00:05:55,100 --> 00:05:56,359
당신의 이름은 무엇입니까?

206
00:05:56,359 --> 00:05:57,150
그렇 : 캐롤라인.

207
00:05:57,150 --> 00:05:58,691
데이비드 J. 마란 : 캐롤라인, 최대 어서.

208
00:05:58,691 --> 00:06:02,070
그리고 당신은 가입 할 수 있습니다
여기에 나와 요르단.

209
00:06:02,070 --> 00:06:03,800
캐롤라인, 감사합니다.

210
00:06:03,800 --> 00:06:04,300
괜찮아.

211
00:06:04,300 --> 00:06:08,330
그래서 우리는 여기에 대해 무엇을
캐롤라인 (26) 푸른 책입니다

212
00:06:08,330 --> 00:06:10,747
FAS는 관리하는 데 사용하는
특정 최종 시험.

213
00:06:10,747 --> 00:06:13,330
이것들은 찾기 힘들지고있다
하지만 우리는 사전에 무슨 짓을했는지

214
00:06:13,330 --> 00:06:15,800
우리가 다른 사람의 이름을 넣어 한 것입니다
이들의 각각의 앞면에,

215
00:06:15,800 --> 00:06:18,133
그러나 우리는에 의해 간단하게 유지했습니다
다음 전체 이름을 넣어.

216
00:06:18,133 --> 00:06:22,720
그래서 우리는 이름을 가진 사람을 둘 것
L, D, J, B, 모든 방법 Z까지,

217
00:06:22,720 --> 00:06:24,090
하지만 그들은 임의의 순서입니다.

218
00:06:24,090 --> 00:06:26,890
그리고 당신은 것, 그래서 만약 당신의 이야기
당신과 같은 문제를 통해 방법

219
00:06:26,890 --> 00:06:31,620
그것은 당신이 앞서 갈 수 않고
에서 Z.에, 우리를 위해이를 정렬

220
00:06:31,620 --> 00:06:34,070
>> 청중 : OK, 그래서 L은 중간, 등이다.

221
00:06:34,070 --> 00:06:35,050
C를 시작했다.

222
00:06:35,050 --> 00:06:42,410
B. L. B 전에 J, Q :

223
00:06:42,410 --> 00:06:45,140
>> 데이비드 J. 마란 : 그 상태에서
일초에 대해 생각했다.

224
00:06:45,140 --> 00:06:48,910
그렇지 않으면 때문에, 이것은 단지입니다
당신, 나, 요르단에 흥미 롭군요.

225
00:06:48,910 --> 00:06:49,724
우리는 거기에 갈.

226
00:06:49,724 --> 00:06:50,640
청중 : [들림].

227
00:06:50,640 --> 00:06:57,299
R.

228
00:06:57,299 --> 00:06:58,090
데이비드 J. 마란 : OK.

229
00:06:58,090 --> 00:06:59,310
당신은 뭐하는거야?

230
00:06:59,310 --> 00:07:01,730
>> CAROLINE : M은 오 후 제공

231
00:07:01,730 --> 00:07:02,564
>> 데이비드 J. 마란 : OK.

232
00:07:02,564 --> 00:07:03,064
>> CAROLINE : O.

233
00:07:03,064 --> 00:07:04,120
데이비드 J. 마란 : 오, 좋아.

234
00:07:04,120 --> 00:07:04,970
>> CAROLINE : E.

235
00:07:04,970 --> 00:07:06,730
>> 데이비드 J. 마란 : E, F. 그래.

236
00:07:06,730 --> 00:07:07,620
>> CAROLINE : T, U, V.

237
00:07:07,620 --> 00:07:10,689
>> 데이비드 J. 마란 : V, T, U, V. 그것은 그래서
당신이 계속 making--있는 것처럼 보인다.

238
00:07:10,689 --> 00:07:12,730
당신이 만드는 것 같습니다
큰 더미 여기에,

239
00:07:12,730 --> 00:07:13,910
그리고 저기 큰 더미 가지.

240
00:07:13,910 --> 00:07:16,230
그래서 알파벳의 첫 번째 절반,
알파벳의 후반.

241
00:07:16,230 --> 00:07:16,460
그래.

242
00:07:16,460 --> 00:07:16,960
좋다.

243
00:07:16,960 --> 00:07:19,680
두 종류의 문제점을 분할.

244
00:07:19,680 --> 00:07:21,771
M, N, X의 네.

245
00:07:21,771 --> 00:07:22,270
CAROLINE : K.

246
00:07:22,270 --> 00:07:22,980
데이비드 J. 마란 : OK.

247
00:07:22,980 --> 00:07:25,070
케이는 그래서 당신은 가지 선택하고
다른 후에는 하나,

248
00:07:25,070 --> 00:07:27,620
왼쪽 또는 오른쪽 중 하나를 넣고,
또는 Z의 바닥에 가고.

249
00:07:27,620 --> 00:07:28,012
그래.

250
00:07:28,012 --> 00:07:29,190
>> 캐롤라인 : Z는 바닥에 것입니다.

251
00:07:29,190 --> 00:07:29,360
>> 데이비드 J. 마란 : OK.

252
00:07:29,360 --> 00:07:30,920
Y는 바닥에 것입니다.

253
00:07:30,920 --> 00:07:31,735
이제 우리는 X를 넣을 수 있습니다

254
00:07:31,735 --> 00:07:32,409
>> CAROLINE : G.

255
00:07:32,409 --> 00:07:33,700
데이비드 J. 마란은 : G의 왼쪽 간다.

256
00:07:33,700 --> 00:07:36,017
S 바로 것입니다.

257
00:07:36,017 --> 00:07:37,642
좋아, 왼쪽 모든 방법을 것입니다.

258
00:07:37,642 --> 00:07:38,790
>> CAROLINE : A, B, C, D

259
00:07:38,790 --> 00:07:39,873
>> 데이비드 J. 마란 : 지금, 좋은.

260
00:07:39,873 --> 00:07:43,260
우리는있어, B는 C를 W의 아래가 가고.

261
00:07:43,260 --> 00:07:45,566
좋아, T.

262
00:07:45,566 --> 00:07:46,611
>> CAROLINE : H, I, J

263
00:07:46,611 --> 00:07:47,860
데이비드 J. 마란 : H, I, J 좋은.

264
00:07:47,860 --> 00:07:49,160
그렇 : 중앙, 나는 gonna-- 해요

265
00:07:49,160 --> 00:07:50,000
데이비드 J. 마란 : OK.

266
00:07:50,000 --> 00:07:52,375
그래서 지금, 우리는 종류에가는거야
이러한 다양한 더미를 병합합니다.

267
00:07:52,375 --> 00:08:00,730
그래서 C를 통해, 그때 D를보고,
E 및 F, 및 G, 및 H, 및 I. 니스.

268
00:08:00,730 --> 00:08:05,540
J, K. 그리고,이 더미는
거꾸로,하지만 괜찮아요.

269
00:08:05,540 --> 00:08:06,040
물론.

270
00:08:06,040 --> 00:08:07,240
우리는 약간의 모서리를 잘라 수 있습니다.

271
00:08:07,240 --> 00:08:07,950
그래.

272
00:08:07,950 --> 00:08:10,530
그리고 우리는 W, X, Y, Z를 필요

273
00:08:10,530 --> 00:08:11,250
>> 그렇 : 네.

274
00:08:11,250 --> 00:08:11,880
>> 데이비드 J. 마란 : 우수한.

275
00:08:11,880 --> 00:08:14,122
그래서 큰는 당신을 감사합니다
이러한 정렬 캐롤라인.

276
00:08:14,122 --> 00:08:15,030
>> [환호]

277
00:08:15,030 --> 00:08:17,287
>> 고맙습니다.

278
00:08:17,287 --> 00:08:18,120
대단히 감사합니다.

279
00:08:18,120 --> 00:08:22,910
그래서 지금의이 순간을 생각해 보자
어떻게 캐롤라인은 그 일에 대해 갔다,

280
00:08:22,910 --> 00:08:26,040
그리고 정확히 우리
방법 이러시면 수 있었다 우리

281
00:08:26,040 --> 00:08:28,409
것을 해결 할 수 있었다
문제 때 우리가했다

282
00:08:28,409 --> 00:08:29,950
임의의 입력의 모두 주어진.

283
00:08:29,950 --> 00:08:31,610
>> 음,이처럼 보이는
이 시스템의 비트입니까?

284
00:08:31,610 --> 00:08:32,110
권리.

285
00:08:32,110 --> 00:08:34,495
이전 글자 그래서
알파벳, 그녀

286
00:08:34,495 --> 00:08:37,120
했다 왼쪽 퍼팅 및
알파벳에서 나중에 편지,

287
00:08:37,120 --> 00:08:38,270
그녀는 오른쪽에두고 있었다.

288
00:08:38,270 --> 00:08:40,500
그리고 곧 그녀는 발견
일부 인접 문자, 사람

289
00:08:40,500 --> 00:08:43,124
즉, 서로 바로 옆에 이동
그녀는 위해 사람들을 둘 것입니다.

290
00:08:43,124 --> 00:08:46,750
그래서 우리는 종류의이 작은 있었다
발생하는 정렬 된 입력의 더미.

291
00:08:46,750 --> 00:08:50,540
>> 그리고 그것은 매우 어떤 건지
우리의 대부분의 인간은 할 것이다.

292
00:08:50,540 --> 00:08:53,530
우리는 일종의 그것을 가려 낼 것이다,
우리는 종류의 메커니즘이있을 것이다.

293
00:08:53,530 --> 00:08:56,930
그러나 쓰기 어려울 수 있습니다
그 아래 수식 자체에.

294
00:08:56,930 --> 00:08:59,010
그것은보다 유기 조금 더 느꼈다.

295
00:08:59,010 --> 00:09:02,560
그래서 보자 경우 우리는 바운드 지금 할 수있는
적은 수의 입력을 가진 문제.

296
00:09:02,560 --> 00:09:05,170
>> 대신 26,하자
훨씬 적은 일을

297
00:09:05,170 --> 00:09:09,890
바로 뒤에, 일곱, 함께 말
이 문은, 말하자면.

298
00:09:09,890 --> 00:09:11,300
그냥 칠 수 있는가?

299
00:09:11,300 --> 00:09:15,240
그리고 지금 목표의 경우
손의 값을 찾을 수있다,

300
00:09:15,240 --> 00:09:17,850
의보고 얼마나 효율적으로하자
우리는이 일에 대해 갈 수 있습니다.

301
00:09:17,850 --> 00:09:22,460
그리고 우리가 지금 할 수있는 경우에 보자
몇 가지 숫자를 적용하기 시작,

302
00:09:22,460 --> 00:09:26,310
또는 일부 수식이있는 설명하기
우리의 전화 번호부의 효율성

303
00:09:26,310 --> 00:09:31,060
알고리즘, 우리의 시험 책 알고리즘 및
보다 일반적으로, 정보 탐색.

304
00:09:31,060 --> 00:09:34,770
>> 이것에 대한 그래서, 내가 앞서 가자하고,
터치 스크린에 여기에,

305
00:09:34,770 --> 00:09:41,100
이 웹 브라우저를 올려
정확히이 일곱 문.

306
00:09:41,100 --> 00:09:46,670
그리고 우리는 다른 하나를 얻을 수있는 경우
여기에 와서 자원 봉사,

307
00:09:46,670 --> 00:09:48,480
나는 여기에이 같은 문을 넣었습니다.

308
00:09:48,480 --> 00:09:49,170
빠른 자원 봉사.

309
00:09:49,170 --> 00:09:51,130
>> 이 one-- 데모가는거야
빨리와 빨리 지금.

310
00:09:51,130 --> 00:09:51,600
내려 가자.

311
00:09:51,600 --> 00:09:52,308
당신의 이름은 무엇입니까?

312
00:09:52,308 --> 00:09:53,040
트레버 : 트레버.

313
00:09:53,040 --> 00:09:53,998
>> 데이비드 J. 마란 : 트레버?

314
00:09:53,998 --> 00:09:55,770
좋아, 트레버는 아래에 제공됩니다.

315
00:09:55,770 --> 00:09:59,212
그래서 트레버는 여기에 자원 봉사를하고있다
비슷한 문제를, 그러나의 하나

316
00:09:59,212 --> 00:10:02,170
범위가 좁고, 그게 무슨
수 있도록 우리는 이제 공식화하려고합니다

317
00:10:02,170 --> 00:10:03,970
이 숫자를 정렬하는 과정.

318
00:10:03,970 --> 00:10:05,500
>> 그래서 트레버, 당신을 만나서 반갑습니다.

319
00:10:05,500 --> 00:10:08,720
그래서 여기 배열에, 그래서이다
일곱 문의 목록을 말한다.

320
00:10:08,720 --> 00:10:10,327
가서 우리에게 숫자 50를 찾을 수 있습니다.

321
00:10:10,327 --> 00:10:12,410
그리고 사실 후,
당신이 그것을 발견하는 방법을 알려주십시오.

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
모든 권리를 이따가해야합니다.

324
00:10:20,040 --> 00:10:21,945
그래, 여기에 하나는?

325
00:10:21,945 --> 00:10:24,680
어 오.

326
00:10:24,680 --> 00:10:25,560
그래.

327
00:10:25,560 --> 00:10:26,680
당신은 그 중 하나를 클릭했습니다.

328
00:10:26,680 --> 00:10:28,690
좋다.

329
00:10:28,690 --> 00:10:29,780
>> 그리고 좋은.

330
00:10:29,780 --> 00:10:30,970
지금 당신은 그 중 하나를 클릭했습니다.

331
00:10:30,970 --> 00:10:34,060
그리고 내가 당신에게 마이크를 줄 수 있도록,
그래서 당신은 단지 한 순간에 있습니다.

332
00:10:34,060 --> 00:10:37,000
가서 클릭
당신이 의도 옆집.

333
00:10:37,000 --> 00:10:39,812
네, 좋아요.

334
00:10:39,812 --> 00:10:41,020
트레버 : 나는 문을 unclick 수 있습니까?

335
00:10:41,020 --> 00:10:42,620
데이비드 J. 마란 : 아니, 당신은 unclick 수 없습니다.

336
00:10:42,620 --> 00:10:43,119
트레버 : OK.

337
00:10:43,119 --> 00:10:43,974
이 하나.

338
00:10:43,974 --> 00:10:45,640
데이비드 J. 마란 : 당신은 어디 가고 싶어?

339
00:10:45,640 --> 00:10:46,410
어느 것?

340
00:10:46,410 --> 00:10:47,230
>> 트레버 : 그 하나.

341
00:10:47,230 --> 00:10:48,042
>> 데이비드 J. 마란 : 번호

342
00:10:48,042 --> 00:10:48,450
>> 트레버 : OK.

343
00:10:48,450 --> 00:10:48,735
이 하나.

344
00:10:48,735 --> 00:10:49,020
>> 데이비드 J. 마란 : 예.

345
00:10:49,020 --> 00:10:49,700
그게 좋았다.

346
00:10:49,700 --> 00:10:50,380
괜찮아.

347
00:10:50,380 --> 00:10:53,900
그래서 알고리즘이 뭔지 나
이, 트레버을 수행하기위한 절차?

348
00:10:53,900 --> 00:10:56,149
>> 트레버 : 그냥 통해 갔다
문 전까지는 (50)를 발견했다.

349
00:10:56,149 --> 00:10:56,940
데이비드 J. 마란 : OK.

350
00:10:56,940 --> 00:10:58,150
우수한 알고리즘.

351
00:10:58,150 --> 00:10:59,540
그래서 괜찮아요.

352
00:10:59,540 --> 00:11:03,120
사실, 만약 내가 공개하기 때문에 무엇입니다
이 두 가지 다른 문 뒤에 무엇을

353
00:11:03,120 --> 00:11:06,954
우리는 여기에 찾을 수 있습니다
우리는 무작위로 입력을해야합니다.

354
00:11:06,954 --> 00:11:08,870
그래서 같은 사실이었다
당신이 얻을 수있는 좋은.

355
00:11:08,870 --> 00:11:12,509
그리고 사실, 당신은보다 더있어
철저하게 전체 배열을 검색,

356
00:11:12,509 --> 00:11:15,300
정말이었을 것 때문에
불운 한 당신이 수를 맞았 더라면

357
00:11:15,300 --> 00:11:16,604
맨 마지막 문 (50).

358
00:11:16,604 --> 00:11:18,520
하지만 대신에 우리 경우
당신에게 가정을했다.

359
00:11:18,520 --> 00:11:20,630
종류 모든 I를 가정
주변이 문,

360
00:11:20,630 --> 00:11:23,500
그래서 당신은이
번호는이 시간을 정렬

361
00:11:23,500 --> 00:11:29,730
하지만 이번에는 실제로이다
이 시간을 different--

362
00:11:29,730 --> 00:11:32,640
실제로 당신을 위해 분류입니다.

363
00:11:32,640 --> 00:11:35,380
손에 이제 목표
숫자 50를 공격하는 것입니다.

364
00:11:35,380 --> 00:11:36,090
>> 트레버 : OK.

365
00:11:36,090 --> 00:11:37,670
>> 데이비드 J. 마란 : 무엇이야
될 것 알고리즘?

366
00:11:37,670 --> 00:11:39,628
>> 트레버 : 그것은 음, 경우
분류, 그건 어느 것

367
00:11:39,628 --> 00:11:42,710
가장 큰 경우 최대로 이따가하고,
내림차순, 그것은 첫 번째있을 것이다

368
00:11:42,710 --> 00:11:44,751
또는 그 반대의 경우,
그것은 마지막 하나가 될 것입니다.

369
00:11:44,751 --> 00:11:48,897
그래서 난 그냥이 문을 누른 것
그럼 그냥 마지막 문을 누릅니다.

370
00:11:48,897 --> 00:11:49,980
데이비드 J. 마란 : 우수한.

371
00:11:49,980 --> 00:11:50,270
괜찮아.

372
00:11:50,270 --> 00:11:51,150
그래서 우리는 수 (50)를 발견했다.

373
00:11:51,150 --> 00:11:52,970
그래서 빨리 당신이 알고로
그들은 분류하고, 우리

374
00:11:52,970 --> 00:11:55,040
이 가정을 활용할 수 있었다.

375
00:11:55,040 --> 00:11:57,040
그래서 그들은 같은 너무 많은 것
전화 번호부 예.

376
00:11:57,040 --> 00:11:59,540
최대한 빨리, 심지어 함께 가지고
이 같은 작은 문제,

377
00:11:59,540 --> 00:12:02,380
당신의 입력을 미리 분류, 우리는 할 수
실제로 틀림없이 값을 찾을 수

378
00:12:02,380 --> 00:12:03,130
보다 효율적으로.

379
00:12:03,130 --> 00:12:05,800
>> 그리고 당신이 인 경우를 말하지 않았다
작은에 큰 작은, 또는 큰 분류

380
00:12:05,800 --> 00:12:08,080
그리고 그것은 매우 합리적이었다
한쪽 또는 다른에서 시작

381
00:12:08,080 --> 00:12:09,750
실제로 목표 값을 찾을 수있다.

382
00:12:09,750 --> 00:12:11,400
그래서뿐만 아니라 트레버에 감사드립니다.

383
00:12:11,400 --> 00:12:13,260
그리고 나는 잘 수행 propose-- 것이다.

384
00:12:13,260 --> 00:12:16,960
우리는, 실제로, 약간의 클립을 가지고
, CS50에서 우리가 제일 좋아하는 순간 중 하나입니다

385
00:12:16,960 --> 00:12:19,700
이에 때때로 이러한 데모
아주 계획에 따라 가지 않는다.

386
00:12:19,700 --> 00:12:22,050
그리고 실제로 지금, 나는
잘못된 인터페이스를 뽑아

387
00:12:22,050 --> 00:12:23,508
있는 터치 스크린을 사용하는 방법.

388
00:12:23,508 --> 00:12:24,660
그래서 내 잘못이 있었다.

389
00:12:24,660 --> 00:12:26,600
>> 따라서이에 대한 것
내년의 클립

390
00:12:26,600 --> 00:12:28,570
나는 내 자신의 화면을 클릭 한 이유에.

391
00:12:28,570 --> 00:12:31,390
그러나의 짧은 살펴 보자
작년에 무슨 일이 있었는지에

392
00:12:31,390 --> 00:12:34,770
많이 와서 제이,과
여기 트레버처럼, 자원 봉사

393
00:12:34,770 --> 00:12:39,380
이 짧은 클립에, 당신은 볼 수 있습니다
이 같은 데모는 매우하지 않았다 방법

394
00:12:39,380 --> 00:12:41,074
배운 같은 교훈을 알 수있다.

395
00:12:41,074 --> 00:12:41,740
[비디오 재생]

396
00:12:41,740 --> 00:12:45,360
나는 당신이 원하는 -all 지금
나를 위해 찾아하는 우리를 위해,

397
00:12:45,360 --> 00:12:51,674
정말, 수 (50)
한 번에 한 단계 씩.

398
00:12:51,674 --> 00:12:52,450
>> 년 - 수 (50)?

399
00:12:52,450 --> 00:12:53,190
>> 년 - 수 (50).

400
00:12:53,190 --> 00:12:55,356
그리고 당신은 무엇을 밝힐 수
이 문을 각 뒤에

401
00:12:55,356 --> 00:12:58,540
단순히 손가락으로 터치하여.

402
00:12:58,540 --> 00:13:00,910
젠장.

403
00:13:00,910 --> 00:13:02,870
>> [하하]

404
00:13:02,870 --> 00:13:03,806
>> [END 재생]

405
00:13:03,806 --> 00:13:05,430
데이비드 J. 마란 : 그래서 아주 잘했다.

406
00:13:05,430 --> 00:13:06,796
사람들은 정렬되지 않은 문이었다.

407
00:13:06,796 --> 00:13:08,670
그리고 제이, 물론,
너무 빨리 모든 것을 발견했다.

408
00:13:08,670 --> 00:13:12,910
트레버는 훨씬 더 나은 일을했다
가르침을받을만한 순간의 관점에서,

409
00:13:12,910 --> 00:13:15,850
그래서이 해에, 말하자면
오래 복용을 찾을 수 있습니다.

410
00:13:15,850 --> 00:13:17,950
물론, 우리는 준
제이 두 번째 기회,

411
00:13:17,950 --> 00:13:20,320
이에 우리는 문을 분류
우리는 트레버를 위해했던 것처럼,

412
00:13:20,320 --> 00:13:22,300
트레버 슈퍼 아니라이 시간을했다.

413
00:13:22,300 --> 00:13:26,124
그러나 제이는 절반 빨리했다.

414
00:13:26,124 --> 00:13:26,790
[비디오 재생]

415
00:13:26,790 --> 00:13:29,650
년 - 목표는 이제하다
우리에게 숫자 50를 찾을 수

416
00:13:29,650 --> 00:13:33,030
하지만 알고리즘을 수행하고
당신이 그것에 대해가는 여러분의 의견을 알려주세요.

417
00:13:33,030 --> 00:13:33,660
>> -그래.

418
00:13:33,660 --> 00:13:35,604
>> 당신이 그것을 발견하면 - 그리고, 당신은 영화를 유지한다.

419
00:13:35,604 --> 00:13:37,228
당신이 그것을 찾을 수없는 경우, 당신은 그것을 다시 제공합니다.

420
00:13:37,228 --> 00:13:38,044
>> -man.

421
00:13:38,044 --> 00:13:38,860
>> 오!

422
00:13:38,860 --> 00:13:40,800
>> - [들림] 확인을 클릭합니다.

423
00:13:40,800 --> 00:13:46,236
그래서 끝을 확인하는거야
오 there's-- 여부를 결정하는 첫 번째.

424
00:13:46,236 --> 00:13:48,646
>> [박수]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [END 재생]

427
00:13:55,729 --> 00:13:56,520
데이비드 J. 마란 : OK.

428
00:13:56,520 --> 00:13:59,760
그래서 명확하게 문을 정렬
효율성으로 이어집니다.

429
00:13:59,760 --> 00:14:01,680
그리고, 두 배 빠른
내가 거기에 의미하는 것입니다.

430
00:14:01,680 --> 00:14:03,270
그리고 제이는 운이 둘 시간을 얻었다.

431
00:14:03,270 --> 00:14:06,685
그리고 그는 또한 마지막에 운이있어
올해는 좀 블루 레이 디스크를 주문

432
00:14:06,685 --> 00:14:07,560
실제로 밖으로 제공합니다.

433
00:14:07,560 --> 00:14:09,768
나는 올해 미안 해요, 우리
트레버을 동일하지 않았다.

434
00:14:09,768 --> 00:14:11,540
그러나 더 나은 여전히​​ 몇 년이었다.

435
00:14:11,540 --> 00:14:14,820
그리고 여러분 중 몇몇은 이것을 알고 있습니다
그는 CS50에 있던 동료, 숀,

436
00:14:14,820 --> 00:14:17,780
정확한에 도전했다
같은 문제, SD에이기는하지만,

437
00:14:17,780 --> 00:14:19,360
당신은 곧 다시 하루에 볼 수있다.

438
00:14:19,360 --> 00:14:22,622
그리고 당신은하지 않았다 것을 확인할 수 있습니다
그는, 제이보다 조금 더 오래 걸릴

439
00:14:22,622 --> 00:14:25,580
트레버보다 조금 더, 그것은이었다
실제로이 좋은 기회

440
00:14:25,580 --> 00:14:29,820
거의 모든 사람이 참여하는
군중 라 가격 격려, 오른쪽입니다

441
00:14:29,820 --> 00:14:31,889
그에게 우리가 찾고 있던 번호를 찾을 수 있습니다.

442
00:14:31,889 --> 00:14:32,930
의하자. 빠른 살펴보십시오.

443
00:14:32,930 --> 00:14:33,320
>> [비디오 재생]

444
00:14:33,320 --> 00:14:33,820
>> -그래.

445
00:14:33,820 --> 00:14:36,680
그래서 여기에 귀하의 작업,
션은, 다음과 같다.

446
00:14:36,680 --> 00:14:40,860
나는이 뒤에 숨겨진
문 일곱 번째.

447
00:14:40,860 --> 00:14:45,120
그러나 이러한 문 중 일부에 자리 잡고
뿐만 아니라 다른 음수입니다.

448
00:14:45,120 --> 00:14:47,500
그리고 당신의 목표는 생각하는 것입니다
숫자의 맨 윗줄의

449
00:14:47,500 --> 00:14:50,390
단지 배열, 또는 그냥
종이 조각의 순서

450
00:14:50,390 --> 00:14:51,510
그들 뒤에 숫자.

451
00:14:51,510 --> 00:14:55,540
그리고 당신의 목표는 정상을 사용한다
배열 여기, 나에게 일곱 번째를 찾을 수 있습니다.

452
00:14:55,540 --> 00:14:58,570
그리고 우리는 비판 예정
당신은 그 일에 대해 가지 방법.

453
00:14:58,570 --> 00:14:59,070
-괜찮아.

454
00:14:59,070 --> 00:15:00,850
우리에게 일곱 번째를 바랍니다 -find.

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
아니.

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
다섯, 19, 13.

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [하하]

461
00:15:24,770 --> 00:15:25,910
>> 이 트릭 질문이 아니다.

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
하나.

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [하하]

466
00:15:34,695 --> 00:15:37,861
이 시점에서, 당신의 점수는 매우 아니다
좋은, 그래서 당신은뿐만 아니라 계속 있습니다.

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
세 가지.

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [하하]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> 계속해.

473
00:15:47,774 --> 00:15:50,690
솔직히, 나는 도움이되지만 궁금 수 없습니다
당신이 심지어 그러니까 ...에 대해 생각하고

474
00:15:50,690 --> 00:15:51,959
>> [하하]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
만 맨 윗줄, 그래서
세 왼쪽 있어요.

477
00:15:55,020 --> 00:15:56,200
그래서 나에게 일곱을 찾을 수 있습니다.

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [하하]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17.

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
세븐.

484
00:16:26,946 --> 00:16:28,780
>> [박수]

485
00:16:28,780 --> 00:16:29,426
>> 괜찮아.

486
00:16:29,426 --> 00:16:30,360
>> [END 재생]

487
00:16:30,360 --> 00:16:31,840
>> 데이비드 J. 마란 : 그래서 우리는 할 수
이 하루 종일보세요.

488
00:16:31,840 --> 00:16:34,090
의 그리고 물론, 일부
올해의 데모 아마도

489
00:16:34,090 --> 00:16:36,330
지금 다음에 종료됩니다
올해의 비디오뿐만 아니라.

490
00:16:36,330 --> 00:16:39,040
그래서 지금 실제로하자
알고리즘에 초점

491
00:16:39,040 --> 00:16:42,140
우리가 할 수없는 경우에는 여기에, 볼
지금 공식화하기 시작

492
00:16:42,140 --> 00:16:46,650
우리는 우리의 데이터를 가져 오는에 대해 갈 수있는 방법
이 상태로는 분류 있다고,

493
00:16:46,650 --> 00:16:50,054
그래서 궁극적으로, 우리가 실제로 할 수있는
더 효율적으로 검색 할 수 있습니다.

494
00:16:50,054 --> 00:16:52,470
그리고 우리는거야에도 불구하고
상당히 작은 데이터 세트를 사용하려면

495
00:16:52,470 --> 00:16:54,511
8 자리 숫자의 우리처럼
보드에 여기있다,

496
00:16:54,511 --> 00:16:58,230
궁극적으로이 같은 아이디어를 적용 할 수
1000 입력에, 만 입력,

497
00:16:58,230 --> 00:17:02,100
40 억 투입, 알고리즘 때문에
근본적으로 동일 할 것입니다.

498
00:17:02,100 --> 00:17:05,359
>> 그리고 이것이 우리의 마지막
자원 봉사자 오늘의 기회,

499
00:17:05,359 --> 00:17:09,790
하지만 아마도 가장 참여 하나,
있는 우리는 여덟 자원 봉사자가 필요

500
00:17:09,790 --> 00:17:12,960
와서 통해 우리를 걸어
정렬 방법 무엇 곧 것

501
00:17:12,960 --> 00:17:15,212
이러한 음악에있을 여기에 서있다.

502
00:17:15,212 --> 00:17:16,170
내가 여기 다시 시작하자.

503
00:17:16,170 --> 00:17:19,692
>> 그래서 turquoise-- 녹색 하나는 무엇입니까?

504
00:17:19,692 --> 00:17:21,130
당신은 커밋하고 있습니까?

505
00:17:21,130 --> 00:17:21,630
두.

506
00:17:21,630 --> 00:17:23,069
내려 가자.

507
00:17:23,069 --> 00:17:23,569
그래.

508
00:17:23,569 --> 00:17:24,420
세 가지.

509
00:17:24,420 --> 00:17:25,400
네.

510
00:17:25,400 --> 00:17:27,247
다섯 확인 가구 있구만하자.

511
00:17:27,247 --> 00:17:28,830
당신은 당신의 친구에 의해 지명되는 것입니다.

512
00:17:28,830 --> 00:17:31,340
여섯, 일곱, 여덟.

513
00:17:31,340 --> 00:17:32,130
최대 어서.

514
00:17:32,130 --> 00:17:32,630
괜찮아.

515
00:17:32,630 --> 00:17:33,190
정말 고맙습니다.

516
00:17:33,190 --> 00:17:33,689
최대 어서.

517
00:17:33,689 --> 00:17:34,790
최대 어서.

518
00:17:34,790 --> 00:17:35,330
>> 괜찮아.

519
00:17:35,330 --> 00:17:38,890
그래서 우리는 here--이가 무엇을
더 어색한 것 중 하나입니다,

520
00:17:38,890 --> 00:17:42,390
이 이후 그에게 유머가 필요합니다
시간이 조금 저.

521
00:17:42,390 --> 00:17:43,442
당신은 숫자 하나가 될 것이다.

522
00:17:43,442 --> 00:17:44,150
당신의 이름은 무엇입니까?

523
00:17:44,150 --> 00:17:44,610
>> 아난 : 아난.

524
00:17:44,610 --> 00:17:45,526
>> 데이비드 J. 마란 : 아난.

525
00:17:45,526 --> 00:17:46,092
데이비드.

526
00:17:46,092 --> 00:17:46,800
당신의 이름은 무엇입니까?

527
00:17:46,800 --> 00:17:47,140
>> 조셉 조셉.

528
00:17:47,140 --> 00:17:49,190
>> 데이비드 J. 마란 : 조셉,
당신은 두 번째입니다.

529
00:17:49,190 --> 00:17:52,260
>> 세레나 : 세레나, 3 번.

530
00:17:52,260 --> 00:17:53,722
스테판 네 번째.

531
00:17:53,722 --> 00:17:54,430
CYNTHIA : 신시아.

532
00:17:54,430 --> 00:17:57,548
데이비드 J. 마란 : 신시아, 5 번.

533
00:17:57,548 --> 00:17:58,452
[들림]

534
00:17:58,452 --> 00:17:59,618
데이비드 J. 마란 : [들림].

535
00:17:59,618 --> 00:18:00,391
데이비드, 여섯 번째.

536
00:18:00,391 --> 00:18:00,890
매트 : 매트.

537
00:18:00,890 --> 00:18:02,160
데이비드 J. 마란 : 매트의 일곱 번째.

538
00:18:02,160 --> 00:18:02,850
그리고?

539
00:18:02,850 --> 00:18:03,210
>> WAVERLY : 웨버.

540
00:18:03,210 --> 00:18:04,470
>> 데이비드 J. 마란 : 웨버, 여덟.

541
00:18:04,470 --> 00:18:04,970
괜찮아.

542
00:18:04,970 --> 00:18:06,510
경우에 당신은 으악를 could--.

543
00:18:06,510 --> 00:18:08,820
여러분 모두의 경우, 같은
거기에 첫 도전,

544
00:18:08,820 --> 00:18:10,820
여덟 음악 스탠드는
여기에 관객을 직면.

545
00:18:10,820 --> 00:18:14,200
당신은 당신의 숫자를 넣을 수 있다면
이러한 음악은 가로막는

546
00:18:14,200 --> 00:18:16,560
그들은 함께 줄 것을
보드에 같은 번호.

547
00:18:16,560 --> 00:18:19,560
그래서 자신에 의해처럼 보이게
이러한 음악에 당신의 숫자를 넣어

548
00:18:19,560 --> 00:18:21,960
여기에 서있다.

549
00:18:21,960 --> 00:18:25,980
우수 지금까지.

550
00:18:25,980 --> 00:18:26,600
>> 우수.

551
00:18:26,600 --> 00:18:26,890
그래.

552
00:18:26,890 --> 00:18:29,556
그래서 지금, 우리는 물어거야
몇 가지 다른 방법으로 질문입니다.

553
00:18:29,556 --> 00:18:31,610
우리는 어떻게 정렬에 대해 갈 수 있습니다
여기이 사람들까지?

554
00:18:31,610 --> 00:18:34,500
우리는 몇 가지 방법을 가지고 있기 때문에
이전에, 우리는 이에했다

555
00:18:34,500 --> 00:18:36,360
종류의 서로 다른 두 가지 버킷을.

556
00:18:36,360 --> 00:18:38,842
그리고 우리가 일반적이었다
함께 일을 조립할.

557
00:18:38,842 --> 00:18:41,050
곧 우리는 두 숫자를 보았다로
즉, 함께 지배

558
00:18:41,050 --> 00:18:41,975
우리가 함께 넣어.

559
00:18:41,975 --> 00:18:43,350
함께 속해 두 글자.

560
00:18:43,350 --> 00:18:45,058
>> 그러나의가 있는지 확인하자 우리
이 공식화 할 수 없습니다,

561
00:18:45,058 --> 00:18:48,044
우리가 궁극적으로이 너무
당신은 몇 가지 의사 코드,

562
00:18:48,044 --> 00:18:49,710
있는 이러한 문제를 해결할 수 있습니다.

563
00:18:49,710 --> 00:18:51,870
그래서 지금, 내가 찾고 있어요
여기에이 숫자에서.

564
00:18:51,870 --> 00:18:55,030
그리고 실수의 전체 무리를 참조하십시오.

565
00:18:55,030 --> 00:18:57,750
결국, 내가 하나를 원하는
왼쪽과 오른쪽 팔.

566
00:18:57,750 --> 00:19:00,650
>> 그래서 내가 찾고 있어요
이들 2 개, 4 개 및 두.

567
00:19:00,650 --> 00:19:02,930
그리고 문제는 분명히 무엇인가?

568
00:19:02,930 --> 00:19:04,261
그래.

569
00:19:04,261 --> 00:19:04,760
겠어요 -

570
00:19:04,760 --> 00:19:07,160
두 분명히하기 전에 온다
네, 그래서 당신은 무엇을 알아?

571
00:19:07,160 --> 00:19:10,210
내가 먼저 욕심 방법을 보자,
많은 같은 문제가됩니다

572
00:19:10,210 --> 00:19:13,790
당신이에서 기억 경우 one-- 설정
문제 하나를 설정의 표준 버전,

573
00:19:13,790 --> 00:19:16,820
여기서 난 그냥 로컬 문제를 해결
즉, 내 앞에 바로 여기

574
00:19:16,820 --> 00:19:17,690
이 날 리드 어디를 참조하십시오.

575
00:19:17,690 --> 00:19:17,870
>> 그래.

576
00:19:17,870 --> 00:19:20,161
그래서 두 네, 날 가자
앞서 단지 당신에게 두 가지를 교환.

577
00:19:20,161 --> 00:19:22,400
당신은 물리적으로 이동 할 수있는 경우
자신과 당신의 종이,

578
00:19:22,400 --> 00:19:25,040
나는를받은 것 같다
더 나은 상태로 나열합니다.

579
00:19:25,040 --> 00:19:26,330
>> 지금, 그들은 좋은거야.

580
00:19:26,330 --> 00:19:28,480
나는, 이동거야
네 여섯, 좋은 보인다.

581
00:19:28,480 --> 00:19:29,110
문제가 아니다.

582
00:19:29,110 --> 00:19:30,440
여섯 여덟, 확인을 클릭합니다.

583
00:19:30,440 --> 00:19:31,860
여덟 하나, 또 다른 문제.

584
00:19:31,860 --> 00:19:34,750
팔 하나에 대한 사실 무엇 때문에?

585
00:19:34,750 --> 00:19:36,990
하나는, 여덟 전에 온다
그래서 우리는 어떻게해야합니까?

586
00:19:36,990 --> 00:19:38,090
의이 두 가지를 교환 할 수 있습니다.

587
00:19:38,090 --> 00:19:39,316
(1 ~ 8).

588
00:19:39,316 --> 00:19:40,690
그리고 지금, 나는 계속거야.

589
00:19:40,690 --> 00:19:42,030
나는 계속 찾고 유지하는거야.

590
00:19:42,030 --> 00:19:42,840
그리고 이제 어떻게되는지 보자.

591
00:19:42,840 --> 00:19:44,680
여덟 세의
물론, 순서가.

592
00:19:44,680 --> 00:19:45,815
의 스왑을 보자.

593
00:19:45,815 --> 00:19:46,940
물론 여덟 일곱.

594
00:19:46,940 --> 00:19:47,481
고장난.

595
00:19:47,481 --> 00:19:48,280
의 스왑을 보자.

596
00:19:48,280 --> 00:19:49,940
여덟 다섯, 물론,하자의 스왑.

597
00:19:49,940 --> 00:19:50,560
괜찮아.

598
00:19:50,560 --> 00:19:51,880
목록 정렬됩니다.

599
00:19:51,880 --> 00:19:53,060
네?

600
00:19:53,060 --> 00:19:54,280
>> 확인을 분명하지.

601
00:19:54,280 --> 00:19:55,860
그러나 그것은 바로, 조금 더 나은 무엇입니까?

602
00:19:55,860 --> 00:19:57,270
무슨 일이 있었 통지 무엇 때문에.

603
00:19:57,270 --> 00:20:01,749
때마다 우리는 스왑을 수행 작은
수 종류의 그런 식으로 여과 된,

604
00:20:01,749 --> 00:20:03,790
그리고 더 큰 수
이 방법으로 여과 된, 또는 우리는거야

605
00:20:03,790 --> 00:20:06,880
에 버블 말했다고 전했습니다 시작
왼쪽 또는 오른쪽으로 버블.

606
00:20:06,880 --> 00:20:10,080
>> 지금, 그것은 때문에, 충분하지 않습니다
기껏해야 수는 수도

607
00:20:10,080 --> 00:20:11,990
한 자리를 옮겼습니다
순방향 또는 최악

608
00:20:11,990 --> 00:20:13,880
숫자가있을 수 있습니다
추가로 한 자리를 옮겼습니다.

609
00:20:13,880 --> 00:20:16,369
그래서 당신은 무엇을, 이런 종류의 알
의 지금까지 꽤 잘했다.

610
00:20:16,369 --> 00:20:17,410
나 그냥 다시 해보자.

611
00:20:17,410 --> 00:20:18,880
두 네, 그들은 OK입니다.

612
00:20:18,880 --> 00:20:20,180
네 여섯, 그들은 OK입니다.

613
00:20:20,180 --> 00:20:21,790
여섯 하나, 순서가.

614
00:20:21,790 --> 00:20:23,007
그럼 두를 교환 할 수 있습니다.

615
00:20:23,007 --> 00:20:25,840
그리고 지금, 문제의 통지
더 나은 다시 조금지기 시작.

616
00:20:25,840 --> 00:20:27,006
여섯 세, 순서가.

617
00:20:27,006 --> 00:20:28,100
이제 두를 교환 할 수 있습니다.

618
00:20:28,100 --> 00:20:29,730
여섯 일곱, 당신은 좋은거야.

619
00:20:29,730 --> 00:20:32,230
세븐 다섯 물론, 순서가.

620
00:20:32,230 --> 00:20:33,920
순서대로 일곱 여덟.

621
00:20:33,920 --> 00:20:36,470
그리고 지금, 내가해야 할 수도 있습니다
더이 몇 번을한다.

622
00:20:36,470 --> 00:20:39,830
그리고 사실, 자신에 대한 생각
아마도 얼마나 많은 시간을 최대로

623
00:20:39,830 --> 00:20:41,330
나는 앞뒤로 걸어해야 할 수도 있습니다?

624
00:20:41,330 --> 00:20:42,390
>> 우리는 다시 그에게 올 것이다.

625
00:20:42,390 --> 00:20:43,700
그래서이 네 아직 확인합니다.

626
00:20:43,700 --> 00:20:44,940
네 하나, 아니.

627
00:20:44,940 --> 00:20:45,747
그래서, 스왑을 할 수 있습니다.

628
00:20:45,747 --> 00:20:47,830
그리고 다시, 시각적으로 알
하나는 버블 링 종류

629
00:20:47,830 --> 00:20:49,163
그것이 있어야 왼쪽에.

630
00:20:49,163 --> 00:20:50,010
네 세 스왑.

631
00:20:50,010 --> 00:20:51,330
네 여섯.

632
00:20:51,330 --> 00:20:53,100
여섯 다섯 스왑.

633
00:20:53,100 --> 00:20:53,959
여섯 일곱.

634
00:20:53,959 --> 00:20:55,000
일곱 여덟은 좋다.

635
00:20:55,000 --> 00:20:55,500
>> 좋다.

636
00:20:55,500 --> 00:20:58,460
우리는 더 나은 있어요.

637
00:20:58,460 --> 00:20:59,130
그래서 보자.

638
00:20:59,130 --> 00:21:00,940
이제, 우리는이 하나 있습니다.

639
00:21:00,940 --> 00:21:02,520
물론, 교체.

640
00:21:02,520 --> 00:21:07,520
2와 3, 3과 4, 넷
다섯, 여섯 일곱, 일곱 여덟.

641
00:21:07,520 --> 00:21:08,020
좋다.

642
00:21:08,020 --> 00:21:08,730
그리고 당신은 무엇을 알아?

643
00:21:08,730 --> 00:21:11,190
, 내가 거기에 하나의 변화를 만들었 기 때문에
나 하나의 전성 검사를 할 수 있습니다.

644
00:21:11,190 --> 00:21:13,023
나에게 모든 방법을 가자
다시 처음으로.

645
00:21:13,023 --> 00:21:13,680
그래.

646
00:21:13,680 --> 00:21:14,750
하나, 그래 two-- 참조?

647
00:21:14,750 --> 00:21:15,870
뭔가 잘못이었다.

648
00:21:15,870 --> 00:21:18,420
셋, 넷, 다섯, 여섯, 일곱, 여덟.

649
00:21:18,420 --> 00:21:21,920
그리고이 마지막 패스입니다
내 지금 당신 편안

650
00:21:21,920 --> 00:21:23,830
그것은 정렬 소유권 주장?

651
00:21:23,830 --> 00:21:24,330
그래.

652
00:21:24,330 --> 00:21:25,880
시각적으로, 그 절대적으로 사실입니다.

653
00:21:25,880 --> 00:21:28,410
그러나 기능적으로, 무엇을
또한 단지 일어 났습니까

654
00:21:28,410 --> 00:21:31,870
당신을 허용하는 마지막 단계에서
이 목록이 실제로 있는지 확인하기

655
00:21:31,870 --> 00:21:32,660
분류?

656
00:21:32,660 --> 00:21:34,477
>> 나는 무엇을 또는​​이 마지막 패스를하지 않았다?

657
00:21:34,477 --> 00:21:35,810
청중 : 아무 변화가 없었다.

658
00:21:35,810 --> 00:21:36,120
데이비드 J. 마란 : 죄송합니다?

659
00:21:36,120 --> 00:21:37,070
청중 : 변경 사항이 없습니다.

660
00:21:37,070 --> 00:21:38,653
데이비드 J. 마란은 : 어떤 변화가 없었다.

661
00:21:38,653 --> 00:21:41,947
그래서 나를 바보 될 것
다시 동일한 알고리즘을

662
00:21:41,947 --> 00:21:43,780
나는 어떤을하지 않은 경우
첫 번째 시간을 변경합니다.

663
00:21:43,780 --> 00:21:45,160
그리고 상태가 변경되지 않았습니다.

664
00:21:45,160 --> 00:21:47,576
분명히, 내가 만들려고하고 있지 않다
어떤 두 번째 시간을 변경합니다.

665
00:21:47,576 --> 00:21:49,820
그리고, 지금은 안전
말을, 목록 정렬됩니다.

666
00:21:49,820 --> 00:21:52,069
>> 그리고 실제로, 이것은 지금
뭔가 우리가 일반적으로 정액을

667
00:21:52,069 --> 00:21:56,900
전화 거품 정렬, 이에 페어,
당신은, 다시 실수를 수정

668
00:21:56,900 --> 00:22:00,210
다시, 다시, 당신에게
앞뒤로 계속,

669
00:22:00,210 --> 00:22:03,370
앞뒤로, 당신까지
이러한 스왑을 확인하지 않는 점에서

670
00:22:03,370 --> 00:22:07,089
당신은 내가, 그래, 확신 할 수 있습니다
실수의 모든 고정 마쳤다.

671
00:22:07,089 --> 00:22:08,630
의 재설정과 다른 접근 방식을 해보자.

672
00:22:08,630 --> 00:22:11,590
너희들은 다시 갈 수 있다면
순서는 당신이 순간 전이었다

673
00:22:11,590 --> 00:22:13,780
이는이처럼 보였다.

674
00:22:13,780 --> 00:22:17,640
이제, 접근을 보자
더 시험 책처럼 작은,

675
00:22:17,640 --> 00:22:21,122
이에 우리는 지속적으로 있었다
알파벳의 문자를 선택

676
00:22:21,122 --> 00:22:22,830
우리는 종류의 원이
다음을 처리합니다.

677
00:22:22,830 --> 00:22:26,420
아마 높은 편지였다,
또는 낮은 편지 Z. 등

678
00:22:26,420 --> 00:22:28,170
>> 그래서 모든 사람들이 다시이 순서입니다.

679
00:22:28,170 --> 00:22:29,800
그리고 지금 내가이 작업을 수행 할 수 있습니다.

680
00:22:29,800 --> 00:22:34,880
의는 내가 알고 보자
여기에 8 자리 숫자.

681
00:22:34,880 --> 00:22:37,410
나는 앞서 갈거야 및
다만 의도적으로 선택

682
00:22:37,410 --> 00:22:38,520
가장 작은 요소.

683
00:22:38,520 --> 00:22:38,760
권리?

684
00:22:38,760 --> 00:22:39,801
이것도 직관적 보인다.

685
00:22:39,801 --> 00:22:42,560
이유는 작은 발견하지 않습니다
그것이 어디에 속하는 원소, 넣어

686
00:22:42,560 --> 00:22:45,280
그 다음 작은 요소를 얻을 넣어
그것은 그것이 속하는 단지 반복한다.

687
00:22:45,280 --> 00:22:46,820
>> 직관적 때문에
그것도 작동합니다.

688
00:22:46,820 --> 00:22:48,441
그래서 네, 그건 아주 작은 수입니다.

689
00:22:48,441 --> 00:22:49,940
나는이 곳을 기억하겠습니다.

690
00:22:49,940 --> 00:22:50,523
분을 기다립니다.

691
00:22:50,523 --> 00:22:51,577
두 작다.

692
00:22:51,577 --> 00:22:53,910
내가 지금 위치를 기억하자 두
이며, 약 4 잊지.

693
00:22:53,910 --> 00:22:55,050
우리는 나중에 다룰 것이다.

694
00:22:55,050 --> 00:22:56,460
여섯, 난 관심 없어.

695
00:22:56,460 --> 00:22:57,810
여덟, 나는에 관심이 아니에요.

696
00:22:57,810 --> 00:22:59,780
하나는 내 새로운 작은 수입니다.

697
00:22:59,780 --> 00:23:01,470
그래서 하나는 위치를 기억거야.

698
00:23:01,470 --> 00:23:02,534
세, 관심이 없습니다.

699
00:23:02,534 --> 00:23:03,450
세븐, 관심이 없습니다.

700
00:23:03,450 --> 00:23:04,530
다섯, 관심이 없습니다.

701
00:23:04,530 --> 00:23:07,390
>> 탈락하지 않고 그래서
단 올해,

702
00:23:07,390 --> 00:23:09,890
나는 수를 잡아 갈거야 one--
당신의 이름은 또 무엇인가?

703
00:23:09,890 --> 00:23:10,150
>> 아난 : 아난.

704
00:23:10,150 --> 00:23:11,220
>> 데이비드 J. 마란 : 아난.

705
00:23:11,220 --> 00:23:13,540
그리고 당신은 저에 가입 할 수 있다면
리스트의 처음

706
00:23:13,540 --> 00:23:14,870
당신이 속한 곳의 당신을 만들어 보자.

707
00:23:14,870 --> 00:23:16,080
아쉽게도 당신의 이름은 무엇입니까?

708
00:23:16,080 --> 00:23:16,650
>> 스테판 : 스테판.

709
00:23:16,650 --> 00:23:18,191
>> 데이비드 J. 마란 : 스테판 방법입니다.

710
00:23:18,191 --> 00:23:23,490
스테판이를 해결하기 전에 그래서
문제는, 우리는 무엇을해야합니까?

711
00:23:23,490 --> 00:23:25,412
우리는 스테판 무엇을해야합니까?

712
00:23:25,412 --> 00:23:27,269
>> 청중 : [들림].

713
00:23:27,269 --> 00:23:28,060
데이비드 J. 마란 : OK.

714
00:23:28,060 --> 00:23:28,850
그래서 우리는 그렇게 할 수 있습니다.

715
00:23:28,850 --> 00:23:31,730
우리는 종류의 스테판과이 걸릴 수 있습니다 자신의
네, 그냥 변수에 넣어

716
00:23:31,730 --> 00:23:33,530
과 위해에 개최
일정 시간,

717
00:23:33,530 --> 00:23:35,220
따라서 번호를 하나의 공간을 만들기.

718
00:23:35,220 --> 00:23:36,280
그리고는 나쁘지 않다.

719
00:23:36,280 --> 00:23:39,270
나는 왜 안 할, 제안 할 수
우리는 여기 스테판를 넣어?

720
00:23:39,270 --> 00:23:41,610
왜이 일을 위반할 수
아이디어 우리가 시작

721
00:23:41,610 --> 00:23:44,830
지난 주, 지난 시간에 대해 얘기?

722
00:23:44,830 --> 00:23:45,330
그래?

723
00:23:45,330 --> 00:23:45,740
>> 청중 : [들림].

724
00:23:45,740 --> 00:23:46,860
>> 데이비드 J. 마란 : 그것은에 대한 인덱스가 없습니다.

725
00:23:46,860 --> 00:23:49,735
이 같은 사실이 생각하는 경우
배열이 음의 하나처럼,

726
00:23:49,735 --> 00:23:52,900
그래서 메모리는 실제로 없다
여기가 참으로 배열 인 경우,

727
00:23:52,900 --> 00:23:55,090
같은 우리는 강연에서 지난 주 선언했다.

728
00:23:55,090 --> 00:23:56,250
그래서 우리는이 작업을 수행해서는 안됩니다.

729
00:23:56,250 --> 00:23:57,340
우리는 변수에 저장할 수 있습니다.

730
00:23:57,340 --> 00:23:57,820
>> 아니면 그거 알아?

731
00:23:57,820 --> 00:23:59,153
나는 다른 사람이 그것을 제안 들었다.

732
00:23:59,153 --> 00:24:01,020
우리는 스테판과 다른 무엇을 할 수 있습니까?

733
00:24:01,020 --> 00:24:03,770
왜 우리가 그를 축출하지 않고
번호 하나는 어디를 통해 그를 넣어.

734
00:24:03,770 --> 00:24:05,170
당신이 거기 가고 싶어한다면.

735
00:24:05,170 --> 00:24:07,300
그리고 실제로, 이것이
꽤 좋은 솔루션입니다.

736
00:24:07,300 --> 00:24:10,480
이제 한 손에, 나는 종류했습니다
의 악화 문제를했다.

737
00:24:10,480 --> 00:24:13,650
네 멀리 떨어져 지금이다
그것이 있어야하는 곳에서.

738
00:24:13,650 --> 00:24:14,900
그것은이 절반으로해야한다.

739
00:24:14,900 --> 00:24:16,100
>> 하지만 당신은 알아?

740
00:24:16,100 --> 00:24:17,630
즉 불운 수 있었다.

741
00:24:17,630 --> 00:24:18,822
아마 여덟 여기에 있었다.

742
00:24:18,822 --> 00:24:20,530
그래서, 어쩌면 우리는 것
운이 입수했습니다,

743
00:24:20,530 --> 00:24:22,460
끝까지 여덟 가깝게 밀려.

744
00:24:22,460 --> 00:24:24,710
하루의 끝에서 그래서,
그것은 종류의 모든 평균 밖으로.

745
00:24:24,710 --> 00:24:26,085
우리는 약 4 상관 할 필요가 없습니다.

746
00:24:26,085 --> 00:24:29,400
내가 지금 걱정하는 모든입니다
작은 요소를 선택하는 단계를 포함한다.

747
00:24:29,400 --> 00:24:32,030
>> 그리고 지금, 나는 무슨거야
번호 하나 잊어하면된다

748
00:24:32,030 --> 00:24:35,160
영구적으로, 내가 알고 있기 때문에
내 뒤에 목록은 현재 정렬됩니다.

749
00:24:35,160 --> 00:24:36,720
그래서 내 목록은 이전에 크기 여덟 살.

750
00:24:36,720 --> 00:24:37,720
지금, 그것은 크기 일곱입니다.

751
00:24:37,720 --> 00:24:40,340
그래서 내 문제는 점점
선형이기는하지만, 작은.

752
00:24:40,340 --> 00:24:43,022
그래서 지금, 나는를 선택하는거야
현재 가장 작은 요소, 두.

753
00:24:43,022 --> 00:24:46,520
여섯, 여덟, 넷, 셋, 일곱, 다섯.

754
00:24:46,520 --> 00:24:47,770
즉, 가장 작은 요소였다.

755
00:24:47,770 --> 00:24:49,416
그래서 나는 일 해요 할 예정입니다
이름이 다시 무엇입니까?

756
00:24:49,416 --> 00:24:49,760
>> 조셉 조셉.

757
00:24:49,760 --> 00:24:50,085
>> 데이비드 J. 마란 : 조셉?

758
00:24:50,085 --> 00:24:52,000
우리는 장소에 요셉을 떠날 것입니다.

759
00:24:52,000 --> 00:24:54,842
지금, 나는 척하는거야
이 사람들이 잘으로 죠 것을,

760
00:24:54,842 --> 00:24:56,550
내가 알고있는이 두
이미 분류되어 있습니다.

761
00:24:56,550 --> 00:24:58,424
의 현재에 집중하자
목록의 나머지.

762
00:24:58,424 --> 00:25:00,080
식스 전류 작다.

763
00:25:00,080 --> 00:25:01,190
여덟 크다.

764
00:25:01,190 --> 00:25:02,970
네 지금 현재 가장 작다.

765
00:25:02,970 --> 00:25:04,762
세 지금 현재 가장 작다.

766
00:25:04,762 --> 00:25:07,720
그리고 지금, 나는 세 가지를 선택하는거야
누가 이름이 다시 무엇 is--?

767
00:25:07,720 --> 00:25:08,190
세레나 : 세레나.

768
00:25:08,190 --> 00:25:10,620
데이비드 J. 마란 : 세레나, 당신이 할 수있는 경우
전화 번호 및 스왑 일 해요 잡아

769
00:25:10,620 --> 00:25:11,550
KALSANG : Kalsang.

770
00:25:11,550 --> 00:25:12,940
데이비드 J. 마란 : Kalsang.

771
00:25:12,940 --> 00:25:15,220
돌아 가자, 우리는있어
그 두 가지를 교환하는 것.

772
00:25:15,220 --> 00:25:17,360
그리고 지금, 자동 조종 장치에이를 만들어 보자.

773
00:25:17,360 --> 00:25:21,589
내가 가서 너희에게 맡겨거야
다음 작은 요소를 선택합니다.

774
00:25:21,589 --> 00:25:22,380
던, 암갈색, 암갈색, 암갈색.

775
00:25:22,380 --> 00:25:24,560
네 번째, 당신은 무엇을해야합니까?

776
00:25:24,560 --> 00:25:26,261
우수.

777
00:25:26,261 --> 00:25:27,760
지금, 나는 또 다른 패스를 만들려고 해요.

778
00:25:27,760 --> 00:25:28,590
던, 암갈색, 암갈색, 암갈색.

779
00:25:28,590 --> 00:25:31,465
나는 다섯 다음 작다 참조하십시오.

780
00:25:31,465 --> 00:25:32,840
지금, 나는 또 다른 패스를 받아 갈거야.

781
00:25:32,840 --> 00:25:33,631
던, 암갈색, 암갈색, 암갈색.

782
00:25:33,631 --> 00:25:34,880
식스 작다.

783
00:25:34,880 --> 00:25:35,520
좋다.

784
00:25:35,520 --> 00:25:36,585
세븐은 작은 것입니다.

785
00:25:36,585 --> 00:25:37,085
변경 없음.

786
00:25:37,085 --> 00:25:38,630
여덟 작은 것입니다.

787
00:25:38,630 --> 00:25:39,170
완료.

788
00:25:39,170 --> 00:25:43,900
>> 그래서 우리가 반복적으로 수행 한
이후 다른 하나의 요소를 선택

789
00:25:43,900 --> 00:25:47,230
우린 뭔가를 구현한다
선택의 일종으로 공식화 것.

790
00:25:47,230 --> 00:25:49,120
그것도 아마의
설명이 간단,

791
00:25:49,120 --> 00:25:51,310
말 그대로 모든 당신을한다는 점에서
다만 계속되고 싶지

792
00:25:51,310 --> 00:25:54,700
목록을 앞뒤로가는
선택한 다음 작은 소자

793
00:25:54,700 --> 00:25:55,720
당신이 완료 될 때까지.

794
00:25:55,720 --> 00:25:58,650
>> 그래서 아마도, 심지어 간단
직관적으로, 지난보다.

795
00:25:58,650 --> 00:26:00,020
이제 마지막 하나를 해보자.

796
00:26:00,020 --> 00:26:03,060
너희들은 스스로를 재설정 할 수 있다면
다음과 같은 위치에

797
00:26:03,060 --> 00:26:08,600
마지막 시간, 보자 경우 우리는 할 수 없습니다
지금 한 다른 접근 방식을 공식화.

798
00:26:08,600 --> 00:26:12,857
사실, 것 사람
거기에서 제안하고자

799
00:26:12,857 --> 00:26:14,440
우리는이 일에 대해 어떻게 다른 사람을 갈 수 있습니까?

800
00:26:14,440 --> 00:26:17,439
전문 용어 또는 정렬을 던지기없이
이미 알려진 답변,

801
00:26:17,439 --> 00:26:19,689
그냥 직관적으로, 우리는 무엇을 할 수 있습니까?

802
00:26:19,689 --> 00:26:21,635
>> 청중 : [들림].

803
00:26:21,635 --> 00:26:22,510
데이비드 J. 마란 : 그래.

804
00:26:22,510 --> 00:26:24,620
그래서 거기에 훌륭한 직관이있다.

805
00:26:24,620 --> 00:26:28,020
좋은 일들이 지금까지 일어날 것
우리가 분할 컴퓨터 과학

806
00:26:28,020 --> 00:26:30,832
및 분할의 문제를 극복
그 절반의 절반과 절반.

807
00:26:30,832 --> 00:26:32,540
그리고 참으로, 우리
그렇게 시작할 수 있습니다.

808
00:26:32,540 --> 00:26:35,754
그리고 사실, 즉,로 우리가합니다거야
아직, 우리의 최상의 솔루션 중 하나를 참조하십시오.

809
00:26:35,754 --> 00:26:37,420
그러나 이제 오래 전에 다시 그에게 올 수 있습니다.

810
00:26:37,420 --> 00:26:40,500
사실, 우리는 할거야
조금 이번 주 그.

811
00:26:40,500 --> 00:26:42,180
이 문제를 해결하기 위해 우리는 다른 무엇을 할 수 있는가?

812
00:26:42,180 --> 00:26:44,647
그래서 여기에 모두에
겉으로는 임의의 순서.

813
00:26:44,647 --> 00:26:45,230
당신은 무엇을 알아?

814
00:26:45,230 --> 00:26:48,320
오히려 앞뒤로 이동보다,
앞뒤로 앞뒤로

815
00:26:48,320 --> 00:26:50,624
때마다,이 같은 느낌
나는 산책을 많이하고 있어요.

816
00:26:50,624 --> 00:26:52,790
이유는 단지에서 시작되지 않습니다
리스트의 처음

817
00:26:52,790 --> 00:26:54,960
그냥 자신이 속한 네를 넣어?

818
00:26:54,960 --> 00:26:59,680
그래서 내가이 순간을 위해 가정하자 그
내 목록은이 첫 번째 요소입니다.

819
00:26:59,680 --> 00:27:04,937
네 시간이 순간에 정렬됩니다,
만약 내가 걱정 모두 다 여기에있다?

820
00:27:04,937 --> 00:27:06,520
이 종류의 사소 사실, 권리인가?

821
00:27:06,520 --> 00:27:10,000
하나의 숫자를 포함하는 목록과 마찬가지로
그 네 번째 분명 정렬됩니다.

822
00:27:10,000 --> 00:27:13,070
>> 그래서 내가 그냥 규정하자
것을이 목록 정렬됩니다.

823
00:27:13,070 --> 00:27:15,090
하지만 지금은이 목록의 나머지 부분을 가지고있다.

824
00:27:15,090 --> 00:27:17,240
그래서 지금, 나는 두 발생합니다.

825
00:27:17,240 --> 00:27:21,690
여기서 분명히 두 개의 작업을 수행
사에 대한 속해?

826
00:27:21,690 --> 00:27:22,580
네 전에.

827
00:27:22,580 --> 00:27:23,862
그래서 여기에 무엇을 할 수 있는가?

828
00:27:23,862 --> 00:27:24,820
이름이 뭐라고?

829
00:27:24,820 --> 00:27:25,090
>> 조셉 조셉.

830
00:27:25,090 --> 00:27:26,030
>> 데이비드 J. 마란 : 조셉,
당신은 한 걸음 뒤로 물러나 수 있다면

831
00:27:26,030 --> 00:27:27,790
전화 번호 그냥 잠시.

832
00:27:27,790 --> 00:27:31,130
그리고 스테판 여기 지금 무엇을해야합니까?

833
00:27:31,130 --> 00:27:33,720
의는 여기 스테판를 이동하자.

834
00:27:33,720 --> 00:27:35,520
그리고 지금, 요셉이 여기에 오게.

835
00:27:35,520 --> 00:27:39,660
그리고 지금, 내가 그 주장하자
여기에 모든 정렬됩니다.

836
00:27:39,660 --> 00:27:42,474
따라서, 유사한 결과이지만
근본적으로 다른 접근 방식.

837
00:27:42,474 --> 00:27:44,140
난 거기 무엇을보고하지 않았습니다.

838
00:27:44,140 --> 00:27:46,310
난 그냥 요소를 계속 복용
그들이 나에게 건네있는 한,

839
00:27:46,310 --> 00:27:47,240
그리고 그들과 거래.

840
00:27:47,240 --> 00:27:48,330
>> 그래서 지금, 나는 여섯 번째를 참조하십시오.

841
00:27:48,330 --> 00:27:51,110
어디 숫자 여섯 속해 있습니까?

842
00:27:51,110 --> 00:27:53,250
우리는 2, 4, 여섯 있습니다.

843
00:27:53,250 --> 00:27:54,800
정확히 그녀는 바로 지금입니다.

844
00:27:54,800 --> 00:27:57,750
그래서 지금의이 혼자 떠나게하고,
목록의이 부분 주장

845
00:27:57,750 --> 00:27:58,772
지금 정렬됩니다.

846
00:27:58,772 --> 00:28:01,230
그리고, 이것은 근본적으로 느낀다
그 다른 난 그냥 해요

847
00:28:01,230 --> 00:28:05,230
여기에 목록을 이동
선형, 나는 결코 다시 배로없는거야.

848
00:28:05,230 --> 00:28:05,730
네.

849
00:28:05,730 --> 00:28:06,230
괜찮아.

850
00:28:06,230 --> 00:28:08,190
그래서 여덟, 당신은 어디에 속하십니까?

851
00:28:08,190 --> 00:28:08,730
바로 여기에.

852
00:28:08,730 --> 00:28:09,310
완벽한.

853
00:28:09,310 --> 00:28:10,210
그래서 지금, 하나.

854
00:28:10,210 --> 00:28:10,900
어 오.

855
00:28:10,900 --> 00:28:13,010
이처럼이 느낌
비용이 될 것이다.

856
00:28:13,010 --> 00:28:15,690
이제 이전 알고리즘에서
난 그냥 사람들을 바 꾸었습니다.

857
00:28:15,690 --> 00:28:18,648
그래서 나는 그에게 모든 방법을 넣을 수 있습니다
시작은, 그러나 요셉을 움직였다.

858
00:28:18,648 --> 00:28:21,450
하지만 지금은, 요셉을 이동하는 경우
무엇을 잘못 될 것?

859
00:28:21,450 --> 00:28:24,250
>> 지금, 나는 일종의 내가했습니다 undone--했습니다
앞으로 다음 한 단계를 촬영

860
00:28:24,250 --> 00:28:26,300
한 단계 뒤로, 지금 때문에
요셉은 순서가 될 것이다.

861
00:28:26,300 --> 00:28:26,830
그래서이 작업을 수행 할 수 있습니다.

862
00:28:26,830 --> 00:28:29,150
당신은 번호 하나를 수행 할 수 있다면
단지 잠시 뒤로 물러나.

863
00:28:29,150 --> 00:28:30,490
우리는 어떻게 put-- 수있는
당신의 이름을 다시했다?

864
00:28:30,490 --> 00:28:31,130
>> 아난 : 아난.

865
00:28:31,130 --> 00:28:32,610
>> 데이비드 J. 마란 : 장소에서 아난?

866
00:28:32,610 --> 00:28:36,091
무엇과 관련하여 일어날 필요
2, 4, 여섯, 8에?

867
00:28:36,091 --> 00:28:37,570
그들은 모두 이동해야합니다.

868
00:28:37,570 --> 00:28:42,590
여덟 그래서 만약 것은 이동하고 싶습니다
먼저, 다음 여섯, 다음 네, 다음 두 가지.

869
00:28:42,590 --> 00:28:45,380
그리고 아난, 경우에 당신은 좋겠
좋은, 여기에 올 것을 좋아합니다.

870
00:28:45,380 --> 00:28:47,760
그러나 여기, 우리는 단지했습니다
종류의 가격을 지불

871
00:28:47,760 --> 00:28:49,510
알고리즘에서 다른 지점에서.

872
00:28:49,510 --> 00:28:52,550
선택과 마지막 반면
종류, 심지어 거품 정렬,

873
00:28:52,550 --> 00:28:54,700
내가 다시 걷고하고있어
앞으로, 뒤로,

874
00:28:54,700 --> 00:28:58,360
확실히 어떤을 추가하고있다
시간적, 문자 그대로 단계적.

875
00:28:58,360 --> 00:29:00,660
>> 삽입 정렬, 처음
이처럼 눈이 보인다

876
00:29:00,660 --> 00:29:05,150
슈퍼 스마트하고 있다는 점에서 그냥 해요
천천히, 점진적 진전,

877
00:29:05,150 --> 00:29:07,120
하지만 난 앞뒤로이 않을거야.

878
00:29:07,120 --> 00:29:09,410
그러나 누군가가 실제로있는 경우
순서 예고 중

879
00:29:09,410 --> 00:29:10,840
난 그냥해야했다 모든 작업.

880
00:29:10,840 --> 00:29:14,750
I는리스트의 절반을 이동했다
단지 숫자위한 공간을 마련합니다.

881
00:29:14,750 --> 00:29:16,790
그래서 동일한 양의
작업의 지금까지를

882
00:29:16,790 --> 00:29:18,690
작품의 단지 다른 종류의, 느낀다.

883
00:29:18,690 --> 00:29:19,370
>> 의 계속하자.

884
00:29:19,370 --> 00:29:22,657
그래서 지금 우리는 모든 것을 알고있다
(1 ~ 8) 사이에 분류되어 있습니다.

885
00:29:22,657 --> 00:29:23,740
자, 내가 3 번 있습니다.

886
00:29:23,740 --> 00:29:25,864
당신이 데리러 좋아하는 경우
3 번, 다시 한 단계.

887
00:29:25,864 --> 00:29:28,260
그리고 무엇 너희들은 어떻게해야합니까?

888
00:29:28,260 --> 00:29:28,760
네.

889
00:29:28,760 --> 00:29:33,070
그래서 다른 한 개, 두 개, 세 단계입니다.

890
00:29:33,070 --> 00:29:36,010
단지 비용을 시간의 세 가지 단위
나, 세 지금은 들어갈 수 있도록.

891
00:29:36,010 --> 00:29:37,460
마지막으로, 일곱.

892
00:29:37,460 --> 00:29:39,730
>> 이제 가서 보자
당신은 단계를 다시 가져 가라.

893
00:29:39,730 --> 00:29:42,780
이것은 단지 우리를 비용 것입니다
한 시간 단위,하지만 괜찮아요.

894
00:29:42,780 --> 00:29:44,170
그리고 지금, 다섯의 정보는 다음의 제품에가는
조금 더 비싼.

895
00:29:44,170 --> 00:29:45,340
당신은 다시 단계를 원하는 경우.

896
00:29:45,340 --> 00:29:48,380
우리는 팔을 이동해야
일곱, 여섯.

897
00:29:48,380 --> 00:29:50,749
그리고 모든 사람들이 지금 정렬됩니다.

898
00:29:50,749 --> 00:29:52,290
그래서 여기에 우리의 자원 봉사자에 큰 손.

899
00:29:52,290 --> 00:29:53,554
정말 고맙습니다.

900
00:29:53,554 --> 00:29:56,220
>> [박수]

901
00:29:56,220 --> 00:29:56,860
>> 여러분 모두 감사합니다.

902
00:29:56,860 --> 00:29:57,520
여러분 모두 감사합니다.

903
00:29:57,520 --> 00:30:02,940
그럼 지금 얼마나 보자
이 모든 비용이 많이 드는 것은이었다.

904
00:30:02,940 --> 00:30:06,210
의 아마 생각해 보자
이들의 간단한 거품 정렬.

905
00:30:06,210 --> 00:30:09,950
그리고, 단지 때문에 단순한 말
당신은 단지에 의해 탐욕을 해결할 수 있습니다

906
00:30:09,950 --> 00:30:11,660
여기 페어의 문제를 해결.

907
00:30:11,660 --> 00:30:13,720
페어의 문제를 해결
여기에, 또 다시

908
00:30:13,720 --> 00:30:17,680
다시, 많은 반복
당신이 배는 실제로 필요가있다.

909
00:30:17,680 --> 00:30:21,050
>> 그래서 밝혀
버블 정렬과, 음,

910
00:30:21,050 --> 00:30:25,820
얼마나 많은 단계를 내가 걸릴해야합니까
그 알고리즘의 첫 번째 패스?

911
00:30:25,820 --> 00:30:30,850
나는의 하나 see--하자 take-- 수 있습니다
둘, 셋, 넷, 다섯, 여섯, 일곱.

912
00:30:30,850 --> 00:30:32,190
그리고 여기에 여덟 요소가있다.

913
00:30:32,190 --> 00:30:35,280
그래서 n에 마이너스 1 단계처럼
목록의 시작 부분에서 얻을

914
00:30:35,280 --> 00:30:36,380
리스트의 마지막.

915
00:30:36,380 --> 00:30:41,350
>> 그러나 선택의 종류와, 난 리콜
또 다시 요소 선택

916
00:30:41,350 --> 00:30:44,590
다시 즉, 최소의
나는 장소에 걸었습니다

917
00:30:44,590 --> 00:30:46,616
하지만 난 아니에요
다시 내 뒤에 찾고.

918
00:30:46,616 --> 00:30:49,490
그래서 조금 더 명확 생각
다음 처음 그, 나는 수도

919
00:30:49,490 --> 00:30:52,680
모든 N 마이너스 1 단계를 수행해야
작은 요소를 찾을 수 있습니다.

920
00:30:52,680 --> 00:30:55,920
그럼 난 자리에 넣어, 그리고
이전에 여기에 있었던 누구든지 퇴거.

921
00:30:55,920 --> 00:30:57,500
>> 하지만 난 필요 없어
이 요소에서 계속 찾고,

922
00:30:57,500 --> 00:30:59,040
내가 알고 있기 때문에 그것은이다
이미 작은.

923
00:30:59,040 --> 00:31:01,581
그래서 지금, 난 그냥 7시에 볼 수있다
요소, 다음 여섯 요소,

924
00:31:01,581 --> 00:31:03,290
다음 다음 다섯 가지 요소, 네 가지 요소.

925
00:31:03,290 --> 00:31:06,900
그리고 수학적으로, N은이면
요소 나 숫자의 개수

926
00:31:06,900 --> 00:31:11,990
우리가 시작, 당신이 상상할 수있는
N이 마이너스 1과 동일 함,

927
00:31:11,990 --> 00:31:14,250
플러스 N 마이너스 2 단계,
플러스 N 마이너스 3 단계,

928
00:31:14,250 --> 00:31:16,780
플러스 N 마이너스 4 단계, 모든
길 아래로 한 단계.

929
00:31:16,780 --> 00:31:18,160
그리고 내 마지막 사람에있어.

930
00:31:18,160 --> 00:31:20,650
>> 그리고 당신은 많은 것을 기억하는 경우
의 책이나 수학 책을 통계

931
00:31:20,650 --> 00:31:24,730
에 그 공식을 가지고
다시 하드 커버 또는 그들 앞에서,

932
00:31:24,730 --> 00:31:27,690
그것은이 시리즈 밝혀
더 간단하게 표현 될 수있다

933
00:31:27,690 --> 00:31:28,857
n 배 n은 마이너스 2 이상 1.

934
00:31:28,857 --> 00:31:31,273
그게 아니라면 그리고 그것은 괜찮아요
당신의 마음의 최전선에.

935
00:31:31,273 --> 00:31:32,420
그러나 이것은 참으로 사실이다.

936
00:31:32,420 --> 00:31:34,449
즉, 쓰기의 단지 간단한 방법입니다.

937
00:31:34,449 --> 00:31:36,240
그리고 당신이 생각하는 경우
다시 초등학교에,

938
00:31:36,240 --> 00:31:38,698
당신은 단지 곱 시작할 때
일 밖으로 물론이,

939
00:31:38,698 --> 00:31:41,820
단지 N 제곱 마이너스 N 2로 나누어 져 있습니다.

940
00:31:41,820 --> 00:31:44,772
내가했던 모든 확장이다
이 표현.

941
00:31:44,772 --> 00:31:46,730
그리고이 해 다시 보자
약간 다르게.

942
00:31:46,730 --> 00:31:49,780
즉 마이너스 N 2 N / 2의 제곱으로 나눈 것.

943
00:31:49,780 --> 00:31:53,270
>> 그래서 다시, 난 그냥 가지 적용 해요
일부 연산이 규칙.

944
00:31:53,270 --> 00:31:57,140
하지만 지금은 알이 큰 용어
이런 식으로, 말하자면

945
00:31:57,140 --> 00:31:58,540
n은 제곱이다.

946
00:31:58,540 --> 00:32:02,910
그래서 그래, 그것은 N 제곱의
2, 마이너스 N / 2로 나눈 값.

947
00:32:02,910 --> 00:32:05,080
>> 그러나 일반적으로, n은,이면
큰 값이 될 것,

948
00:32:05,080 --> 00:32:08,740
나는 그 N 제곱 항에 갈거야
지배적 인 요소가 될 것입니다.

949
00:32:08,740 --> 00:32:10,490
그냥 될 것
더 큰 기여

950
00:32:10,490 --> 00:32:12,877
N / 2보다 단계의 수.

951
00:32:12,877 --> 00:32:13,960
그래서 나는이 무엇을 의미합니까?

952
00:32:13,960 --> 00:32:16,795
심지어, 간단한 예제를 해보자
수학은 조금 큰를 얻을 수 있지만.

953
00:32:16,795 --> 00:32:20,210
>> 그래서 우리는 백만명 있다고 가정
단, 또는 100 만 가지에

954
00:32:20,210 --> 00:32:21,320
우리는 정렬 할 것이다.

955
00:32:21,320 --> 00:32:23,730
의 백만을 연결하자
정확히 식으로

956
00:32:23,730 --> 00:32:27,230
이 총 소요 얼마나 많은 단계를 확인합니다
말 사용 만 요소를 정렬하려면,

957
00:32:27,230 --> 00:32:28,560
선택 정렬.

958
00:32:28,560 --> 00:32:30,760
>> 그래서 우리는 이전과 동일한 공식이있을 것이다.

959
00:32:30,760 --> 00:32:34,120
내가 얻을 수 있도록 나는 백만 플러그 것
백만, 2로 나눈 제곱

960
00:32:34,120 --> 00:32:35,990
마이너스 만 2로 나눈.

961
00:32:35,990 --> 00:32:40,180
나는 사전에 그 수학을하는 경우
여기에, 우리는 5000 억이

962
00:32:40,180 --> 00:32:47,460
마이너스 50 만, 어떤
, 499,999,500,000 우리에게 제공

963
00:32:47,460 --> 00:32:49,270
이는 무척 큽니다.

964
00:32:49,270 --> 00:32:54,370
>> 사실, 당신은 지금 비교하는 경우
499000000000, 999000000,

965
00:32:54,370 --> 00:33:01,210
우리의 원래 값에 대한 50 만,
5000 억, 그것은 그렇게 망할 가까이.

966
00:33:01,210 --> 00:33:06,850
권리? N 2가 제공 나눈 제곱
us-- 또는 오히려, n은 2로 나눈 제곱

967
00:33:06,850 --> 00:33:08,370
우리에게 5000 억을 주었다.

968
00:33:08,370 --> 00:33:13,510
즉 무척는 가까이
499999500000로,

969
00:33:13,510 --> 00:33:17,970
오프 50 만 뺀 말을하다,
또는보다 일반적으로, 오프 감산

970
00:33:17,970 --> 00:33:20,010
N은 정말 큰 거래를 제곱.

971
00:33:20,010 --> 00:33:22,490
이러한하게 N은 제곱
숫자는 정말 빨리 성장한다.

972
00:33:22,490 --> 00:33:25,790
>> 이제, 이것은 단지 중요한 것이면
우리와 같은, 컴퓨터 과학자로서,

973
00:33:25,790 --> 00:33:29,350
일반적으로 너무 많은 걱정하지 않을 수 있습니다
이러한 식의 뉘앙스에 대한

974
00:33:29,350 --> 00:33:31,400
정확히 무엇을
정확한 답변입니다.

975
00:33:31,400 --> 00:33:33,390
우리는 그, 그거 알아 케어?

976
00:33:33,390 --> 00:33:37,810
하루의 끝에서,이 수식
제곱 N 정도이다.

977
00:33:37,810 --> 00:33:39,350
>> 예, 우리는 거기에 2로 나눈 것입니다.

978
00:33:39,350 --> 00:33:41,360
예, 우리는 오프 N 마이너스 2를 뺀 것입니다.

979
00:33:41,360 --> 00:33:46,860
그러나 결국, 용어
정말 우리를 상처 우리를 비용

980
00:33:46,860 --> 00:33:48,995
많은 단계는 정사각형 용어이다.

981
00:33:48,995 --> 00:33:51,370
그래서 어떤 컴퓨터 과학자
일반적으로 할 것입니다

982
00:33:51,370 --> 00:33:54,160
그 모두를 무시한다
작은 순서 조건,

983
00:33:54,160 --> 00:33:56,900
단지 하나를 보면 그
비용에 가장 기여한다.

984
00:33:56,900 --> 00:34:00,530
>> 그리고 이는 우리가 할 수있는, 좋은
지금 훨씬 더 일반성에 이야기

985
00:34:00,530 --> 00:34:02,470
알고리즘에 대해, 그리고 그것들을 비교할 수있다.

986
00:34:02,470 --> 00:34:04,550
난 그것과 사실
이 O를 사용하여 의도적이다.

987
00:34:04,550 --> 00:34:06,680
나는 순서에 말할 때
의, 내가 특별히 해요

988
00:34:06,680 --> 00:34:09,560
뭔가를 참조
큰 O. 큰 O라는

989
00:34:09,560 --> 00:34:14,090
표기하는 컴퓨터
과학자는 설명하기 위해 사용

990
00:34:14,090 --> 00:34:16,710
이 상단 뭔가에 바인딩됩니다.

991
00:34:16,710 --> 00:34:21,150
>> 당신이 알고리즘이 있다고한다면
n은 제곱의 큰 O에,

992
00:34:21,150 --> 00:34:23,380
내가 제안으로 단지
순간 전, 그 수단

993
00:34:23,380 --> 00:34:27,710
자사의 실행의 관점에서
시간이나 효율성,

994
00:34:27,710 --> 00:34:30,090
그것은 순서 취
n 개의 단계를 제곱.

995
00:34:30,090 --> 00:34:31,420
어쩌면 이하, 어쩌면 더.

996
00:34:31,420 --> 00:34:33,435
그러나 N의 제곱에 순서이다.

997
00:34:33,435 --> 00:34:34,560
그리고 그 상한을합니다.

998
00:34:34,560 --> 00:34:36,530
그것은 수 없을거야
보다 더 고통스러운.

999
00:34:36,530 --> 00:34:40,800
그것은 N 제곱이 될 것, 또는 2 아니에요
N, 또는 훨씬 더 큰 뭔가.

1000
00:34:40,800 --> 00:34:43,800
이것은 바운드 위입니다
무엇에 그 비용이다.

1001
00:34:43,800 --> 00:34:46,150
그래서,하자 주어진
몇 가지 예를 고려해보십시오.

1002
00:34:46,150 --> 00:34:49,820
그리고 이것은 단지 유한 한 목록입니다
매우 일반적인 실행 시간

1003
00:34:49,820 --> 00:34:52,870
될 운명이야 알고리즘
우리가했습니다 몇 가지의 예시

1004
00:34:52,870 --> 00:34:53,600
이미 본.

1005
00:34:53,600 --> 00:34:58,060
>> 예를 들어, 케이스에 따라서
선택 정렬, 나는 여기에 무엇을 주장하고있어

1006
00:34:58,060 --> 00:35:02,250
그 선택 정렬의 실행이다
시간 N의 제곱에 순서이다.

1007
00:35:02,250 --> 00:35:06,260
최악의 경우, 내가 가진거야
여기에 임의의 숫자의 전체 무리.

1008
00:35:06,260 --> 00:35:08,600
그리고 우리는 수학적으로 본 것과 같이,
나는 계속 걸어 경우

1009
00:35:08,600 --> 00:35:11,310
목록을 통해
목록, 작은 다음을 선택

1010
00:35:11,310 --> 00:35:14,410
또 다시 요소, 나는 경우
실제로 모든 단계를 적어

1011
00:35:14,410 --> 00:35:18,750
나는 공식을 통해 (formulaically) 제안으로 내가 데려 갈거야
전에 제곱 N의 순서에있어

1012
00:35:18,750 --> 00:35:20,370
내가 데려 갈거야 단계.

1013
00:35:20,370 --> 00:35:24,520
>> 그리고 그 거품을 밝혀
정렬과 삽입 정렬

1014
00:35:24,520 --> 00:35:27,370
최악의 경우만큼 느리다.

1015
00:35:27,370 --> 00:35:32,040
예를 들어, 고려, 삽입 정렬,
우리가 처리 맨 마지막 알고리즘,

1016
00:35:32,040 --> 00:35:35,500
이는, 우리가 요소를 보면했다
자신이 속한 곳 다음 삽입합니다.

1017
00:35:35,500 --> 00:35:38,720
그리고 우리는 다음 요소로 보았다,
그것이 속하는 곳을 삽입하고.

1018
00:35:38,720 --> 00:35:40,990
>> 그래서 최상의 시나리오를 고려하십시오.

1019
00:35:40,990 --> 00:35:45,590
내 자원 봉사자들이 줄을했다 가정
말 그대로이 같은 여덟 통해 하나,

1020
00:35:45,590 --> 00:35:47,440
이미 정렬.

1021
00:35:47,440 --> 00:35:51,300
삽입 정렬은 얼마나 많은 단계입니다
팔명를 정렬하는 걸릴 것,

1022
00:35:51,300 --> 00:35:55,640
그들은 무대에 도착하는 경우
이처럼 보이는?

1023
00:35:55,640 --> 00:35:57,410
>> 8 명이이 이미 정렬.

1024
00:35:57,410 --> 00:35:58,760
그리고 삽입 정렬을 사용합니다.

1025
00:35:58,760 --> 00:36:02,180
알고리즘의 마지막.

1026
00:36:02,180 --> 00:36:03,640
음, 정말 빨리를 재현 할 수 있습니다.

1027
00:36:03,640 --> 00:36:05,504
여기 시작 그래서 만약, 내가 하나를 참조하십시오.

1028
00:36:05,504 --> 00:36:06,420
어디 하나에 속해 있습니까?

1029
00:36:06,420 --> 00:36:07,730
그것은 바로 여기에 속한다.

1030
00:36:07,730 --> 00:36:08,330
나는 두 가지를 참조하십시오.

1031
00:36:08,330 --> 00:36:09,660
어디 두 속해 있습니까?

1032
00:36:09,660 --> 00:36:10,260
바로 여기에.

1033
00:36:10,260 --> 00:36:10,900
나는 3을 참조하십시오.

1034
00:36:10,900 --> 00:36:11,920
어디 세 속해 있습니까?

1035
00:36:11,920 --> 00:36:12,480
바로 여기에.

1036
00:36:12,480 --> 00:36:13,100
>> 나는 네를 참조하십시오.

1037
00:36:13,100 --> 00:36:13,600
바로 여기에.

1038
00:36:13,600 --> 00:36:15,660
다섯, 여섯, 일곱, 여덟.

1039
00:36:15,660 --> 00:36:17,320
자신을 반복 할 이유가 없습니다.

1040
00:36:17,320 --> 00:36:21,260
그리고, 얼마나 많은 단계
즉, N의 관점에서 무엇입니까?

1041
00:36:21,260 --> 00:36:23,870
또한 N의 순서에있어
단계, 오른쪽? N 마이너스 1.

1042
00:36:23,870 --> 00:36:27,567
하지만 선형 수를했다
단계로, 지금은 끝났어요.

1043
00:36:27,567 --> 00:36:28,900
그래서하지만, 최상의 경우이다.

1044
00:36:28,900 --> 00:36:29,983
어떤 최악의 경우는 어떻습니까?

1045
00:36:29,983 --> 00:36:32,730
무엇 여덟, 저기 있었다
일곱은이 아래로했다

1046
00:36:32,730 --> 00:36:35,840
그리고 하나, 둘, 그래서, 여기에 있었다
목록은 정말 반전 있다고?

1047
00:36:35,840 --> 00:36:38,300
>> 글쎄, 무슨 일이 실제로 발생
이 번호는 경우?

1048
00:36:38,300 --> 00:36:41,300
그리고 우리는 예 단지 몇을 다하겠습니다.

1049
00:36:41,300 --> 00:36:49,300
어떤 숫자 8 참으로, 경우
여기에, 그리고 number-- 으악.

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
그래서 만약에, 참으로, 수
여덟, 여기에 모든 방법입니다

1052
00:36:56,430 --> 00:36:57,790
나는 삽입 정렬을 사용하고 있습니다?

1053
00:36:57,790 --> 00:36:58,290
>> 그래.

1054
00:36:58,290 --> 00:37:00,280
나는 그것이 장소에서의 순간에 주장한다.

1055
00:37:00,280 --> 00:37:03,152
하지만 지금은, seven-- 곳 일곱 갈입니까?

1056
00:37:03,152 --> 00:37:04,360
물론, 여기 간다.

1057
00:37:04,360 --> 00:37:06,760
그래서 한 곳 이상 팔을 이동해야합니다.

1058
00:37:06,760 --> 00:37:08,554
지금 여섯, 어디로 가야합니까?

1059
00:37:08,554 --> 00:37:09,220
음, 좋아.

1060
00:37:09,220 --> 00:37:13,150
지금, 나는 이상 팔을 이동해야
장소와 장소를 통해 일곱,

1061
00:37:13,150 --> 00:37:14,440
그리고, 나는 여섯 아래로 풍덩.

1062
00:37:14,440 --> 00:37:16,870
>> 그래서 처음, 그것은 선정
일을 해결하기 위해 나를 한 단계,

1063
00:37:16,870 --> 00:37:18,570
다음은 일을 해결하기 위해 나에게 두 단계를 요했다.

1064
00:37:18,570 --> 00:37:20,370
얼마나 많은 단계입니다
해결하기 위해 걸릴 것

1065
00:37:20,370 --> 00:37:22,720
바로 이곳에 오 넣어 것?

1066
00:37:22,720 --> 00:37:23,340
세 가지.

1067
00:37:23,340 --> 00:37:29,520
지금은해야하기 때문에
하나 둘, 셋을 이동합니다.

1068
00:37:29,520 --> 00:37:32,430
얼마나 많은 단계를이 걸릴 것입니다
바로 이곳에서 네를 넣어?

1069
00:37:32,430 --> 00:37:36,040
4 플러스 5 플러스 6 플러스 7.

1070
00:37:36,040 --> 00:37:40,260
>> 그리고 그것은 수학적으로 동일한이다
우리는 선택의 종류에 대한 설명 무엇.

1071
00:37:40,260 --> 00:37:42,130
우리는이 시리즈가
그것은 단지 증가합니다.

1072
00:37:42,130 --> 00:37:45,650
1 플러스 2 플러스 3 플러스 4,
또는 반대로, 7 플러스 (6)

1073
00:37:45,650 --> 00:37:52,610
플러스 5 플러스 4 오늘의를 위해 추가
N의 순서에에 목적 제곱.

1074
00:37:52,610 --> 00:37:57,640
>> 그래서 나도 그 규정하자
버블 정렬은 n이 제곱에 있습니다.

1075
00:37:57,640 --> 00:38:01,340
때문에 거품 정렬, 각각
시간 나는 목록을 이동

1076
00:38:01,340 --> 00:38:03,100
나는 대략 얼마나 많은 단계를 데려 갈거야?

1077
00:38:03,100 --> 00:38:06,260
때마다 나는 그대로
거기에서 거기까지 걸어?

1078
00:38:06,260 --> 00:38:07,960
대략 N 단계.

1079
00:38:07,960 --> 00:38:12,650
그러나 얼마나 많은 시간 나는 수도
목록을 갈 필요가?

1080
00:38:12,650 --> 00:38:13,920
>> 음, 대략 N 시간.

1081
00:38:13,920 --> 00:38:15,680
아마 N 마이너스 1 만 약 n 배.

1082
00:38:15,680 --> 00:38:16,430
글쎄, 그건 왜?

1083
00:38:16,430 --> 00:38:19,560
음, 거품 정렬과, 경우
우리는 거품 정렬 시작

1084
00:38:19,560 --> 00:38:23,570
최악의 목록
다시 완전히 상황,

1085
00:38:23,570 --> 00:38:25,550
거꾸로, 어떤 일이 일어날?

1086
00:38:25,550 --> 00:38:28,830
나는 목록을 이동 한 수
하나는 거기에 모든 방법을 속한다.

1087
00:38:28,830 --> 00:38:33,280
>> 그러나 버블 정렬로, 얼마나 멀리 하나를 수행합니다
목록을 내 첫 번째 패스를 이동?

1088
00:38:33,280 --> 00:38:36,620
얼마나 많은 명소 것은 그가 나올까요
올바른 위치에 가까운?

1089
00:38:36,620 --> 00:38:37,240
딱 하나만.

1090
00:38:37,240 --> 00:38:40,281
그래서이 과정의 경우 가지 이유
이 알고리즘을 통해마다

1091
00:38:40,281 --> 00:38:41,880
다윗의 복용 약 N 단계.

1092
00:38:41,880 --> 00:38:44,940
그러나 얼마나 많은 패스
리스트를 통한 인

1093
00:38:44,940 --> 00:38:49,060
거품에 하나 걸릴 것
자신이 속한 왼쪽으로?

1094
00:38:49,060 --> 00:38:51,840
>> 그는, 같은 이동있어
n 개의 공간이 방법.

1095
00:38:51,840 --> 00:38:57,960
그러니 그냥 목록의 정렬을 수행하기 위해,
나는 앞뒤로 N 시간을 걸어야한다.

1096
00:38:57,960 --> 00:39:01,540
그리고 때마다, 나는 해요
N 요소를 찾고 있습니다.

1097
00:39:01,540 --> 00:39:05,410
그래서에 n 개의 물건 n 번을
N의 순서가 제곱.

1098
00:39:05,410 --> 00:39:07,220
>> 이제, 우리는 일부에서 볼 수 있습니다
반바지의

1099
00:39:07,220 --> 00:39:10,440
CS50의 다음 문제에 포함 된
다음에, 또 다른 접근 방법을 설정,

1100
00:39:10,440 --> 00:39:13,490
하지만 지금은, 그냥 생각 해보자
다른 실행 시간,

1101
00:39:13,490 --> 00:39:16,840
특히 정렬 사람이 취할 경우
약간의 시간이에서 침몰합니다.

1102
00:39:16,840 --> 00:39:21,790
어떻게 우리가 이미 본 적이 알고리즘의
즉, N 단계의 순서를 취한다?

1103
00:39:21,790 --> 00:39:27,560
>> 선형 수를 취해야
의는 우리가 지금까지 본 적이 있다고 단계?

1104
00:39:27,560 --> 00:39:29,350
그게 뭔데?

1105
00:39:29,350 --> 00:39:30,480
전화 번호부 검색.

1106
00:39:30,480 --> 00:39:31,390
첫 번째 알고리즘.

1107
00:39:31,390 --> 00:39:31,560
권리?

1108
00:39:31,560 --> 00:39:33,650
우리는 선형있어 어디
마이크 스미스을 검색 하시나요?

1109
00:39:33,650 --> 00:39:34,150
사실.

1110
00:39:34,150 --> 00:39:37,180
주 제로에서, 나는 시작했을 때
한 번에 한 페이지를 선회,

1111
00:39:37,180 --> 00:39:40,095
나는 심지어 종류라고 말했다
선형 느낌 알고리즘,

1112
00:39:40,095 --> 00:39:42,720
우리는에 그 사진을 가지고 있었다
직선 레드 라인 보드

1113
00:39:42,720 --> 00:39:44,678
과 직선 노란색
라인, 그 참이었다

1114
00:39:44,678 --> 00:39:46,810
N의 큰 O에있는 알고리즘.

1115
00:39:46,810 --> 00:39:50,680
>> 휴대폰에 마이크 스미스를 찾을 수 있기 때문에
최악의 경우에 해당 페이지의 책,

1116
00:39:50,680 --> 00:39:52,422
나 N 조치를 취할 수 있습니다.

1117
00:39:52,422 --> 00:39:53,630
출석을 복용에 대해 무엇?

1118
00:39:53,630 --> 00:39:55,790
일이 삼 사 오 육.

1119
00:39:55,790 --> 00:39:59,420
이것의 실행 시간에 무엇입니까
출석을 촬영 알고리즘?

1120
00:39:59,420 --> 00:40:03,070
때문에 이론적으로 N의 빅 오, 나는
방에있는 모든 사람을 가리 키도록해야합니다.

1121
00:40:03,070 --> 00:40:05,861
>> 이제 옆으로, 일에 대해
주 제로에서 다른 최적화?

1122
00:40:05,861 --> 00:40:08,117
둘, 넷, 여섯, 여덟, 열, 12.

1123
00:40:08,117 --> 00:40:10,200
컴퓨터 과학자 것
실현 잠깐,

1124
00:40:10,200 --> 00:40:12,320
그 순서에의
n은 두 단계로 나눈.

1125
00:40:12,320 --> 00:40:12,820
권리?

1126
00:40:12,820 --> 00:40:14,444
내가 한 번에 두 사람이하고 있어요 때문입니다.

1127
00:40:14,444 --> 00:40:17,015
그러나 우리는 무시하는거야
그 낮은 순서의 조건,

1128
00:40:17,015 --> 00:40:19,140
그리고 우리는 단지에가는거야
(2)에 의해 분할을 버리고,

1129
00:40:19,140 --> 00:40:21,830
그냥 말 N의 큰 O
뿐만 아니라 그 알고리즘.

1130
00:40:21,830 --> 00:40:22,760
>> 이건 어때?

1131
00:40:22,760 --> 00:40:26,170
우리는이 중 일부를 건너,하지만 거 야
N의 로그했다 알고리즘을했다?

1132
00:40:26,170 --> 00:40:29,900
즉 대략 N 단계를 기록 걸렸다?

1133
00:40:29,900 --> 00:40:30,870
분할 및 정복.

1134
00:40:30,870 --> 00:40:31,369
정확히.

1135
00:40:31,369 --> 00:40:33,900
전화 번호부 예 에서처럼
주 제로 오늘 아침,

1136
00:40:33,900 --> 00:40:36,191
여기서 우리는 문제를 분할
다시 다시 다시.

1137
00:40:36,191 --> 00:40:39,070
우리는 주에 칠판에 그린
곡선 녹색 선 제로,

1138
00:40:39,070 --> 00:40:41,460
우리는 그 날했다
로그 알고리즘.

1139
00:40:41,460 --> 00:40:44,970
>> 그리고 실제로, 수는 단계를
분할을 수행하고 정복하는 데 걸리는,

1140
00:40:44,970 --> 00:40:48,610
또는 이진 검색으로에게 우리는 시작합니다
전화 번호부에서와 같이, 그것을 호출

1141
00:40:48,610 --> 00:40:50,680
로그 및 단계의 순서이다.

1142
00:40:50,680 --> 00:40:52,470
그리고 이것은 이상한 하나의 비트입니다.

1143
00:40:52,470 --> 00:40:54,910
>> 한 단계 무엇이,
상세하게

1144
00:40:54,910 --> 00:40:56,240
단계의 상수?

1145
00:40:56,240 --> 00:40:58,865
어쩌면 그것은 어쩌면 세 가지이다, 2의,
그러나 컴퓨터 과학자 단지

1146
00:40:58,865 --> 00:41:01,423
1 큰 O로 단순화
일부 단계 상수.

1147
00:41:01,423 --> 00:41:04,256
당신이 그렇게 할 수있는 일이 무엇입니까
단계의 일정한 수를한다?

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> 박수의 실행 시간은 무엇입니까?

1150
00:41:10,930 --> 00:41:11,920
일정 시간.

1151
00:41:11,920 --> 00:41:12,420
권리?

1152
00:41:12,420 --> 00:41:15,490
마찬가지로,의 실행 시간 무엇을
한 소요 아무것도

1153
00:41:15,490 --> 00:41:18,570
동작, 같은 F 안녕하세요 세계를 인쇄 할 수 있습니다.

1154
00:41:18,570 --> 00:41:24,110
즉, 일정 시간이라고 할 수도
인쇄 F 덜 코너의 경우를 제외하고,

1155
00:41:24,110 --> 00:41:28,260
어떤 실행 시간을 수도
인쇄의 F 실제로 수?

1156
00:41:28,260 --> 00:41:28,790
그리고 왜?

1157
00:41:28,790 --> 00:41:30,550
이 경우에 N 측정은 무엇인가?

1158
00:41:30,550 --> 00:41:32,251
>> 청중 : [들림].

1159
00:41:32,251 --> 00:41:33,250
데이비드 J. 마란 : 맞아요.

1160
00:41:33,250 --> 00:41:34,900
문자의 수
우리는 인쇄 할.

1161
00:41:34,900 --> 00:41:36,191
그래서 매우 상황에 맞는이다.

1162
00:41:36,191 --> 00:41:39,910
오늘, 우리는에 많은 초점을 맞추고있어
문자와 여기 보드에 숫자.

1163
00:41:39,910 --> 00:41:43,540
그러나 그것은 또한 수 있습니다
실제 문자열의 문자.

1164
00:41:43,540 --> 00:41:46,420
다른 거기 밖으로 그래서집니다
대한 배려가 시작됩니다 측정,

1165
00:41:46,420 --> 00:41:48,530
그 반대의
빅 오의, 말하자면.

1166
00:41:48,530 --> 00:41:50,120
>> 즉, 오메가 표기법입니다.

1167
00:41:50,120 --> 00:41:53,380
큰 O는 무엇을 의미하는 반면
상단 당신의 실행 시간에 바인딩?

1168
00:41:53,380 --> 00:41:55,580
최대로, 얼마나 많은 시간을
일이 걸릴 수 있습니다?

1169
00:41:55,580 --> 00:41:59,250
Omega-- 죄송이오고 계속
up--은 그 반대입니다,

1170
00:41:59,250 --> 00:42:02,960
그것은 하한 켜져있다
시간 뭔가의 양이 걸릴 수 있습니다.

1171
00:42:02,960 --> 00:42:10,480
>> 겠어요 - 예를 들어, 어떤 일이 알고리즘이다
즉, 항상 N 제곱 단계를 수행?

1172
00:42:10,480 --> 00:42:15,600
음, 알고리즘 중 하나는 우리가 본 것
오늘은, 사실, 그뿐만 아니라이 될 수 있습니다.

1173
00:42:15,600 --> 00:42:16,720
선택 정렬.

1174
00:42:16,720 --> 00:42:18,270
선택 정렬 꽤 바보.

1175
00:42:18,270 --> 00:42:21,760
심지어 심지어 algorithm-- 죄송 경우
배열이 이미 정렬되어있는 경우,

1176
00:42:21,760 --> 00:42:24,150
선택의 종류에 가고
목록을 계속 걸어

1177
00:42:24,150 --> 00:42:28,907
이 작은이 있는지 확인합니다
요소 다시하고 다시하고 다시.

1178
00:42:28,907 --> 00:42:31,740
그리고 당신은에 인간하더라도
관객은 잠깐 것을 알고,

1179
00:42:31,740 --> 00:42:33,948
당신은 이미 통과
작은 요소, 컴퓨터

1180
00:42:33,948 --> 00:42:37,300
보이는 때까지 몰라
목록을 모든 방법.

1181
00:42:37,300 --> 00:42:40,240
마찬가지로,이 낮은 것을 바인딩
또한 고려 될 수도

1182
00:42:40,240 --> 00:42:42,000
선형 시간이 될 수 있습니다.

1183
00:42:42,000 --> 00:42:48,260
>> 그것은에 얼마나 많은 시간을 차지하나요
최적의 정렬 n 개의 요소

1184
00:42:48,260 --> 00:42:52,420
버블 정렬과 같은 것을 사용하는 경우?

1185
00:42:52,420 --> 00:42:54,280
목록이 이미 정렬됩니다 가정하자.

1186
00:42:54,280 --> 00:42:56,696
우리는 거품 정렬가 필요했다
N의 순서는 단계 제곱.

1187
00:42:56,696 --> 00:42:59,640
그러나 이미 무엇을 분류 거라면?

1188
00:42:59,640 --> 00:43:02,310
당신이 후 실현 경우
배열을 하나의 통과

1189
00:43:02,310 --> 00:43:03,540
것을 당신은 스왑을하지거야?

1190
00:43:03,540 --> 00:43:05,970
당신은 패스 더 만들고 유지해야합니까?

1191
00:43:05,970 --> 00:43:06,470
>> 아니.

1192
00:43:06,470 --> 00:43:10,340
그래서 낮은 버블 정렬에 바인딩
선형라고 할 수 있습니다.

1193
00:43:10,340 --> 00:43:11,830
N의 오메가.

1194
00:43:11,830 --> 00:43:14,450
그리고 우리는 볼 수 있습니다
뿐만 아니라 이들의 다른 사람.

1195
00:43:14,450 --> 00:43:17,990
그럼 잠깐 살펴 보자
여기에 단지 시각화에서

1196
00:43:17,990 --> 00:43:20,790
이러한 자신을 구별하는 방법을 볼 수 있습니다.

1197
00:43:20,790 --> 00:43:24,592
나는이에 여기 아래로 갈거야
C50의 웹 사이트에서 확인할 수의 페이지,

1198
00:43:24,592 --> 00:43:27,550
하지만 작업을 얻을 수있는 고통이 될 것입니다,
그것은라는 기술을 이용하기 때문에

1199
00:43:27,550 --> 00:43:30,560
를 자바 애플릿,
요즘 대부분 지원되지 않는,

1200
00:43:30,560 --> 00:43:32,730
적어도 크롬과 어떤 다른 사람에 의해.

1201
00:43:32,730 --> 00:43:37,070
>> 그리고 내가 가서이 속도를하자
위로 무슨 일이 일어나고 있는지에 대해 설명합니다.

1202
00:43:37,070 --> 00:43:40,840
이 거품의 데모입니다
종류, 첫 번째 알고리즘은 우리가 바라 보았다.

1203
00:43:40,840 --> 00:43:43,950
그리고 그것은 그에서 시각화 각의
이 바의 수를 나타냅니다.

1204
00:43:43,950 --> 00:43:45,710
큰 바,
수 더 큰.

1205
00:43:45,710 --> 00:43:47,520
작은 바,
수치가 작을.

1206
00:43:47,520 --> 00:43:50,353
그리고 당신도, 시각적으로 볼 수있는
이 있지만, 슈퍼 빠른 것입니다

1207
00:43:50,353 --> 00:43:53,699
, 빨간색 막대 나 같은 점이다
뒤로 걷는 등의 문제를 해결.

1208
00:43:53,699 --> 00:43:56,740
당신은 더 큰 요소를 볼 수 있습니다
실제로 오른쪽까지 버블 링되어,

1209
00:43:56,740 --> 00:43:59,650
그리고 작은 요소
왼쪽까지 버블 링됩니다.

1210
00:43:59,650 --> 00:44:01,870
그리고 여기 아래, 우리의 경우
실제로 더 자세히 보면,

1211
00:44:01,870 --> 00:44:04,330
우리는 사실을 믿을 수
비교와 스왑의 수

1212
00:44:04,330 --> 00:44:05,350
즉 만들어지고 있었다.

1213
00:44:05,350 --> 00:44:07,360
>> 하지만 그 대신, 이제 살펴 보자
두 번째 알고리즘에

1214
00:44:07,360 --> 00:44:11,240
우리는 함께 이전 보았다 우리
자원 봉사자, 선택 정렬.

1215
00:44:11,240 --> 00:44:13,500
시각, 그것은이
매우 다른 효과.

1216
00:44:13,500 --> 00:44:16,820
그러나에, 다시, 매우 직관적
우리는 작은 다음을 선택 유지하는 것이

1217
00:44:16,820 --> 00:44:18,660
요소, 우리는 약간의 행운이있어.

1218
00:44:18,660 --> 00:44:20,110
즉, 근본적으로 빠르게 느꼈다.

1219
00:44:20,110 --> 00:44:22,840
그러나 우리는 또 다시이를 실행 한 경우
다시 입력이 많은,

1220
00:44:22,840 --> 00:44:26,680
우리는 그것이 실제로 있다고 볼 것이다
아직 N의 큰 O에 제곱.

1221
00:44:26,680 --> 00:44:29,920
>> 이제 마지막 하나를하자
여기에, 삽입 정렬,

1222
00:44:29,920 --> 00:44:33,180
이는 세 번째 알고리즘이었다
우리는 리콜 보았다

1223
00:44:33,180 --> 00:44:36,700
이 사람은 다루고 있음
요소가 그들을 발견으로,

1224
00:44:36,700 --> 00:44:39,290
그러나 그것은 어쩌면 이동
가지 이상 공간을 확보하기 위해

1225
00:44:39,290 --> 00:44:41,660
자신이 속한 요소를 삽입.

1226
00:44:41,660 --> 00:44:45,330
>> 그리고이 너무을주는 끝
최종 결과. 이제 그 모든 세

1227
00:44:45,330 --> 00:44:46,490
꽤 빨리 느꼈다.

1228
00:44:46,490 --> 00:44:48,740
그리고 사실, 나는 그들을 실행
꽤 좋은 클립에서.

1229
00:44:48,740 --> 00:44:52,510
그러나 근본적으로, 그들은 모든 것
꽤 무서운, 솔직히 말해서.

1230
00:44:52,510 --> 00:44:56,960
이러한 알고리즘은 모두 지금까지
N의 큰 O에서 실행되는 제곱

1231
00:44:56,960 --> 00:44:59,270
꽤 걸릴
시간은 결국 실행합니다.

1232
00:44:59,270 --> 00:45:01,920
>> 그리고 실제로, 우리는 볼 수 있습니다
그리고 마지막으로이 느낌

1233
00:45:01,920 --> 00:45:04,090
나는이 세 번째이자 마지막 데모를 끌어합니다.

1234
00:45:04,090 --> 00:45:05,840
이것은 또 다른입니다
그 시각화거야

1235
00:45:05,840 --> 00:45:08,500
왼쪽에 거품 정렬을 표시하려면,
중간에 선택 정렬,

1236
00:45:08,500 --> 00:45:13,410
뭔가 중 하나로서 우리
손, 이전 제안 제기

1237
00:45:13,410 --> 00:45:15,020
오른쪽 정렬을 병합합니다.

1238
00:45:15,020 --> 00:45:16,937
분할 및 정복
오른쪽 전략.

1239
00:45:16,937 --> 00:45:19,520
그리고 우리가하는지, 사실이야
수요일에 볼 것.

1240
00:45:19,520 --> 00:45:21,990
그러나의 병렬로 실행하려면 다음 시간을 할 수 있습니다.

1241
00:45:21,990 --> 00:45:26,765
이것은 대략 동일한 수의
요소들은 모두 동시에 실행.

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
선택 대 버블 정렬
병합 정렬 대 정렬.

1244
00:45:34,440 --> 00:45:36,760
>> 지금, 그들은 모두 실행하고
동시에 이론.

1245
00:45:36,760 --> 00:45:39,830
CPU가 실행되고
같은 속도,하지만

1246
00:45:39,830 --> 00:45:44,014
이 얼마나 지루한 느낄 수있다
매우 빠르게 될 것,

1247
00:45:44,014 --> 00:45:45,930
다만 얼마나 빨리 할 때
우리는 주의 비트를 삽입

1248
00:45:45,930 --> 00:45:49,330
제로의 알고리즘 수
우리는 일을 속도.

1249
00:45:49,330 --> 00:45:51,760
>> 그리고 지금의 비교하자
마지막 형태의이.

1250
00:45:51,760 --> 00:45:55,710
나는 앞서 갈거야
CS50의 웹 사이트에

1251
00:45:55,710 --> 00:45:59,020
우리는 오늘이 마지막 링크가
어디 인터넷에서 사람

1252
00:45:59,020 --> 00:46:03,960
친절하게 비디오를 함께 넣어 그
어떤 다른 정렬을 캡처

1253
00:46:03,960 --> 00:46:07,510
알고리즘은 같은 소리.

1254
00:46:07,510 --> 00:46:09,577
이것은 삽입 정렬이다.

1255
00:46:09,577 --> 00:46:12,072
>> [삐 '소리]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> 이에 당신이 주파수를 적용하고
바 바의 높이를 기준으로합니다.

1258
00:46:16,850 --> 00:46:19,826
이 거품의 일종이다.

1259
00:46:19,826 --> 00:46:21,822
>> [뒤틀린 '삐'소리]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> 오는 is-- 다음 깨달음
위로 다음 is-- 선택 정렬,

1262
00:46:45,774 --> 00:46:48,820
여기서 다시, 우리는 선택하고
다음 작은 요소,

1263
00:46:48,820 --> 00:46:51,820
우리는 성장하고 볼 수 있습니다
왼쪽에서 오른쪽으로.

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> 우리의 우승자 지금까지 오늘, 일종의 병합합니다.

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
이 일을 나누어 어떻게 주목
[들림] 반 분기에.

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
우리가하지 않은 그놈 종류,
에 대해 이야기하고, 시각적으로 작성

1270
00:47:21,660 --> 00:47:24,450
그리고 조금 audally
다른 모양과 소리.

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
앞뒤로가는,
물건을 청소.

1273
00:47:30,160 --> 00:47:32,230
또한 힙 정렬을 체크 아웃
이 남자의 웹 사이트에.

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> 그리고 그것 뿐이다.

1276
00:47:36,810 --> 00:47:38,210
우리는 당신이 다음 번에 ​​볼 수 있습니다.

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> [휙 음악]

1279
00:47:48,334 --> 00:50:24,839