1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [เล่นเพลง]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> เดวิดเจลัน: นี่คือ CS50

5
00:00:12,550 --> 00:00:14,612
และนี่คือจุดเริ่มต้นของสัปดาห์ที่สาม

6
00:00:14,612 --> 00:00:16,820
ดังนั้นเราจึงได้มีจำนวนมากที่น่าตื่นเต้น
สิ่งที่จะครอบคลุมในวันนี้

7
00:00:16,820 --> 00:00:20,160
จำนวนมากของโอกาสในการ
อาสาสมัครขึ้นไปบนเวที

8
00:00:20,160 --> 00:00:22,780
และท้ายที่สุดในวันนี้คือ
ไม่ได้เกี่ยวกับรหัสที่ทั้งหมด

9
00:00:22,780 --> 00:00:24,820
แต่มันเป็นเรื่องของความคิดและ
มันเป็นเรื่องของขั้นตอนวิธี

10
00:00:24,820 --> 00:00:28,420
และที่จริงกลับมาบางส่วนของ
บทเรียนที่ได้จากสัปดาห์ที่ศูนย์

11
00:00:28,420 --> 00:00:31,910
ประเด็นการเรียกคืนเรา
แนะนำประหลาดนี้

12
00:00:31,910 --> 00:00:33,880
และแรงบันดาลใจการกู้ยืมเงิน
จากที่จะเริ่มต้น

13
00:00:33,880 --> 00:00:36,879
เพื่อแก้ปัญหาที่เคยซับซ้อนมากขึ้น
ปัญหาอัลกอริทึม

14
00:00:36,879 --> 00:00:38,420
แต่ก่อนคู่ของประกาศ

15
00:00:38,420 --> 00:00:42,020
ดังนั้นหนึ่งถ้าคุณต้องการที่จะเข้าร่วม
พนักงาน CS50 และเพื่อนร่วมชั้นที่รับประทานอาหารกลางวัน

16
00:00:42,020 --> 00:00:44,670
ศุกร์นี้ทั้งที่นี่และใน
เคมบริดจ์และใน New Haven,

17
00:00:44,670 --> 00:00:48,060
กรุณาเยี่ยมชมการเรียนการสอนของ
เว็บไซต์ที่ URL ที่สามารถพบได้

18
00:00:48,060 --> 00:00:50,390
บรรยายพุธนี้จะ
ไม่ได้อยู่ที่นี่ในแซนเดอ

19
00:00:50,390 --> 00:00:53,610
มันจะเป็นแบบออนไลน์เท่านั้นดังนั้น
ปรับแต่งในที่เว็บไซต์ CS50 ของ

20
00:00:53,610 --> 00:00:55,850
ไม่ว่าจะเป็นที่นี่ในเคมบริดจ์
หรือ New Haven ได้เป็นอย่างดี

21
00:00:55,850 --> 00:00:58,110
>> และปัญหาที่เกิดขึ้นแล้วตั้งสอง
ที่มีอยู่แล้วในมือของคุณ

22
00:00:58,110 --> 00:01:03,067
หากคุณไม่ได้ดำดิ่งในยังให้ฉัน
ที่จะนำเสนอข้อเสนอแนะถ้อยคำรุนแรง

23
00:01:03,067 --> 00:01:05,150
โดยเฉพาะอย่างยิ่งตอนนี้เป็น
ปัญหาการตั้งค่าล่วงหน้า

24
00:01:05,150 --> 00:01:08,669
จริงๆคุณต้องการที่จะเริ่มต้นตอนนี้หากไม่ได้
ตะลุยบิตบนวันหยุดสุดสัปดาห์หรือก่อนที่

25
00:01:08,669 --> 00:01:10,710
เมื่อพวกเขาออกไปใน
วันศุกร์เพราะคุณจะ

26
00:01:10,710 --> 00:01:14,380
พบว่าพวกเขาไม่จำเป็นต้อง
ได้รับอีกต่อไปหรือท้าทายมากขึ้นต่อ

27
00:01:14,380 --> 00:01:14,950
ทางทิศตะวันออก

28
00:01:14,950 --> 00:01:17,575
ผมคิดว่าคุณจะพบว่าใน
โดยทั่วไปพวกเขามีแนวโน้มที่จะใช้เวลาประมาณ

29
00:01:17,575 --> 00:01:18,892
รอบระยะเวลาเดียวกัน

30
00:01:18,892 --> 00:01:20,850
แต่มันขึ้นอยู่อย่างแน่นอน
นักเรียนและมัน

31
00:01:20,850 --> 00:01:22,880
ขึ้นอยู่กับความคิด
ที่คุณเข้าใกล้มัน

32
00:01:22,880 --> 00:01:24,910
แต่อย่างสม่ำเสมอคุณจะ
เพื่อให้ทำงานขึ้นกับผนังบาง

33
00:01:24,910 --> 00:01:26,350
และคุณกำลังจะตี
ข้อผิดพลาดบางอย่างและคุณเพียงแค่

34
00:01:26,350 --> 00:01:27,950
จะไม่สามารถที่จะ
ได้รับมากกว่านั้นในบางจุด

35
00:01:27,950 --> 00:01:31,380
และมันก็มีคุณค่าอย่างมหาศาลที่จะสามารถ
จะก้าวออกไปกลับมาในวันรุ่งขึ้น

36
00:01:31,380 --> 00:01:35,286
ไปเวลาทำการโพสต์ใน CS50 พูดคุย
หรือชอบที่จะได้รับจริงยกเลิกการปิดกั้น

37
00:01:35,286 --> 00:01:36,160
ดังนั้นเก็บที่ในใจ

38
00:01:36,160 --> 00:01:40,830
เริ่มต้นที่เก่าแก่ที่สุดเท่าที่จะทำได้
เป็นสิ่งที่ดีที่สุดที่คุณสามารถทำได้

39
00:01:40,830 --> 00:01:44,160
ดังนั้นนี่คือที่เราเริ่มต้น
ชั้นกว่าในสัปดาห์ที่ศูนย์

40
00:01:44,160 --> 00:01:47,441
และเราจะได้รับอาสาสมัคร
ที่นี่จะช่วยให้ฉันพบไมโครโฟน?

41
00:01:47,441 --> 00:01:47,940
ตกลง.

42
00:01:47,940 --> 00:01:48,900
ลุกขึ้นยืนแล้ว

43
00:01:48,900 --> 00:01:50,080
มาขึ้น

44
00:01:50,080 --> 00:01:53,707
เดาว่าเป็นวิธีการที่จะไปทำงาน

45
00:01:53,707 --> 00:01:54,415
คุณชื่ออะไร?

46
00:01:54,415 --> 00:01:55,570
ลัน ESTRADA: อลันดา

47
00:01:55,570 --> 00:01:56,778
เดวิดเจลัน: อลันดา

48
00:01:56,778 --> 00:01:57,910
มาขึ้น

49
00:01:57,910 --> 00:01:58,619
ยินดีที่ได้พบคุณ.

50
00:01:58,619 --> 00:01:59,910
ลัน ESTRADA: ยินดีที่ได้พบคุณ

51
00:01:59,910 --> 00:02:02,772
เดวิดเจลัน: และคุณได้ที่นี่
กับเราในสัปดาห์ที่ศูนย์แน่นอน

52
00:02:02,772 --> 00:02:03,028
ลัน ESTRADA: ฉันเป็น

53
00:02:03,028 --> 00:02:03,160
ฉันเป็น.

54
00:02:03,160 --> 00:02:05,868
>> เดวิดเจลัน: ดังนั้นคุณอาจจะไป
ไปข้างหน้าและหาสำหรับเราไมค์สมิ ธ

55
00:02:05,868 --> 00:02:08,639
เป็นอย่างที่คุณสามารถ?

56
00:02:08,639 --> 00:02:10,639
ให้เร็วที่สุดเท่าที่คุณสามารถ

57
00:02:10,639 --> 00:02:13,756
แท้จริงฉีกปัญหา
ในช่วงครึ่งปีตามที่คุณต้องการ

58
00:02:13,756 --> 00:02:15,130
>> ลัน ESTRADA: อืม

59
00:02:15,130 --> 00:02:17,380
เดวิดเจลัน: แท้จริง
ปัญหาการฉีกขาดในช่วงครึ่งปี

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> ลัน ESTRADA: โอ้

62
00:02:22,083 --> 00:02:22,583
มิลลิเมตร

63
00:02:22,583 --> 00:02:23,300
ดีมาก.

64
00:02:23,300 --> 00:02:23,700
>> เดวิดเจลัน: OK

65
00:02:23,700 --> 00:02:24,200
ดี

66
00:02:24,200 --> 00:02:24,701
ขอขอบคุณ.

67
00:02:24,701 --> 00:02:25,700
ลัน ESTRADA: ดีมาก

68
00:02:25,700 --> 00:02:26,210
ตกลง.

69
00:02:26,210 --> 00:02:27,610
>> เดวิดเจลัน: และดังนั้นตอนนี้
คุณเหลาลง

70
00:02:27,610 --> 00:02:29,320
จะมีขนาดครึ่งหนึ่งของปัญหา

71
00:02:29,320 --> 00:02:31,267
ตอนนี้เรากำลังลงไปในสี่

72
00:02:31,267 --> 00:02:33,475
คุณให้ความสนใจกับ
ที่ด้านข้างที่เรากำลังรักษา?

73
00:02:33,475 --> 00:02:34,405
>> [หัวเราะ]

74
00:02:34,405 --> 00:02:35,970
>> ลัน ESTRADA: ใช่ฉัน think--

75
00:02:35,970 --> 00:02:37,594
>> เดวิดเจลัน: ส่วนสิ่งที่เรามีอะไรบ้าง?

76
00:02:37,594 --> 00:02:39,150
ลัน ESTRADA: Mufflers ดังนั้น

77
00:02:39,150 --> 00:02:39,941
>> เดวิดเจลัน: OK

78
00:02:39,941 --> 00:02:42,810
แต่ไมค์สมิ ธ เป็นไป
จะเป็นหลังจาก Mufflers

79
00:02:42,810 --> 00:02:44,130
So--

80
00:02:44,130 --> 00:02:48,180
>> [หัวเราะ]

81
00:02:48,180 --> 00:02:48,742
>> ทั้งหมดขวา

82
00:02:48,742 --> 00:02:50,200
ลัน ESTRADA: เรามองหาที่ไหน?

83
00:02:50,200 --> 00:02:52,049
เดวิดเจลัน: ไมค์สมิ ธ

84
00:02:52,049 --> 00:02:53,090
ลัน ESTRADA: ไมค์สมิ ธ

85
00:02:53,090 --> 00:02:54,760
เดวิดเจลัน: ตอนนี้เรากำลังอยู่ในการผ่าตัด

86
00:02:54,760 --> 00:02:57,840
ตอนนี้แพทย์

87
00:02:57,840 --> 00:02:58,340
Now--

88
00:02:58,340 --> 00:02:59,856
>> ลัน ESTRADA: Let's- ให้เป็นไปด้วยความจริง

89
00:02:59,856 --> 00:03:00,370
จริง.

90
00:03:00,370 --> 00:03:00,970
>> เดวิดเจลัน: จริง

91
00:03:00,970 --> 00:03:01,470
ตกลง.

92
00:03:01,470 --> 00:03:03,700
หากคุณต้องการจริง

93
00:03:03,700 --> 00:03:05,250
ในขณะนี้ซึ่งทางไมค์สมิ ธ

94
00:03:05,250 --> 00:03:06,250
>> ลัน ESTRADA: วิธีนี้

95
00:03:06,250 --> 00:03:07,333
>> เดวิดเจลัน: ทางไหน?

96
00:03:07,333 --> 00:03:08,240
ลัน ESTRADA: รอ

97
00:03:08,240 --> 00:03:08,790
M สิทธิ is--?

98
00:03:08,790 --> 00:03:09,110
เราเริ่มต้น with--

99
00:03:09,110 --> 00:03:10,090
>> เดวิดเจลัน: ใช่

100
00:03:10,090 --> 00:03:10,650
พวกเขากำลังที่เหลือ

101
00:03:10,650 --> 00:03:11,430
คุณถูก.

102
00:03:11,430 --> 00:03:11,710
>> ลัน ESTRADA: ใช่

103
00:03:11,710 --> 00:03:13,126
>> เดวิดเจลัน: ดังนั้นไมค์ที่นี่

104
00:03:13,126 --> 00:03:13,990
ลัน ESTRADA: อะไรนะ?

105
00:03:13,990 --> 00:03:14,665
>> [หัวเราะ]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> ตัวอย่างที่ไม่ดีครับ

108
00:03:18,330 --> 00:03:18,830
ขอโทษ

109
00:03:18,830 --> 00:03:21,610
เดวิดเจลัน: นี้จะสอน
คุณจะกระโดดออกมาจากเก้าอี้ของคุณ

110
00:03:21,610 --> 00:03:22,318
>> ลัน ESTRADA: โอ้

111
00:03:22,318 --> 00:03:22,890
โอ้

112
00:03:22,890 --> 00:03:23,390
ผมมีคุณ

113
00:03:23,390 --> 00:03:24,670
ผมมีคุณ

114
00:03:24,670 --> 00:03:25,170
โอ้

115
00:03:25,170 --> 00:03:25,669
โอ้

116
00:03:25,669 --> 00:03:26,812
is-- นี้ตกลงฉันมีคุณ

117
00:03:26,812 --> 00:03:27,520
สมิ ธ ที่นี่?

118
00:03:27,520 --> 00:03:28,894
>> เดวิดเจลัน: สมิ ธ ขอขอบคุณ

119
00:03:28,894 --> 00:03:30,535
ดังนั้นฉันจะให้มองถึงสมิ ธ

120
00:03:30,535 --> 00:03:30,790
>> ลัน ESTRADA: โอ้ใช่

121
00:03:30,790 --> 00:03:31,340
ไม่ไม่ไม่.

122
00:03:31,340 --> 00:03:31,600
ไม่นะ.

123
00:03:31,600 --> 00:03:31,940
นี่เป็นของฉัน.

124
00:03:31,940 --> 00:03:32,580
>> เดวิดเจลัน: โอ้คุณมีสมิ ธ

125
00:03:32,580 --> 00:03:33,415
ตกลง.

126
00:03:33,415 --> 00:03:34,040
>> ลัน ESTRADA: ใช่ฉัน
สมิ ธ ได้ที่นี่

127
00:03:34,040 --> 00:03:34,700
ขอโทษนะเพื่อน.

128
00:03:34,700 --> 00:03:35,860
ผมคิดว่าเรา Michael--
เขากำลังมองหาไมเคิล

129
00:03:35,860 --> 00:03:36,550
ขอโทษ

130
00:03:36,550 --> 00:03:37,550
>> เดวิดเจลัน: มันตกลง

131
00:03:37,550 --> 00:03:39,950
สิทธิทั้งหมดตอนนี้เรากำลัง
เข้า Paccini และบุตร

132
00:03:39,950 --> 00:03:41,242
>> ลัน ESTRADA: Paccini และบุตรชาย

133
00:03:41,242 --> 00:03:43,158
เดวิดเจลัน: เฉพาะคุณ
และผมอยู่ในนี้

134
00:03:43,158 --> 00:03:44,050
ตกลง.

135
00:03:44,050 --> 00:03:45,130
พบกับเราไมค์สมิ ธ

136
00:03:45,130 --> 00:03:45,830
สมิ ธ

137
00:03:45,830 --> 00:03:46,310
>> ลัน ESTRADA: สมิ ธ

138
00:03:46,310 --> 00:03:46,750
>> เดวิดเจลัน: สมิ ธ

139
00:03:46,750 --> 00:03:47,728
เราอยู่ในอาขยะ

140
00:03:47,728 --> 00:03:48,644
ลัน ESTRADA: แย่มาก

141
00:03:48,644 --> 00:03:50,096
โอ้

142
00:03:50,096 --> 00:03:52,480
นี้จะใช้เวลาสักครู่

143
00:03:52,480 --> 00:03:54,340
>> [หัวเราะ]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
เดวิดเจลันรองเท้า

146
00:03:56,720 --> 00:03:58,080
เราอยู่ในรองเท้า

147
00:03:58,080 --> 00:04:00,210
>> ลัน ESTRADA: ตอนนี้เรากำลัง gonna--

148
00:04:00,210 --> 00:04:01,105
>> เดวิดเจลัน: ดี

149
00:04:01,105 --> 00:04:01,980
ลัน ESTRADA: Which--

150
00:04:01,980 --> 00:04:03,620
[หัวเราะ]

151
00:04:03,620 --> 00:04:05,440
โอ้นี้เป็นที่ดี

152
00:04:05,440 --> 00:04:06,910
[หัวเราะ]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> เดวิดเจลัน: มันตกลง

155
00:04:09,390 --> 00:04:11,365
>> ลัน ESTRADA: โอ้นี่เป็นสิ่งที่ดี

156
00:04:11,365 --> 00:04:14,425
ฉันไม่คิดว่าฉันจะ
มีเพื่อน PSAT หลังจากนี้

157
00:04:14,425 --> 00:04:15,300
เดวิดเจลัน: ดี

158
00:04:15,300 --> 00:04:16,078
กีฬา

159
00:04:16,078 --> 00:04:17,036
ลัน ESTRADA: กีฬา

160
00:04:17,036 --> 00:04:18,668
อืม, L, M, N, O, พี

161
00:04:18,668 --> 00:04:19,459
เดวิดเจลัน: OK

162
00:04:19,459 --> 00:04:21,600
ดังนั้นขอฉีกนี้ในช่วงครึ่งปี

163
00:04:21,600 --> 00:04:22,270
ไม่เป็นไร.

164
00:04:22,270 --> 00:04:25,606
จบไม่ดีนี้ต่อไปเพราะไมค์
สมิ ธ จะไม่อยู่ในสมุดหน้าเหลือง

165
00:04:25,606 --> 00:04:26,430
>> ลัน ESTRADA: Aw

166
00:04:26,430 --> 00:04:27,140
>> เดวิดเจลัน: ไม่มีก็ OK

167
00:04:27,140 --> 00:04:28,930
แต่ขอหลอกเช่น
เขาอยู่บนหน้านี้

168
00:04:28,930 --> 00:04:33,260
ดังนั้นตอนนี้คุณเหลาปัญหาลง
ให้เป็นหนึ่งในหน้าและเราพบว่าไมค์สมิ ธ

169
00:04:33,260 --> 00:04:35,180
>> [เชียร์]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
OK ขอบคุณ.

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
ตกลง.

174
00:04:41,200 --> 00:04:43,646
นั่นเป็นพิเศษ

175
00:04:43,646 --> 00:04:45,954
แต่มันก็ยังคงได้เร็วขึ้น
กว่าการค้นหาเชิงเส้น

176
00:04:45,954 --> 00:04:47,870
นั้นเราจะเริ่มต้นที่
จุดเริ่มต้นของหนังสือเล่มนี้

177
00:04:47,870 --> 00:04:51,210
และเราย้ายไปทางของเราจากซ้ายไปขวา
ในที่สุดก็มองหาไมค์สมิ ธ

178
00:04:51,210 --> 00:04:53,540
ดังนั้นถ้าสมุดโทรศัพท์
อาจจะมี 1,000 หน้า

179
00:04:53,540 --> 00:04:56,300
บางทีมันอาจจะมีการดำเนินการ
เรา 10 หรือเพื่อน้ำตาหน้า

180
00:04:56,300 --> 00:04:59,380
>> แต่คุณอาจจะมีการยกระดับ
สัมผัสสมมติฐาน

181
00:04:59,380 --> 00:05:03,602
ในช่วงทุกที่ซึ่งเป็นที่จะบอกว่า
ว่าสมุดโทรศัพท์ล่วงหน้าคืออะไร?

182
00:05:03,602 --> 00:05:04,310
ผู้ชม: เรียง

183
00:05:04,310 --> 00:05:05,000
เดวิดเจลัน: มันเรียง

184
00:05:05,000 --> 00:05:05,160
ใช่มั้ย?

185
00:05:05,160 --> 00:05:07,909
มันเรียงตามตัวอักษรดังนั้น
ว่าทั้งหมดของชื่อเหล่านั้นและตัวเลข

186
00:05:07,909 --> 00:05:11,230
ถูกจัดเรียงจากเอไปยัง
Z และตัวอักษรที่อยู่ในระหว่าง

187
00:05:11,230 --> 00:05:13,100
แต่วันนี้เราตอนนี้ขอให้
คำถามที่ดี

188
00:05:13,100 --> 00:05:16,170
วิธีการทำ Verizon หรือโทรศัพท์
บริษัท ได้รับมันเป็นรัฐที่?

