1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] 당신은 아마 사람들이 빠르게 효율적인 알고리즘에 대해하는 말을 들었지

2
00:00:10,950 --> 00:00:13,090
특정 작업을 실행하기 위해,

3
00:00:13,090 --> 00:00:16,110
하지만 빠르게 효율적으로 할 수있는 알고리즘에 대해 정확히 무엇을 의미합니까?

4
00:00:16,110 --> 00:00:18,580
음, 실시간 측정에 대해 얘기 안

5
00:00:18,580 --> 00:00:20,500
초 또는 분처럼.

6
00:00:20,500 --> 00:00:22,220
이 때문 컴퓨터 하드웨어

7
00:00:22,220 --> 00:00:24,260
및 소프트웨어 크게 다릅니다.

8
00:00:24,260 --> 00:00:26,020
내 프로그램은, 당신보다 느리게 실행 할 수

9
00:00:26,020 --> 00:00:28,000
나는 이전 컴퓨터에서 파일을 실행 중이니까

10
00:00:28,000 --> 00:00:30,110
아니면 온라인 비디오 게임을 재생 할 일 because

11
00:00:30,110 --> 00:00:32,670
동시에, 즉 모든 기억을 나도보고있다

12
00:00:32,670 --> 00:00:35,400
아니면 다른 소프트웨어를 통해 내 프로그램을 실행 될 수 있습니다

13
00:00:35,400 --> 00:00:37,550
이는 낮은 수준에서 다른 컴퓨터와 통신합니다.

14
00:00:37,550 --> 00:00:39,650
그것은 사과와 오렌지를 비교하는 것입니다.

15
00:00:39,650 --> 00:00:41,940
내 느린 컴퓨터가 오래 걸립니다해서

16
00:00:41,940 --> 00:00:43,410
당신의 대답을 돌려 줄보다

17
00:00:43,410 --> 00:00:45,510
당신은보다 효율적인 알고리즘을 의미하지는 않습니다.

18
00:00:45,510 --> 00:00:48,830
>> 그래서, 우리는 우리가 직접 프로그램의 런타임을 비교 할 수 없으므로

19
00:00:48,830 --> 00:00:50,140
초 또는 분,

20
00:00:50,140 --> 00:00:52,310
우리가 어떻게 2 개의 다른 알고리즘을 비교합니까

21
00:00:52,310 --> 00:00:55,030
에 관계없이 하드웨어 또는 소프트웨어 환경의?

22
00:00:55,030 --> 00:00:58,000
알고리즘 효율성을 측정하는보다 균일 한 방법을 만들려면,

23
00:00:58,000 --> 00:01:00,360
컴퓨터 과학자와 수학자 고안 한

24
00:01:00,360 --> 00:01:03,830
프로그램의 점근 복잡도를 측정하기위한 개념

25
00:01:03,830 --> 00:01:06,110
그리고 표기법은 '빅 Ohnotation'이라는

26
00:01:06,110 --> 00:01:08,320
이 기술하십시오.

27
00:01:08,320 --> 00:01:10,820
공식적인 정의는 그 함수 F (x)를

28
00:01:10,820 --> 00:01:13,390
g의 순서 (X)에서 실행

29
00:01:13,390 --> 00:01:15,140
일부 (X) 값이 존재하는 경우, X ₀ 및

30
00:01:15,140 --> 00:01:17,630
일부 상수, C, 어떤 용도로

31
00:01:17,630 --> 00:01:19,340
F (X)는보다 작거나 같다

32
00:01:19,340 --> 00:01:21,230
그 일정한 시간 g (x)를

33
00:01:21,230 --> 00:01:23,190
X ₀보다 큰 모든 X 용.

34
00:01:23,190 --> 00:01:25,290
>> 그러나 공식적인 정의에 의해 거리에 두려워하지 않습니다.

35
00:01:25,290 --> 00:01:28,020
이 사실은 이론적 인 측면 안에 무엇을 의미합니까?

36
00:01:28,020 --> 00:01:30,580
음, 기본적 분석 방법

37
00:01:30,580 --> 00:01:33,580
프로그램의 실행은 점근 적 성장 얼마나 빠르게.

