1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> 좋아, 그래서, 계산 복잡도.

3
00:00:07,910 --> 00:00:10,430
경고 조금
우리는 너무 far--에서 다이빙을하기 전에

4
00:00:10,430 --> 00:00:13,070
이것은 아마도들 수 있습니다
대부분의 수학 무거운 물건

5
00:00:13,070 --> 00:00:14,200
우리는 CS50에 대해 이야기.

6
00:00:14,200 --> 00:00:16,950
희망이 너무 압도적되지 않습니다
우리는 시도하고 당신을 안내합니다

7
00:00:16,950 --> 00:00:19,200
공정을 통해, 그러나
공정한 경고 조금.

8
00:00:19,200 --> 00:00:21,282
조금있다
수학의 여기에있었습니다.

9
00:00:21,282 --> 00:00:23,990
좋아, 순서에 있도록하는 것은 만들려면
우리의 전산 자원의 사용

10
00:00:23,990 --> 00:00:28,170
현실을 전 세계에이 정말
알고리즘을 이해하는 것이 중요합니다

11
00:00:28,170 --> 00:00:30,750
그들이 어떻게 데이터를 처리합니다.

12
00:00:30,750 --> 00:00:32,810
우리가이 있으면 정말
효율적인 알고리즘, 우리

13
00:00:32,810 --> 00:00:36,292
자원의 양을 최소화 할 수있다
우리는 그것을 처리 할 수​​ 있습니다.

14
00:00:36,292 --> 00:00:38,750
우리는 알고리즘이있는 경우 그
작업을 많이 걸릴 것입니다

15
00:00:38,750 --> 00:00:41,210
정말를 처리하는
대량의 데이터 세트, 그것은이다

16
00:00:41,210 --> 00:00:44,030
더 많은 것을 요구하는 것
더 많은 자원, 어느

17
00:00:44,030 --> 00:00:47,980
물건의 돈, RAM, 모든 종류이다.

18
00:00:47,980 --> 00:00:52,090
>> 그래서 수있는 것은 분석하기
알고리즘은,이 도구 세트를 사용하여

19
00:00:52,090 --> 00:00:56,110
기본적 question-- 묻는다
이 알고리즘의 규모를 어떻게하는지

20
00:00:56,110 --> 00:00:59,020
우리는 더 많은 데이터를 던져로?

21
00:00:59,020 --> 00:01:02,220
CS50에서는 데이터 양이있어
작업은 매우 작다.

22
00:01:02,220 --> 00:01:05,140
일반적으로, 우리의 프로그램이 진행된다
두 번째 또는 less--에서 실행

23
00:01:05,140 --> 00:01:07,830
아마 훨씬 덜
특히 초기에.

24
00:01:07,830 --> 00:01:12,250
>> 그러나 거래 회사에 대한 생각
고객의 수백만의 수백.

25
00:01:12,250 --> 00:01:14,970
그리고 그들은 처리해야
그 고객 데이터.

26
00:01:14,970 --> 00:01:18,260
고객의 수대로
이는, 더 크고 더 큰 얻는다

27
00:01:18,260 --> 00:01:21,230
그것은 필요 것
더 많은 자원.

28
00:01:21,230 --> 00:01:22,926
얼마나 더 많은 자원?

29
00:01:22,926 --> 00:01:25,050
글쎄, 그건 방법에 따라 달라집니다
우리의 알고리즘을 분석하여,

30
00:01:25,050 --> 00:01:28,097
이 도구 상자에 도구를 사용하여.

31
00:01:28,097 --> 00:01:31,180
우리의 복잡성에 대해 말할 때
algorithm--하는 때로는거야

32
00:01:31,180 --> 00:01:34,040
그것은 시간이라 듣고
복잡성 또는 공간 복잡성

33
00:01:34,040 --> 00:01:36,190
하지만 우리는 단지거야
complexity-- 호출

34
00:01:36,190 --> 00:01:38,770
우리는 일반적으로 약 얘기
최악의 시나리오.