189
00:05:16,170 --> 00:05:19,560
>> เพราะมันเป็นสิ่งหนึ่งที่จะยกระดับ
สมมติฐานที่ว่าและดังนั้น

190
00:05:19,560 --> 00:05:22,570
แก้ปัญหาด้วยอย่างเป็น
ขั้นตอนวิธีการได้อย่างมีประสิทธิภาพ

191
00:05:22,570 --> 00:05:24,900
แต่เราไม่เคยจริงๆ
ถามในสัปดาห์ที่ศูนย์ดี

192
00:05:24,900 --> 00:05:27,790
มันราคาเท่าไหร่
Verizon หรือคนอื่น

193
00:05:27,790 --> 00:05:29,620
ที่จะได้รับสมุดโทรศัพท์ว่าในการเรียงลำดับ?

194
00:05:29,620 --> 00:05:29,780
>> ใช่มั้ย?

195
00:05:29,780 --> 00:05:31,529
มันไม่สำคัญว่าถ้า
เงยหน้าขึ้นมองไมค์สมิ ธ

196
00:05:31,529 --> 00:05:35,190
เป็นไปอย่างรวดเร็วสุดถ้าจะใช้เวลาคุณ
ปีในการจัดเรียงหน้าแรก

197
00:05:35,190 --> 00:05:35,690
ใช่มั้ย?

198
00:05:35,690 --> 00:05:38,620
คุณอาจมีเพียงลอด
ผ่านสมุดโทรศัพท์สุ่ม

199
00:05:38,620 --> 00:05:40,690
ถ้ามันเป็นไปได้สุด
ราคาแพงในการจัดเรียง

200
00:05:40,690 --> 00:05:42,350
ดังนั้นถ้าเราสามารถมีอาสาสมัครอีก

201
00:05:42,350 --> 00:05:46,350
ลองมามองขึ้นไปที่นี่ที่
วิธีการที่เรา might-- มา up-- วิธี

202
00:05:46,350 --> 00:05:48,100
เราอาจจะไปเกี่ยวกับการเรียงลำดับเหล่านี้

203
00:05:48,100 --> 00:05:51,990
>> และถ้าทำได้จริงจอร์แดน
เข้าร่วมกับเราได้ที่นี่บนเวที

204
00:05:51,990 --> 00:05:55,100
ขึ้นมาเพื่อรอสักครู่

205
00:05:55,100 --> 00:05:56,359
คุณชื่ออะไร?

206
00:05:56,359 --> 00:05:57,150
CAROLINE: แคโรไลน์

207
00:05:57,150 --> 00:05:58,691
เดวิดเจลัน: แคโรไลน์มาขึ้น

208
00:05:58,691 --> 00:06:02,070
และคุณจะได้เข้าร่วม
โดยผมและจอร์แดนที่นี่

209
00:06:02,070 --> 00:06:03,800
แคโรไลน์ขอขอบคุณ

210
00:06:03,800 --> 00:06:04,300
ทั้งหมดขวา

211
00:06:04,300 --> 00:06:08,330
ดังนั้นสิ่งที่เรามีที่นี่สำหรับ
แคโรไลน์ 26 หนังสือสีฟ้า

212
00:06:08,330 --> 00:06:10,747
FAS ที่ใช้ในการบริหารจัดการ
การสอบครั้งสุดท้ายบางอย่าง

213
00:06:10,747 --> 00:06:13,330
เหล่านี้จะได้รับยากที่จะหา
แต่สิ่งที่เราได้ทำไว้ล่วงหน้า

214
00:06:13,330 --> 00:06:15,800
คือการที่เราได้ใส่ชื่อของใครบางคน
ที่ด้านหน้าของแต่ละเหล่านี้

215
00:06:15,800 --> 00:06:18,133
แต่เราได้เก็บมันไว้โดยง่าย
แล้ววางออกชื่อเต็ม

216
00:06:18,133 --> 00:06:22,720
ดังนั้นเราจะทำให้คนที่มีชื่อ
L, D, J, B, ทุกทางของ A ถึง Z

217
00:06:22,720 --> 00:06:24,090
แต่พวกเขากำลังในการสุ่ม

218
00:06:24,090 --> 00:06:26,890
ดังนั้นถ้าคุณจะพูดคุยของคุณ
ทางผ่านปัญหาเป็นคุณ

219
00:06:26,890 --> 00:06:31,620
ไม่ว่าคุณสามารถไปข้างหน้าและ
เรียงลำดับเหล่านี้สำหรับเราจาก A ถึง Z

220
00:06:31,620 --> 00:06:34,070
>> ผู้ชม: ตกลงดังนั้น L เป็นเหมือนกลาง

221
00:06:34,070 --> 00:06:35,050
C เป็นจุดเริ่มต้น

222
00:06:35,050 --> 00:06:42,410
บีเจก่อนที่แอลบีคิว

223
00:06:42,410 --> 00:06:45,140
>> เดวิดเจลัน: กดที่
คิดว่าสำหรับคนที่สอง

224
00:06:45,140 --> 00:06:48,910
เพราะมิฉะนั้นนี้เป็นเพียง
ที่น่าสนใจให้กับคุณฉันและจอร์แดน

225
00:06:48,910 --> 00:06:49,724
เราจะไปที่นั่น.

226
00:06:49,724 --> 00:06:50,640
ผู้ชม: [ไม่ได้ยิน]

227
00:06:50,640 --> 00:06:57,299
อาร์

228
00:06:57,299 --> 00:06:58,090
เดวิดเจลัน: OK

229
00:06:58,090 --> 00:06:59,310
คุณกำลังทำอะไร?

230
00:06:59,310 --> 00:07:01,730
>> CAROLINE: เอ็มมาหลังจากทุม

231
00:07:01,730 --> 00:07:02,564
>> เดวิดเจลัน: OK

232
00:07:02,564 --> 00:07:03,064
>> CAROLINE: ทุม

233
00:07:03,064 --> 00:07:04,120
เดวิดเจลันโอ้, ดี

234
00:07:04,120 --> 00:07:04,970
>> CAROLINE: อี

235
00:07:04,970 --> 00:07:06,730
>> เดวิดเจลัน: E, เอฟใช่

236
00:07:06,730 --> 00:07:07,620
>> CAROLINE: T, U, โวลต์

237
00:07:07,620 --> 00:07:10,689
>> เดวิดเจลัน: V, T, U, โวลต์ดังนั้นจึง
ดูเหมือนว่าคุณกำลัง making-- เก็บไป

238
00:07:10,689 --> 00:07:12,730
ดูเหมือนว่าคุณกำลังทำ
กองใหญ่กว่าที่นี่

239
00:07:12,730 --> 00:07:13,910
และชนิดของกองใหญ่ที่นั่น

240
00:07:13,910 --> 00:07:16,230
ดังนั้นในช่วงครึ่งแรกของตัวอักษร
ช่วงครึ่งหลังของตัวอักษร

241
00:07:16,230 --> 00:07:16,460
ตกลง.

242
00:07:16,460 --> 00:07:16,960
ดี

243
00:07:16,960 --> 00:07:19,680
การแยกชนิดของปัญหาที่เกิดขึ้นในสอง

244
00:07:19,680 --> 00:07:21,771
M, N, เอ็กซ์ใช่

245
00:07:21,771 --> 00:07:22,270
CAROLINE: เค

246
00:07:22,270 --> 00:07:22,980
เดวิดเจลัน: OK

247
00:07:22,980 --> 00:07:25,070
เคดังนั้นคุณชนิดของการเลือก
พวกเขาเป็นหนึ่งหลังจากที่อื่น

248
00:07:25,070 --> 00:07:27,620
วางไว้ทั้งซ้ายหรือขวา
หรือไปซีบนพื้น

249
00:07:27,620 --> 00:07:28,012
ตกลง.

250
00:07:28,012 --> 00:07:29,190
>> CAROLINE: Z ที่เกิดขึ้นบนพื้น

251
00:07:29,190 --> 00:07:29,360
>> เดวิดเจลัน: OK

252
00:07:29,360 --> 00:07:30,920
Y ที่เกิดขึ้นบนพื้น

253
00:07:30,920 --> 00:07:31,735
ตอนนี้เราสามารถใส่เอ็กซ์

254
00:07:31,735 --> 00:07:32,409
>> CAROLINE: กรัม

255
00:07:32,409 --> 00:07:33,700
เดวิดเจลัน: จีไปซ้าย

256
00:07:33,700 --> 00:07:36,017
S เป็นไปทางด้านขวา

257
00:07:36,017 --> 00:07:37,642
สิทธิทั้งหมดจะไปตลอดทางซ้าย

258
00:07:37,642 --> 00:07:38,790
>> CAROLINE: A, B, C, D

259
00:07:38,790 --> 00:07:39,873
>> เดวิดเจลัน: ตอนนี้ดี

260
00:07:39,873 --> 00:07:43,260
เรามี A, B, W ของซีจะลงไปที่นั่น

261
00:07:43,260 --> 00:07:45,566
ทั้งหมดขวาที

262
00:07:45,566 --> 00:07:46,611
>> CAROLINE: H, I, เจ

263
00:07:46,611 --> 00:07:47,860
เดวิดเจลัน: H, I, ดีเจ

264
00:07:47,860 --> 00:07:49,160
CAROLINE: ในศูนย์ที่ฉัน gonna--

265
00:07:49,160 --> 00:07:50,000
เดวิดเจลัน: OK

266
00:07:50,000 --> 00:07:52,375
ดังนั้นตอนนี้เรากำลังจะชนิด
การผสานกองต่างๆเหล่านี้

267
00:07:52,375 --> 00:08:00,730
ดังนั้น A ถึง C แล้วฉันจะดูดีและ
E, และ F และ G และ H, และฉันดี

268
00:08:00,730 --> 00:08:05,540
เจเคแล้วกองนี้
คว่ำ แต่ที่ตกลง

269
00:08:05,540 --> 00:08:06,040
ตรวจสอบว่า

270
00:08:06,040 --> 00:08:07,240
เราสามารถตัดบางมุม

271
00:08:07,240 --> 00:08:07,950
ตกลง.

272
00:08:07,950 --> 00:08:10,530
และจากนั้นเราต้อง W, X, Y, ซี

273
00:08:10,530 --> 00:08:11,250
>> CAROLINE: ใช่

274
00:08:11,250 --> 00:08:11,880
>> เดวิดเจลัน: ยอดเยี่ยม

275
00:08:11,880 --> 00:08:14,122
ดังนั้นใหญ่ขอบคุณ
แคโรไลน์สำหรับการเรียงลำดับเหล่านี้

276
00:08:14,122 --> 00:08:15,030
>> [เชียร์]

277
00:08:15,030 --> 00:08:17,287
>> ขอขอบคุณ.

278
00:08:17,287 --> 00:08:18,120
ขอบคุณมาก.

279
00:08:18,120 --> 00:08:22,910
ดังนั้นตอนนี้ขอพิจารณาสักครู่
วิธีแคโรไลน์ไปเกี่ยวกับการทำที่

280
00:08:22,910 --> 00:08:26,040
และสิ่งที่เรา
ก็สามารถที่ to-- วิธีการที่เรา

281
00:08:26,040 --> 00:08:28,409
ก็สามารถที่จะแก้ปัญหาที่
ปัญหาที่เกิดขึ้นเมื่อเราเป็นเพียงแค่

282
00:08:28,409 --> 00:08:29,950
รับทั้งกลุ่มของปัจจัยการผลิตแบบสุ่ม

283
00:08:29,950 --> 00:08:31,610
>> ดีก็ดูเหมือนว่ามี
เป็นบิตของระบบมีหรือไม่?

284
00:08:31,610 --> 00:08:32,110
ขวา

285
00:08:32,110 --> 00:08:34,495
ดังนั้นตัวอักษรก่อนหน้านี้
ในตัวอักษรที่เธอ

286
00:08:34,495 --> 00:08:37,120
ก็วางไปทางซ้ายและ
ตัวอักษรต่อไปในตัวอักษร

287
00:08:37,120 --> 00:08:38,270
เธอถูกวางลงไปในที่ที่เหมาะสม

288
00:08:38,270 --> 00:08:40,500
และทันทีที่เธอพบว่า
บางตัวอักษรที่ใกล้ชิดคน

289
00:08:40,500 --> 00:08:43,124
ที่ไปทางขวาถัดจากแต่ละอื่น ๆ
เธอจะทำให้ผู้ที่อยู่ในการสั่งซื้อ

290
00:08:43,124 --> 00:08:46,750
และเพื่อให้เราชนิดมีขนาดเล็กเหล่านี้
กองของปัจจัยการผลิตที่เกิดขึ้นที่เรียงลำดับ

291
00:08:46,750 --> 00:08:50,540
>> และเพื่อให้เป็นสิ่งที่ค่อนข้างชอบ
มนุษย์ส่วนใหญ่ของเราจะทำอย่างไร

292
00:08:50,540 --> 00:08:53,530
เราจะเรียงลำดับของการลอดผ่านได้
และเราต้องการชนิดของการมีกลไก

293
00:08:53,530 --> 00:08:56,930
แต่มันอาจจะยากที่จะเขียน
มันลงในสูตรต่อ

294
00:08:56,930 --> 00:08:59,010
มันให้ความรู้สึกเล็ก ๆ น้อย ๆ อินทรีย์กว่านั้น

295
00:08:59,010 --> 00:09:02,560
ดังนั้นเรามาดูถ้าเราสามารถที่ถูกผูกไว้ในขณะนี้
ปัญหาที่เกิดขึ้นกับปัจจัยการผลิตน้อยลง

296
00:09:02,560 --> 00:09:05,170
>> แทนที่จะ 26 ขอ
ทำสิ่งที่ไกลน้อย

297
00:09:05,170 --> 00:09:09,890
ที่มีเพียงแค่พูดว่าเจ็ดหลัง
ประตูเหล่านี้เพื่อที่จะพูด

298
00:09:09,890 --> 00:09:11,300
มีเพียงเจ็ดตัวเลข?

299
00:09:11,300 --> 00:09:15,240
และถ้าเป้าหมายในขณะนี้ที่
มือคือการหาค่า

300
00:09:15,240 --> 00:09:17,850
เรามาดูวิธีได้อย่างมีประสิทธิภาพ
เราสามารถไปเกี่ยวกับการทำเช่นนี้

301
00:09:17,850 --> 00:09:22,460
และให้ดูว่าเราสามารถทำได้ในขณะนี้
เริ่มต้นที่จะใช้ตัวเลขบางอย่าง

302
00:09:22,460 --> 00:09:26,310
หรือสูตรบางอย่างกับการที่จะอธิบาย
ประสิทธิภาพของหนังสือเล่มโทรศัพท์ของเรา

303
00:09:26,310 --> 00:09:31,060
ขั้นตอนวิธีการขั้นตอนวิธีการสอบหนังสือของเราและ
มากขึ้นโดยทั่วไปในการหาข้อมูล

304
00:09:31,060 --> 00:09:34,770
>> ดังนั้นนี้ให้ฉันไปข้างหน้าและ
บนหน้าจอสัมผัสมากกว่าที่นี่

305
00:09:34,770 --> 00:09:41,100
นำขึ้นเว็บเบราเซอร์ที่มี
ว่าทั้งเจ็ดประตู

306
00:09:41,100 --> 00:09:46,670
และถ้าเราจะได้รับคนอื่น ๆ
อาสาสมัครที่จะมามากกว่าที่นี่

307
00:09:46,670 --> 00:09:48,480
ฉันได้ใส่ประตูเหล่านี้เหมือนกันมากกว่าที่นี่

308
00:09:48,480 --> 00:09:49,170
อาสาสมัครด่วน

309
00:09:49,170 --> 00:09:51,130
>> การสาธิต one-- นี้จะ
ไปได้เร็วขึ้นและเร็วขึ้นในขณะนี้

310
00:09:51,130 --> 00:09:51,600
มาลง

311
00:09:51,600 --> 00:09:52,308
คุณชื่ออะไร?

312
00:09:52,308 --> 00:09:53,040
เทรเวอร์: เทรเวอร์

313
00:09:53,040 --> 00:09:53,998
>> เดวิดเจลัน: เทรเวอร์?

314
00:09:53,998 --> 00:09:55,770
สิทธิทั้งหมดเทรเวอร์มาล​​ง

315
00:09:55,770 --> 00:09:59,212
ดังนั้นเทรเวอร์ได้อาสาที่นี่เพื่อ
ทำปัญหาที่คล้ายกัน แต่อย่างหนึ่งที่เป็น

316
00:09:59,212 --> 00:10:02,170
แคบอยู่ในขอบเขตและที่จะ
เพื่อให้เราพยายามที่จะทำพิธีในขณะนี้

317
00:10:02,170 --> 00:10:03,970
กระบวนการสำหรับการเรียงลำดับตัวเลขเหล่านี้

318
00:10:03,970 --> 00:10:05,500
>> ดังนั้นเทรเวอร์มีความสุขที่ได้พบคุณ

319
00:10:05,500 --> 00:10:08,720
ดังนั้นนี่คืออาร์เรย์เพื่อที่จะ
พูดรายการเจ็ดประตู

320
00:10:08,720 --> 00:10:10,327
ไปข้างหน้าและพบกับเราได้ที่หมายเลข 50

321
00:10:10,327 --> 00:10:12,410
และแล้วหลังจากที่ความจริง
บอกเราว่าคุณจะพบว่า

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
ควร be-- ทั้งหมดที่ด้านขวา

324
00:10:20,040 --> 00:10:21,945
ใช่นี้เป็นหนึ่งในที่นี่หรือไม่

325
00:10:21,945 --> 00:10:24,680
เอ่อโอ้.

326
00:10:24,680 --> 00:10:25,560
ตกลง.

327
00:10:25,560 --> 00:10:26,680
คุณคลิกที่หนึ่ง

328
00:10:26,680 --> 00:10:28,690
ดี

329
00:10:28,690 --> 00:10:29,780
>> และดี.

330
00:10:29,780 --> 00:10:30,970
ตอนนี้คุณคลิกที่หนึ่ง

331
00:10:30,970 --> 00:10:34,060
และให้ฉันให้ไมโครโฟน
เพื่อให้คุณได้ในเวลาเพียงสักครู่

332
00:10:34,060 --> 00:10:37,000
ไปข้างหน้าและคลิก
ประตูถัดไปที่คุณตั้งใจ

333
00:10:37,000 --> 00:10:39,812
ใช่ที่ดี

334
00:10:39,812 --> 00:10:41,020
เทรเวอร์: ฉันสามารถยกเลิกการคลิกประตู?

335
00:10:41,020 --> 00:10:42,620
เดวิดเจลัน: ไม่มีคุณจะไม่สามารถยกเลิกการคลิก

336
00:10:42,620 --> 00:10:43,119
เทรเวอร์: OK

337
00:10:43,119 --> 00:10:43,974
อันนี้.

338
00:10:43,974 --> 00:10:45,640
เดวิดเจลัน: คุณต้องการไปที่ไหน?

339
00:10:45,640 --> 00:10:46,410
อันไหน?

340
00:10:46,410 --> 00:10:47,230
>> เทรเวอร์: ที่หนึ่ง

341
00:10:47,230 --> 00:10:48,042
>> เดวิดเจลัน: เลขที่

342
00:10:48,042 --> 00:10:48,450
>> เทรเวอร์: OK

343
00:10:48,450 --> 00:10:48,735
อันนี้.

344
00:10:48,735 --> 00:10:49,020
>> เดวิดเจลัน: ใช่

345
00:10:49,020 --> 00:10:49,700
นั่นเป็นสิ่งที่ดี.

346
00:10:49,700 --> 00:10:50,380
ทั้งหมดขวา

347
00:10:50,380 --> 00:10:53,900
ดังนั้นสิ่งที่เป็นอัลกอริทึมของคุณหรือ
ขั้นตอนในการทำเช่นนี้เทรเวอร์?

348
00:10:53,900 --> 00:10:56,149
>> เทรเวอร์: ผมเพิ่งผ่านไป
ประตูจนผมพบว่า 50

349
00:10:56,149 --> 00:10:56,940
เดวิดเจลัน: OK

350
00:10:56,940 --> 00:10:58,150
ขั้นตอนวิธีการที่ดีเยี่ยม

351
00:10:58,150 --> 00:10:59,540
ดังนั้นที่ดี

352
00:10:59,540 --> 00:11:03,120
เพราะในความเป็นจริงถ้าผมแสดงให้เห็นว่ามีอะไร
ที่อยู่เบื้องหลังทั้งสองประตูอื่น ๆ สิ่งที่