38
00:01:33,580 --> 00:01:37,170
귀하의 입력의 크기가 무한대으로 증가함에입니다

39
00:01:37,170 --> 00:01:41,390
말하자면, 크기 10의 배열에 비해 크기가 1000 배열을 정렬하고 있습니다.

40
00:01:41,390 --> 00:01:44,950
프로그램의 실행은 어떻게 성장합니까?

41
00:01:44,950 --> 00:01:47,390
예를 들어, 문자의 수를 계산 상상

42
00:01:47,390 --> 00:01:49,350
문자열의 간단한 방법

43
00:01:49,350 --> 00:01:51,620
 전체 문자열을 통해 도보

44
00:01:51,620 --> 00:01:54,790
문자 별 문자와 각 문자에 대한 카운터를 1 추가.

45
00:01:55,700 --> 00:01:58,420
이 알고리즘은 선형 시간에 실행이라고합니다

46
00:01:58,420 --> 00:02:00,460
문자의 수에 관하여,

47
00:02:00,460 --> 00:02:02,670
문자열에 'N'.

48
00:02:02,670 --> 00:02:04,910
즉,이 O (n)이에서 실행됩니다.

49
00:02:05,570 --> 00:02:07,290
왜인가요?

50
00:02:07,290 --> 00:02:09,539
음,이 방법을 사용하여 시간이 필요합니다

51
00:02:09,539 --> 00:02:11,300
전체 문자열을 통과하는

52
00:02:11,300 --> 00:02:13,920
문자의 수에 비례합니다.

53
00:02:13,920 --> 00:02:16,480
20 문자열의 문자 수를 계산

54
00:02:16,480 --> 00:02:18,580
진실이 밝혀 질 때 두 배 정도 걸릴 것입니다

55
00:02:18,580 --> 00:02:20,330
10 문자열의 문자 수를 계산하려면,

56
00:02:20,330 --> 00:02:23,000
당신은 모든 문자를보고 있기 때문에

57
00:02:23,000 --> 00:02:25,740
각 문자는 ... 같은 시간이 걸립니다.

58
00:02:25,740 --> 00:02:28,050
당신은 문자의 수를 증가에 따라

59
00:02:28,050 --> 00:02:30,950
런타임는 입력 길이로 선형 증가 할 것이다.

60
00:02:30,950 --> 00:02:33,500
>> 그 선형 시간을 결정 없다면, 상상

61
00:02:33,500 --> 00:02:36,390
O (n)이, 그냥 충분히 빨리 당신 아니 었나요?

62
00:02:36,390 --> 00:02:38,750
아마 당신은 큰 문자열을 저장하는

63
00:02:38,750 --> 00:02:40,450
와 당신이 걸릴 것입니다 추가 시간이 없소

64
00:02:40,450 --> 00:02:44,000
하나씩 계산의 문자를 모두 통과합니다.

65
00:02:44,000 --> 00:02:46,650
그래서 다른 일을 시도하기로 결정했습니다.

66
00:02:46,650 --> 00:02:49,270
당신은 이미 문자의 수를 저장하기 위해 무슨 일이 일어날 경우

67
00:02:49,270 --> 00:02:52,690
문자열에 ', 렌'라는 변수에, 말

68
00:02:52,690 --> 00:02:54,210
초기 프로그램에,

69
00:02:54,210 --> 00:02:57,800
당신은 심지어 문자열의 첫 문자를 저장하기 전에?

70
00:02:57,800 --> 00:02:59,980
그런 다음, 모든 당신은 문자열 길이를 알아 지금해야 할

71
00:02:59,980 --> 00:03:02,570
변수의 값이 무엇인지 확인합니다.

72
00:03:02,570 --> 00:03:05,530
당신은 전혀 문자열 자체를 볼 필요가 없습니다 것입니다

73
00:03:05,530 --> 00:03:08,160
와 렌 같은 변수 값을 액세스하는 것으로 간주됩니다

74
00:03:08,160 --> 00:03:11,100
점근 일정한 시간 운영,

75
00:03:11,100 --> 00:03:13,070
또는 O (1).

