1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Phần 3 - thoải mái hơn]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Đại học Harvard]

3
00:00:05,070 --> 00:00:07,310
>> [Đây là CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Vì vậy, câu hỏi đầu tiên là lạ worded.

5
00:00:12,700 --> 00:00:17,480
GDB cho phép bạn "gỡ lỗi" một chương trình, nhưng cụ thể hơn, những gì hiện nó cho bạn làm gì?

6
00:00:17,480 --> 00:00:22,590
Tôi sẽ trả lời rằng một trong, và tôi không biết những gì là chính xác mong đợi,

7
00:00:22,590 --> 00:00:27,910
vì vậy tôi đoán đó là một cái gì đó dọc theo dòng của nó cho phép bạn từng bước

8
00:00:27,910 --> 00:00:31,540
đi bộ thông qua chương trình, tương tác với nó, các biến thay đổi, làm tất cả những điều này -

9
00:00:31,540 --> 00:00:34,270
về cơ bản hoàn toàn kiểm soát thực hiện của một chương trình

10
00:00:34,270 --> 00:00:38,410
và kiểm tra bất kỳ phần nào của việc thực hiện của chương trình.

11
00:00:38,410 --> 00:00:43,030
Vì vậy, những tính năng cho phép bạn gỡ lỗi thứ.

12
00:00:43,030 --> 00:00:44,830
Okay.

13
00:00:44,830 --> 00:00:50,520
Tại sao tìm kiếm nhị phân yêu cầu rằng một mảng được sắp xếp?

14
00:00:50,520 --> 00:00:53,360
Ai muốn trả lời điều đó?

15
00:00:56,120 --> 00:01:00,070
[Sinh viên] Bởi vì nó không làm việc nếu nó không được sắp xếp. >> Yeah. [Cười]

16
00:01:00,070 --> 00:01:04,910
Nếu nó không được sắp xếp, sau đó nó không thể tách nó ra

17
00:01:04,910 --> 00:01:07,850
và biết rằng tất cả mọi thứ bên trái là ít hơn và tất cả mọi thứ ở bên phải

18
00:01:07,850 --> 00:01:10,490
lớn hơn giá trị trung bình.

19
00:01:10,490 --> 00:01:12,790
Vì vậy, nó cần phải được sắp xếp.

20
00:01:12,790 --> 00:01:14,170
Okay.

21
00:01:14,170 --> 00:01:17,570
Tại sao là bong bóng sắp xếp trong O n bình phương?

22
00:01:17,570 --> 00:01:23,230
Có ai đầu tiên muốn cung cấp cho một cái nhìn tổng quan cao cấp rất nhanh chóng những bong bóng sắp xếp?

23
00:01:25,950 --> 00:01:33,020
[Sinh viên] Về cơ bản bạn đi qua mỗi phần tử và bạn kiểm tra các yếu tố đầu tiên.

24
00:01:33,020 --> 00:01:37,150
Nếu họ đang ra khỏi nơi bạn trao đổi chúng, sau đó bạn kiểm tra các yếu tố tiếp theo và như vậy.

25
00:01:37,150 --> 00:01:40,770
Khi bạn đến cuối, sau đó bạn biết rằng các phần tử lớn nhất được đặt ở cuối,

26
00:01:40,770 --> 00:01:42,750
do đó, bạn bỏ qua điều đó một sau đó bạn tiếp tục đi qua,

27
00:01:42,750 --> 00:01:48,490
và mỗi lần bạn phải kiểm tra một trong những yếu tố ít hơn cho đến khi bạn không có thay đổi. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Nó được gọi là bong bóng sắp xếp bởi vì nếu bạn lật mảng trên mặt của nó vì vậy nó lên và xuống, dọc,

29
00:01:58,470 --> 00:02:03,100
sau đó các giá trị lớn sẽ chìm xuống đáy và các giá trị nhỏ sẽ bong bóng lên đến đỉnh.

30
00:02:03,100 --> 00:02:05,210
Đó là làm thế nào nó có tên của nó.

31
00:02:05,210 --> 00:02:08,220
Và yeah, bạn chỉ cần đi qua.

32
00:02:08,220 --> 00:02:11,190
Bạn tiếp tục đi qua mảng, trao đổi các giá trị lớn hơn

33
00:02:11,190 --> 00:02:14,040
để có được các giá trị lớn nhất để phía dưới.

34
00:02:14,040 --> 00:02:17,500
>> Tại sao nó O n bình phương?

35
00:02:18,690 --> 00:02:24,620
Đầu tiên, không ai muốn nói lý do tại sao nó là O của n bình phương?

36
00:02:24,620 --> 00:02:28,760
[Sinh viên] Bởi vì cho mỗi lần chạy nó đi n lần.

37
00:02:28,760 --> 00:02:32,100
Bạn chỉ có thể chắc chắn rằng bạn đã thực hiện các yếu tố lớn nhất tất cả các con đường xuống,

38
00:02:32,100 --> 00:02:35,230
sau đó bạn phải lặp lại rằng đối với nhiều yếu tố. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Vì vậy, giữ trong tâm trí O lớn có nghĩa là gì và những gì phương tiện Omega lớn.

40
00:02:41,800 --> 00:02:50,560
O lớn như trên ràng buộc về cách làm chậm nó thực sự có thể chạy.

41
00:02:50,560 --> 00:02:58,990
Vì vậy, bằng cách nói rằng O của n bình phương, nó không phải là O của n hoặc khác nó sẽ có thể chạy

42
00:02:58,990 --> 00:03:02,640
trong thời gian tuyến tính, nhưng nó là O của n cubed

43
00:03:02,640 --> 00:03:06,390
bởi vì nó được bao bọc bởi O n cubed.

44
00:03:06,390 --> 00:03:12,300
Nếu nó được bao bọc bởi O n bình phương, sau đó nó giáp còn bởi n cubed.

45
00:03:12,300 --> 00:03:20,280
Vì vậy, nó là n bình phương, và trong trường hợp tồi tệ nhất tuyệt đối không thể làm tốt hơn so với n bình phương,

46
00:03:20,280 --> 00:03:22,830
đó là lý do tại sao nó là O n bình phương.

47
00:03:22,830 --> 00:03:31,200
Vì vậy, để xem toán học nhỏ như thế nào đi ra để được n bình phương,

48
00:03:31,200 --> 00:03:40,530
nếu chúng ta có năm điều trong danh sách của chúng tôi, lần đầu tiên có bao nhiêu giao dịch hoán đổi chúng ta có thể có khả năng cần phải thực hiện

49
00:03:40,530 --> 00:03:47,170
để có được điều này? Hãy thực sự chỉ -

50
00:03:47,170 --> 00:03:52,040
Làm thế nào nhiều giao dịch hoán đổi chúng ta sẽ phải thực hiện trong thời gian đầu tiên của loại bong bóng thông qua các mảng?

51
00:03:52,040 --> 00:03:53,540
[Sinh viên] n - 1. >> Yeah.

52
00:03:53,540 --> 00:03:58,340
>> Nếu có 5 yếu tố, chúng ta sẽ cần phải thực hiện n - 1.

53
00:03:58,340 --> 00:04:01,100
Sau đó, một trong những thứ hai có bao nhiêu giao dịch hoán đổi chúng ta sẽ phải thực hiện?

54
00:04:01,100 --> 00:04:03,440
[Sinh viên] n - 2. >> Yeah.

55
00:04:03,440 --> 00:04:11,640
Và thứ ba sẽ là n - 3, và sau đó để thuận tiện tôi sẽ viết cuối cùng hai

56
00:04:11,640 --> 00:04:15,270
như sau đó chúng ta sẽ cần phải thực hiện 2 giao dịch hoán đổi và trao đổi 1.

57
00:04:15,270 --> 00:04:19,899
Tôi đoán là người cuối cùng có thể hoặc có thể không thực sự cần phải xảy ra.

58
00:04:19,899 --> 00:04:22,820
Nó là một trao đổi? Tôi không biết.

59
00:04:22,820 --> 00:04:26,490
Vì vậy đây là tổng số tiền giao dịch hoán đổi hoặc ít nhất là so sánh bạn có để làm.

60
00:04:26,490 --> 00:04:29,910
Thậm chí nếu bạn không trao đổi, bạn vẫn cần phải so sánh các giá trị.

61
00:04:29,910 --> 00:04:33,910
Vì vậy, có n - 1 so sánh trong lần chạy đầu tiên thông qua các mảng.

62
00:04:33,910 --> 00:04:42,050
Nếu bạn sắp xếp lại những điều này, chúng ta hãy thực sự làm cho sáu điều mọi thứ chồng lên độc đáo,

63
00:04:42,050 --> 00:04:44,790
và sau đó tôi sẽ làm 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Vì vậy, chỉ cần sắp xếp lại số tiền này, chúng tôi muốn thấy chúng tôi làm cho bao nhiêu so sánh

65
00:04:49,910 --> 00:04:52,700
trong toàn bộ các thuật toán.

66
00:04:52,700 --> 00:04:56,550
Vì vậy, nếu chúng ta mang lại cho những kẻ ở đây,

67
00:04:56,550 --> 00:05:07,470
sau đó chúng tôi vẫn đang tổng hợp so sánh tuy nhiên nhiều người đã có.

68
00:05:07,470 --> 00:05:13,280
Nhưng nếu chúng ta tổng hợp những điều này và chúng tôi tổng hợp những điều này và chúng tôi tổng hợp các,

69
00:05:13,280 --> 00:05:18,130
nó vẫn là cùng một vấn đề. Chúng tôi chỉ tổng hợp những nhóm cụ thể.

70
00:05:18,130 --> 00:05:22,400
>> Vì vậy, bây giờ chúng tôi đang tổng hợp 3 n. Nó không phải chỉ là 3 của n.

71
00:05:22,400 --> 00:05:27,650
Nó luôn luôn sẽ là n / 2 n.

72
00:05:27,650 --> 00:05:29,430
Vì vậy, ở đây chúng tôi xảy ra để có 6.

73
00:05:29,430 --> 00:05:34,830
Nếu chúng ta có 10 điều, sau đó chúng ta có thể làm điều này nhóm cho 5 cặp khác nhau của sự vật

74
00:05:34,830 --> 00:05:37,180
và kết thúc với n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Vì vậy, bạn luôn luôn để có được n / 2 n, và do đó, điều này chúng tôi sẽ ghi nó ra bình phương / 2 n.

76
00:05:45,840 --> 00:05:48,890
Và do đó, mặc dù nó là yếu tố của một nửa, mà xảy ra để đi vào

77
00:05:48,890 --> 00:05:54,190
vì thực tế là thông qua mỗi lần lặp trên mảng, chúng tôi so sánh 1 ít

78
00:05:54,190 --> 00:05:58,040
vì vậy đó là làm thế nào chúng tôi nhận được hơn 2, nhưng nó vẫn còn n bình phương.

79
00:05:58,040 --> 00:06:01,650
Chúng tôi không quan tâm về các yếu tố liên tục của một nửa.

80
00:06:01,650 --> 00:06:07,760
Vì vậy, rất nhiều các công cụ O lớn như thế này dựa trên chỉ là loại việc sắp xếp của toán học,

81
00:06:07,760 --> 00:06:12,260
làm tiền số học và các công cụ loạt hình học,

82
00:06:12,260 --> 00:06:17,750
nhưng hầu hết trong số họ trong khóa học này là khá đơn giản.

83
00:06:17,750 --> 00:06:19,290
Okay.

84
00:06:19,290 --> 00:06:24,430
Tại sao chèn sắp xếp trong Omega của n? Omega có nghĩa là gì?

85
00:06:24,430 --> 00:06:27,730
Hai học sinh nói cùng một lúc - không thể hiểu] >> Vâng.

86
00:06:27,730 --> 00:06:30,630
Omega bạn có thể nghĩ là giới hạn thấp hơn.

87
00:06:30,630 --> 00:06:36,550
>> Vì vậy, không có vấn đề như thế nào hiệu quả chèn thuật toán sắp xếp của bạn,

88
00:06:36,550 --> 00:06:41,810
không phân biệt của danh sách là thông qua tại, nó luôn luôn phải so sánh ít nhất n vật

89
00:06:41,810 --> 00:06:44,620
hoặc nó có để lặp lại những thứ n.

90
00:06:44,620 --> 00:06:47,280
Tại sao vậy?

91
00:06:47,280 --> 00:06:51,190
[Sinh viên] Bởi vì nếu danh sách đã được sắp xếp, sau đó thông qua phiên đầu tiên

92
00:06:51,190 --> 00:06:54,080
bạn chỉ có thể đảm bảo rằng các phần tử đầu tiên là ít nhất,

93
00:06:54,080 --> 00:06:56,490
và lặp thứ hai, bạn chỉ có thể đảm bảo đầu tiên hai là

94
00:06:56,490 --> 00:07:00,010
bởi vì bạn không biết rằng phần còn lại của danh sách được sắp xếp. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Nếu bạn vượt qua trong một danh sách được sắp xếp hoàn toàn, ít nhất bạn phải đi qua tất cả các yếu tố

96
00:07:08,910 --> 00:07:12,180
để thấy rằng không có gì cần phải được di chuyển xung quanh.

97
00:07:12,180 --> 00:07:14,720
Vì vậy, đi qua danh sách và nói oh, điều này đã được sắp xếp,

98
00:07:14,720 --> 00:07:18,240
nó không thể cho bạn biết nó được sắp xếp cho đến khi bạn kiểm tra từng phần tử

99
00:07:18,240 --> 00:07:20,660
để thấy rằng họ đang có trong thứ tự sắp xếp.

100
00:07:20,660 --> 00:07:25,290
Vì vậy, các ràng buộc về sắp xếp chèn là Omega của n.

101
00:07:25,290 --> 00:07:28,210
Trường hợp xấu nhất là những gì thời gian chạy của hợp nhất loại,

102
00:07:28,210 --> 00:07:31,390
trường hợp xấu nhất là O lớn một lần nữa?

103
00:07:31,390 --> 00:07:37,660
Vì vậy, trong trường hợp kịch bản tồi tệ nhất, hợp nhất loại chạy như thế nào?

104
00:07:42,170 --> 00:07:43,690
[Sinh viên] N log n. >> Yeah.

105
00:07:43,690 --> 00:07:49,990
Nhanh nhất các thuật toán phân loại chung là n log n. Bạn không thể làm tốt hơn.

106
00:07:51,930 --> 00:07:55,130
>> Có những trường hợp đặc biệt, và nếu chúng ta có ngày hôm nay - thời gian nhưng chúng tôi có thể won't

107
00:07:55,130 --> 00:07:59,330
chúng ta có thể thấy một mà không tốt hơn so với n log n.

108
00:07:59,330 --> 00:08:04,050
Tuy nhiên, trong trường hợp chung, bạn không thể làm tốt hơn so với n log n.

