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

2
00:00:05,830 --> 00:00:07,910
>> Tất cả các quyền, do đó, tính toán phức tạp.

3
00:00:07,910 --> 00:00:10,430
Chỉ cần một chút của một cảnh báo
trước khi chúng ta đi sâu vào quá far--

4
00:00:10,430 --> 00:00:13,070
điều này có lẽ sẽ là một trong số
những điều nhất môn toán nặng

5
00:00:13,070 --> 00:00:14,200
chúng ta nói về trong CS50.

6
00:00:14,200 --> 00:00:16,950
Hy vọng rằng nó sẽ không quá áp đảo
và chúng tôi sẽ cố gắng và hướng dẫn bạn

7
00:00:16,950 --> 00:00:19,200
thông qua quá trình này, nhưng
chỉ là một chút của một cảnh báo công bằng.

8
00:00:19,200 --> 00:00:21,282
Có một chút
của toán học liên quan ở đây.

9
00:00:21,282 --> 00:00:23,990
Được rồi, vì vậy để làm cho
sử dụng các tài nguyên tính toán của chúng tôi

10
00:00:23,990 --> 00:00:28,170
trong world-- thực sự nó thực sự
quan trọng để hiểu các thuật toán

11
00:00:28,170 --> 00:00:30,750
và làm thế nào họ xử lý dữ liệu.

12
00:00:30,750 --> 00:00:32,810
Nếu chúng ta có một thực sự
thuật toán hiệu quả, chúng tôi

13
00:00:32,810 --> 00:00:36,292
có thể giảm thiểu số lượng tài nguyên
chúng tôi có sẵn để đối phó với nó.

14
00:00:36,292 --> 00:00:38,750
Nếu chúng ta có một thuật toán mà
là sẽ mất rất nhiều công việc

15
00:00:38,750 --> 00:00:41,210
để xử lý một thực sự
tập dữ liệu lớn, nó

16
00:00:41,210 --> 00:00:44,030
sẽ đòi hỏi nhiều hơn
và nhiều tài nguyên, mà

17
00:00:44,030 --> 00:00:47,980
là tiền bạc, RAM, tất cả các loại công cụ.

18
00:00:47,980 --> 00:00:52,090
>> Vì vậy, để có thể phân tích một
thuật toán sử dụng bộ công cụ này,

19
00:00:52,090 --> 00:00:56,110
về cơ bản, yêu cầu các question--
làm thế nào quy mô thuật toán này

20
00:00:56,110 --> 00:00:59,020
như chúng ta ném càng nhiều dữ liệu vào nó?

21
00:00:59,020 --> 00:01:02,220
Trong CS50, số lượng dữ liệu chúng tôi
làm việc với là khá nhỏ.

22
00:01:02,220 --> 00:01:05,140
Nói chung, các chương trình của chúng tôi sẽ
để chạy trong một giây hoặc less--

23
00:01:05,140 --> 00:01:07,830
có lẽ ít hơn rất nhiều
đặc biệt vào đầu.

24
00:01:07,830 --> 00:01:12,250
>> Nhưng hãy nghĩ về một công ty giao dịch
với hàng trăm triệu khách hàng.

25
00:01:12,250 --> 00:01:14,970
Và họ cần xử lý
rằng dữ liệu khách hàng.

26
00:01:14,970 --> 00:01:18,260
Khi số lượng khách hàng của họ
có được lớn hơn và lớn hơn,

27
00:01:18,260 --> 00:01:21,230
nó sẽ yêu cầu
hơn và nhiều tài nguyên.

28
00:01:21,230 --> 00:01:22,926
Làm thế nào nhiều hơn các nguồn lực?

29
00:01:22,926 --> 00:01:25,050
Vâng, điều đó phụ thuộc vào cách
chúng tôi phân tích các thuật toán,

30
00:01:25,050 --> 00:01:28,097
sử dụng các công cụ trong hộp công cụ này.

31
00:01:28,097 --> 00:01:31,180
Khi chúng ta nói về sự phức tạp của
một algorithm-- mà đôi khi bạn sẽ

32
00:01:31,180 --> 00:01:34,040
nghe nó gọi là thời gian
phức tạp hoặc không gian phức tạp