76
00:03:13,070 --> 00:03:17,110
왜인가요? 음, 점근 복잡도가 무슨 뜻인지 기억 해요.

77
00:03:17,110 --> 00:03:19,100
어떻게 크기와 같은 런타임 변화는 않습니다

78
00:03:19,100 --> 00:03:21,400
의 입력은 성장?

79
00:03:21,400 --> 00:03:24,630
>> 당신은 더 큰 문자열의 문자 수를 얻으려고 했어요.

80
00:03:24,630 --> 00:03:26,960
글쎄, 당신은 문자열을 만드는 방법 큰 문제가되지 않을

81
00:03:26,960 --> 00:03:28,690
심지어 만 자,

82
00:03:28,690 --> 00:03:31,150
모든 당신은이 방법으로 문자열의 길이를 찾기 위해해야​​ 할

83
00:03:31,150 --> 00:03:33,790
, 변수 렌의 값을 읽을 것입니다

84
00:03:33,790 --> 00:03:35,440
어떤 당신은 이미했습니다.

85
00:03:35,440 --> 00:03:38,200
인 입력의 길이, 당신이 찾아내는하려는 문자열의 길이,

86
00:03:38,200 --> 00:03:41,510
프로그램이 실행 얼마나 빠르게 전혀 영향을 미치지 않습니다.

87
00:03:41,510 --> 00:03:44,550
프로그램의이 부분은 한 문자열에서 동등하게 빠른 실행

88
00:03:44,550 --> 00:03:46,170
과 천 문자열,

89
00:03:46,170 --> 00:03:49,140
이 프로그램은 일정한 시간에 실행로 지칭 될 이유 죠

90
00:03:49,140 --> 00:03:51,520
입력 크기와 관련하여.

91
00:03:51,520 --> 00:03:53,920
>> 물론, 단점이 있어요.

92
00:03:53,920 --> 00:03:55,710
당신은 당신의 컴퓨터에 추가 메모리 공간을 지출

93
00:03:55,710 --> 00:03:57,380
변수를 저장

94
00:03:57,380 --> 00:03:59,270
하고 나타납니다 여분의 시간

95
00:03:59,270 --> 00:04:01,490
변수의 실제 저장을하려면,

96
00:04:01,490 --> 00:04:03,390
그러나 요점은 여전히​​ 유효,

97
00:04:03,390 --> 00:04:05,060
귀하의 문자열이 얼마나 있었는지 알아내는

98
00:04:05,060 --> 00:04:07,600
전혀 문자열의 길이에 의존하지 않습니다.

99
00:04:07,600 --> 00:04:10,720
그래서, O (1) 또는 일정한 시간에 실행됩니다.

100
00:04:10,720 --> 00:04:13,070
이건 정말 의미가 없습니다

101
00:04:13,070 --> 00:04:15,610
당신의 코드는, 1 단계에서 실행

102
00:04:15,610 --> 00:04:17,470
하지만 아무리 많은 단계가 있으며,

103
00:04:17,470 --> 00:04:20,019
이 입력의 크기가 변경되지 않는 경우는,

104
00:04:20,019 --> 00:04:23,420
그것은 여전히​​ 우리가 O (1)으로 대표되는 점근 적 상수입니다.

105
00:04:23,420 --> 00:04:25,120
>> 당신은 아마 추측 수 있듯이,

106
00:04:25,120 --> 00:04:27,940
로 알고리즘을 측정하는 방법에는 여러 큰 O 런타임이 있습니다.

107
00:04:27,940 --> 00:04:32,980
O (N) ² 알고리즘은 O (n)이 알고리즘보다 점근 느린 있습니다.

108
00:04:32,980 --> 00:04:35,910
요소의 수 (N)가 증가함에입니다

109
00:04:35,910 --> 00:04:39,280
결국 O (n)이 ² 알고리즘은 많은 시간이 걸릴 것입니다

110
00:04:39,280 --> 00:04:41,000
O (n)이 알고리즘은 실행보다.

111
00:04:41,000 --> 00:04:43,960
이 O (n)이 알고리즘은 항상 빠르게 실행 뜻은 아닙니다