109
00:08:04,050 --> 00:08:09,680
Và hợp nhất các loại sẽ xảy ra là một trong những bạn nên biết cho khóa học này là n log n.

110
00:08:09,680 --> 00:08:13,260
Và vì vậy chúng tôi thực sự sẽ được thực hiện mà ngày hôm nay.

111
00:08:13,260 --> 00:08:18,070
Và cuối cùng, không quá ba câu, công tác loại lựa chọn như thế nào?

112
00:08:18,070 --> 00:08:20,370
Không ai muốn trả lời, và tôi sẽ đếm các câu của bạn

113
00:08:20,370 --> 00:08:22,390
bởi vì nếu bạn đi trên 3 -

114
00:08:25,530 --> 00:08:28,330
Có ai nhớ loại lựa chọn?

115
00:08:31,280 --> 00:08:37,809
Lựa chọn loại thường là khá dễ dàng để nhớ từ tên.

116
00:08:37,809 --> 00:08:45,350
Bạn chỉ cần lặp qua mảng tìm thấy bất cứ điều gì có giá trị lớn nhất hoặc nhỏ nhất -

117
00:08:45,350 --> 00:08:47,290
để bất cứ điều gì bạn đang phân loại.

118
00:08:47,290 --> 00:08:50,750
Vì vậy, hãy nói rằng chúng tôi đang phân loại từ nhỏ nhất đến lớn nhất.

119
00:08:50,750 --> 00:08:55,250
Bạn lặp qua mảng, tìm kiếm bất cứ điều gì các yếu tố tối thiểu,

120
00:08:55,250 --> 00:08:59,750
chọn nó và sau đó chỉ cần trao đổi nó bất cứ điều gì ở nơi đầu tiên.

121
00:08:59,750 --> 00:09:04,090
Và sau đó trên đèo thứ hai trên mảng, tìm kiếm các yếu tố tối thiểu một lần nữa,

122
00:09:04,090 --> 00:09:07,490
chọn nó và sau đó trao đổi nó với những gì ở vị trí thứ hai.

123
00:09:07,490 --> 00:09:10,650
Vì vậy, chúng tôi chỉ chọn và lựa chọn các giá trị tối thiểu

124
00:09:10,650 --> 00:09:16,050
và chèn chúng vào mặt trước của mảng cho đến khi nó được sắp xếp.

125
00:09:19,210 --> 00:09:21,560
Câu hỏi về điều đó?

126
00:09:21,560 --> 00:09:25,710
>> Đây chắc chắn xuất hiện trong các hình thức mà bạn phải điền vào khi bạn đang trình pset.

127
00:09:29,010 --> 00:09:32,360
Đó là về cơ bản các câu trả lời cho những người.

128
00:09:32,360 --> 00:09:34,230
Được rồi, vì vậy bây giờ mã hóa vấn đề.

129
00:09:34,230 --> 00:09:40,140
Tôi đã gửi qua email - bất cứ ai không nhận được rằng email? Okay.

130
00:09:40,140 --> 00:09:46,630
Tôi đã gửi qua email không gian mà chúng ta sẽ được sử dụng,

131
00:09:46,630 --> 00:09:52,120
và nếu bạn nhấn chuột vào tên của tôi - vì vậy tôi nghĩ rằng tôi sẽ được ở phía dưới

132
00:09:52,120 --> 00:09:57,170
vì r ngược - nhưng nếu bạn nhấn chuột vào tên của tôi, bạn sẽ thấy 2 phiên bản.

133
00:09:57,170 --> 00:10:02,650
Phiên bản 1 sẽ được tôi đã sao chép và dán mã vào không gian

134
00:10:02,650 --> 00:10:06,900
cho việc tìm kiếm, bạn sẽ phải thực hiện.

135
00:10:06,900 --> 00:10:10,540
Và sửa đổi 2 sẽ được điều sắp xếp mà chúng ta thực hiện sau đó.

136
00:10:10,540 --> 00:10:15,770
Vì vậy, bạn có thể bấm vào sửa đổi của tôi 1 và làm việc từ đó.

137
00:10:17,350 --> 00:10:22,060
Và bây giờ chúng tôi muốn thực hiện tìm kiếm nhị phân.

138
00:10:22,060 --> 00:10:26,470
>> Có ai muốn chỉ cần cung cấp cho một lời giải thích giả cấp cao

139
00:10:26,470 --> 00:10:31,440
của những gì chúng ta sẽ phải làm cho tìm kiếm? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Sinh viên] Bạn chỉ mất giữa của mảng và xem những gì bạn đang tìm kiếm

141
00:10:36,170 --> 00:10:38,650
là ít hơn hoặc nhiều hơn thế.

142
00:10:38,650 --> 00:10:41,080
Và nếu nó ít hơn, bạn đi đến một nửa đó là ít,

143
00:10:41,080 --> 00:10:44,750
và nếu nó nhiều hơn, bạn đi đến một nửa sau đó là nhiều và bạn lặp lại cho đến khi bạn chỉ nhận được một điều.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Yeah.

145
00:10:46,570 --> 00:10:51,320
Chú ý rằng số mảng của chúng tôi đã được sắp xếp,

146
00:10:51,320 --> 00:10:57,190
và do đó có nghĩa rằng chúng ta có thể tận dụng lợi thế đó và chúng tôi lần đầu tiên có thể kiểm tra,

147
00:10:57,190 --> 00:11:00,390
okay, tôi đang tìm cho số 50.

148
00:11:00,390 --> 00:11:03,720
Vì vậy, tôi có thể đi vào giữa.

149
00:11:03,720 --> 00:11:07,380
Trung là khó để xác định khi nó là một số thậm chí của vật,

150
00:11:07,380 --> 00:11:10,820
nhưng chúng ta hãy chỉ nói rằng chúng ta sẽ luôn luôn cắt ngắn để giữa.

151
00:11:10,820 --> 00:11:14,420
Vì vậy, ở đây chúng tôi có 8 điều, do đó, giữa sẽ là 16.

152
00:11:14,420 --> 00:11:17,330
Tôi đang tìm cho 50, do đó, 50 là lớn hơn 16.

153
00:11:17,330 --> 00:11:21,310
Vì vậy, bây giờ tôi về cơ bản có thể xử lý mảng của tôi như những yếu tố này.

154
00:11:21,310 --> 00:11:23,450
Tôi có thể vứt bỏ tất cả mọi thứ từ trên 16.

155
00:11:23,450 --> 00:11:27,440
Bây giờ mảng của tôi chỉ là 4 yếu tố này, tôi nhắc lại.

156
00:11:27,440 --> 00:11:31,910
Vì vậy, sau đó tôi muốn tìm giữa một lần nữa, đó là sẽ là 42.

157
00:11:31,910 --> 00:11:34,730
42 là ít hơn 50, vì vậy tôi có thể vứt bỏ hai yếu tố này.

158
00:11:34,730 --> 00:11:36,890
Đây là mảng còn lại của mình.

159
00:11:36,890 --> 00:11:38,430
Tôi sẽ tìm thấy giữa một lần nữa.

160
00:11:38,430 --> 00:11:42,100
Tôi đoán 50 là một ví dụ xấu bởi vì tôi đã luôn luôn ném đi mọi thứ bên trái,

161
00:11:42,100 --> 00:11:48,280
nhưng bằng biện pháp tương tự, nếu tôi đang tìm kiếm một cái gì đó

162
00:11:48,280 --> 00:11:52,100
và nó ít hơn so với các yếu tố tôi hiện đang xem xét,

163
00:11:52,100 --> 00:11:55,080
sau đó tôi sẽ vứt bỏ tất cả mọi thứ bên phải.

164
00:11:55,080 --> 00:11:58,150
Vì vậy, bây giờ chúng tôi cần phải thực hiện điều đó.

165
00:11:58,150 --> 00:12:02,310
Chú ý rằng chúng ta cần phải vượt qua trong kích thước.

166
00:12:02,310 --> 00:12:06,730
Chúng tôi cũng có thể không cần phải cứng mã kích thước.

167
00:12:06,730 --> 00:12:11,640
Vì vậy, nếu chúng tôi nhận được thoát khỏi đó # xác định

168
00:12:19,630 --> 00:12:21,430
Okay.

169
00:12:21,430 --> 00:12:27,180
Làm thế nào tôi có thể độc đáo tìm ra những gì kích thước của mảng số hiện nay là?

170
00:12:27,180 --> 00:12:30,950
>> Làm thế nào nhiều yếu tố trong mảng số?

171
00:12:30,950 --> 00:12:33,630
[Sinh viên] số, khung, chiều dài?

172
00:12:33,630 --> 00:12:36,600
[Bowden] không tồn tại trong C.

173
00:12:36,600 --> 00:12:38,580
Cần chiều dài.

174
00:12:38,580 --> 00:12:42,010
Mảng không có tài sản, do đó, không có tài sản dài của mảng

175
00:12:42,010 --> 00:12:45,650
mà chỉ cần sẽ cung cấp cho bạn lâu dài tuy nhiên nó sẽ xảy ra.

176
00:12:48,180 --> 00:12:51,620
[Sinh viên] Xem nó có bao nhiêu bộ nhớ và phân chia bao nhiêu - >> Vâng.

177
00:12:51,620 --> 00:12:55,810
Vì vậy, làm thế nào chúng ta có thể xem nó có bao nhiêu bộ nhớ? >> [Sinh viên] sizeof. >> Yeah, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof là các nhà điều hành đó là sẽ trở lại kích thước của các mảng số.

179
00:13:01,680 --> 00:13:10,060
Và đó sẽ là các số nguyên tuy nhiên nhiều lần kích thước của một số nguyên

180
00:13:10,060 --> 00:13:14,050
vì đó là bao nhiêu bộ nhớ nó thực sự chiếm.

181
00:13:14,050 --> 00:13:17,630
Vì vậy, nếu tôi muốn có số thứ trong mảng,

182
00:13:17,630 --> 00:13:20,560
sau đó tôi sẽ muốn chia bởi kích thước của một số nguyên.

183
00:13:22,820 --> 00:13:26,010
Okay. Vì vậy, cho phép tôi vượt qua kích thước ở đây.

184
00:13:26,010 --> 00:13:29,430
Tại sao tôi cần phải vượt qua kích thước ở tất cả?

185
00:13:29,430 --> 00:13:38,570
Tại sao tôi không thể chỉ cần làm ở đây int size = sizeof (haystack) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Tại sao điều này không làm việc?

187
00:13:41,490 --> 00:13:44,470
[Sinh viên] Nó không phải là một biến toàn cầu.

188
00:13:44,470 --> 00:13:51,540
Bowden] Haystack tồn tại và chúng ta đang đi qua với số lượng như haystack,

189
00:13:51,540 --> 00:13:54,700
và đây là loại tiên báo về những gì sắp tới. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Sinh viên] Haystack chỉ là tham chiếu đến nó, vì vậy nó sẽ trở lại tham khảo đó là lớn như thế nào.

191
00:14:00,170 --> 00:14:02,150
Yeah.

192
00:14:02,150 --> 00:14:09,000
Tôi nghi ngờ trong bài giảng mà bạn đã nhìn thấy ngăn xếp nhưng thực sự, phải không?

193
00:14:09,000 --> 00:14:11,270
Chúng tôi đã chỉ nói về nó.

194
00:14:11,270 --> 00:14:16,090
Vì vậy, ngăn xếp là nơi mà tất cả các biến của bạn sẽ được lưu trữ.

195
00:14:16,090 --> 00:14:19,960
>> Bất kỳ bộ nhớ đó là phân bổ cho các biến địa phương trong ngăn xếp,

196
00:14:19,960 --> 00:14:24,790
và chức năng cho từng không gian riêng của mình trên stack, stack frame của nó là những gì nó được gọi là.

197
00:14:24,790 --> 00:14:31,590
Vì vậy, chính có stack frame của nó, và bên trong của nó sẽ tồn tại mảng này số,

198
00:14:31,590 --> 00:14:34,270
và nó sẽ là sizeof kích cỡ (số).

199
00:14:34,270 --> 00:14:38,180
Nó sẽ có kích thước của các số chia cho kích thước của các yếu tố,

200
00:14:38,180 --> 00:14:42,010
nhưng đó là tất cả cuộc sống trong khung chính stack.

201
00:14:42,010 --> 00:14:45,190
Khi chúng tôi gọi là tìm kiếm, tìm kiếm được khung stack riêng của mình,

202
00:14:45,190 --> 00:14:48,840
không gian riêng của mình để lưu trữ tất cả các biến địa phương của mình.

203
00:14:48,840 --> 00:14:56,420
Tuy nhiên, lập luận này - vì vậy haystack không phải là một bản sao của toàn bộ mảng này.

204
00:14:56,420 --> 00:15:00,990
Chúng tôi không vượt qua trong toàn bộ mảng như là một bản sao vào tìm kiếm.

205
00:15:00,990 --> 00:15:04,030
Nó chỉ cần vượt qua một tham chiếu đến mảng đó.

206
00:15:04,030 --> 00:15:11,470
Vì vậy, tìm kiếm có thể truy cập vào những con số này thông qua tham chiếu này.

207
00:15:11,470 --> 00:15:17,100
Nó vẫn còn truy cập vào những điều mà sống bên trong của khung chính stack,

208
00:15:17,100 --> 00:15:22,990
nhưng về cơ bản, khi chúng tôi nhận được cho con trỏ, mà nên được sớm,

209
00:15:22,990 --> 00:15:24,980
đây là những gì con trỏ.

210
00:15:24,980 --> 00:15:29,400
Con trỏ chỉ là tài liệu tham khảo cho những thứ, và bạn có thể sử dụng con trỏ để truy cập mọi thứ

211
00:15:29,400 --> 00:15:32,030
là trong khung stack những thứ khác.

212
00:15:32,030 --> 00:15:37,660
Vì vậy, dù các con số là địa phương chính, chúng tôi vẫn có thể truy cập nó thông qua con trỏ này.

213
00:15:37,660 --> 00:15:41,770
Nhưng kể từ khi nó chỉ là một con trỏ và nó chỉ là một tài liệu tham khảo,

214
00:15:41,770 --> 00:15:45,040
sizeof (haystack) chỉ trả về kích thước của các tài liệu tham khảo chính nó.

215
00:15:45,040 --> 00:15:47,950
Nó không trả lại kích thước của điều nó trỏ đến.

216
00:15:47,950 --> 00:15:51,110
Nó không trả lại kích thước thực tế của các số.

217
00:15:51,110 --> 00:15:55,660
Và do đó, điều này không phải là đi làm việc như chúng ta muốn nó.

218
00:15:55,660 --> 00:15:57,320
>> Câu hỏi về điều đó?

219
00:15:57,320 --> 00:16:03,250
Con trỏ sẽ được đi vào chi tiết nhiều hơn đáng kể đẫm máu trong tuần tới.