35
00:01:38,770 --> 00:01:42,640
최악의 절대 더미의 주어
우리는 그것을 던지는을받을 수있는 데이터,

36
00:01:42,640 --> 00:01:46,440
방법이 알고리즘을 것입니다
처리하거나 그 데이터를 처리?

37
00:01:46,440 --> 00:01:51,450
우리는 일반적으로 최악 전화
알고리즘 큰-O의 런타임.

38
00:01:51,450 --> 00:01:56,770
그래서 알고리즘이라고 할 수 있습니다
제곱 n 또는 N의 O의 O에서 실행됩니다.

39
00:01:56,770 --> 00:01:59,110
에 대한 더 많은 것을
이들은 초 의미한다.

40
00:01:59,110 --> 00:02:01,620
>> 때때로, 그러나, 우리는 치료를 할
최상의 시나리오에 대한.

41
00:02:01,620 --> 00:02:05,400
데이터가 모든 경우 우리는 원
그것은 할 수 그것은 절대적으로 완벽했다

42
00:02:05,400 --> 00:02:09,630
우리는이 완벽을 전송했다
우리의 알고리즘을 통해 데이터의 집합입니다.

43
00:02:09,630 --> 00:02:11,470
어떻게 그 상황에서 처리 할 것인가?

44
00:02:11,470 --> 00:02:15,050
우리는 때때로로 그 참조
큰 오메가, 큰-O와 달리 그렇게,

45
00:02:15,050 --> 00:02:16,530
우리는 큰 오메가 있습니다.

46
00:02:16,530 --> 00:02:18,880
최상의 시나리오를위한 빅 오메가.

47
00:02:18,880 --> 00:02:21,319
최악의 경우에 대한 큰-O.

48
00:02:21,319 --> 00:02:23,860
일반적으로, 우리는 약 때 이야기
알고리즘의 복잡성

49
00:02:23,860 --> 00:02:26,370
우리에 대해 얘기하고
최악의 시나리오.

50
00:02:26,370 --> 00:02:28,100
그래서 명심.

51
00:02:28,100 --> 00:02:31,510
>> 그리고이 클래스에서, 우리는 일반적으로거야
옆으로 엄격한 분석을 떠날 수 있습니다.

52
00:02:31,510 --> 00:02:35,350
과학 분야가 있습니다
이런 종류의 물건에 전념입니다.

53
00:02:35,350 --> 00:02:37,610
우리는 추론에 대해 이야기 할 때
알고리즘을 통해,

54
00:02:37,610 --> 00:02:41,822
우리는 많은 부분 별 조각을 다하겠습니다하는
알고리즘은 우리가 수업 시간에 대한 이야기​​.

55
00:02:41,822 --> 00:02:44,780
우리는 정말로 단지에 대해 얘기하고
상식으로 통해 추론,

56
00:02:44,780 --> 00:02:47,070
하지 수식, 또는 증거와,
또는 그런 아무것도.

57
00:02:47,070 --> 00:02:51,600
그래서 걱정하지 마세요, 우리는하지 않습니다
큰 수학 수업으로 선회.

58
00:02:51,600 --> 00:02:55,920
>> 그래서 우리는 복잡성을 걱정했다
이는 질문을 어떻게 요구 때문에

59
00:02:55,920 --> 00:03:00,160
우리의 알고리즘은 더 큰 처리하나요과
큰 데이터 세트는 그들에게 던져지는.

60
00:03:00,160 --> 00:03:01,960
음, 데이터 세트는 무엇인가?

61
00:03:01,960 --> 00:03:03,910
내가 그런 말을하면 무엇을 의미 했습니까?

62
00:03:03,910 --> 00:03:07,600
그것은 가장 만드는 어떤 의미
문맥의 의미는, 솔직히 말해서.

63
00:03:07,600 --> 00:03:11,160
우리는 알고리즘이있는 경우
프로세스는 Strings-- 우리는 아마있어