33
00:01:34,040 --> 00:01:36,190
nhưng chúng tôi chỉ cần đi
để gọi complexity--

34
00:01:36,190 --> 00:01:38,770
nói chung chúng ta đang nói về
các trường hợp xấu nhất.

35
00:01:38,770 --> 00:01:42,640
Với đống tuyệt đối tồi tệ nhất của
dữ liệu mà chúng tôi có thể được ném vào nó,

36
00:01:42,640 --> 00:01:46,440
làm thế nào là thuật toán này sẽ
xử lý hoặc xử lý dữ liệu đó?

37
00:01:46,440 --> 00:01:51,450
Chúng tôi thường gọi trường hợp xấu nhất
thời gian chạy của một thuật toán O lớn.

38
00:01:51,450 --> 00:01:56,770
Vì vậy, một thuật toán có thể được nói đến
chạy trong O của n hoặc O của n bình phương.

39
00:01:56,770 --> 00:01:59,110
Và nhiều hơn nữa về những gì
những người có nghĩa là trong một giây.

40
00:01:59,110 --> 00:02:01,620
>> Đôi khi, mặc dù, chúng tôi chăm sóc
về các trường hợp tốt nhất.

41
00:02:01,620 --> 00:02:05,400
Nếu dữ liệu là tất cả mọi thứ chúng tôi muốn
nó được và nó đã được hoàn toàn hoàn hảo

42
00:02:05,400 --> 00:02:09,630
và chúng tôi đã gửi hoàn hảo này
thiết lập các dữ liệu thông qua các thuật toán của chúng tôi.

43
00:02:09,630 --> 00:02:11,470
Làm thế nào nó sẽ xử lý trong tình huống đó?

44
00:02:11,470 --> 00:02:15,050
Chúng ta đôi khi chỉ đến đó như
big-Omega, vì vậy trong tương phản với big-O,

45
00:02:15,050 --> 00:02:16,530
chúng tôi có lớn Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega cho các trường hợp tốt nhất.

47
00:02:18,880 --> 00:02:21,319
Big-O cho các trường hợp xấu nhất.

48
00:02:21,319 --> 00:02:23,860
Nói chung, khi chúng ta nói về
sự phức tạp của một thuật toán,

49
00:02:23,860 --> 00:02:26,370
chúng ta đang nói về
trường hợp xấu nhất kịch bản.

50
00:02:26,370 --> 00:02:28,100
Vì vậy, giữ cho rằng trong tâm trí.

51
00:02:28,100 --> 00:02:31,510
>> Và trong lớp học này, chúng ta thường đi
để lại những phân tích nghiêm ngặt sang một bên.

52
00:02:31,510 --> 00:02:35,350
Có khoa học và các lĩnh vực
dành cho loại công cụ này.

53
00:02:35,350 --> 00:02:37,610
Khi chúng ta nói về lý luận
thông qua các thuật toán,

54
00:02:37,610 --> 00:02:41,822
mà chúng tôi sẽ làm piece-by-piece cho nhiều
các thuật toán chúng ta nói về trong lớp.

55
00:02:41,822 --> 00:02:44,780
Chúng tôi đang thực sự chỉ nói về
lý luận thông qua nó với ý nghĩa thông thường,

56
00:02:44,780 --> 00:02:47,070
không có công thức, hoặc giấy tờ chứng minh,
hoặc bất cứ điều gì như thế.

57
00:02:47,070 --> 00:02:51,600
Vì vậy, đừng lo lắng, chúng tôi sẽ không được
biến thành một lớp toán học lớn.

58
00:02:51,600 --> 00:02:55,920
>> Vì vậy, tôi đã nói, chúng tôi quan tâm về sự phức tạp
bởi vì nó đưa ra câu hỏi, làm thế nào

59
00:02:55,920 --> 00:03:00,160
làm các thuật toán của chúng tôi xử lý lớn hơn và
các tập dữ liệu lớn được ném vào chúng.

60
00:03:00,160 --> 00:03:01,960
Vâng, một tập hợp dữ liệu là gì?

61
00:03:01,960 --> 00:03:03,910
Tôi đã có ý nghĩa gì khi tôi nói vậy?

62
00:03:03,910 --> 00:03:07,600
Nó có nghĩa là bất cứ điều gì làm cho hầu hết
ý nghĩa trong bối cảnh, phải trung thực.