220
00:16:06,750 --> 00:16:13,740
Và đây là lý do tại sao rất nhiều những điều mà bạn biết, sự việc tìm kiếm nhiều nhất hoặc những thứ loại,

221
00:16:13,740 --> 00:16:16,990
họ đang gần như tất cả sẽ cần phải có kích thước thực tế của mảng,

222
00:16:16,990 --> 00:16:20,440
bởi vì trong C, chúng tôi không có ý tưởng những gì các kích thước của mảng.

223
00:16:20,440 --> 00:16:22,720
Bạn cần phải tự vượt qua nó.

224
00:16:22,720 --> 00:16:27,190
Và bạn có thể không tự vượt qua trong toàn bộ mảng bởi vì bạn chỉ cần đi qua các tài liệu tham khảo

225
00:16:27,190 --> 00:16:30,390
và nó không thể có được kích thước từ tài liệu tham khảo.

226
00:16:30,390 --> 00:16:32,300
Okay.

227
00:16:32,300 --> 00:16:38,160
Vì vậy, bây giờ chúng tôi muốn thực hiện những gì đã được giải thích trước.

228
00:16:38,160 --> 00:16:41,530
Bạn có thể làm việc trên nó trong một phút,

229
00:16:41,530 --> 00:16:45,250
và bạn không phải lo lắng về việc nhận được tất cả mọi thứ làm việc hoàn hảo 100%.

230
00:16:45,250 --> 00:16:51,410
Chỉ cần viết mã giả một nửa để làm thế nào bạn nghĩ rằng nó sẽ làm việc.

231
00:16:52,000 --> 00:16:53,630
Okay.

232
00:16:53,630 --> 00:16:56,350
Không cần phải hoàn toàn thực hiện với điều này.

233
00:16:56,350 --> 00:17:02,380
Nhưng không ai cảm thấy thoải mái với những gì họ có cho đến nay,

234
00:17:02,380 --> 00:17:05,599
giống như một cái gì đó, chúng ta có thể làm việc với nhau?

235
00:17:05,599 --> 00:17:09,690
Có ai muốn làm tình nguyện? Hoặc tôi sẽ chọn ngẫu nhiên.

236
00:17:12,680 --> 00:17:18,599
Nó không có được quyền bởi bất kỳ biện pháp nào, nhưng một cái gì đó chúng ta có thể sửa đổi vào một trạng thái làm việc.

237
00:17:18,599 --> 00:17:20,720
[Sinh viên] Chắc chắn rồi. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Vì vậy, bạn có thể lưu các sửa đổi bằng cách nhấn vào biểu tượng Save ít.

239
00:17:27,220 --> 00:17:29,950
Bạn đang Ramya, phải không? >> [Sinh viên] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Vì vậy, bây giờ tôi có thể xem sửa đổi của bạn và tất cả mọi người có thể kéo lên sửa đổi.

241
00:17:35,140 --> 00:17:38,600
Và ở đây chúng tôi có - Được rồi.

242
00:17:38,600 --> 00:17:43,160
Vì vậy, Ramya đi với các giải pháp đệ quy, mà chắc chắn là một giải pháp hợp lệ.

243
00:17:43,160 --> 00:17:44,970
Có hai cách bạn có thể làm vấn đề này.

244
00:17:44,970 --> 00:17:48,060
Bạn có thể làm điều đó lặp đi lặp lại hoặc đệ quy.

245
00:17:48,060 --> 00:17:53,860
Hầu hết các vấn đề bạn gặp phải có thể được thực hiện đệ quy cũng có thể được thực hiện lặp đi lặp lại.

246
00:17:53,860 --> 00:17:58,510
Vì vậy, ở đây chúng tôi đã thực hiện nó đệ quy.

247
00:17:58,510 --> 00:18:03,730
>> Có ai đó muốn xác định những gì nó có nghĩa là để làm cho một hàm đệ quy?

248
00:18:07,210 --> 00:18:08,920
[Sinh viên] Khi bạn có một hàm gọi chính nó

249
00:18:08,920 --> 00:18:13,470
và sau đó gọi chính nó cho đến khi nó đi ra với đúng sự thật và đúng sự thật. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
Một chức năng đệ quy chỉ là một chức năng mà tự gọi mình.

251
00:18:17,680 --> 00:18:24,140
Có ba điều lớn mà một hàm đệ quy phải có.

252
00:18:24,140 --> 00:18:27,310
Đầu tiên là rõ ràng, nó gọi chính nó.

253
00:18:27,310 --> 00:18:29,650
Thứ hai là trường hợp cơ sở.

254
00:18:29,650 --> 00:18:33,390
Vì vậy, tại một số điểm chức năng cần phải ngừng kêu gọi chính nó,

255
00:18:33,390 --> 00:18:35,610
và đó là trường hợp cơ sở.

256
00:18:35,610 --> 00:18:43,860
Vì vậy, ở đây chúng tôi biết rằng chúng tôi nên dừng lại, chúng ta nên từ bỏ tìm kiếm của chúng tôi

257
00:18:43,860 --> 00:18:48,150
khi bắt đầu bằng kết thúc và chúng ta sẽ đi qua đó có nghĩa là gì.

258
00:18:48,150 --> 00:18:52,130
Nhưng cuối cùng, điều cuối cùng mà quan trọng cho các chức năng đệ quy:

259
00:18:52,130 --> 00:18:59,250
các chức năng bằng cách nào đó phải tiếp cận trường hợp cơ sở.

260
00:18:59,250 --> 00:19:04,140
Cũng giống như nếu bạn không thực sự cập nhật bất cứ điều gì khi bạn thực hiện cuộc gọi thứ hai đệ quy,

261
00:19:04,140 --> 00:19:07,880
nếu bạn đang nghĩa đen chỉ kêu gọi các chức năng một lần nữa cùng với các đối số

262
00:19:07,880 --> 00:19:10,130
và không có biến toàn cầu đã thay đổi hoặc bất cứ điều gì,

263
00:19:10,130 --> 00:19:14,430
bạn sẽ không bao giờ đến trường hợp cơ sở, trong trường hợp đó là xấu.

264
00:19:14,430 --> 00:19:17,950
Nó sẽ là một đệ quy vô hạn và tràn một chồng.

265
00:19:17,950 --> 00:19:24,330
Nhưng ở đây chúng ta thấy rằng bản cập nhật đang diễn ra kể từ khi chúng tôi đang được cập nhật bắt đầu + end / 2,

266
00:19:24,330 --> 00:19:28,180
chúng tôi cập nhật các đối số kết thúc ở đây, chúng tôi cập nhật các đối số bắt đầu ở đây.

267
00:19:28,180 --> 00:19:32,860
Vì vậy, trong tất cả các cuộc gọi đệ quy, chúng tôi đang được cập nhật một cái gì đó. Okay.

268
00:19:32,860 --> 00:19:38,110
Bạn có muốn đi bộ chúng tôi thông qua các giải pháp của bạn? >> Chắc chắn rồi.

269
00:19:38,110 --> 00:19:44,270
Tôi đang sử dụng SearchHelp để mỗi khi tôi thực hiện cuộc gọi chức năng này

270
00:19:44,270 --> 00:19:47,910
Tôi có một khởi đầu, nơi tôi đang tìm kiếm trong mảng và kết thúc

271
00:19:47,910 --> 00:19:49,380
nơi tôi đang tìm các mảng.

272
00:19:49,380 --> 00:19:55,330
>> Tại mỗi bước mà nó nói nó là nhân tố trung, đó là bắt đầu + kết thúc / 2,

273
00:19:55,330 --> 00:19:58,850
là bằng những gì chúng tôi đang tìm kiếm?

274
00:19:58,850 --> 00:20:04,650
Và nếu được, sau đó chúng tôi tìm thấy nó, và tôi đoán được thông qua các cấp độ của đệ quy.

275
00:20:04,650 --> 00:20:12,540
Và nếu đó là không đúng sự thật, sau đó chúng tôi kiểm tra xem giá trị đó giữa của mảng là quá lớn,

276
00:20:12,540 --> 00:20:19,320
trong trường hợp đó chúng ta nhìn vào nửa bên trái của mảng bằng cách đi từ đầu đến chỉ số trung bình.

277
00:20:19,320 --> 00:20:22,710
Và nếu không chúng tôi làm nửa cuối.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Okay.

279
00:20:24,740 --> 00:20:27,730
Nghe được đó.

280
00:20:27,730 --> 00:20:36,640
Được rồi, do một vài điều, và trên thực tế, đây là một điều rất cao cấp

281
00:20:36,640 --> 00:20:41,270
rằng bạn sẽ không bao giờ cần biết cho khóa học này, nhưng nó là sự thật.

282
00:20:41,270 --> 00:20:46,080
Chức năng đệ quy, bạn luôn nghe thấy rằng họ là một việc xấu

283
00:20:46,080 --> 00:20:51,160
bởi vì nếu bạn đệ quy gọi cho mình quá nhiều lần, bạn sẽ có được tràn stack

284
00:20:51,160 --> 00:20:54,990
vì, như tôi đã nói, tất cả các chức năng được khung stack riêng của mình.

285
00:20:54,990 --> 00:20:59,500
Vì vậy, mỗi cuộc gọi của chức năng đệ quy được khung stack riêng của mình.

286
00:20:59,500 --> 00:21:04,140
Vì vậy, nếu bạn thực hiện 1.000 cuộc gọi đệ quy, bạn nhận được 1.000 khung stack,

287
00:21:04,140 --> 00:21:08,390
và nhanh chóng dẫn đến khung stack và những thứ quá nhiều mà chỉ vỡ.

288
00:21:08,390 --> 00:21:13,480
Vì vậy, đó là lý do tại sao chức năng đệ quy nói chung là xấu.

289
00:21:13,480 --> 00:21:19,370
Nhưng có một tập hợp con tốt đẹp của các chức năng đệ quy được gọi là chức năng đệ quy đuôi,

290
00:21:19,370 --> 00:21:26,120
và điều này sẽ xảy ra là một ví dụ về một trong những nơi mà nếu trình biên dịch thông báo này

291
00:21:26,120 --> 00:21:29,920
và nó nên, tôi nghĩ rằng Clang nếu bạn vượt qua nó-O2 cờ

292
00:21:29,920 --> 00:21:33,250
sau đó nó sẽ thông báo này là đệ quy đuôi và làm cho những điều tốt đẹp.

293
00:21:33,250 --> 00:21:40,050
>> Nó sẽ sử dụng lại cùng một khung stack hơn và hơn nữa cho mỗi cuộc gọi đệ quy.

294
00:21:40,050 --> 00:21:47,010
Và như vậy kể từ khi bạn đang sử dụng cùng một stack frame, bạn không cần phải lo lắng về

295
00:21:47,010 --> 00:21:51,690
bao giờ ngăn xếp tràn, và cùng một lúc, như bạn nói,

296
00:21:51,690 --> 00:21:56,380
một khi bạn trở lại đúng, sau đó nó đã trở lại tất cả các khung stack

297
00:21:56,380 --> 00:22:01,740
và các cuộc gọi ngày 10 đến SearchHelp để quay trở lại lần thứ 9, đã trở lại 8.

298
00:22:01,740 --> 00:22:05,360
Vì vậy, mà không cần phải xảy ra khi các chức năng đệ quy đuôi.

299
00:22:05,360 --> 00:22:13,740
Và do đó, những gì làm cho chức năng đệ quy đuôi là thông báo cho bất kỳ cuộc gọi cho searchHelp

300
00:22:13,740 --> 00:22:18,470
các cuộc gọi đệ quy mà nó làm cho nó trở về.

301
00:22:18,470 --> 00:22:25,290
Vì vậy, trong cuộc gọi đầu tiên SearchHelp, chúng tôi ngay lập tức quay trở lại sai,

302
00:22:25,290 --> 00:22:29,590
ngay lập tức trở lại đúng, hoặc chúng tôi thực hiện cuộc gọi đệ quy để SearchHelp

303
00:22:29,590 --> 00:22:33,810
nơi những gì chúng tôi đang trở về là gì mà cuộc gọi đang trở lại.

304
00:22:33,810 --> 00:22:51,560
Và chúng ta không thể làm điều này nếu chúng ta đã làm một cái gì đó giống như int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
chỉ là một số thay đổi ngẫu nhiên.

306
00:22:55,440 --> 00:23:01,470
>> Vì vậy, bây giờ gọi đệ quy, int x = SearchHelp gọi đệ quy,

307
00:23:01,470 --> 00:23:05,740
không còn là đệ quy đuôi bởi vì nó thực sự không phải trả lại

308
00:23:05,740 --> 00:23:10,400
trở lại trước một khung stack để cuộc gọi trước đến chức năng

309
00:23:10,400 --> 00:23:13,040
sau đó có thể làm một cái gì đó với giá trị trả về.

310
00:23:13,040 --> 00:23:22,190
Vì vậy, đây không phải là đệ quy đuôi, nhưng những gì chúng ta có trước đây là độc đáo đệ quy đuôi. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Sinh viên] Nếu không phải là trường hợp cơ sở thứ hai được kiểm tra

312
00:23:27,000 --> 00:23:30,640
bởi vì có thể là một tình huống nơi mà khi bạn vượt qua các đối số

313
00:23:30,640 --> 00:23:35,770
bạn đã bắt đầu = kết thúc, nhưng họ là những giá trị kim.

314
00:23:35,770 --> 00:23:47,310
Các câu hỏi đã không thể chúng tôi chạy vào trường hợp cuối cùng là giá trị kim

315
00:23:47,310 --> 00:23:52,000
hoặc bắt đầu = kết thúc, một cách thích hợp, bắt đầu = kết thúc

316
00:23:52,000 --> 00:23:59,480
và bạn đã không thực sự kiểm tra giá trị cụ thể nào được nêu ra,

317
00:23:59,480 --> 00:24:03,910
sau đó bắt đầu + end / 2 là chỉ cần đi được cùng một giá trị.

318
00:24:03,910 --> 00:24:07,890
Nhưng chúng tôi đã quay trở lại sai lầm và chúng tôi không bao giờ thực sự kiểm tra các giá trị.

319
00:24:07,890 --> 00:24:14,240
Vì vậy, ít nhất, trong cuộc gọi đầu tiên, nếu kích thước là 0, sau đó chúng tôi muốn quay trở lại sai.

320
00:24:14,240 --> 00:24:17,710
Nhưng nếu kích thước là 1, sau đó bắt đầu được sẽ không kết thúc bằng,

321
00:24:17,710 --> 00:24:19,820
và ít nhất chúng ta sẽ kiểm tra một yếu tố.

322
00:24:19,820 --> 00:24:26,750
Nhưng tôi nghĩ rằng bạn là đúng trong đó chúng ta có thể kết thúc trong một trường hợp bắt đầu + end / 2,