64
00:03:11,160 --> 00:03:13,440
문자열의 크​​기에 대해 이야기.

65
00:03:13,440 --> 00:03:15,190
즉, 데이터의 set--
크기, 수

66
00:03:15,190 --> 00:03:17,050
문자열을 구성하는 문자.

67
00:03:17,050 --> 00:03:20,090
우리가 얘기하는 경우
파일을 처리 알고리즘,

68
00:03:20,090 --> 00:03:23,930
우리는 방법에 대해 이야기 할 수 있습니다
많은 킬로바이트 해당 파일을 포함한다.

69
00:03:23,930 --> 00:03:25,710
그리고 그 데이터 세트이다.

70
00:03:25,710 --> 00:03:28,870
우리는 알고리즘에 대해 이야기하는 경우
즉,보다 일반적으로는 어레이 처리

71
00:03:28,870 --> 00:03:31,510
같은 정렬 알고리즘으로
또는 알고리즘을 찾고,

72
00:03:31,510 --> 00:03:36,690
우리는 아마 수에 대해 얘기하고
어레이를 포함하는 소자.

73
00:03:36,690 --> 00:03:39,272
>> 이제, 우리는 측정 할 수 있습니다
algorithm-- 특히,

74
00:03:39,272 --> 00:03:40,980
내가 말할 때, 우리는 할 수
나는 알고리즘을 측정

75
00:03:40,980 --> 00:03:43,840
우리는 어떻게 측정 할 수있는 의미
많은 자원이 소요.

76
00:03:43,840 --> 00:03:48,990
그 자원이든, 얼마나 많은
RAM--의 바이트의 RAM이 메가 바이트

77
00:03:48,990 --> 00:03:49,790
그것은 사용합니다.

78
00:03:49,790 --> 00:03:52,320
또는 얼마나 많은 시간이 실행​​하는 데 걸리는.

79
00:03:52,320 --> 00:03:56,200
그리고 우리는이를 호출 할 수 있습니다
N의 F를 임의로 측정한다.

80
00:03:56,200 --> 00:03:59,420
여기서 n은 수이다
데이터 세트의 요소.

81
00:03:59,420 --> 00:04:02,640
그리고 N의 F 얼마나 많은 일도있다.

82
00:04:02,640 --> 00:04:07,530
얼마나 많은 자원 단위로 수행
이것은 그 데이터를 처리하도록 요구한다.

83
00:04:07,530 --> 00:04:10,030
>> 이제, 우리는 실제로 상관 없어
정확하게 N의 F 무엇이다.

84
00:04:10,030 --> 00:04:13,700
사실, 우리는 매우 드물게 will-- 없다
확실히 것이다 결코이 그 수업 전에서

85
00:04:13,700 --> 00:04:18,709
어떤 정말 깊이로 잠수
f를 n은 무엇인지 분석.

86
00:04:18,709 --> 00:04:23,510
우리는 무엇의 F에 대해 이야기하는거야
N은 약 또는 무엇을하는 경향이다.

87
00:04:23,510 --> 00:04:27,600
및 알고리즘의 경향은
최고 차항에 의해 결정.

88
00:04:27,600 --> 00:04:29,440
그리고 우리는 무엇을 볼 수 있습니다 나는
고려하여 그 뜻

89
00:04:29,440 --> 00:04:31,910
좀 더 구체적인 예를 살펴 보자.

90
00:04:31,910 --> 00:04:34,620
>> 그래서 우리가 있다고 가정 해 봅시다
세 가지 다른 알고리즘.

91
00:04:34,620 --> 00:04:39,350
그 중 첫째는 N 소요
자원의 제곱, 일부 단위

92
00:04:39,350 --> 00:04:42,880
크기 n의 데이터 세트를 처리한다.

93
00:04:42,880 --> 00:04:47,000
우리는 소요 제 2 알고리즘을
제곱 플러스 N 제곱 자원 N