63
00:03:07,600 --> 00:03:11,160
Nếu chúng ta có một thuật toán,
Processes Strings-- chúng tôi có thể

64
00:03:11,160 --> 00:03:13,440
nói về kích thước của chuỗi.

65
00:03:13,440 --> 00:03:15,190
Đó là các dữ liệu set--
kích thước, số lượng

66
00:03:15,190 --> 00:03:17,050
các ký tự tạo nên các chuỗi.

67
00:03:17,050 --> 00:03:20,090
Nếu chúng ta đang nói về một
thuật toán xử lý các tập tin,

68
00:03:20,090 --> 00:03:23,930
chúng ta có thể nói về cách
nhiều kilobytes gồm tập tin đó.

69
00:03:23,930 --> 00:03:25,710
Và đó là tập hợp dữ liệu.

70
00:03:25,710 --> 00:03:28,870
Nếu chúng ta đang nói về một thuật toán
xử lý mảng thường hơn,

71
00:03:28,870 --> 00:03:31,510
chẳng hạn như thuật toán phân loại
hoặc tìm kiếm các thuật toán,

72
00:03:31,510 --> 00:03:36,690
có lẽ chúng ta đang nói về số lượng
các yếu tố đó bao gồm một mảng.

73
00:03:36,690 --> 00:03:39,272
>> Bây giờ, chúng ta có thể đo lường một
algorithm-- nói riêng,

74
00:03:39,272 --> 00:03:40,980
khi tôi nói rằng chúng tôi có thể
đo một thuật toán, tôi

75
00:03:40,980 --> 00:03:43,840
có nghĩa là chúng ta có thể đo lường như thế nào
nhiều nguồn lực nó chiếm.

76
00:03:43,840 --> 00:03:48,990
Cho dù những nguồn lực đang có, bao nhiêu
byte của RAM-- hoặc MB RAM

77
00:03:48,990 --> 00:03:49,790
nó sử dụng.

78
00:03:49,790 --> 00:03:52,320
Hoặc có bao nhiêu thời gian để chạy.

79
00:03:52,320 --> 00:03:56,200
Và chúng ta có thể gọi đây
đo lường, tùy tiện, f của n.

80
00:03:56,200 --> 00:03:59,420
Trong đó n là số
các phần tử trong tập hợp dữ liệu.

81
00:03:59,420 --> 00:04:02,640
Và f của n là bao nhiêu somethings.

82
00:04:02,640 --> 00:04:07,530
Có bao nhiêu đơn vị tài nguyên không
nó yêu cầu để xử lý dữ liệu đó.

83
00:04:07,530 --> 00:04:10,030
>> Bây giờ, chúng tôi thực sự không quan tâm
về những gì f của n là chính xác.

84
00:04:10,030 --> 00:04:13,700
Trong thực tế, chúng tôi rất hiếm khi will--
chắc chắn sẽ không bao giờ trong tôi class-- này

85
00:04:13,700 --> 00:04:18,709
nhảy vào bất kỳ thực sự sâu sắc
phân tích của f của n là gì.

86
00:04:18,709 --> 00:04:23,510
Chúng tôi chỉ cần đi để nói về những gì e
n là xấp xỉ hoặc những gì nó có xu hướng.

87
00:04:23,510 --> 00:04:27,600
Và xu hướng của một thuật toán là
quyết định bởi hạn mức độ cao nhất của nó.

88
00:04:27,600 --> 00:04:29,440
Và chúng ta có thể thấy những gì tôi
ý nghĩa bởi đó bằng cách tham gia

89
00:04:29,440 --> 00:04:31,910
một nhìn vào một ví dụ cụ thể hơn.

90
00:04:31,910 --> 00:04:34,620
>> Vì vậy, chúng ta hãy nói rằng chúng tôi có
ba thuật toán khác nhau.

91
00:04:34,620 --> 00:04:39,350
Việc đầu tiên trong số đó có n
cubed, một số đơn vị tài nguyên

92
00:04:39,350 --> 00:04:42,880
để xử lý một tập hợp dữ liệu có kích thước n.

93
00:04:42,880 --> 00:04:47,000
Chúng tôi có một thuật toán thứ hai mà phải mất
n cubed cộng với nguồn n bình