323
00:24:26,750 --> 00:24:31,190
bắt đầu kết thúc lên được giống như là bắt đầu + kết thúc / 2,

324
00:24:31,190 --> 00:24:35,350
nhưng chúng tôi không bao giờ thực sự kiểm tra yếu tố đó.

325
00:24:35,350 --> 00:24:44,740
>> Vì vậy, nếu chúng tôi kiểm tra đầu tiên là yếu tố giữa các giá trị mà chúng ta đang tìm kiếm,

326
00:24:44,740 --> 00:24:47,110
sau đó chúng tôi có thể ngay lập tức trở lại đúng sự thật.

327
00:24:47,110 --> 00:24:50,740
Khác nếu chúng bằng nhau, sau đó không có điểm trong việc tiếp tục

328
00:24:50,740 --> 00:24:58,440
kể từ khi chúng tôi chỉ để cập nhật cho một trường hợp, nơi chúng tôi đang ở trên một mảng duy nhất phần tử.

329
00:24:58,440 --> 00:25:01,110
Nếu đó không phải là yếu tố duy nhất mà chúng ta đang tìm kiếm,

330
00:25:01,110 --> 00:25:03,530
sau đó tất cả mọi thứ là sai. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Sinh viên] Cái này là kể từ khi kích thước thực sự là lớn hơn số phần tử trong mảng

332
00:25:08,900 --> 00:25:13,070
đã có bù đắp - >> tự như vậy, kích thước -

333
00:25:13,070 --> 00:25:19,380
[Sinh viên] nếu mảng là kích thước 0 thì SearchHelp sẽ thực sự kiểm tra đống cỏ khô từ 0

334
00:25:19,380 --> 00:25:21,490
cuộc gọi đầu tiên.

335
00:25:21,490 --> 00:25:25,300
Mảng có kích thước 0, 0 - >> Vâng.

336
00:25:25,300 --> 00:25:30,750
Có một điều mà nó có thể là tốt. Hãy suy nghĩ.

337
00:25:30,750 --> 00:25:40,120
Vì vậy, nếu các mảng có 10 yếu tố và một trong những trung chúng ta sẽ kiểm tra là chỉ số 5,

338
00:25:40,120 --> 00:25:45,700
vì vậy chúng tôi đang kiểm tra 5, và hãy nói rằng giá trị nhỏ.

339
00:25:45,700 --> 00:25:50,720
Vì vậy, chúng tôi đang ném tất cả mọi thứ từ 5 trở đi.

340
00:25:50,720 --> 00:25:54,030
Vì vậy, bắt đầu + kết thúc / 2 là có được kết thúc mới của chúng tôi,

341
00:25:54,030 --> 00:25:57,450
Vì vậy, yeah, nó luôn luôn ở ngoài cuối của mảng.

342
00:25:57,450 --> 00:26:03,570
Nếu đó là một trường hợp nếu nó là chẵn hoặc lẻ, sau đó chúng tôi sẽ kiểm tra, nói rằng, 4,

343
00:26:03,570 --> 00:26:05,770
nhưng chúng tôi vẫn ném đi

344
00:26:05,770 --> 00:26:13,500
Vì vậy, yeah, cuối cùng là luôn luôn có được vượt quá thực tế của mảng.

345
00:26:13,500 --> 00:26:18,350
Vì vậy, các yếu tố mà chúng tôi đang tập trung vào, cuối cùng là luôn luôn có được một sau đó.

346
00:26:18,350 --> 00:26:24,270
Và như vậy nếu bắt đầu không bao giờ kết thúc bằng, chúng tôi đang trong một mảng có kích thước 0.

347
00:26:24,270 --> 00:26:35,600
>> Những điều khác tôi đã suy nghĩ là chúng tôi đang được cập nhật bắt đầu được bắt đầu + kết thúc / 2,

348
00:26:35,600 --> 00:26:44,020
vì vậy đây là trường hợp mà tôi đang gặp rắc rối với nơi bắt đầu + kết thúc / 2

349
00:26:44,020 --> 00:26:46,820
là yếu tố chúng tôi đang kiểm tra.

350
00:26:46,820 --> 00:26:58,150
Hãy nói rằng chúng tôi đã có 10-phần tử mảng. Sao cũng được.

351
00:26:58,150 --> 00:27:03,250
Vì vậy, bắt đầu + kết thúc / 2 là có được một cái gì đó như thế này,

352
00:27:03,250 --> 00:27:07,060
và nếu đó không phải là giá trị, nói rằng chúng ta muốn cập nhật.

353
00:27:07,060 --> 00:27:10,060
Giá trị lớn, vì vậy chúng tôi muốn tìm một nửa của mảng này.

354
00:27:10,060 --> 00:27:15,910
Vì vậy, làm thế nào chúng tôi cập nhật bắt đầu, chúng tôi đang cập nhật bắt đầu đến nay là yếu tố này.

355
00:27:15,910 --> 00:27:23,790
Nhưng điều này vẫn có thể làm việc, hoặc ít nhất, bạn có thể làm bắt đầu + kết thúc / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Sinh viên] Bạn không cần phải được bắt đầu + end không nghe được] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Chúng tôi đã kiểm tra yếu tố này và biết nó không phải là cái mà chúng ta đang tìm kiếm.

358
00:27:33,240 --> 00:27:36,800
Vì vậy, chúng ta không cần phải cập nhật bắt đầu được yếu tố này.

359
00:27:36,800 --> 00:27:39,560
Chúng tôi chỉ có thể bỏ qua nó và cập nhật bắt đầu được yếu tố này.

360
00:27:39,560 --> 00:27:46,060
Và có bao giờ trường hợp một, hãy nói, rằng đây là kết thúc,

361
00:27:46,060 --> 00:27:53,140
để sau đó bắt đầu sẽ được điều này, bắt đầu + end / 2 sẽ được điều này,

362
00:27:53,140 --> 00:28:00,580
bắt đầu + end - Vâng, tôi nghĩ rằng nó có thể kết thúc trong đệ quy vô hạn.

363
00:28:00,580 --> 00:28:12,690
Hãy nói rằng nó chỉ là một mảng của các kích thước 2 hoặc một mảng có kích thước 1. Tôi nghĩ rằng điều này sẽ làm việc.

364
00:28:12,690 --> 00:28:19,490
Vì vậy, hiện nay, bắt đầu là yếu tố đó và cuối cùng là 1 ngoài nó.

365
00:28:19,490 --> 00:28:24,110
Vì vậy, các yếu tố đó chúng ta sẽ kiểm tra là một trong những điều này,

366
00:28:24,110 --> 00:28:29,400
và sau đó khi chúng tôi cập nhật bắt đầu, chúng tôi đang cập nhật bắt đầu là 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
đó là sẽ kết thúc chúng tôi trở lại với yếu tố này bắt đầu.

368
00:28:33,160 --> 00:28:36,210
>> Vì vậy, chúng tôi đang kiểm tra các yếu tố tương tự hơn và hơn nữa.

369
00:28:36,210 --> 00:28:43,310
Vì vậy, đây là trường hợp tất cả các cuộc gọi đệ quy thực sự phải cập nhật một cái gì đó.

370
00:28:43,310 --> 00:28:48,370
Vì vậy, chúng ta cần phải làm bắt đầu + kết thúc / 2 + 1, hoặc người nào khác có một trường hợp

371
00:28:48,370 --> 00:28:50,710
chúng tôi không thực sự cập nhật bắt đầu.

372
00:28:50,710 --> 00:28:53,820
Mọi người đều nhìn thấy không?

373
00:28:53,820 --> 00:28:56,310
Okay.

374
00:28:56,310 --> 00:29:03,860
Có ai có câu hỏi về giải pháp này hay ý kiến ​​nào?

375
00:29:05,220 --> 00:29:10,280
Okay. Có ai có một giải pháp mà tất cả chúng ta có thể nhìn vào lặp đi lặp lại?

376
00:29:17,400 --> 00:29:20,940
Tất cả chúng ta làm điều đó đệ quy?

377
00:29:20,940 --> 00:29:25,950
Hoặc tôi cũng đoán nếu bạn mở cô, sau đó bạn có thể có ghi đè một trong những trang trước của bạn.

378
00:29:25,950 --> 00:29:28,810
Liệu nó sẽ tự động tiết kiệm? Tôi không tích cực.

379
00:29:35,090 --> 00:29:39,130
Có ai đã lặp đi lặp lại?

380
00:29:39,130 --> 00:29:42,430
Chúng tôi có thể đi bộ qua nó với nhau nếu không.

381
00:29:46,080 --> 00:29:48,100
Ý tưởng là có được như vậy.

382
00:30:00,260 --> 00:30:02,830
Lặp đi lặp lại giải pháp.

383
00:30:02,830 --> 00:30:07,140
Chúng tôi sẽ muốn về cơ bản làm cùng một ý tưởng

384
00:30:07,140 --> 00:30:16,530
mà chúng tôi muốn theo dõi kết thúc mới của mảng và bắt đầu mới của mảng

385
00:30:16,530 --> 00:30:18,510
và làm điều đó hơn và hơn.

386
00:30:18,510 --> 00:30:22,430
Và nếu những gì chúng tôi đang theo dõi như là bắt đầu và kết thúc bao giờ giao nhau,

387
00:30:22,430 --> 00:30:29,020
sau đó chúng tôi đã không tìm thấy nó và chúng ta có thể quay trở lại sai.

388
00:30:29,020 --> 00:30:37,540
Vì vậy, làm thế nào để làm điều đó? Bất cứ ai có đề xuất hoặc mã cho tôi để kéo lên?

389
00:30:42,190 --> 00:30:47,450
[Sinh viên] Làm một vòng lặp while. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Bạn sẽ muốn làm một vòng lặp.

391
00:30:49,450 --> 00:30:51,830
>> Bạn đã có mã tôi có thể kéo lên, hoặc những gì bạn đã đi để đề nghị?

392
00:30:51,830 --> 00:30:56,340
[Sinh viên] Tôi nghĩ vậy. >> Tất cả đúng. Điều này làm cho mọi việc dễ dàng hơn. Tên của bạn là gì?

393
00:30:56,340 --> 00:30:57,890
[Sinh viên] Lucas.

394
00:31:00,140 --> 00:31:04,190
Phiên bản 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Thấp là những gì chúng ta gọi là bắt đầu trước khi.

396
00:31:13,200 --> 00:31:17,080
Lên không phải là hoàn toàn những gì chúng tôi gọi là cuối trước khi.

397
00:31:17,080 --> 00:31:22,750
Trên thực tế, cuối cùng là trong mảng. Đây là một yếu tố chúng ta nên xem xét.

398
00:31:22,750 --> 00:31:26,890
Quá thấp là 0, là kích thước của mảng - 1,

399
00:31:26,890 --> 00:31:34,780
và bây giờ chúng tôi đang vòng lặp, và chúng tôi đang kiểm tra -

400
00:31:34,780 --> 00:31:37,340
Tôi đoán bạn có thể đi bộ qua nó.

401
00:31:37,340 --> 00:31:41,420
Suy nghĩ của bạn là gì thông qua? Đi bộ chúng tôi thông qua mã của bạn.

402
00:31:41,420 --> 00:31:49,940
[Sinh viên] Chắc chắn rồi. Nhìn vào giá trị haystack ở giữa và so sánh nó với kim.

403
00:31:49,940 --> 00:31:58,520
Vì vậy, nếu nó lớn hơn kim của bạn, sau đó bạn muốn - oh, trên thực tế, mà nên ngược.

404
00:31:58,520 --> 00:32:05,180
Bạn sẽ muốn vứt bỏ nửa bên phải, và như vậy, mà nên là cách.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Vì vậy, điều này nên được ít hơn? Đó có phải là những gì bạn nói? >> [Sinh viên] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okay. Ít hơn.

407
00:32:10,390 --> 00:32:15,700
Vì vậy, nếu những gì chúng tôi đang tìm kiếm là nhỏ hơn so với những gì chúng ta muốn,

408
00:32:15,700 --> 00:32:19,410
sau đó yeah, chúng tôi muốn vứt bỏ nửa bên trái,

409
00:32:19,410 --> 00:32:22,210
có nghĩa là chúng tôi đang cập nhật tất cả mọi thứ chúng tôi đang xem xét

410
00:32:22,210 --> 00:32:26,610
bằng cách di chuyển thấp bên phải của mảng.

411
00:32:26,610 --> 00:32:30,130
Điều này có vẻ tốt.

412
00:32:30,130 --> 00:32:34,550
Tôi nghĩ rằng nó có cùng một vấn đề mà chúng tôi đã nói trước đó,

413
00:32:34,550 --> 00:32:49,760
nếu thấp là 0 và là 1, sau đó thấp + lên / 2 sẽ thiết lập được điều tương tự một lần nữa.

414
00:32:49,760 --> 00:32:53,860
>> Và ngay cả khi đó không phải là trường hợp, nó vẫn còn ở rất ít hiệu quả hơn

415
00:32:53,860 --> 00:32:57,630
chỉ cần vứt bỏ các yếu tố, chúng tôi chỉ nhìn mà chúng ta biết là sai.

416
00:32:57,630 --> 00:33:03,240
Quá thấp + lên / 2 + 1 - >> [sinh viên] Điều đó phải được theo cách khác.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Hoặc này - 1 và một trong những khác là + 1.

418
00:33:05,900 --> 00:33:09,580
[Sinh viên] Và có phải là một đôi dấu bằng. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Sinh viên] Yeah.

420
00:33:14,540 --> 00:33:15,910
Okay.

421
00:33:15,910 --> 00:33:21,280
Và cuối cùng, bây giờ mà chúng ta có 1 + 1 điều,

422
00:33:21,280 --> 00:33:31,520
là nó - nó có thể không bao giờ có thể thấp để kết thúc với một giá trị lớn hơn lên?

423
00:33:35,710 --> 00:33:40,320
Tôi nghĩ rằng cách duy nhất có thể xảy ra - nó có thể? >> [Sinh viên] Tôi không biết.

424
00:33:40,320 --> 00:33:45,220
Nhưng nếu nó được cắt ngắn và sau đó được trừ đi 1 và sau đó - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Sinh viên] có thể sẽ được điều sai lầm.

426
00:33:49,700 --> 00:33:53,940
Tôi nghĩ rằng nó sẽ được tốt chỉ vì

427
00:33:53,940 --> 00:33:58,800
cho nó để kết thúc thấp hơn, họ sẽ có được bình đẳng, tôi nghĩ.

428
00:33:58,800 --> 00:34:03,070
Nhưng nếu chúng bằng nhau, sau đó chúng tôi sẽ không có thực hiện vòng lặp trong khi để bắt đầu với

429
00:34:03,070 --> 00:34:06,670
và chúng tôi sẽ trả lại giá trị. Vì vậy, tôi nghĩ rằng bây giờ chúng tôi đang tốt.