94
00:04:47,000 --> 00:04:49,350
크기 n의 데이터 세트를 처리한다.

95
00:04:49,350 --> 00:04:52,030
그리고 우리는 세 번째가
그 in-- 실행 알고리즘

96
00:04:52,030 --> 00:04:58,300
소요 N 제곱 마이너스 8N 제곱
자원의 플러스 20 N 단위

97
00:04:58,300 --> 00:05:02,370
알고리즘을 처리하는 데
크기 n의 설정 데이터.

98
00:05:02,370 --> 00:05:05,594
>> 이제 다시, 우리는 정말하지 않을 수 있습니다
세부의이 수준으로 얻을 수 있습니다.

99
00:05:05,594 --> 00:05:08,260
난 그냥이를 가지고 정말 해요
여기에 한 점의 그림으로

100
00:05:08,260 --> 00:05:10,176
나는 될거야 것을
두 번째로 제작하는

101
00:05:10,176 --> 00:05:12,980
우리는 정말 걱정이다
사물의 경향에 대한

102
00:05:12,980 --> 00:05:14,870
데이터 세트는 더 큰 얻을 수있다.

103
00:05:14,870 --> 00:05:18,220
데이터 세트가 너무 작 으면, 거기
실제로 꽤 큰 차이

104
00:05:18,220 --> 00:05:19,870
이러한 알고리즘.

105
00:05:19,870 --> 00:05:23,000
이 세 번째 알고리즘
13 시간이 오래 걸립니다

106
00:05:23,000 --> 00:05:27,980
자원의 13 배 크기
처음에 상대적으로 실행합니다.

107
00:05:27,980 --> 00:05:31,659
>> 우리의 데이타 세트 크기가 10 인 경우, 이는
더 큰,하지만 반드시 큰되지 않습니다

108
00:05:31,659 --> 00:05:33,950
우리는 거기에 있다고 볼 수 있습니다
실제로 차이의 비트.

109
00:05:33,950 --> 00:05:36,620
세 번째 알고리즘
더 효율적이된다.

110
00:05:36,620 --> 00:05:40,120
실제로 40 %에 관하여 -
또는 60 % 더 효율적입니다.

111
00:05:40,120 --> 00:05:41,580
이는 40 %의 시간을 소요.

112
00:05:41,580 --> 00:05:45,250
그것은 걸릴 수 있습니다 run-- 수 있습니다
자원의 400 단위

113
00:05:45,250 --> 00:05:47,570
크기 10의 데이터 세트를 처리한다.

114
00:05:47,570 --> 00:05:49,410
첫 반면
알고리즘 반대로

115
00:05:49,410 --> 00:05:54,520
자원의 1,000 개 소요
크기 10의 데이터 세트를 처리한다.

116
00:05:54,520 --> 00:05:57,240
그러나 같은 무슨보고
우리의 숫자는 더 큰 얻을.

117
00:05:57,240 --> 00:05:59,500
>> 이제, 차
이러한 알고리즘 사이

118
00:05:59,500 --> 00:06:01,420
좀 덜 명확하게 시작한다.

119
00:06:01,420 --> 00:06:04,560
존재한다는 사실과
낮은 순서 terms-- 또는 오히려,

120
00:06:04,560 --> 00:06:09,390
낮은 exponents--와 용어
무관되기 시작합니다.

121
00:06:09,390 --> 00:06:12,290
데이터 세트의 크기이면
1,000과 제 알고리즘

122
00:06:12,290 --> 00:06:14,170
억 단계에서 실행됩니다.

123
00:06:14,170 --> 00:06:17,880
그리고 두 번째 알고리즘에서 실행
억 백만 단계.

124
00:06:17,880 --> 00:06:20,870
그리고 세 번째 알고리즘은 실행
억 단계의 단지 수줍어한다.

125
00:06:20,870 --> 00:06:22,620
그것은 거의 억 단계입니다.