112
00:04:43,960 --> 00:04:46,410
O (N) ² 알고리즘보다, 심지어 같은 환경에서,

113
00:04:46,410 --> 00:04:48,080
동일한 하드웨어에서.

114
00:04:48,080 --> 00:04:50,180
어쩌면 작은 입력 크기,

115
00:04:50,180 --> 00:04:52,900
 O (n)이 ² 알고리즘은 실제로 빠르게 작동 할 수

116
00:04:52,900 --> 00:04:55,450
그러나, 결국, 입력 크기로 증가

117
00:04:55,450 --> 00:04:58,760
무한대에 대한, O (n)이 ² 알고리즘의 런타임

118
00:04:58,760 --> 00:05:02,000
결국 O (n)이 알고리즘의 실행을 일식 것입니다.

119
00:05:02,000 --> 00:05:04,230
그냥 어떤 이차 수학 함수와 같은

120
00:05:04,230 --> 00:05:06,510
 결국 모든 선형 기능을 추월되며​​,

121
00:05:06,510 --> 00:05:09,200
얼마나 머리가 선형 함수를 시작하든를 시작합니다 없습니다.

122
00:05:10,010 --> 00:05:12,000
당신은 대량의 데이터를 다룰 경우

123
00:05:12,000 --> 00:05:15,510
O에서 실행 알고리즘 (n)이 ² 시간은 정말 프로그램을 속도가 느려지 들어갑니다

124
00:05:15,510 --> 00:05:17,770
하지만 작은 입력 크기,

125
00:05:17,770 --> 00:05:19,420
당신은 아마 발견도하지 않습니다.

126
00:05:19,420 --> 00:05:21,280
>> 또 다른 점근 복잡도는,

127
00:05:21,280 --> 00:05:24,420
로그 시간 O (로그 n)이.

128
00:05:24,420 --> 00:05:26,340
빨리이 실행 알고리즘의 예

129
00:05:26,340 --> 00:05:29,060
, 고전 이진 검색 알고리즘입니다

130
00:05:29,060 --> 00:05:31,850
요소의 이미 정렬 된 목록에서 요소를 찾는 데.

131
00:05:31,850 --> 00:05:33,400
>> 당신은 이진 검색 무엇을 모르는 경우

132
00:05:33,400 --> 00:05:35,170
정말 빨리 당신을 위해 설명합니다.

133
00:05:35,170 --> 00:05:37,020
자, 당신이 3 번을 찾고 말

134
00:05:37,020 --> 00:05:40,200
정수의 배열 인치

135
00:05:40,200 --> 00:05:42,140
이 배열의 중간 요소 본다

136
00:05:42,140 --> 00:05:46,830
그리고 "난 너보다 더 원하는 요소에 동일하거나보다?"부탁

137
00:05:46,830 --> 00:05:49,150
느낌이 좋은, 평등 이죠. 당신은 요소를 발견하면 완료됩니다.

138
00:05:49,150 --> 00:05:51,300
가 더이라면, 당신은 요소를 알

139
00:05:51,300 --> 00:05:53,440
, 배열의 오른쪽에 있어야이

140
00:05:53,440 --> 00:05:55,200
당신은뿐만 아니라, 미래에 그에서 볼 수

141
00:05:55,200 --> 00:05:57,690
가 작다면, 다음은 왼쪽에 있어야 알아.

142
00:05:57,690 --> 00:06:00,980
이 프로세스는 다음 작은 크기의 배열로 반복됩니다

143
00:06:00,980 --> 00:06:02,870
올바른 요소가 발견 될 때까지.

144
00:06:08,080 --> 00:06:11,670
>> 이 강력한 알고리즘은 각 작업을 반으로 배열의 크기를 잘라냅니다.

145
00:06:11,670 --> 00:06:14,080
따라서, 크기 8 정렬 배열에 요소를 찾으려면

146
00:06:14,080 --> 00:06:16,170
최대 (₂ 8 로그인)

147
00:06:16,170 --> 00:06:18,450
이러한 작업 또는 3,