353
00:11:03,120 --> 00:11:06,954
เราจะพบว่าที่นี่คือ
เรามีเพียงการป้อนข้อมูลแบบสุ่ม

354
00:11:06,954 --> 00:11:08,870
เพื่อให้เป็นจริง
ดีที่สุดเท่าที่คุณจะได้รับ

355
00:11:08,870 --> 00:11:12,509
และในความเป็นจริงคุณได้ดีกว่า
การค้นหาอย่างละเอียดถี่ถ้วนอาร์เรย์ทั้ง

356
00:11:12,509 --> 00:11:15,300
เพราะมันจะได้รับจริงๆ
ถ้าคุณโชคร้ายได้ตีจำนวน

357
00:11:15,300 --> 00:11:16,604
50 ที่ประตูสุดท้าย

358
00:11:16,604 --> 00:11:18,520
แต่ถ้าเราแทน
ให้คุณสมมติฐาน

359
00:11:18,520 --> 00:11:20,630
สมมติว่าฉันจัดเรียงทั้งหมดของ
ประตูเหล่านี้ไปรอบ ๆ

360
00:11:20,630 --> 00:11:23,500
เพื่อให้คุณมี
ตัวเลขเรียงเวลานี้

361
00:11:23,500 --> 00:11:29,730
แต่เวลานี้ก็จริง
different-- เวลานี้

362
00:11:29,730 --> 00:11:32,640
มันเรียงจริงสำหรับคุณ

363
00:11:32,640 --> 00:11:35,380
และตอนนี้เป้าหมายที่อยู่ในมือ
คือการตีจำนวน 50

364
00:11:35,380 --> 00:11:36,090
>> เทรเวอร์: OK

365
00:11:36,090 --> 00:11:37,670
>> เดวิดเจลัน: มีอะไร
ขั้นตอนวิธีการของคุณจะเป็นอย่างไร

366
00:11:37,670 --> 00:11:39,628
>> เทรเวอร์: ดีถ้ามัน
เรียงมันเป็นอย่างใดอย่างหนึ่งไป

367
00:11:39,628 --> 00:11:42,710
เพื่อ be-- ถ้าที่ใหญ่ที่สุดที่ใหญ่ที่สุด
ลงมาก็จะเป็นคนแรก

368
00:11:42,710 --> 00:11:44,751
หรือถ้ามันเป็นตรงข้าม
มันจะเป็นคนสุดท้าย

369
00:11:44,751 --> 00:11:48,897
ดังนั้นผมก็จะแตะที่ประตูนี้และ
จากนั้นเพียงแค่แตะประตูที่ผ่านมา

370
00:11:48,897 --> 00:11:49,980
เดวิดเจลัน: ยอดเยี่ยม

371
00:11:49,980 --> 00:11:50,270
ทั้งหมดขวา

372
00:11:50,270 --> 00:11:51,150
ดังนั้นเราจึงพบว่าจำนวน 50

373
00:11:51,150 --> 00:11:52,970
ดังนั้นทันทีที่คุณรู้ว่า
พวกเขาถูกจัดเรียงเรา

374
00:11:52,970 --> 00:11:55,040
ก็สามารถที่จะใช้ประโยชน์จากสมมติฐานนี้

375
00:11:55,040 --> 00:11:57,040
ดังนั้นพวกเขากำลังมากเกินไปเช่น
ตัวอย่างสมุดโทรศัพท์

376
00:11:57,040 --> 00:11:59,540
ทันทีที่คุณมีและถึงแม้จะมี
ปัญหาเล็ก ๆ เช่นนี้

377
00:11:59,540 --> 00:12:02,380
ปัจจัยการผลิตของคุณก่อนเรียงเราสามารถ
จริงหาค่าเนื้อหา

378
00:12:02,380 --> 00:12:03,130
มีประสิทธิภาพมากขึ้น

379
00:12:03,130 --> 00:12:05,800
>> และฉันไม่ได้บอกคุณว่ามันเป็น
เรียงขนาดเล็กไปจนถึงขนาดใหญ่หรือขนาดใหญ่ที่มีขนาดเล็ก

380
00:12:05,800 --> 00:12:08,080
และเพื่อให้มันเป็นที่เหมาะสมมาก
ที่จะเริ่มต้นที่ปลายด้านหนึ่งหรืออื่น ๆ

381
00:12:08,080 --> 00:12:09,750
ที่จริงการหาค่าเป้าหมายที่

382
00:12:09,750 --> 00:12:11,400
ดังนั้นขอขอบคุณเทรเวอร์ได้เป็นอย่างดี

383
00:12:11,400 --> 00:12:13,260
และฉันจะทำอย่าง propose--

384
00:12:13,260 --> 00:12:16,960
เรามีคลิปเล็ก ๆ น้อย ๆ ในความเป็นจริงว่า
เป็นหนึ่งในช่วงเวลาที่ชื่นชอบของเราใน CS50,

385
00:12:16,960 --> 00:12:19,700
โดยบางครั้งการสาธิตเหล่านี้
ค่อนข้างไม่เป็นไปตามแผน

386
00:12:19,700 --> 00:12:22,050
และแน่นอนตอนนี้ผม
ดึงขึ้นอินเตอร์เฟซที่ไม่ถูกต้อง

387
00:12:22,050 --> 00:12:23,508
ที่จะใช้หน้าจอสัมผัส

388
00:12:23,508 --> 00:12:24,660
เพื่อให้เป็นความผิดของฉันมี

389
00:12:24,660 --> 00:12:26,600
>> ดังนั้นนี่จะทำให้
คลิปของปีถัดไปเป็น

390
00:12:26,600 --> 00:12:28,570
สาเหตุที่ผมได้รับการคลิกบนหน้าจอของตัวเอง

391
00:12:28,570 --> 00:12:31,390
แต่ลองมาดูอย่างรวดเร็ว
สิ่งที่เกิดขึ้นเมื่อปีที่แล้ว

392
00:12:31,390 --> 00:12:34,770
กับเจย์ที่ขึ้นมามาก
เช่นเดียวกับเทรเวอร์ที่นี่อาสา

393
00:12:34,770 --> 00:12:39,380
และในคลิปสั้น ๆ นี้คุณจะเห็น
สาธิตวิธีการเดียวกันนี้ได้ไม่มาก

394
00:12:39,380 --> 00:12:41,074
เปิดเผยบทเรียนเดียวกันเรียนรู้

395
00:12:41,074 --> 00:12:41,740
[วิดีโอเล่นภาพ]

396
00:12:41,740 --> 00:12:45,360
ฉันต้องการให้คุณพักที่จะทำในขณะนี้คือ
เพื่อหาสิ่งที่สำหรับฉันและสำหรับเรา

397
00:12:45,360 --> 00:12:51,674
จริงๆจำนวน 50
หนึ่งขั้นในเวลา.

398
00:12:51,674 --> 00:12:52,450
>> จำนวน -The 50?

399
00:12:52,450 --> 00:12:53,190
>> จำนวน -The 50

400
00:12:53,190 --> 00:12:55,356
และคุณสามารถที่จะเปิดเผยสิ่งที่
ที่อยู่เบื้องหลังแต่ละประตูเหล่านี้

401
00:12:55,356 --> 00:12:58,540
ง่ายๆโดยการสัมผัสด้วยนิ้วมือ

402
00:12:58,540 --> 00:13:00,910
ประณามมัน

403
00:13:00,910 --> 00:13:02,870
>> [หัวเราะ]

404
00:13:02,870 --> 00:13:03,806
>> [จบเล่นภาพ]

405
00:13:03,806 --> 00:13:05,430
เดวิดเจลัน: ดังนั้นที่ไปเป็นอย่างดี

406
00:13:05,430 --> 00:13:06,796
สิ่งเหล่านี้เป็นประตูไม่ได้เรียงลำดับ

407
00:13:06,796 --> 00:13:08,670
และเจแน่นอน
พบว่ามันเร็วเกินไปทั้งหมด

408
00:13:08,670 --> 00:13:12,910
เทรเวอร์ได้งานที่ดีมาก
ในแง่ของการเป็นช่วงเวลาที่เชื่อฟัง

409
00:13:12,910 --> 00:13:15,850
เพื่อที่จะพูดในปีนี้
ใช้เวลานานที่จะหาได้

410
00:13:15,850 --> 00:13:17,950
แน่นอนแล้วเราให้
เจโอกาสครั้งที่สอง

411
00:13:17,950 --> 00:13:20,320
โดยเราเรียงประตู
เช่นเดียวกับที่เราทำสำหรับเทรเวอร์

412
00:13:20,320 --> 00:13:22,300
และเทรเวอร์ได้ดีสุดในเวลานี้

413
00:13:22,300 --> 00:13:26,124
แต่เจย์ไม่ได้ครึ่งหนึ่งได้อย่างรวดเร็ว

414
00:13:26,124 --> 00:13:26,790
[วิดีโอเล่นภาพ]

415
00:13:26,790 --> 00:13:29,650
-The เป้าหมายตอนนี้คือการยัง
พบกับเราได้ที่หมายเลข 50,

416
00:13:29,650 --> 00:13:33,030
แต่ทำมันอัลกอริทึมและ
บอกเราว่าคุณกำลังจะไปเกี่ยวกับเรื่องนี้

417
00:13:33,030 --> 00:13:33,660
>> -ตกลง.

418
00:13:33,660 --> 00:13:35,604
>> และอื่นถ้าคุณพบว่าคุณเก็บภาพยนตร์

419
00:13:35,604 --> 00:13:37,228
หากคุณพบว่ามันไม่คุณจะให้มันกลับมา

420
00:13:37,228 --> 00:13:38,044
>> -ชาย.

421
00:13:38,044 --> 00:13:38,860
>> โอ้!

422
00:13:38,860 --> 00:13:40,800
>> - [ไม่ได้ยิน] ตกลง

423
00:13:40,800 --> 00:13:46,236
ดังนั้นฉันจะไปตรวจสอบปลาย
ครั้งแรกเพื่อตรวจสอบว่า there's-- โอ้

424
00:13:46,236 --> 00:13:48,646
>> [APPLAUSE]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [จบเล่นภาพ]

427
00:13:55,729 --> 00:13:56,520
เดวิดเจลัน: OK

428
00:13:56,520 --> 00:13:59,760
ดังนั้นการเรียงลำดับประตูอย่างชัดเจน
นำไปสู่​​การมีประสิทธิภาพมากขึ้น

429
00:13:59,760 --> 00:14:01,680
และเพื่อให้สองครั้งที่รวดเร็ว
คือสิ่งที่ฉันมีความหมาย

430
00:14:01,680 --> 00:14:03,270
และเพื่อให้มีโชคดีเจทั้งสองครั้ง

431
00:14:03,270 --> 00:14:06,685
และเขายังมีโชคดีในการที่ผ่านมา
ปีที่ผมสั่งบางแผ่น Blu-ray

432
00:14:06,685 --> 00:14:07,560
ที่จริงให้ออก

433
00:14:07,560 --> 00:14:09,768
ฉันขอโทษในปีนี้เรา
ไม่ได้มีเดียวกันเทรเวอร์

434
00:14:09,768 --> 00:14:11,540
แต่ดีกว่ายังคงเป็นไม่กี่ปีหลัง

435
00:14:11,540 --> 00:14:14,820
และบางส่วนของคุณอาจจะรู้ว่านี้
เพื่อนฌอนซึ่งเมื่อเขาอยู่ใน CS50,

436
00:14:14,820 --> 00:14:17,780
กำลังถูกท้าทายด้วยแน่นอน
ปัญหาเดียวกันแม้ว่าใน SD,

437
00:14:17,780 --> 00:14:19,360
ในขณะที่คุณจะเห็นทันทีกลับในวันที่

438
00:14:19,360 --> 00:14:22,622
และคุณจะพบว่าไม่เพียง แต่
เขาใช้เวลานานกว่าเจ

439
00:14:22,622 --> 00:14:25,580
นานกว่าเทรเวอร์ก็คือ
จริงนี้โอกาสที่ยอดเยี่ยม

440
00:14:25,580 --> 00:14:29,820
จะมีส่วนร่วมเกือบทุกคนใน
ฝูงชนลาราคาที่เหมาะสมให้กำลังใจ

441
00:14:29,820 --> 00:14:31,889
เขาไปหาตัวเลขที่เรากำลังมองหา

442
00:14:31,889 --> 00:14:32,930
ลอง ใช้ดูอย่างรวดเร็ว

443
00:14:32,930 --> 00:14:33,320
>> [วิดีโอเล่นภาพ]

444
00:14:33,320 --> 00:14:33,820
>> -ตกลง.

445
00:14:33,820 --> 00:14:36,680
เพื่อให้งานของคุณที่นี่
ฌอนเป็นดังต่อไปนี้

446
00:14:36,680 --> 00:14:40,860
ฉันได้ซ่อนอยู่หลังเหล่านี้
ประตูหมายเลขเจ็ด

447
00:14:40,860 --> 00:14:45,120
แต่ซุกอยู่ในบางส่วนของประตูเหล่านี้
เช่นเดียวกับตัวเลขเชิงลบอื่น ๆ

448
00:14:45,120 --> 00:14:47,500
และเป้าหมายของคุณคือการคิด
นี้แถวบนสุดของตัวเลข

449
00:14:47,500 --> 00:14:50,390
เช่นเดียวกับอาร์เรย์หรือเพียงแค่
ลำดับของชิ้นส่วนของกระดาษ

450
00:14:50,390 --> 00:14:51,510
กับตัวเลขที่อยู่เบื้องหลังพวกเขา

451
00:14:51,510 --> 00:14:55,540
และเป้าหมายของคุณคือเพียงแค่ใช้ด้านบน
อาร์เรย์ที่นี่หาฉันจำนวนเจ็ด

452
00:14:55,540 --> 00:14:58,570
และเรามีแล้วจะวิจารณ์
วิธีการที่คุณไปเกี่ยวกับการทำมัน

453
00:14:58,570 --> 00:14:59,070
สิทธิพัก

454
00:14:59,070 --> 00:15:00,850
-Find เราหมายเลขเจ็ดโปรด

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
เลขที่

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
ห้า, 19, 13

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [หัวเราะ]

461
00:15:24,770 --> 00:15:25,910
>> มันไม่ได้เป็นคำถามเคล็ดลับ

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
หนึ่ง

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [หัวเราะ]

466
00:15:34,695 --> 00:15:37,861
ณ จุดนี้คะแนนของคุณไม่ได้มาก
ที่ดีดังนั้นคุณอาจรวมทั้งให้ไป

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
สาม

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [หัวเราะ]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> ต่อไป.

473
00:15:47,774 --> 00:15:50,690
ตรงไปตรงมาผมไม่สามารถช่วย แต่สงสัย
สิ่งที่คุณได้คิดเกี่ยวกับ so--

474
00:15:50,690 --> 00:15:51,959
>> [หัวเราะ]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
เฉพาะแถวบนสุดเพื่อ
คุณมีสามด้านซ้าย

477
00:15:55,020 --> 00:15:56,200
ดังนั้นหาฉันเจ็ด

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [หัวเราะ]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
เซเว่น

484
00:16:26,946 --> 00:16:28,780
>> [APPLAUSE]

485
00:16:28,780 --> 00:16:29,426
>> ทั้งหมดขวา

486
00:16:29,426 --> 00:16:30,360
>> [จบเล่นภาพ]

487
00:16:30,360 --> 00:16:31,840
>> เดวิดเจลัน: ดังนั้นเราจะทำได้
ดูเหล่านี้ตลอดทั้งวัน

488
00:16:31,840 --> 00:16:34,090
และแน่นอนบางส่วนของ
การสาธิตในปีนี้อาจจะ

489
00:16:34,090 --> 00:16:36,330
ตอนนี้จะจบลงในต่อไป
วิดีโอปีเช่นกัน

490
00:16:36,330 --> 00:16:39,040
ดังนั้นตอนนี้เรามาจริง
มุ่งเน้นไปที่ขั้นตอนวิธี

491
00:16:39,040 --> 00:16:42,140
ที่นี่และดูว่าเราไม่สามารถ
ตอนนี้เริ่มที่จะทำพิธี

492
00:16:42,140 --> 00:16:46,650
วิธีการที่เราสามารถไปเกี่ยวกับการรับข้อมูลของเรา
ในสภาพนี้ว่ามันเรียงลำดับ

493
00:16:46,650 --> 00:16:50,054
เพื่อที่ว่าในท้ายที่สุดที่เราสามารถทำได้จริง
ค้นหามันมีประสิทธิภาพมากขึ้น

494
00:16:50,054 --> 00:16:52,470
และแม้ว่าเราจะ
ที่จะใช้ชุดข้อมูลขนาดค่อนข้างเล็ก

495
00:16:52,470 --> 00:16:54,511
เหมือนเลขแปดเรา
มีที่นี่บนกระดาน

496
00:16:54,511 --> 00:16:58,230
ในที่สุดความคิดเดียวกันนี้สามารถนำไปใช้
ปัจจัยการผลิตถึง 1,000, ล้านปัจจัยการผลิต

497
00:16:58,230 --> 00:17:02,100
4000000000 ปัจจัยการผลิตเพราะขั้นตอนวิธี
จะไปเป็นพื้นฐานเดียวกัน

498
00:17:02,100 --> 00:17:05,359
>> และเพื่อให้เป็นครั้งสุดท้ายของเรา
เปิดโอกาสให้อาสาสมัครในวันนี้

499
00:17:05,359 --> 00:17:09,790
แต่บางทีอาจจะเป็นหนึ่งในการมีส่วนร่วมมากที่สุด
ที่เราต้องแปดอาสาสมัคร

500
00:17:09,790 --> 00:17:12,960
ที่จะเกิดขึ้นและเดินเราผ่านทาง
กระบวนการของการเรียงลำดับสิ่งที่จะเร็ว ๆ นี้

501
00:17:12,960 --> 00:17:15,212
จะอยู่ในเพลงเหล่านี้ยืนอยู่ที่นี่

502
00:17:15,212 --> 00:17:16,170
ผมขอเริ่มต้นกลับมาที่นี่

503
00:17:16,170 --> 00:17:19,692
>> ดังนั้นหนึ่งในสีเขียว turquoise-- มันคืออะไร?

504
00:17:19,692 --> 00:17:21,130
คุณกระทำ?

505
00:17:21,130 --> 00:17:21,630
สอง

506
00:17:21,630 --> 00:17:23,069
มาลง

507
00:17:23,069 --> 00:17:23,569
ตกลง.

508
00:17:23,569 --> 00:17:24,420
สาม

509
00:17:24,420 --> 00:17:25,400
สี่

510
00:17:25,400 --> 00:17:27,247
ให้ me-- ตกลงห้า

511
00:17:27,247 --> 00:17:28,830
คุณกำลังถูกเสนอชื่อโดยเพื่อนของคุณ

512
00:17:28,830 --> 00:17:31,340
หกเจ็ดแปด

513
00:17:31,340 --> 00:17:32,130
มาขึ้น

514
00:17:32,130 --> 00:17:32,630
ทั้งหมดขวา

515
00:17:32,630 --> 00:17:33,190
ขอบคุณมาก.

516
00:17:33,190 --> 00:17:33,689
มาขึ้น

517
00:17:33,689 --> 00:17:34,790
มาขึ้น

518
00:17:34,790 --> 00:17:35,330
>> ทั้งหมดขวา

519
00:17:35,330 --> 00:17:38,890
ดังนั้นสิ่งที่เรามีและ here-- นี้
เป็นหนึ่งในคนที่น่าอึดอัดใจมากขึ้น

520
00:17:38,890 --> 00:17:42,390
ตั้งแต่นี้จะกำหนดว่าคุณต้องมีอารมณ์ขัน
ฉันเพียงเล็กน้อยเวลา

521
00:17:42,390 --> 00:17:43,442
คุณจะต้องเป็นหมายเลขหนึ่ง

522
00:17:43,442 --> 00:17:44,150
คุณชื่ออะไร?

523
00:17:44,150 --> 00:17:44,610
>> อันนัน: อันนัน

524
00:17:44,610 --> 00:17:45,526
>> เดวิดเจลัน: อันนัน

525
00:17:45,526 --> 00:17:46,092
เดวิด

526
00:17:46,092 --> 00:17:46,800
คุณชื่ออะไร?

527
00:17:46,800 --> 00:17:47,140
>> JOSEPH: โจเซฟ

528
00:17:47,140 --> 00:17:49,190
>> เดวิดเจลัน: โจเซฟ
คุณเป็นอันดับสอง