126
00:06:22,620 --> 00:06:25,640
그 낮은 순서 조건은 시작
정말 무관하게합니다.

127
00:06:25,640 --> 00:06:27,390
그리고 정말에
집 망치 point--

128
00:06:27,390 --> 00:06:31,240
입력되는 데이터의 크기는 (a)의 경우는
3 천 5 백만 이들의 세 꽤 많이

129
00:06:31,240 --> 00:06:34,960
하나 quintillion-- 경우를 취할
내 수학 correct-- 단계입니다

130
00:06:34,960 --> 00:06:37,260
입력 된 데이터를 처리하는
크기 만.

131
00:06:37,260 --> 00:06:38,250
즉, 많은 단계입니다.

132
00:06:38,250 --> 00:06:42,092
상기 사실은 그들 중 하나 수도
몇 십만, 또는 몇을 (100)

133
00:06:42,092 --> 00:06:44,650
만 더 적은 경우
우리는 숫자에 대해 얘기하고

134
00:06:44,650 --> 00:06:46,990
즉 종류의 무관의 big--.

135
00:06:46,990 --> 00:06:50,006
그들은 모두 가지고하는 경향이
약 N의 제곱,

136
00:06:50,006 --> 00:06:52,380
그래서 우리는 실제로 참조 할 것
이 알고리즘의 모든

137
00:06:52,380 --> 00:06:59,520
N의 순서 인 것으로
제곱 또는 n의 제곱의 큰-O.

138
00:06:59,520 --> 00:07:03,220
>> 여기에 더의 일부 목록입니다
일반적인 계산 복잡도 클래스

139
00:07:03,220 --> 00:07:05,820
우리는에서 발생하는거야
알고리즘, 일반적으로.

140
00:07:05,820 --> 00:07:07,970
또한 특별히 CS50에서.

141
00:07:07,970 --> 00:07:11,410
이들은에서 정렬
일반적으로 상단에 빠른,

142
00:07:11,410 --> 00:07:13,940
하단에 일반적으로 느린한다.

143
00:07:13,940 --> 00:07:16,920
따라서 일정 시간 알고리즘 경향
에 관계없이, 가장 빠른 될

144
00:07:16,920 --> 00:07:19,110
크기의
데이터 입력하면 전달합니다.

145
00:07:19,110 --> 00:07:23,760
그들은 항상 하나의 동작을 취하거나
다루는 하나의 자원 유닛을 포함한다.

146
00:07:23,760 --> 00:07:25,730
그것은이있을 수 있습니다, 그것은 수도
3 일, 그것은 4 수 있습니다.

147
00:07:25,730 --> 00:07:26,910
그러나 상수이다.

148
00:07:26,910 --> 00:07:28,400
그것은 변화하지 않습니다.

149
00:07:28,400 --> 00:07:31,390
>> 대수 시간 알고리즘
조금 더 낫다.

150
00:07:31,390 --> 00:07:33,950
그리고 정말 좋은 예
로그 시간 알고리즘

151
00:07:33,950 --> 00:07:37,420
당신은 분명히 지금까지 본 것입니다했습니다
전화 번호부의 따로 따로 찢어

152
00:07:37,420 --> 00:07:39,480
전화 번호부에 마이크 스미스를 찾을 수 있습니다.

153
00:07:39,480 --> 00:07:40,980
우리는 반으로 문제를 잘라.

154
00:07:40,980 --> 00:07:43,580
N은 커질수록도록
큰 및 larger--

155
00:07:43,580 --> 00:07:47,290
사실, 때마다 당신은 두 번
n은 단지 한 단계 걸립니다.

156
00:07:47,290 --> 00:07:49,770
그것은 훨씬 더 그래서
보다, 말, 선형 시간.

157
00:07:49,770 --> 00:07:53,030
n을 두 번하면 어느 그것은이다
단계의 두 수를합니다.

158
00:07:53,030 --> 00:07:55,980
n을 세 겹 경우 소요
단계의 수를 배로.