94
00:04:47,000 --> 00:04:49,350
để xử lý một tập hợp dữ liệu có kích thước n.

95
00:04:49,350 --> 00:04:52,030
Và chúng tôi có một phần ba
thuật toán chạy in-- đó

96
00:04:52,030 --> 00:04:58,300
chiếm n trừ cubed 8N phương
cộng với 20 n đơn vị tài nguyên

97
00:04:58,300 --> 00:05:02,370
để xử lý một thuật toán
với dữ liệu thiết lập kích thước n.

98
00:05:02,370 --> 00:05:05,594
>> Bây giờ một lần nữa, chúng ta thật sự không hẹn
để có được vào mức độ chi tiết này.

99
00:05:05,594 --> 00:05:08,260
Tôi thực sự chỉ có những lên
ở đây như là một minh họa của một điểm

100
00:05:08,260 --> 00:05:10,176
rằng tôi sẽ được
làm trong một giây,

101
00:05:10,176 --> 00:05:12,980
là chúng ta chỉ thực sự quan tâm
về xu hướng của sự vật

102
00:05:12,980 --> 00:05:14,870
như các bộ dữ liệu có được lớn hơn.

103
00:05:14,870 --> 00:05:18,220
Vì vậy, nếu các tập dữ liệu là nhỏ, có
thực sự là một sự khác biệt khá lớn

104
00:05:18,220 --> 00:05:19,870
trong các thuật toán.

105
00:05:19,870 --> 00:05:23,000
Các thuật toán thứ ba có
mất lâu hơn 13 lần,

106
00:05:23,000 --> 00:05:27,980
13 lần số lượng tài nguyên
để chạy tương đối với một trong những đầu tiên.

107
00:05:27,980 --> 00:05:31,659
>> Nếu dữ liệu của chúng tôi là kích thước 10,
là lớn hơn, nhưng không nhất thiết là rất lớn,

108
00:05:31,659 --> 00:05:33,950
chúng ta có thể thấy rằng có
thực sự là một chút của một sự khác biệt.

109
00:05:33,950 --> 00:05:36,620
Các thuật toán thứ ba
trở nên hiệu quả hơn.

110
00:05:36,620 --> 00:05:40,120
Đó là về thực 40% -
hoặc 60% hiệu quả hơn.

111
00:05:40,120 --> 00:05:41,580
Phải mất 40% số lượng thời gian.

112
00:05:41,580 --> 00:05:45,250
Nó có thể run-- nó có thể mất
400 đơn vị tài nguyên

113
00:05:45,250 --> 00:05:47,570
để xử lý một tập hợp dữ liệu có kích thước 10.

114
00:05:47,570 --> 00:05:49,410
Trong khi đó, người đầu tiên
thuật toán, ngược lại,

115
00:05:49,410 --> 00:05:54,520
có 1.000 đơn vị tài nguyên
để xử lý một tập hợp dữ liệu có kích thước 10.

116
00:05:54,520 --> 00:05:57,240
Nhưng hãy nhìn những gì xảy ra khi
số của chúng tôi nhận được thậm chí lớn hơn.

117
00:05:57,240 --> 00:05:59,500
>> Bây giờ, sự khác biệt
giữa các thuật toán

118
00:05:59,500 --> 00:06:01,420
bắt đầu trở thành một chút ít rõ ràng hơn.

119
00:06:01,420 --> 00:06:04,560
Và thực tế là có
thấp hơn để terms-- hay đúng hơn,

120
00:06:04,560 --> 00:06:09,390
các điều khoản với exponents-- thấp
bắt đầu trở nên không thích hợp.

121
00:06:09,390 --> 00:06:12,290
Nếu một tập hợp dữ liệu có kích thước
1000 và các thuật toán đầu tiên

122
00:06:12,290 --> 00:06:14,170
chạy trong một tỷ bước.

123
00:06:14,170 --> 00:06:17,880
Và các thuật toán thứ hai chạy trong
một tỷ đồng và một triệu bước.

124
00:06:17,880 --> 00:06:20,870
Và các thuật toán thứ ba chạy
trong chỉ nhút nhát của một tỷ bước.

125
00:06:20,870 --> 00:06:22,620
Đó là khá nhiều một tỷ bước.