529
00:17:49,190 --> 00:17:52,260
>> SERENA: เซเรน่าเลขที่สาม

530
00:17:52,260 --> 00:17:53,722
สเตฟาน, บ้านเลขที่สี่

531
00:17:53,722 --> 00:17:54,430
CYNTHIA: ซินเทีย

532
00:17:54,430 --> 00:17:57,548
เดวิดเจลัน: ซินเทียหมายเลขห้า

533
00:17:57,548 --> 00:17:58,452
[ไม่ได้ยิน]

534
00:17:58,452 --> 00:17:59,618
เดวิดเจลัน: [ไม่ได้ยิน]

535
00:17:59,618 --> 00:18:00,391
เดวิดเลขหก

536
00:18:00,391 --> 00:18:00,890
MATT: แมตต์

537
00:18:00,890 --> 00:18:02,160
เดวิดเจลัน: หมายเลขเจ็ดของแมตต์

538
00:18:02,160 --> 00:18:02,850
และ?

539
00:18:02,850 --> 00:18:03,210
>> WAVERLY: เวเวอร์ลีย์

540
00:18:03,210 --> 00:18:04,470
>> เดวิดเจลัน: Waverly จำนวนแปด

541
00:18:04,470 --> 00:18:04,970
ทั้งหมดขวา

542
00:18:04,970 --> 00:18:06,510
หากคุณ could-- ขออภัย

543
00:18:06,510 --> 00:18:08,820
หากคุณทั้งหมดเป็นของคุณ
ความท้าทายแรกมี

544
00:18:08,820 --> 00:18:10,820
แปดเพลงยืน
ที่นี่หันหน้าไปทางผู้ชม

545
00:18:10,820 --> 00:18:14,200
หากคุณสามารถใส่หมายเลขของคุณบน
เพลงเหล่านี้ยืนอยู่ในลักษณะ

546
00:18:14,200 --> 00:18:16,560
ว่าพวกเขาบรรทัดขึ้นกับ
ตัวเลขเดียวกันบนกระดาน

547
00:18:16,560 --> 00:18:19,560
เพื่อให้ตัวเองมีลักษณะเหมือนว่าด้วยการ
ใส่หมายเลขของคุณเกี่ยวกับดนตรีเหล่านี้

548
00:18:19,560 --> 00:18:21,960
ยืนอยู่ที่นี่

549
00:18:21,960 --> 00:18:25,980
ที่ดีเยี่ยมเพื่อให้ห่างไกล

550
00:18:25,980 --> 00:18:26,600
>> ที่ดีเยี่ยม

551
00:18:26,600 --> 00:18:26,890
ตกลง.

552
00:18:26,890 --> 00:18:29,556
ดังนั้นตอนนี้เรากำลังจะถาม
คำถามที่แตกต่างกันไม่กี่

553
00:18:29,556 --> 00:18:31,610
วิธีที่เราสามารถไปเกี่ยวกับการเรียงลำดับ
คนเหล่านี้ขึ้นที่นี่?

554
00:18:31,610 --> 00:18:34,500
เพราะเรามีวิธีการไม่กี่
ก่อนหน้านี้โดยที่เราอยู่

555
00:18:34,500 --> 00:18:36,360
ชนิดของการทำสองถังที่แตกต่างกัน

556
00:18:36,360 --> 00:18:38,842
แล้วเราโดยทั่วไป
piecing สิ่งร่วมกัน

557
00:18:38,842 --> 00:18:41,050
ทันทีที่เราเห็นตัวเลขสอง
ที่เป็นกัน

558
00:18:41,050 --> 00:18:41,975
เราเอามารวมกัน

559
00:18:41,975 --> 00:18:43,350
ตัวอักษรสองตัวที่อยู่ร่วมกัน

560
00:18:43,350 --> 00:18:45,058
>> แต่ขอดูว่าเรา
ไม่สามารถทำพิธีนี้

561
00:18:45,058 --> 00:18:48,044
เพื่อให้เราได้ในท้ายที่สุด
บางหลอกรหัสที่คุณจะ

562
00:18:48,044 --> 00:18:49,710
ที่คุณสามารถแก้ปัญหาเหล​​่านี้

563
00:18:49,710 --> 00:18:51,870
ดังนั้นตอนนี้ผมมองออกไป
ตัวเลขเหล่านี้ที่นี่

564
00:18:51,870 --> 00:18:55,030
และฉันเห็นทั้งกลุ่มของความผิดพลาด

565
00:18:55,030 --> 00:18:57,750
ในที่สุดฉันต้องการหนึ่งใน
ซ้ายและแปดด้านขวา

566
00:18:57,750 --> 00:19:00,650
>> และฉันจึงมองหาที่
ทั้งสองสี่และสอง

567
00:19:00,650 --> 00:19:02,930
และสิ่งที่เป็นปัญหาที่เห็นได้ชัด?

568
00:19:02,930 --> 00:19:04,261
ใช่

569
00:19:04,261 --> 00:19:04,760
ดังนั้น

570
00:19:04,760 --> 00:19:07,160
สองอย่างเห็นได้ชัดมาก่อน
สี่เพื่อให้คุณรู้อะไรไหม

571
00:19:07,160 --> 00:19:10,210
ครั้งแรกที่ผมขอใช้วิธีโลภ
ถ้าคุณจะมีปัญหามากเช่น

572
00:19:10,210 --> 00:19:13,790
ตั้ง one-- ถ้าคุณจำได้จาก
Standard Edition ปัญหาชุดหนึ่ง

573
00:19:13,790 --> 00:19:16,820
ที่ฉันเพียงแค่ในประเทศแก้ปัญหา
ว่าที่นี่ในด้านหน้าของฉัน

574
00:19:16,820 --> 00:19:17,690
และดูว่ามันจะทำให้ผม

575
00:19:17,690 --> 00:19:17,870
>> ตกลง.

576
00:19:17,870 --> 00:19:20,161
ดังนั้นสองและสี่ให้ฉันไป
ไปข้างหน้าและเพียงแค่สลับคุณทั้งสอง

577
00:19:20,161 --> 00:19:22,400
หากคุณสามารถย้ายร่างกาย
ตัวเองและกระดาษของคุณ

578
00:19:22,400 --> 00:19:25,040
ฉันดูเหมือนจะมีอากาศ
รายการอยู่ในสถานะที่ดีกว่า

579
00:19:25,040 --> 00:19:26,330
>> ตอนนี้พวกเขากำลังดี

580
00:19:26,330 --> 00:19:28,480
ฉันจะย้ายไป
สี่หกและดูดี

581
00:19:28,480 --> 00:19:29,110
ไม่ใช่ปัญหา.

582
00:19:29,110 --> 00:19:30,440
หกสิบแปด, OK

583
00:19:30,440 --> 00:19:31,860
แปดและเป็นหนึ่งในปัญหาที่เกิดขึ้นอีก

584
00:19:31,860 --> 00:19:34,750
เพราะสิ่งที่เป็นความจริงประมาณแปดและเป็นหนึ่ง?

585
00:19:34,750 --> 00:19:36,990
ใครมาก่อนแปด
และเพื่อให้สิ่งที่เราควรทำอย่างไร?

586
00:19:36,990 --> 00:19:38,090
ลองสลับทั้งสอง

587
00:19:38,090 --> 00:19:39,316
หนึ่งแปด

588
00:19:39,316 --> 00:19:40,690
และตอนนี้ฉันจะเก็บไป

589
00:19:40,690 --> 00:19:42,030
ฉันจะให้มองไปข้างหน้า

590
00:19:42,030 --> 00:19:42,840
และเรามาดูสิ่งที่เกิดขึ้น

591
00:19:42,840 --> 00:19:44,680
แปดและสามของ
แน่นอนว่าการออกคำสั่ง

592
00:19:44,680 --> 00:19:45,815
แลกเปลี่ยน Let 's

593
00:19:45,815 --> 00:19:46,940
แปดเจ็ดของหลักสูตร

594
00:19:46,940 --> 00:19:47,481
ชำรุด.

595
00:19:47,481 --> 00:19:48,280
แลกเปลี่ยน Let 's

596
00:19:48,280 --> 00:19:49,940
แปดห้าของหลักสูตรให้แลกเปลี่ยนของ

597
00:19:49,940 --> 00:19:50,560
ทั้งหมดขวา

598
00:19:50,560 --> 00:19:51,880
รายชื่อเรียง

599
00:19:51,880 --> 00:19:53,060
ใช่?

600
00:19:53,060 --> 00:19:54,280
>> ตกลงไม่ชัด

601
00:19:54,280 --> 00:19:55,860
แต่มันก็เป็นเพียงเล็กน้อยดีกว่าใช่มั้ย?

602
00:19:55,860 --> 00:19:57,270
เพราะสิ่งที่เกิดขึ้นแจ้งให้ทราบล่วงหน้า

603
00:19:57,270 --> 00:20:01,749
ทุกครั้งที่เราดำเนินการแลกเปลี่ยนที่มีขนาดเล็ก
จำนวนชนิดของการกระจายวิธีการที่

604
00:20:01,749 --> 00:20:03,790
และจำนวนที่ใหญ่กว่า
กระจายด้วยวิธีนี้หรือเราจะ

605
00:20:03,790 --> 00:20:06,880
เริ่มต้นพูดกับฟอง
ไปทางซ้ายหรือฟองไปทางขวา

606
00:20:06,880 --> 00:20:10,080
>> ตอนนี้ก็ยังไม่พอเพราะ
ที่ดีที่สุดอาจจะเป็นจำนวนมาก

607
00:20:10,080 --> 00:20:11,990
ได้ย้ายจุดหนึ่ง
ไปข้างหน้าหรือที่เลวร้ายที่สุด

608
00:20:11,990 --> 00:20:13,880
จำนวนอาจจะมี
ย้ายจุดหนึ่งต่อไป

609
00:20:13,880 --> 00:20:16,369
เพื่อให้คุณรู้ว่าสิ่งที่ประเภทนี้
การทำงานสวยดีเพื่อให้ห่างไกล

610
00:20:16,369 --> 00:20:17,410
ผมขอลองอีกครั้ง

611
00:20:17,410 --> 00:20:18,880
สองและสี่พวกเขากำลังตกลง

612
00:20:18,880 --> 00:20:20,180
สี่หกและพวกเขากำลังตกลง

613
00:20:20,180 --> 00:20:21,790
และเป็นหนึ่งในหก, ออกคำสั่ง

614
00:20:21,790 --> 00:20:23,007
ดังนั้นขอให้คุณทั้งสองสลับ

615
00:20:23,007 --> 00:20:25,840
และตอนนี้สังเกตเห็นปัญหาของ
เริ่มต้นที่จะได้รับดีขึ้นเล็กน้อยอีกครั้ง

616
00:20:25,840 --> 00:20:27,006
หกและสามออกคำสั่ง

617
00:20:27,006 --> 00:20:28,100
ลองสลับคุณทั้งสอง

618
00:20:28,100 --> 00:20:29,730
หกเจ็ดและคุณจะดี

619
00:20:29,730 --> 00:20:32,230
เซเว่นและห้าของหลักสูตรที่ออกคำสั่ง

620
00:20:32,230 --> 00:20:33,920
เจ็ดแปดในการสั่งซื้อ

621
00:20:33,920 --> 00:20:36,470
และตอนนี้ผมอาจจะต้อง
ทำเช่นนี้ไม่กี่ครั้ง

622
00:20:36,470 --> 00:20:39,830
และในความเป็นจริงคิดว่าสำหรับตัวเอง
บางทีอาจจะเป็นวิธีการที่หลายต่อหลายครั้งที่สุด

623
00:20:39,830 --> 00:20:41,330
ผมอาจจะต้องเดินกลับมา?

624
00:20:41,330 --> 00:20:42,390
>> เราจะกลับมาที่

625
00:20:42,390 --> 00:20:43,700
ดังนั้นสองและสี่ยังคงตกลง

626
00:20:43,700 --> 00:20:44,940
สี่และหนึ่งอ้าง

627
00:20:44,940 --> 00:20:45,747
ดังนั้นขอแลกเปลี่ยนของ

628
00:20:45,747 --> 00:20:47,830
และอีกครั้งสังเกตเห็นสายตา
หนึ่งเป็นชนิดของเดือด

629
00:20:47,830 --> 00:20:49,163
ไปทางซ้ายที่มันควรจะเป็น

630
00:20:49,163 --> 00:20:50,010
สี่สามแลกเปลี่ยน

631
00:20:50,010 --> 00:20:51,330
สี่หก

632
00:20:51,330 --> 00:20:53,100
และห้าหกแลกเปลี่ยน

633
00:20:53,100 --> 00:20:53,959
หกเจ็ด

634
00:20:53,959 --> 00:20:55,000
เจ็ดแปดเป็นสิ่งที่ดี

635
00:20:55,000 --> 00:20:55,500
>> ดี

636
00:20:55,500 --> 00:20:58,460
เราได้รับที่ดียิ่งขึ้น

637
00:20:58,460 --> 00:20:59,130
ดังนั้นเรามาดู

638
00:20:59,130 --> 00:21:00,940
ตอนนี้เรามีสองและเป็นหนึ่งใน

639
00:21:00,940 --> 00:21:02,520
แน่นอนแลกเปลี่ยน

640
00:21:02,520 --> 00:21:07,520
สองและสามสามและสี่สี่
ห้าหกเจ็ดเจ็ดแปด

641
00:21:07,520 --> 00:21:08,020
ดี

642
00:21:08,020 --> 00:21:08,730
และคุณรู้ว่าสิ่งที่?

643
00:21:08,730 --> 00:21:11,190
เพราะผมทำอย่างใดอย่างหนึ่งการเปลี่ยนแปลงที่นั่น
ให้ฉันทำอย่างใดอย่างหนึ่งการตรวจสอบสุขภาพจิตดี

644
00:21:11,190 --> 00:21:13,023
ให้ฉันไปตลอดทาง
กลับไปที่จุดเริ่มต้น

645
00:21:13,023 --> 00:21:13,680
ตกลง.

646
00:21:13,680 --> 00:21:14,750
หนึ่ง two-- ยุบเห็น?

647
00:21:14,750 --> 00:21:15,870
บางอย่างผิดปกติ

648
00:21:15,870 --> 00:21:18,420
สามสี่ห้าหกเจ็ดแปด

649
00:21:18,420 --> 00:21:21,920
และในการส่งผ่านที่ผ่านมานี้มี
คุณสะดวกสบายกับฉันตอนนี้

650
00:21:21,920 --> 00:21:23,830
อ้างว่ามันจะถูกจัดเรียง?

651
00:21:23,830 --> 00:21:24,330
ตกลง.

652
00:21:24,330 --> 00:21:25,880
มองเห็นว่าเป็นความจริงอย่างแน่นอน

653
00:21:25,880 --> 00:21:28,410
แต่หน้าที่อะไร
ไม่เพียงเกิดขึ้น

654
00:21:28,410 --> 00:21:31,870
ในผู้ที่ผ่านไปผ่านมาที่ช่วยให้คุณ
เพื่อยืนยันว่ารายการนี​​้เป็นที่แน่นอน

655
00:21:31,870 --> 00:21:32,660
เรียง?

656
00:21:32,660 --> 00:21:34,477
>> ผมทำอะไรหรือไม่ทำผ่านที่ผ่านมานี้หรือไม่?

657
00:21:34,477 --> 00:21:35,810
ผู้ชม: ไม่มีการเปลี่ยนแปลงได้

658
00:21:35,810 --> 00:21:36,120
เดวิดเจลัน: ขออภัย?

659
00:21:36,120 --> 00:21:37,070
ผู้ชม: ไม่มีการเปลี่ยนแปลง

660
00:21:37,070 --> 00:21:38,653
เดวิดเจลัน: ไม่มีการเปลี่ยนแปลงได้

661
00:21:38,653 --> 00:21:41,947
ดังนั้นมันจะโง่ของฉันไป
ทำขั้นตอนวิธีการเดียวกับที่อีกครั้ง

662
00:21:41,947 --> 00:21:43,780
ถ้าฉันไม่ได้ทำการใด ๆ
การเปลี่ยนแปลงครั้งแรก

663
00:21:43,780 --> 00:21:45,160
และรัฐไม่ได้เปลี่ยนแปลง

664
00:21:45,160 --> 00:21:47,576
แน่นอนผมไม่ได้จะทำให้
การเปลี่ยนแปลงใด ๆ ที่เป็นครั้งที่สอง

665
00:21:47,576 --> 00:21:49,820
และเพื่อให้มันปลอดภัยในขณะนี้
ที่จะบอกว่าจะเรียงลำดับรายการ

666
00:21:49,820 --> 00:21:52,069
>> และแน่นอนตอนนี้
สิ่งที่เราจะโดยทั่วไป

667
00:21:52,069 --> 00:21:56,900
การจัดเรียงฟองโทรโดยคู่,
คุณแก้ไขข้อผิดพลาดอีกครั้ง

668
00:21:56,900 --> 00:22:00,210
และอีกครั้งและอีกครั้งและคุณ
ให้ไปกลับมา

669
00:22:00,210 --> 00:22:03,370
และกลับมาจนกว่าคุณจะ
ทำให้ไม่มีการแลกเปลี่ยนดังกล่าวที่จุด

670
00:22:03,370 --> 00:22:07,089
คุณสามารถมั่นใจได้ใช่ฉัน
เสร็จสิ้นทั้งหมดของการแก้ไขความผิดพลาด

671
00:22:07,089 --> 00:22:08,630
ลองตั้งค่าและลองใช้วิธีอื่น

672
00:22:08,630 --> 00:22:11,590
ถ้าพวกคุณจะกลับไปสู่
เพื่อที่คุณเป็นช่วงเวลาที่ผ่านมา

673
00:22:11,590 --> 00:22:13,780
ซึ่งมองเช่นนี้

674
00:22:13,780 --> 00:22:17,640
ตอนนี้ขอใช้วิธีการหนึ่ง
เล็ก ๆ น้อย ๆ เช่นเดียวกับหนังสือสอบ

675
00:22:17,640 --> 00:22:21,122
โดยที่เรามีอย่างต่อเนื่อง
เลือกตัวอักษรที่

676
00:22:21,122 --> 00:22:22,830
ที่เราต้องการชนิดของ
ที่จะจัดการกับต่อไป

677
00:22:22,830 --> 00:22:26,420
บางทีมันอาจจะเป็นตัวอักษรสูง
เช่น A, หรือตัวอักษรที่ต่ำซี

678
00:22:26,420 --> 00:22:28,170
>> เพื่อให้ทุกคนกลับมาในลำดับนี้

679
00:22:28,170 --> 00:22:29,800
และตอนนี้ให้ฉันทำเช่นนี้

680
00:22:29,800 --> 00:22:34,880
ลองมาดูฉันรู้ว่าฉันมี
เลขแปดที่นี่

681
00:22:34,880 --> 00:22:37,410
ฉันจะไปข้างหน้าและ
เพียงแค่จงใจเลือก

682
00:22:37,410 --> 00:22:38,520
องค์ประกอบที่มีขนาดเล็กที่สุด

683
00:22:38,520 --> 00:22:38,760
ใช่มั้ย?

684
00:22:38,760 --> 00:22:39,801
นี้ดูเหมือนง่ายเกินไป

685
00:22:39,801 --> 00:22:42,560
ทำไมฉันจึงไม่พบว่ามีขนาดเล็กที่สุด
องค์ประกอบที่ใส่ไว้ที่มันอยู่,

686
00:22:42,560 --> 00:22:45,280
จากนั้นได้รับองค์ประกอบที่เล็กที่สุดต่อไปใส่
ว่าที่มันเป็นและเพียงแค่การทำซ้ำ

687
00:22:45,280 --> 00:22:46,820
>> เพราะสังหรณ์ใจ
ที่ควรจะทำงานมากเกินไป

688
00:22:46,820 --> 00:22:48,441
ดังนั้นสี่ที่เป็นตัวเลขขนาดเล็กสวย

689
00:22:48,441 --> 00:22:49,940
ฉันจะจำที่นี้

690
00:22:49,940 --> 00:22:50,523
ประเดี๋ยวก่อน

691
00:22:50,523 --> 00:22:51,577
สองมีขนาดเล็ก

692
00:22:51,577 --> 00:22:53,910
ตอนนี้ผมขอจำที่สอง
เป็นและลืมเกี่ยวกับสี่

693
00:22:53,910 --> 00:22:55,050
เราจะจัดการกับในภายหลังว่า

694
00:22:55,050 --> 00:22:56,460
หกฉันไม่สนใจ