159
00:07:55,980 --> 00:07:58,580
단위 당 하나의 단계.

160
00:07:58,580 --> 00:08:01,790
>> 그런 일들이 조금 more--를 얻을 수
좀 덜 좋은 거기에서.

161
00:08:01,790 --> 00:08:06,622
당신은 때때로, 선형 리듬 시간이
로그 선형 시간이라고하거나 N N를 기록합니다.

162
00:08:06,622 --> 00:08:08,330
그리고 우리는 예거야
알고리즘의

163
00:08:08,330 --> 00:08:13,370
여전히 더 나은 N 로그 N에서 실행
보다 차 time--의 N 제곱.

164
00:08:13,370 --> 00:08:17,320
또는 다항식 시간, N 두
이보다 더 큰 숫자.

165
00:08:17,320 --> 00:08:20,810
또는 지수 시간, 어느
심지어 worse-- C N이다.

166
00:08:20,810 --> 00:08:24,670
그래서 일부 상수는로 상승
입력의 크기의 힘.

167
00:08:24,670 --> 00:08:28,990
그래서 경우 ​​1,000--이 있다면
데이터 입력은, 크기 1,000이고

168
00:08:28,990 --> 00:08:31,310
그것은 1,000 전원 C 걸릴 것이다.

169
00:08:31,310 --> 00:08:33,559
이 다항식 시간보다 훨씬 더 나쁘다.

170
00:08:33,559 --> 00:08:35,030
>> 계승 시간이 더 악화입니다.

171
00:08:35,030 --> 00:08:37,760
그리고 사실, 거기에 정말 할
무한 시간 알고리즘이 존재

172
00:08:37,760 --> 00:08:43,740
누구의 소위로 바보 sort--
작업은 무작위로 배열 셔플하는 것입니다

173
00:08:43,740 --> 00:08:45,490
다음 확인
여부가 분류되어 있습니다.

174
00:08:45,490 --> 00:08:47,589
그리고 그것은 무작위 아니라면
다시 배열 셔플

175
00:08:47,589 --> 00:08:49,130
그리고 정렬 여부 확인합니다.

176
00:08:49,130 --> 00:08:51,671
그리고로 당신은 아마 imagine-- 수 있습니다
당신은 상황을 상상할 수

177
00:08:51,671 --> 00:08:55,200
여기서 최악의 경우에, 그 뜻
실제로 배열로 시작하지 마십시오.

178
00:08:55,200 --> 00:08:57,150
그 알고리즘은 영원히 실행됩니다.

179
00:08:57,150 --> 00:08:59,349
그리고 그 일 것입니다
무한한 시간 알고리즘.

180
00:08:59,349 --> 00:09:01,890
희망 당신은 작성되지 않습니다
어떤 계승 또는 무한 시간

181
00:09:01,890 --> 00:09:04,510
CS50에서 알고리즘.

182
00:09:04,510 --> 00:09:09,150
>> 자, 보자 조금 더
몇 가지 간단한에서 구체적인 모습

183
00:09:09,150 --> 00:09:11,154
계산 복잡도 클래스.

184
00:09:11,154 --> 00:09:13,070
그래서 우리는 example--이
또는 두 가지 예 here--

185
00:09:13,070 --> 00:09:15,590
일정 시간 알고리즘,
이는 항상 가지고

186
00:09:15,590 --> 00:09:17,980
최악의 경우에 하나의 작업.

187
00:09:17,980 --> 00:09:20,050
첫 번째 example-- 그래서
우리는 기능을 가지고

188
00:09:20,050 --> 00:09:23,952
당신을 위해 4라고하는
크기 1000의 배열을합니다.

189
00:09:23,952 --> 00:09:25,660
하지만 분명히
실제로 보이지 않는다

190
00:09:25,660 --> 00:09:29,000
그건 ... 정말 무슨 상관하지 않는다에서
그것의 내부에 그 배열의 형태가됩​​니다.