126
00:06:22,620 --> 00:06:25,640
Những điều khoản dưới để bắt đầu
để trở nên thực sự không thích hợp.

127
00:06:25,640 --> 00:06:27,390
Và chỉ để thực sự
búa nhà point--

128
00:06:27,390 --> 00:06:31,240
nếu các dữ liệu đầu vào là có kích thước một
million-- cả ba khá nhiều

129
00:06:31,240 --> 00:06:34,960
mất một quintillion-- nếu
toán học của tôi là bước correct--

130
00:06:34,960 --> 00:06:37,260
để xử lý dữ liệu đầu vào
kích thước của một triệu.

131
00:06:37,260 --> 00:06:38,250
Đó là rất nhiều bước.

132
00:06:38,250 --> 00:06:42,092
Và thực tế là một trong số họ có thể
mất một vài 100,000, hoặc một vài 100

133
00:06:42,092 --> 00:06:44,650
triệu thậm chí ít khi
chúng ta đang nói về một số

134
00:06:44,650 --> 00:06:46,990
rằng big-- đó là loại không thích hợp.

135
00:06:46,990 --> 00:06:50,006
Họ đều có xu hướng mất
khoảng n cubed,

136
00:06:50,006 --> 00:06:52,380
và vì vậy chúng tôi sẽ thực sự tham khảo
cho tất cả các thuật toán

137
00:06:52,380 --> 00:06:59,520
như là vào thứ tự của n
cubed hoặc O lớn của n cubed.

138
00:06:59,520 --> 00:07:03,220
>> Dưới đây là một danh sách của một số chi tiết
lớp phức tạp tính toán thông thường

139
00:07:03,220 --> 00:07:05,820
rằng chúng ta sẽ gặp phải trong
các thuật toán, nói chung.

140
00:07:05,820 --> 00:07:07,970
Và cũng đặc biệt trong CS50.

141
00:07:07,970 --> 00:07:11,410
Chúng được đặt hàng từ
nói chung là nhanh nhất ở đầu,

142
00:07:11,410 --> 00:07:13,940
để thường chậm nhất ở phía dưới.

143
00:07:13,940 --> 00:07:16,920
Vì vậy, các thuật toán thời gian liên tục có xu hướng
là nhanh nhất, không phân biệt

144
00:07:16,920 --> 00:07:19,110
các kích thước của
dữ liệu đầu vào bạn vượt qua trong.

145
00:07:19,110 --> 00:07:23,760
Họ luôn luôn có một hoạt động hoặc
một đơn vị nguồn lực để đối phó với.

146
00:07:23,760 --> 00:07:25,730
Nó có thể là 2, nó có thể
được 3, nó có thể là 4.

147
00:07:25,730 --> 00:07:26,910
Nhưng đó là một hằng số.

148
00:07:26,910 --> 00:07:28,400
Nó không thay đổi.

149
00:07:28,400 --> 00:07:31,390
>> Thuật toán thời gian logarit
là tốt hơn một chút.

150
00:07:31,390 --> 00:07:33,950
Và một ví dụ thực sự tốt của
một thuật toán thời gian logarit

151
00:07:33,950 --> 00:07:37,420
bạn đã chắc chắn nhìn thấy bây giờ là
xé nát của cuốn sách điện thoại

152
00:07:37,420 --> 00:07:39,480
để tìm Mike Smith trong sổ điện thoại.

153
00:07:39,480 --> 00:07:40,980
Chúng tôi cắt các vấn đề trong một nửa.

154
00:07:40,980 --> 00:07:43,580
Và như vậy, n được lớn hơn
và lớn hơn và larger--

155
00:07:43,580 --> 00:07:47,290
trên thực tế, mỗi khi bạn tăng gấp đôi
n, nó chỉ mất một bước nữa.

156
00:07:47,290 --> 00:07:49,770
Vì vậy, đó là tốt hơn rất nhiều
hơn, nói, thời gian tuyến tính.

157
00:07:49,770 --> 00:07:53,030
Đó là nếu bạn tăng gấp đôi n, nó
mất gấp đôi số lượng các bước.

158
00:07:53,030 --> 00:07:55,980
Nếu bạn tăng gấp ba n, phải mất
tăng gấp ba lần số lượng các bước.