695
00:22:56,460 --> 00:22:57,810
แปดผมไม่ได้สนใจใน

696
00:22:57,810 --> 00:22:59,780
หนึ่งคือจำนวนน้อยใหม่ของฉัน

697
00:22:59,780 --> 00:23:01,470
ดังนั้นฉันจะจำที่หนึ่ง

698
00:23:01,470 --> 00:23:02,534
สามไม่สนใจ

699
00:23:02,534 --> 00:23:03,450
เซเว่น, ไม่ได้สนใจ

700
00:23:03,450 --> 00:23:04,530
ห้าไม่ได้สนใจ

701
00:23:04,530 --> 00:23:07,390
>> ดังนั้นโดยไม่ล้ม
เวทีปีนี้

702
00:23:07,390 --> 00:23:09,890
ฉันจะคว้าจำนวน one--
และสิ่งที่เป็นชื่อของคุณอีกครั้ง

703
00:23:09,890 --> 00:23:10,150
>> อันนัน: อันนัน

704
00:23:10,150 --> 00:23:11,220
>> เดวิดเจลัน: อันนัน

705
00:23:11,220 --> 00:23:13,540
และถ้าคุณสามารถเข้าร่วมเราได้ที่
จุดเริ่มต้นของรายการ

706
00:23:13,540 --> 00:23:14,870
ขอนำคุณที่คุณอยู่

707
00:23:14,870 --> 00:23:16,080
Unfortunately-- คุณชื่ออะไร?

708
00:23:16,080 --> 00:23:16,650
>> STEFAN: สเตฟาน

709
00:23:16,650 --> 00:23:18,191
>> เดวิดเจลัน: สเตฟานเป็นในทาง

710
00:23:18,191 --> 00:23:23,490
ดังนั้นก่อนที่สเตฟานแก้นี้
ปัญหาสิ่งที่เราควรทำอย่างไร?

711
00:23:23,490 --> 00:23:25,412
เราจะทำอย่างไรกับสเตฟาน?

712
00:23:25,412 --> 00:23:27,269
>> ผู้ชม: [ไม่ได้ยิน]

713
00:23:27,269 --> 00:23:28,060
เดวิดเจลัน: OK

714
00:23:28,060 --> 00:23:28,850
ดังนั้นเราจึงสามารถดำเนินการได้

715
00:23:28,850 --> 00:23:31,730
การเรียงลำดับของเราอาจจะใช้เวลาของเขาและสเตฟาน
สี่และเพียงวางไว้ในตัวแปร

716
00:23:31,730 --> 00:23:33,530
และยึดมั่นในมัน
ปริมาณของบางเวลา

717
00:23:33,530 --> 00:23:35,220
จึงทำให้ห้องพักสำหรับจำนวนหนึ่ง

718
00:23:35,220 --> 00:23:36,280
และที่ไม่ได้เลวร้าย

719
00:23:36,280 --> 00:23:39,270
ฉันจะแนะนำทำไมไม่ได้
เราเพียงแค่ใส่สเตฟานนี่?

720
00:23:39,270 --> 00:23:41,610
ทำไมนี้อาจละเมิดหนึ่ง
ความคิดที่เราเริ่มต้น

721
00:23:41,610 --> 00:23:44,830
พูดคุยเกี่ยวกับเวลาที่ผ่านมาสัปดาห์ที่ผ่านมา?

722
00:23:44,830 --> 00:23:45,330
ใช่?

723
00:23:45,330 --> 00:23:45,740
>> ผู้ชม: [ไม่ได้ยิน]

724
00:23:45,740 --> 00:23:46,860
>> เดวิดเจลัน: มีดัชนีมันไม่มี

725
00:23:46,860 --> 00:23:49,735
ถ้าคุณคิดว่านี้แท้จริงเป็น
อาร์เรย์นี้เป็นเหมือนหนึ่งในเชิงลบ

726
00:23:49,735 --> 00:23:52,900
เพื่อให้มีหน่วยความจำที่ไม่มีจริง
นี่ถ้านี่เป็นอาร์เรย์

727
00:23:52,900 --> 00:23:55,090
เหมือนอย่างที่เราประกาศเมื่อสัปดาห์ที่แล้วในการบรรยาย

728
00:23:55,090 --> 00:23:56,250
ดังนั้นเราจึงไม่ควรทำเช่นนี้

729
00:23:56,250 --> 00:23:57,340
เราอาจจะเก็บไว้ในตัวแปร

730
00:23:57,340 --> 00:23:57,820
>> หรือคุณรู้อะไรไหม

731
00:23:57,820 --> 00:23:59,153
ผมได้ยินคนอื่นบอกว่ามัน

732
00:23:59,153 --> 00:24:01,020
อะไรที่เราจะทำกับสเตฟาน?

733
00:24:01,020 --> 00:24:03,770
ทำไมเราไม่เพียงเขาและขับไล่
ทำให้เขามากกว่าที่เป็นหมายเลขหนึ่ง

734
00:24:03,770 --> 00:24:05,170
ดังนั้นหากคุณต้องการที่จะไปที่นั่น

735
00:24:05,170 --> 00:24:07,300
และแน่นอนนี่คือ
วิธีการแก้ปัญหาที่ดีงาม

736
00:24:07,300 --> 00:24:10,480
ตอนนี้ในมือข้างหนึ่งผมชนิด
การทำให้ปัญหาแย่ลง

737
00:24:10,480 --> 00:24:13,650
สี่คือตอนนี้ห่างไกลออกไป
จากที่ที่มันควรจะเป็น

738
00:24:13,650 --> 00:24:14,900
มันควรจะเป็นต่อครึ่งนี้

739
00:24:14,900 --> 00:24:16,100
>> แต่คุณรู้อะไรไหม

740
00:24:16,100 --> 00:24:17,630
ที่จะได้รับโชคร้าย

741
00:24:17,630 --> 00:24:18,822
บางทีจำนวนแปดอยู่ที่นี่

742
00:24:18,822 --> 00:24:20,530
ดังนั้นบางทีเราจะ
มีอากาศที่โชคดี

743
00:24:20,530 --> 00:24:22,460
และผลักดันแปดใกล้ชิดกับปลาย

744
00:24:22,460 --> 00:24:24,710
ดังนั้นในตอนท้ายของวัน
ชนิดของค่าเฉลี่ยออกทั้งหมด

745
00:24:24,710 --> 00:24:26,085
เราไม่จำเป็นต้องดูแลเกี่ยวกับสี่

746
00:24:26,085 --> 00:24:29,400
ทั้งหมดที่ฉันดูแลเกี่ยวกับตอนนี้คือ
การเลือกองค์ประกอบที่เล็กที่สุด

747
00:24:29,400 --> 00:24:32,030
>> และตอนนี้สิ่งที่ผมกำลังจะไป
ทำคือลืมเกี่ยวกับหมายเลขหนึ่ง

748
00:24:32,030 --> 00:24:35,160
อย่างถาวรเพราะฉันรู้ว่า
รายการอยู่ข้างหลังผมจะถูกจัดเรียงในขณะนี้

749
00:24:35,160 --> 00:24:36,720
ดังนั้นรายชื่อของฉันคือขนาดแปดก่อนหน้านี้

750
00:24:36,720 --> 00:24:37,720
ตอนนี้ก็มีขนาดเจ็ด

751
00:24:37,720 --> 00:24:40,340
ดังนั้นปัญหาของฉันจะได้รับ
ที่มีขนาดเล็กแม้จะเป็นเส้นตรง

752
00:24:40,340 --> 00:24:43,022
ดังนั้นตอนนี้ฉันจะเลือก
ปัจจุบันอง​​ค์ประกอบที่เล็กที่สุดสอง

753
00:24:43,022 --> 00:24:46,520
หกแปดสี่สามเจ็ดห้า

754
00:24:46,520 --> 00:24:47,770
นั่นคือองค์ประกอบที่เล็กที่สุด

755
00:24:47,770 --> 00:24:49,416
ดังนั้นสิ่งที่ฉันจะทำ with--
สิ่งที่เป็นชื่อของคุณอีกครั้งหรือไม่

756
00:24:49,416 --> 00:24:49,760
>> JOSEPH: โจเซฟ

757
00:24:49,760 --> 00:24:50,085
>> เดวิดเจลัน: โจเซฟ?

758
00:24:50,085 --> 00:24:52,000
เรากำลังจะออกจากโจเซฟในสถานที่

759
00:24:52,000 --> 00:24:54,842
ตอนนี้ผมกำลังจะไปหลอก
ว่าคนเหล่านี้ are-- ดี

760
00:24:54,842 --> 00:24:56,550
ฉันรู้ว่าสองคนนี้
จะถูกจัดเรียงอยู่แล้ว

761
00:24:56,550 --> 00:24:58,424
ตอนนี้ขอมุ่งเน้นไปที่
ส่วนที่เหลือของรายการ

762
00:24:58,424 --> 00:25:00,080
หกเป็นที่เล็กที่สุดในปัจจุบัน

763
00:25:00,080 --> 00:25:01,190
แปดมีขนาดใหญ่

764
00:25:01,190 --> 00:25:02,970
สี่คือตอนนี้มีขนาดเล็กที่สุดในปัจจุบัน

765
00:25:02,970 --> 00:25:04,762
สามคือตอนนี้มีขนาดเล็กที่สุดในปัจจุบัน

766
00:25:04,762 --> 00:25:07,720
ดังนั้นตอนนี้ผมกำลังจะไปเลือกที่สาม
ที่ is-- สิ่งที่ชื่อของคุณอีกครั้งหรือไม่

767
00:25:07,720 --> 00:25:08,190
SERENA: เซเรน่า

768
00:25:08,190 --> 00:25:10,620
เดวิดเจลัน: เซเรน่าหากคุณสามารถ
คว้าหมายเลขของคุณและแลกเปลี่ยน with--

769
00:25:10,620 --> 00:25:11,550
Kalsang: Kalsang

770
00:25:11,550 --> 00:25:12,940
เดวิดเจลัน: Kalsang

771
00:25:12,940 --> 00:25:15,220
มาที่ด้านหลังและเรา
จะสลับทั้งสอง

772
00:25:15,220 --> 00:25:17,360
และตอนนี้เรามาใส่นี้ในหม้อแปลงไฟฟ้​​า

773
00:25:17,360 --> 00:25:21,589
ฉันจะไปและปล่อยให้พวกคุณ
เพื่อเลือกองค์ประกอบที่เล็กที่สุดต่อไป

774
00:25:21,589 --> 00:25:22,380
ตาลตาลตาลตาล

775
00:25:22,380 --> 00:25:24,560
จำนวนสี่สิ่งที่คุณควรทำอย่างไร?

776
00:25:24,560 --> 00:25:26,261
ที่ดีเยี่ยม

777
00:25:26,261 --> 00:25:27,760
ตอนนี้ฉันจะทำให้ผ่านอื่น

778
00:25:27,760 --> 00:25:28,590
ตาลตาลตาลตาล

779
00:25:28,590 --> 00:25:31,465
ฉันเห็นห้าเป็นต่อไปที่เล็กที่สุด

780
00:25:31,465 --> 00:25:32,840
ตอนนี้ฉันจะใช้เวลาผ่านอีก

781
00:25:32,840 --> 00:25:33,631
ตาลตาลตาลตาล

782
00:25:33,631 --> 00:25:34,880
หกเป็นที่เล็กที่สุด

783
00:25:34,880 --> 00:25:35,520
ดี

784
00:25:35,520 --> 00:25:36,585
เซเว่นเป็นที่เล็กที่สุด

785
00:25:36,585 --> 00:25:37,085
ไม่มีการเปลี่ยนแปลง.

786
00:25:37,085 --> 00:25:38,630
แปดเป็นที่เล็กที่สุด

787
00:25:38,630 --> 00:25:39,170
เสร็จสิ้น

788
00:25:39,170 --> 00:25:43,900
>> ดังนั้นสิ่งที่เราได้ทำเพียงแค่ซ้ำ
การเลือกองค์ประกอบหนึ่งหลังจากที่อื่น

789
00:25:43,900 --> 00:25:47,230
มีการดำเนินการอะไรบางอย่างที่เรา
จะเป็นจัดเรียงเป็นระเบียบแบบแผนเลือก

790
00:25:47,230 --> 00:25:49,120
และก็อาจจะรวมถึง
ง่ายที่จะอธิบาย

791
00:25:49,120 --> 00:25:51,310
ในการที่แท้จริงทั้งหมดที่คุณ
ต้องการจะทำคือเพียงแค่ให้

792
00:25:51,310 --> 00:25:54,700
จะกลับมาผ่านรายการ
การเลือกองค์ประกอบที่เล็กที่สุดต่อไป

793
00:25:54,700 --> 00:25:55,720
จนกว่าคุณจะทำ

794
00:25:55,720 --> 00:25:58,650
>> ดังนั้นจึงเป็นได้ง่ายอาจ
สังหรณ์ใจกว่าที่ผ่านมา

795
00:25:58,650 --> 00:26:00,020
ลองคนสุดท้ายหนึ่ง

796
00:26:00,020 --> 00:26:03,060
ถ้าพวกคุณสามารถตั้งค่าตัวเอง
ในตำแหน่งดังต่อไปนี้

797
00:26:03,060 --> 00:26:08,600
เป็นครั้งสุดท้ายให้ดูว่าเราไม่สามารถ
ขณะนี้เป็นระเบียบแบบแผนวิธีการหนึ่งอื่น ๆ

798
00:26:08,600 --> 00:26:12,857
ในความเป็นจริงจะมีใครบางคน
ออกมีชอบที่จะนำเสนอ

799
00:26:12,857 --> 00:26:14,440
วิธีอื่นที่เราอาจจะไปเกี่ยวกับการทำเช่นนี้?

800
00:26:14,440 --> 00:26:17,439
โดยไม่ต้องโยนออก buzzwords หรือประเภท
คำตอบที่เป็นที่รู้จักอยู่แล้ว

801
00:26:17,439 --> 00:26:19,689
เพียงแค่สังหรณ์ใจว่าเราจะทำอย่างไร

802
00:26:19,689 --> 00:26:21,635
>> ผู้ชม: [ไม่ได้ยิน]

803
00:26:21,635 --> 00:26:22,510
เดวิดเจลัน: ใช่

804
00:26:22,510 --> 00:26:24,620
จึงมีบางอย่างที่ดีมีสัญชาตญาณ

805
00:26:24,620 --> 00:26:28,020
สิ่งที่ดีดูเหมือนจะเกิดขึ้นป่านนี้
วิทยาการคอมพิวเตอร์เมื่อเราแบ่ง

806
00:26:28,020 --> 00:26:30,832
และพิชิตปัญหาของการหาร
ในช่วงครึ่งปีและครึ่งหนึ่งและอีกครึ่งหนึ่ง

807
00:26:30,832 --> 00:26:32,540
และอื่น ๆ แน่นอนเรา
สามารถเริ่มต้นที่จะทำ

808
00:26:32,540 --> 00:26:35,754
และในความเป็นจริงที่เป็นไปได้ที่เราจะ
เห็นหนึ่งในโซลูชั่นที่ดีที่สุดของเรายัง

809
00:26:35,754 --> 00:26:37,420
แต่ขอกลับมาว่าอีกไม่นาน

810
00:26:37,420 --> 00:26:40,500
ในความเป็นจริงที่เรากำลังจะทำ
ที่เล็ก ๆ น้อย ๆ ต่อมาในสัปดาห์นี้

811
00:26:40,500 --> 00:26:42,180
อะไรที่เราอาจจะทำเพื่อแก้ปัญหานี้?

812
00:26:42,180 --> 00:26:44,647
ทุกคนดังนั้นนี่คือใน
เพื่อสุ่ม

813
00:26:44,647 --> 00:26:45,230
คุณรู้อะไรไหม?

814
00:26:45,230 --> 00:26:48,320
แทนที่จะกลับมา
กลับมากลับมา

815
00:26:48,320 --> 00:26:50,624
แต่ละครั้งนี้รู้สึกเหมือน
ฉันทำมากของการเดิน

816
00:26:50,624 --> 00:26:52,790
ทำไมฉันจึงไม่เพียงแค่เริ่มต้นที่
จุดเริ่มต้นของรายการ

817
00:26:52,790 --> 00:26:54,960
และเพียงแค่ใส่สี่ที่มันอยู่?

818
00:26:54,960 --> 00:26:59,680
เพื่อให้ฉันถือว่าสำหรับช่วงเวลาที่
รายการของฉันเพียงแค่นี้องค์ประกอบแรก

819
00:26:59,680 --> 00:27:04,937
มีการเรียงสี่ในขณะนี้ในเวลา,
ถ้าสิ่งที่ผมสนใจคือทุกอย่างที่นี่?

820
00:27:04,937 --> 00:27:06,520
นี่คือการจัดเรียงของจริงนิด ๆ ใช่มั้ย?

821
00:27:06,520 --> 00:27:10,000
เช่นเดียวกับรายการที่มีจำนวนหนึ่งและ
เลขที่สี่ที่จะถูกจัดเรียงอย่างเห็นได้ชัด

822
00:27:10,000 --> 00:27:13,070
>> ดังนั้นให้ฉันเพียงแค่กำหนด
ว่ารายการนี​​้จะถูกจัดเรียง

823
00:27:13,070 --> 00:27:15,090
แต่ตอนนี้ฉันมีส่วนที่เหลือของรายการนี​​้

824
00:27:15,090 --> 00:27:17,240
ดังนั้นตอนนี้ผมพบสอง

825
00:27:17,240 --> 00:27:21,690
ในกรณีที่ไม่สองอย่างเห็นได้ชัด
อยู่ในส่วนที่เกี่ยวกับสี่?

826
00:27:21,690 --> 00:27:22,580
ก่อนที่สี่

827
00:27:22,580 --> 00:27:23,862
ดังนั้นสิ่งที่ฉันสามารถทำอะไรที่นี่?

828
00:27:23,862 --> 00:27:24,820
คุณชื่ออะไรนะ?

829
00:27:24,820 --> 00:27:25,090
>> JOSEPH: โจเซฟ

830
00:27:25,090 --> 00:27:26,030
>> เดวิดเจลัน: โจเซฟ
ถ้าคุณสามารถย้อนกลับไป

831
00:27:26,030 --> 00:27:27,790
เพียงช่วงเวลาที่มีหมายเลขของคุณ

832
00:27:27,790 --> 00:27:31,130
และตอนนี้สิ่งที่ควรทำสเตฟานนี่?

833
00:27:31,130 --> 00:27:33,720
ลองเปลี่ยนสเตฟานมากกว่าที่นี่

834
00:27:33,720 --> 00:27:35,520
และตอนนี้ปล่อยให้โจเซฟมาที่นี่

835
00:27:35,520 --> 00:27:39,660
และตอนนี้ให้ฉันอ้างว่า
ทุกอย่างที่นี่จะถูกจัดเรียง

836
00:27:39,660 --> 00:27:42,474
ดังนั้นผลที่คล้ายกัน แต่
วิธีการที่แตกต่างกัน

837
00:27:42,474 --> 00:27:44,140
ฉันไม่ได้แม้กระทั่งสิ่งที่มองลงไปที่นั่น

838
00:27:44,140 --> 00:27:46,310
ฉันเพียงแค่ให้การองค์ประกอบ
ขณะที่พวกเขากำลังส่งให้ฉัน

839
00:27:46,310 --> 00:27:47,240
และจัดการกับพวกเขา

840
00:27:47,240 --> 00:27:48,330
>> ดังนั้นตอนนี้ผมเห็นเลขหก

841
00:27:48,330 --> 00:27:51,110
เลขหกไหนอยู่?

842
00:27:51,110 --> 00:27:53,250
เรามีสองสี่หก

843
00:27:53,250 --> 00:27:54,800
ตรงที่เธอเป็นอยู่ในขณะนี้

844
00:27:54,800 --> 00:27:57,750
ดังนั้นขอให้ออกจากที่อยู่คนเดียวและตอนนี้
อ้างว่าเป็นส่วนหนึ่งของรายการนี​​้

845
00:27:57,750 --> 00:27:58,772
จะถูกจัดเรียงในขณะนี้

846
00:27:58,772 --> 00:28:01,230
ดังนั้นนี้รู้สึกพื้นฐาน
ที่แตกต่างกันในการที่ฉันแค่

847
00:28:01,230 --> 00:28:05,230
เคลื่อนที่ผ่านรายการที่นี่
เส้นตรงและฉันไม่เคยเสแสร้งกลับ

848
00:28:05,230 --> 00:28:05,730
ใช่

849
00:28:05,730 --> 00:28:06,230
ทั้งหมดขวา