191
00:09:29,000 --> 00:09:30,820
항상 단지 4를 반환합니다.

192
00:09:30,820 --> 00:09:32,940
그래서, 알고리즘,
그것은 그 사실에도 불구하고

193
00:09:32,940 --> 00:09:35,840
1000 요소를하지 않습니다 소요
그들과 함께 아무것도 할.

194
00:09:35,840 --> 00:09:36,590
다만 4를 반환합니다.

195
00:09:36,590 --> 00:09:38,240
항상 한 단계입니다.

196
00:09:38,240 --> 00:09:41,600
>> 사실, (2)를 추가하는 nums--
우리는 저기 ... 전에 본 적이

197
00:09:41,600 --> 00:09:43,680
두 정수를 처리합니다.

198
00:09:43,680 --> 00:09:44,692
그것은 하나의 단계 아니다.

199
00:09:44,692 --> 00:09:45,900
실제로 몇 단계입니다.

200
00:09:45,900 --> 00:09:50,780
당신은 얻을, 당신이 B를 얻을, 당신은 추가
함께하고 출력 결과.

201
00:09:50,780 --> 00:09:53,270
그래서 84 단계입니다.

202
00:09:53,270 --> 00:09:55,510
그러나, 항상 일정의
에 관계없이 A 또는 B의.

203
00:09:55,510 --> 00:09:59,240
당신은을 얻을 수 있고, B를 얻을 추가
함께 그들, 출력 결과.

204
00:09:59,240 --> 00:10:02,900
그래서 일정 시간 알고리즘이다.

205
00:10:02,900 --> 00:10:05,170
>> 다음의 예
선형 시간 algorithm--

206
00:10:05,170 --> 00:10:08,740
그 소요 gets-- 알고리즘
하나의 추가 단계, 가능성,

207
00:10:08,740 --> 00:10:10,740
귀하의 의견은 1 성장함에 따라.

208
00:10:10,740 --> 00:10:14,190
그래서, 우리가 찾고있는 가정 해 봅시다
배열 번호 5 내부.

209
00:10:14,190 --> 00:10:16,774
당신은 상황 곳이있을 수 있습니다
당신은 상당히 일찍 찾을 수 있습니다.

210
00:10:16,774 --> 00:10:18,606
하지만 당신은 할 수
상황 곳을

211
00:10:18,606 --> 00:10:20,450
배열의 마지막 요소가 될 수 있습니다.

212
00:10:20,450 --> 00:10:23,780
크기 5의 배열의 경우에
우리는 숫자 5를 찾고 있습니다.

213
00:10:23,780 --> 00:10:25,930
그것은 5 조치를 취할 것입니다.

214
00:10:25,930 --> 00:10:29,180
그리고 사실, 거기에 상상
이 배열되지 5 어디서나.

215
00:10:29,180 --> 00:10:32,820
우리는 여전히 실제로 봐야
배열의 모든 단일 요소

216
00:10:32,820 --> 00:10:35,550
결정하기 위해
여부 5가있다.

217
00:10:35,550 --> 00:10:39,840
>> 그래서 인 최악의 경우에,
소자 배열의 마지막

218
00:10:39,840 --> 00:10:41,700
또는 전혀 존재하지 않습니다.

219
00:10:41,700 --> 00:10:44,690
우리는 여전히 봐야
n 개의 모든 요소를​​ 삭제합니다.

220
00:10:44,690 --> 00:10:47,120
그래서이 알고리즘
선형 시간에 실행됩니다.

221
00:10:47,120 --> 00:10:50,340
다음과 같은 방법으로 다음 사항을 확인 할 수 있습니다
말함으로써 조금 외삽,

222
00:10:50,340 --> 00:10:53,080
우리는 6 요소의 배열을했다 경우
우리는 숫자 5를 찾고 있었다

223
00:10:53,080 --> 00:10:54,890
그것은 6 조치를 취할 수 있습니다.