159
00:07:55,980 --> 00:07:58,580
Một bước trên một đơn vị.

160
00:07:58,580 --> 00:08:01,790
>> Sau đó, việc có được một chút more--
chút ít tuyệt vời từ đó.

161
00:08:01,790 --> 00:08:06,622
Bạn có thời gian tuyến tính nhịp điệu, đôi khi
gọi là nhật ký thời gian tuyến tính, hoặc chỉ n log n.

162
00:08:06,622 --> 00:08:08,330
Và chúng tôi sẽ là một ví dụ
của một thuật toán mà

163
00:08:08,330 --> 00:08:13,370
chạy trong n n log, mà vẫn còn tốt hơn
hơn bậc hai time-- n bình phương.

164
00:08:13,370 --> 00:08:17,320
Hoặc thời gian đa thức, n hai
bất kỳ số nào lớn hơn hai.

165
00:08:17,320 --> 00:08:20,810
Hoặc thời gian mũ, mà
thậm chí còn worse-- C đến n.

166
00:08:20,810 --> 00:08:24,670
Vì vậy, một số số liên tục tăng lên
sức mạnh của các kích thước của đầu vào.

167
00:08:24,670 --> 00:08:28,990
Vì vậy, nếu có 1,000-- nếu
dữ liệu đầu vào là có kích thước 1.000,

168
00:08:28,990 --> 00:08:31,310
nó sẽ mất C với sức mạnh 1000.

169
00:08:31,310 --> 00:08:33,559
Nó tồi tệ hơn rất nhiều so với thời gian đa thức.

170
00:08:33,559 --> 00:08:35,030
>> Thời gian thừa thậm chí còn tồi tệ hơn.

171
00:08:35,030 --> 00:08:37,760
Và trên thực tế, có thực sự làm
tồn tại thuật toán thời gian vô hạn,

172
00:08:37,760 --> 00:08:43,740
chẳng hạn như, cái gọi là ngu ngốc mà sort--
công việc là để shuffle ngẫu nhiên một mảng

173
00:08:43,740 --> 00:08:45,490
và sau đó kiểm tra xem
cho dù nó được sắp xếp.

174
00:08:45,490 --> 00:08:47,589
Và nếu nó không phải, ngẫu nhiên
xáo trộn các mảng lại

175
00:08:47,589 --> 00:08:49,130
và kiểm tra để xem liệu nó được sắp xếp.

176
00:08:49,130 --> 00:08:51,671
Và như bạn có thể có thể imagine--
bạn có thể tưởng tượng một tình huống

177
00:08:51,671 --> 00:08:55,200
nơi mà trong trường hợp xấu nhất, có ý chí
không bao giờ thực sự bắt đầu với mảng.

178
00:08:55,200 --> 00:08:57,150
Thuật toán mà có thể chạy mãi.

179
00:08:57,150 --> 00:08:59,349
Và do đó sẽ là một
vô hạn thuật toán thời gian.

180
00:08:59,349 --> 00:09:01,890
Hy vọng rằng bạn sẽ không được viết
bất cứ lúc nào thừa hoặc vô hạn

181
00:09:01,890 --> 00:09:04,510
thuật toán trong CS50.

182
00:09:04,510 --> 00:09:09,150
>> Vì vậy, chúng ta hãy thêm một chút
cái nhìn cụ thể tại một số đơn giản

183
00:09:09,150 --> 00:09:11,154
lớp học tính toán phức tạp.

184
00:09:11,154 --> 00:09:13,070
Vì vậy, chúng ta có một example--
hoặc hai ví dụ here--

185
00:09:13,070 --> 00:09:15,590
các thuật toán thời gian liên tục,
mà luôn luôn đi

186
00:09:15,590 --> 00:09:17,980
một hoạt động duy nhất trong trường hợp xấu nhất.

187
00:09:17,980 --> 00:09:20,050
Vì vậy, các example-- đầu tiên
chúng tôi có một chức năng

188
00:09:20,050 --> 00:09:23,952
gọi là 4 cho bạn, mà
mất một mảng có kích thước 1.000.

189
00:09:23,952 --> 00:09:25,660
Nhưng sau đó rõ ràng
không thực sự nhìn