850
00:28:06,230 --> 00:28:08,190
ดังนั้นแปดที่คุณอยู่?

851
00:28:08,190 --> 00:28:08,730
ที่นี่.

852
00:28:08,730 --> 00:28:09,310
ที่สมบูรณ์แบบ

853
00:28:09,310 --> 00:28:10,210
ดังนั้นตอนนี้อย่างใดอย่างหนึ่ง

854
00:28:10,210 --> 00:28:10,900
เอ่อโอ้.

855
00:28:10,900 --> 00:28:13,010
นี้รู้สึกเหมือนมัน
จะมีราคาแพง

856
00:28:13,010 --> 00:28:15,690
ขณะนี้ในขั้นตอนวิธีการก่อนหน้านี้
ฉันคนก็เปลี่ยน

857
00:28:15,690 --> 00:28:18,648
ดังนั้นผมจึงอาจจะทำให้เขาทุกทางที่
เริ่มต้น แต่จากนั้นก็ย้ายโจเซฟ

858
00:28:18,648 --> 00:28:21,450
แต่ถ้าผมย้ายโจเซฟตอนนี้
สิ่งที่จะเป็นความผิด?

859
00:28:21,450 --> 00:28:24,250
>> ตอนนี้ผมได้จัดเรียงของ undone-- ฉัน
ดำเนินการขั้นตอนหนึ่งไปข้างหน้าแล้ว

860
00:28:24,250 --> 00:28:26,300
ขั้นตอนหนึ่งที่กลับมาเพราะตอนนี้
โจเซฟจะออกคำสั่ง

861
00:28:26,300 --> 00:28:26,830
ถ้าอย่างนั้นเราทำเช่นนี้

862
00:28:26,830 --> 00:28:29,150
ถ้าคุณสามารถใช้หมายเลขหนึ่ง
และย้อนกลับไปเพื่อรอสักครู่

863
00:28:29,150 --> 00:28:30,490
วิธีที่เราสามารถ put-- สิ่งที่
เป็นชื่อของคุณอีกครั้ง

864
00:28:30,490 --> 00:28:31,130
>> อันนัน: อันนัน

865
00:28:31,130 --> 00:28:32,610
>> เดวิดเจลัน: อันนันในสถานที่?

866
00:28:32,610 --> 00:28:36,091
สิ่งที่ต้องเกิดขึ้นด้วยความเคารพ
สองสี่หกและแปด?

867
00:28:36,091 --> 00:28:37,570
พวกเขาทุกคนต้องเปลี่ยน

868
00:28:37,570 --> 00:28:42,590
ดังนั้นถ้าแปดต้องการที่จะเปลี่ยน
ครั้งแรกแล้วหกแล้วสี่แล้วสอง

869
00:28:42,590 --> 00:28:45,380
และแล้วอันนันหากคุณต้องการ
ชอบที่จะมาที่นี่ดี

870
00:28:45,380 --> 00:28:47,760
แต่ที่นี่เราได้เพียงแค่
ชนิดของการจ่ายราคา

871
00:28:47,760 --> 00:28:49,510
ที่จุดที่แตกต่างกันในขั้นตอนวิธี

872
00:28:49,510 --> 00:28:52,550
ขณะที่ครั้งที่แล้วกับการเลือก
การจัดเรียงและแม้กระทั่งการจัดเรียงฟอง

873
00:28:52,550 --> 00:28:54,700
ฉันเดินกลับ
มากลับมา

874
00:28:54,700 --> 00:28:58,360
ซึ่งเป็นที่แน่นอนเพิ่มขึ้น
เวลาที่ชาญฉลาดและขั้นตอนอย่างแท้จริง

875
00:28:58,360 --> 00:29:00,660
>> จัดเรียงแทรกในตอนแรก
ได้อย่างรวดเร็ว, ดูเหมือนว่ามัน

876
00:29:00,660 --> 00:29:05,150
สุดชาญฉลาดในการที่ฉันแค่
ทำให้ช้าความคืบหน้าเพิ่มขึ้น

877
00:29:05,150 --> 00:29:07,120
แต่ฉันจะไม่กลับมา

878
00:29:07,120 --> 00:29:09,410
แต่ถ้าคนที่เป็นจริง
ออกคำสั่งแจ้งให้ทราบล่วงหน้า

879
00:29:09,410 --> 00:29:10,840
ทั้งหมดของการทำงานฉันเพิ่งมีการทำ

880
00:29:10,840 --> 00:29:14,750
ผมต้องย้ายครึ่งหนึ่งของรายการ
เพียงเพื่อให้มีที่ว่างสำหรับจำนวนหนึ่ง

881
00:29:14,750 --> 00:29:16,790
ดังนั้นจึงเป็นปริมาณที่เท่ากัน
ของการทำงานป่านนี้มัน

882
00:29:16,790 --> 00:29:18,690
รู้สึกเพียงประเภทที่แตกต่างกันของการทำงาน

883
00:29:18,690 --> 00:29:19,370
>> ให้ดำเนินการต่อ

884
00:29:19,370 --> 00:29:22,657
ดังนั้นตอนนี้เรารู้ว่าทุกคน
ระหว่างหนึ่งและแปดเรียง

885
00:29:22,657 --> 00:29:23,740
ที่นี่ผมมีบ้านเลขที่สาม

886
00:29:23,740 --> 00:29:25,864
ถ้าคุณชอบที่จะรับ
เลขที่สามย้อนกลับไปหนึ่ง

887
00:29:25,864 --> 00:29:28,260
และสิ่งที่พวกคุณจะต้องทำอย่างไร

888
00:29:28,260 --> 00:29:28,760
อือ

889
00:29:28,760 --> 00:29:33,070
เพื่อให้เป็นอีกหนึ่งสองสามขั้นตอน

890
00:29:33,070 --> 00:29:36,010
สามหน่วยของเวลาที่เพิ่งเสียค่าใช้จ่าย
ฉันดังนั้นที่สามตอนนี้สามารถใส่

891
00:29:36,010 --> 00:29:37,460
สุดท้ายเจ็ด

892
00:29:37,460 --> 00:29:39,730
>> ลองไปข้างหน้าและมี
คุณจะใช้ขั้นตอนกลับ

893
00:29:39,730 --> 00:29:42,780
นี้เป็นเพียงจะค่าใช้จ่ายเรา
หนึ่งหน่วยของเวลา แต่ที่ตกลง

894
00:29:42,780 --> 00:29:44,170
และตอนนี้ห้าของไป
จะมีราคาแพงมากขึ้นเล็กน้อย

895
00:29:44,170 --> 00:29:45,340
หากคุณต้องการที่จะย้อนกลับไป

896
00:29:45,340 --> 00:29:48,380
เราต้องการที่จะย้ายแปด
เจ็ดหก

897
00:29:48,380 --> 00:29:50,749
และแล้วทุกคนจะถูกจัดเรียงในขณะนี้

898
00:29:50,749 --> 00:29:52,290
ดังนั้นมือใหญ่อาสาสมัครของเราที่นี่

899
00:29:52,290 --> 00:29:53,554
ขอบคุณมาก.

900
00:29:53,554 --> 00:29:56,220
>> [APPLAUSE]

901
00:29:56,220 --> 00:29:56,860
>> ขอบคุณทุกคน.

902
00:29:56,860 --> 00:29:57,520
ขอบคุณทุกคน.

903
00:29:57,520 --> 00:30:02,940
ดังนั้นเรามาดูวิธีการที่ขณะนี้เป็นเพียง
ค่าใช้จ่ายทั้งหมดที่เป็น

904
00:30:02,940 --> 00:30:06,210
ลองพิจารณาอาจจะเป็น
ที่ง่ายที่สุดของเหล่านี้จัดเรียงฟอง

905
00:30:06,210 --> 00:30:09,950
และผมพูดง่ายเพียงเพราะ
คุณสามารถแก้ปัญหาได้อย่างตะกละตะกลามโดยเพียงแค่

906
00:30:09,950 --> 00:30:11,660
แก้ไขปัญหาที่เกิดขึ้นจากจำนวนที่นี่

907
00:30:11,660 --> 00:30:13,720
แก้ไขปัญหาที่เกิดขึ้นจากจำนวน
ที่นี่อีกครั้งและอีกครั้ง

908
00:30:13,720 --> 00:30:17,680
และอีกครั้งทำซ้ำเป็นจำนวนมาก
ครั้งตามที่คุณจริงต้อง

909
00:30:17,680 --> 00:30:21,050
>> ดังนั้นมันกลับกลายเป็นว่า
มีการจัดเรียงฟองดี

910
00:30:21,050 --> 00:30:25,820
วิธีการหลายขั้นตอนที่ฉันจะต้องใช้เวลาในการ
ผ่านแรกของอัลกอริทึมที่?

911
00:30:25,820 --> 00:30:30,850
ฉันอาจ take-- ขอ see-- หนึ่ง
สองสามสี่ห้าหกเจ็ด

912
00:30:30,850 --> 00:30:32,190
และมีแปดองค์ประกอบที่นี่

913
00:30:32,190 --> 00:30:35,280
ดังนั้นมันก็เหมือน n ลบ 1 ขั้นตอนในการ
ได้รับจากจุดเริ่มต้นของรายการ

914
00:30:35,280 --> 00:30:36,380
ไปยังจุดสิ้นสุดของรายการ

915
00:30:36,380 --> 00:30:41,350
>> แต่มีการจัดเรียงการเลือกจำได้ว่าฉัน
การเลือกองค์ประกอบอีกครั้งและอีกครั้ง

916
00:30:41,350 --> 00:30:44,590
และอีกครั้งที่มีขนาดเล็กที่สุด
ฉันวางไว้ในสถานที่

917
00:30:44,590 --> 00:30:46,616
แต่แล้วฉันไม่ได้
มองข้างหลังผมอีกครั้ง

918
00:30:46,616 --> 00:30:49,490
ดังนั้นผมจึงคิดว่ามันเป็นที่ชัดเจนมากขึ้นเล็ก ๆ น้อย ๆ
แล้วที่เป็นครั้งแรกที่ฉันอาจ

919
00:30:49,490 --> 00:30:52,680
ต้องใช้เวลาทั้งหมด n ลบ 1 ขั้นตอน
เพื่อหาองค์ประกอบที่เล็กที่สุด

920
00:30:52,680 --> 00:30:55,920
จากนั้นฉันใส่ไว้ในสถานที่และฉัน
ขับไล่ใครก็ตามที่อยู่ที่นี่ก่อนหน้านี้

921
00:30:55,920 --> 00:30:57,500
>> แต่แล้วผมจะได้ไม่ต้อง
ให้มองที่องค์ประกอบนี้

922
00:30:57,500 --> 00:30:59,040
เพราะผมรู้ว่ามันเป็น
แล้วมีขนาดเล็กที่สุด

923
00:30:59,040 --> 00:31:01,581
ดังนั้นตอนนี้ฉันสามารถดูเพียงเจ็ด
องค์ประกอบแล้วหกองค์ประกอบ

924
00:31:01,581 --> 00:31:03,290
แล้วห้าองค์ประกอบแล้วธาตุทั้งสี่

925
00:31:03,290 --> 00:31:06,900
และเพื่อให้ทางคณิตศาสตร์ถ้า n เป็น
จำนวนขององค์ประกอบหรือตัวเลข

926
00:31:06,900 --> 00:31:11,990
ที่เราเริ่มต้นด้วยคุณสามารถจินตนาการ
ว่าเรื่องนี้เป็นเช่นเดียวกับ n ลบ 1,

927
00:31:11,990 --> 00:31:14,250
บวก n ลบ 2 ขั้นตอน
บวก n ลบ 3 ขั้นตอน

928
00:31:14,250 --> 00:31:16,780
บวกลบ n 4 ขั้นตอนทั้งหมด
ทางลงไปเพียงหนึ่งขั้นตอน

929
00:31:16,780 --> 00:31:18,160
และฉันกับคนสุดท้ายของฉัน

930
00:31:18,160 --> 00:31:20,650
>> และถ้าคุณจำได้ว่าเป็นจำนวนมาก
สถิติของหนังสือหรือหนังสือคณิตศาสตร์

931
00:31:20,650 --> 00:31:24,730
มีสูตรที่ผู้ที่อยู่ใน
ปกหลังหรือด้านหน้าของพวกเขา

932
00:31:24,730 --> 00:31:27,690
ปรากฎว่าชุดนี้
สามารถแสดงขึ้นเพียง

933
00:31:27,690 --> 00:31:28,857
เป็นครั้ง n n ลบ 1 2

934
00:31:28,857 --> 00:31:31,273
และก็ปรับหากที่ไม่
อยู่ในระดับแนวหน้าของจิตใจของคุณ

935
00:31:31,273 --> 00:31:32,420
แต่นี้เป็นความจริง

936
00:31:32,420 --> 00:31:34,449
นั่นเป็นเพียงวิธีที่ง่ายของการเขียนมัน

937
00:31:34,449 --> 00:31:36,240
และจากนั้นถ้าคุณคิด
กลับไปที่โรงเรียนชั้นประถมศึกษาปี

938
00:31:36,240 --> 00:31:38,698
เมื่อคุณเพียงแค่เริ่มต้นคูณ
สิ่งที่ออกมานี้แน่นอน

939
00:31:38,698 --> 00:31:41,820
เป็นเพียงการยืด n ลบ n หารด้วย 2

940
00:31:41,820 --> 00:31:44,772
ทั้งหมดที่ฉันได้ทำคือการขยาย
มีการแสดงออก

941
00:31:44,772 --> 00:31:46,730
และเพื่อให้เขียนนี้
แตกต่างกันเล็กน้อย

942
00:31:46,730 --> 00:31:49,780
ที่ squared n หารด้วย 2 ลบ n / 2

943
00:31:49,780 --> 00:31:53,270
>> ดังนั้นอีกครั้งฉันเพียงแค่ชนิดของการใช้
กฎทางคณิตศาสตร์มี

944
00:31:53,270 --> 00:31:57,140
แต่ตอนนี้สังเกตเห็นว่าคำที่ยิ่งใหญ่ที่สุด
ในการแสดงออกนี้เพื่อที่จะพูด

945
00:31:57,140 --> 00:31:58,540
คือว่า n ยกกำลังสอง

946
00:31:58,540 --> 00:32:02,910
ดังนั้นใช่มันยกกำลังสอง n
โดยแบ่งออกเป็น 2 ลบ n / 2

947
00:32:02,910 --> 00:32:05,080
>> แต่โดยทั่วไปถ้า n เป็น
จะเป็นค่าใหญ่

948
00:32:05,080 --> 00:32:08,740
ฉันจะอ้างว่า n ยกกำลังสอง
เป็นไปได้ที่จะเป็นปัจจัยที่โดดเด่น

949
00:32:08,740 --> 00:32:10,490
มันเป็นเพียงแค่ไปได้
ผู้สนับสนุนที่ใหญ่กว่า

950
00:32:10,490 --> 00:32:12,877
จำนวนของขั้นตอนกว่า n / 2

951
00:32:12,877 --> 00:32:13,960
ดังนั้นสิ่งที่ผมหมายถึงนี้?

952
00:32:13,960 --> 00:32:16,795
ลองตัวอย่างง่ายแม้
แม้ว่าคณิตศาสตร์ที่ได้รับขนาดใหญ่เล็ก ๆ น้อย ๆ

953
00:32:16,795 --> 00:32:20,210
>> ดังนั้นสมมติว่าเรามี 1 ล้านคน
บนเวทีหรือสิ่งที่ 1000000

954
00:32:20,210 --> 00:32:21,320
ที่เราต้องการเรียงลำดับ

955
00:32:21,320 --> 00:32:23,730
ลองเสียบล้าน
เข้าสูตรที่ว่า

956
00:32:23,730 --> 00:32:27,230
เพื่อดูว่าหลายขั้นตอนจะใช้เวลารวม
การเรียงลำดับล้านองค์ประกอบที่ใช้พูด

957
00:32:27,230 --> 00:32:28,560
เลือกการเรียงลำดับ

958
00:32:28,560 --> 00:32:30,760
>> ดังนั้นเราจึงต้องการมีสูตรเช่นเดียวกับก่อน

959
00:32:30,760 --> 00:32:34,120
ฉันเสียบล้านบาทเพื่อให้ฉันได้รับ
ล้าน squared หารด้วย 2

960
00:32:34,120 --> 00:32:35,990
ลบล้านบาทโดยแบ่งออกเป็น 2

961
00:32:35,990 --> 00:32:40,180
ถ้าผมทำคณิตศาสตร์ที่ล่วงหน้า
ที่นี่เรามี 500000000000

962
00:32:40,180 --> 00:32:47,460
ลบ 500,000 ซึ่ง
จะช่วยให้เรา 499,999,500,000,

963
00:32:47,460 --> 00:32:49,270
ซึ่งเป็นสาปสวยขนาดใหญ่

964
00:32:49,270 --> 00:32:54,370
>> ในความเป็นจริงถ้าคุณเปรียบเทียบในขณะนี้
499,000,000,000 เลขที่ 999 ล้านบาท

965
00:32:54,370 --> 00:33:01,210
500,000 กับค่าเดิมของเรา
500,000,000,000, มันจึงแช่งใกล้

966
00:33:01,210 --> 00:33:06,850
ใช่มั้ย? n squared หารด้วย 2 จะช่วยให้
us-- หรือมากกว่า n squared หารด้วย 2

967
00:33:06,850 --> 00:33:08,370
ทำให้เรา 500000000000

968
00:33:08,370 --> 00:33:13,510
นั่นเป็นสาปสวยใกล้เคียง
เพื่อ 499,999,500,000,

969
00:33:13,510 --> 00:33:17,970
ซึ่งก็คือการบอกว่าลบออก 500,000
หรือมากกว่าโดยทั่วไปลบออก

970
00:33:17,970 --> 00:33:20,010
n ยืดไม่ได้จริงๆเป็นเรื่องใหญ่

971
00:33:20,010 --> 00:33:22,490
n ที่ทำให้สองเหล่านี้
ตัวเลขที่เติบโตอย่างรวดเร็วจริงๆ

972
00:33:22,490 --> 00:33:25,790
>> ตอนนี้เป็นสิ่งสำคัญเพียงตราบเท่า
ในขณะที่เราเป็นนักวิทยาศาสตร์คอมพิวเตอร์

973
00:33:25,790 --> 00:33:29,350
มักจะไม่ได้ไปดูแลมาก
เกี่ยวกับความแตกต่างของสูตรเหล่านี้

974
00:33:29,350 --> 00:33:31,400
และตรงกับสิ่งที่
คำตอบที่ชัดเจน

975
00:33:31,400 --> 00:33:33,390
เราดูแลเพียง แต่ที่คุณรู้อะไรไหม

976
00:33:33,390 --> 00:33:37,810
ในตอนท้ายของวันสูตรนี้
เป็นคำสั่งของ n แคว

977
00:33:37,810 --> 00:33:39,350
>> ใช่เรากำลังหารด้วย 2 ในการมี

978
00:33:39,350 --> 00:33:41,360
ใช่เรากำลังลบออก n ลบ 2

979
00:33:41,360 --> 00:33:46,860
แต่ในตอนท้ายของวันที่คำว่า
ที่จริงเจ็บเราและค่าใช้จ่ายเรา

980
00:33:46,860 --> 00:33:48,995
จำนวนมากของขั้นตอนคือระยะตาราง

981
00:33:48,995 --> 00:33:51,370
และเพื่อให้สิ่งที่นักวิทยาศาสตร์คอมพิวเตอร์
เป็นไปโดยทั่วไปทำ

982
00:33:51,370 --> 00:33:54,160
จะไม่สนใจทุกคน
ที่มีขนาดเล็กแง่การสั่งซื้อ

983
00:33:54,160 --> 00:33:56,900
และเพียงแค่มองไปที่คนที่
มีส่วนช่วยมากที่สุดค่าใช้จ่าย

984
00:33:56,900 --> 00:34:00,530
>> และนี่เป็นสิ่งที่ดีเพราะเราสามารถ
ตอนนี้พูดคุยในทั่วไปมากขึ้น

985
00:34:00,530 --> 00:34:02,470
เกี่ยวกับขั้นตอนวิธีการและสามารถเปรียบเทียบพวกเขา

986
00:34:02,470 --> 00:34:04,550
และความจริงที่ว่าฉัน
โดยใช้ O นี้โดยเจตนา

987
00:34:04,550 --> 00:34:06,680
เมื่อฉันพูดเกี่ยวกับการสั่งซื้อ
ของผมโดยเฉพาะ