430
00:34:06,670 --> 00:34:11,530
Chú ý rằng mặc dù vấn đề này không còn là đệ quy,

431
00:34:11,530 --> 00:34:17,400
cùng một loại ý tưởng áp dụng, nơi chúng ta có thể xem cách này quá dễ dàng vay chính nó

432
00:34:17,400 --> 00:34:23,659
một giải pháp đệ quy bởi thực tế rằng chúng ta chỉ cần cập nhật các chỉ số hơn và hơn nữa,

433
00:34:23,659 --> 00:34:29,960
chúng tôi đang làm cho vấn đề nhỏ hơn và nhỏ hơn, chúng tôi đang tập trung vào một tập hợp con của mảng.

434
00:34:29,960 --> 00:34:40,860
[Sinh viên] Nếu thấp là 0, và lên là 1, cả hai đều sẽ là 0 + 1/2, mà sẽ đi đến 0,

435
00:34:40,860 --> 00:34:44,429
và sau đó sẽ là một trong + 1, một trong những sẽ là - 1.

436
00:34:47,000 --> 00:34:50,870
[Sinh viên] Chúng ta đang kiểm tra bình đẳng?

437
00:34:50,870 --> 00:34:55,100
Cũng giống như nếu một trong những trung lưu thực sự là kim?

438
00:34:55,100 --> 00:34:58,590
Chúng tôi không làm điều đó? Oh!

439
00:35:00,610 --> 00:35:02,460
Nếu it's -

440
00:35:05,340 --> 00:35:13,740
Vâng. Chúng ta không thể làm bài kiểm tra xuống ở đây bởi vì chúng ta hãy nói rằng giữa đầu tiên -

441
00:35:13,740 --> 00:35:16,430
[Sinh viên] Nó thực sự thích Không vứt ràng buộc.

442
00:35:16,430 --> 00:35:20,220
Vì vậy, nếu bạn quăng đi những ràng buộc, bạn phải kiểm tra xem nó đầu tiên hoặc bất cứ điều gì.

443
00:35:20,220 --> 00:35:23,350
Ah. Yeah. >> [Sinh viên] Yeah.

444
00:35:23,350 --> 00:35:29,650
Vì vậy, bây giờ chúng tôi đã vứt bỏ chúng tôi hiện đang nhìn,

445
00:35:29,650 --> 00:35:33,260
có nghĩa là bây giờ chúng ta cũng cần phải có

446
00:35:33,260 --> 00:35:44,810
nếu (haystack [(+ up) / 2] == kim), sau đó chúng ta có thể trở lại đúng sự thật.

447
00:35:44,810 --> 00:35:52,070
Và cho dù tôi đặt khác hoặc chỉ cần thiết nếu, nó có nghĩa là điều tương tự

448
00:35:52,070 --> 00:35:57,110
vì điều này sẽ đã trở lại đúng sự thật.

449
00:35:57,110 --> 00:36:01,450
Vì vậy, tôi sẽ đặt khác nếu, nhưng nó không quan trọng.

450
00:36:01,450 --> 00:36:10,440
>> Vì vậy, nếu người nào khác, khác, và đây là một điều phổ biến tôi làm

451
00:36:10,440 --> 00:36:14,340
mà ngay cả khi đó là trường hợp, nơi tất cả mọi thứ là tốt ở đây,

452
00:36:14,340 --> 00:36:22,780
như thấp không bao giờ có thể lớn hơn lên, nó không có giá trị lý luận về cho dù đó là sự thật.

453
00:36:22,780 --> 00:36:28,010
Vì vậy, bạn cũng có thể nói trong khi thấp là ít hơn hoặc bằng

454
00:36:28,010 --> 00:36:30,720
hoặc trong khi thấp là ít hơn

455
00:36:30,720 --> 00:36:35,300
do đó, nếu họ có bao giờ bằng hoặc thấp sẽ xảy ra để vượt lên,

456
00:36:35,300 --> 00:36:40,130
sau đó chúng ta có thể thoát ra khỏi vòng lặp này.

457
00:36:41,410 --> 00:36:44,630
Câu hỏi, bình luận?

458
00:36:47,080 --> 00:36:49,270
Okay. Điều này có vẻ tốt.

459
00:36:49,270 --> 00:36:52,230
Bây giờ chúng tôi muốn làm loại.

460
00:36:52,230 --> 00:37:04,030
Nếu chúng ta đi đến phiên bản thứ hai của tôi, chúng ta thấy những con số tương tự,

461
00:37:04,030 --> 00:37:07,550
nhưng bây giờ họ không còn theo thứ tự sắp xếp.

462
00:37:07,550 --> 00:37:12,840
Và chúng tôi muốn thực hiện loại bằng cách sử dụng bất kỳ thuật toán trong O n log n.

463
00:37:12,840 --> 00:37:17,240
Vì vậy, thuật toán nào bạn nghĩ rằng chúng ta nên thực hiện ở đây? >> [Sinh viên] Merge sắp xếp.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Hợp nhất sắp xếp là O (n log n), vì vậy đó là những gì chúng ta sẽ làm.

465
00:37:23,810 --> 00:37:26,680
Và vấn đề là có được khá tương tự,

466
00:37:26,680 --> 00:37:31,920
nó một cách dễ dàng vay chính nó đến một giải pháp đệ quy.

467
00:37:31,920 --> 00:37:35,580
Chúng tôi cũng có thể đến với một giải pháp lặp đi lặp lại nếu chúng ta muốn,

468
00:37:35,580 --> 00:37:42,540
nhưng đệ quy sẽ được dễ dàng hơn ở đây và chúng ta nên làm đệ quy.

469
00:37:45,120 --> 00:37:49,530
Tôi đoán chúng tôi sẽ đi bộ qua các loại hợp nhất đầu tiên,

470
00:37:49,530 --> 00:37:54,280
mặc dù là một đoạn video đáng yêu trên loại hợp nhất rồi. [Cười]

471
00:37:54,280 --> 00:37:59,780
Vì vậy, kết hợp loại có - Tôi đang lãng phí rất nhiều của bài viết này.

472
00:37:59,780 --> 00:38:02,080
Oh, chỉ có một trái.

473
00:38:02,080 --> 00:38:03,630
Vì vậy, hợp nhất.

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

475
00:38:26,090 --> 00:38:27,440
Okay.

476
00:38:29,910 --> 00:38:33,460
Merge mất hai mảng riêng biệt.

477
00:38:33,460 --> 00:38:36,780
Riêng hai mảng đều được sắp xếp.

478
00:38:36,780 --> 00:38:40,970
Vì vậy, mảng này, 1, 3, 5, sắp xếp. Mảng này, 0, 2, 4, sắp xếp.

479
00:38:40,970 --> 00:38:46,710
Bây giờ những gì hợp nhất nên làm là kết hợp chúng thành một mảng duy nhất đó là chính nó được sắp xếp.

480
00:38:46,710 --> 00:38:57,130
Vì vậy, chúng tôi muốn một mảng có kích thước 6 có nghĩa là sẽ có những yếu tố bên trong của nó

481
00:38:57,130 --> 00:38:59,390
theo thứ tự sắp xếp.

482
00:38:59,390 --> 00:39:03,390
>> Và vì vậy chúng ta có thể tận dụng lợi thế của thực tế là hai mảng này đều được sắp xếp

483
00:39:03,390 --> 00:39:06,800
để làm điều này trong thời gian tuyến tính,

484
00:39:06,800 --> 00:39:13,510
tuyến tính thời gian có nghĩa là nếu mảng này là kích thước x và điều này là kích thước y,

485
00:39:13,510 --> 00:39:20,970
sau đó tổng số các thuật toán là O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Vì vậy, đề nghị.

487
00:39:23,150 --> 00:39:26,030
[Sinh viên] chúng ta có thể bắt đầu từ bên trái?

488
00:39:26,030 --> 00:39:30,150
Vì vậy, bạn sẽ đặt 0 xuống đầu tiên và sau đó số 1 và sau đó bạn vào 2.

489
00:39:30,150 --> 00:39:33,320
Vì vậy, nó là loại như bạn có một tab di chuyển sang bên phải. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Đối với cả hai của các mảng nếu chúng ta chỉ tập trung vào các yếu tố ngoài cùng bên trái.

491
00:39:41,070 --> 00:39:43,530
Bởi vì cả hai mảng được sắp xếp, chúng ta biết rằng 2 yếu tố này

492
00:39:43,530 --> 00:39:46,920
là những yếu tố nhỏ nhất trong mảng một trong hai.

493
00:39:46,920 --> 00:39:53,500
Vì vậy, điều đó có nghĩa là 1 của 2 yếu tố đó phải là phần tử nhỏ nhất trong mảng sáp nhập của chúng tôi.

494
00:39:53,500 --> 00:39:58,190
Nó chỉ như vậy sẽ xảy ra rằng nhỏ nhất là một trong những ngày đúng thời điểm này.

495
00:39:58,190 --> 00:40:02,580
Vì vậy, chúng ta hãy 0, chèn nó vào bên trái vì 0 là ít hơn 1,

496
00:40:02,580 --> 00:40:08,210
do đó, có 0, chèn nó vào vị trí đầu tiên của chúng tôi, và sau đó chúng tôi cập nhật này

497
00:40:08,210 --> 00:40:12,070
đến nay tập trung vào các yếu tố đầu tiên.

498
00:40:12,070 --> 00:40:14,570
Và bây giờ chúng tôi lặp lại.

499
00:40:14,570 --> 00:40:20,670
Vì vậy, bây giờ chúng ta so sánh 2 và 1. 1 là nhỏ hơn, do đó, chúng ta sẽ chèn 1.

500
00:40:20,670 --> 00:40:25,300
Chúng tôi cập nhật con trỏ để trỏ đến anh chàng này.

501
00:40:25,300 --> 00:40:33,160
Bây giờ chúng ta làm điều đó một lần nữa, do đó, 2. Điều này sẽ cập nhật, so sánh những 2, 3.

502
00:40:33,160 --> 00:40:37,770
Điều này cập nhật, sau đó 4 và 5.

503
00:40:37,770 --> 00:40:42,110
Vì vậy, đó là hợp nhất.

504
00:40:42,110 --> 00:40:49,010
>> Nó nên được khá rõ ràng rằng nó là tuyến tính thời gian kể từ khi chúng tôi chỉ đi qua mỗi phần tử một lần.

505
00:40:49,010 --> 00:40:55,980
Và đó là bước lớn nhất để thực hiện hợp nhất loại là làm điều này.

506
00:40:55,980 --> 00:40:59,330
Và nó không phải là khó.

507
00:40:59,330 --> 00:41:15,020
Một vài điều phải lo lắng về là chúng ta hãy nói rằng chúng tôi đã được sáp nhập 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Trong trường hợp này, chúng tôi kết thúc trong kịch bản này là một trong những sẽ nhỏ hơn,

509
00:41:30,930 --> 00:41:36,160
sau đó chúng tôi cập nhật con trỏ này, một trong những điều này sẽ nhỏ hơn, cập nhật,

510
00:41:36,160 --> 00:41:41,280
cái này thì nhỏ hơn, và bây giờ bạn có nhận ra

511
00:41:41,280 --> 00:41:44,220
khi bạn đã thực sự chạy ra khỏi các yếu tố để so sánh với.

512
00:41:44,220 --> 00:41:49,400
Từ khi chúng tôi đã được sử dụng toàn bộ mảng này,

513
00:41:49,400 --> 00:41:55,190
tất cả mọi thứ trong mảng này bây giờ chỉ cần đưa vào đây.

514
00:41:55,190 --> 00:42:02,040
Vì vậy, nếu chúng ta bao giờ chạy vào điểm mà một trong các mảng của chúng tôi là hoàn toàn sáp nhập đã,

515
00:42:02,040 --> 00:42:06,510
sau đó chúng tôi chỉ đưa tất cả các yếu tố của các mảng khác và chèn chúng vào cuối mảng.

516
00:42:06,510 --> 00:42:13,630
Vì vậy, chúng tôi chỉ có thể chèn 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Đó là một điều để xem ra cho.

518
00:42:22,080 --> 00:42:26,120
Thực hiện có nên bước 1.

519
00:42:26,120 --> 00:42:32,600
Hợp nhất sắp xếp sau đó trên cơ sở đó, đó là 2 bước, 2 bước ngớ ngẩn.

520
00:42:38,800 --> 00:42:42,090
Hãy chỉ cho mảng này.

521
00:42:57,920 --> 00:43:05,680
Vì vậy, hợp nhất sắp xếp, bước 1 là đệ quy phá vỡ các mảng vào nửa.

522
00:43:05,680 --> 00:43:09,350
Vì vậy, chia mảng này vào nửa.

523
00:43:09,350 --> 00:43:22,920
Bây giờ chúng ta có 4, 15, 16, 50 và 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Và bây giờ chúng tôi làm điều đó một lần nữa và chúng tôi chia thành các nửa.

525
00:43:25,800 --> 00:43:27,530
Tôi sẽ chỉ làm điều đó trên mặt này.

526
00:43:27,530 --> 00:43:34,790
Vì vậy, 4, 15, 16, 50.

527
00:43:34,790 --> 00:43:37,440
Chúng tôi sẽ làm điều tương tự ở đây.

528
00:43:37,440 --> 00:43:40,340
Và bây giờ chúng tôi chia nó thành hai nửa một lần nữa.

529
00:43:40,340 --> 00:43:51,080
Và chúng tôi có 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Vì vậy, đó là trường hợp cơ sở của chúng tôi.

531
00:43:53,170 --> 00:44:00,540
Một khi các mảng có kích thước 1, sau đó chúng tôi dừng lại với phân tách thành hai nửa.

532
00:44:00,540 --> 00:44:03,190
>> Bây giờ chúng ta phải làm gì với điều này?

533
00:44:03,190 --> 00:44:15,730
Chúng tôi kết thúc điều này cũng sẽ phá vỡ thành 8, 23, 42, và 108.

534
00:44:15,730 --> 00:44:24,000
Vì vậy, bây giờ chúng ta đang ở vào thời điểm này, bây giờ bước hai của hợp nhất loại chỉ là sáp nhập cặp danh sách.

535
00:44:24,000 --> 00:44:27,610
Vì vậy, chúng tôi muốn hợp nhất các. Chúng tôi chỉ cần gọi hợp nhất.

536
00:44:27,610 --> 00:44:31,410
Chúng tôi biết hợp nhất sẽ trở lại trong các thứ tự sắp xếp.

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

538
00:44:33,920 --> 00:44:41,440
Bây giờ chúng tôi muốn kết hợp này, và đó sẽ trở lại một danh sách với những người theo thứ tự sắp xếp,

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

540
00:44:44,160 --> 00:44:57,380
Chúng tôi kết hợp những - tôi không thể viết - 8, 23 và 42, 108.

