1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [섹션 3 - 더 편안한]

2
00:00:02,570 --> 00:00:05,070
[롭 보덴 - 하버드 대학교 (Harvard University)]

3
00:00:05,070 --> 00:00:07,310
>> [이 CS50입니다. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> 그래서 첫 번째 질문은 이상하게 worded합니다.

5
00:00:12,700 --> 00:00:17,480
GDB는 더 구체적으로 프로그램을 "디버깅"하지만 할 수 있습니다, 당신은 무슨 일을하게됩니까?

6
00:00:17,480 --> 00:00:22,590
나는 거기에 대답을거야, 그리고 당신 정확히 예상 건지 모르겠어요

7
00:00:22,590 --> 00:00:27,910
그래서 그것의 라인을 따라 그게 일이 있는거 같은데하면 단계적으로 할 수 있습니다

8
00:00:27,910 --> 00:00:31,540
그와 상호 작용하는,이 프로그램을 통해 도보로, 변경 변수는이 모든 일을 -

9
00:00:31,540 --> 00:00:34,270
기본적으로 완전히 프로그램의 실행을 제어

10
00:00:34,270 --> 00:00:38,410
그리고 프로그램의 실행 특정 부분을 검사한다.

11
00:00:38,410 --> 00:00:43,030
그래서 그 기능은 당신이 일을 디버깅 보자.

12
00:00:43,030 --> 00:00:44,830
좋아요.

13
00:00:44,830 --> 00:00:50,520
왜 이진 검색은 배열을 정렬 할 것을 요구합니까?

14
00:00:50,520 --> 00:00:53,360
누가 그런 대답을 원하는가?

15
00:00:56,120 --> 00:01:00,070
[학생]가 정렬되지 않은 경우 작동하지 않기 때문에. >> 그래. [웃음]

16
00:01:00,070 --> 00:01:04,910
이 정렬되지 않을 경우, 다음의 절반에 분할 불가능

17
00:01:04,910 --> 00:01:07,850
그리고 왼쪽으로 그 모든 걸 알고 점점 오른쪽으로 전부

18
00:01:07,850 --> 00:01:10,490
중간 값보다 더 크다.

19
00:01:10,490 --> 00:01:12,790
그럼 정렬해야합니다.

20
00:01:12,790 --> 00:01:14,170
좋아요.

21
00:01:14,170 --> 00:01:17,570
왜 제곱 n의 O에 거품 정렬은?

22
00:01:17,570 --> 00:01:23,230
사람이 먼저 버블 정렬이 무슨 날인지 매우 빠른 높은 수준의 개요를 제공할까요?

23
00:01:25,950 --> 00:01:33,020
[학생] 당신은 기본적으로 각 요소에 통과하고 처음 몇 요소를 확인합니다.

24
00:01:33,020 --> 00:01:37,150
그들은 당신이 그들을 교체 곳에서라면, 당신은 다음 몇 요소 등을 확인합니다.

25
00:01:37,150 --> 00:01:40,770
당신이 마지막에 도달하면 다음 가장 큰 요소가 끝 부분에 위치 알고,

26
00:01:40,770 --> 00:01:42,750
그래서 당신은, 하나는 다음 겪고 계속 무시

27
00:01:42,750 --> 00:01:48,490
각 시간은 당신이 더 변경 사항을 않을 때까지 적은 요소를 확인해야합니다. >> 그래.

28
00:01:48,490 --> 00:01:58,470
당신이 그면에 배열 뒤집기를하는 경우 때문에 아래로 일어 서서 때문은, 버블 정렬 수직라고

29
00:01:58,470 --> 00:02:03,100
다음 큰 값은 아래로 가라 앉을 것이며 작은 값은 위로 거품까지 것이다.

30
00:02:03,100 --> 00:02:05,210
그게 그 이름을 방법입니다.

31
00:02:05,210 --> 00:02:08,220
그리고 그래, 당신은 단지를 통해 이동합니다.

32
00:02:08,220 --> 00:02:11,190
당신은 더 큰 가치를 교환, 배열 겪고 계속

33
00:02:11,190 --> 00:02:14,040
아래로 가장 큰 값을 가져옵니다.

34
00:02:14,040 --> 00:02:17,500
>> 왜 제곱 n의 O입니까?

35
00:02:18,690 --> 00:02:24,620
첫째, 사람은 n의 제곱 O 왜하고 싶은 말은 무엇입니까?

36
00:02:24,620 --> 00:02:28,760
[학생] 각 실행에 대해이 n 번에 가면 때문에.

37
00:02:28,760 --> 00:02:32,100
당신은, 당신이 가장 큰 요소 끝까지 간 것 확신 할 수

38
00:02:32,100 --> 00:02:35,230
다음은 많은 요소로 그 방법을 반복해야합니다. >> 그래.

39
00:02:35,230 --> 00:02:41,800
그래서 큰 O가 의미하는과 큰 오메가 무슨 말인지 명심하십시오.

40
00:02:41,800 --> 00:02:50,560
큰 O는 실제로 실행할 수있는 방법을 느린에 행 위처럼입니다.

41
00:02:50,560 --> 00:02:58,990
따라서 제곱 n의 그것이 O를 말하여, 그것은 n의 O하지 않거나 다른 그 실행시킬 수 있습니다

42
00:02:58,990 --> 00:03:02,640
선형 시간에하지만, N cubed의 O입니다

43
00:03:02,640 --> 00:03:06,390
그것은 N cubed의 O에 묶여 때문입니다.

44
00:03:06,390 --> 00:03:12,300
이 제곱 n의 O에 묶여있어 경우, 그것은 N cubed으로도 묶여있어.

45
00:03:12,300 --> 00:03:20,280
따라서이 제곱 습니 있으며, 절대 최악의 경우는 제곱 N보다 더 할 수 없어

46
00:03:20,280 --> 00:03:22,830
그 말은 제곱 N의 O 이유입니다.

47
00:03:22,830 --> 00:03:31,200
그래, 그게 N 제곱으로 나오는 방법에 약간의 수학을 볼 수

48
00:03:31,200 --> 00:03:40,530
우리는 목록에있는 다섯 가지를 가지고 있다면, 처음 몇 스왑 우리는 잠재적해야 할 수

49
00:03:40,530 --> 00:03:47,170
이 이용을 위해? 의를 실제로하자 -

50
00:03:47,170 --> 00:03:52,040
얼마나 많은 스왑 우리는 배열을 통해 버블 정렬의 첫 번째 실행에서해야하는거야?

51
00:03:52,040 --> 00:03:53,540
[학생] N - 1. >> 그래.

52
00:03:53,540 --> 00:03:58,340
>> 1-5 요소가있는 경우, 우리는 n을해야 할거야.

53
00:03:58,340 --> 00:04:01,100
그런 다음 두 번째 하나를 얼마나 많은 스왑 우리가해야하는거야?

54
00:04:01,100 --> 00:04:03,440
[학생] N - 2. >> 그래.

55
00:04:03,440 --> 00:04:11,640
그리고 세 번째는 N이 될 것입니다 - 3, 그리고 편의를 위해 난 마지막 2 개의를 작성합니다

56
00:04:11,640 --> 00:04:15,270
다음으로 우리는이 스왑 1 스왑을해야 할거야.

57
00:04:15,270 --> 00:04:19,899
나는 마지막으로 하나 또는 실제로 일어난해야 할 수도 있고 그렇지 않을 수도 있습니다 같아요.

58
00:04:19,899 --> 00:04:22,820
이 스왑입니까? 모르겠어요.

59
00:04:22,820 --> 00:04:26,490
따라서 이것들은 총 스왑의 양이나해야 할 일이 적어도 비교합니다.

60
00:04:26,490 --> 00:04:29,910
당신은 교환하지 않는 경우에도, 당신은 여전히​​ 값을 비교해야합니다.

61
00:04:29,910 --> 00:04:33,910
따라서 N이 있습니다 - 배열을 통해 처음 실행 1 비교는.

62
00:04:33,910 --> 00:04:42,050
당신이 이런 일을 정렬하는 경우, 일 똑바로 쌓아 그러니 실제로 6 일을하게

63
00:04:42,050 --> 00:04:44,790
그럼 내가, 2, 1 3 다하겠습니다.

64
00:04:44,790 --> 00:04:49,910
그러므로이 금액을 재 배열, 우리는 우리가 만들어 얼마나 많은 비교를보고 싶은

65
00:04:49,910 --> 00:04:52,700
전체 알고리즘 인치

66
00:04:52,700 --> 00:04:56,550
우리는 여기이 사람들을 가지고하면,

67
00:04:56,550 --> 00:05:07,470
그런 다음에 우리가 아직도 있었다 그러나 많은 비교를 합산하고 있습니다.

68
00:05:07,470 --> 00:05:13,280
그러나 우리는 이것들을 요약하고이를 합계하고이를 합계하면,

69
00:05:13,280 --> 00:05:18,130
당신은 여전히​​ 같은 문제입니다. 우리는 그 특정 그룹을 합계.

70
00:05:18,130 --> 00:05:22,400
>> 이제 우리는 3에게 N의를 합산하고 있습니다. 그것은 불과 3 N의 없습니다.

71
00:05:22,400 --> 00:05:27,650
항상 N / 2 N의 질거야.

72
00:05:27,650 --> 00:05:29,430
그래서 여기에 우리는 6가 발생합니다.

73
00:05:29,430 --> 00:05:34,830
우리가 10 가지가 있으면, 우리는 사물의 5 개의 쌍에 대해이 그룹화 할 수

74
00:05:34,830 --> 00:05:37,180
과 n + N + N + N + N이 생깁니다.

75
00:05:37,180 --> 00:05:45,840
그럼 당신은 항상 N / 2 N의를 얻을 것 등이 우리는 N 제곱 / 2로를 조금합니다.

76
00:05:45,840 --> 00:05:48,890
그리고 이제에 와서 일 반 요인,이지만

77
00:05:48,890 --> 00:05:54,190
배열이 지남에 따라 각 반복을 통해 우리가 하나 더 비교는 사실 때문에

78
00:05:54,190 --> 00:05:58,040
그래서 우리가이 극복하는 방법은 있지만, 아직도 제곱 습니됩니다.

79
00:05:58,040 --> 00:06:01,650
우리는 반의 상수 요소에 대해 신경 쓰지 않습니다.

80
00:06:01,650 --> 00:06:07,760
이와 같은 큰 O의 진짜 많이 수학 이러한 종류의 일을, 그냥에 의존 자,

81
00:06:07,760 --> 00:06:12,260
산술 금액과 기하학적 시리즈 물건을하고,

82
00:06:12,260 --> 00:06:17,750
하지만이 과정에서 대부분은 매우 간단합니다.

83
00:06:17,750 --> 00:06:19,290
좋아요.

84
00:06:19,290 --> 00:06:24,430
왜 삽입 정렬은 n의 오메가에? 오메가는 무엇을 의미합니까?

85
00:06:24,430 --> 00:06:27,730
[한 번에 말하기 두 학생 - 이해할 수없는] >> 그래.

86
00:06:27,730 --> 00:06:30,630
오메가 당신은 아래 행으로 생각 할 수 있습니다.

87
00:06:30,630 --> 00:06:36,550
>> 따라서 삽입 정렬 알고리즘이 얼마나 효율적 상관없이,

88
00:06:36,550 --> 00:06:41,810
에 관계없이에지나 목록, 항상 적어도 N 물건을 비교하는

89
00:06:41,810 --> 00:06:44,620
아니면 N 일 동안 반복한다.

90
00:06:44,620 --> 00:06:47,280
왜 그럴까요?

91
00:06:47,280 --> 00:06:51,190
[학생] 때문에 목록이 이미 정렬되어있는 경우 다음을 통해 첫 번째 반복

92
00:06:51,190 --> 00:06:54,080
만, 최초의 요소가 최소입니다 보장 할 수

93
00:06:54,080 --> 00:06:56,490
두 번째 반복은 당신은 단지 첫 두가 보장 할 수

94
00:06:56,490 --> 00:07:00,010
당신은 목록의 나머지는 정렬됩니다 알 수 없기 때문입니다. >> 그래.

95
00:07:00,010 --> 00:07:08,910
당신은 최소한 완전히 정렬 된 목록에 통과하면 모든 요소를​​ 통해 가야

96
00:07:08,910 --> 00:07:12,180
아무것도 주위에 이동 할 필요가 없다 볼 수 있습니다.

97
00:07:12,180 --> 00:07:14,720
그래서 목록을 통해 전달 아, 그리고 이것은 이미 정렬 말은

98
00:07:14,720 --> 00:07:18,240
당신이이 정렬하는지 알고에 각 요소를 확인하기 전에는 불가능

99
00:07:18,240 --> 00:07:20,660
그들은 정렬 순서에 있는지 확인하십시오.

100
00:07:20,660 --> 00:07:25,290
그래서 삽입 정렬에 행 낮은은 n의 오메가입니다.

101
00:07:25,290 --> 00:07:28,210
최악의 경우는, 병합 정렬 시간 무엇을 실행중인

102
00:07:28,210 --> 00:07:31,390
최악의 경우 다시 빅 O 것?

103
00:07:31,390 --> 00:07:37,660
따라서 최악의 시나리오에 병합 정렬은 어떻게 실행합니까?

104
00:07:42,170 --> 00:07:43,690
[학생] N 로그 N. >> 그래.

105
00:07:43,690 --> 00:07:49,990
가장 빠른 일반적인 정렬 알고리즘은 N 로그 N 수 있습니다. 당신은 더 잘할 수 없습니다.

106
00:07:51,930 --> 00:07:55,130
>> 이 특별한 경우가 있으며, 우리가 오늘 시간이 있으면 - 우리는 아마도 그게 좀 -

107
00:07:55,130 --> 00:07:59,330
우리는 N 로그 N보다 나은 수행을 볼 수 있습니다.

108
00:07:59,330 --> 00:08:04,050
그러나 일반적으로 경우에, 당신은 N 로그 N보다 더 할 수 없습니다.

109
00:08:04,050 --> 00:08:09,680
그리고 병합 정렬은 N 로그 N이이 과정에 대해 알고 있어야 사람이되고 발생합니다.

110
00:08:09,680 --> 00:08:13,260
그래서 우리는 실제로 오늘날 구현됩니다.

111
00:08:13,260 --> 00:08:18,070
그리고 마지막으로, 더 이상 세 개의 문장에서 어떻게 선택 정렬 작업을합니까?

112
00:08:18,070 --> 00:08:20,370
누군가에게 묻고 싶은 않으며, 당신의 문장을 계산합니다

113
00:08:20,370 --> 00:08:22,390
왜냐하면 당신은 3 위에 가면 -

114
00:08:25,530 --> 00:08:28,330
사람이 선택 정렬을 기억 하는가?

115
00:08:31,280 --> 00:08:37,809
선택 정렬은 이름에서 기억 일반적으로 매우 간단합니다.

116
00:08:37,809 --> 00:08:45,350
넌 그냥 배열을 통해 반복, 어쨌든 가장 큰 값이 아니면 작은 발견 -

117
00:08:45,350 --> 00:08:47,290
당신이 들어 정렬간에 순서

118
00:08:47,290 --> 00:08:50,750
그럼 우리가 작은에서 큰에 정리하고 있어요 가정 해 보겠습니다.

119
00:08:50,750 --> 00:08:55,250
당신은 최소한의 요소가 무엇이든간에 찾고, 배열을 통해 반복

120
00:08:55,250 --> 00:08:59,750
을 선택한 다음, 그냥 처음에 무엇이든을 바꾸고.

121
00:08:59,750 --> 00:09:04,090
그리고 배열을 통해 두번째 패스에서 다시 최소 요소를 찾습니다

122
00:09:04,090 --> 00:09:07,490
을 선택한 다음, 두 번째 위치에있는 것만을 바꾸고.

123
00:09:07,490 --> 00:09:10,650
그래서 우리는 선별 및 최소 값을 선택하는

124
00:09:10,650 --> 00:09:16,050
그리고 배열의 앞쪽으로 삽입하면이 정렬 될 때까지.

125
00:09:19,210 --> 00:09:21,560
그 질문 있나?

126
00:09:21,560 --> 00:09:25,710
>> 이러한 필연적으로 당신이 pset를 제출 할 때 작성해야하는 형태로 나타납니다.

127
00:09:29,010 --> 00:09:32,360
사람들은 기본적으로 해당에 대한 답변입니다.

128
00:09:32,360 --> 00:09:34,230
그럼 이제 문제를 코딩.

129
00:09:34,230 --> 00:09:40,140
이미 이메일을 통해 발송 - 사람은 이메일을받지 못하셨습니까? 좋아요.

130
00:09:40,140 --> 00:09:46,630
난 이미 이메일을 통해 우리가 사용하려고하고있는 공간을 발송

131
00:09:46,630 --> 00:09:52,120
당신이 내 이름을 클릭하면 - 그리고 그래서 내가 바닥에 할 것 같아요

132
00:09:52,120 --> 00:09:57,170
때문에 뒤로 R의 - 당신이 내 이름을 클릭하면 당신은이 버전을 볼 수 있습니다.

133
00:09:57,170 --> 00:10:02,650
금요일 수정 1 전 이미 복사 공간에 코드를 붙여 넣을 수 것입니다

134
00:10:02,650 --> 00:10:06,900
검색 문제에 대해 당신은 구현해야 할거야.

135
00:10:06,900 --> 00:10:10,540
및 개정 2 우리가 그 후에 구현 정렬 일이 될 것입니다.

136
00:10:10,540 --> 00:10:15,770
그럼 당신은 내 일 월요일 수정 1을 클릭하고 거기에서 작업 할 수 있습니다.

137
00:10:17,350 --> 00:10:22,060
그리고 지금 우리는 이진 검색을 구현​​하고 싶습니다.

138
00:10:22,060 --> 00:10:26,470
>> 사람은 의사 높은 수준의 설명을 제공하기 위해 하는가

139
00:10:26,470 --> 00:10:31,440
무엇을 우리가 검색 할 필요가가는 건가요? 그래.

140
00:10:31,440 --> 00:10:36,170
[학생] 당신은 배열의 중간을하고 원하는되는지 확인

141
00:10:36,170 --> 00:10:38,650
보다 작거나 그 이상입니다.

142
00:10:38,650 --> 00:10:41,080
그리고 더 있다면, 당신은 덜 반으로 이동

143
00:10:41,080 --> 00:10:44,750
더 있다면, 당신은 더 반에 가서 당신은 반복 당신은 한 가지를 얻을 때까지.

144
00:10:44,750 --> 00:10:46,570
[보덴] 그래.

145
00:10:46,570 --> 00:10:51,320
우리의 숫자 배열이 이미 정렬이된다는 것을 명심,

146
00:10:51,320 --> 00:10:57,190
그리고 그건 우리가 활용할 수 있으며, 우리가 먼저 확인 할 수 있다는 것을 의미

147
00:10:57,190 --> 00:11:00,390
알았어, 내가 50 번째 찾고 있어요.

148
00:11:00,390 --> 00:11:03,720
그래서 중간에 이동할 수 있습니다.

149
00:11:03,720 --> 00:11:07,380
중동, 이건 일 짝수 때 정의하기 어렵다

150
00:11:07,380 --> 00:11:10,820
하지만 우리가 항상 중간에 자르됩니다 거라고 만 말해 두지.

151
00:11:10,820 --> 00:11:14,420
그래서 여기에 우리는 8 일이 있으므로, 중간은 16이 될 것입니다.

152
00:11:14,420 --> 00:11:17,330
나는 50을 찾고 있는데, 50 대 16보다 큽니다.

153
00:11:17,330 --> 00:11:21,310
그래서 지금은 기본적으로 이러한 요소로 내 배열을 처리 할 수​​ 있습니다.

154
00:11:21,310 --> 00:11:23,450
난 16에서 온 모든 것을 던져 수 있습니다.

155
00:11:23,450 --> 00:11:27,440
지금 내 배열은 이러한 4 가지 요소이고, 나는 반복한다.

156
00:11:27,440 --> 00:11:31,910
그래서 내가 다시 중간을 찾고 싶어요, 어떤이 42가 될 것입니다.

157
00:11:31,910 --> 00:11:34,730
42 50 이하이며, 그래서이 두 요소를 던져 수 있습니다.

158
00:11:34,730 --> 00:11:36,890
이건 내 남은 배열입니다.

159
00:11:36,890 --> 00:11:38,430
다시 중간을 찾을거야.

160
00:11:38,430 --> 00:11:42,100
난 항상 왼쪽에 물건을 버린 건데 때문에, 50 나쁜 예를했던 것 같은데

161
00:11:42,100 --> 00:11:48,280
하지만 같은 조치에 의해, 경우에 난 뭔가를 찾고 있어요

162
00:11:48,280 --> 00:11:52,100
그리고 내가 현재보고 요소보다 덜

163
00:11:52,100 --> 00:11:55,080
그런 다음 오른쪽에있는 모든 버릴거야.

164
00:11:55,080 --> 00:11:58,150
이제 우리는 그렇게 구현해야합니다.

165
00:11:58,150 --> 00:12:02,310
우리는 크기가 통과 할 필요가납니다.

166
00:12:02,310 --> 00:12:06,730
우리는 또한 하드 코드 크기가 필요 없습니다.

167
00:12:06,730 --> 00:12:11,640
우리가 제거한다면 # 정의 -

168
00:12:19,630 --> 00:12:21,430
좋아요.

169
00:12:21,430 --> 00:12:27,180
어떻게 멋지게 숫자 배열의 크기가 현재 무슨 알아낼 수 있나요?

170
00:12:27,180 --> 00:12:30,950
>> 숫자 배열에서 얼마나 많은 요소?

171
00:12:30,950 --> 00:12:33,630
[학생] 숫자, 괄호,. 길이?

172
00:12:33,630 --> 00:12:36,600
[보덴]는 C.에 존재하지 않습니다

173
00:12:36,600 --> 00:12:38,580
필요합니다. 길이입니다.

174
00:12:38,580 --> 00:12:42,010
배열 속성을 필요가 없습니다, 배열의 더 길이 속성이 없습니다 때문에

175
00:12:42,010 --> 00:12:45,650
그 그냥 갈거야 당신은 그러나 긴 줄 것이다.

176
00:12:48,180 --> 00:12:51,620
[학생] 그것이 얼마나 많은 메모리를 확인하고 얼마나 많은에 의해 분할 - >> 그래.

177
00:12:51,620 --> 00:12:55,810
그럼 어떻게 우리는이 얼마나 메모리를 볼 수 있나요? >> [학생] Sizeof. >> 네, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof는 숫자 배열의 크기를 반환하는거야 연산자입니다.

179
00:13:01,680 --> 00:13:10,060
그리고 그러나 많은 정수 할 거에요 시간은 정수의 크기 없습니다

180
00:13:10,060 --> 00:13:14,050
그 실제로 차지 얼마나 기억 이니까.

181
00:13:14,050 --> 00:13:17,630
나는 배열의 가지 수를 원하는하면,

182
00:13:17,630 --> 00:13:20,560
그럼 내가 정수의 크기에 따라 나눌 싶은거야.

183
00:13:22,820 --> 00:13:26,010
좋아요. 그래서 그런 날 여기서 크기 전달 할 수 있습니다.

184
00:13:26,010 --> 00:13:29,430
이유는 전혀 크기로 전달해야하나요?

185
00:13:29,430 --> 00:13:38,570
왜 그냥 int는 크기가 여기에 할 수 없어 = sizeof (건초 더미) / sizeof (int는)?

186
00:13:38,570 --> 00:13:41,490
왜 작동하지 않는 이유는 무엇입니까?

187
00:13:41,490 --> 00:13:44,470
[학생]은 전역 변수 아닙니다.

188
00:13:44,470 --> 00:13:51,540
[보덴] 덤불이 존재 우리는 모래 사장으로 번호를 전달하고

189
00:13:51,540 --> 00:13:54,700
그리고이 온 건지의 foreshadowing 종류입니다. 그래.

190
00:13:54,700 --> 00:14:00,170
[학생] 건초 더미 그냥에 대한 참조이므로 해당 참조가 얼마나 큰 반환합니다.

191
00:14:00,170 --> 00:14:02,150
그래.

192
00:14:02,150 --> 00:14:09,000
난 당신이 정말 바로 아직 스택을 본 한 강의에서 의심?

193
00:14:09,000 --> 00:14:11,270
우리는 그것에 대해 이야기를 나눴습니다.

194
00:14:11,270 --> 00:14:16,090
귀하의 모든 변수는 저장하려고 곳 스택입니다.

195
00:14:16,090 --> 00:14:19,960
>> 지역 변수에 할당에 대한 기억은 스택에 갈 수 있습니다

196
00:14:19,960 --> 00:14:24,790
각 함수는 스택에 자신의 공간을지면 자신의 스택 프레임은이란이다.

197
00:14:24,790 --> 00:14:31,590
그럼 메인은 스택 프레임을 가지고 있으며, 내부 그것의이 숫자 배열을 존재하는 것이다

198
00:14:31,590 --> 00:14:34,270
그리고 크기 sizeof (숫자)이 될거야.

199
00:14:34,270 --> 00:14:38,180
그것은 요소의 크기로 나눈 숫자의 크기를 갖게되는구나

200
00:14:38,180 --> 00:14:42,010
하지만 메인의 스택 프레임 내의 모든 삶을 그.

201
00:14:42,010 --> 00:14:45,190
우리가 검색을 호출하면 검색 자체 스택 프레임을 도착

202
00:14:45,190 --> 00:14:48,840
자신의 공간을 지역 변수를 모두 저장할 수 있습니다.

203
00:14:48,840 --> 00:14:56,420
그러나 이러한 주장은 - 그래서 모래 사장이 전체 배열의 복사본이 아닙니다.

204
00:14:56,420 --> 00:15:00,990
우리는 검색에 사본으로 전체 배열에 전달하지 않습니다.

205
00:15:00,990 --> 00:15:04,030
이건 그냥 배열에 대한 참조를 전달합니다.

206
00:15:04,030 --> 00:15:11,470
따라서 검색이 참조를 통해이 숫자에 액세스 할 수 있습니다.

207
00:15:11,470 --> 00:15:17,100
아직, 주의 스택 프레임의 내부에 살고있는 일들을 액세스있어

208
00:15:17,100 --> 00:15:22,990
하지만 기본적으로, 우리는 포인터에 도착하면, 이는 곧 올 거예요,

209
00:15:22,990 --> 00:15:24,980
이 포인터가 무엇인지입니다.

210
00:15:24,980 --> 00:15:29,400
포인터는 일에 대한 참조이며, 당신은 물건을 액세스 할 포인터를 사용할 수 있습니다

211
00:15:29,400 --> 00:15:32,030
다른 것들 '스택 프레임에서 해당합니다.

212
00:15:32,030 --> 00:15:37,660
숫자가 메인에 로컬하더라도 그래서, 우리는 우리가 여전히이 포인터를 통해 액세스 할 수 있습니다.

213
00:15:37,660 --> 00:15:41,770
그러나 단지 포인터이고, 단지 참조니까,

214
00:15:41,770 --> 00:15:45,040
sizeof (건초 더미)는 단지 참조 자체의 크기를 반환합니다.

215
00:15:45,040 --> 00:15:47,950
그것이 가리키는있어 물건의 크기를 반환하지 않습니다.

216
00:15:47,950 --> 00:15:51,110
이 숫자의 실제 크기를 반환하지 않습니다.

217
00:15:51,110 --> 00:15:55,660
우리가 원하는대로 그리고이 작동하지 않을 수 있습니다.

218
00:15:55,660 --> 00:15:57,320
>> 그 질문 있나?

219
00:15:57,320 --> 00:16:03,250
포인터는 오는 주에 훨씬 더 많은 유혈 자세히으로 없어 질 것입니다.

220
00:16:06,750 --> 00:16:13,740
왜 표시되는 일, 대부분의 검색 물건 또는 정렬 많은, 그리고이 집은

221
00:16:13,740 --> 00:16:16,990
거의 모든 배열의 실제 크기를해야 할거야

222
00:16:16,990 --> 00:16:20,440
C에 속하기 때문이다, 우리는 배열의 크기가 뭔지는 전혀 감이 없습니다.

223
00:16:20,440 --> 00:16:22,720
당신은 수동으로 들여 통과해야

224
00:16:22,720 --> 00:16:27,190
방금 참조를 전달 있기 때문에 그리고 당신은 수동으로 전체 배열에 전달할 수 없습니다

225
00:16:27,190 --> 00:16:30,390
그리고 참조의 크기를 얻을 수 없습니다.

226
00:16:30,390 --> 00:16:32,300
좋아요.

227
00:16:32,300 --> 00:16:38,160
이제 우리는 전에 설명 된 것을 구현하고 싶습니다.

228
00:16:38,160 --> 00:16:41,530
당신은 잠시 동안 그 작업을 할 수 있습니다

229
00:16:41,530 --> 00:16:45,250
그리고 당신은 모든 것을 완벽하게 백퍼센트 작업을 것에 대해 걱정할 필요가 없습니다.

230
00:16:45,250 --> 00:16:51,410
당신이이 일을해야한다고 생각 방법에 대한 반 의사를 써주세요.

231
00:16:52,000 --> 00:16:53,630
좋아요.

232
00:16:53,630 --> 00:16:56,350
완전히 아직이 작업을 수행 할 필요가 없습니다.

233
00:16:56,350 --> 00:17:02,380
그러나 사람은, 지금까지 일이있는 편안한 기분

234
00:17:02,380 --> 00:17:05,599
뭔가처럼 우리가 함께 사용할 수 있습니까?

235
00:17:05,599 --> 00:17:09,690
사람이 자원 봉사할까요? 아니면 내가 무작위로 선택됩니다.

236
00:17:12,680 --> 00:17:18,599
그것은 바로 어떤 조치하지만 우리가 작업 상태로 수정할 수 있습니다 무언가가 될 필요가 없습니다.

237
00:17:18,599 --> 00:17:20,720
[학생] 그래. 좋아요 >>.

238
00:17:20,720 --> 00:17:27,220
그래서 작은 저장 아이콘을 클릭하여 수정 사항을 저장할 수 있습니다.

239
00:17:27,220 --> 00:17:29,950
당신이 옳아, Ramya 거지? >> [학생] 그래. >> [보덴] 좋아요.

240
00:17:29,950 --> 00:17:35,140
이제 당신의 버전을 볼 수 있으며, 모든 사용자가 수정을 끌어 수 있습니다.

241
00:17:35,140 --> 00:17:38,600
그리고 여기에 우리가 있습니다 - 그래.

242
00:17:38,600 --> 00:17:43,160
그럼 Ramya는 확실히 유효한 솔루션입니다 재귀 솔루션과 함께했다.

243
00:17:43,160 --> 00:17:44,970
이 문제를 할 수있는 두 가지 방법이 있습니다.

244
00:17:44,970 --> 00:17:48,060
당신도 반복적으로 또는 반복적으로 할 수 있습니다.

245
00:17:48,060 --> 00:17:53,860
당신은 재귀 적으로 수행 할 수있는 발생하는 대부분의 문제는 반복적으로 수행 할 수 있습니다.

246
00:17:53,860 --> 00:17:58,510
그래서 여기에 우리가 반복적으로 그것을 한 적이있어.

247
00:17:58,510 --> 00:18:03,730
>> 누군가는 함수가 재귀 수 있도록 의미를 정의 할합니까?

248
00:18:07,210 --> 00:18:08,920
[학생]는 당신이 기능이되면 자신을 호출

249
00:18:08,920 --> 00:18:13,470
사실과 진실에 나오는 때까지 다음 자체를 호출합니다. >> 그래.

250
00:18:13,470 --> 00:18:17,680
재귀 함수는 자신을 호출하는 기능입니다.

251
00:18:17,680 --> 00:18:24,140
재귀 함수가 있어야 세 곳의 큰 가지가 있습니다.

252
00:18:24,140 --> 00:18:27,310
먼저 분명히, 그 자체를 호출합니다.

253
00:18:27,310 --> 00:18:29,650
두 번째는 기본 경우가 있습니다.

254
00:18:29,650 --> 00:18:33,390
그런 점에서이 함수 자체를 호출 중지해야합니다

255
00:18:33,390 --> 00:18:35,610
그의 기본 케이스는 무슨 일 것입니다.

256
00:18:35,610 --> 00:18:43,860
그래서 여기 우리가 중지해야한다는 것을 알, 우리는 검색에 포기해야

257
00:18:43,860 --> 00:18:48,150
시작은 끝을 동일 때 - 우리는 그게 뭘 뜻 갈거야.

258
00:18:48,150 --> 00:18:52,130
그러나 마지막으로, 재귀 함수에 대한 중요 마지막으로 :

259
00:18:52,130 --> 00:18:59,250
기능은 어떻게 든 기본 케이스를 접근해야합니다.

260
00:18:59,250 --> 00:19:04,140
두 번째 재귀 호출을 할 때 실제로 아무것도 업데이트하지 않는 경우처럼,

261
00:19:04,140 --> 00:19:07,880
당신은 말 그대로 그냥 같은 인수와 함께 다시 함수를 호출하는 경우

262
00:19:07,880 --> 00:19:10,130
그리고 더 전역 변수는 변경하거나 아무 것도있다

263
00:19:10,130 --> 00:19:14,430
당신은 기본 케이스에 도달하지 않습니다이 경우 좋지 인치

264
00:19:14,430 --> 00:19:17,950
그것은 무한 재귀와 스택 오버플로 될 것입니다.

265
00:19:17,950 --> 00:19:24,330
하지만 여기 우리는 우리가 시작 할 + 끝 / 2 업데이트 이후 업데이트가 일어나는 것을 볼

266
00:19:24,330 --> 00:19:28,180
우리는 여기에서 시작 인수를 업데이트, 여기 최종 인수를 업데이트하고 있습니다.

267
00:19:28,180 --> 00:19:32,860
이 모든 재귀 호출에서 우리가 뭔가를 업데이트하고 있습니다. 좋아요.

268
00:19:32,860 --> 00:19:38,110
귀하의 솔루션을 통해 우리를 걸어 하시겠습니까? >> 물론이지.

269
00:19:38,110 --> 00:19:44,270
나는 때마다 내가이 함수 호출을 너무 SearchHelp를 사용

270
00:19:44,270 --> 00:19:47,910
나는 배열에 원하는 곳의 시작과 끝을 가지고

271
00:19:47,910 --> 00:19:49,380
어디에서 나는 배열을 찾고 있어요.

272
00:19:49,380 --> 00:19:55,330
>> 사고가 시작되는 중간 요소 + 끝 / 2인데 모든 단계에서,

273
00:19:55,330 --> 00:19:58,850
우리가 찾고있는 같다?

274
00:19:58,850 --> 00:20:04,650
그게 있다면, 우리는 그것을 발견, 나는 재귀의 수준을 통과하면 그 같아요.

275
00:20:04,650 --> 00:20:12,540
그게 사실이 아니라면 그리고, 우리는, 배열의 중간 값이 너무 커서 있는지 확인

276
00:20:12,540 --> 00:20:19,320
경우있는 우리는 시작부터 중간 색인으로 이동하여 배열의 왼쪽 이분의 일 봐.

277
00:20:19,320 --> 00:20:22,710
그리고 그렇지 않으면 우리는 결국 반을.

278
00:20:22,710 --> 00:20:24,740
[보덴] 좋아.

279
00:20:24,740 --> 00:20:27,730
좋은 생각이에요.

280
00:20:27,730 --> 00:20:36,640
좋아요, 몇 가지 있으므로, 실제로이 매우 높은 수준 일이

281
00:20:36,640 --> 00:20:41,270
언니는이 과정에 대해 알아야 할하지 않습니다,하지만 사실입니다.

282
00:20:41,270 --> 00:20:46,080
재귀 기능, 당신은 언제나 나쁜 것만은 면서요?

283
00:20:46,080 --> 00:20:51,160
당신은 재귀 적으로 자신을 너무 많이 호출하는 경우, 당신은 스택 오버 플로우를하기 때문에

284
00:20:51,160 --> 00:20:54,990
내가 전에 말했듯이 이후, 모든 기능은 자체 스택 프레임을 가져옵니다.

285
00:20:54,990 --> 00:20:59,500
그래서 재귀 함수의 각 호출은 자신의 스택 프레임을 가져옵니다.

286
00:20:59,500 --> 00:21:04,140
이 1,000 재귀 호출을한다면, 당신은 1000 스택 프레임을

287
00:21:04,140 --> 00:21:08,390
빠르게 당신은 너무 많은 스택 프레임과 일들이 그냥 무단 필요로 이어집니다.

288
00:21:08,390 --> 00:21:13,480
재귀 함수는 일반적으로 나쁜 그래서 그게.

289
00:21:13,480 --> 00:21:19,370
그러나 재귀 함수의 좋은 일부는 꼬리 - 재귀 함수를이라고합니다

290
00:21:19,370 --> 00:21:26,120
이는 컴파일러가이 통지하는 경우 하나의 예를 들어 할 일

291
00:21:26,120 --> 00:21:29,920
하고해야, 내 생각 엔 - 꽝에 당신은 - O2의 깃발을 통과하면

292
00:21:29,920 --> 00:21:33,250
다음이 꼬리 재귀이 발견하고 일 잘 할 것입니다.

293
00:21:33,250 --> 00:21:40,050
>> 그것은 각 재귀 호출에 대해 다시 이상 같은 스택 프레임을 재사용합니다.

294
00:21:40,050 --> 00:21:47,010
이 같은 스택 프레임을 사용하고 있기 때문에 그리고, 당신은 걱정하지 않아도됩니다

295
00:21:47,010 --> 00:21:51,690
당신은 전에 말했듯이 이제까지 넘쳐을 쌓아, 같은 시간에,

296
00:21:51,690 --> 00:21:56,380
당신은 TRUE를 반환 곳 한 번, 다음이 스택 프레임의 모든을 반환하는

297
00:21:56,380 --> 00:22:01,740
그리고 SearchHelp은 9로 돌아가이의 열째 호출, 8로 돌아합니다.

298
00:22:01,740 --> 00:22:05,360
그래서 그런 기능이 꼬리 재귀 때 일어날 필요가 없습니다.

299
00:22:05,360 --> 00:22:13,740
그리고 어떤이 함수 꼬리 재귀 만드는 것은 통보는 그 searchHelp에 특정 통화에 대한

300
00:22:13,740 --> 00:22:18,470
가 쌓아가 는걸 재귀 호출은 반환있어.

301
00:22:18,470 --> 00:22:25,290
따라서 SearchHelp에 대한 첫 번째 호출에서, 우리는 하나 즉시 false를 반환

302
00:22:25,290 --> 00:22:29,590
바로 TRUE를 반환, 또는 우리는 SearchHelp에 재귀 호출을

303
00:22:29,590 --> 00:22:33,810
우리가 돌​​려하면 해당 호출이 반환 무엇입니다.

304
00:22:33,810 --> 00:22:51,560
우리가 INT X = SearchHelp, 반품 X * 2와 같은 짓을한다면 우리는이 작업을 수행 할 수 없습니다

305
00:22:51,560 --> 00:22:55,440
그냥 무작위로 변화.

306
00:22:55,440 --> 00:23:01,470
>> 그래서 지금이 재귀 호출이 int는 X = SearchHelp 재귀 호출

307
00:23:01,470 --> 00:23:05,740
실제로 반환해야 않기 때문에 꼬리가 더 이상은 재귀입니다

308
00:23:05,740 --> 00:23:10,400
다시 이전 스택 프레임에 해당하므로 함수에 그 이전 호출

309
00:23:10,400 --> 00:23:13,040
한 다음 반환 값으로 뭔가를 할 수 있습니다.

310
00:23:13,040 --> 00:23:22,190
그래서이 꼬리 재귀가 아니라 꼬리 재귀 잘되기 전에 우리가했던 일. 그래.

311
00:23:22,190 --> 00:23:27,000
[학생]하는 것은 두 번째 기본 케이스가 먼저 확인해야하지 않겠

312
00:23:27,000 --> 00:23:30,640
당신이에게 인수를 전달 곳 때 상황이있을 수 있기 때문에

313
00:23:30,640 --> 00:23:35,770
당신은 = 끝을 시작했지만, 그들은 바늘 값입니다.

314
00:23:35,770 --> 00:23:47,310
끝이 바늘 값입니다 질문은 우리가이 사건을 실행할 수 없습니다되었습니다

315
00:23:47,310 --> 00:23:52,000
또는 = 끝을 시작 적절 = 종료를 시작합니다

316
00:23:52,000 --> 00:23:59,480
당신은 실제로, 아직 해당 특정 값을 확인하지 않은

317
00:23:59,480 --> 00:24:03,910
그런 다음 + 끝 / 2를 시작은 같은 값 될 것입니다.

318
00:24:03,910 --> 00:24:07,890
그러나 우리는 이미 true를 반환 한 우리는 실제로 값을 검사하지 않습니다.

319
00:24:07,890 --> 00:24:14,240
크기가 0이면 따라서 최소한 첫 번째 전화에서, 우리는 False를 반환하고 싶습니다.

320
00:24:14,240 --> 00:24:17,710
크기가 1이라면, 그 시작은 평등 끝으로 이동되지 않습니다

321
00:24:17,710 --> 00:24:19,820
우리는 적어도 한 요소가 있는지 확인합니다.

322
00:24:19,820 --> 00:24:26,750
하지만, 당신이 + 끝 / 2를 시작 위치를 우리가 경우에 결국 수 있다는 점에서 옳다고 생각

323
00:24:26,750 --> 00:24:31,190
시작, 시작 + 끝 / 2와 같은 존재 종료

324
00:24:31,190 --> 00:24:35,350
그러나 우리는 실제로 요소를 선택하지 마십시오.

325
00:24:35,350 --> 00:24:44,740
>> 그래서 우리가 먼저 확인한다면 중간 요소는, 우리가 찾는 값

326
00:24:44,740 --> 00:24:47,110
그러면 우리는 바로 TRUE를 반환 할 수 있습니다.

327
00:24:47,110 --> 00:24:50,740
그들은 같은거야 다른 경우, 계속해서 아무런 변화가 없다

328
00:24:50,740 --> 00:24:58,440
우리는 우리가 단일 요소 배열에있는 경우로 업데이트 할거야 때문입니다.

329
00:24:58,440 --> 00:25:01,110
그 하나의 요소는 우리가 찾고있는 사람이없는 경우

330
00:25:01,110 --> 00:25:03,530
모든게 잘못되었습니다. 그래.

331
00:25:03,530 --> 00:25:08,900
[학생] 문제는, 크기부터 배열의 구성 요소 수보다 실제로 큰 것입니다

332
00:25:08,900 --> 00:25:13,070
오프셋은 이미이 - >>은 따라서 크기가됩니다 -

333
00:25:13,070 --> 00:25:19,380
[학생]는 배열의 크기가 0이라면 말 다음 SearchHelp는 실제로 0의 모래 사장을 검사합니다

334
00:25:19,380 --> 00:25:21,490
첫 번째 통화.

335
00:25:21,490 --> 00:25:25,300
>> 네 - 배열의 크기는 0을 가지고 0집니다.

336
00:25:25,300 --> 00:25:30,750
그 일이 또 있지 - 좋은 수 있습니다. 의 생각 좀 해보자.

337
00:25:30,750 --> 00:25:40,120
배열은 10 원소를 가지고 우리가 확인 가고있는 가운데 하나는 인덱스 5,이면

338
00:25:40,120 --> 00:25:45,700
그래서 우리는 5를 확인하고, 값이 적은 말합시다.

339
00:25:45,700 --> 00:25:50,720
그래서 우리는 5 이후에서 떨어져 모든 것을 던져 요.

340
00:25:50,720 --> 00:25:54,030
그럼 끝 / 2의 새로운 끝 될 것입니다 + 시작

341
00:25:54,030 --> 00:25:57,450
그래 그래서 항상 배열의 끝 넘어있을거야.

342
00:25:57,450 --> 00:26:03,570
그건 마치하거나,​​ 이상한면이 사실이라면, 우리는, 말, 4를 확인 것

343
00:26:03,570 --> 00:26:05,770
하지만 우리는 여전히 포기하겠다 니 -

344
00:26:05,770 --> 00:26:13,500
그래 그래서 끝은 항상 배열의 실제 끝 이상 될 것입니다.

345
00:26:13,500 --> 00:26:18,350
우리가에 초점을 맞추고있는 요소 그래서 끝은 항상 그 후에 하나가 될 것입니다.

346
00:26:18,350 --> 00:26:24,270
시작 적 평등 말을한다면 그리고, 우리는 크기 0의 배열입니다.

347
00:26:24,270 --> 00:26:35,600
>> 내가 생각했는데 다른 건 우리가 시작되는 시작을 업데이트하고 있습니다 + 끝 / 2입니다

348
00:26:35,600 --> 00:26:44,020
그래서이 + 끝 / 2를 시작합니다 제가에 문제가있는 경우는,

349
00:26:44,020 --> 00:26:46,820
우리가 확인하고있는 요소입니다.

350
00:26:46,820 --> 00:26:58,150
자, 우리가이 10 요소 배열을 가지고 말한다. 뭐든간에.

351
00:26:58,150 --> 00:27:03,250
그럼 끝 / 2이 같은 뭔가있을 것입니다 + 시작

352
00:27:03,250 --> 00:27:07,060
그리고 그 값이 아니라면, 우리는 업데이트 할 말한다.

353
00:27:07,060 --> 00:27:10,060
이 값은 더 크다, 그래서 우리는 배열의이 반쪽 좀보세요.

354
00:27:10,060 --> 00:27:15,910
그래서 우리는 시작을 업데이트하는 방법, 우리는이 요소로 시작을 업데이트하고 있습니다.

355
00:27:15,910 --> 00:27:23,790
그러나 아직도 작동 할 수 있습니다, 또는 적어도, 당신은 시작을 할 수 + 끝 / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[학생] 당신은 + 끝을 시작 할 필요는 없습니다 [안 들리게] >> 그래.

357
00:27:27,850 --> 00:27:33,240
우리는 이미이 요소를 확인하고 우리가 찾고있는 사람은 알아 있습니다.

358
00:27:33,240 --> 00:27:36,800
그래서 우리는이 요소로 시작을 업데이트 할 필요가 없습니다.

359
00:27:36,800 --> 00:27:39,560
우리는 그것을 생략하고이 요소하기 시작 업데이트 할 수 있습니다.

360
00:27:39,560 --> 00:27:46,060
그리고 경우 적 있는데,이 끝이라고 말합시다,

361
00:27:46,060 --> 00:27:53,140
이 것 때문에 시작을 누른 다음, + 끝을 시작 / 2이 될,

362
00:27:53,140 --> 00:28:00,580
+ 끝을 시작 - 예, 나는 무한 재귀에 끝낼 수 있다고 생각합니다.

363
00:28:00,580 --> 00:28:12,690
그냥 크기 2 크기 1 배열의 배열 보자 말한다. 이 일 것이라 생각합니다.

364
00:28:12,690 --> 00:28:19,490
따라서 현재 시작 요소와 끝이없는 1이다.

365
00:28:19,490 --> 00:28:24,110
그래서 우리가 확인하는 것하는 요소는,이 하나입니다

366
00:28:24,110 --> 00:28:29,400
그리고 우리가 시작을 업데이트 할 때, 우리는 0 + 1 / 2,로 시작 업데이트

367
00:28:29,400 --> 00:28:33,160
이는 시작이 요소가되는 우리를 다시 종료 예정이다.

368
00:28:33,160 --> 00:28:36,210
>> 그래서 우리는 다시 이상 같은 요소를 확인하고 있습니다.

369
00:28:36,210 --> 00:28:43,310
그래서이 모든 재귀 호출은 실제로 무언가를 업데이트해야하는 경우입니다.

370
00:28:43,310 --> 00:28:48,370
그래서 우리는 사건이 시작 + 끝 / + 1 또는 다른 2 할 필요가

371
00:28:48,370 --> 00:28:50,710
어디 우리가 실제로 시작을 업데이트하지.

372
00:28:50,710 --> 00:28:53,820
누구나 다 봤어?

373
00:28:53,820 --> 00:28:56,310
좋아요.

374
00:28:56,310 --> 00:29:03,860
사람이이 솔루션이나 더 많은 댓글에 대해 질문이 있습니까?

375
00:29:05,220 --> 00:29:10,280
좋아요. 사람이 우리가 볼 수있는 솔루션을 반복십니까?

376
00:29:17,400 --> 00:29:20,940
우리 모두 재귀 적으로 그 짓을 한거야?

377
00:29:20,940 --> 00:29:25,950
아니면 또 그 여자를 열 경우, 당신은 이전을 무시 아마 그랬을거야.

378
00:29:25,950 --> 00:29:28,810
가 자동으로 저장합니까? 나는 긍정적 아니야.

379
00:29:35,090 --> 00:29:39,130
사람이 반복십니까?

380
00:29:39,130 --> 00:29:42,430
우리는 함께 통과하면 할 수 없습니다.

381
00:29:46,080 --> 00:29:48,100
이 아이디어는 동일 될 것입니다.

382
00:30:00,260 --> 00:30:02,830
솔루션을 반복.

383
00:30:02,830 --> 00:30:07,140
우리는 기본적으로 같은 생각을하고 싶어요 할거야

384
00:30:07,140 --> 00:30:16,530
우리는 배열의 새로운 끝을 추적하고 배열의 새로운 시작을 유지하려는

385
00:30:16,530 --> 00:30:18,510
그리고 그게 반복 않습니다.

386
00:30:18,510 --> 00:30:22,430
그리고 우리가 시작과 끝 어느 교차하면서 추적을 유지하고 있는지 경우,

387
00:30:22,430 --> 00:30:29,020
그리고 우리는 그것을 찾을 수 없습니다 우리는 false를 반환 할 수 있습니다.

388
00:30:29,020 --> 00:30:37,540
그럼 난해야하나요? 누구든지 꺼내 나에게 제안이나 코드가 있습니까?

389
00:30:42,190 --> 00:30:47,450
[학생] 한동안 루프를 수행합니다. >> 그래.

390
00:30:47,450 --> 00:30:49,450
당신은 루프를하고 싶은 것입니다.

391
00:30:49,450 --> 00:30:51,830
>> 당신은 내가 끌어 수있는 코드가나요 무엇을 당신이 제안하는거야?

392
00:30:51,830 --> 00:30:56,340
[학생] 그런 것 같아요. >> 좋아. 이 일이 쉬울 수 있습니다. 이름이 무엇입니까?

393
00:30:56,340 --> 00:30:57,890
[학생] 루카스.

394
00:31:00,140 --> 00:31:04,190
금요일 수정 1. 좋아요.

395
00:31:04,190 --> 00:31:13,200
낮은 우리가 전에 시작이라는거야.

396
00:31:13,200 --> 00:31:17,080
최대 우리가 이전에 종료라는 매우 일이 아닙니다.

397
00:31:17,080 --> 00:31:22,750
사실, 끝은 배열 내에서 지금이다. 우리가 고려해야 할 요소입니다.

398
00:31:22,750 --> 00:31:26,890
따라서 낮은이 0, 최대 배열의 크기 - 1

399
00:31:26,890 --> 00:31:34,780
지금 우리는 반복하고 있으며, 우리는 확인하는 중입니다 -

400
00:31:34,780 --> 00:31:37,340
난 당신이 통과 할 수 같아요.

401
00:31:37,340 --> 00:31:41,420
이런 식으로 당신의 생각은 무엇입니까? 코드를 통해 저희를 걸어보세요.

402
00:31:41,420 --> 00:31:49,940
[학생] 그래. 중간에있는 건초 더미 값을보고 바늘에 비교합니다.

403
00:31:49,940 --> 00:31:58,520
오, 사실은, 그 뒤로해야 - 그게 당신의 바늘보다 더 있다면 그래서 당신은 원하는.

404
00:31:58,520 --> 00:32:05,180
당신은 오른쪽 절반을 멀리 던져 싶을 거예요, 그래서 그래, 그 방법이 될 것입니다.

405
00:32:05,180 --> 00:32:08,830
[보덴]는 그래서이 미만이어야 하는가? 그 말은 무엇입니까? >> [학생] 그래.

406
00:32:08,830 --> 00:32:10,390
[보덴] 좋아. 조금 덜.

407
00:32:10,390 --> 00:32:15,700
우리가보고있는 것은 우리가 원하는 것보다 작다면은,

408
00:32:15,700 --> 00:32:19,410
그리고 그래, 우리는 왼쪽 절반을 버리려하고

409
00:32:19,410 --> 00:32:22,210
어떤 우리가 생각하는 모든 업데이트하는 의미

410
00:32:22,210 --> 00:32:26,610
배열의 오른쪽에 낮은 이동하여.

411
00:32:26,610 --> 00:32:30,130
이 좋아 보인다.

412
00:32:30,130 --> 00:32:34,550
내 말은, 우리가 이전에 말한 것과 같은 문제를 가지고 있다고 생각

413
00:32:34,550 --> 00:32:49,760
어디에서 낮은은 0이며 최대 1이 낮은 다음입니다 + 위 / 2 다시 같은 일로 설정 할 경우.

414
00:32:49,760 --> 00:32:53,860
>> 그리고 그런 경우가 아닌 경우에도, 그것은 적어도 아직 더 효율적입니다

415
00:32:53,860 --> 00:32:57,630
단지 요소를 버릴 우리는 우리가 잘못 알고있는 바라 보았다.

416
00:32:57,630 --> 00:33:03,240
따라서 낮은 + 위 / 2 + 1 - >> [학생] 그건 다른 방법이 있어야합니다.

417
00:33:03,240 --> 00:33:05,900
[보덴] 또는이 있어야합니다 - 1, 다른 하나는 + 1 있어야합니다.

418
00:33:05,900 --> 00:33:09,580
[학생] 그리고 더블이 있어야 등호. >> [보덴] 그래.

419
00:33:09,580 --> 00:33:11,340
[학생] 그래.

420
00:33:14,540 --> 00:33:15,910
좋아요.

421
00:33:15,910 --> 00:33:21,280
그리고 마지막으로, 이제이 + 1이 있는지 - 1 일,

422
00:33:21,280 --> 00:33:31,520
그게 - 그게되지 않을 수 있습니다 - 그것은 낮은에보다 큰 값을 끝내고 다시 수 있나요?

423
00:33:35,710 --> 00:33:40,320
가능성이 있나요 - 난 무슨 일이 할 수있는 유일한 방법은 생각 하나? >> [학생] 내가 모르겠어요.

424
00:33:40,320 --> 00:33:45,220
하지만립니다 도착 후 마이너스 도착하면 그 다음 1 - >> 그래.

425
00:33:45,220 --> 00:33:47,480
[학생]은 가능성이 엉망 것입니다.

426
00:33:49,700 --> 00:33:53,940
나는 단 한 잘해야한다고 생각

427
00:33:53,940 --> 00:33:58,800
가 낮은 결국하는 사람들이 동일 할 것입니다, 나는 생각합니다.

428
00:33:58,800 --> 00:34:03,070
사람들이 동일한 경우 그러나, 우리는 시작하는 동안 루프를 수행하지 않았을

429
00:34:03,070 --> 00:34:06,670
그리고 우리가 값을 반환합니다. 그래서 지금 우리가 좋은 것 같아요.

430
00:34:06,670 --> 00:34:11,530
공지 사항이이 문제를 더 이상 재귀 없다하더라도

431
00:34:11,530 --> 00:34:17,400
우리가이 그렇게 쉽게 자체적으로 확인할 수있는 아이디어의 같은 종류가 적용

432
00:34:17,400 --> 00:34:23,659
우리가 다시 이상 인덱스를 업데이트한다는 사실에 의해 재귀 솔루션,

433
00:34:23,659 --> 00:34:29,960
우리는 문제가 작아하는거야, 우리는 배열의 하위 집합에 초점을하고 있습니다.

434
00:34:29,960 --> 00:34:40,860
[학생] 낮은이 0과 최대 1이면, 그들은 모두, 0 + 1 / 2, 0으로가는거야 것

435
00:34:40,860 --> 00:34:44,429
그리고 하나 + 1 것, 하나는 것 - 1.

436
00:34:47,000 --> 00:34:50,870
[학생] 어디 ​​평등을 확인하는거야?

437
00:34:50,870 --> 00:34:55,100
중간 사람이 실제로 바늘 경우처럼?

438
00:34:55,100 --> 00:34:58,590
현재 그런 짓도하지 않았어? 오!

439
00:35:00,610 --> 00:35:02,460
뭐냐면 경우 -

440
00:35:05,340 --> 00:35:13,740
예. 시작하자 첫 번째 중간 말을하기 때문에 우리는 여기까지 테스트를하지 못하는 -

441
00:35:13,740 --> 00:35:16,430
[학생] 실제로 바인딩을 버리지 똑같아.

442
00:35:16,430 --> 00:35:20,220
당신이 바운드를 던져 버리면 그럼, 첫 번째 또는 무엇이든을 확인해야합니다.

443
00:35:20,220 --> 00:35:23,350
아. 그래. >> [학생] 그래.

444
00:35:23,350 --> 00:35:29,650
이제 우리는 우리가 현재를 바라 보았다 하나를 멀리 던진 것

445
00:35:29,650 --> 00:35:33,260
그건 우리가 또한 현재이 필요합니다 의미합니다

446
00:35:33,260 --> 00:35:44,810
(건초 더미은 [(낮은 + 최대) / 2] == 바늘), 우리는 TRUE를 반환 할 수 있습니다.

447
00:35:44,810 --> 00:35:52,070
그리고 다른하거나하는 경우 넣어 있는지, 그건 말 그대로 같은 일을 의미합니다

448
00:35:52,070 --> 00:35:57,110
이 사실이 반환했을 때문입니다.

449
00:35:57,110 --> 00:36:01,450
그래서 다른 경우 올려 놓을 게요,하지만 중요하지 않습니다.

450
00:36:01,450 --> 00:36:10,440
>> 그래서 다른이, 다른이,이 내가 할 일반적인 일이있는 경우

451
00:36:10,440 --> 00:36:14,340
어디에 모든 여기 좋은 경우 경우에도

452
00:36:14,340 --> 00:36:22,780
낮은가보다 클 수 없어 같은, 그 사실 여부에 대한 가치를 추론 없습니다.

453
00:36:22,780 --> 00:36:28,010
낮은보다 작거나 같다면서 그래서 당신은뿐만 아니라 말할 수도

454
00:36:28,010 --> 00:36:30,720
또는 낮은 미만 중에

455
00:36:30,720 --> 00:36:35,300
저들은 같거나 낮은 경우 그래서, 통과 일

456
00:36:35,300 --> 00:36:40,130
그리고 우리는이 루프의 탈출 할 수 있습니다.

457
00:36:41,410 --> 00:36:44,630
질문, 문제, 의견이 있으십니까?

458
00:36:47,080 --> 00:36:49,270
좋아요. 이 좋아 보인다.

459
00:36:49,270 --> 00:36:52,230
이제 우리는 정렬을하고 싶어요.

460
00:36:52,230 --> 00:37:04,030
우리가 저의 두 번째 버전으로 가면, 우리는 이와 같은 숫자를 볼 수

461
00:37:04,030 --> 00:37:07,550
하지만 지금은 정렬 순서가 더 이상 없습니다.

462
00:37:07,550 --> 00:37:12,840
그리고 우리는 N 로그 N의 O에서 알고리즘을 사용하여 정렬을 구현하고 싶습니다.

463
00:37:12,840 --> 00:37:17,240
우리가 여기 구현해야하는 알고리즘을 것 같아? >> [학생] 병합 정렬.

464
00:37:17,240 --> 00:37:23,810
[보덴] 그래. 병합 정렬은 수 있도록 우리가 할 수있는 일은 무엇이야, O (N 로그 N)입니다.

465
00:37:23,810 --> 00:37:26,680
그리고 문제는 매우 유사한 될 것입니다

466
00:37:26,680 --> 00:37:31,920
어디서 쉽게 재귀 솔루션을 자체적으로.

467
00:37:31,920 --> 00:37:35,580
우리가 원하는 경우 또한, 반복적 인 솔루션을 가지고 올 수

468
00:37:35,580 --> 00:37:42,540
하지만 재귀 여기 쉬워 질 것이며 우리는 재귀를해야합니다.

469
00:37:45,120 --> 00:37:49,530
내 말은, 우리가 처음 병합 정렬 통과 될 듯

470
00:37:49,530 --> 00:37:54,280
병합 정렬의 아름다운 동영상이 이미 있지만. [웃음]

471
00:37:54,280 --> 00:37:59,780
그럼 저 밖에 정렬 병합 -이 문서의 많은 낭비하고 있습니다.

472
00:37:59,780 --> 00:38:02,080
아, 왼쪽에 하나 남았어요.

473
00:38:02,080 --> 00:38:03,630
따라서 병합합니다.

474
00:38:08,190 --> 00:38:12,470
아, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
좋아요.

476
00:38:29,910 --> 00:38:33,460
병합 두 개의 별도의 배열을 소요됩니다.

477
00:38:33,460 --> 00:38:36,780
개별적으로 두 배열을 정렬됩니다 모두.

478
00:38:36,780 --> 00:38:40,970
그래서 배열, 1, 3, 5, 정렬. 이 배열, 0, 2, 4, 정렬.

479
00:38:40,970 --> 00:38:46,710
이제 어떻게 병합 어떻게해야하는 자체가 정렬됩니다 하나의 배열로 그들을 결합합니다.

480
00:38:46,710 --> 00:38:57,130
그래서 우리는 그 내부에 이러한 요소를 갖게 돼 크기가 6 배열을 원하는

481
00:38:57,130 --> 00:38:59,390
정렬 순서를 유지해야합니다.

482
00:38:59,390 --> 00:39:03,390
>> 그래서 우리는 이러한 두 배열이 정렬되어 있다는 사실을 활용할 수

483
00:39:03,390 --> 00:39:06,800
선형 시간에이 작업을 수행하려면,

484
00:39:06,800 --> 00:39:13,510
선형 시간 의미이 배열은 크기 X이며,이 크기 Y 인 경우는,

485
00:39:13,510 --> 00:39:20,970
다음 총 알고리즘은 O (X + Y)해야합니다. 좋아요.

486
00:39:20,970 --> 00:39:23,150
제안 그럼.

487
00:39:23,150 --> 00:39:26,030
[학생] 우리는 왼쪽에서 시작 될까요?

488
00:39:26,030 --> 00:39:30,150
그럼 당신은 첫번째 다운 후 1 0을 놓을 게요 그리고 당신은 여기 2에있다.

489
00:39:30,150 --> 00:39:33,320
그래서 당신이 오른쪽으로 움직 탭을 것 같은 그런거야. >> [보덴] 그래.

490
00:39:33,320 --> 00:39:41,070
우리가 왼쪽 요소에 초점을 경우 다음 배열 둘 다하십시오.

491
00:39:41,070 --> 00:39:43,530
두 배열이 정렬되기 때문에, 우리는 알이 두 요소

492
00:39:43,530 --> 00:39:46,920
두 배열에서 가장 작은 요소입니다.

493
00:39:46,920 --> 00:39:53,500
그래서 지난 2 요소의 1의 병합 배열에서 가장 작은 요소해야한다는 것을 의미합니다.

494
00:39:53,500 --> 00:39:58,190
그건 아주 작은이 오른쪽이 시간에 한 것을 발생합니다.

495
00:39:58,190 --> 00:40:02,580
0 미만이기 때문에 그래서 우리는, 0을 왼쪽에 삽입

496
00:40:02,580 --> 00:40:08,210
그래서, 0을 첫 번째 위치에 삽입 후 우리는이 업데이트

497
00:40:08,210 --> 00:40:12,070
이제 첫 번째 요소에 집중하기로하였습니다.

498
00:40:12,070 --> 00:40:14,570
그리고 지금 우리는 반복한다.

499
00:40:14,570 --> 00:40:20,670
이제 우리는 2 비교하고 1. 1 작, 그래서 우리는 1 삽입됩니다.

500
00:40:20,670 --> 00:40:25,300
우리는이 사람을 가리 키도록이 포인터를 업데이트합니다.

501
00:40:25,300 --> 00:40:33,160
이제 우리는 다시는 이런 짓을, 2 때문에. 이 업데이트,이 2, 3을 비교합니다.

502
00:40:33,160 --> 00:40:37,770
다음이 업데이트 4, 5.

503
00:40:37,770 --> 00:40:42,110
그럼 병합입니다.

504
00:40:42,110 --> 00:40:49,010
>> 우리가 한 번만 각 요소를 통해 이동하고 있기 때문에 선형 시간입니다 분명해야합니다.

505
00:40:49,010 --> 00:40:55,980
그래서 병합 정렬 이런 짓을하는 거지 구현에 가장 큰 단계입니다.

506
00:40:55,980 --> 00:40:59,330
그리고 그리 어렵지도 않아.

507
00:40:59,330 --> 00:41:15,020
걱정할 것 몇가지는 가자 우리가 1, 2, 3, 4, 5, 6을 병합 한 말입니다.

508
00:41:15,020 --> 00:41:30,930
이 경우 우리는이 하나가 작아 질 것입니다 시나리오에 종료

509
00:41:30,930 --> 00:41:36,160
그리고 우리가이 포인터를 업데이트이 하나가 작아 질 것입니다,이 업데이트

510
00:41:36,160 --> 00:41:41,280
이 하나는 작은, 그리고 지금은 인식​​해야

511
00:41:41,280 --> 00:41:44,220
당신이 실제로와 비교하는 요소가 부족했을 때.

512
00:41:44,220 --> 00:41:49,400
우리는 이미이 전체 배열을 사용했기 때문에

513
00:41:49,400 --> 00:41:55,190
이 배열의 모든 지금은 여기에 삽입됩니다.

514
00:41:55,190 --> 00:42:02,040
우리는 언제나 우리의 배열 중 하나가 완전히 이미 병합되어있는 포인트로 실행한다면

515
00:42:02,040 --> 00:42:06,510
다음에 우리가 다른 배열의 모든 요소를​​ 가지고 배열의 끝 부분에 삽입.

516
00:42:06,510 --> 00:42:13,630
그래서 우리는 단지, 5, 6을 4 삽입 할 수 있습니다. 좋아요.

517
00:42:13,630 --> 00:42:18,070
그 해보세요 한 것입니다.

518
00:42:22,080 --> 00:42:26,120
그 1 단계해야 구현.

519
00:42:26,120 --> 00:42:32,600
병합 그에 따라 다음 정렬, 그것은 2 단계, 2 단계 바보입니다.

520
00:42:38,800 --> 00:42:42,090
우선은이 배열을 제공합니다.

521
00:42:57,920 --> 00:43:05,680
따라서 정렬 병합 1 단계는 반복적으로 절반에 배열을 깰 것입니다.

522
00:43:05,680 --> 00:43:09,350
그럼 절반에이 배열을 분할.

523
00:43:09,350 --> 00:43:22,920
우리는 지금 4, 15, 16, 50 및 8, 23, 42, 108이 있습니다.

524
00:43:22,920 --> 00:43:25,800
그리고 이제 다시는 이런 짓을 우리는 반쪽으로이 분할.

525
00:43:25,800 --> 00:43:27,530
이면에 할 만합니다.

526
00:43:27,530 --> 00:43:34,790
50, 4, 15, 16 그럼.

527
00:43:34,790 --> 00:43:37,440
우리는 여기에 같은 일을 할 것입니다.

528
00:43:37,440 --> 00:43:40,340
그리고 지금 우리는 다시 절반으로 나눠.

529
00:43:40,340 --> 00:43:51,080
그리고 우리는 4, 15, 16, 50가 있습니다.

530
00:43:51,080 --> 00:43:53,170
그래서 우리의 기본 케이스입니다.

531
00:43:53,170 --> 00:44:00,540
배열의 크기가 1의지면, 우리는 절반으로 분할을 중지합니다.

532
00:44:00,540 --> 00:44:03,190
>> 이제 우리는 이걸 어떻게하지?

533
00:44:03,190 --> 00:44:15,730
이 또한 8, 23, 42, 그리고 108로 분석을 끝내고.

534
00:44:15,730 --> 00:44:24,000
이제 우리는이 시점에서 건, 지금 병합 정렬의 두 방금 목록으로 쌍을 병합되어 단계.

535
00:44:24,000 --> 00:44:27,610
그래서 우리는이를 병합하고 싶습니다. 우리는 병합 전화.

536
00:44:27,610 --> 00:44:31,410
우리는 병합 정렬 순서이를 반환합니다 알아요.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
이제 우리는 이러한 병합하려는 그건 정렬 순서들로 목록을 반환합니다

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
우리는 사람들을 병합 - 나는 쓸 수 - 8, 23, 42, 108.

541
00:44:57,380 --> 00:45:02,890
그래서 우리는 한 번에 병합 쌍을 수 있습니다.

542
00:45:02,890 --> 00:45:05,140
이제 우리는 다시 병합합니다.

543
00:45:05,140 --> 00:45:10,130
그 자체로이 목록의 각이 정렬되고 있다는 사실을 알 수,

544
00:45:10,130 --> 00:45:15,220
그리고 우리가 정렬됩니다 크기 4의 목록을 이러한 목록을 병합 할 수 있습니다

545
00:45:15,220 --> 00:45:19,990
및 정렬 크기 4의 목록을 가져 두 목록을 병합합니다.

546
00:45:19,990 --> 00:45:25,710
그리고 마지막으로, 우리는 정렬 크기 8 중 하나를 목록을 가져 오려면 크기 4의 두 목록을 병합 할 수 있습니다.

547
00:45:25,710 --> 00:45:34,030
여기가 전체 N 로그 N 것을 확인하기 위해 우리는 이미 병합 선형 것을 보았다,

548
00:45:34,030 --> 00:45:40,390
그래서 때 우리는 그렇게 병합의 전체 비용 같은 이들을 병합을 상대

549
00:45:40,390 --> 00:45:43,410
이 두 목록에 단 2 때문입니다 -

550
00:45:43,410 --> 00:45:49,610
또는 잘, 그것은 n의 O이지만, 여기에 N는이 두 요소이므로 2입니다.

551
00:45:49,610 --> 00:45:52,850
그리고이 2 2되며이 2 2되며이 2 2 수

552
00:45:52,850 --> 00:45:58,820
그래서 우리가해야하는 병합 전체에서, 우리는 n을하고 결국.

553
00:45:58,820 --> 00:46:03,210
이처럼 + 2 + 2 + 2는 N이 8입니다

554
00:46:03,210 --> 00:46:08,060
그래서이 세트에 통합의 비용 습니됩니다.

555
00:46:08,060 --> 00:46:10,810
그리고 여기에 같은.

556
00:46:10,810 --> 00:46:16,980
우리는이 2,이 두 병합되며 개별적으로이 병합은 수술을 4 이동합니다

557
00:46:16,980 --> 00:46:23,610
이 병합,이 모든 사이에 다시 한번 수술을 4 차례 걸릴,하지만

558
00:46:23,610 --> 00:46:29,030
우리가 합병을 N 총 일 결국, 그래서이 단계 N이 걸립니다.

559
00:46:29,030 --> 00:46:33,670
그리고 각 단계는 통합 된 N 요소를 걸립니다.

560
00:46:33,670 --> 00:46:36,110
>> 그리고 얼마나 많은 수준 있습니까?

561
00:46:36,110 --> 00:46:40,160
각 수준에서의 배열은 크기를 2로 증가.

562
00:46:40,160 --> 00:46:44,590
다음은 배열의 크기는 하나의 아르 여기가 사이즈 2의 야, 여기 사람들은, 크기 4 야

563
00:46:44,590 --> 00:46:46,470
마지막으로, 그들은 크기가 8하고 있습니다.

564
00:46:46,470 --> 00:46:56,450
이 배로 증가되어 있으므로 있기 때문에, 로그의 N이 수준의 총이있을거야하고 ​​있습니다.

565
00:46:56,450 --> 00:47:02,090
따라서 로그 N 레벨, 각 레벨 복용 N 총 작업과,

566
00:47:02,090 --> 00:47:05,720
우리는 N 로그 N 알고리즘을.

567
00:47:05,720 --> 00:47:07,790
질문이 있으십니까?

568
00:47:08,940 --> 00:47:13,320
사람들은 이미 구현하는 방법에 대한 진전이 좀 있었나요?

569
00:47:13,320 --> 00:47:18,260
난 그냥 자신의 코드를 살펴볼 수 이미 상태에 아무도 없어요?

570
00:47:20,320 --> 00:47:22,260
좀 기다려 줄 수 있습니다.

571
00:47:24,770 --> 00:47:27,470
이 사람은 더 이상 될 것입니다.

572
00:47:27,470 --> 00:47:28,730
나는 매우 재발하는 것이 좋습니다 -

573
00:47:28,730 --> 00:47:30,510
당신은 병합에 대한 재귀을 할 필요가 없습니다

574
00:47:30,510 --> 00:47:33,750
병합에 대한 재귀을 수행하기 때문에 당신은 다양한 크기의 무리를 통과 할거야.

575
00:47:33,750 --> 00:47:37,150
당신은 할 수 있지만, 그것은 괴롭히는입니다.

576
00:47:37,150 --> 00:47:43,720
그러나 정렬 자체에 대한 재귀 아주 간단합니다.

577
00:47:43,720 --> 00:47:49,190
당신은 문자 그대로 오른쪽 절반에 정렬, 왼쪽 부분에 정렬를 호출합니다. 좋아요.

578
00:47:51,770 --> 00:47:54,860
누구나 아직 당겨 수 있을까요?

579
00:47:54,860 --> 00:47:57,540
아니면 좀 기다려주지.

580
00:47:58,210 --> 00:47:59,900
좋아요.

581
00:47:59,900 --> 00:48:02,970
누구든지 우리가 작업 할 수있어?

582
00:48:05,450 --> 00:48:09,680
아니면 우리가 그냥이 작동하고 거기에서 확장됩니다.

583
00:48:09,680 --> 00:48:14,050
>> 누구나 내가 살펴볼 수있는 이것보다 더 있나요?

584
00:48:14,050 --> 00:48:17,770
[학생] 그래. 당신은 내를 당겨 수 있습니다. >> 좋아.

585
00:48:17,770 --> 00:48:19,730
네!

586
00:48:22,170 --> 00:48:25,280
[학생] 조건이 많이있었습니다. >> 오, 이런. 당신은 할 수 있습니다 -

587
00:48:25,280 --> 00:48:28,110
[학생] 내가 저장해야합니다. >> 그래.

588
00:48:32,420 --> 00:48:35,730
그래서 우리는 개별적으로 병합을 수행 했어요.

589
00:48:35,730 --> 00:48:38,570
아,하지만 그렇게 나쁘지 않아.

590
00:48:39,790 --> 00:48:41,650
좋아요.

591
00:48:41,650 --> 00:48:47,080
그럼 정렬은 mergeSortHelp를 호출 자체입니다.

592
00:48:47,080 --> 00:48:49,530
mergeSortHelp이 무엇을 우리에게 설명합니다.

593
00:48:49,530 --> 00:48:55,700
[학생] MergeSortHelp 꽤 많이 두 가지 주요 단계를 수행,

594
00:48:55,700 --> 00:49:01,270
이는 배열의 각 절반을 정렬하고 둘을 병합하는 것입니다.

595
00:49:04,960 --> 00:49:08,050
[보덴] 그래, 그럼 잠깐만을 제공합니다.

596
00:49:10,850 --> 00:49:13,210
내가이 생각을 - >> [학생] 내가 필요 -

597
00:49:17,100 --> 00:49:19,400
그래. 난 뭔가를 누락되었습니다.

598
00:49:19,400 --> 00:49:23,100
병합에서, 나는 새로운 배열을 만들 필요가 있다고 인식

599
00:49:23,100 --> 00:49:26,530
나는 자리에 할 수 없어. >> 예. 당신은 할 수 있습니다. 수정.

600
00:49:26,530 --> 00:49:28,170
[학생] 그래서 새로운 배열을 만들 수 있습니다.

601
00:49:28,170 --> 00:49:31,510
나는 다시 변경하려면 병합의 끝 부분에 잊어 버렸습니다.

602
00:49:31,510 --> 00:49:34,490
좋아요. 우리는 새로운 배열이 필요합니다.

603
00:49:34,490 --> 00:49:41,000
병합 정렬에서는이 거의 항상 사실입니다.

604
00:49:41,000 --> 00:49:44,340
더 나은 알고리즘 시간을 벌었의 비용의 일부

605
00:49:44,340 --> 00:49:47,310
거의 항상 조금 더 많은 메모리를 사용하는 필요합니다.

606
00:49:47,310 --> 00:49:51,570
그래서 여기, 당신이 아무리이 정렬 병합 없다

607
00:49:51,570 --> 00:49:54,780
당신은 필연적으로 몇 가지 여분의 메모리를 사용해야합니다.

608
00:49:54,780 --> 00:49:58,240
그 또는 그녀는 새로운 배열을 만들었습니다.

609
00:49:58,240 --> 00:50:03,400
그리고는 말에 우리가 원래의 배열에 새로운 배열을 복사 할 필요가 말한다.

610
00:50:03,400 --> 00:50:04,830
[학생] 내가 그래, 그렇게 생각 해요.

611
00:50:04,830 --> 00:50:08,210
그 참조 또는 어떤에 의해 계산의 관점에서 작동 있을지 모르겠어 -

612
00:50:08,210 --> 00:50:11,650
그래, 작동합니다. >> [학생] 좋아요.

613
00:50:20,620 --> 00:50:24,480
이을 실행 해 봤어요? >> [학생] 아니, 아직. 좋아요 >>.

614
00:50:24,480 --> 00:50:28,880
를 실행 해, 그리고 난 잠시 그​​것에 대해 얘기하자.

615
00:50:28,880 --> 00:50:35,200
[학생] 난하지만 모든 함수 프로토 타입 모든이 필요합니다?

616
00:50:37,640 --> 00:50:40,840
함수 프로토 타입. 예 - 오, 당신은 같은 의미합니다.

617
00:50:40,840 --> 00:50:43,040
정렬 mergeSortHelp를 호출합니다.

618
00:50:43,040 --> 00:50:47,390
>> 따라서 정렬 mergeSortHelp을 (를) 호출 할 수 있도록, mergeSortHelp이 두 정의되어 있어야합니다

619
00:50:47,390 --> 00:50:56,370
정렬하기 전이나 우리는 프로토 타입을 필요 해요. 그냥 복사하는 붙여 넣습니다.

620
00:50:56,370 --> 00:50:59,490
그리고 마찬가지로, mergeSortHelp는 병합 전화입니다

621
00:50:59,490 --> 00:51:03,830
하지만 병합이 아직 정의되지 않은, 그래서 우리는 mergeSortHelp 알려 수

622
00:51:03,830 --> 00:51:08,700
그게 병합 어떤 모양 것입니다, 그리고 그 걸.

623
00:51:09,950 --> 00:51:15,730
mergeSortHelp 했어요.

624
00:51:22,770 --> 00:51:32,660
우리가 더 기본 케이스가 없습니다있는 우리는 여기서 문제가 있습니다.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp가 재귀이기 때문에, 모든 재귀 함수

626
00:51:38,110 --> 00:51:42,610
재귀 자체를 호출 멈출 때를 알고 기본 케이스의 어떤 종류를해야 할 것입니다.

627
00:51:42,610 --> 00:51:45,590
우리의 기본 사건은 여기서 무엇을 할 것입니까? 그래.

628
00:51:45,590 --> 00:51:49,110
[학생] 크기가 1이면? >> [보덴] 예.

629
00:51:49,110 --> 00:51:56,220
우리가 바로 본 자처럼, 우리는 분할 배열을 중지

630
00:51:56,220 --> 00:52:01,850
일단 우리는 필연적으로 자신을 정렬 크기 1의 배열에 들어 갔어요.

631
00:52:01,850 --> 00:52:09,530
크기가 1 동일 경우 그래서, 우리는 우리가, 배열이 이미 정렬됩니다 알고

632
00:52:09,530 --> 00:52:12,970
그래서 우리는 그냥 돌아갈 수 있습니다.

633
00:52:12,970 --> 00:52:16,880
>> 무효 야주의 때문에 특정 아무것도 반환하지 않습니다, 우리는 반환합니다.

634
00:52:16,880 --> 00:52:19,580
좋아요. 그럼 그건 우리의 기본 케이스입니다.

635
00:52:19,580 --> 00:52:27,440
나는 우리가, 크기 0의 배열을 병합 할 일이 경우, 기본 케이스도 할 수 있겠 군

636
00:52:27,440 --> 00:52:30,030
우리는 아마 어떤 시점에서 중지하려면

637
00:52:30,030 --> 00:52:33,610
그래서 우리는 단지 미만 2보다 작거나 1 같은 크기를 말할 수

638
00:52:33,610 --> 00:52:37,150
이 지금 어떤 배열을 위해 일 할 수 있도록.

639
00:52:37,150 --> 00:52:38,870
좋아요.

640
00:52:38,870 --> 00:52:42,740
그럼 그건 우리의 기본 케이스입니다.

641
00:52:42,740 --> 00:52:45,950
이제 병합을 통해 문의 걸어 나가고 싶어요?

642
00:52:45,950 --> 00:52:49,140
이러한 모든 경우는 무엇을 의미합니까?

643
00:52:49,140 --> 00:52:54,480
여기에, 우리는 같은 생각을하고있는 -

644
00:52:56,970 --> 00:53:02,470
[학생] 내가 모든 mergeSortHelp 전화와 크기를 통과해야합니다.

645
00:53:02,470 --> 00:53:10,080
나는 추가 기본으로 크기를 추가하고 크기 / 2처럼, 없습니다.

646
00:53:10,080 --> 00:53:16,210
[보덴] 오, 크기 / 2, 크기 / 2. >> [학생] 그래, 또한뿐만 아니라 위의 기능 인치

647
00:53:16,210 --> 00:53:21,320
[보덴] 여기? >> [학생] 바로 크기입니다. >> [보덴] 오. 크기, 크기? >> [학생] 그래.

648
00:53:21,320 --> 00:53:23,010
[보덴] 좋아.

649
00:53:23,010 --> 00:53:26,580
잠깐만 내 말 좀 들어 생각해 보자.

650
00:53:26,580 --> 00:53:28,780
우리는 문제로 실행하려면 어떻게해야합니까?

651
00:53:28,780 --> 00:53:33,690
우리는 항상 0으로 왼쪽을 치료하고 있습니다. >> [학생] 번호

652
00:53:33,690 --> 00:53:36,340
너무 이상 해요. 미안 해요. 그것은 시작해야합니다. 그래.

653
00:53:36,340 --> 00:53:39,230
[보덴] 좋아. 난 더 좋아.

654
00:53:39,230 --> 00:53:43,880
그리고 끝. 좋아요.

655
00:53:43,880 --> 00:53:47,200
그래서 지금은 병합을 통해 문의 걸어 나가고 싶어요? >> [학생] 좋아요.

656
00:53:47,200 --> 00:53:52,150
난 내가 만든이 새로운 배열을 통해 걷고거야.

657
00:53:52,150 --> 00:53:57,420
의 크기는 우리가 정렬 할 배열의 부분의 크기

658
00:53:57,420 --> 00:54:03,460
내가 새로운 배열 단계에서 넣어해야하는 요소를 찾기 위해 노력.

659
00:54:03,460 --> 00:54:10,140
배열의 왼쪽 이분의 일이 더 이상 요소가 계속되면 그게을 수행하는, 제가 처음으로 확인하고 있어요,

660
00:54:10,140 --> 00:54:14,260
그렇지되면, 당신은 말에 의하면 다른 조건에 가서

661
00:54:14,260 --> 00:54:20,180
좋아요, 오른쪽 배열에 있어야합니다, 우리는 newArray의 현재 색인에 넣어드립니다.

662
00:54:20,180 --> 00:54:27,620
>> 배열의 오른쪽도 완료하는 경우 그리고 그렇지 않으면, 확인하고 있어요

663
00:54:27,620 --> 00:54:30,630
이 경우 그냥 왼쪽에 넣어.

664
00:54:30,630 --> 00:54:34,180
그래서 실제로 필요하지 않을 수도 있습니다. 잘 모르겠 는데요.

665
00:54:34,180 --> 00:54:40,970
어쨌든, 두의 어느 다른 두 검사는 왼쪽이나 오른쪽 작은 수 있습니다.

666
00:54:40,970 --> 00:54:49,770
또한 각각의 경우에, 나는 증가 중 자리 표시 자 증가거야.

667
00:54:49,770 --> 00:54:52,040
[보덴] 좋아.

668
00:54:52,040 --> 00:54:53,840
좋았어.

669
00:54:53,840 --> 00:54:58,800
누구든지 의견이나 우려 사항이나 질문이 있습니까?

670
00:55:00,660 --> 00:55:07,720
또는 다섯 것 같아 - - 우리가 존재에 물건을 가지고 있다고 사가지 경우 자

671
00:55:07,720 --> 00:55:13,100
그러나 우리는, 왼쪽 배열은 우리가 병합 할 필요가 떨쳐 버리게되었는지 여부를 결정해야

672
00:55:13,100 --> 00:55:16,390
오른쪽 배열은 우리가 병합 할 필요가 떨쳐 버리게되었는지 여부 -

673
00:55:16,390 --> 00:55:18,400
나는 아무 것도 지적하고있는 겁니다.

674
00:55:18,400 --> 00:55:21,730
따라서 왼쪽 배열 떨쳐 버리게 되었어 또는 오른쪽 배열 떨쳐 버리게되었는지 여부.

675
00:55:21,730 --> 00:55:24,320
이러한 두 가지 경우입니다.

676
00:55:24,320 --> 00:55:30,920
우리는 또한 왼쪽 것은 옳은 일 미만 여부의 사소한 경우 필요합니다.

677
00:55:30,920 --> 00:55:33,910
그럼 우리가 왼쪽 일을 선택해주세요.

678
00:55:33,910 --> 00:55:37,630
사람들은 경우입니다.

679
00:55:37,630 --> 00:55:40,990
여기가했다, 그렇지 있다는 있도록.

680
00:55:40,990 --> 00:55:46,760
배열을 떠났다. 이 1, 2, 3입니다. 좋아요. 응, 그것들은 우리가 어떻게 할 수도 네 가지입니다.

681
00:55:50,350 --> 00:55:54,510
그리고 우리는이 솔루션을 반복적으로 이동하지 않습니다.

682
00:55:54,510 --> 00:55:55,980
나는 권장하지 않습니다 -

683
00:55:55,980 --> 00:56:03,070
병합 정렬은 재귀 모두 꼬리가 아닌 함수의 예입니다

684
00:56:03,070 --> 00:56:07,040
어서, 어서 꼬리가 재귀 수 있도록 쉬운 일이 아니지

685
00:56:07,040 --> 00:56:13,450
뿐만 아니라 그것이 반복하게하는 것은 매우 쉬운 일이 아닙니다.

686
00:56:13,450 --> 00:56:16,910
이 매우 간단합니다.

687
00:56:16,910 --> 00:56:19,170
병합 정렬의 구현

688
00:56:19,170 --> 00:56:22,140
당신이 무슨 짓을하든를 병합하지, 당신은 병합을 구축거야.

689
00:56:22,140 --> 00:56:29,170
>> 따라서 병합의 상단에 내장 정렬 재귀 적으로 단지이 세 행이다 병합합니다.

690
00:56:29,170 --> 00:56:34,700
반복적으로, 그것은 생각이 더 짜증나는 더 어렵습니다.

691
00:56:34,700 --> 00:56:41,860
하지만 mergeSortHelp부터 재귀 꼬리 아니라는 것을 - 그 자체가 전화했을 때 -

692
00:56:41,860 --> 00:56:46,590
그것은 여전히​​이 재귀 호출 반환 후 일을해야합니다.

693
00:56:46,590 --> 00:56:50,830
그래서 스택 프레임도이를 호출 한 후 계속 존재해야합니다.

694
00:56:50,830 --> 00:56:54,170
그리고이 작업을 호출 할 때, 스택 프레임이 존재 계속해야합니다

695
00:56:54,170 --> 00:56:57,780
심지어 전화 후, 우리는 여전히 병합 할 필요가 때문입니다.

696
00:56:57,780 --> 00:57:01,920
그리고이 꼬리 재귀 수 있도록 nontrivial입니다.

697
00:57:04,070 --> 00:57:06,270
질문이 있으십니까?

698
00:57:08,300 --> 00:57:09,860
괜찮아요.

699
00:57:09,860 --> 00:57:13,400
따라서 정렬 돌아 간다 - 아, 제가 보여 드리고 싶은 두 가지가 있습니다. 좋아요.

700
00:57:13,400 --> 00:57:17,840
정렬로 돌아 간다, 우리는 신속하게이 작업을 수행합니다.

701
00:57:17,840 --> 00:57:21,030
또는 검색 할 수 있습니다. 정렬? 정렬. 그래.

702
00:57:21,030 --> 00:57:22,730
종류의 시작으로 돌아 간다.

703
00:57:22,730 --> 00:57:29,870
우리는 어떤 알고리즘을 사용하여 해당 종류의 배열 알고리즘을 만들려면

704
00:57:29,870 --> 00:57:33,660
n의 O 인치

705
00:57:33,660 --> 00:57:40,860
그럼이 가능합니까? 누구든지 어떤 종류가 있습니까 -

706
00:57:40,860 --> 00:57:44,300
언니가 전에 암시 -

707
00:57:44,300 --> 00:57:48,300
우리는 N 로그 N에서 N의 O하도록 지속적으로에 대한 경우는,

708
00:57:48,300 --> 00:57:51,450
우리는 우리의 알고리즘 시간 현명를 향상

709
00:57:51,450 --> 00:57:55,250
이는 우리가를 만회하기 위해 수행해야 할 일가는거야? 의미

710
00:57:55,250 --> 00:57:59,520
[학생] 공간. >> 그래. 우리는 더 많은 공간을 사용하려고하고 있습니다.

711
00:57:59,520 --> 00:58:04,490
아니라 그저 더 많은 공간, 그것은 기하 급수적으로 더 많은 공간입니다.

712
00:58:04,490 --> 00:58:14,320
그래서 알고리즘이 유형의 의사 무언가, 의사의 polynom 생각 -

713
00:58:14,320 --> 00:58:18,980
유사 - 내가 기억 할 수 없습니다. 의사 무언가.

714
00:58:18,980 --> 00:58:22,210
우리는 많은 공간을 사용할 필요하기 때문에 그건

715
00:58:22,210 --> 00:58:28,610
이 달성하지만, 현실적인 아닌지 확인하십시오.

716
00:58:28,610 --> 00:58:31,220
>> 그리고 어떻게 우리는이를 어떻게해야합니까?

717
00:58:31,220 --> 00:58:36,810
우리가 보장 할 경우이를 달성 할 수있는 배열의 특정 요소

718
00:58:36,810 --> 00:58:39,600
아래의 특정 크기입니다.

719
00:58:42,070 --> 00:58:44,500
그래서, 단지 크기가 200입니다 가정하자

720
00:58:44,500 --> 00:58:48,130
배열의 모든 요소는 다음과 크기가 200 개입니다.

721
00:58:48,130 --> 00:58:51,080
그리고이 사실은 매우 현실적인입니다.

722
00:58:51,080 --> 00:58:58,660
당신은 매우 쉽게 당신이 수있는 모든 것을 다 알고있는 배열을 할 수 있습니다

723
00:58:58,660 --> 00:59:00,570
어떤 수보다 적은 될 것입니다.

724
00:59:00,570 --> 00:59:07,400
당신이 절대적으로 거대한 벡터 또는 무언가가있는 경우 같은

725
00:59:07,400 --> 00:59:11,810
하지만 모든 0과 5 사이가 될거야 알고

726
00:59:11,810 --> 00:59:14,790
다음은이 일을 할 속도가 매우 빠르고거야.

727
00:59:14,790 --> 00:59:17,930
그리고 요소에 관한 바운드는 5

728
00:59:17,930 --> 00:59:21,980
이 바인딩 있도록 당신이 사용 거예요 얼마나 많은 메모리입니다.

729
00:59:21,980 --> 00:59:26,300
따라서 바운드는 200 개입니다.

730
00:59:26,300 --> 00:59:32,960
정수는 최대 4 억이 될 수 있기 때문에 이론적으로는 바인딩은 항상있다

731
00:59:32,960 --> 00:59:40,600
하지만 그때 우리는 공간을 사용하려는 때문에 비현실적이야

732
00:59:40,600 --> 00:59:44,400
4000000000의 순서 있습니다. 그래서 그게 비현실적이야.

733
00:59:44,400 --> 00:59:47,060
하지만 여기 우리가 바운드 말하지는 200 개입니다.

734
00:59:47,060 --> 00:59:59,570
n의 O에 일에 그 트릭은 우리가 크기의 기준은 준수라는 또 다른 배열을 것입니다.

735
00:59:59,570 --> 01:00:10,470
그래서 사실,이에 대한 바로 가기입니다 - 꽝이 짓을한다면 잘 모르겠어요.

736
01:00:11,150 --> 01:00:15,330
그러나 최소한 GCC에 - 난 가정 꽝도 그렇지 -

737
01:00:15,330 --> 01:00:18,180
이 단지 0s로 전체 배열을 초기화합니다.

738
01:00:18,180 --> 01:00:25,320
그 작업을 수행하지 않으려면 그럼, 제가 별도로 할 수있는 (INT I = 0;

739
01:00:25,320 --> 01:00:31,500
내가 <BOUND, 나는 + +)와 카운트 [I] = 0;

740
01:00:31,500 --> 01:00:35,260
이제 모든 것은 0으로 초기화됩니다.

741
01:00:35,260 --> 01:00:39,570
나는 내 배열을 통해 반복

742
01:00:39,570 --> 01:00:51,920
그리고 내가하고있는 건 각의 수를 계산하려고하는데 - 여기 가서하​​자.

743
01:00:51,920 --> 01:00:55,480
우리는 4, 15, 16, 50, 8, 23, 42, 108이 있습니다.

744
01:00:55,480 --> 01:01:00,010
내가 계산하는거야 요소 각각의 사건의 번호입니다.

745
01:01:00,010 --> 01:01:03,470
의 실제로 어떤 반복과 여기에 몇 가지 더 추가 할 수 있습니다.

746
01:01:03,470 --> 01:01:11,070
우리가 여기에있는 값이 그래서,의 값은 [I] 배열 될 것입니다.

747
01:01:11,070 --> 01:01:14,850
그래서 발은 4 또는 8 또는 무엇이든 다 될 수 있습니다.

748
01:01:14,850 --> 01:01:18,870
그리고 지금은 내가 본 적이 얼마나 많은 그 가치를 믿고있어

749
01:01:18,870 --> 01:01:21,230
카운트 있도록 [발] + +;

750
01:01:21,230 --> 01:01:29,430
이 작업을 수행 한 후 카운트는 0001과 같이 예정이다.

751
01:01:29,430 --> 01:01:42,190
카운트를하자 [발] - + 1 준수.

752
01:01:42,190 --> 01:01:48,230
>> 지금 우리가 0에서 시작하는 사실에 대해 설명 할 뿐이에요.

753
01:01:48,230 --> 01:01:50,850
그래서, 만약 200, 가장 큰 숫자가 될거야

754
01:01:50,850 --> 01:01:54,720
그리고 0-200은 201 일입니다.

755
01:01:54,720 --> 01:02:01,540
우리가 한 4 때문에 중요 그래서, 00001처럼 보이게됩니다.

756
01:02:01,540 --> 01:02:10,210
그럼 우리가 수의 8 색인에서 1을해야 0001이됩니다.

757
01:02:10,210 --> 01:02:14,560
우리는 수의 23 색인에서 2해야합니다.

758
01:02:14,560 --> 01:02:17,630
우리는 수의 42 색인에 2해야합니다.

759
01:02:17,630 --> 01:02:21,670
그래서 우리는 수를 사용할 수 있습니다.

760
01:02:34,270 --> 01:02:44,920
따라서 num_of_item = 카운트 [I].

761
01:02:44,920 --> 01:02:52,540
그리고 num_of_item는 2 있다면, 우리는 수 세의 2를 삽입 할을 의미합니다

762
01:02:52,540 --> 01:02:55,290
우리의 정렬 배열에.

763
01:02:55,290 --> 01:03:02,000
그래서 우리는 우리가 배열로 얼마나 멀리를 추적해야합니다.

764
01:03:02,000 --> 01:03:05,470
따라서 인덱스 = 0.

765
01:03:05,470 --> 01:03:09,910
배열 - 그냥 쓰기됩니다.

766
01:03:16,660 --> 01:03:18,020
개수 -

767
01:03:19,990 --> 01:03:28,580
배열 [인덱스 + +] = 난;

768
01:03:28,580 --> 01:03:32,490
내가 원하는거야? 그게 제가 원하는 것 같아요.

769
01:03:35,100 --> 01:03:38,290
네, 좋은 보입니다. 좋아요.

770
01:03:38,290 --> 01:03:43,050
그래서 모두가 내 카운트 배열의 목적은 무엇 알 겠죠?

771
01:03:43,050 --> 01:03:48,140
이 숫자 각각의 사건의 수를 계산합니다.

772
01:03:48,140 --> 01:03:51,780
그리고, 그 계산 배열을 통해 반복 있어요

773
01:03:51,780 --> 01:03:57,190
그리고 카운트 배열의 i 번째 위치

774
01:03:57,190 --> 01:04:01,930
내 정렬 배열에 나타납니다 나도 그게 횟수입니다.

775
01:04:01,930 --> 01:04:06,840
4 건의 1이 될 것입니다 이유

776
01:04:06,840 --> 01:04:11,840
8 건의 1이 될 것입니다, 23 건의는 2가 될 것입니다.

777
01:04:11,840 --> 01:04:16,900
그래서 내 정렬 배열에 삽입하는 방법을 그들에게 많은입니다.

778
01:04:16,900 --> 01:04:19,200
그럼 난 그냥 그렇게 해요.

779
01:04:19,200 --> 01:04:28,960
내 정렬 배열에 빠져 num_of_item를 삽입하고 있습니다.

780
01:04:28,960 --> 01:04:31,670
>> 질문이 있으십니까?

781
01:04:32,460 --> 01:04:43,100
우리가 한번 이상 반복되어 있기 때문에 그리고 다시,이 선형 시간

782
01:04:43,100 --> 01:04:47,470
하지만,이 번호로 어떻게 또한 선형입니다

783
01:04:47,470 --> 01:04:50,730
그래서이 많이 귀하의 바인딩이 무엇인지에 따라 달라집니다.

784
01:04:50,730 --> 01:04:53,290
200 바인딩으로, 그 그렇게 나쁘지 않아.

785
01:04:53,290 --> 01:04:58,330
당신의 바운드 10,000 될거 경우, 그건 좀 더 나쁜

786
01:04:58,330 --> 01:05:01,360
당신의 바운드가 4,000,000,000 될 것입니다 경우하지만 완전히 비현실적이야

787
01:05:01,360 --> 01:05:07,720
이 배열은 비현실적인 is 크기 4000000000,의되어야 할 것이다.

788
01:05:07,720 --> 01:05:10,860
그래서 그런 걸. 질문이 있으십니까?

789
01:05:10,860 --> 01:05:13,270
[안 들리게 학생 응답] >> 좋아요.

790
01:05:13,270 --> 01:05:15,710
우리가 겪고있을 때 나는 다른 일을 깨달았습니다.

791
01:05:17,980 --> 01:05:23,720
나는 문제가 루카스의 아마도 우리가 본 모든 하나 하나의 생각.

792
01:05:23,720 --> 01:05:26,330
나는 완전히 잊어 버렸습니다.

793
01:05:26,330 --> 01:05:31,040
제가 댓글 싶어있는 유일한 방법은 당신이 인덱스 같은 것을 다루는 때

794
01:05:31,040 --> 01:05:38,320
당신은 루프에 대해를 쓸 때 당신은 정말이 표시되지 않을

795
01:05:38,320 --> 01:05:41,120
하지만 기술적으로, 때마다,이 인덱스를 다루고 있습니다

796
01:05:41,120 --> 01:05:45,950
당신은 거의 항상 부호없는 (unsigned) 정수 처리해야합니다.

797
01:05:45,950 --> 01:05:53,850
당신이 서명 정수 처리 할 때 그 이유는,

798
01:05:53,850 --> 01:05:56,090
당신은이 서명 정수가 있고 당신이 그들을 함께 추가 있도록하는 경우

799
01:05:56,090 --> 01:06:00,640
그리고 그 사람들도 큰를 종료 한 다음은 음수로 결국.

800
01:06:00,640 --> 01:06:03,410
그래서 그런 정수 오버 플로우가 무엇입니다.

801
01:06:03,410 --> 01:06:10,500
>> 난 2 억 10 억 추가하면, 나는 부정적인 1000000000이 생깁니다.

802
01:06:10,500 --> 01:06:15,480
그 정수는 컴퓨터에서 작동 방법은 다음과 같습니다.

803
01:06:15,480 --> 01:06:17,510
사용의 문제는 그래서 -

804
01:06:17,510 --> 01:06:23,500
즉, 낮은은 2,000,000,000 일 경우를 제외하고 괜찮아, 최대 1,000,000,000 할 일

805
01:06:23,500 --> 01:06:27,120
그리고이 1,000,000,000 음수가 될 것입니다, 그리고 나서 우리는 나눌 것이다 그 둘의

806
01:06:27,120 --> 01:06:29,730
및 제외 500,000,000이 생깁니다.

807
01:06:29,730 --> 01:06:33,760
그래서이 집이 당신이 배열을 통해 검색 할 일 경우에만 문제

808
01:06:33,760 --> 01:06:38,070
일들이 있습니다.

809
01:06:38,070 --> 01:06:44,050
낮은 +가 오버 플로우에게 무슨 일이 생긴다면, 그럼 그게 문제입니다.

810
01:06:44,050 --> 01:06:47,750
즉시 우리가 그들을 서명하기로 한 후 2,000,000,000 1,000,000,000 플러스는 3 억.

811
01:06:47,750 --> 01:06:51,960
2로 나누어 3000000000는 1.5 억.

812
01:06:51,960 --> 01:06:55,670
그들은 서명되지 않은 너무 자마자, 모든 완벽한 곳입니다.

813
01:06:55,670 --> 01:06:59,900
당신은 루프에 대해를 쓸 때 그리고 그렇게도 문제입니다

814
01:06:59,900 --> 01:07:03,940
실제로, 아마 자동으로 수행합니다.

815
01:07:09,130 --> 01:07:12,330
사실은 당신을 소리 것입니다.

816
01:07:12,330 --> 01:07:21,610
이 숫자는 단지 정수에 너무 큰이지만, 경우에 따라서는 부호없는 정수에 적응

817
01:07:21,610 --> 01:07:24,970
당신 지르지되며, 당신이 정말로 문제로 실행하지 못한 이유 인 것.

818
01:07:29,150 --> 01:07:34,820
당신이 지수는 음수가 될 수 없다는 것을 볼 수 있습니다

819
01:07:34,820 --> 01:07:39,220
그리고 당신은 배열을 통해 반복 할 때

820
01:07:39,220 --> 01:07:43,970
당신은 거의 항상 INT 부호 말할 수 있지만, 당신은 정말 필요 없어요.

821
01:07:43,970 --> 01:07:47,110
물건은 그냥뿐만 아니라 거의 작동 할 수 있습니다.

822
01:07:48,740 --> 01:07:50,090
좋아요. [속삭임] 지금이 몇시입니까?

823
01:07:50,090 --> 01:07:54,020
그냥 난 정말 빠르게 해줄 게 - 나는 보여주고 싶었다 마지막으로.

824
01:07:54,020 --> 01:08:03,190
당신은 우리가 # 5 같은 걸로 MAX를 정의 할 수 있도록 우리가 # 정의했는지 알아?

825
01:08:03,190 --> 01:08:05,940
MAX하지 보자. # 200 준수 정의합니다. 그건 우리가 전에했던 일이야.

826
01:08:05,940 --> 01:08:10,380
그냥 복사 붙여 넣기를 할 것이다 상수를 정의 그

827
01:08:10,380 --> 01:08:13,010
우리는 구속 작성하는 일마다.

828
01:08:13,010 --> 01:08:18,189
>> 그래서 우리는 실제로 # 정의로 더 많은 작업을 수행 할 수 있습니다.

829
01:08:18,189 --> 01:08:21,170
우리는 # 기능을 정의 할 수 있습니다.

830
01:08:21,170 --> 01:08:23,410
그들은 정말 기능 아니지만 우리가 함수를 호출합니다.

831
01:08:23,410 --> 01:08:36,000
예 MAX (X, Y) 같은 것하는 것은 (? : X X <Y Y)로 정의됩니다. 좋아요.

832
01:08:36,000 --> 01:08:40,660
그럼 당신은 3 원 연산자 구문에 익숙해 져야만

833
01:08:40,660 --> 01:08:49,029
하지만 x는 Y보다 작습니다? y를 돌아 다른 x를 반환합니다.

834
01:08:49,029 --> 01:08:54,390
그래서,이 별도의 기능을 할 수 있습니다 볼 수 있습니다

835
01:08:54,390 --> 01:09:01,399
BOOL MAX 2 인수를 같이하고 기능이 될 수이를 반환합니다.

836
01:09:01,399 --> 01:09:08,340
이 같은 짓을 내가 볼 가장 일반적인 것들 중 하나입니다. 우리는 그들을 매크로 전화하십시오.

837
01:09:08,340 --> 01:09:11,790
이 매크로입니다.

838
01:09:11,790 --> 01:09:15,859
이 단지의 구문입​​니다.

839
01:09:15,859 --> 01:09:18,740
당신이 원하는 건 뭐든지 할 수 매크로를 쓸 수 있습니다.

840
01:09:18,740 --> 01:09:22,649
당신은 자주 printfs 물건을 디버깅 매크로를 참조하십시오.

841
01:09:22,649 --> 01:09:29,410
printf의 일종 그래서, 밑줄 LINE을 강조처럼 C에 특별한 상수가 있습니다

842
01:09:29,410 --> 01:09:31,710
2, LINE 밑줄 밑줄

843
01:09:31,710 --> 01:09:37,550
내가 2 FUNC 밑줄 생각도 있습니다. 그게 수 있습니다. 그런 것 같아.

844
01:09:37,550 --> 01:09:40,880
이러한 일들은 함수의 이름으로 대체됩니다

845
01:09:40,880 --> 01:09:42,930
또는 중이 줄의 번호입니다.

846
01:09:42,930 --> 01:09:48,630
자주, 당신은 여기 그때 그냥 쓸 수있는 디버깅 printfs를 작성

847
01:09:48,630 --> 01:09:54,260
디버깅 그리고 줄 번호와 I가 할 일을 겪게 기능을 출력합니다

848
01:09:54,260 --> 01:09:57,020
그렇게 DEBUG 문을 발생하는.

849
01:09:57,020 --> 01:09:59,550
그리고 당신은 다른 일을 인쇄 할 수 있습니다.

850
01:09:59,550 --> 01:10:05,990
따라서 해보세요해야 하나 내가 # DOUBLE_MAX을 정의하는 일 경우입니다

851
01:10:05,990 --> 01:10:11,380
2 * y 및 2와 같은 무엇인가로 * X.

852
01:10:11,380 --> 01:10:14,310
그럼 어떤 이유를 들어, 당신은 많은 것을 할 수있어.

853
01:10:14,310 --> 01:10:16,650
따라서 매크로합니다.

854
01:10:16,650 --> 01:10:18,680
이것은 실제로 고장 났어요.

855
01:10:18,680 --> 01:10:23,050
나는 DOUBLE_MAX (3, 6)과 같은 짓을하여 전화를합니다.

856
01:10:23,050 --> 01:10:27,530
그럼 무엇을 반환해야 하는가?

857
01:10:28,840 --> 01:10:30,580
[학생] 12.

858
01:10:30,580 --> 01:10:34,800
예, 12 반환해야 12이 반환됩니다.

859
01:10:34,800 --> 01:10:43,350
3 x는 대체됩니다, 6 Y에 대한 대체, 우리는 12 2 * 6, 반환됩니다.

860
01:10:43,350 --> 01:10:47,710
지금 이건 어때? 무엇을 반환해야 하는가?

861
01:10:47,710 --> 01:10:50,330
[학생] 14. >> 이상적으로, 14.

862
01:10:50,330 --> 01:10:55,290
문제는 작업을 정의하는 방법 해시는 문자 복사 및 붙여 넣기 일을 기억이다

863
01:10:55,290 --> 01:11:00,160
거의 모든 걸, 그래서 어떤이로 해석 될 것입니다

864
01:11:00,160 --> 01:11:11,270
1 + 6, 2 번 1 + 6, 2 회 3보다 3 이내의 거리에 있습니다.

865
01:11:11,270 --> 01:11:19,780
>> 따라서 이런 이유로 당신은 거의 항상 괄호 안에 모든 것을 감싸.

866
01:11:22,180 --> 01:11:25,050
당신은 거의 항상 괄호 안에 감싸 모든 변수.

867
01:11:25,050 --> 01:11:29,570
내가 여기를 수행 할 필요가 없습니다되는 것처럼 당신은 필요 없어 경우도있다

868
01:11:29,570 --> 01:11:32,110
미만이기 때문에 거의 언제나 일 것,

869
01:11:32,110 --> 01:11:34,330
비록 그게 그 사실이 아닐 수도 있습니다.

870
01:11:34,330 --> 01:11:41,870
DOUBLE_MAX (1 == 2)과 같은 터무니없는 일이있을 경우,

871
01:11:41,870 --> 01:11:49,760
3 다음 미만으로 대체 당할 것이다 즉, 2 동일 동일

872
01:11:49,760 --> 01:11:53,460
그리고 나서, 그 같은 2, 1보다 3 이하 할 않는거야

873
01:11:53,460 --> 01:11:55,620
이는 우리가 원하는하지 않습니다.

874
01:11:55,620 --> 01:12:00,730
따라서 모든 연산자 우선 순위 문제를 방지하기 위해,

875
01:12:00,730 --> 01:12:02,870
항상 괄호 안에 넣어.

876
01:12:03,290 --> 01:12:07,700
좋아요. 그리고 그은 5 시반 거예요.

877
01:12:08,140 --> 01:12:12,470
당신이 pset에 대한 질문이 있으면 저희에게 알려주십시오.

878
01:12:12,470 --> 01:12:18,010
재미있을 것, 그리고 해커 버전은 훨씬 더 현실적인입니다

879
01:12:18,010 --> 01:12:22,980
작년의 해커 판보다, 그래서 우리는 당신의 많은 해보 바랍니다.

880
01:12:22,980 --> 01:12:26,460
작년은 매우 압도적이었다.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]