988
00:34:06,680 --> 00:34:09,560
หมายถึงบางสิ่งบางอย่าง
เรียกว่าขนาดใหญ่และขนาดใหญ่โอโอ

989
00:34:09,560 --> 00:34:14,090
เป็นสัญกรณ์ที่คอมพิวเตอร์
นักวิทยาศาสตร์ใช้ในการอธิบาย

990
00:34:14,090 --> 00:34:16,710
ขอบเขตบนของบางสิ่งบางอย่าง

991
00:34:16,710 --> 00:34:21,150
>> ดังนั้นถ้าคุณบอกว่าอัลกอริทึม
อยู่ในโอใหญ่ของ n ยืด,

992
00:34:21,150 --> 00:34:23,380
ขณะที่ผมนำเสนอเพียง
ช่วงเวลาที่ผ่านมาหมายความว่า

993
00:34:23,380 --> 00:34:27,710
ว่าในแง่ของการทำงานของมัน
เวลาหรือประสิทธิภาพของมัน

994
00:34:27,710 --> 00:34:30,090
มันจะใช้เวลาในการสั่งซื้อ
n ของสองขั้นตอน

995
00:34:30,090 --> 00:34:31,420
บางทีอาจจะมากกว่าอาจจะน้อย

996
00:34:31,420 --> 00:34:33,435
แต่มันเป็นคำสั่งของ n ยืด

997
00:34:33,435 --> 00:34:34,560
และนั่นคือขอบเขตบน

998
00:34:34,560 --> 00:34:36,530
มันไม่ได้เป็นไปได้
เจ็บปวดมากไปกว่านั้น

999
00:34:36,530 --> 00:34:40,800
มันไม่ได้เป็นไปได้คีบ n หรือ 2
ถึง n หรือบางสิ่งบางอย่างที่ใหญ่กว่ามาก

1000
00:34:40,800 --> 00:34:43,800
นี้เป็นขอบเขตบน
ในสิ่งที่เป็นค่าใช้จ่าย

1001
00:34:43,800 --> 00:34:46,150
เพื่อให้ได้รับการขอ
พิจารณาเพียงไม่กี่ตัวอย่าง

1002
00:34:46,150 --> 00:34:49,820
และนี่เป็นเพียงรายชื่อแน่นอน
ของที่พบบ่อยมากเวลาทำงาน

1003
00:34:49,820 --> 00:34:52,870
สำหรับขั้นตอนวิธีการที่หมายถึงการเป็น
เป็นตัวอย่างของบางสิ่งบางอย่างเราได้

1004
00:34:52,870 --> 00:34:53,600
เห็นแล้ว

1005
00:34:53,600 --> 00:34:58,060
>> ดังนั้นสำหรับตัวอย่างเช่นในกรณีของ
การเรียงลำดับการเลือกสิ่งที่ฉันอ้างนี่

1006
00:34:58,060 --> 00:35:02,250
คือการจัดเรียงของการทำงานที่เลือก
เวลาที่อยู่ในคำสั่งของ n ยืด

1007
00:35:02,250 --> 00:35:06,260
ในกรณีที่เลวร้ายที่สุดที่ฉันจะมี
ทั้งกลุ่มของตัวเลขสุ่มที่นี่

1008
00:35:06,260 --> 00:35:08,600
และอย่างที่เราเห็นทางคณิตศาสตร์
ถ้าฉันให้เดิน

1009
00:35:08,600 --> 00:35:11,310
ผ่านรายการที่ผ่านการ
รายการต่อไปเลือกที่เล็กที่สุด

1010
00:35:11,310 --> 00:35:14,410
องค์ประกอบอีกครั้งและอีกครั้งถ้าฉัน
เขียนลงจริงทุกขั้นตอน

1011
00:35:14,410 --> 00:35:18,750
ฉันสละตามที่ผมเสนอ formulaically
ก่อนจะอยู่ในคำสั่งของ n แคว

1012
00:35:18,750 --> 00:35:20,370
ขั้นตอนที่ฉันสละ

1013
00:35:20,370 --> 00:35:24,520
>> และปรากฎว่าฟอง
การจัดเรียงและจัดเรียงแทรก

1014
00:35:24,520 --> 00:35:27,370
เป็นเพียงความช้าในกรณีที่เลวร้ายที่สุด

1015
00:35:27,370 --> 00:35:32,040
พิจารณาเช่นการจัดเรียงแทรก
ขั้นตอนวิธีสุดท้ายที่เราจัดการกับ

1016
00:35:32,040 --> 00:35:35,500
ซึ่งเราดูที่องค์ประกอบ
แล้วใส่มันที่มันอยู่

1017
00:35:35,500 --> 00:35:38,720
และจากนั้นเรามองที่องค์ประกอบถัดไป
และใส่มันที่มันอยู่

1018
00:35:38,720 --> 00:35:40,990
>> เพื่อพิจารณาสถานการณ์ที่ดีที่สุด

1019
00:35:40,990 --> 00:35:45,590
สมมติว่าผมได้อาสาสมัครของฉันเริ่มขึ้น
แท้จริงเช่นนี้หนึ่งถึงแปด

1020
00:35:45,590 --> 00:35:47,440
เรียงแล้ว

1021
00:35:47,440 --> 00:35:51,300
วิธีหลายขั้นตอนคือการจัดเรียงแทรก
จะใช้เวลาในการจัดเรียงแปดคน

1022
00:35:51,300 --> 00:35:55,640
ถ้าพวกเขามาถึงบนเวที
มองเช่นนี้หรือไม่?

1023
00:35:55,640 --> 00:35:57,410
>> แปดคนเรียงแล้ว

1024
00:35:57,410 --> 00:35:58,760
และฉันจะใช้การจัดเรียงแทรก

1025
00:35:58,760 --> 00:36:02,180
ที่สุดท้ายของขั้นตอนวิธี

1026
00:36:02,180 --> 00:36:03,640
ดีขอซ้ำอย่างรวดเร็วจริง

1027
00:36:03,640 --> 00:36:05,504
ดังนั้นถ้าฉันเริ่มต้นที่นี่ผมเห็นอย่างใดอย่างหนึ่ง

1028
00:36:05,504 --> 00:36:06,420
หนึ่งจะอยู่ที่ไหน?

1029
00:36:06,420 --> 00:36:07,730
มันเป็นของที่นี่

1030
00:36:07,730 --> 00:36:08,330
ผมเห็นสอง

1031
00:36:08,330 --> 00:36:09,660
สองไหนอยู่?

1032
00:36:09,660 --> 00:36:10,260
ที่นี่.

1033
00:36:10,260 --> 00:36:10,900
ผมเห็นสาม

1034
00:36:10,900 --> 00:36:11,920
สามไหนอยู่?

1035
00:36:11,920 --> 00:36:12,480
ที่นี่.

1036
00:36:12,480 --> 00:36:13,100
>> เราเห็นสี่

1037
00:36:13,100 --> 00:36:13,600
ที่นี่.

1038
00:36:13,600 --> 00:36:15,660
ห้าหกเจ็ดแปด

1039
00:36:15,660 --> 00:36:17,320
ไม่มีเหตุผลที่จะทำซ้ำตัวเองไม่ได้

1040
00:36:17,320 --> 00:36:21,260
ดังนั้นวิธีการหลายขั้นตอน
คือว่าในแง่ของ n?

1041
00:36:21,260 --> 00:36:23,870
มันอยู่ในคำสั่งของ n
ขั้นตอนใช่มั้ย? n ลบ 1

1042
00:36:23,870 --> 00:36:27,567
แต่ผมเอาตัวเลขเชิงเส้น
ขั้นตอนและตอนนี้ฉันทำ

1043
00:36:27,567 --> 00:36:28,900
เพื่อให้เป็นกรณีที่ดีที่สุด แต่

1044
00:36:28,900 --> 00:36:29,983
สิ่งที่เกี่ยวกับกรณีที่เลวร้ายที่สุด?

1045
00:36:29,983 --> 00:36:32,730
สิ่งที่แปดที่นั่น
และเจ็ดลงที่นั่น

1046
00:36:32,730 --> 00:36:35,840
และหนึ่งและสองได้มากกว่าที่นี่ดังนั้น
ว่ารายการที่ตรงกันข้ามอย่างแท้จริง?

1047
00:36:35,840 --> 00:36:38,300
>> ดีสิ่งที่เกิดขึ้นจริง
ถ้านี้เป็นจำนวน?

1048
00:36:38,300 --> 00:36:41,300
และเราจะทำเพียงไม่กี่ตัวอย่าง

1049
00:36:41,300 --> 00:36:49,300
เกิดอะไรขึ้นถ้าจริงจำนวนแปด
อยู่ที่นี่และ number-- ขออภัย

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
ดังนั้นสิ่งที่ถ้าจริงจำนวน
แปดคือทุกทางมากกว่าที่นี่

1052
00:36:56,430 --> 00:36:57,790
และฉันใช้การจัดเรียงแทรก?

1053
00:36:57,790 --> 00:36:58,290
>> ตกลง.

1054
00:36:58,290 --> 00:37:00,280
ฉันเรียกร้องในขณะนี้ก็อยู่ในสถานที่

1055
00:37:00,280 --> 00:37:03,152
แต่ตอนนี้ไม่ seven-- ที่เจ็ดไป?

1056
00:37:03,152 --> 00:37:04,360
แน่นอนว่ามันจะไปมากกว่าที่นี่

1057
00:37:04,360 --> 00:37:06,760
ดังนั้นผมจึงต้องย้ายแปดมากกว่าที่เดียว

1058
00:37:06,760 --> 00:37:08,554
ตอนนี้หกที่มันไม่ไป?

1059
00:37:08,554 --> 00:37:09,220
ดีสิ่งที่ถูกต้อง

1060
00:37:09,220 --> 00:37:13,150
ตอนนี้ผมต้องย้ายแปดมากกว่า
สถานที่ที่เจ็ดและสถานที่

1061
00:37:13,150 --> 00:37:14,440
และจากนั้นผมป๋อมลงหก

1062
00:37:14,440 --> 00:37:16,870
>> ดังนั้นครั้งแรกก็มีค่าใช้จ่าย
ฉันหนึ่งขั้นตอนในการแก้ไขสิ่งที่

1063
00:37:16,870 --> 00:37:18,570
แล้วค่าใช้จ่ายฉันสองขั้นตอนในการแก้ไขสิ่งที่

1064
00:37:18,570 --> 00:37:20,370
วิธีการหลายขั้นตอนมันเป็น
จะใช้เวลาในการแก้ไขปัญหา

1065
00:37:20,370 --> 00:37:22,720
สิ่งที่จะนำห้าในสถานที่ที่เหมาะสมหรือไม่

1066
00:37:22,720 --> 00:37:23,340
สาม

1067
00:37:23,340 --> 00:37:29,520
เพราะตอนนี้ฉันต้อง
ย้ายหนึ่งสองสาม

1068
00:37:29,520 --> 00:37:32,430
วิธีหลายขั้นตอนมันจะใช้เวลา
ที่จะนำสี่ในสถานที่ที่เหมาะสมหรือไม่

1069
00:37:32,430 --> 00:37:36,040
4 บวก 5 บวก 6 บวก 7

1070
00:37:36,040 --> 00:37:40,260
>> และดังนั้นจึงเป็นทางคณิตศาสตร์เหมือนกันกับ
สิ่งที่เราอธิบายไว้สำหรับการจัดเรียงการเลือก

1071
00:37:40,260 --> 00:37:42,130
เรามีชุดนี้
นั่นเป็นเพียงที่เพิ่มขึ้น

1072
00:37:42,130 --> 00:37:45,650
1 บวก 2 บวก 3 บวก 4,
หรือตรงกันข้าม 7 บวก 6

1073
00:37:45,650 --> 00:37:52,610
บวก 5 บวก 4 เพิ่มขึ้นสำหรับวันนี้
เพื่อวัตถุประสงค์ในการสั่งซื้อของ n ยืด

1074
00:37:52,610 --> 00:37:57,640
>> เพื่อให้ฉันเกินไปที่กำหนด
การจัดเรียงฟองยังอยู่ในกำลังสอง n

1075
00:37:57,640 --> 00:38:01,340
เพราะมีการจัดเรียงฟองแต่ละ
ทุกครั้งที่ผมไปผ่านรายการ

1076
00:38:01,340 --> 00:38:03,100
ฉันสละประมาณวิธีการหลายขั้นตอน?

1077
00:38:03,100 --> 00:38:06,260
เวลาที่ฉันแต่ละตัวอักษร
เดินจากที่นั่นไปที่นั่น?

1078
00:38:06,260 --> 00:38:07,960
ขั้นตอนประมาณ n

1079
00:38:07,960 --> 00:38:12,650
แต่วิธีการที่หลายต่อหลายครั้งผมอาจจะ
ต้องผ่านรายการหรือไม่

1080
00:38:12,650 --> 00:38:13,920
>> ดีประมาณ n เวลา

1081
00:38:13,920 --> 00:38:15,680
บางที n ลบ 1 แต่ประมาณ n ครั้ง

1082
00:38:15,680 --> 00:38:16,430
ดีทำไมเป็นอย่างนั้น?

1083
00:38:16,430 --> 00:38:19,560
ดีกับการจัดเรียงฟองถ้า
เราเริ่มต้นด้วยการจัดเรียงฟอง

1084
00:38:19,560 --> 00:38:23,570
ที่มีรายชื่อในที่เลวร้ายที่สุดที่เป็นไปได้
สถานการณ์อีกครั้งซึ่งจะสมบูรณ์

1085
00:38:23,570 --> 00:38:25,550
หลังสิ่งที่จะเกิดขึ้น?

1086
00:38:25,550 --> 00:38:28,830
ฉันไปถึงรายชื่อและจำนวน
เป็นหนึ่งในทุกทางที่นั่น

1087
00:38:28,830 --> 00:38:33,280
>> แต่มีการจัดเรียงฟองวิธีไกลไม่อย่างใดอย่างหนึ่ง
ย้ายผ่านครั้งแรกของฉันผ่านรายการหรือไม่

1088
00:38:33,280 --> 00:38:36,620
วิธีการหลายจุดที่เขาไม่ได้รับ
ใกล้ชิดกับสถานที่ที่ถูกต้องหรือไม่

1089
00:38:36,620 --> 00:38:37,240
แค่หนึ่ง.

1090
00:38:37,240 --> 00:38:40,281
ดังนั้นหากคุณชนิดของเหตุผลที่ผ่านนี้
เวลาผ่านไปผ่านขั้นตอนวิธีนี้ทุก

1091
00:38:40,281 --> 00:38:41,880
ดาวิดขั้นตอนการประมาณ n

1092
00:38:41,880 --> 00:38:44,940
แต่วิธีการที่หลายคนผ่าน
ผ่านรายการมันเป็น

1093
00:38:44,940 --> 00:38:49,060
จะใช้เวลาหนึ่งฟอง
ด้านซ้ายที่มันอยู่หรือไม่?

1094
00:38:49,060 --> 00:38:51,840
>> เขามีที่จะย้ายเหมือน
พื้นที่ n วิธีนี้

1095
00:38:51,840 --> 00:38:57,960
ดังนั้นเพียงแค่จะทำเรียงลำดับของรายการ
ผมต้องเดินไปมาครั้ง n

1096
00:38:57,960 --> 00:39:01,540
และทุกครั้งที่ผม
มองไปที่องค์ประกอบ n

1097
00:39:01,540 --> 00:39:05,410
ดังนั้นทำสิ่ง n n ครั้ง
การสั่งซื้อของ n ยกกำลังสอง

1098
00:39:05,410 --> 00:39:07,220
>> ตอนนี้เราจะเห็นในบาง
กางเกงขาสั้นที่

1099
00:39:07,220 --> 00:39:10,440
ที่ฝังอยู่ในปัญหาต่อไปของ CS50
ตั้งค่าอีกวิธีหนึ่งที่เหล่านี้

1100
00:39:10,440 --> 00:39:13,490
แต่ตอนนี้ขอเพียงแค่พิจารณา
บางครั้งการทำงานอื่น ๆ

1101
00:39:13,490 --> 00:39:16,840
โดยเฉพาะอย่างยิ่งถ้าคนที่ใช้การเรียงลำดับ
นิด ๆ หน่อย ๆ ของเวลาที่จะจมอยู่ใน

1102
00:39:16,840 --> 00:39:21,790
อะไรขั้นตอนวิธีการที่เราได้เห็นแล้ว
ที่ใช้เวลาในการสั่งซื้อขั้นตอน n หรือไม่

1103
00:39:21,790 --> 00:39:27,560
>> สิ่งที่ควรใช้จำนวนเชิงเส้น
ขั้นตอนของการที่เราได้เห็นป่านนี้?

1104
00:39:27,560 --> 00:39:29,350
นั่นอะไร?

1105
00:39:29,350 --> 00:39:30,480
การค้นหาสมุดโทรศัพท์

1106
00:39:30,480 --> 00:39:31,390
อัลกอริทึมแรก

1107
00:39:31,390 --> 00:39:31,560
ใช่มั้ย?

1108
00:39:31,560 --> 00:39:33,650
ที่เรากำลังเป็นเส้นตรง
หาไมค์สมิ ธ

1109
00:39:33,650 --> 00:39:34,150
อันที่จริง

1110
00:39:34,150 --> 00:39:37,180
จากสัปดาห์ที่ศูนย์เมื่อฉันเริ่มต้น
หันหน้าหนึ่งที่เวลา

1111
00:39:37,180 --> 00:39:40,095
และผมก็บอกว่ามันเป็นชนิด
อัลกอริทึมของความรู้สึกเชิงเส้น

1112
00:39:40,095 --> 00:39:42,720
และเรามีภาพที่
คณะกรรมการที่มีเส้นสีแดงตรง

1113
00:39:42,720 --> 00:39:44,678
และสีเหลืองตรง
เส้นเหล่านั้นแน่นอน

1114
00:39:44,678 --> 00:39:46,810
อัลกอริทึมที่อยู่ในโอใหญ่ของ n

1115
00:39:46,810 --> 00:39:50,680
>> เพราะจะหาไมค์สมิ ธ ในโทรศัพท์
หนังสือหน้า n ในกรณีที่เลวร้ายที่สุด

1116
00:39:50,680 --> 00:39:52,422
อาจใช้เวลา me n ขั้นตอน

1117
00:39:52,422 --> 00:39:53,630
สิ่งที่เกี่ยวกับการเข้าร่วมประชุม?

1118
00:39:53,630 --> 00:39:55,790
หนึ่งสองสามสี่ห้าหก.

1119
00:39:55,790 --> 00:39:59,420
อะไรเวลาทำงานนี้
อัลกอริทึมสำหรับการเข้าร่วมประชุม?

1120
00:39:59,420 --> 00:40:03,070
Big O ของ n เพราะในทฤษฎีฉัน
ต้องชี้ทุกคนในห้อง

1121
00:40:03,070 --> 00:40:05,861
>> ขณะนี้เป็นกันสิ่งที่เกี่ยวกับ
การเพิ่มประสิทธิภาพอื่น ๆ จากสัปดาห์ที่ศูนย์?

1122
00:40:05,861 --> 00:40:08,117
สองสี่หกแปด, 10, 12

1123
00:40:08,117 --> 00:40:10,200
นักวิทยาศาสตร์คอมพิวเตอร์จะ
ตระหนักถึงรอสักครู่

1124
00:40:10,200 --> 00:40:12,320
ที่อยู่ในคำสั่งของ
แบ่ง n โดยขั้นตอนที่สอง

1125
00:40:12,320 --> 00:40:12,820
ใช่มั้ย?

1126
00:40:12,820 --> 00:40:14,444
เพราะฉันทำคนสองคนในเวลาเดียวกัน

1127
00:40:14,444 --> 00:40:17,015
แต่เรากำลังจะไปที่จะไม่สนใจ
ผู้ที่ต่ำกว่าเงื่อนไขการสั่งซื้อ

1128
00:40:17,015 --> 00:40:19,140
และเรากำลังจะ
โยนออกไปหารด้วย 2

1129
00:40:19,140 --> 00:40:21,830
และเพียงแค่บอกว่าโอใหญ่ของ n
สำหรับขั้นตอนวิธีการที่ดี

1130
00:40:21,830 --> 00:40:22,760
>> สิ่งที่เกี่ยวกับคนนี้?

1131
00:40:22,760 --> 00:40:26,170
เราจะข้ามบางเหล่านี้ แต่สิ่งที่
เป็นอัลกอริทึมที่ได้รับเข้าสู่ระบบของ n อยู่แล้ว?