541
00:44:57,380 --> 00:45:02,890
Vì vậy, chúng tôi có các cặp sáp nhập một lần.

542
00:45:02,890 --> 00:45:05,140
Bây giờ chúng ta chỉ cần kết hợp một lần nữa.

543
00:45:05,140 --> 00:45:10,130
Chú ý rằng mỗi các danh sách này được sắp xếp trong chính nó,

544
00:45:10,130 --> 00:45:15,220
và sau đó chúng tôi chỉ có thể hợp nhất các danh sách này để có được một danh sách các kích thước 4 được sắp xếp

545
00:45:15,220 --> 00:45:19,990
và hợp nhất hai danh sách này để có được một danh sách các kích thước 4 được sắp xếp.

546
00:45:19,990 --> 00:45:25,710
Và cuối cùng, chúng ta có thể hợp nhất hai danh sách các kích thước 4 để có được một danh sách các kích thước 8 được sắp xếp.

547
00:45:25,710 --> 00:45:34,030
Vì vậy, để thấy rằng đây là tổng thể n log n, chúng ta đã thấy rằng hợp nhất là tuyến tính,

548
00:45:34,030 --> 00:45:40,390
do đó, khi chúng ta đang đối phó với việc sáp nhập này, do đó, như tổng chi phí của hợp nhất

549
00:45:40,390 --> 00:45:43,410
cho hai danh sách này chỉ là 2 bởi vì -

550
00:45:43,410 --> 00:45:49,610
Hoặc tốt, đó là O của n, n ở đây chỉ là 2 yếu tố này, do đó, nó là 2.

551
00:45:49,610 --> 00:45:52,850
Và những 2 sẽ là 2 và những 2 sẽ được 2 và những 2 sẽ là 2,

552
00:45:52,850 --> 00:45:58,820
do đó, trên tất cả các sáp nhập mà chúng ta cần làm, chúng tôi kết thúc làm n.

553
00:45:58,820 --> 00:46:03,210
Giống như 2 + 2 + 2 + 2 là 8, mà là n,

554
00:46:03,210 --> 00:46:08,060
do đó, chi phí của việc sáp nhập trong bộ này là n.

555
00:46:08,060 --> 00:46:10,810
Và sau đó điều tương tự ở đây.

556
00:46:10,810 --> 00:46:16,980
Chúng tôi sẽ hợp nhất các 2, sau đó những 2, và cá nhân hợp nhất này sẽ có bốn hoạt động,

557
00:46:16,980 --> 00:46:23,610
này hợp nhất sẽ có bốn hoạt động, nhưng một lần nữa, giữa tất cả các,

558
00:46:23,610 --> 00:46:29,030
chúng tôi kết thúc hợp nhất n tổng điều, và do đó, bước này có n.

559
00:46:29,030 --> 00:46:33,670
Và do đó, mỗi cấp có n phần tử được sáp nhập.

560
00:46:33,670 --> 00:46:36,110
>> Và bao nhiêu cấp?

561
00:46:36,110 --> 00:46:40,160
Ở mỗi cấp độ, mảng của chúng tôi phát triển bởi kích thước 2.

562
00:46:40,160 --> 00:46:44,590
Mảng của chúng tôi là có kích thước 1, ở đây chúng có kích thước 2, ở đây họ đang có kích thước 4,

563
00:46:44,590 --> 00:46:46,470
và cuối cùng, chúng có kích thước 8.

564
00:46:46,470 --> 00:46:56,450
Vì vậy, kể từ khi nó được tăng gấp đôi, có sẽ được tổng cộng log n của các cấp độ.

565
00:46:56,450 --> 00:47:02,090
Vì vậy, với log n cấp độ, mỗi cấp độ cá nhân n hoạt động tổng,

566
00:47:02,090 --> 00:47:05,720
chúng tôi nhận được một log n n thuật toán.

567
00:47:05,720 --> 00:47:07,790
Câu hỏi?

568
00:47:08,940 --> 00:47:13,320
Có người đã đạt được tiến bộ về làm thế nào để thực hiện điều này?

569
00:47:13,320 --> 00:47:18,260
Có ai đã có trong một tiểu bang mà tôi chỉ có thể kéo lên mã của họ?

570
00:47:20,320 --> 00:47:22,260
Tôi có thể cung cấp cho một phút.

571
00:47:24,770 --> 00:47:27,470
Điều này một là có thể kéo dài hơn.

572
00:47:27,470 --> 00:47:28,730
Tôi rất khuyên bạn nên tái diễn -

573
00:47:28,730 --> 00:47:30,510
Bạn không phải làm đệ quy cho hợp nhất

574
00:47:30,510 --> 00:47:33,750
bởi vì để làm đệ quy cho hợp nhất, bạn sẽ phải vượt qua một loạt các kích cỡ khác nhau.

575
00:47:33,750 --> 00:47:37,150
Bạn có thể, nhưng nó gây phiền nhiễu.

576
00:47:37,150 --> 00:47:43,720
Nhưng đệ quy để sắp xếp chính nó là khá dễ dàng.

577
00:47:43,720 --> 00:47:49,190
Bạn chỉ theo nghĩa đen gọi sắp xếp trên nửa bên trái, sắp xếp trên nửa bên phải. Okay.

578
00:47:51,770 --> 00:47:54,860
Bất cứ ai có bất cứ điều gì tôi có thể kéo lên?

579
00:47:54,860 --> 00:47:57,540
Hoặc nếu không tôi sẽ cung cấp cho một phút.

580
00:47:58,210 --> 00:47:59,900
Okay.

581
00:47:59,900 --> 00:48:02,970
Bất cứ ai cũng có một cái gì đó chúng ta có thể làm việc với?

582
00:48:05,450 --> 00:48:09,680
Nếu không chúng ta sẽ chỉ làm việc với điều này và sau đó mở rộng từ đó.

583
00:48:09,680 --> 00:48:14,050
>> Bất cứ ai có nhiều hơn này mà tôi có thể kéo lên?

584
00:48:14,050 --> 00:48:17,770
[Sinh viên] Yeah. Bạn có thể kéo lên tôi. >> Tất cả đúng.

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

586
00:48:22,170 --> 00:48:25,280
[Sinh viên] Có rất nhiều điều kiện. >> Oh, bắn. Bạn có thể không -

587
00:48:25,280 --> 00:48:28,110
[Sinh viên] Tôi có để lưu nó. >> Yeah.

588
00:48:32,420 --> 00:48:35,730
Vì vậy, chúng tôi đã làm việc hợp nhất một cách riêng biệt.

589
00:48:35,730 --> 00:48:38,570
Vâng, nhưng đó không phải là xấu.

590
00:48:39,790 --> 00:48:41,650
Okay.

591
00:48:41,650 --> 00:48:47,080
Vì vậy, sắp xếp là chính nó chỉ cần gọi điện thoại mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Giải thích cho chúng tôi những gì mergeSortHelp không.

593
00:48:49,530 --> 00:48:55,700
[Sinh viên] MergeSortHelp khá nhiều hiện hai bước chính,

594
00:48:55,700 --> 00:49:01,270
đó là để sắp xếp mỗi nửa của mảng và sau đó kết hợp cả hai người trong số họ.

595
00:49:04,960 --> 00:49:08,050
[Bowden] rồi, do đó cung cấp cho tôi một giây.

596
00:49:10,850 --> 00:49:13,210
Tôi nghĩ rằng điều này - >> [sinh viên] Tôi cần phải -

597
00:49:17,100 --> 00:49:19,400
Yeah. Tôi đang thiếu một cái gì đó.

598
00:49:19,400 --> 00:49:23,100
Hợp nhất, tôi nhận ra rằng tôi cần phải tạo một mảng mới

599
00:49:23,100 --> 00:49:26,530
bởi vì tôi không thể làm điều đó tại chỗ. >>. Bạn có thể không. Chính xác.

600
00:49:26,530 --> 00:49:28,170
[Sinh viên] Vì vậy, tôi tạo ra một mảng mới.

601
00:49:28,170 --> 00:49:31,510
Tôi quên vào cuối hợp nhất lại thay đổi.

602
00:49:31,510 --> 00:49:34,490
Okay. Chúng ta cần một mảng mới.

603
00:49:34,490 --> 00:49:41,000
Trong loại hợp nhất, điều này hầu như luôn luôn đúng.

604
00:49:41,000 --> 00:49:44,340
Một phần của chi phí của một thuật toán tốt hơn thời gian khôn ngoan

605
00:49:44,340 --> 00:49:47,310
hầu như luôn luôn cần phải sử dụng bộ nhớ nhiều hơn một chút.

606
00:49:47,310 --> 00:49:51,570
Vì vậy, ở đây, không có vấn đề làm thế nào bạn làm hợp nhất sắp xếp,

607
00:49:51,570 --> 00:49:54,780
mà bạn chắc chắn sẽ cần phải sử dụng một số bộ nhớ thêm.

608
00:49:54,780 --> 00:49:58,240
Anh ta hoặc cô tạo ra một mảng mới.

609
00:49:58,240 --> 00:50:03,400
Và sau đó bạn nói rằng cuối cùng chúng tôi chỉ cần sao chép mảng mới vào mảng ban đầu.

610
00:50:03,400 --> 00:50:04,830
[Sinh viên] Tôi nghĩ như vậy, yeah.

611
00:50:04,830 --> 00:50:08,210
Tôi không biết rằng các công trình về tính tham khảo hoặc bất cứ điều gì -

612
00:50:08,210 --> 00:50:11,650
Yeah, nó sẽ làm việc. >> [Sinh viên] Okay.

613
00:50:20,620 --> 00:50:24,480
Bạn hãy thử chạy này? >> [Sinh viên] Không, không phải. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Thử chạy nó, và sau đó tôi sẽ nói về nó cho một thứ hai.

615
00:50:28,880 --> 00:50:35,200
[Sinh viên] Tôi cần phải có tất cả các nguyên mẫu chức năng và tất cả mọi thứ, mặc dù, phải không?

616
00:50:37,640 --> 00:50:40,840
Các chức năng nguyên mẫu. Oh, bạn có nghĩa là như thế - Có.

617
00:50:40,840 --> 00:50:43,040
Sắp xếp được gọi mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Vì vậy, để sắp xếp để gọi mergeSortHelp mergeSortHelp hoặc phải được xác định

619
00:50:47,390 --> 00:50:56,370
trước khi sắp xếp hoặc chúng ta chỉ cần các mẫu thử nghiệm. Chỉ cần sao chép và dán mà.

620
00:50:56,370 --> 00:50:59,490
Và tương tự như vậy, mergeSortHelp đang kêu gọi hợp nhất,

621
00:50:59,490 --> 00:51:03,830
nhưng hợp nhất đã được xác định, vì vậy chúng tôi chỉ có thể cho mergeSortHelp biết

622
00:51:03,830 --> 00:51:08,700
đó là những gì hợp nhất sẽ trông giống như, và thế là chấm dứt.

623
00:51:09,950 --> 00:51:15,730
Vì vậy, mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Chúng tôi có một vấn đề ở đây, nơi chúng tôi không có trường hợp cơ sở.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp là đệ quy, do đó, bất kỳ chức năng đệ quy

626
00:51:38,110 --> 00:51:42,610
sẽ cần một số loại của trường hợp cơ sở để biết khi nào dừng đệ quy tự gọi mình.

627
00:51:42,610 --> 00:51:45,590
Trường hợp cơ sở của chúng tôi sẽ được gì đây? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Sinh viên] Nếu kích thước là 1? >> [Bowden].

629
00:51:49,110 --> 00:51:56,220
Vì vậy, như chúng ta đã thấy ngay tại đó, chúng tôi dừng mảng tách

630
00:51:56,220 --> 00:52:01,850
một khi chúng ta đã tạo thành những mảng có kích thước 1, mà chắc chắn đều được sắp xếp.

631
00:52:01,850 --> 00:52:09,530
Vì vậy, nếu kích thước bằng 1, chúng ta biết mảng đã được sắp xếp,

632
00:52:09,530 --> 00:52:12,970
vì vậy chúng tôi chỉ có thể trở lại.

633
00:52:12,970 --> 00:52:16,880
>> Chú ý rằng có hiệu lực, nên chúng tôi không trả lại bất cứ điều gì đặc biệt, chúng tôi chỉ trả lại.

634
00:52:16,880 --> 00:52:19,580
Okay. Vì vậy, đó là trường hợp cơ sở của chúng tôi.

635
00:52:19,580 --> 00:52:27,440
Tôi đoán trường hợp cơ sở của chúng tôi cũng có thể được nếu chúng ta xảy ra để được sáp nhập một mảng có kích thước 0,

636
00:52:27,440 --> 00:52:30,030
chúng tôi có thể muốn dừng lại tại một số điểm,

637
00:52:30,030 --> 00:52:33,610
vì vậy chúng tôi chỉ có thể nói kích thước ít hơn 2 hoặc nhỏ hơn hoặc bằng 1

638
00:52:33,610 --> 00:52:37,150
để điều này sẽ làm việc cho bất kỳ mảng.

639
00:52:37,150 --> 00:52:38,870
Okay.

640
00:52:38,870 --> 00:52:42,740
Vì vậy, đó là trường hợp cơ sở của chúng tôi.

641
00:52:42,740 --> 00:52:45,950
Bây giờ bạn có muốn đi bộ chúng tôi thông qua hợp nhất?

642
00:52:45,950 --> 00:52:49,140
Tất cả các trường hợp này có ý nghĩa gì?

643
00:52:49,140 --> 00:52:54,480
Lên ở đây, chúng ta chỉ cần làm cùng một ý tưởng, các -

644
00:52:56,970 --> 00:53:02,470
[Sinh viên] tôi cần phải được đi qua kích thước với tất cả các cuộc gọi mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Tôi được thêm vào kích thước như một chính bổ sung và nó không phải ở đó, như kích thước / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, kích thước / 2, kích thước / 2. >> [Sinh viên] Yeah, và cũng trong hàm trên cũng.

647
00:53:16,210 --> 00:53:21,320
Bowden]? >> [Sinh viên] Chỉ cần kích thước. >> [Bowden] Oh. Kích thước, kích thước? >> [Sinh viên] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Okay.

649
00:53:23,010 --> 00:53:26,580
Hãy để tôi suy nghĩ cho một thứ hai.

650
00:53:26,580 --> 00:53:28,780
Chúng tôi chạy vào một vấn đề?

651
00:53:28,780 --> 00:53:33,690
Chúng tôi luôn xử lý bên trái là 0. >> [Sinh viên] số

652
00:53:33,690 --> 00:53:36,340
Đó là sai quá. Xin lôi. Nó nên được bắt đầu. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Tôi thích điều đó tốt hơn.

654
00:53:39,230 --> 00:53:43,880
Và kết thúc. Okay.

655
00:53:43,880 --> 00:53:47,200
Vì vậy, bây giờ bạn muốn đi bộ chúng tôi thông qua hợp nhất? >> [Sinh viên] Okay.