224
00:10:54,890 --> 00:10:57,620
우리 -7- 소자 어레이가있는 경우 및
우리는 숫자 5를 찾고 있습니다.

225
00:10:57,620 --> 00:10:59,160
그것은 7 조치를 취할 수 있습니다.

226
00:10:59,160 --> 00:11:02,920
우리는 또 하나의 요소를 추가하는 우리의
배열은, 한 단계 더 걸립니다.

227
00:11:02,920 --> 00:11:06,750
즉 선형 알고리즘이다
최악의 경우에.

228
00:11:06,750 --> 00:11:08,270
>> 커플 당신을 위해 빠른 질문.

229
00:11:08,270 --> 00:11:11,170
어떤이의 runtime-- 무엇입니까
최악의 경우의 런타임

230
00:11:11,170 --> 00:11:13,700
코드의 특정 조각의?

231
00:11:13,700 --> 00:11:17,420
그래서 실행 여기에 4 루프가
j는 0, m까지의 모든 방향에서 동일하다.

232
00:11:17,420 --> 00:11:21,980
그리고 제가 여기에보고하고있어,입니다
루프의 몸은 일정 시간에 실행됩니다.

233
00:11:21,980 --> 00:11:24,730
그래서 그 용어를 사용하여
우리는 이미 어떤 비슷해 얘기했습니다

234
00:11:24,730 --> 00:11:29,390
최악 것
이 알고리즘의 실행?

235
00:11:29,390 --> 00:11:31,050
두 번째를 가져 가라.

236
00:11:31,050 --> 00:11:34,270
루프의 내측부
일정 시간에 실행됩니다.

237
00:11:34,270 --> 00:11:37,510
상기의 외측부
루프는 m 회를 실행하는 것입니다.

238
00:11:37,510 --> 00:11:40,260
따라서 최악의 경우 런타임은 여기에 무엇입니까?

239
00:11:40,260 --> 00:11:43,210
당신은 M의 큰-O를 생각 했습니까?

240
00:11:43,210 --> 00:11:44,686
당신은 잘 될 것입니다.

241
00:11:44,686 --> 00:11:46,230
>> 어떻게 다른 하나는?

242
00:11:46,230 --> 00:11:48,590
우리가이 시간
루프의 내부 루프.

243
00:11:48,590 --> 00:11:50,905
우리는 외부 루프를
즉, 0에서 P로 실행됩니다.

244
00:11:50,905 --> 00:11:54,630
그리고 우리는 실행되는 내부 루프가
0에서 P, 그리고 그 내부,

245
00:11:54,630 --> 00:11:57,890
나는 주 몸이
루프는 일정 시간에 실행됩니다.

246
00:11:57,890 --> 00:12:02,330
따라서 최악의 경우 런타임은 무엇인가
코드의 특정 조각의?

247
00:12:02,330 --> 00:12:06,140
음, 다시, 우리는이
P 시간을 실행 외부 루프.

248
00:12:06,140 --> 00:12:09,660
그리고 각 time-- 반복
그 루프, 오히려.

249
00:12:09,660 --> 00:12:13,170
우리는 내부 루프가
그 또한 P 시간을 실행합니다.

250
00:12:13,170 --> 00:12:16,900
그 내부에 그리고, 거기에
이 상수 time-- 작은 조각.

251
00:12:16,900 --> 00:12:19,890
>> 우리가 외부 루프가 있다면 그래서
어느 쪽이 내부 회 실행

252
00:12:19,890 --> 00:12:22,880
내부 루프가
무엇 times-- 페이지를 실행

253
00:12:22,880 --> 00:12:26,480
최악의 경우의 런타임
이 코드 조각의?

254
00:12:26,480 --> 00:12:30,730
당신은 P의 큰 O는 제곱 생각 했습니까?

255
00:12:30,730 --> 00:12:31,690
>> 나는 더그 로이드입니다.

256
00:12:31,690 --> 00:12:33,880
이 CS50입니다.

257
00:12:33,880 --> 00:12:35,622