190
00:09:25,660 --> 00:09:29,000
tại it-- không thực sự quan tâm những gì
bên trong của nó, của mảng đó.

191
00:09:29,000 --> 00:09:30,820
Lúc nào cũng chỉ trả về bốn.

192
00:09:30,820 --> 00:09:32,940
Vì vậy, thuật toán,
mặc dù thực tế rằng nó

193
00:09:32,940 --> 00:09:35,840
mất 1.000 yếu tố không
làm bất cứ điều gì với họ.

194
00:09:35,840 --> 00:09:36,590
Chỉ cần trả về bốn.

195
00:09:36,590 --> 00:09:38,240
Nó luôn luôn là một bước duy nhất.

196
00:09:38,240 --> 00:09:41,600
>> Trong thực tế, thêm 2 nums-- mà
chúng tôi đã nhìn thấy trước như well--

197
00:09:41,600 --> 00:09:43,680
chỉ xử lý hai số nguyên.

198
00:09:43,680 --> 00:09:44,692
Nó không phải là một bước duy nhất.

199
00:09:44,692 --> 00:09:45,900
Nó thực sự là một vài bước.

200
00:09:45,900 --> 00:09:50,780
Bạn nhận được một, bạn sẽ có được b, bạn thêm chúng
với nhau, và bạn xuất kết quả.

201
00:09:50,780 --> 00:09:53,270
Vì vậy, nó là 84 bước.

202
00:09:53,270 --> 00:09:55,510
Nhưng nó luôn luôn không đổi,
bất kể một hoặc b.

203
00:09:55,510 --> 00:09:59,240
Bạn có để có được một, có được b, thêm
chúng lại với nhau, kết quả đầu ra.

204
00:09:59,240 --> 00:10:02,900
Vì vậy, đó là một thuật toán thời gian liên tục.

205
00:10:02,900 --> 00:10:05,170
>> Dưới đây là một ví dụ về một
thời gian tuyến tính algorithm--

206
00:10:05,170 --> 00:10:08,740
một thuật toán mà gets-- mà mất
một bước bổ sung, có thể,

207
00:10:08,740 --> 00:10:10,740
như là đầu vào của bạn phát triển bởi 1.

208
00:10:10,740 --> 00:10:14,190
Vì vậy, chúng ta hãy nói rằng chúng tôi đang tìm kiếm
số 5 bên trong một mảng.

209
00:10:14,190 --> 00:10:16,774
Bạn có thể có một tình huống mà
bạn có thể tìm thấy nó khá sớm.

210
00:10:16,774 --> 00:10:18,606
Nhưng bạn cũng có thể có
một tình huống mà nó

211
00:10:18,606 --> 00:10:20,450
có thể là yếu tố cuối cùng của mảng.

212
00:10:20,450 --> 00:10:23,780
Trong một mảng có kích thước 5, nếu
chúng tôi đang tìm kiếm các số 5.

213
00:10:23,780 --> 00:10:25,930
Nó sẽ có 5 bước.

214
00:10:25,930 --> 00:10:29,180
Và trên thực tế, hãy tưởng tượng rằng có
không phải 5 bất cứ nơi nào trong mảng này.

215
00:10:29,180 --> 00:10:32,820
Chúng tôi vẫn thực sự phải nhìn vào
mỗi phần tử của mảng

216
00:10:32,820 --> 00:10:35,550
nhằm xác định
hay không 5 là có.

217
00:10:35,550 --> 00:10:39,840
>> Vì vậy, trong trường hợp xấu nhất, đó là
các nguyên tố là cuối cùng trong mảng

218
00:10:39,840 --> 00:10:41,700
hoặc không tồn tại.

219
00:10:41,700 --> 00:10:44,690
Chúng tôi vẫn phải nhìn vào
tất cả các yếu tố n.

220
00:10:44,690 --> 00:10:47,120
Và do đó, thuật toán này
chạy trong thời gian tuyến tính.

221
00:10:47,120 --> 00:10:50,340
Bạn có thể xác nhận rằng bằng
ngoại suy một chút bằng cách nói,

222
00:10:50,340 --> 00:10:53,080
nếu chúng ta có một mảng 6 phần tử và
chúng tôi đang tìm kiếm các số 5,