656
00:53:47,200 --> 00:53:52,150
Tôi chỉ đi qua mảng mới này mà tôi đã tạo ra.

657
00:53:52,150 --> 00:53:57,420
Kích thước của nó là kích thước của phần của mảng mà chúng tôi muốn được sắp xếp

658
00:53:57,420 --> 00:54:03,460
và cố gắng để tìm thấy những yếu tố mà tôi nên đặt trong bước mảng mới.

659
00:54:03,460 --> 00:54:10,140
Vì vậy, để làm được điều đó, đầu tiên tôi kiểm tra nếu có một nửa trái của mảng tiếp tục có những yếu tố nào,

660
00:54:10,140 --> 00:54:14,260
và nếu nó không, sau đó bạn đi xuống với điều kiện khác, mà chỉ nói

661
00:54:14,260 --> 00:54:20,180
okay, nó phải là trong mảng bên phải, và chúng tôi sẽ đặt trong các chỉ số hiện tại của newArray.

662
00:54:20,180 --> 00:54:27,620
>> Và sau đó nếu không, tôi kiểm tra nếu phía bên phải của mảng cũng được hoàn thành,

663
00:54:27,620 --> 00:54:30,630
trong trường hợp đó, tôi chỉ cần đặt ở bên trái.

664
00:54:30,630 --> 00:54:34,180
Điều đó có thể không thực sự cần thiết. Tôi không chắc.

665
00:54:34,180 --> 00:54:40,970
Nhưng dù sao, hai kiểm tra của hai nhỏ hơn ở bên trái hoặc bên phải.

666
00:54:40,970 --> 00:54:49,770
Và cũng có thể trong mỗi trường hợp, tôi incrementing giữ chỗ nào tôi tăng.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Okay.

668
00:54:52,040 --> 00:54:53,840
Điều đó có vẻ tốt.

669
00:54:53,840 --> 00:54:58,800
Có ai có ý kiến ​​hay quan tâm hoặc câu hỏi?

670
00:55:00,660 --> 00:55:07,720
Vì vậy, bốn trường hợp mà chúng tôi đã mang lại những điều chỉ là có vẻ như năm -

671
00:55:07,720 --> 00:55:13,100
nhưng chúng ta phải xem xét liệu các mảng bên trái đã chạy ra khỏi những điều chúng ta cần phải hợp nhất,

672
00:55:13,100 --> 00:55:16,390
liệu mảng phải đã hết những điều chúng ta cần phải hợp nhất -

673
00:55:16,390 --> 00:55:18,400
Tôi chỉ ở không có gì.

674
00:55:18,400 --> 00:55:21,730
Vì vậy, liệu các mảng bên trái đã chạy ra khỏi những điều hoặc các mảng bên phải đã chạy ra khỏi những điều.

675
00:55:21,730 --> 00:55:24,320
Đó là hai trường hợp.

676
00:55:24,320 --> 00:55:30,920
Chúng ta cũng cần trường hợp tầm thường cho dù điều trái là ít hơn đúng.

677
00:55:30,920 --> 00:55:33,910
Sau đó, chúng tôi muốn chọn điều trái.

678
00:55:33,910 --> 00:55:37,630
Đó là các trường hợp.

679
00:55:37,630 --> 00:55:40,990
Vì vậy, điều này là đúng, vì vậy đó mà.

680
00:55:40,990 --> 00:55:46,760
Mảng còn lại. Đó là 1, 2, 3. Okay. Vì vậy, yeah, những người đang có bốn điều chúng tôi có thể muốn làm.

681
00:55:50,350 --> 00:55:54,510
Và chúng tôi sẽ không đi qua một giải pháp lặp.

682
00:55:54,510 --> 00:55:55,980
Tôi sẽ không khuyên -

683
00:55:55,980 --> 00:56:03,070
Kết hợp các loại là một ví dụ của một chức năng đó là cả hai không đệ quy đuôi,

684
00:56:03,070 --> 00:56:07,040
nó không phải dễ dàng để làm cho nó đệ quy đuôi,

685
00:56:07,040 --> 00:56:13,450
nhưng cũng có thể nó không phải là rất dễ dàng để làm cho nó lặp đi lặp lại.

686
00:56:13,450 --> 00:56:16,910
Điều này là rất dễ dàng.

687
00:56:16,910 --> 00:56:19,170
Điều này thực hiện các loại hợp nhất,

688
00:56:19,170 --> 00:56:22,140
sáp nhập, không có vấn đề gì bạn làm, bạn sẽ xây dựng hợp nhất.

689
00:56:22,140 --> 00:56:29,170
>> Vì vậy, hợp nhất loại được xây dựng trên đầu trang của hợp nhất đệ quy chỉ là ba dòng này.

690
00:56:29,170 --> 00:56:34,700
Lặp đi lặp lại, nó là gây phiền nhiễu và khó khăn hơn để suy nghĩ về.

691
00:56:34,700 --> 00:56:41,860
Nhưng hãy chú ý rằng nó không phải đệ quy đuôi từ mergeSortHelp - khi nó gọi chính nó -

692
00:56:41,860 --> 00:56:46,590
nó vẫn cần làm những việc sau khi trở về cuộc gọi đệ quy.

693
00:56:46,590 --> 00:56:50,830
Vì vậy, stack frame này phải tiếp tục tồn tại ngay cả sau khi kêu gọi này.

694
00:56:50,830 --> 00:56:54,170
Và sau đó khi bạn gọi điều này, các stack frame phải tiếp tục tồn tại

695
00:56:54,170 --> 00:56:57,780
bởi vì ngay cả sau khi cuộc gọi đó, chúng tôi vẫn cần phải hợp nhất.

696
00:56:57,780 --> 00:57:01,920
Và đó là không tầm thường để làm cho đệ quy đuôi.

697
00:57:04,070 --> 00:57:06,270
Câu hỏi?

698
00:57:08,300 --> 00:57:09,860
Được rồi.

699
00:57:09,860 --> 00:57:13,400
Quay trở lại để sắp xếp - oh, có hai điều tôi muốn hiển thị. Okay.

700
00:57:13,400 --> 00:57:17,840
Trở lại để sắp xếp, chúng tôi sẽ làm điều này một cách nhanh chóng.

701
00:57:17,840 --> 00:57:21,030
Hoặc tìm kiếm. Sắp xếp? Sắp xếp. Yeah.

702
00:57:21,030 --> 00:57:22,730
Quay trở lại sự khởi đầu của loại.

703
00:57:22,730 --> 00:57:29,870
Chúng tôi muốn tạo ra một thuật toán sắp xếp các mảng bằng cách sử dụng bất kỳ thuật toán

704
00:57:29,870 --> 00:57:33,660
O của n.

705
00:57:33,660 --> 00:57:40,860
Vì vậy, làm thế nào có thể? Có ai có bất kỳ loại -

706
00:57:40,860 --> 00:57:44,300
Tôi gợi ý trước đó tại -

707
00:57:44,300 --> 00:57:48,300
Nếu chúng ta để cải thiện từ n log n O n,

708
00:57:48,300 --> 00:57:51,450
chúng tôi đã được cải thiện thuật toán của chúng tôi thời gian khôn ngoan,

709
00:57:51,450 --> 00:57:55,250
có nghĩa là những gì chúng ta sẽ cần phải làm gì để làm cho điều đó?

710
00:57:55,250 --> 00:57:59,520
[Sinh viên] Space. >> Yeah. Chúng tôi sẽ được sử dụng nhiều không gian hơn.

711
00:57:59,520 --> 00:58:04,490
Và thậm chí không chỉ cần nhiều không gian hơn, đó là theo cấp số nhân nhiều không gian hơn.

712
00:58:04,490 --> 00:58:14,320
Vì vậy, tôi nghĩ rằng loại thuật toán này là một cái gì đó giả, polynom giả -

713
00:58:14,320 --> 00:58:18,980
pseudo - Tôi không thể nhớ. Pseudo một cái gì đó.

714
00:58:18,980 --> 00:58:22,210
Nhưng đó là bởi vì chúng ta cần phải sử dụng quá nhiều không gian

715
00:58:22,210 --> 00:58:28,610
rằng điều này có thể đạt được nhưng không thực tế.

716
00:58:28,610 --> 00:58:31,220
>> Và làm thế nào để chúng ta đạt được điều này?

717
00:58:31,220 --> 00:58:36,810
Chúng tôi có thể đạt được điều này nếu chúng tôi đảm bảo rằng bất kỳ yếu tố đặc biệt trong mảng

718
00:58:36,810 --> 00:58:39,600
dưới đây là một kích thước nhất định.

719
00:58:42,070 --> 00:58:44,500
Vì vậy, chúng ta hãy chỉ nói rằng size kích thước là 200,

720
00:58:44,500 --> 00:58:48,130
bất kỳ yếu tố trong một mảng dưới kích cỡ 200.

721
00:58:48,130 --> 00:58:51,080
Và điều này thực sự là rất thực tế.

722
00:58:51,080 --> 00:58:58,660
Bạn có thể dễ dàng có một mảng mà bạn biết tất cả mọi thứ trong nó

723
00:58:58,660 --> 00:59:00,570
sẽ được ít hơn so với một số số.

724
00:59:00,570 --> 00:59:07,400
Cũng giống như nếu bạn có một số vector hoàn toàn hoặc một cái gì đó lớn

725
00:59:07,400 --> 00:59:11,810
nhưng bạn biết tất cả mọi thứ sẽ được giữa 0 và 5,

726
00:59:11,810 --> 00:59:14,790
sau đó nó sẽ nhanh hơn đáng kể để làm điều này.

727
00:59:14,790 --> 00:59:17,930
Và bị ràng buộc vào bất kỳ của các yếu tố là 5,

728
00:59:17,930 --> 00:59:21,980
do đó, điều này bị ràng buộc, đó là bao nhiêu bộ nhớ bạn sẽ được sử dụng.

729
00:59:21,980 --> 00:59:26,300
Vì vậy, ràng buộc là 200.

730
00:59:26,300 --> 00:59:32,960
Trong lý thuyết luôn luôn bị ràng buộc vì một số nguyên chỉ có thể lên đến 4 tỷ đồng,

731
00:59:32,960 --> 00:59:40,600
nhưng đó là không thực tế từ đó chúng tôi muốn được sử dụng không gian

732
00:59:40,600 --> 00:59:44,400
về trình tự của 4 tỷ đồng. Vì vậy, đó là không thực tế.

733
00:59:44,400 --> 00:59:47,060
Nhưng ở đây chúng tôi sẽ nói ràng buộc của chúng tôi là 200.

734
00:59:47,060 --> 00:59:59,570
Các trick để làm nó trong O n là chúng ta thực hiện một mảng gọi là tội kích thước RÀNG BUỘC.

735
00:59:59,570 --> 01:00:10,470
Vì vậy, trên thực tế, đây là một phím tắt cho - Tôi thực sự không biết nếu Clang thực hiện điều này.

736
01:00:11,150 --> 01:00:15,330
Nhưng trong GCC ít nhất Clang giả sử tôi làm nó quá -

737
01:00:15,330 --> 01:00:18,180
điều này sẽ chỉ khởi tạo mảng toàn bộ là số 0.