148
00:06:18,450 --> 00:06:22,260
중간 요소를 확인 한 후 반으로 배열을 절단은해야합니다

149
00:06:22,260 --> 00:06:25,670
크기 16의 배열은 (₂ 16 로그인)이 소요 반면,

150
00:06:25,670 --> 00:06:27,480
또는 4 작전.

151
00:06:27,480 --> 00:06:30,570
그는 두 배 크기의 배열을위한 1 개 작업입니다.

152
00:06:30,570 --> 00:06:32,220
배열의 크기를 두 배로

153
00:06:32,220 --> 00:06:35,160
이 코드의 1 덩어리하여 런타임을 증가시킵니다.

154
00:06:35,160 --> 00:06:37,770
다시 다음 분할, 목록의 중간 요소를 확인.

155
00:06:37,770 --> 00:06:40,440
그래서,이 로그 시간에 작동하도록했다 있어요

156
00:06:40,440 --> 00:06:42,440
O (로그 n)이.

157
00:06:42,440 --> 00:06:44,270
그러나, 당신이 말하는 기다려

158
00:06:44,270 --> 00:06:47,510
목록에서 찾고있는 요소가있는 곳이에 따라 달라집니다되지 않는 이유는 무엇입니까?

159
00:06:47,510 --> 00:06:50,090
어떻게하면 당신이 볼 첫 번째 요소는 바로 사람이되고 어떻게됩니까?

160
00:06:50,090 --> 00:06:52,040
그런 다음, 단지, 1 작업을 걸립니다

161
00:06:52,040 --> 00:06:54,310
목록이 얼마나 큰 상관 없습니다.

162
00:06:54,310 --> 00:06:56,310
>> 컴퓨터 과학자들은 더 많은 검색어를하는 이유 죠

163
00:06:56,310 --> 00:06:58,770
가장 케이스를 반영 점근 복잡도에 대한

164
00:06:58,770 --> 00:07:01,050
그리고 최악의 경우 알고리즘의 공연.

165
00:07:01,050 --> 00:07:03,320
더 제대로, 상부 및 하부 경계

166
00:07:03,320 --> 00:07:05,090
런타임 있습니다.

167
00:07:05,090 --> 00:07:07,660
이진 검색을위한 가장 좋은 경우에, 우리의 요소입니다

168
00:07:07,660 --> 00:07:09,330
저기 중간에,

169
00:07:09,330 --> 00:07:11,770
그리고 당신은 일정한 시간에 이해

170
00:07:11,770 --> 00:07:14,240
배열의 나머지가 얼마나 커 상관 없습니다.

171
00:07:15,360 --> 00:07:17,650
이에 사용되는 기호는 Ω이다.

172
00:07:17,650 --> 00:07:19,930
그래서,이 알고리즘은 Ω (1)에서 실행이라고합니다.

173
00:07:19,930 --> 00:07:21,990
가장 좋은 경우는, 신속하게 요소를 찾아

174
00:07:21,990 --> 00:07:24,200
배열이 얼마나 큰 상관없이,

175
00:07:24,200 --> 00:07:26,050
하지만 최악의 경우에

176
00:07:26,050 --> 00:07:28,690
그것은 (로그 n)이 분할 검사를 수행 할 수 있습니다

177
00:07:28,690 --> 00:07:31,030
배열의 오른쪽 요소를 찾을 수 있습니다.

178
00:07:31,030 --> 00:07:34,270
최악의 상부 경계는 이미 알고있는 큰 "O"로 지칭합니다.

179
00:07:34,270 --> 00:07:38,080
그래서, O (로그 n)이 있지만, Ω (1)입니다.

180
00:07:38,080 --> 00:07:40,680
>> 선형 검색, 반대로,

181
00:07:40,680 --> 00:07:43,220
당신은 배열의 모든 요소를​​ 통과하는

182
00:07:43,220 --> 00:07:45,170
당신이 원하는 하나를 찾으려면

183
00:07:45,170 --> 00:07:47,420
가장 Ω (1)에 있습니다.

184
00:07:47,420 --> 00:07:49,430
다시, 첫 번째 요소는 당신이 원하는.