223
00:10:53,080 --> 00:10:54,890
nó có thể mất 6 bước.

224
00:10:54,890 --> 00:10:57,620
Nếu chúng ta có một mảng 7 phần tử và
chúng tôi đang tìm kiếm các số 5.

225
00:10:57,620 --> 00:10:59,160
Nó có thể mất 7 bước.

226
00:10:59,160 --> 00:11:02,920
Khi chúng ta thêm một yếu tố nữa để chúng tôi
mảng, phải mất thêm một bước nữa.

227
00:11:02,920 --> 00:11:06,750
Đó là một thuật toán tuyến tính
trong trường hợp xấu nhất.

228
00:11:06,750 --> 00:11:08,270
>> Vài câu hỏi nhanh chóng cho bạn.

229
00:11:08,270 --> 00:11:11,170
Các runtime-- những gì là những gì
trường hợp xấu nhất-runtime

230
00:11:11,170 --> 00:11:13,700
của đoạn này đặc biệt của mã?

231
00:11:13,700 --> 00:11:17,420
Vì vậy, tôi có một vòng lặp 4 ở đây mà chạy
từ j bằng 0, tất cả các con đường lên đến m.

232
00:11:17,420 --> 00:11:21,980
Và những gì tôi nhìn thấy ở đây, là các
thân của vòng lặp chạy trong thời gian liên tục.

233
00:11:21,980 --> 00:11:24,730
Vì vậy, bằng cách sử dụng các thuật ngữ
chúng tôi đã nói chuyện gì about--

234
00:11:24,730 --> 00:11:29,390
sẽ là trường hợp xấu nhất
thời gian chạy của thuật toán này?

235
00:11:29,390 --> 00:11:31,050
Mất một giây.

236
00:11:31,050 --> 00:11:34,270
Phần bên trong của vòng lặp
chạy trong thời gian liên tục.

237
00:11:34,270 --> 00:11:37,510
Và phần ngoài của
vòng lặp sẽ chạy lần m.

238
00:11:37,510 --> 00:11:40,260
Vì vậy, thời gian chạy trường hợp xấu nhất ở đây là gì?

239
00:11:40,260 --> 00:11:43,210
Bạn có đoán big-O của m?

240
00:11:43,210 --> 00:11:44,686
Bạn muốn được bên phải.

241
00:11:44,686 --> 00:11:46,230
>> Làm thế nào về nhau?

242
00:11:46,230 --> 00:11:48,590
Hiện nay chúng tôi có một
vòng lặp bên trong một vòng lặp.

243
00:11:48,590 --> 00:11:50,905
Chúng tôi có một vòng ngoài
chạy từ số không đến p.

244
00:11:50,905 --> 00:11:54,630
Và chúng ta có một vòng lặp bên trong chạy
từ số không đến p, và bên trong đó,

245
00:11:54,630 --> 00:11:57,890
Tôi tuyên bố rằng cơ thể
vòng lặp chạy trong thời gian liên tục.

246
00:11:57,890 --> 00:12:02,330
Vì vậy, thời gian chạy trường hợp xấu nhất là gì
của đoạn này đặc biệt của mã?

247
00:12:02,330 --> 00:12:06,140
Vâng, một lần nữa, chúng ta có một
vòng ngoài mà chạy lần p.

248
00:12:06,140 --> 00:12:09,660
Và mỗi lần lặp time--
vòng lặp đó, thay.

249
00:12:09,660 --> 00:12:13,170
Chúng tôi có một vòng trong
mà cũng chạy lần p.

250
00:12:13,170 --> 00:12:16,900
Và sau đó bên trong đó, có các
hằng time-- ít đoạn đó.

251
00:12:16,900 --> 00:12:19,890
>> Vì vậy, nếu chúng ta có một vòng lặp bên ngoài mà
chạy p lần bên trong đó là

252
00:12:19,890 --> 00:12:22,880
một vòng lặp bên đó
chạy p times-- là gì

253
00:12:22,880 --> 00:12:26,480
trường hợp xấu nhất-runtime
của đoạn mã này?

254
00:12:26,480 --> 00:12:30,730
Bạn có đoán O lớn của p bình phương?

255
00:12:30,730 --> 00:12:31,690
>> Tôi Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Đây là CS50.

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