1132
00:40:26,170 --> 00:40:29,900
ที่เอาคร่าว ๆ เข้าสู่ระบบขั้นตอน n?

1133
00:40:29,900 --> 00:40:30,870
แบ่งและพิชิต

1134
00:40:30,870 --> 00:40:31,369
ที่แน่นอน

1135
00:40:31,369 --> 00:40:33,900
เหมือนเช่นสมุดโทรศัพท์ใน
สัปดาห์ที่ศูนย์และก่อนหน้านี้ในวันนี้

1136
00:40:33,900 --> 00:40:36,191
ที่เราแบ่งปัญหา
อีกครั้งและอีกครั้งและอีกครั้ง

1137
00:40:36,191 --> 00:40:39,070
เราดึงมันลงบนกระดานในสัปดาห์
ศูนย์เป็นเส้นสีเขียวโค้ง

1138
00:40:39,070 --> 00:40:41,460
และเรากล่าวว่าวันนั้นมันเป็น
ขั้นตอนวิธีการลอการิทึม

1139
00:40:41,460 --> 00:40:44,970
>> และแน่นอนจำนวนของขั้นตอนมัน
ใช้เวลาในการดำเนินการแบ่งและพิชิต,

1140
00:40:44,970 --> 00:40:48,610
หรือการค้นหาแบบไบนารีที่เราจะเริ่มต้น
เรียกมันว่าเป็นในสมุดโทรศัพท์

1141
00:40:48,610 --> 00:40:50,680
เป็นคำสั่งของการเข้าสู่ระบบและขั้นตอนที่

1142
00:40:50,680 --> 00:40:52,470
และนี่คือบิตของประหลาด

1143
00:40:52,470 --> 00:40:54,910
>> สิ่งที่เกิดขั้นตอนเดียว
หรือมากขึ้นโดยเฉพาะ

1144
00:40:54,910 --> 00:40:56,240
จำนวนคงที่ของขั้นตอน?

1145
00:40:56,240 --> 00:40:58,865
อาจจะเป็นทั้งสองอาจจะเป็นที่สาม
แต่นักวิทยาศาสตร์คอมพิวเตอร์เพียง

1146
00:40:58,865 --> 00:41:01,423
ช่วยลดความยุ่งยากเป็นโอใหญ่ของ 1,
บางจำนวนคงที่ของขั้นตอน

1147
00:41:01,423 --> 00:41:04,256
อะไรเป็นสิ่งที่คุณจะทำอย่างนั้น
จะใช้เวลาเป็นจำนวนมากอย่างต่อเนื่องของขั้นตอน?

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> อะไรเวลาการทำงานของตบมือหรือไม่

1150
00:41:10,930 --> 00:41:11,920
เวลาคงที่

1151
00:41:11,920 --> 00:41:12,420
ใช่มั้ย?

1152
00:41:12,420 --> 00:41:15,490
เช่นเดียวกับสิ่งที่เป็นเวลาทำงานของ
ทำอะไรที่ใช้เวลาเพียงหนึ่ง

1153
00:41:15,490 --> 00:41:18,570
การดำเนินการเช่นเดียวกับการพิมพ์ F Hello World

1154
00:41:18,570 --> 00:41:24,110
ที่อาจจะมีการกล่าวถึงเป็นเวลาอย่างต่อเนื่อง
เว้นแต่กรณีที่มีมุมน้อย F พิมพ์

1155
00:41:24,110 --> 00:41:28,260
สิ่งที่อาจจะเวลาการทำงาน
ของ F พิมพ์จริงจะเป็นอย่างไร

1156
00:41:28,260 --> 00:41:28,790
และทำไม?

1157
00:41:28,790 --> 00:41:30,550
เป็นวัดที่ n ในกรณีที่ว่าคืออะไร?

1158
00:41:30,550 --> 00:41:32,251
>> ผู้ชม: [ไม่ได้ยิน]

1159
00:41:32,251 --> 00:41:33,250
เดวิดเจลัน: แน่นอน

1160
00:41:33,250 --> 00:41:34,900
จำนวนของตัวละคร
เราต้องการที่จะพิมพ์

1161
00:41:34,900 --> 00:41:36,191
ดังนั้นจึงเป็นไปตามบริบทมาก

1162
00:41:36,191 --> 00:41:39,910
วันนี้เราได้รับการมุ่งเน้นมากใน
ตัวอักษรและตัวเลขที่นี่บนกระดาน

1163
00:41:39,910 --> 00:41:43,540
แต่ก็ยังอาจจะมี
ตัวอักษรในสตริงที่เกิดขึ้นจริง

1164
00:41:43,540 --> 00:41:46,420
ดังนั้นมันจะเปิดออกมีอีก
ตัวชี้วัดที่จะเริ่มต้นการดูแลเกี่ยวกับ

1165
00:41:46,420 --> 00:41:48,530
และที่ตรงข้าม
ของ O ขนาดใหญ่เพื่อที่จะพูด

1166
00:41:48,530 --> 00:41:50,120
>> นั่นเป็นสัญกรณ์โอเมก้า

1167
00:41:50,120 --> 00:41:53,380
ในขณะที่ขนาดใหญ่ O หมายถึงสิ่งที่เป็นที่
บนผูกพันกับเวลาทำงานของคุณ?

1168
00:41:53,380 --> 00:41:55,580
ที่สุด, เวลาเท่าไร
บางสิ่งบางอย่างอาจใช้เวลา?

1169
00:41:55,580 --> 00:41:59,250
ขอโทษ Omega-- นี้ช่วยให้มา
up-- อยู่ตรงข้ามของที่

1170
00:41:59,250 --> 00:42:02,960
โดยจะเป็นขีด จำกัด ล่างบน
จำนวนเงินของบางสิ่งบางครั้งอาจใช้เวลา

1171
00:42:02,960 --> 00:42:10,480
>> ดังนั้น ตัวอย่างเช่นสิ่งที่เป็นอัลกอริทึม
ที่ใช้ขั้นตอนที่สองเสมอ n?

1172
00:42:10,480 --> 00:42:15,600
ดีซึ่งเป็นหนึ่งในขั้นตอนวิธีการที่เราได้เห็น
วันนี้ในความเป็นจริงอาจจะมีเช่นกัน

1173
00:42:15,600 --> 00:42:16,720
การเรียงลำดับการเลือก

1174
00:42:16,720 --> 00:42:18,270
เลือกการเรียงลำดับโง่สวย

1175
00:42:18,270 --> 00:42:21,760
แม้ว่าขอโทษ algorithm-- แม้
ถ้าอาร์เรย์จะเรียงลำดับแล้ว

1176
00:42:21,760 --> 00:42:24,150
การเรียงลำดับการเลือกจะไป
ให้เดินผ่านรายการ

1177
00:42:24,150 --> 00:42:28,907
เพื่อให้แน่ใจว่ามีขนาดเล็กที่สุด
องค์ประกอบอีกครั้งและอีกครั้งและอีกครั้ง

1178
00:42:28,907 --> 00:42:31,740
และแม้ว่าคุณมนุษย์ใน
ผู้ชมรู้ว่ารอสักครู่

1179
00:42:31,740 --> 00:42:33,948
คุณได้ผ่านการ
องค์ประกอบที่เล็กที่สุดของคอมพิวเตอร์

1180
00:42:33,948 --> 00:42:37,300
ไม่ทราบว่าจนดูเหมือน
ตลอดทางผ่านรายการ

1181
00:42:37,300 --> 00:42:40,240
ในทำนองเดียวกันที่ถูกผูกไว้ที่ต่ำกว่าที่
นอกจากนี้ยังอาจจะนำมาพิจารณา

1182
00:42:40,240 --> 00:42:42,000
อาจจะมีเวลาเชิงเส้น

1183
00:42:42,000 --> 00:42:48,260
>> เวลาเท่าไหร่มันไม่ใช้เวลาในการ
การจัดเรียงองค์ประกอบ n ในที่ดีที่สุด

1184
00:42:48,260 --> 00:42:52,420
กรณีใช้สิ่งที่ต้องการจัดเรียงฟอง?

1185
00:42:52,420 --> 00:42:54,280
สมมติว่ารายการของคุณจะถูกจัดเรียงอยู่แล้ว

1186
00:42:54,280 --> 00:42:56,696
เราได้กล่าวว่าการจัดเรียงฟองใช้เวลาใน
คำสั่งของ n สองขั้นตอน

1187
00:42:56,696 --> 00:42:59,640
แต่สิ่งที่ถ้ามันเรียงอยู่แล้ว?

1188
00:42:59,640 --> 00:43:02,310
เกิดอะไรขึ้นถ้าคุณรู้หลังจาก
หนึ่งผ่านอาร์เรย์

1189
00:43:02,310 --> 00:43:03,540
ที่คุณได้ทำสัญญาแลกเปลี่ยนไม่?

1190
00:43:03,540 --> 00:43:05,970
คุณจำเป็นต้องให้การผ่านมากขึ้น?

1191
00:43:05,970 --> 00:43:06,470
>> เลขที่

1192
00:43:06,470 --> 00:43:10,340
ดังนั้นที่ถูกผูกไว้ที่ลดลงในการจัดเรียงฟอง
อาจจะกล่าวได้ว่าเป็นเชิงเส้น

1193
00:43:10,340 --> 00:43:11,830
โอเมก้าของ n

1194
00:43:11,830 --> 00:43:14,450
และเราสามารถมองไปที่
คนอื่น ๆ เหล่านี้เช่นกัน

1195
00:43:14,450 --> 00:43:17,990
ดังนั้นลองมาดูอย่างรวดเร็ว
ที่เพียงการสร้างภาพที่นี่

1196
00:43:17,990 --> 00:43:20,790
เพื่อดูวิธีการเหล่านี้แยกตัวเอง

1197
00:43:20,790 --> 00:43:24,592
ฉันจะไปลงที่นี่เป็นแบบนี้
หน้าเว็บที่มีอยู่ในเว็บไซต์ C50 ของ

1198
00:43:24,592 --> 00:43:27,550
แต่มันจะเป็นความเจ็บปวดที่จะได้รับการทำงานที่
เพราะมันใช้เทคโนโลยีที่เรียกว่า

1199
00:43:27,550 --> 00:43:30,560
จาวาซึ่งเป็น
ส่วนใหญ่ได้รับการสนับสนุนวันนี้

1200
00:43:30,560 --> 00:43:32,730
อย่างน้อยโครเมี่ยมและอื่น ๆ บางอย่าง

1201
00:43:32,730 --> 00:43:37,070
>> และแจ้งให้เราไปข้างหน้าและเพิ่มความเร็วในการนี​​้
และอธิบายถึงสิ่งที่เกิดขึ้น

1202
00:43:37,070 --> 00:43:40,840
นี่คือการสาธิตของฟอง
เรียงลำดับขั้นตอนวิธีแรกที่เรามองไปที่

1203
00:43:40,840 --> 00:43:43,950
และมันก็สร้างภาพในการที่แต่ละ
ของเหล่านี้แสดงให้เห็นถึงบาร์จำนวน

1204
00:43:43,950 --> 00:43:45,710
ที่ใหญ่กว่าบาร์
ที่ใหญ่กว่าจำนวน

1205
00:43:45,710 --> 00:43:47,520
ที่มีขนาดเล็กบาร์
ที่มีขนาดเล็กจำนวน

1206
00:43:47,520 --> 00:43:50,353
และสิ่งที่คุณสามารถดูสายตาแม้
แม้ว่านี้จะเร็วสุด

1207
00:43:50,353 --> 00:43:53,699
เป็นที่แถบสีแดงเป็นเหมือนผม
เดินกลับมาแก้ไขปัญหา

1208
00:43:53,699 --> 00:43:56,740
คุณจะเห็นว่าองค์ประกอบที่ใหญ่กว่า
เป็นจริงเดือดปุด ๆ ขึ้นไปทางขวา

1209
00:43:56,740 --> 00:43:59,650
และองค์ประกอบที่มีขนาดเล็ก
กำลังเดือดปุด ๆ ขึ้นไปทางซ้าย

1210
00:43:59,650 --> 00:44:01,870
และลงที่นี่ถ้าเรา
จริงการมองอย่างใกล้ชิด

1211
00:44:01,870 --> 00:44:04,330
เราจริงสามารถนับ
จำนวนของการเปรียบเทียบและแลกเปลี่ยน

1212
00:44:04,330 --> 00:44:05,350
ที่ถูกสร้างขึ้นมา

1213
00:44:05,350 --> 00:44:07,360
>> แต่แทนที่จะให้ดู
ขั้นตอนวิธีการที่สอง

1214
00:44:07,360 --> 00:44:11,240
เรามองที่ก่อนหน้านี้กับเรา
อาสาสมัครเลือกการเรียงลำดับ

1215
00:44:11,240 --> 00:44:13,500
สายตาก็มี
ผลกระทบที่แตกต่างกันมาก

1216
00:44:13,500 --> 00:44:16,820
แต่มันเป็นอีกครั้งที่ใช้งานง่ายมากใน
ที่เราเลือกต่อไปให้น้อยที่สุด

1217
00:44:16,820 --> 00:44:18,660
องค์ประกอบและเราได้น้อยที่โชคดี

1218
00:44:18,660 --> 00:44:20,110
ที่รู้สึกพื้นฐานได้เร็วขึ้น

1219
00:44:20,110 --> 00:44:22,840
แต่ถ้าเราวิ่งนี้อีกครั้งและอีกครั้ง
และอีกครั้งที่มีจำนวนมากของปัจจัยการผลิต

1220
00:44:22,840 --> 00:44:26,680
เราจะเห็นว่ามันเป็นจริง
ยังคงอยู่ในโอใหญ่ของ n ยกกำลังสอง

1221
00:44:26,680 --> 00:44:29,920
>> ให้ทำอย่างใดอย่างหนึ่งสุดท้าย
ที่นี่จัดเรียงแทรก

1222
00:44:29,920 --> 00:44:33,180
ซึ่งเป็นขั้นตอนวิธีที่สาม
เรามองที่และการเรียกคืน

1223
00:44:33,180 --> 00:44:36,700
ว่าคนนี้เกี่ยวข้องกับ
เป็นองค์ประกอบที่จะพบพวกเขา

1224
00:44:36,700 --> 00:44:39,290
แต่ก็อาจจะมีการเปลี่ยนแปลง
สิ่งที่มากกว่าที่จะทำให้ห้องพัก

1225
00:44:39,290 --> 00:44:41,660
ใส่องค์ประกอบที่พวกเขาอยู่

1226
00:44:41,660 --> 00:44:45,330
>> และนี้ก็จบลงด้วยการให้
ผลสุดท้าย. ตอนนี้ทั้งสามของคนเหล่านั้น

1227
00:44:45,330 --> 00:44:46,490
รู้สึกอย่างรวดเร็ว

1228
00:44:46,490 --> 00:44:48,740
และแน่นอนฉันวิ่งพวกเขา
ที่คลิปที่ดีงาม

1229
00:44:48,740 --> 00:44:52,510
แต่พื้นฐานที่พวกเขากำลังทั้งหมด
ที่น่ากลัวสวยที่จะซื่อสัตย์

1230
00:44:52,510 --> 00:44:56,960
ทุกขั้นตอนวิธีการเหล่านี้ป่านนี้
การทำงานใน O ใหญ่ของ n ที่ยกกำลังสอง

1231
00:44:56,960 --> 00:44:59,270
ใช้เวลาไม่น้อยของ
เวลาในการทำงานในท้ายที่สุด

1232
00:44:59,270 --> 00:45:01,920
>> และแน่นอนเราสามารถมองเห็น
และความรู้สึกนี้สุดท้าย

1233
00:45:01,920 --> 00:45:04,090
ถ้าผมดึงสาธิตสามและครั้งสุดท้ายนี้

1234
00:45:04,090 --> 00:45:05,840
นี้เป็นอีกหนึ่ง
การสร้างภาพที่เกิดขึ้น

1235
00:45:05,840 --> 00:45:08,500
เพื่อแสดงให้เห็นการจัดเรียงฟองด้านซ้าย
การเรียงลำดับการเลือกที่อยู่ตรงกลาง

1236
00:45:08,500 --> 00:45:13,410
และสิ่งที่เป็นหนึ่งในของเรา
มือยกข้อเสนอแนะก่อนหน้านี้

1237
00:45:13,410 --> 00:45:15,020
ผสานการจัดเรียงที่อยู่ด้านขวา

1238
00:45:15,020 --> 00:45:16,937
แบ่งและพิชิต
กลยุทธ์ด้านขวา

1239
00:45:16,937 --> 00:45:19,520
และนั่นคือในความเป็นจริงสิ่งที่เรากำลัง
จะไปดูที่ในวันพุธที่

1240
00:45:19,520 --> 00:45:21,990
แต่เวลาให้ของเหล่านี้ในการทำงานแบบขนาน

1241
00:45:21,990 --> 00:45:26,765
มันเป็นประมาณจำนวนเดียวกันของ
องค์ประกอบทั้งหมดที่ทำงานในเวลาเดียวกัน

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
การจัดเรียงฟองเทียบกับการเลือก
การเรียงลำดับเทียบกับการจัดเรียงผสาน

1244
00:45:34,440 --> 00:45:36,760
>> ตอนนี้พวกเขากำลังทั้งหมดที่ทำงาน
ในทางทฤษฎีในเวลาเดียวกัน

1245
00:45:36,760 --> 00:45:39,830
ซีพียูทำงานที่
ความเร็วเท่ากัน แต่คุณ

1246
00:45:39,830 --> 00:45:44,014
สามารถรู้สึกว่าน่าเบื่อนี้
อย่างรวดเร็วจะกลายเป็น

1247
00:45:44,014 --> 00:45:45,930
และเพียงแค่วิธีการที่รวดเร็วเมื่อ
เราฉีดบิตของสัปดาห์

1248
00:45:45,930 --> 00:45:49,330
ขั้นตอนวิธีการของศูนย์สามารถ
เราเร็วขึ้น

1249
00:45:49,330 --> 00:45:51,760
>> และตอนนี้เรามาเปรียบเทียบ
เหล่านี้ในรูปแบบหนึ่งที่ผ่านมา

1250
00:45:51,760 --> 00:45:55,710
ฉันจะไปข้างหน้า
ไปยังเว็บไซต์ของ CS50 ที่

1251
00:45:55,710 --> 00:45:59,020
เรามีการเชื่อมโยงนี้สุดท้ายสำหรับวันนี้
ที่มีคนบนอินเทอร์เน็ต

1252
00:45:59,020 --> 00:46:03,960
กรุณาใส่กันวิดีโอที่
จับเรียงลำดับสิ่งที่แตกต่างกัน

1253
00:46:03,960 --> 00:46:07,510
อัลกอริทึมเสียงเหมือน

1254
00:46:07,510 --> 00:46:09,577
นี่คือการจัดเรียงแทรก

1255
00:46:09,577 --> 00:46:12,072
>> [beeping]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> ด้วยเหตุนี้คุณกำลังใช้ความถี่
ขึ้นอยู่กับความสูงของบาร์บาร์

1258
00:46:16,850 --> 00:46:19,826
นี้จะเรียงลำดับฟอง

1259
00:46:19,826 --> 00:46:21,822
>> [เหย beeping]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> ขึ้นมาต่อไป is-- มา
ขึ้นต่อไปจัดเรียงเลือก is--,

1262
00:46:45,774 --> 00:46:48,820
อีกครั้งที่เราเลือก
องค์ประกอบที่เล็กที่สุดต่อไป

1263
00:46:48,820 --> 00:46:51,820
และเราสามารถดูได้ที่เพิ่มขึ้น
จากซ้ายไปขวา

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> ผสานเรียงลำดับผู้ชนะของเราจึงห่างไกลในวันนี้

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
ขอให้สังเกตว่ามันสิ่งหาร
เข้า [ไม่ได้ยิน] ครึ่งและไตรมาส

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
การเรียงลำดับคำพังเพยที่เราไม่ได้
พูดคุยเกี่ยวกับการมองเห็นและสร้าง

1270
00:47:21,660 --> 00:47:24,450
และ audally บิตของการเป็น
รูปร่างที่แตกต่างกันและเสียง

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
จะกลับมา
ทำความสะอาดสิ่งขึ้น

1273
00:47:30,160 --> 00:47:32,230
ยังตรวจสอบ heapsort
บนเว็บไซต์ของผู้ชายคนนี้

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> และที่มัน

1276
00:47:36,810 --> 00:47:38,210
เราจะเห็นคุณในครั้งต่อไป

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> [whooshing และดนตรี]

1279
00:47:48,334 --> 00:50:24,839