185
00:07:49,430 --> 00:07:51,930
그래서, 배열이 얼마나 큰 문제가되지 않습니다.

186
00:07:51,930 --> 00:07:54,840
최악의 경우,이 배열의 마지막 요소입니다.

187
00:07:54,840 --> 00:07:58,560
그래서, 당신은 그것을 발견 할 배열에있는 모든 N 요소를 통과해야

188
00:07:58,560 --> 00:08:02,170
당신은 3을 찾는 경우 좋아해요.

189
00:08:04,320 --> 00:08:06,030
그래서, O (n)이 시간에 실행

190
00:08:06,030 --> 00:08:09,330
이 배열의 요소의 수에 비례 때문입니다.

191
00:08:10,800 --> 00:08:12,830
>> 사용 하나 더 기호 Θ입니다.

192
00:08:12,830 --> 00:08:15,820
이것은 최고의 최악의 경우 알고리즘을 설명하는 데 사용할 수있는

193
00:08:15,820 --> 00:08:17,440
동일합니다.

194
00:08:17,440 --> 00:08:20,390
이것은 우리가 이전에 얘기했던 문자열 길이 알고리즘의 경우입니다.

195
00:08:20,390 --> 00:08:22,780
우리가 전에 변수에 저장하는 경우 즉,

196
00:08:22,780 --> 00:08:25,160
우리는 문자열을 저장하고 나중에 일정한 시간을 액세스 할 수 있습니다.

197
00:08:25,160 --> 00:08:27,920
어떤 번호든지

198
00:08:27,920 --> 00:08:30,130
우리가 변수에 저장하고, 우리가보고해야합니다.

199
00:08:33,110 --> 00:08:35,110
가장 좋은 경우는, 우리는 그걸 정말보고

200
00:08:35,110 --> 00:08:37,120
그리고 문자열의 길이를 찾습니다.

201
00:08:37,120 --> 00:08:39,799
Ω (1) 또는 최선의 일정한 시간은 그럼.

202
00:08:39,799 --> 00:08:41,059
최악의 경우는,

203
00:08:41,059 --> 00:08:43,400
우리는 바라 보면, 문자열의 길이를 찾습니다.

204
00:08:43,400 --> 00:08:47,300
따라서 O (1) 또는 최악의 경우 일정 시간이.

205
00:08:47,300 --> 00:08:49,180
그래서, 가장 좋은 경우와 최악의 경우 이후 동일합니다

206
00:08:49,180 --> 00:08:52,520
이것은 Θ (1) 시간에 실행이라고 할 수있다.

207
00:08:54,550 --> 00:08:57,010
>> 요약에서, 우리는 코드의 효율성에 대한 이유에 좋은 방법이

208
00:08:57,010 --> 00:09:00,110
그들은 실행 시간 실제 시간을 아무것도 알지 않고,

209
00:09:00,110 --> 00:09:02,270
어떤은 외부 요인에 많은 영향을받습니다

210
00:09:02,270 --> 00:09:04,190
서로 다른 하드웨어, 소프트웨어 등의

211
00:09:04,190 --> 00:09:06,040
또는 코드의 세부 사항.

212
00:09:06,040 --> 00:09:08,380
또한, 우리가 무슨 일이 일어날 지에 대해 잘 이유를 할 수 있습니다

213
00:09:08,380 --> 00:09:10,180
때 입력 증가의 크기.

214
00:09:10,180 --> 00:09:12,490
>> 당신은 O (n)이 ² 알고리즘에서 실행중인 경우

215
00:09:12,490 --> 00:09:15,240
또는 더 나쁜, O (2 ⁿ) 알고리즘,

216
00:09:15,240 --> 00:09:17,170
가장 빠르게 성장하고있는 유형 중 하나,

217
00:09:17,170 --> 00:09:19,140
당신은 정말 침체를 발견하기 시작합니다

218
00:09:19,140 --> 00:09:21,220
당신은 많은 양의 데이터 작업을 시작할 때.

219
00:09:21,220 --> 00:09:23,590
>> 그건 점근​​ 복잡성입니다. 감사합니다.