738
01:00:18,180 --> 01:00:25,320
Vì vậy, nếu tôi không muốn làm điều đó, sau đó tôi riêng biệt có thể làm for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <sách; i + +) và số lượng [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Vì vậy, bây giờ tất cả mọi thứ được khởi tạo là 0.

741
01:00:35,260 --> 01:00:39,570
Tôi lặp qua mảng của tôi,

742
01:00:39,570 --> 01:00:51,920
và những gì tôi đang làm là tôi đếm số lượng của từng - đang đi xuống.

743
01:00:51,920 --> 01:00:55,480
Chúng tôi có 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Những gì tôi đang đếm là số lần xuất hiện của mỗi người trong số những yếu tố.

745
01:01:00,010 --> 01:01:03,470
Hãy để thực sự thêm một vài chi tiết ở đây với một số lặp đi lặp lại.

746
01:01:03,470 --> 01:01:11,070
Vì vậy, giá trị, chúng tôi có ở đây, giá trị mà là có được mảng [i].

747
01:01:11,070 --> 01:01:14,850
Vì vậy, val có thể là 4 hoặc 8 hoặc bất cứ điều gì.

748
01:01:14,850 --> 01:01:18,870
Và bây giờ tôi đếm có bao nhiêu giá trị mà tôi đã nhìn thấy,

749
01:01:18,870 --> 01:01:21,230
để tính [val] + +;

750
01:01:21,230 --> 01:01:29,430
Sau này được thực hiện, số lượng sẽ xem xét một cái gì đó giống như 0001.

751
01:01:29,430 --> 01:01:42,190
Hãy làm tính [val] - RÀNG BUỘC + 1.

752
01:01:42,190 --> 01:01:48,230
>> Bây giờ đó là chỉ cần vào tài khoản cho một thực tế mà chúng tôi đang bắt đầu từ 0.

753
01:01:48,230 --> 01:01:50,850
Vì vậy, nếu 200 là có được số lượng lớn nhất của chúng tôi,

754
01:01:50,850 --> 01:01:54,720
sau đó 0 đến 200 là 201 điều.

755
01:01:54,720 --> 01:02:01,540
Vì vậy, số lượng, nó sẽ trông giống như 00.001 bởi vì chúng tôi có một trong 4.

756
01:02:01,540 --> 01:02:10,210
Sau đó, chúng ta sẽ có 0001 mà chúng ta sẽ có 1 trong các chỉ số 8 số.

757
01:02:10,210 --> 01:02:14,560
Chúng ta sẽ có 2 trong chỉ số 23 số.

758
01:02:14,560 --> 01:02:17,630
Chúng ta sẽ có một 2 trong chỉ mục thứ 42 của số.

759
01:02:17,630 --> 01:02:21,670
Vì vậy, chúng ta có thể sử dụng số.

760
01:02:34,270 --> 01:02:44,920
Vì vậy, num_of_item = đếm [i].

761
01:02:44,920 --> 01:02:52,540
Và vì vậy nếu num_of_item là 2, có nghĩa là chúng ta muốn chèn 2 số tôi

762
01:02:52,540 --> 01:02:55,290
vào mảng được sắp xếp của chúng tôi.

763
01:02:55,290 --> 01:03:02,000
Vì vậy, chúng ta cần phải theo dõi như thế nào đến nay chúng tôi vào mảng.

764
01:03:02,000 --> 01:03:05,470
Vì vậy, chỉ số = 0.

765
01:03:05,470 --> 01:03:09,910
Mảng - tôi sẽ chỉ viết nó.

766
01:03:16,660 --> 01:03:18,020
Đếm -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
Có phải đó là những gì tôi muốn? Tôi nghĩ rằng đó là những gì tôi muốn.

769
01:03:35,100 --> 01:03:38,290
Có, điều này có vẻ tốt. Okay.

770
01:03:38,290 --> 01:03:43,050
Vì vậy, không tất cả mọi người hiểu mục đích của mảng tính của tôi là gì?

771
01:03:43,050 --> 01:03:48,140
Nó đếm số lần xuất hiện của mỗi của những con số.

772
01:03:48,140 --> 01:03:51,780
Sau đó, tôi đang iterating trên mảng đó tính,

773
01:03:51,780 --> 01:03:57,190
và vị trí thứ i trong mảng tính

774
01:03:57,190 --> 01:04:01,930
là số của tôi là sẽ xuất hiện trong mảng được sắp xếp của tôi.

775
01:04:01,930 --> 01:04:06,840
Đó là lý do tại sao tội 4 có được 1

776
01:04:06,840 --> 01:04:11,840
và số lượng của 8 sẽ được 1, đếm của 23 sẽ là 2.

777
01:04:11,840 --> 01:04:16,900
Vì vậy, đó là nhiều người trong số họ như thế nào tôi muốn để chèn vào mảng được sắp xếp của tôi.

778
01:04:16,900 --> 01:04:19,200
Sau đó, tôi chỉ làm điều đó.

779
01:04:19,200 --> 01:04:28,960
Tôi chèn num_of_item i vào mảng sắp xếp của tôi.

780
01:04:28,960 --> 01:04:31,670
>> Câu hỏi?

781
01:04:32,460 --> 01:04:43,100
Và như vậy một lần nữa, đây là tuyến tính thời gian kể từ khi chúng tôi chỉ là iterating qua điều này một lần,

782
01:04:43,100 --> 01:04:47,470
nhưng nó cũng tuyến tính trong con số này sẽ xảy ra là,

783
01:04:47,470 --> 01:04:50,730
và do đó, nó phụ thuộc nhiều vào những gì ràng buộc của bạn.

784
01:04:50,730 --> 01:04:53,290
Với một ràng buộc là 200, đó là không phải là xấu.

785
01:04:53,290 --> 01:04:58,330
Nếu bị ràng buộc của bạn sẽ là 10.000, thì đó là tồi tệ hơn một chút,

786
01:04:58,330 --> 01:05:01,360
nhưng nếu ràng buộc của bạn là có được 4 tỷ đồng, đó là hoàn toàn không thực tế

787
01:05:01,360 --> 01:05:07,720
và mảng này sẽ có kích thước 4 tỷ đồng, đó là không thực tế.

788
01:05:07,720 --> 01:05:10,860
Vì vậy, đó là điều đó. Câu hỏi?

789
01:05:10,860 --> 01:05:13,270
[Không nghe được sinh viên phản ứng] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Tôi nhận ra một điều khác khi chúng tôi đã đi qua.

791
01:05:17,980 --> 01:05:23,720
Tôi nghĩ rằng vấn đề của Lucas và có lẽ mỗi người trong chúng ta đã thấy.

792
01:05:23,720 --> 01:05:26,330
Tôi hoàn toàn quên mất.

793
01:05:26,330 --> 01:05:31,040
Điều duy nhất tôi muốn nhận xét về là khi bạn đang làm việc với những thứ như các chỉ số,

794
01:05:31,040 --> 01:05:38,320
bạn không bao giờ thực sự thấy điều này khi bạn đang viết một vòng lặp for,

795
01:05:38,320 --> 01:05:41,120
nhưng về mặt kỹ thuật, bất cứ khi nào bạn đang làm việc với các chỉ số này,

796
01:05:41,120 --> 01:05:45,950
bạn có khá nhiều nên luôn luôn đối phó với số nguyên unsigned.

797
01:05:45,950 --> 01:05:53,850
Lý do cho điều này là khi bạn đang làm việc với số nguyên đã ký kết,

798
01:05:53,850 --> 01:05:56,090
vì vậy nếu bạn có 2 số nguyên ký và thêm chúng với nhau

799
01:05:56,090 --> 01:06:00,640
và họ kết thúc quá lớn, sau đó bạn kết thúc với một số âm.

800
01:06:00,640 --> 01:06:03,410
Vì vậy, đó là những gì số nguyên tràn.

801
01:06:03,410 --> 01:06:10,500
>> Nếu tôi thêm 2 tỷ đồng và 1 tỷ, tôi kết thúc với tiêu cực 1 tỷ.

802
01:06:10,500 --> 01:06:15,480
Đó là cách số nguyên làm việc trên máy tính.

803
01:06:15,480 --> 01:06:17,510
Vì vậy, các vấn đề với việc sử dụng -

804
01:06:17,510 --> 01:06:23,500
Đó là tốt ngoại trừ nếu thấp sẽ xảy ra là 2 tỷ đồng và sẽ xảy ra là 1 tỷ đồng,

805
01:06:23,500 --> 01:06:27,120
sau đó điều này là có được tiêu cực 1 tỷ và sau đó chúng ta sẽ phân chia cho 2

806
01:06:27,120 --> 01:06:29,730
và kết thúc với âm 500 triệu.

807
01:06:29,730 --> 01:06:33,760
Vì vậy, đây chỉ là một vấn đề nếu bạn xảy ra để được tìm kiếm thông qua một mảng

808
01:06:33,760 --> 01:06:38,070
tỷ thứ.

809
01:06:38,070 --> 01:06:44,050
Nhưng nếu thấp + lên xảy ra tràn, thì đó là một vấn đề.

810
01:06:44,050 --> 01:06:47,750
Ngay khi chúng tôi làm cho họ unsigned, sau đó 2 tỷ đồng cộng với 1 tỷ là 3 tỷ đồng.

811
01:06:47,750 --> 01:06:51,960
3 tỷ đồng chia cho 2 là 1,5 tỷ đồng.

812
01:06:51,960 --> 01:06:55,670
Vì vậy, ngay sau khi chúng được unsigned, mọi thứ đều hoàn hảo.

813
01:06:55,670 --> 01:06:59,900
Và đó là cũng là một vấn đề khi bạn đang viết cho các vòng,

814
01:06:59,900 --> 01:07:03,940
và trên thực tế, nó có thể sẽ làm tự động.

815
01:07:09,130 --> 01:07:12,330
Nó sẽ thực sự chỉ cần hét lên với bạn.

816
01:07:12,330 --> 01:07:21,610
Vì vậy, nếu con số này là quá lớn để có trong chỉ là một số nguyên nhưng nó sẽ phù hợp với một số nguyên unsigned,

817
01:07:21,610 --> 01:07:24,970
nó sẽ la lên ở bạn, vì vậy đó là lý do tại sao bạn không bao giờ thực sự chạy vào vấn đề.

818
01:07:29,150 --> 01:07:34,820
Bạn có thể thấy rằng một chỉ số sẽ không bao giờ được tiêu cực,

819
01:07:34,820 --> 01:07:39,220
và do đó, khi bạn đang iterating trên mảng,

820
01:07:39,220 --> 01:07:43,970
bạn hầu như luôn luôn có thể nói unsigned int i, nhưng bạn không thực sự có.

821
01:07:43,970 --> 01:07:47,110
Những điều sẽ làm việc khá nhiều chỉ là tốt.

822
01:07:48,740 --> 01:07:50,090
Okay. [Thì thầm] What time is it?

823
01:07:50,090 --> 01:07:54,020
Điều cuối cùng tôi muốn thể hiện và tôi sẽ chỉ làm điều đó thực sự nhanh chóng.

824
01:07:54,020 --> 01:08:03,190
Bạn biết làm thế nào chúng ta đã # define # vì vậy chúng tôi có thể xác định MAX là 5 hoặc một cái gì đó?

825
01:08:03,190 --> 01:08:05,940
Hãy không làm MAX. # Xác định RÀNG BUỘC tới 200. Đó là những gì chúng tôi đã làm trước đây.

826
01:08:05,940 --> 01:08:10,380
Định nghĩa một hằng số, mà chỉ là sẽ được sao chép và dán

827
01:08:10,380 --> 01:08:13,010
bất cứ nơi nào chúng tôi xảy ra để viết RÀNG BUỘC.

828
01:08:13,010 --> 01:08:18,189
>> Vì vậy, chúng tôi thực sự có thể làm nhiều hơn với # định nghĩa.

829
01:08:18,189 --> 01:08:21,170
Chúng tôi # có thể xác định chức năng.

830
01:08:21,170 --> 01:08:23,410
Họ không thực sự chức năng, nhưng chúng tôi sẽ gọi cho họ chức năng.

831
01:08:23,410 --> 01:08:36,000
Một ví dụ sẽ là một cái gì đó như MAX (x, y) được định nghĩa là (x <y y: x). Okay.

832
01:08:36,000 --> 01:08:40,660
Vì vậy, bạn nên làm quen với cú pháp điều hành ternary,

833
01:08:40,660 --> 01:08:49,029
nhưng là x ít hơn y? Quay trở lại y, khác trở về x.

834
01:08:49,029 --> 01:08:54,390
Vì vậy, bạn có thể thấy bạn có thể làm cho chức năng riêng biệt,

835
01:08:54,390 --> 01:09:01,399
và chức năng có thể là như bool MAX mất 2 đối số, trả lại điều này.

836
01:09:01,399 --> 01:09:08,340
Đây là một trong những phổ biến nhất mà tôi thấy được thực hiện như thế này. Chúng tôi gọi họ là macro.

837
01:09:08,340 --> 01:09:11,790
Đây là một vĩ mô.

838
01:09:11,790 --> 01:09:15,859
Đây chỉ là cú pháp cho nó.

839
01:09:15,859 --> 01:09:18,740
Bạn có thể viết một macro để làm bất cứ điều gì bạn muốn.

840
01:09:18,740 --> 01:09:22,649
Bạn thường xuyên thấy các macro để gỡ lỗi printfs và các công cụ.

841
01:09:22,649 --> 01:09:29,410
Vì vậy, một loại printf, có là hằng số đặc biệt trong C như gạch dưới DÒNG gạch dưới,

842
01:09:29,410 --> 01:09:31,710
2 nhấn DÒNG gạch dưới,

843
01:09:31,710 --> 01:09:37,550
và tôi cũng nghĩ rằng 2 nhấn FUNC. Đó có thể là nó. Một cái gì đó như thế.

844
01:09:37,550 --> 01:09:40,880
Những điều này sẽ được thay thế bằng tên của chức năng

845
01:09:40,880 --> 01:09:42,930
hoặc số của dòng mà bạn đang ở trên.

846
01:09:42,930 --> 01:09:48,630
Thường xuyên, bạn viết printfs gỡ lỗi mà xuống đây tôi có thể sau đó chỉ cần viết

847
01:09:48,630 --> 01:09:54,260
DEBUG và nó sẽ in số dòng và chức năng mà tôi xảy ra được trong

848
01:09:54,260 --> 01:09:57,020
mà nó gặp phải tuyên bố rằng DEBUG.

849
01:09:57,020 --> 01:09:59,550
Và bạn cũng có thể in những thứ khác.

850
01:09:59,550 --> 01:10:05,990
Vì vậy, có một điều bạn nên xem ra cho là nếu tôi xảy ra # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
như là một cái gì đó giống như 2 * y và 2 * x.

852
01:10:11,380 --> 01:10:14,310
Vì vậy, đối với lý do nào, bạn xảy ra để làm điều đó rất nhiều.

853
01:10:14,310 --> 01:10:16,650
Vì vậy, làm cho nó một macro.

854
01:10:16,650 --> 01:10:18,680
Điều này thực sự bị phá vỡ.

855
01:10:18,680 --> 01:10:23,050
Tôi sẽ gọi nó bằng cách làm một cái gì đó như DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Vì vậy, những gì nên được trả lại?

857
01:10:28,840 --> 01:10:30,580
[Sinh viên] 12.

858
01:10:30,580 --> 01:10:34,800
Có, 12 nên được trả lại, và 12 được trả lại.

859
01:10:34,800 --> 01:10:43,350
3 được thay thế cho x, 6 được thay thế cho y, và chúng tôi trở lại 2 * 6, là 12.

860
01:10:43,350 --> 01:10:47,710
Bây giờ những gì về điều này? Những gì nên được quay trở lại?

861
01:10:47,710 --> 01:10:50,330
[Sinh viên] 14. >> Lý tưởng nhất, 14.

862
01:10:50,330 --> 01:10:55,290
Vấn đề là làm thế nào băm xác định công việc, hãy nhớ đó là một bản sao đen và dán

863
01:10:55,290 --> 01:11:00,160
của tất cả mọi thứ khá nhiều, do đó, điều này sẽ được giải thích như

864
01:11:00,160 --> 01:11:11,270
3 so với 1 cộng với 6, 2 lần 1 cộng với 6, 2 lần 3.

865
01:11:11,270 --> 01:11:19,780
>> Vì vậy, vì lý do này, bạn hầu như luôn luôn quấn tất cả mọi thứ trong ngoặc đơn.

866
01:11:22,180 --> 01:11:25,050
Bất kỳ biến bạn gần như luôn luôn quấn trong dấu ngoặc đơn.

867
01:11:25,050 --> 01:11:29,570
Có những trường hợp mà bạn không có, như tôi biết rằng tôi không cần phải làm điều đó ở đây

868
01:11:29,570 --> 01:11:32,110
vì ít hơn khá nhiều luôn luôn chỉ cần đi để làm việc,

869
01:11:32,110 --> 01:11:34,330
mặc dù thậm chí có thể không phải là sự thật.

870
01:11:34,330 --> 01:11:41,870
Nếu có cái gì đó vô lý như DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
sau đó sẽ được thay thế với 3 so với 1 tương đương với bằng 2,

872
01:11:49,760 --> 01:11:53,460
và như vậy sau đó nó sẽ phải làm 3 ít hơn 1, điều đó bằng 2,

873
01:11:53,460 --> 01:11:55,620
mà không phải là những gì chúng ta muốn.

874
01:11:55,620 --> 01:12:00,730
Vì vậy, để ngăn chặn bất kỳ nhà điều hành các vấn đề ưu tiên,

875
01:12:00,730 --> 01:12:02,870
luôn luôn bọc trong dấu ngoặc đơn.

876
01:12:03,290 --> 01:12:07,700
Okay. Và đó là nó, 5:30.

877
01:12:08,140 --> 01:12:12,470
Nếu bạn có bất kỳ câu hỏi trên pset, cho chúng tôi biết.

878
01:12:12,470 --> 01:12:18,010
Nó sẽ được vui vẻ, và phiên bản hacker cũng là thực tế hơn nhiều

879
01:12:18,010 --> 01:12:22,980
so với phiên bản hacker năm ngoái, vì vậy chúng tôi hy vọng rằng rất nhiều bạn thử nó.

880
01:12:22,980 --> 01:12:26,460
Năm ngoái đã rất áp đảo.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]