1
00:00:00,000 --> 00:00:11,100
>> [เล่นเพลง]

2
00:00:11,100 --> 00:00:11,490
>> เดวิดเจลัน: ทั้งหมดขวา

3
00:00:11,490 --> 00:00:12,170
ดังนั้นยินดีต้อนรับกลับ

4
00:00:12,170 --> 00:00:15,180
นี่คือ CS50 และเป็น
ในตอนท้ายของสัปดาห์ที่สาม

5
00:00:15,180 --> 00:00:17,770
>> ดังนั้นจำในหลายสัปดาห์ที่ผ่านมา
เราได้รับการใช้จ่ายไม่น้อย

6
00:00:17,770 --> 00:00:20,820
เวลาใน C, การเขียนโปรแกรมบนไวยากรณ์

7
00:00:20,820 --> 00:00:24,680
และก็ค่อนข้างปกติถ้าคุณยังคง
ดิ้นรนกับปัญหาชุดที่ 2 จะ

8
00:00:24,680 --> 00:00:25,950
ทุบหัวของคุณกับผนัง

9
00:00:25,950 --> 00:00:28,310
มันเป็นความลับที่ดูข้อความผิดพลาด
และข้อบกพร่องที่คุณ

10
00:00:28,310 --> 00:00:29,220
ไม่สามารถค่อนข้างไล่ลง

11
00:00:29,220 --> 00:00:32,310
เพราะมั่นใจว่าในเวลาเพียง
เวลาไม่กี่สัปดาห์ 'คุณจะมองย้อนกลับไป

12
00:00:32,310 --> 00:00:35,930
สิ่งที่ชอบซีซาร์และ [? V-genair,?]
อาจจะแตกและ

13
00:00:35,930 --> 00:00:40,050
ตระหนักถึงไกลแค่ไหนที่คุณได้มา
ในช่วงเวลาสั้นของเวลา

14
00:00:40,050 --> 00:00:43,670
ดังนั้นหากที่ปลอบใจใด ๆ
แขวนอยู่ในนั้นสำหรับตอนนี้

15
00:00:43,670 --> 00:00:46,610
>> วันนี้แม้ว่าเราจะเริ่มการเปลี่ยนแปลง
ไปสู่​​สิ่งที่ระดับที่สูงขึ้น

16
00:00:46,610 --> 00:00:49,820
และเราเริ่มที่จะได้รับอยู่ที่
พวกคุณรู้วิธีการเขียนโปรแกรมหรือ

17
00:00:49,820 --> 00:00:52,090
อย่างน้อยจุดเริ่มต้นของ
ระดับความสะดวกสบายที่

18
00:00:52,090 --> 00:00:56,520
และเราจะเริ่มต้นที่จะต้องพิจารณาวิธีการที่เราสามารถ
ไปเกี่ยวกับการออกแบบโปรแกรมเพิ่มเติม

19
00:00:56,520 --> 00:00:57,440
มีประสิทธิภาพ

20
00:00:57,440 --> 00:01:01,090
วิธีที่เราสามารถไปเกี่ยวกับการเพิ่มประสิทธิภาพ
ประสิทธิภาพของอัลกอริทึมของเราและ

21
00:01:01,090 --> 00:01:03,110
โดยทั่วไปการแก้ปัญหามากขึ้น
ปัญหาที่น่าสนใจ

22
00:01:03,110 --> 00:01:06,850
และเริ่มที่จะได้รับอยู่ที่
ถ้าเราต้องการที่จะเราสามารถรหัสใด ๆ

23
00:01:06,850 --> 00:01:08,350
จากตัวอย่างที่เรามีในใจ

24
00:01:08,350 --> 00:01:11,430
ดังนั้นวันนี้เราไม่ได้สัมผัสแป้นพิมพ์
สำหรับรูปแบบของรหัสใด ๆ

25
00:01:11,430 --> 00:01:15,150
มันจะเป็นระดับที่สูงมากและ
ท้ายที่สุดเกี่ยวกับการแก้ปัญหา

26
00:01:15,150 --> 00:01:20,490
>> เพื่อที่จะได้รับไปยังจุดที่ให้ฉันเสนอ
ว่าต่อไปนี้เจ็ด

27
00:01:20,490 --> 00:01:24,290
รูปสี่เหลี่ยมเป็นตัวแทนของเจ็ดประตูหลัง
ซึ่งเป็นทั้งกลุ่ม

28
00:01:24,290 --> 00:01:26,340
ตัวเลขในหมู่ซึ่งเป็นจำนวน 50

29
00:01:26,340 --> 00:01:30,470
ผมขอโครงการนี​​้เกี่ยวกับเรื่องนี้
หน้าจอที่นี่เช่นกัน

30
00:01:30,470 --> 00:01:36,770
และเสนอที่เราต้องการอาสาสมัคร
ช่วยหาฉันหมายเลขในด้านหน้าของ

31
00:01:36,770 --> 00:01:38,140
อินเทอร์เน็ตที่นี่เพื่อดู

32
00:01:38,140 --> 00:01:40,755
มาขึ้นในสีชมพู

33
00:01:40,755 --> 00:01:43,050
ทั้งหมดขวา

34
00:01:43,050 --> 00:01:43,930
คุณชื่ออะไร?

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER: [ได้ยิน]

36
00:01:44,850 --> 00:01:45,170
>> เดวิดเจลัน: ขอโทษ?

37
00:01:45,170 --> 00:01:45,860
>> JENNIFER: เจนนิเฟอร์

38
00:01:45,860 --> 00:01:46,390
>> เดวิดเจลัน: เจนนิเฟอร์

39
00:01:46,390 --> 00:01:46,980
เจนนิเฟอร์ทั้งหมดขวา

40
00:01:46,980 --> 00:01:47,630
Nice to meet you

41
00:01:47,630 --> 00:01:48,370
มาขึ้น

42
00:01:48,370 --> 00:01:52,430
ดังนั้นเหล่านี้ที่นี่มีเจ็ดประตูและสิ่งที่
ฉันต้องการให้คุณสามารถทำเพื่อเราที่นี่

43
00:01:52,430 --> 00:01:56,560
ในด้านหน้าของทั้งเพื่อนร่วมชั้นของคุณ
คือหาให้เราทราบหมายเลข 50

44
00:01:56,560 --> 00:02:00,860
เพื่อหาจำนวนคุณสามารถแอบมองอยู่ข้างหลัง
ใด ๆ ของประตูเหล่านี้โดยเพียงแค่แตะ

45
00:02:00,860 --> 00:02:03,030
ที่หนึ่งของประตูและมัน
จะเปิดเผยจำนวนของ

46
00:02:03,030 --> 00:02:06,080
และขอดูวิธีการอย่างรวดเร็วคุณ
เราสามารถหาหมายเลขที่ 50

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50

53
00:02:16,530 --> 00:02:17,350
ทำได้อย่างดี

54
00:02:17,350 --> 00:02:18,040
ทั้งหมดขวา

55
00:02:18,040 --> 00:02:19,906
ตบมือให้เจนนิเฟอร์

56
00:02:19,906 --> 00:02:21,530
>> [APPLAUSE]

57
00:02:21,530 --> 00:02:22,320
>> ทั้งหมดขวา

58
00:02:22,320 --> 00:02:25,254
ดังนั้นสิ่งที่กลยุทธ์ของคุณเป็น
ค้นหาหมายเลข 50?

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER: อืมผมคิดว่าบางทีถ้า -

60
00:02:27,222 --> 00:02:27,714
[เงียบสงัด]

61
00:02:27,714 --> 00:02:28,206
>> เดวิดเจลัน: โอ้

62
00:02:28,206 --> 00:02:29,630
ให้มันเป็นหนึ่งในสอง

63
00:02:29,630 --> 00:02:32,420
ดังนั้นกลยุทธ์ของคุณเป็น
ค้นหาหมายเลข 50?

64
00:02:32,420 --> 00:02:34,760
>> JENNIFER: ดังนั้นฉันเพียงแค่เริ่มต้นที่
จุดเริ่มต้นที่จะเห็นสิ่งที่หมายเลขแรก

65
00:02:34,760 --> 00:02:38,590
แล้วก็ผมคิดว่าบางทีถ้า
พวกเขากำลังเรียงลำดับฉันเพิ่งจะเก็บ

66
00:02:38,590 --> 00:02:39,970
แตะที่สูงขึ้น?

67
00:02:39,970 --> 00:02:40,140
>> เดวิดเจลัน: ตกลง

68
00:02:40,140 --> 00:02:42,910
และเราดูเหมือนจะได้พบ
ว่าจะเป็นกรณี

69
00:02:42,910 --> 00:02:45,670
ถึงแม้ว่าเราจะมากลับชั้นเปลือก
เพียงเล็กน้อยและคุณต้องการที่จะไป

70
00:02:45,670 --> 00:02:47,640
ข้างหน้าและเผยให้เห็นประตูอื่น ๆ
คุณอาจจะได้เลือก?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER: โอ้ที่รัก

73
00:02:51,712 --> 00:02:53,128
>> เดวิดเจลัน: อ่า

74
00:02:53,128 --> 00:02:54,280
>> JENNIFER: ดังนั้นฉันเพียงแค่มีโชคดี

75
00:02:54,280 --> 00:02:55,270
>> เดวิดเจลัน: คุณโชคดี

76
00:02:55,270 --> 00:02:55,710
ทั้งหมดขวา

77
00:02:55,710 --> 00:02:56,795
ดังนั้นไม่เลว

78
00:02:56,795 --> 00:02:58,750
แต่ที่น่าสนใจ
เข้าใจใช่มั้ย?

79
00:02:58,750 --> 00:03:01,870
ถ้าคุณคิดและคุณได้รับ,
แน่นอนบิตโชคดีมี

80
00:03:01,870 --> 00:03:05,350
แต่ถ้าคุณคิดว่าตัวเลขที่เป็น
เรียงลำดับที่คุณสามารถจะแม่นยำมากขึ้น

81
00:03:05,350 --> 00:03:08,750
เป็นวิธีการที่มีอิทธิพลต่อ
พฤติกรรมของคุณ?

82
00:03:08,750 --> 00:03:11,715
>> JENNIFER: ดังนั้นหากพวกเขาได้รับการเรียงลำดับผม
คิดว่าบางทีที่เล็กที่สุดไปหามากที่สุด

83
00:03:11,715 --> 00:03:11,970
>> เดวิดเจลัน: ตกลง

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER: หรือถ้านี้จบลงด้วยการ
ใหญ่จริงๆแล้วที่ใหญ่ที่สุดไปหาน้อยที่สุด

85
00:03:15,260 --> 00:03:15,540
>> เดวิดเจลัน: ตกลง

86
00:03:15,540 --> 00:03:18,170
ดังนั้นที่ใหญ่ที่สุดไปหาน้อยที่สุดหรือ
ที่เล็กที่สุดไปหามากที่สุด

87
00:03:18,170 --> 00:03:21,990
แต่ให้ฉันเสนอสมมติว่าคุณมี
อากาศที่โชคร้ายและคิดว่าพวกเขา

88
00:03:21,990 --> 00:03:26,840
ไม่ได้ในความเป็นจริงเรียงลำดับของวิธีการหลาย
คุณอาจประตูเหล่านั้นได้มีการแอบมอง

89
00:03:26,840 --> 00:03:28,590
หลังในกรณีที่เลวร้ายที่สุดที่?

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER: ทั้งหมดของพวกเขา

91
00:03:29,860 --> 00:03:30,420
>> เดวิดเจลัน: ทั้งหมดของพวกเขา

92
00:03:30,420 --> 00:03:31,740
เพื่อขอพูดคุยที่เป็น n

93
00:03:31,740 --> 00:03:34,790
มีเกิดขึ้นเป็น 7 แต่ช่วยให้มากขึ้น
โดยทั่วไปว่ามีประตู n เมื่อ

94
00:03:34,790 --> 00:03:35,650
หน้าจอที่นี่

95
00:03:35,650 --> 00:03:40,110
ดังนั้นในกรณีที่เลวร้ายที่สุดที่คุณจะได้
ที่จะมองหาที่อยู่เบื้องหลัง 7 ประตูหรือประตู n

96
00:03:40,110 --> 00:03:44,140
และอื่น ๆ นี้จริงๆคือมันบิตของ
โชควันนี้ แต่จริง ๆ แล้วมันเส้น

97
00:03:44,140 --> 00:03:46,440
อัลกอริทึมของแปลกแม้ว่าคุณ
เป็นชนิดของการกระโดดไปรอบ ๆ

98
00:03:46,440 --> 00:03:47,080
ที่ยุติธรรมหรือไม่

99
00:03:47,080 --> 00:03:47,500
>> JENNIFER: ใช่

100
00:03:47,500 --> 00:03:50,000
>> เดวิดเจลัน: ดีให้ฉันดูว่าของคุณ
กลยุทธ์การเปลี่ยนแปลงถ้าเราไปสู่​​การ

101
00:03:50,000 --> 00:03:52,190
ตัวอย่างที่สองของเราที่นี่ด้วย
7 ประตูที่แตกต่างกัน

102
00:03:52,190 --> 00:03:55,240
ตัวเลขเดียวกัน แต่นี้
เวลาที่พวกเขาจะถูกจัดเรียง

103
00:03:55,240 --> 00:03:58,350
กลยุทธ์ที่นี่จะเป็นของคุณคืออะไร,
พยายามที่จะนำออกมาจากใจของคุณคืออะไร

104
00:03:58,350 --> 00:03:59,310
หมายเลขอื่น ๆ ได้ -

105
00:03:59,310 --> 00:03:59,930
>> JENNIFER: ตกลง

106
00:03:59,930 --> 00:04:02,290
>> เดวิดเจลัน: - ก่อนหน้านี้?

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER: เริ่มต้นให้
กับครั้งแรกหนึ่ง

108
00:04:03,180 --> 00:04:03,540
>> เดวิดเจลัน: ทั้งหมดขวา

109
00:04:03,540 --> 00:04:05,190
เริ่มต้นด้วยหนึ่งครั้งแรก

110
00:04:05,190 --> 00:04:05,960
4

111
00:04:05,960 --> 00:04:08,810
ตอนนี้ที่คุณจะไปและทำไม

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER: 4 มีขนาดเล็กจริงๆ

113
00:04:10,040 --> 00:04:12,500
ดังนั้นหากพวกเขากำลังจัดเรียงอาจจะมีขนาดเล็กที่สุด
ที่ใหญ่ที่สุดที่ควรจะเป็น

114
00:04:12,500 --> 00:04:13,290
เป็นสองนั้นและ -

115
00:04:13,290 --> 00:04:13,670
>> เดวิดเจลัน: ตกลง

116
00:04:13,670 --> 00:04:15,990
ลองดูที่คุณคิดว่า?

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER: ลองครั้งหนึ่ง

118
00:04:19,050 --> 00:04:19,500
ไนซ์

119
00:04:19,500 --> 00:04:20,880
>> เดวิดเจลัน: ทำอย่างมาก

120
00:04:20,880 --> 00:04:21,860
ทั้งหมดขวา

121
00:04:21,860 --> 00:04:23,010
>> [APPLAUSE]

122
00:04:23,010 --> 00:04:24,310
>> เดวิดเจลัน: ตกลง

123
00:04:24,310 --> 00:04:26,790
ดังนั้นคุณจริงการทำเช่นนี้
น่ากลัวเพราะคุณ

124
00:04:26,790 --> 00:04:27,700
ทำมันได้เป็นอย่างดี

125
00:04:27,700 --> 00:04:31,150
ซึ่งจะทำให้เราไม่สามารถที่จะ
ทำให้บางจุด

126
00:04:31,150 --> 00:04:32,565
ดังนั้นขอพยายามที่จะย้อนกลับที่นี่

127
00:04:32,565 --> 00:04:34,560
>> JENNIFER: ตกลง

128
00:04:34,560 --> 00:04:35,980
>> เดวิดเจลัน: ดีมาก
ทำกระนั้น

129
00:04:35,980 --> 00:04:39,060
ดังนั้นคุณเริ่มต้นที่จุดเริ่มต้น
ที่คุณเห็นว่ามันเป็น 4 แล้วคุณ

130
00:04:39,060 --> 00:04:40,240
ย้ายไปยังจุดสิ้นสุด

131
00:04:40,240 --> 00:04:42,320
แต่สมมติว่าคุณไม่ได้รับโชคดี
มีและคิดว่า 50

132
00:04:42,320 --> 00:04:42,890
เป็นที่อื่น

133
00:04:42,890 --> 00:04:46,190
สิ่งที่ขั้นตอนที่สามของคุณได้รับ?

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER: กลับไปที่จุดเริ่มต้น

135
00:04:47,680 --> 00:04:48,320
>> เดวิดเจลัน: กลับไป
ที่จุดเริ่มต้น

136
00:04:48,320 --> 00:04:51,320
ตกลงดังนั้นคุณจะได้สัมผัส
ประตูนี้ซึ่งเป็น 8

137
00:04:51,320 --> 00:04:51,660
ทั้งหมดขวา

138
00:04:51,660 --> 00:04:52,650
เพื่อให้ไม่ 50

139
00:04:52,650 --> 00:04:55,380
ที่ที่คุณจะได้ดูต่อไปหรือไม่

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER: ถ้าฉันไม่ได้
รู้ว่าพวกเขาเรียง

141
00:04:56,720 --> 00:04:57,005
>> เดวิดเจลัน: ถูกต้อง

142
00:04:57,005 --> 00:04:58,490
ดีถ้าคุณไม่ได้รู้ว่า
พวกเขาจะถูกจัดเรียง -

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER: โอ้ไม่ทราบว่าใช่

144
00:04:58,700 --> 00:05:00,910
>> เดวิดเจลัน: - แต่คุณไม่ได้
ทราบว่าเป็น 50 หรือยัง?

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER: เพียงแค่เก็บไป

146
00:05:01,785 --> 00:05:02,130
>> เดวิดเจลัน: ทั้งหมดขวา

147
00:05:02,130 --> 00:05:02,520
ตกลง

148
00:05:02,520 --> 00:05:03,800
เก็บไป

149
00:05:03,800 --> 00:05:05,270
ตกลงว่าผมสามารถทำงานร่วมกับ

150
00:05:05,270 --> 00:05:05,610
>> JENNIFER: ตกลง

151
00:05:05,610 --> 00:05:07,210
>> เดวิดเจลัน: ตอนนี้ถ้าคุณกันเพียง
จะให้ไปอะไรของคุณ

152
00:05:07,210 --> 00:05:09,680
อัลกอริทึมจุติได้รับการสนับสนุนเป็น

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER: เชิงเส้น -

154
00:05:10,740 --> 00:05:11,820
>> เดวิดเจลัน: มันเป็นชนิดของเส้นตรง

155
00:05:11,820 --> 00:05:13,480
แต่ให้ฉันเสนอให้
ฉันวางในจุดที่

156
00:05:13,480 --> 00:05:14,900
ให้ฉันรีเฟรชหน้า

157
00:05:14,900 --> 00:05:17,120
หมายเลขเดียวกันการจัดเรียงเดียวกัน
ประตูเดียวกัน

158
00:05:17,120 --> 00:05:21,350
แต่คิดว่ากลับไปในวันนั้นเป็นครั้งแรกใน
ชั้นเมื่อเราฉีกสมุดโทรศัพท์ใน

159
00:05:21,350 --> 00:05:25,480
ครึ่งเรียงลำดับจากและสิ่งที่เป็น
กลยุทธ์ของเรามี?

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER: เริ่มที่ตรงกลาง

161
00:05:26,450 --> 00:05:26,690
>> เดวิดเจลัน: ตกลง

162
00:05:26,690 --> 00:05:27,610
เพื่อเริ่มต้นที่ตรงกลาง

163
00:05:27,610 --> 00:05:28,790
ดังนั้นขอไปข้างหน้าและจำลองว่า

164
00:05:28,790 --> 00:05:30,720
เริ่มที่ตรงกลางโดย
เผยให้เห็นประตูที่

165
00:05:30,720 --> 00:05:31,660
ดังนั้นหมายเลข 16

166
00:05:31,660 --> 00:05:35,290
ดังนั้นคนที่แต่งตัวประหลาดที่แข็งแกร่งจะได้ในสิ่งที่ทำ
ที่ฉีกสมุดโทรศัพท์ในช่วงครึ่งปี,

167
00:05:35,290 --> 00:05:38,450
จะได้รับการคาดเดาต่อไปหรือไม่

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER: ไปในช่วงครึ่งปีนี้

169
00:05:39,400 --> 00:05:41,700
>> เดวิดเจลัน: และทำไมไปทางขวา?

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER: หากพวกเขาจัดเรียงของที่เล็กที่สุด
ที่ใหญ่ที่สุดแล้วควรจะเป็น 50

171
00:05:43,900 --> 00:05:44,720
ในตอนท้ายว่า

172
00:05:44,720 --> 00:05:44,920
>> เดวิดเจลัน: ดี

173
00:05:44,920 --> 00:05:45,390
ที่เหมาะสมโดยสิ้นเชิง

174
00:05:45,390 --> 00:05:48,380
ดังนั้นเช่นสมุดโทรศัพท์ที่คุณจะไป
ขวาตรงข้ามกับไปทางซ้าย แต่ที่นี่

175
00:05:48,380 --> 00:05:49,500
Takeaway ที่สำคัญคือ

176
00:05:49,500 --> 00:05:53,930
ขณะนี้คุณสามารถทิ้งหรือฉีก,
ครึ่งหนึ่งของปัญหานี้ออกจากคุณไม่ได้

177
00:05:53,930 --> 00:05:55,970
7 ประตู แต่จริงๆมีเพียง 3

178
00:05:55,970 --> 00:05:57,870
ซึ่งเป็นประมาณครึ่งหนึ่งของ
ขนาดของปัญหา

179
00:05:57,870 --> 00:05:58,350
ทั้งหมดขวา

180
00:05:58,350 --> 00:06:01,890
ดังนั้นตอนนี้สิ่งที่คุณจะต้อง
หลังจากที่คุณทำไปทางขวา?

181
00:06:01,890 --> 00:06:05,870
>> JENNIFER: 16 ดังนั้นยังคงมีขนาดเล็กสวย,
เมื่อเทียบกับ 50 ดังนั้นบางทีฉันจะพยายาม,

182
00:06:05,870 --> 00:06:06,700
เช่นนี้เป็นหนึ่งใน

183
00:06:06,700 --> 00:06:07,890
>> เดวิดเจลัน: ทั้งหมดขวา

184
00:06:07,890 --> 00:06:08,720
42

185
00:06:08,720 --> 00:06:10,830
ทั้งหมดขวาดังนั้นตอนนี้สิ่งที่เป็นของคุณ
สัญชาตญาณบอกคุณ?

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER: ฉันสามารถโยนออกไป
นี้แล้วก็ -

187
00:06:12,100 --> 00:06:12,360
>> เดวิดเจลัน: ตกลง

188
00:06:12,360 --> 00:06:14,212
ดีคุณสามารถโยนออกไป
ซีกซ้ายมี

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER: - เลือกหนึ่งนี้

190
00:06:14,890 --> 00:06:15,530
>> เดวิดเจลัน: และขวา

191
00:06:15,530 --> 00:06:15,760
>> JENNIFER: ใช่

192
00:06:15,760 --> 00:06:17,820
>> ลันเดวิดเจ: ดังนั้นแม้ว่ามันเป็นเรื่องยาก
เพื่อดูบางทีเมื่อมีเพียง

193
00:06:17,820 --> 00:06:21,320
7 ประตูคิดเกี่ยวกับตอนนี้
ความสอดคล้องของ

194
00:06:21,320 --> 00:06:22,620
อัลกอริทึมที่คุณเพิ่งนำมาใช้

195
00:06:22,620 --> 00:06:24,510
ในกรณีที่ก่อนหน้านี้ที่คุณคิดว่า
ได้รับโชคดีซึ่งเป็นที่ดี

196
00:06:24,510 --> 00:06:26,540
แต่คุณไม่ใช้การแก้ปัญหา,
ผมจะบอกว่า

197
00:06:26,540 --> 00:06:29,150
ที่คุณใช้ในการเรียงลำดับของสัญชาตญาณของคุณและ
รู้ว่ามันเรียงลำดับถ้ามันสวย

198
00:06:29,150 --> 00:06:31,600
ขนาดเล็กที่จุดเริ่มต้นเห็นได้ชัดว่าเราได้
ได้ไปขึ้นไปทางขวา

199
00:06:31,600 --> 00:06:34,990
แต่ในความรู้สึกบางอย่างคุณโชคดี,
เพราะบางทีมันอาจจะเป็นจำนวน 100,

200
00:06:34,990 --> 00:06:36,220
และอาจจะ 50 ได้มากขึ้นในช่วงกลาง

201
00:06:36,220 --> 00:06:37,910
บางที 50 ก็ยิ่งกว่าที่นี่

202
00:06:37,910 --> 00:06:40,960
>> แต่สิ่งที่คุณทำน้อยแตกต่างกัน
เวลานี้คุณได้ทำสิ่งเดียวกัน

203
00:06:40,960 --> 00:06:42,150
ครั้งแล้วครั้งเล่า

204
00:06:42,150 --> 00:06:45,310
และฉันจะยืนยันว่าสิ่งที่คุณเพิ่ง
ไม่แม้จะได้รับอิทธิพลจากโทรศัพท์

205
00:06:45,310 --> 00:06:48,100
หนังสือเช่นเป็นบางสิ่งบางอย่างมาก
ขั้นตอนมากขึ้นและมาก

206
00:06:48,100 --> 00:06:49,930
พิเศษน้อยดาด

207
00:06:49,930 --> 00:06:51,620
มากน้อยสัญชาตญาณ

208
00:06:51,620 --> 00:06:57,160
ดังนั้นในตอนท้ายของวันวิธีการที่จะ
ที่คุณอธิบายประสิทธิภาพของ

209
00:06:57,160 --> 00:07:00,530
อัลกอริทึมแรกที่คุณไป
จากซ้ายไปขวาเมื่อเทียบกับ

210
00:07:00,530 --> 00:07:03,430
อัลกอริทึมที่สองที่นี่?

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER: หนึ่งนี้ควรเช่นอาจจะ
ลดลงครึ่งหนึ่งเวลาหรือมากยิ่งขึ้นครับ

212
00:07:06,460 --> 00:07:07,320
>> เดวิดเจลัน: ตกลงอาจจะมากยิ่งขึ้น

213
00:07:07,320 --> 00:07:10,150
ให้ผลักดันหนักขึ้นเล็กน้อยว่า

214
00:07:10,150 --> 00:07:13,030
อะไรจริงๆถ้าเรายังคงนี้
ตรรกะเราแน่นอนลดลงครึ่งหนึ่ง

215
00:07:13,030 --> 00:07:15,830
ใช้เวลาอยู่กับขั้นตอนวิธีการที่สองนี้
โดยการขว้างปาไปครึ่งหนึ่งของ

216
00:07:15,830 --> 00:07:18,470
ตัวเลข แต่เราทำอะไรต่อไปเมื่อ
ซ้ำเมื่อเจนนิเฟอร์เปิดเผย

217
00:07:18,470 --> 00:07:20,615
ตัวเลขที่สอง?

218
00:07:20,615 --> 00:07:22,830
>> เราลดลงครึ่งหนึ่งของตัวเลขที่ประตูอีกครั้ง

219
00:07:22,830 --> 00:07:25,270
และแล้วสิ่งที่พวกเราทำหลังจากนั้นถ้า
มีประตูมากขึ้นที่จะเล่นกับเขา?

220
00:07:25,270 --> 00:07:27,520
เราก็จะลดลงครึ่งหนึ่งพวกเขาและอีกครั้ง
และอีกครั้งและอีกครั้ง

221
00:07:27,520 --> 00:07:30,420
และนี่ก็เป็นเช่นเดียวกับพวกคุณทั้งหมด
ยืนขึ้นที่สัปดาห์แรกของเดือน

222
00:07:30,420 --> 00:07:33,000
ชั้นครึ่งของคุณนั่งลงครึ่งหนึ่ง
ของคุณนั่งลงครึ่งหนึ่งของคุณ

223
00:07:33,000 --> 00:07:35,440
นั่งลงจนเป็นหนึ่งเดียว
จิตวิญญาณก็กำลังยืนอยู่

224
00:07:35,440 --> 00:07:39,050
และเราบอกว่าเวลาทำงานของ
ว่าจำนวนของขั้นตอนที่จะเอาเป็น

225
00:07:39,050 --> 00:07:40,430
โดยคำสั่งของสิ่งที่?

226
00:07:40,430 --> 00:07:41,230
>> 1 SPEAKER: [ได้ยิน]

227
00:07:41,230 --> 00:07:43,970
>> เดวิดเจลัน: log ฐานดังนั้น 2 ของ n
หรือเพียงแค่เพิ่มขึ้นเพียงเข้าสู่ระบบของ n

228
00:07:43,970 --> 00:07:45,060
ดังนั้นบางสิ่งบางอย่างเกี่ยวกับลอการิทึม

229
00:07:45,060 --> 00:07:48,380
และกราฟที่ไม่เป็นเส้นตรง
ที่เพิ่งได้เลวร้ายลงและแย่กว่านั้นก็คือ

230
00:07:48,380 --> 00:07:52,490
นี้เส้นโค้งที่น่าสนใจที่ไม่ได้
ได้รับที่ไม่ดีดังนั้นเมื่อเวลาผ่านไป

231
00:07:52,490 --> 00:07:53,910
ดังนั้นขอยึดมั่นในความคิดนี้

232
00:07:53,910 --> 00:07:54,690
ขอขอบคุณเจนนิเฟอร์

233
00:07:54,690 --> 00:07:56,150
ขอบคุณมากสำหรับการมาขึ้น

234
00:07:56,150 --> 00:07:57,400
และหนึ่งวินาที

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
ไม่มีโคมไฟโต๊ะในวันนี้ แต่เรา
จะมี CS50 ลูกความเครียด

237
00:08:02,925 --> 00:08:03,420
>> JENNIFER: พี่

238
00:08:03,420 --> 00:08:04,410
>> เดวิดเจลัน: ขวาทั้งหมดที่นี่

239
00:08:04,410 --> 00:08:06,545
ขอบคุณสำหรับการที่เกิดขึ้น
ความเครียดขึ้นที่นี่

240
00:08:06,545 --> 00:08:07,350
ทั้งหมดขวา

241
00:08:07,350 --> 00:08:10,620
ดังนั้นขอดูว่าเราไม่สามารถในขณะนี้
เป็นระเบียบแบบแผนนี้อีกเล็กน้อย

242
00:08:10,620 --> 00:08:14,820
ดังนั้นอีกครั้งสิ่งที่เราก็ไม่ได้เป็น
เป็นหลักสิ่งเดียวกับที่เราทำ

243
00:08:14,820 --> 00:08:16,660
ในสัปดาห์แรกที่

244
00:08:16,660 --> 00:08:23,780
แต่แทนที่จะมีเพียงปลายเส้น
อัลกอริทึมที่เราวาด

245
00:08:23,780 --> 00:08:27,210
ก่อนหน้านี้เป็นเส้นตรงนี้
ด้วยเหตุนี้ถ้าเราใส่หนึ่งประตูเพิ่มเติมเกี่ยวกับการ

246
00:08:27,210 --> 00:08:29,610
หน้าจอแล้วเจนนิเฟอร์จะ
ได้มีการมองที่อาจเกิดขึ้น,

247
00:08:29,610 --> 00:08:30,600
หลังประตูอีกหนึ่ง

248
00:08:30,600 --> 00:08:33,490
ถ้าเราใส่ประตูสองบานมากขึ้นเธออาจจะมี
ที่จะมองหาที่อยู่เบื้องหลังประตูสองบานมากขึ้น

249
00:08:33,490 --> 00:08:35,990
>> และเพื่อให้มีเส้นนี้คือ
ความสัมพันธ์ระหว่างขนาดของ

250
00:08:35,990 --> 00:08:39,059
ปัญหาในการพูด, แกน x และ
ปริมาณของเวลาที่ใช้

251
00:08:39,059 --> 00:08:40,440
แก้เมื่อ y

252
00:08:40,440 --> 00:08:43,330
แต่ภาพที่ผมก็ยิ่งทำให้
ก่อนหน้านี้สายสีเขียวคือ

253
00:08:43,330 --> 00:08:45,970
สีเขียวจงใจเพราะ
มันก็รู้สึกดีขึ้น

254
00:08:45,970 --> 00:08:49,790
ในทางทฤษฎีอัลกอริทึมเมื่อเราได้มัน
กับสมุดโทรศัพท์เมื่อเราทำมัน

255
00:08:49,790 --> 00:08:52,420
กับพวกคุณนับกันและกันและ
ในกรณีที่สองเมื่อเจนนิเฟอร์เพียง

256
00:08:52,420 --> 00:08:55,250
มันขึ้นที่นี่มันเป็นจัดเรียง
จากพื้นฐานที่ดีขึ้น

257
00:08:55,250 --> 00:08:57,180
เพราะมันไม่ได้เป็นเพียงแค่สองครั้งที่รวดเร็ว

258
00:08:57,180 --> 00:08:58,870
มันไม่ได้เป็นแม้กระทั่งสี่ครั้งเป็นอย่างรวดเร็ว

259
00:08:58,870 --> 00:09:03,290
มันเป็นทั้งหมดขึ้นอยู่กับสิ่งที่
ขนาดของอินพุตเป็นว่ากี่

260
00:09:03,290 --> 00:09:05,220
ขั้นตอนท้ายที่สุดมันจะเอา

261
00:09:05,220 --> 00:09:08,040
>> และดังนั้นนี้คิดง่ายๆว่าเราทุกคนเอา
เพื่อรับกับสมุดโทรศัพท์,

262
00:09:08,040 --> 00:09:10,200
ในทำนองเดียวกันสามารถนำมาประยุกต์ใช้
ไปบางอย่างเช่นนี้

263
00:09:10,200 --> 00:09:12,380
และนี้อาจจะมีมากขึ้นเรื่อย ๆ
ที่รู้จักกันเป็นอย่างที่คุณอาจจะ

264
00:09:12,380 --> 00:09:13,940
คิดแบ่งและพิชิต

265
00:09:13,940 --> 00:09:16,390
ไม่แตกต่างจากสิ่งที่เราทำแน่นอน
กับสมุดโทรศัพท์

266
00:09:16,390 --> 00:09:18,300
>> แต่ pseudocode การเรียกคืนเป็นนี้

267
00:09:18,300 --> 00:09:21,800
ดังนั้นเราจะไม่ทำเช่นนี้อีกครั้ง แต่จำ
ช่วงสัปดาห์แรกนั้นเราทุกคนลุกขึ้นยืน

268
00:09:21,800 --> 00:09:25,140
แล้วครึ่งหนึ่งของคุณนั่งลงครึ่งหนึ่งของ
คุณนั่งลงครึ่งหนึ่งของคุณนั่งลง

269
00:09:25,140 --> 00:09:29,280
อัลกอริทึมที่ถูกนำมาใช้ใน
บิตของวิธีการโกงในการที่จะ

270
00:09:29,280 --> 00:09:32,870
ไม่ได้เพียงหนึ่งฉันนับ
โดยพื้นฐานมีประสิทธิภาพมากขึ้น

271
00:09:32,870 --> 00:09:35,830
ในกรณีที่ผมได้ใช้ประโยชน์
ทรัพยากรรอง

272
00:09:35,830 --> 00:09:39,470
เรียงจากลำโพงหลายสมองหลาย
คนสมาร์ทในหลาย ๆ

273
00:09:39,470 --> 00:09:42,740
ห้องพักได้รับการช่วยฉันได้รับจากบางสิ่งบางอย่าง
เส้นบางสิ่งบางอย่าง

274
00:09:42,740 --> 00:09:45,190
ลอการิทึมจากบางสิ่งบางอย่าง
สีแดงเป็นสีเขียวบางสิ่งบางอย่าง

275
00:09:45,190 --> 00:09:48,650
>> แต่ในกรณีนี้เจนนิเฟอร์คนเดียวก็สามารถ
ลึกซึ้งปรับปรุง

276
00:09:48,650 --> 00:09:52,370
ประสิทธิภาพการทำงานของอัลกอริทึมแรกของเธอด้วย
อีกครั้งเพียงแค่คิดหนักขึ้นเล็กน้อย

277
00:09:52,370 --> 00:09:56,650
และตอนนี้เมื่อมันมาถึงเวลาที่จะใช้
สิ่งเหล่านี้หา

278
00:09:56,650 --> 00:10:00,670
สิ่งบรรทัดของรหัสที่คุณสามารถเขียนเช่น
ที่คุณสามารถทำซ้ำได้อีกครั้งและ

279
00:10:00,670 --> 00:10:03,350
อีกครั้งและอีกครั้งที่จัดเรียงของ
ในแฟชั่นวนลูป

280
00:10:03,350 --> 00:10:06,370
เพราะคุณจะไม่ได้
หรูหราเช่นเดียวกับเจนนิเฟอร์ก็เป็นครั้งแรกที่ไป

281
00:10:06,370 --> 00:10:10,460
เพียงแค่มีทั้งกลุ่มอิฟส์และพูดว่า
อืมถ้าเป็นหมายเลขแรกคือ 4,

282
00:10:10,460 --> 00:10:11,800
ให้ฉันกระโดดไปตลอดทางจนถึงปลาย

283
00:10:11,800 --> 00:10:14,180
Ooh ถ้าจำนวนที่มีขนาดใหญ่เกินไป,
ให้ฉันย้ายพลกลับ

284
00:10:14,180 --> 00:10:15,220
ไปยังองค์ประกอบที่สอง

285
00:10:15,220 --> 00:10:18,210
คุณจะพบว่ามันเป็นไปได้มาก
ยากที่จะเป็นระเบียบแบบแผนในสิ่งที่มนุษย์เรา

286
00:10:18,210 --> 00:10:21,270
โมเมว่าเป็นที่เหมาะสมมาก
heuristics แต่คอมพิวเตอร์เป็นเพียง

287
00:10:21,270 --> 00:10:23,260
จะทำสิ่งที่คุณบอกให้ทำ

288
00:10:23,260 --> 00:10:25,280
>> ตอนนี้มีที่น่าสนใจมาก
ผลกระทบ

289
00:10:25,280 --> 00:10:29,950
กราฟนี้จะหมายถึงการจัดเรียงของในการจัดเรียงของ
เอาชนะสายตา แต่แจ้งให้ทราบที่

290
00:10:29,950 --> 00:10:32,230
เส้นตรงในกราฟนี้คืออะไร?

291
00:10:32,230 --> 00:10:35,330
ในกรณีที่กราฟเส้นตรงคือ
ที่เราเรียกว่า n?

292
00:10:35,330 --> 00:10:37,580
ดีก็เรียงลำดับของไปทางด้านล่าง
ของภาพนี้ใช่มั้ย?

293
00:10:37,580 --> 00:10:40,500
ดังนั้นสิ่งที่เราทำคือเราได้จัดเรียงของ
ซูมออกไปยังแกน x และ

294
00:10:40,500 --> 00:10:44,780
แกน y จะพยายามที่จะได้รับความรู้สึกของสิ่งที่
ประเภทอื่น ๆ ของเส้นโค้งที่มีลักษณะเหมือน

295
00:10:44,780 --> 00:10:47,760
>> และข้อมูลเฉพาะของทางคณิตศาสตร์
การแสดงออกในวันนี้จะไม่สำคัญดังนั้น

296
00:10:47,760 --> 00:10:52,440
มาก แต่สังเกตเห็นว่ามีจำนวนมาก
ขั้นตอนวิธีการที่เลวร้ายยิ่งไกลกว่า

297
00:10:52,440 --> 00:10:53,470
สิ่งที่เป็นเส้นตรง

298
00:10:53,470 --> 00:10:55,410
แท้จริง n cubed ดูไม่ดีสวย

299
00:10:55,410 --> 00:10:58,400
2 ถึง n ที่มีลักษณะดีงาม
n squared ดูไม่ดีสวย

300
00:10:58,400 --> 00:11:01,630
และเราจะเห็นสิ่งที่บางส่วนของผู้
อาจจะอยู่ในความเป็นจริงวันนี้

301
00:11:01,630 --> 00:11:05,430
และ log n ไม่ได้รู้สึกไม่ดี แต่
ดีกว่า n เป็น 2 log ฐานของ n

302
00:11:05,430 --> 00:11:08,080
แต่คุณรู้ว่ามันจะได้รับแม้กระทั่ง
ที่น่าตื่นตาตื่นใจมากขึ้นถ้าเจนนิเฟอร์หรือถ้าเรา,

303
00:11:08,080 --> 00:11:12,910
ช่วงสัปดาห์แรกนั้นได้เกิดขึ้นกับ
สิ่งที่บันทึกเข้าสู่ระบบของ n

304
00:11:12,910 --> 00:11:15,880
>> ดังนั้นในคำอื่น ๆ ที่มีทั้งคนนี้
ช่วงของการแก้ปัญหาไปได้ที่จะ

305
00:11:15,880 --> 00:11:18,570
ปัญหา แต่แม้ที่นี่แจ้งให้ทราบล่วงหน้า
สิ่งที่จะเกิดขึ้น

306
00:11:18,570 --> 00:11:22,910
เมื่อตอนที่ผมซูมออกซึ่งของเส้นโค้งเหล่านี้
จะพิสูจน์ให้เป็นที่แน่นอน

307
00:11:22,910 --> 00:11:26,630
ที่เลวร้ายที่สุดของคนที่อยู่บนหน้าจอในขณะนี้?

308
00:11:26,630 --> 00:11:28,680
ดังนั้น n คีบดูสวย
ที่ไม่ดีในขณะนี้

309
00:11:28,680 --> 00:11:32,470
แต่ถ้าเราซูมออกและดูรายละเอียดของ
x และแกน y ที่จะ

310
00:11:32,470 --> 00:11:34,550
ครองในที่สุด?

311
00:11:34,550 --> 00:11:37,120
ดังนั้นมันเป็นจริงปรากฎว่า 2
n และคุณสามารถคิดออกเพียงแค่นี้โดย

312
00:11:37,120 --> 00:11:39,990
เสียบในบางส่วนมีขนาดใหญ่มากขึ้น
ตัวเลขและคุณจะเห็นว่า 2

313
00:11:39,990 --> 00:11:42,070
n จริงได้รับใหญ่ได้เร็วขึ้นมาก

314
00:11:42,070 --> 00:11:45,530
ถ้าเราจริงๆซูมออก 2 ไป
อัลกอริทึม n อย่างแน่นอนครับ

315
00:11:45,530 --> 00:11:48,170
ผมหมายถึงนี้จะใช้เวลา
ไม่น้อยของเวลา

316
00:11:48,170 --> 00:11:49,460
คอมพิวเตอร์เพื่อปั่นผ่าน

317
00:11:49,460 --> 00:11:52,500
>> แต่คุณจะเห็นเมื่อเวลาผ่านไปโดยเฉพาะอย่างยิ่ง
กับชุดปัญหาในอนาคตและแม้กระทั่ง

318
00:11:52,500 --> 00:11:55,600
โครงการสุดท้ายคือข้อมูลของคุณ
ชุดที่มีขนาดใหญ่ได้รับสิทธิทั้งหมดหรือไม่

319
00:11:55,600 --> 00:11:58,300
แม้จะอยู่ในรุ่นแรกของ Facebook,
เป็นจำนวนของเพื่อน ๆ และ

320
00:11:58,300 --> 00:12:01,840
จำนวนผู้ใช้ที่ลงทะเบียนได้ที่มีขนาดใหญ่,
คุณสามารถเรียงลำดับของโทรศัพท์ในและ

321
00:12:01,840 --> 00:12:05,530
ใช้สิ่งที่มีการค้นหาเชิงเส้น
หรือการเรียงลำดับที่ง่ายมาก

322
00:12:05,530 --> 00:12:07,030
อัลกอริทึมดังที่เราจะเห็นในวันนี้

323
00:12:07,030 --> 00:12:09,280
คุณต้องเริ่มคิดหนัก
และหนักเกี่ยวกับปัญหาเหล​​่านี้

324
00:12:09,280 --> 00:12:12,070
และประเภทของสถ​​านที่มีปัญหาเช่น
Facebook และ Google และ Microsoft,

325
00:12:12,070 --> 00:12:16,350
และคนอื่น ๆ ทำงานบนคือสิ่งเหล่านี้
การเรียงลำดับของการจัดเรียงข้อมูลขนาดใหญ่ของคำถาม

326
00:12:16,350 --> 00:12:18,530
วันเหล่านี้มากขึ้นเรื่อย ๆ

327
00:12:18,530 --> 00:12:18,900
>> ทั้งหมดขวา

328
00:12:18,900 --> 00:12:23,800
ดังนั้นความสำเร็จของเจนนิเฟอร์ในสองที่
ขั้นตอนวิธีการตรงไปตรงมาเธอได้อย่างน่าอัศจรรย์

329
00:12:23,800 --> 00:12:26,110
กันครั้งแรก แต่ขอ
เขียนเป็นโชคเพื่อให้เรา

330
00:12:26,110 --> 00:12:27,000
สามารถทำให้จุดนี้

331
00:12:27,000 --> 00:12:30,970
ในกรณีที่สองเธอ leveraged
อัลกอริทึมที่ซ้ำอีกครั้งและ

332
00:12:30,970 --> 00:12:34,670
อีกครั้ง แต่เธอได้รับ
สมมติฐานบางอย่างที่เราอนุญาต

333
00:12:34,670 --> 00:12:39,370
แต่เธอหลอกรายละเอียดบาง
ครั้งที่สองว่าเธอไม่ได้มี

334
00:12:39,370 --> 00:12:39,840
เป็นครั้งแรก

335
00:12:39,840 --> 00:12:41,800
ซึ่งเป็นอะไร

336
00:12:41,800 --> 00:12:43,050
>> รายการที่ถูกจัดเรียง

337
00:12:43,050 --> 00:12:46,350
ดังนั้นทันทีที่รายการถูกเรียงลำดับเรา
อ้างว่าเจนนิเฟอร์ก็สามารถที่จะทำ

338
00:12:46,350 --> 00:12:47,480
พื้นฐานที่ดีขึ้น

339
00:12:47,480 --> 00:12:51,450
7 ประตูใช่ไม่ได้เป็นที่น่าสนใจ,
แต่คิดว่ามันเรา 7000000 ประตู

340
00:12:51,450 --> 00:12:54,080
เข้าสู่ระบบของ n แน่นอนจะ
ที่จะดำเนินการอีกมาก

341
00:12:54,080 --> 00:12:55,610
ได้เร็วขึ้นในระยะยาว

342
00:12:55,610 --> 00:12:58,880
แต่เธอจะต้องมี
ประตูเรียงสำหรับเธอ

343
00:12:58,880 --> 00:13:02,320
ตอนนี้ผมเอาเสรีภาพของการทำที่
ล่วงหน้าบนหน้าจอคอมพิวเตอร์

344
00:13:02,320 --> 00:13:05,160
ที่นี่ แต่คิดว่าเจนนิเฟอร์ว่า
ต้องทำที่ตัวเอง?

345
00:13:05,160 --> 00:13:10,120
สมมติว่าประตูในคำถาม
แสดงข้อมูลในฐานข้อมูลหรือ

346
00:13:10,120 --> 00:13:14,260
เพื่อนลงทะเบียนสำหรับ Facebook หรือ
หน้าเว็บใดบนอินเทอร์เน็ตที่

347
00:13:14,260 --> 00:13:16,880
เว็บไซต์ต่างๆอาจจำเป็นต้อง
ไปยังหน้าเว็บหรือค้นหากว่า

348
00:13:16,880 --> 00:13:20,940
>> สมมติว่าคุณเพิ่งได้ข้อมูลดิบ
ตั้งค่าและมันถูกทิ้งให้อยู่กับคุณหรือ

349
00:13:20,940 --> 00:13:23,010
เจนนิเฟอร์จะทำเรียงลำดับที่

350
00:13:23,010 --> 00:13:26,950
ที่ค่อนข้างจะต้องการให้เราตอบ
คำถามที่ดีเท่าใดเวลา

351
00:13:26,950 --> 00:13:31,080
จะได้เอาเจนนิเฟอร์หรือแม้กระทั่งผม
ในการจัดเรียงตัวเลขเหล่านี้ล่วงหน้าเพื่อ

352
00:13:31,080 --> 00:13:32,680
ที่เธอจะได้ใช้ประโยชน์จากการที่

353
00:13:32,680 --> 00:13:32,880
ใช่ไหม?

354
00:13:32,880 --> 00:13:36,620
เพราะความหมายของหลักสูตรคือ
ถ้าฉันจะใช้เวลามากในขณะที่ในการจัดเรียง

355
00:13:36,620 --> 00:13:40,800
ตัวเลขที่ห่าใส่ใจที่คุณ
สามารถค้นหาหมายเลข 50 เช่นอย่างรวดเร็ว,

356
00:13:40,800 --> 00:13:44,850
อย่างเช่นในกรณีของเจนนิเฟอร์ถ้าเรามากกว่า
จมจำนวนของเวลาทั้งหมด

357
00:13:44,850 --> 00:13:46,920
มันต้องใช้เวลาโดยการเรียงลำดับสิ่งล่วงหน้า?

358
00:13:46,920 --> 00:13:49,320
>> ดังนั้นขอดูว่าเราไม่สามารถ
วาดภาพที่นี่

359
00:13:49,320 --> 00:13:51,370
ฉันมีความเครียดทั้งกลุ่มอื่น ๆ
ลูกว่าที่ช่วย

360
00:13:51,370 --> 00:13:52,270
ทำลายน้ำแข็งที่นี่

361
00:13:52,270 --> 00:13:55,690
และถ้าคุณจะไม่คิดเรา
ต้องเจ็ดอาสาสมัคร -

362
00:13:55,690 --> 00:13:57,060
เมื่อตกลง

363
00:13:57,060 --> 00:13:57,240
ว้าว

364
00:13:57,240 --> 00:13:59,250
ดังนั้นเราจึงไม่จำเป็นต้องใช้จ่าย
เมื่อโคมไฟโต๊ะเขียนหนังสือ, ดูเหมือนว่า

365
00:13:59,250 --> 00:13:59,690
ทั้งหมดขวา

366
00:13:59,690 --> 00:14:01,530
ดังนั้นวิธีการเกี่ยวกับคุณสองในด้านหน้า

367
00:14:01,530 --> 00:14:04,160
วิธีการเกี่ยวกับคุณสองคนอยู่ด้านหลัง

368
00:14:04,160 --> 00:14:04,870
เพื่อที่สี่

369
00:14:04,870 --> 00:14:09,890
วิธีการเกี่ยวกับคุณในด้านหน้า
ห้าหกและเจ็ด

370
00:14:09,890 --> 00:14:10,320
มีสิทธิ

371
00:14:10,320 --> 00:14:13,260
ของเพื่อนของคุณคุณชี้ออก
เพื่อให้คุณได้รับรางวัล

372
00:14:13,260 --> 00:14:13,700
>> ทั้งหมดขวา

373
00:14:13,700 --> 00:14:14,410
มาขึ้น

374
00:14:14,410 --> 00:14:17,120
และทำไมเราไม่คุณมี
ผมมาที่นี่

375
00:14:17,120 --> 00:14:18,960
ฉันจะให้คุณในแต่ละจำนวน

376
00:14:18,960 --> 00:14:22,150
และไปข้างหน้าและจัดให้ตัวเอง
จะเหมือนกันกับสิ่งที่

377
00:14:22,150 --> 00:14:25,180
ที่ปรากฎบนหน้าจอ

378
00:14:25,180 --> 00:14:26,530
>> [interposing VOICES]

379
00:14:26,530 --> 00:14:28,160
>> เดวิดเจลัน: อุ๊เสียใจ

380
00:14:28,160 --> 00:14:30,210
แมลง

381
00:14:30,210 --> 00:14:32,180
ทั้งหมดขวา

382
00:14:32,180 --> 00:14:32,750
ดีที่นี่เราไป

383
00:14:32,750 --> 00:14:34,180
หมายเลขห้า

384
00:14:34,180 --> 00:14:35,136
หมายเลขหก

385
00:14:35,136 --> 00:14:37,770
หนึ่งสองสามสี่
ห้าหกเจ็ด

386
00:14:37,770 --> 00:14:39,410
โอ้นี้เป็นที่น่าอึดอัดใจ

387
00:14:39,410 --> 00:14:41,210
>> 2 SPEAKER: ฉันเพิ่งจะได้รับ -

388
00:14:41,210 --> 00:14:41,900
>> เดวิดเจลัน: จัดการที่ดี

389
00:14:41,900 --> 00:14:43,130
ทั้งหมดขวา

390
00:14:43,130 --> 00:14:44,611
ขอบคุณสำหรับการมีส่วนร่วม

391
00:14:44,611 --> 00:14:47,200
>> [APPLAUSE]

392
00:14:47,200 --> 00:14:48,580
>> ตกลง

393
00:14:48,580 --> 00:14:48,860
ทั้งหมดขวา

394
00:14:48,860 --> 00:14:51,970
ดังนั้นเราจึงมีสี่สองหก
หนึ่งสามเจ็ดห้า

395
00:14:51,970 --> 00:14:56,010
ที่สมบูรณ์แบบเพื่อให้เรามีอาสาสมัครที่เจ็ด
ที่นี่ที่มีความเท่าเทียมกันในความกว้าง

396
00:14:56,010 --> 00:14:57,430
อาร์เรย์ที่เรากำลังเล่น
ที่มีก่อนหน้านี้

397
00:14:57,430 --> 00:14:59,470
และฉันเลือกที่เจ็ดเหตุผล
ที่จะเป็นเพียง

398
00:14:59,470 --> 00:15:00,840
ความสะดวกในการนิด ๆ หน่อย ๆ

399
00:15:00,840 --> 00:15:04,400
และฉันจะนำเสนอเป็นครั้งแรกที่
เราจัดเรียงเหล่านี้เจ็ดอาสาสมัคร

400
00:15:04,400 --> 00:15:06,786
หากคุณต้องการเป็นครั้งแรก,
เพื่อกล่าวทักทายแม้ว่า

401
00:15:06,786 --> 00:15:08,970
ตั้งแต่นี้เป็นไปได้
หลายนาทีที่น่าอึดอัดใจ

402
00:15:08,970 --> 00:15:10,370
แนะนำตัว

403
00:15:10,370 --> 00:15:10,980
>> เกรซ: สวัสดีครับผมเกรซ

404
00:15:10,980 --> 00:15:14,190
ฉันที่ในปี Leverett บ้าน

405
00:15:14,190 --> 00:15:14,620
>> แบรนสัน: Hi

406
00:15:14,620 --> 00:15:15,620
ผมแบรนสัน

407
00:15:15,620 --> 00:15:16,920
ผมน้องใหม่ในเชื่อม

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> gabe: Hi

410
00:15:20,230 --> 00:15:21,040
ผมเกบ

411
00:15:21,040 --> 00:15:22,300
ฉันจูเนียร์ในแคบอต

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> NEIL: ฉันนีล

414
00:15:25,980 --> 00:15:29,090
ฉันครั้งแรกในแมตทิว

415
00:15:29,090 --> 00:15:29,550
>> JASON: ฉันเจสัน

416
00:15:29,550 --> 00:15:32,816
ฉันครั้งแรกในกรี

417
00:15:32,816 --> 00:15:33,700
>> MIKE: ฉันไมค์

418
00:15:33,700 --> 00:15:37,360
ผมน้องใหม่ในสีเทา

419
00:15:37,360 --> 00:15:37,990
>> JESS: ฉันเจ

420
00:15:37,990 --> 00:15:40,313
ฉันที่ในปี Leverett

421
00:15:40,313 --> 00:15:41,300
>> เดวิดเจลัน: ยอดเยี่ยม

422
00:15:41,300 --> 00:15:41,850
ทั้งหมดขวา

423
00:15:41,850 --> 00:15:44,190
ดีขอขอบคุณทั้งหมดของเรา
อาสาสมัครที่นี่ป่านนี้

424
00:15:44,190 --> 00:15:47,110
และความท้าทายที่อยู่ในมือขณะนี้เป็นไป
จะต้องเรียงลำดับจากพวกเหล่านี้ แต่แล้ว

425
00:15:47,110 --> 00:15:50,250
เราจะต้องคิดว่าเล็ก ๆ น้อย ๆ
อย่างหนักเกี่ยวกับวิธีการได้อย่างมีประสิทธิภาพเราจริง

426
00:15:50,250 --> 00:15:51,110
เรียงพวกเขา

427
00:15:51,110 --> 00:15:52,580
ดังนั้นขอความพยายามครั้งแรกนี้

428
00:15:52,580 --> 00:15:55,970
พวกคุณจะได้เห็นตัวเลขของแต่ละคน
เพียงแค่วางรอบมุม

429
00:15:55,970 --> 00:15:59,380
ไปข้างหน้าและใช้เวลาไม่กี่วินาทีและ
จัดเรียงเองจากที่เล็กที่สุดใน

430
00:15:59,380 --> 00:16:01,240
จากซ้ายไปขวาที่ใหญ่ที่สุดบน

431
00:16:01,240 --> 00:16:02,490
ไป

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> ตกลง

434
00:16:07,530 --> 00:16:08,030
ดี

435
00:16:08,030 --> 00:16:09,370
นั่นคือรวดเร็วสาปจริงๆ

436
00:16:09,370 --> 00:16:14,040
ตอนนี้คนที่นี่สิ่งที่เป็นอัลกอริทึม
ว่าคนเหล่านี้นำมาใช้?

437
00:16:14,040 --> 00:16:14,900
>> 1 SPEAKER: น้อยไปหามากที่สุด

438
00:16:14,900 --> 00:16:15,000
>> เดวิดเจลัน: ตกลง

439
00:16:15,000 --> 00:16:18,070
น้อยไปหาที่ยิ่งใหญ่ที่สุดที่เป็นจริงที่จัดเรียงของ
วัตถุประสงค์ แต่ฉันไม่แน่ใจว่าเป็น

440
00:16:18,070 --> 00:16:18,890
จริงๆอัลกอริทึม

441
00:16:18,890 --> 00:16:21,810
น้อยไปหามากที่สุดไม่ได้บอก
ฉันขั้นตอนโดยขั้นตอนว่าจะทำอย่างไร

442
00:16:21,810 --> 00:16:22,833
อ้าง?

443
00:16:22,833 --> 00:16:24,083
>> 1 SPEAKER: [ได้ยิน]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> เดวิดเจลัน: ตกลง

446
00:16:26,280 --> 00:16:28,920
ดังนั้นหากคุณเห็นคนที่มีขนาดเล็กกว่า
จำนวนของคุณแล้วย้ายไป

447
00:16:28,920 --> 00:16:29,680
ทางด้านขวาของพวกเขา

448
00:16:29,680 --> 00:16:32,800
เพื่อที่ว่าตอนนี้ได้รับแสดงออกมากขึ้น,
มากขึ้นเช่นอัลกอริทึมเพราะคุณ

449
00:16:32,800 --> 00:16:35,410
สามารถพูดได้ว่าถ้านี้แล้วว่า

450
00:16:35,410 --> 00:16:37,050
ดังนั้นเราจึงมีชนิดของบางอย่าง
สร้างเงื่อนไข

451
00:16:37,050 --> 00:16:39,700
และคนเหล่านี้ดูเหมือนจะทำอย่างนั้นไม่กี่
ครั้งเพราะบางท่านย้ายบิต

452
00:16:39,700 --> 00:16:40,420
ของระยะทาง

453
00:16:40,420 --> 00:16:43,410
ดังนั้นจึงสันนิษฐานได้ว่าชนิดของบางอย่าง
วนลูปที่เกิดขึ้นในจิตใจของพวกเขา

454
00:16:43,410 --> 00:16:44,610
>> แต่ลองทำแผนว่า

455
00:16:44,610 --> 00:16:47,540
ถ้าพวกคุณสามารถตั้งค่ากลับ
เพื่อตกลงนี้

456
00:16:47,540 --> 00:16:50,650
ลองดูถ้าเราไม่สามารถเป็นระเบียบแบบแผนนี้
บิตและจากนั้นถามคำถามเพียง

457
00:16:50,650 --> 00:16:51,580
วิธีที่มีประสิทธิภาพนี้คืออะไร?

458
00:16:51,580 --> 00:16:54,220
แน่นอนว่าเมื่อเราทำเช่นนี้มากขึ้นอย่างช้าๆ
มันจะเป็นความรู้สึกที่ดีของ

459
00:16:54,220 --> 00:16:57,210
อัลกอริทึม แต่ขอดูว่าเราสามารถ
วางนิ้วมือข​​องเราในขั้นตอนที่ถูกต้อง

460
00:16:57,210 --> 00:16:58,670
>> ดังนั้นคุณสองคนมีสี่และสอง

461
00:16:58,670 --> 00:17:01,020
หรือคุณลำดับที่ถูกต้องหรือไม่ถูกต้อง?

462
00:17:01,020 --> 00:17:01,900
เห็นได้ชัดว่าไม่ถูกต้อง

463
00:17:01,900 --> 00:17:02,710
ดังนั้นเราจึงเปลี่ยน

464
00:17:02,710 --> 00:17:05,170
ตอนนี้ฉันจะต้องย้ายออกไป
ที่นี่และพูด 4-6

465
00:17:05,170 --> 00:17:06,240
คุณถูกต้องหรือไม่ถูกต้อง?

466
00:17:06,240 --> 00:17:06,599
>> gabe: ถูกต้อง

467
00:17:06,599 --> 00:17:07,180
>> เดวิดเจลัน: ถูกต้อง

468
00:17:07,180 --> 00:17:08,300
และเป็นหนึ่งในหก?

469
00:17:08,300 --> 00:17:08,609
Nope

470
00:17:08,609 --> 00:17:09,630
แลกเปลี่ยน

471
00:17:09,630 --> 00:17:10,490
เพื่อที่ว่าสองแลกเปลี่ยน

472
00:17:10,490 --> 00:17:11,710
หกและสาม?

473
00:17:11,710 --> 00:17:11,980
Nope

474
00:17:11,980 --> 00:17:13,000
แลกเปลี่ยน

475
00:17:13,000 --> 00:17:13,930
หกและเจ็ด?

476
00:17:13,930 --> 00:17:14,630
ดูดี

477
00:17:14,630 --> 00:17:15,396
เจ็ดห้า?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [ได้ยิน]

479
00:17:16,150 --> 00:17:17,089
>> เดวิดเจลัน: ตกลงแลกเปลี่ยน

480
00:17:17,089 --> 00:17:19,770
และจัดเรียง

481
00:17:19,770 --> 00:17:19,980
ทั้งหมดขวา

482
00:17:19,980 --> 00:17:21,440
ดังนั้นเห็นได้ชัดไม่ได้ใช่มั้ย?

483
00:17:21,440 --> 00:17:22,470
ดังนั้นจึงมีเป็นจำนวนมากที่เกิดขึ้น

484
00:17:22,470 --> 00:17:24,920
แต่อันที่จริงคนเหล่านี้แม้
เพียงแค่สัญชาตญาณ

485
00:17:24,920 --> 00:17:25,450
เก็บย้าย

486
00:17:25,450 --> 00:17:27,710
พวกเขาไม่ได้หยุดเพียงแค่เมื่อพวกเขา
การแก้ไขปัญหาหนึ่ง

487
00:17:27,710 --> 00:17:27,839
ดังนั้น

488
00:17:27,839 --> 00:17:29,390
อันที่จริงฉันจะมี
ที่จะทำในสิ่งเดียวกัน

489
00:17:29,390 --> 00:17:32,720
ฉันจะต้องจัดเรียงของกลับย้อนกลับ
ที่จุดเริ่มต้นของปัญหานี้,

490
00:17:32,720 --> 00:17:35,630
หรือจุดเริ่มต้นของแถวนี้
คนขอเริ่มต้นเรียกพวกเขา

491
00:17:35,630 --> 00:17:38,366
>> และตอนนี้สิ่งที่ควรอัลกอริทึมของฉัน
เมื่อผ่านที่สองเป็นอย่างไร

492
00:17:38,366 --> 00:17:39,220
>> 1 SPEAKER: สิ่งเดียวกัน

493
00:17:39,220 --> 00:17:39,940
>> เดวิดเจลัน: สิ่งเดียวกัน

494
00:17:39,940 --> 00:17:41,460
และนี้ฉันเริ่มที่จะชอบใช่มั้ย?

495
00:17:41,460 --> 00:17:44,720
เร็วที่สุดเท่าที่คุณสามารถพบว่าตัวเองกำลังทำอะไรอยู่
สิ่งเดียวกันอีกครั้งและอีกครั้งที่

496
00:17:44,720 --> 00:17:47,890
กลายเป็นมากขึ้นเช่นอัลกอริทึม,
และสัญชาตญาณของมนุษย์น้อยลง

497
00:17:47,890 --> 00:17:48,680
>> ดังนั้นตอนนี้ที่นี่เราไปอีกครั้ง

498
00:17:48,680 --> 00:17:49,870
สองและสี่

499
00:17:49,870 --> 00:17:50,220
เลขที่

500
00:17:50,220 --> 00:17:51,050
และเป็นหนึ่งในสี่?

501
00:17:51,050 --> 00:17:53,380
ah, มีแน่นอนบางอย่าง
ยังคงทำงานที่จะต้องทำ

502
00:17:53,380 --> 00:17:53,620
และสาม?

503
00:17:53,620 --> 00:17:54,572
ดี

504
00:17:54,572 --> 00:17:56,000
สี่และหก?

505
00:17:56,000 --> 00:17:58,380
หกห้า?

506
00:17:58,380 --> 00:17:59,470
หกและเจ็ด?

507
00:17:59,470 --> 00:18:00,970
ตกลงตอนนี้ทำ

508
00:18:00,970 --> 00:18:01,550
ตกลงไม่มี

509
00:18:01,550 --> 00:18:02,710
ผมต้องกลับไป

510
00:18:02,710 --> 00:18:05,130
>> ดังนั้นตอนนี้อีกครั้งที่เรากำลังทำนี้
เล็ก ๆ น้อย ๆ อย่างจงใจ

511
00:18:05,130 --> 00:18:08,700
และตอนนี้มีเพียงหนึ่งสมอง
การดำเนินการขั้นตอนวิธีนี้

512
00:18:08,700 --> 00:18:10,290
CPU หนึ่งถ้าคุณจะ

513
00:18:10,290 --> 00:18:13,090
และตรงไปตรงมาว่าเป็นทรัพยากรเพียง
เรากำลังจะมีการเข้าถึง

514
00:18:13,090 --> 00:18:16,280
และเมื่อเรากลับไปที่แป้นพิมพ์
และมีบางอย่างเช่น C ที่ของเรา

515
00:18:16,280 --> 00:18:19,600
การกำจัดของเราเพียงแค่เขียนโปรแกรม
ที่สามารถทำสิ่งหนึ่งที่เวลา

516
00:18:19,600 --> 00:18:22,900
ในขณะที่คนเหล่านี้สักครู่ที่ผ่านมาเรา
leveraged brainpower โดยรวมของพวกเขา

517
00:18:22,900 --> 00:18:24,180
เช่นเดียวกับพวกคุณได้ในศูนย์สัปดาห์

518
00:18:24,180 --> 00:18:24,980
ดังนั้นขอให้ทำเช่นนี้

519
00:18:24,980 --> 00:18:26,260
>> และเป็นหนึ่งในสอง

520
00:18:26,260 --> 00:18:26,945
สองและสาม

521
00:18:26,945 --> 00:18:27,460
สามและสี่

522
00:18:27,460 --> 00:18:28,310
สี่และห้า

523
00:18:28,310 --> 00:18:28,620
ห้าและหก

524
00:18:28,620 --> 00:18:30,510
หกและเจ็ด

525
00:18:30,510 --> 00:18:31,880
ทำ?

526
00:18:31,880 --> 00:18:34,560
ดังนั้นฉัน แต่ให้ฉันเล่น
ปีศาจของผู้สนับสนุน

527
00:18:34,560 --> 00:18:37,950
ฉันจัดเรียงของเครื่องคอมพิวเตอร์ที่เพียงแค่
ทำผ่านผ่านแถวนี้

528
00:18:37,950 --> 00:18:40,225
คนรู้ว่าฉันทำ?

529
00:18:40,225 --> 00:18:40,670
>> 1 SPEAKER: เลขที่

530
00:18:40,670 --> 00:18:41,050
>> เดวิดเจลัน: ดังนั้นทำไม?

531
00:18:41,050 --> 00:18:46,900
สิ่งที่ฉันจะต้องทำเพื่อที่จะ
สรุปเด็ดขาดว่าฉันทำ?

532
00:18:46,900 --> 00:18:48,230
อาจเป็นหนึ่งในการส่งผ่านมากขึ้น

533
00:18:48,230 --> 00:18:48,430
ใช่ไหม?

534
00:18:48,430 --> 00:18:51,760
เพราะฉันรู้จากก่อนหน้านี้ที่
ผ่านเป็นที่ฉันได้รับการแก้ไขความผิดพลาด

535
00:18:51,760 --> 00:18:53,920
และวิธีการที่อาจจะมี
ยังผิดพลาดอีก

536
00:18:53,920 --> 00:18:54,840
ที่ฉันต้องแก้ไข

537
00:18:54,840 --> 00:18:58,680
ดังนั้นฉันสามารถตรวจสอบโดยการกรอกลับและ
แล้วการตรวจสอบ, 1-2, สองและ

538
00:18:58,680 --> 00:19:00,940
สามสามและสี่สี่และห้า
ห้าและหกหกและเจ็ด

539
00:19:00,940 --> 00:19:02,510
ตกลงตอนนี้ผมไม่ทำงาน

540
00:19:02,510 --> 00:19:05,990
>> แน่นอนฉันสามารถจำได้ว่าผมไม่ได้ทำ
ทำงานร่วมกับบางอย่างเช่นตัวแปร,

541
00:19:05,990 --> 00:19:06,975
เช่น int

542
00:19:06,975 --> 00:19:12,490
เรียกว่าแลกเปลี่ยนและถ้าสลับเป็น 0 เมื่อฉัน
ได้รับที่นี่และมันเริ่มต้นที่ 0 แล้ว

543
00:19:12,490 --> 00:19:15,520
ฉันจะโง่ให้ไป
กลับมาตรวจสอบอีกครั้งและ

544
00:19:15,520 --> 00:19:16,450
อีกครั้งและอีกครั้งใช่มั้ย?

545
00:19:16,450 --> 00:19:18,450
เพราะคุณได้รับการติดอยู่ในบางส่วน
ชนิดของห่วงอนันต์

546
00:19:18,450 --> 00:19:21,250
ดังนั้นทันทีที่มีสัญญาแลกเปลี่ยน 0 คน,
เราสามารถเรียกร้องว่านี้

547
00:19:21,250 --> 00:19:23,810
อัลกอริทึมเป็นจริงสมบูรณ์

548
00:19:23,810 --> 00:19:25,400
>> ตอนนี้ขอใส่ชื่อเกี่ยวกับเรื่องนี้

549
00:19:25,400 --> 00:19:28,930
วิธีที่ผมเสนอเราเพียงแค่
สิ่งที่เรียกว่าฟองสบู่จะดำเนินการ

550
00:19:28,930 --> 00:19:32,800
เรียงลำดับดังกล่าวเป็นที่รู้จักกันในแง่ที่ว่า
ตัวเลขที่เป็นชนิดที่ใหญ่กว่า

551
00:19:32,800 --> 00:19:37,990
ฟองทางของพวกเขาขึ้นไปด้านบนหรือเพิ่มขึ้น
ไปยังจุดสิ้นสุดของอาร์เรย์ของตัวเลข

552
00:19:37,990 --> 00:19:40,270
แต่วิธีการที่มีประสิทธิภาพขั้นตอนวิธีนี้คือ?

553
00:19:40,270 --> 00:19:44,600
ผมไม่กี่ขั้นตอนที่ร่างกายต้อง
ใช้ตัวอย่างเช่นในการจัดเรียงเหล่านี้

554
00:19:44,600 --> 00:19:45,850
เจ็ดมนุษย์

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> สี่ถึงห้า?

557
00:19:49,550 --> 00:19:51,420
ตกลงมากเกินไปเป็นที่สุด
จะเป็นคำตอบ

558
00:19:51,420 --> 00:19:54,960
แต่แม้แล้วจำนวนเฉพาะ
ไม่ได้เป็นที่น่าสนใจดังนั้น

559
00:19:54,960 --> 00:19:56,670
ลองพูดคุยว่ามันเป็น n

560
00:19:56,670 --> 00:20:00,520
ดังนั้นถ้าฉันได้ n คนขึ้นที่นี่และพวกเขา
ถูกจัดเรียงของในลำดับแบบสุ่มที่

561
00:20:00,520 --> 00:20:02,180
จุดเริ่มต้นในการสั่งซื้อเดิมที่

562
00:20:02,180 --> 00:20:04,910
ดีฉันไม่กี่ขั้นตอนมี
ที่จะใช้ในครั้งแรกผ่าน?

563
00:20:04,910 --> 00:20:09,810
มันเป็นหนึ่งสองสามสี่ห้า
หกและพวกเขากำลังเจ็ดคนดังนั้น

564
00:20:09,810 --> 00:20:13,670
ที่เจ็ดหก - เพื่อที่ว่า n
ลบหนึ่งขั้นตอนเป็นครั้งแรก

565
00:20:13,670 --> 00:20:16,280
>> ตอนนี้ฉันไม่กี่ขั้นตอนมี
ที่จะใช้เมื่อผมกรอ?

566
00:20:16,280 --> 00:20:19,310
ดีเราจริงอาจดับเบิลว่าถ้า
เราอยากจะ แต่ตอนนี้ผม

567
00:20:19,310 --> 00:20:22,300
เพียงแค่จะบอกขวาทั้งหมด
อีก n ลบ 1

568
00:20:22,300 --> 00:20:25,240
ดังนั้น n ลบ 1 เป็นไปได้
ที่น่ารำคาญในการติดตามเพื่อขอ

569
00:20:25,240 --> 00:20:26,400
เพียงแค่รอบขึ้นเล็กน้อย

570
00:20:26,400 --> 00:20:27,770
ขั้นตอน 2n ดังนั้น

571
00:20:27,770 --> 00:20:29,310
ดังนั้นขั้นตอนที่ 14 ให้หรือใช้

572
00:20:29,310 --> 00:20:31,930
>> ผมไม่กี่ครั้งที่ใช้
ขั้นตอนในครั้งต่อไป?

573
00:20:31,930 --> 00:20:33,740
ดีก็ 3n

574
00:20:33,740 --> 00:20:34,510
จริงๆ

575
00:20:34,510 --> 00:20:37,920
และตอนนี้ในกรณีที่เลวร้ายที่สุดสำหรับ
เช่นวิธีการหลายครั้งที่ฉันจะมี

576
00:20:37,920 --> 00:20:41,730
หายไปและกลับไปและกลับ
การดำเนินการขั้นตอนวิธีนี้การแลกเปลี่ยน

577
00:20:41,730 --> 00:20:44,620
คนที่ผ่านแต่ละประมาณ?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
มัน n squared จริงใช่มั้ย?

580
00:20:50,010 --> 00:20:53,000
>> เพราะในกรณีที่เลวร้ายที่สุดที่คุณสามารถชนิด
ของคิดเกี่ยวกับเรื่องนี้อย่างสังหรณ์ใจ,

581
00:20:53,000 --> 00:20:54,800
แม้ว่ามันอาจใช้เวลาเพียงเล็กน้อย
บิตของเวลาที่จะจมลงไปค่ะ

582
00:20:54,800 --> 00:20:57,590
ในกรณีที่เลวร้ายที่สุดสิ่งที่จะเหล่านี้
เจ็ดคนได้เหมือนใน

583
00:20:57,590 --> 00:21:00,230
แง่ของการจัดเรียง
ของตัวเลขของพวกเขา

584
00:21:00,230 --> 00:21:01,460
โดยสิ้นเชิงหลังขวา?

585
00:21:01,460 --> 00:21:02,815
และเพียงเพื่อจำลองว่า
สิ่งที่ชื่อของคุณอีกครั้ง?

586
00:21:02,815 --> 00:21:03,360
>> MIKE: ไมค์

587
00:21:03,360 --> 00:21:03,640
>> เดวิดเจลัน: ไมค์?

588
00:21:03,640 --> 00:21:08,100
ตกลงไมค์ที่คุณสามารถเพียงแค่เข้าร่วมฉันกว่า
ที่นี่เพียงหนึ่งที่สอง?

589
00:21:08,100 --> 00:21:08,880
ที่จริงไม่มี

590
00:21:08,880 --> 00:21:10,150
ขออภัยไมค์ขอย้อนกลับ

591
00:21:10,150 --> 00:21:10,910
ชื่ออะไรของคุณอีกครั้ง?

592
00:21:10,910 --> 00:21:11,180
>> NEIL: นีล

593
00:21:11,180 --> 00:21:11,640
>> เดวิดเจลัน: นีล

594
00:21:11,640 --> 00:21:13,750
ตกลงนีลคุณมาพร้อมกับ
ฉันถ้าคุณไม่ทราบ

595
00:21:13,750 --> 00:21:17,150
ดังนั้นฉันจะเสนอเพียงเพื่อ
ความเรียบง่ายที่นีลขณะนี้อยู่ในของเขา

596
00:21:17,150 --> 00:21:18,510
กรณีที่เลวร้ายที่สุด

597
00:21:18,510 --> 00:21:20,720
แต่จำวิธีการที่ฉันนำมาใช้
อัลกอริทึมของฉัน

598
00:21:20,720 --> 00:21:24,530
ผมเปรียบเทียบเปรียบเทียบเปรียบเทียบ
การเปรียบเทียบการเปรียบเทียบโอ้

599
00:21:24,530 --> 00:21:26,640
ตอนนี้คนเหล่านี้จะออก
ของคำสั่งดังนั้นฉันจะแก้ไข

600
00:21:26,640 --> 00:21:27,980
ดังนั้นพวกคุณสลับ

601
00:21:27,980 --> 00:21:31,630
แต่พิจารณาในขณะนี้เท่าไหร่ไกลออกไป
นีลไม่ต้องไป?

602
00:21:31,630 --> 00:21:32,690
มัน n ลวก

603
00:21:32,690 --> 00:21:33,570
คุณรู้ว่ามันไม่จริง n

604
00:21:33,570 --> 00:21:36,040
มันเหมือนกับ n ลบ 1 แต่ฉันได้รับ
การติดตามรำคาญเล็ก ๆ น้อย ๆ

605
00:21:36,040 --> 00:21:37,550
หมายเลขเพื่อให้เพียงเรียกว่า n

606
00:21:37,550 --> 00:21:42,860
>> ดังนั้นถ้านีลย้ายหนึ่งขั้นสูงสุดในแต่ละ
เวลาและจะย้ายนีขั้นตอนเดียว

607
00:21:42,860 --> 00:21:46,580
ฉันต้องทำเรื่องนี้ให้ผ่านไปน่าเบื่อจริงๆ
ไปมานี้เป็นประมาณ

608
00:21:46,580 --> 00:21:52,080
การทำเช่นนี้ขั้นตอนที่ n, ครั้งโดยรวมที่ n,
เพราะมันจะพาฉันไป

609
00:21:52,080 --> 00:21:55,820
ที่มีหลายขั้นตอนเพื่อให้ได้นีลทั้งหมด
วิธีการที่เขาเป็น

610
00:21:55,820 --> 00:21:58,620
นับประสาคนอื่นถ้าพวกคุณ
ทั้งหมดถูกสั่งให้ผิดพลาดเช่นกัน

611
00:21:58,620 --> 00:22:01,100
>> จัดเรียงฟองดังนั้นขอเรียก n squared

612
00:22:01,100 --> 00:22:04,860
เวลาทำงานของอัลกอริทึมนี้
ประสิทธิภาพการทำงานของอัลกอริทึมนี้

613
00:22:04,860 --> 00:22:07,120
ประสิทธิภาพของอัลกอริทึมนี้
เราก็ต้องอธิบายมากขึ้น

614
00:22:07,120 --> 00:22:08,800
โดยทั่วไปเป็น n squared

615
00:22:08,800 --> 00:22:11,650
ซึ่งเป็นสิ่งที่ดีเพราะผมสามารถทำอะไรได้
เช่นเดียวกันกับคนแปดคนเก้า

616
00:22:11,650 --> 00:22:15,450
คนล้านคนและที่
คำตอบไม่ได้จะเปลี่ยน

617
00:22:15,450 --> 00:22:18,870
>> ดังนั้นถ้าพวกคุณจะไม่คิดให้
ตั้งค่าที่คุณไปยังที่ที่คุณเริ่มต้น

618
00:22:18,870 --> 00:22:22,510
และลองทั้งสองวิธีอื่น ๆ และ
ดูว่าเราไม่สามารถทำโดยพื้นฐาน

619
00:22:22,510 --> 00:22:23,820
ที่ดีกว่านี้

620
00:22:23,820 --> 00:22:27,130
ดังนั้นเวลานี้ผมจะนำเสนอ
การเรียงลำดับของขั้นตอนวิธีที่แตกต่างกัน

621
00:22:27,130 --> 00:22:29,950
นั่นคือฉลาดมากของเราได้ตลอดเวลาที่ผ่านมา
และพวกคุณมีสิทธิที่จะมี

622
00:22:29,950 --> 00:22:32,470
สัญชาตญาณทางด้านขวาของเพียงชนิด
จากการแลกเปลี่ยนคู่

623
00:22:32,470 --> 00:22:36,500
แต่ถ้าผมอยากจะเข้ามาใกล้นี้
เพียงและเป้าหมายของฉันคือการย้าย

624
00:22:36,500 --> 00:22:39,800
ทั้งหมดของตัวเลขเล็ก ๆ น้อย ๆ ด้วยวิธีนี้และ
ผลักดันทั้งหมดของตัวเลขขนาดใหญ่ที่

625
00:22:39,800 --> 00:22:43,030
วิธีการที่ว่าทำไมฉันจึงไม่เพียงแค่ทำใน
ไร้เดียงสามากที่สุดวิธีที่เป็นไปได้และดูว่าฉัน

626
00:22:43,030 --> 00:22:45,730
สามารถทำได้ดีกว่าสิ่งที่เป็น
อัลกอริทึมที่ซับซ้อนอย่างเป็นธรรม?

627
00:22:45,730 --> 00:22:46,620
>> ดังนั้นเรามาดู

628
00:22:46,620 --> 00:22:48,940
สี่เป็นจำนวนน้อยสวยดังนั้นฉัน
จะไปปล่อยให้คุณมีช่วงเวลาที่

629
00:22:48,940 --> 00:22:50,610
Ooh หมายเลขสองจะดียิ่งขึ้น

630
00:22:50,610 --> 00:22:52,230
คุณสามารถเพียงเพื่อก้าวไปข้างหน้า
สำหรับช่วงเวลา?

631
00:22:52,230 --> 00:22:55,670
ปัจจุบันนี้เป็นที่เล็กที่สุดหมายเลขของฉัน
ผู้สมัครและฉันจะจำ

632
00:22:55,670 --> 00:22:57,000
ว่าด้วยความเหมือนตัวแปร

633
00:22:57,000 --> 00:22:57,930
แต่ฉันจะให้ตรวจสอบ

634
00:22:57,930 --> 00:22:59,890
มีคนที่มี
จำนวนมีขนาดเล็ก?

635
00:22:59,890 --> 00:23:00,460
หกไม่

636
00:23:00,460 --> 00:23:01,390
โอ้มีนีลอีกครั้ง

637
00:23:01,390 --> 00:23:04,050
>> ดังนั้นฉันจะผลักดันให้คุณกลับมา
การเรียงลำดับของแนวคิด

638
00:23:04,050 --> 00:23:05,120
นีลจะมาข้างหน้า

639
00:23:05,120 --> 00:23:08,440
และตอนนี้ตัวแปรที่ฉันใช้เพื่อ
ติดตามผู้ที่มีขนาดเล็กที่สุด

640
00:23:08,440 --> 00:23:11,390
จำนวนที่มีการปรับปรุงเพื่อให้มี
สถานที่ตั้งของนีล

641
00:23:11,390 --> 00:23:12,110
ดีให้ดู

642
00:23:12,110 --> 00:23:13,960
สามเจ็ดห้า

643
00:23:13,960 --> 00:23:15,590
ตกลงฉันรู้ว่านีลเป็นที่เล็กที่สุด

644
00:23:15,590 --> 00:23:18,110
สิ่งที่ง่ายที่สุดคือสิ่งที่
สำหรับผมที่จะทำตอนนี้?

645
00:23:18,110 --> 00:23:21,410
ฉันจะไม่ไปเสียเวลาของฉันโดยเพียงแค่
เดือดปุด ๆ Neil จุดหนึ่งไปทางซ้าย

646
00:23:21,410 --> 00:23:25,350
ทำไมฉันจึงไม่เพียงแค่ใส่นีลที่เขา
เป็นซึ่งเป็นหลักสูตรที่?

647
00:23:25,350 --> 00:23:26,160
>> ทุกวิธีทางที่จุดเริ่มต้น

648
00:23:26,160 --> 00:23:27,720
ดังนั้นนีลมาพร้อมกับผม

649
00:23:27,720 --> 00:23:28,910
และสิ่งที่เป็นชื่อของคุณอีกครั้ง?

650
00:23:28,910 --> 00:23:29,310
>> เกรซ: เก​​รซ

651
00:23:29,310 --> 00:23:29,710
>> เดวิดเจลัน: เกรซ

652
00:23:29,710 --> 00:23:29,920
ตกลง

653
00:23:29,920 --> 00:23:32,490
ดังนั้นเกรซ, โชคไม่ดีที่คุณ
ชนิดของในทาง

654
00:23:32,490 --> 00:23:34,290
ดังนั้นทำอย่างไรเราแก้ปัญหานี้หรือไม่

655
00:23:34,290 --> 00:23:34,490
ใช่ไหม?

656
00:23:34,490 --> 00:23:37,500
ถ้าเป็นแถวมี
เพียงเจ็ดสถานที่

657
00:23:37,500 --> 00:23:40,830
จำได้ว่ามีการปล้นเราได้พูดคุยเกี่ยวกับ
ประกาศทุกเพศทุกวัยและเรามีเพียง

658
00:23:40,830 --> 00:23:41,740
จำนวน จำกัด ทุกเพศทุกวัย?

659
00:23:41,740 --> 00:23:42,535
ความคิดเดียวกันที่นี่

660
00:23:42,535 --> 00:23:44,300
เรามีเพียงจำนวน จำกัด ของ ints

661
00:23:44,300 --> 00:23:47,590
เกรซเป็นชนิดของในของเรา
ทางเราไม่ดังนั้นวิธีการแก้ไข?

662
00:23:47,590 --> 00:23:49,555
>> วิธีที่ง่ายที่สุดก็เป็นเช่นกัน
เกรซ, เสียใจ

663
00:23:49,555 --> 00:23:51,870
คุณจะต้องไปผ่าน
มีเพื่อให้เราสามารถทำให้ห้อง

664
00:23:51,870 --> 00:23:55,290
ตอนนี้ถ้าคุณคิดว่าเกี่ยวกับเรื่องนี้อาจจะ
เราเพียงแค่ทำปัญหาแย่ลง

665
00:23:55,290 --> 00:23:58,510
และบางทีที่เราทำเพราะสิ่งที่ถ้า
เกรซอยู่ในสถานที่ที่เหมาะสมหรือไม่

666
00:23:58,510 --> 00:24:01,730
แต่เรารู้ว่าเธอไม่ได้เพราะ
มิฉะนั้นเธอจะได้รับ

667
00:24:01,730 --> 00:24:03,980
ที่ยืนอยู่ข้างหน้าแทน
นีลในเวลานี้ใช่มั้ย?

668
00:24:03,980 --> 00:24:05,550
เราได้ตรวจสอบจำนวนของเธอออก

669
00:24:05,550 --> 00:24:05,770
>> ทั้งหมดขวา

670
00:24:05,770 --> 00:24:09,110
ดังนั้นตอนนี้นีลที่อยู่ในสถานที่ที่เหมาะสมและ
ฉันจะทำเพิ่มประสิทธิภาพของเล็กน้อย

671
00:24:09,110 --> 00:24:11,740
สำหรับนาทีถัดไป, ฉันจะไม่สนใจ
นีลทั้งหมดเข้าด้วยกันเพื่อที่จะไม่ไป

672
00:24:11,740 --> 00:24:15,280
เสียเวลาของเขาหรือไม่ตั้งใจ
สลับเขาไปยังสถานที่ที่ไม่ถูกต้อง

673
00:24:15,280 --> 00:24:17,805
ดังนั้นตอนนี้ฉันจะหาวิธีต่อไป
องค์ประกอบที่เล็กที่สุด?

674
00:24:17,805 --> 00:24:18,480
สอง

675
00:24:18,480 --> 00:24:20,225
นั่นเป็นตัวเลขที่ดีงามถ้า
คุณต้องการที่จะก้าวไปข้างหน้าและ

676
00:24:20,225 --> 00:24:21,100
ผมจะจำคุณ

677
00:24:21,100 --> 00:24:21,980
หกไม่ดี

678
00:24:21,980 --> 00:24:24,820
สี่สามเจ็ดห้าไม่ดี

679
00:24:24,820 --> 00:24:26,800
เพื่อให้ฉันย้ายคุณ
สถานที่ที่เหมาะสมของคุณ

680
00:24:26,800 --> 00:24:28,470
และเราก็โชคดีในเวลานี้

681
00:24:28,470 --> 00:24:31,350
>> ตอนนี้ฉันจะไม่สนใจเหล่านี้
ผู้ชายสองคนและตอนนี้อย่างใดอย่างหนึ่งมากขึ้น

682
00:24:31,350 --> 00:24:32,260
ผ่านนี้

683
00:24:32,260 --> 00:24:33,490
หกว่าเป็นจำนวนที่ค่อนข้างเล็ก

684
00:24:33,490 --> 00:24:34,300
มาข้างหน้า

685
00:24:34,300 --> 00:24:35,220
โอ้ขอโทษ

686
00:24:35,220 --> 00:24:37,640
จำนวนของเกรซจะดีกว่า
ดังนั้นขั้นตอนในข้างหน้า

687
00:24:37,640 --> 00:24:38,260
สี่

688
00:24:38,260 --> 00:24:39,120
ขออภัยเกรซ,

689
00:24:39,120 --> 00:24:39,950
กลับไปอีกครั้ง

690
00:24:39,950 --> 00:24:41,550
บ้านเลขที่สามจะดีกว่า

691
00:24:41,550 --> 00:24:42,290
เจ็ด

692
00:24:42,290 --> 00:24:42,720
ห้า

693
00:24:42,720 --> 00:24:43,550
และตอนนี้คุณชื่ออะไรอีก?

694
00:24:43,550 --> 00:24:44,000
>> JASON: เจสัน

695
00:24:44,000 --> 00:24:44,420
>> เดวิดเจลัน: เจสัน

696
00:24:44,420 --> 00:24:47,050
ดังนั้นเจสันอยู่ในขณะนี้มีขนาดเล็กที่สุด
องค์ประกอบที่ผมได้เลือกไว้

697
00:24:47,050 --> 00:24:49,160
เขาเป็นคนที่จะไป?

698
00:24:49,160 --> 00:24:50,380
เพื่อที่หกคือ

699
00:24:50,380 --> 00:24:51,210
และชื่อของคุณอีกครั้ง?

700
00:24:51,210 --> 00:24:51,710
>> gabe: เกบ

701
00:24:51,710 --> 00:24:52,340
>> เดวิดเจลัน: เกบ

702
00:24:52,340 --> 00:24:53,220
เกบในทาง

703
00:24:53,220 --> 00:24:54,640
สิ่งที่ง่ายที่สุดที่จะทำคืออะไร?

704
00:24:54,640 --> 00:24:58,390
Swap สองคนเหล่านี้และดำเนินการต่อ

705
00:24:58,390 --> 00:24:59,020
ดังนั้นตอนนี้เรามาดู

706
00:24:59,020 --> 00:25:00,170
ขนาดเล็กที่สุดของใคร?

707
00:25:00,170 --> 00:25:01,030
สี่

708
00:25:01,030 --> 00:25:01,990
ผมขอแค่โกง

709
00:25:01,990 --> 00:25:03,090
ห้าเป็นไปได้น้อยที่สุด

710
00:25:03,090 --> 00:25:05,220
ฉันคิดว่าต่อไปถ้าคุณต้องการที่จะก้าว
ไปข้างหน้าผมมีอะไรจะทำอย่างไรกับ

711
00:25:05,220 --> 00:25:06,820
คนเหล่านี้มีเกบ?

712
00:25:06,820 --> 00:25:08,450
Swap อีกครั้ง

713
00:25:08,450 --> 00:25:10,740
ดังนั้นตอนนี้ยังคงเล็กน้อยออกคำสั่ง

714
00:25:10,740 --> 00:25:14,140
ผมพบว่าเกบจะมีขนาดเล็กที่สุดดังนั้น
ผมปรากฏเขาออกไปกว่าพวกคุณ

715
00:25:14,140 --> 00:25:15,190
และทำ

716
00:25:15,190 --> 00:25:17,200
>> ดังนั้นคำตอบจะเหมือนกัน

717
00:25:17,200 --> 00:25:18,600
ผลลัพธ์ที่ได้คือเดียวกัน

718
00:25:18,600 --> 00:25:22,730
ซึ่งของทั้งสองขั้นตอนวิธีการ
ที่ดีกว่า

719
00:25:22,730 --> 00:25:23,500
คนที่สองผมได้ยิน

720
00:25:23,500 --> 00:25:24,252
ทำไม?

721
00:25:24,252 --> 00:25:25,900
>> ลำโพงที่ 3: มัน n ขั้นตอน [ได้ยิน]

722
00:25:25,900 --> 00:25:27,600
>> ลันเดวิดเจ: มัน n ขั้นตอนที่มากที่สุด

723
00:25:27,600 --> 00:25:28,490
น่าสนใจ

724
00:25:28,490 --> 00:25:30,610
ดังนั้นจึงเป็นแม้ว่า?

725
00:25:30,610 --> 00:25:33,630
ดังนั้นผมจึงไม่หาวิธี
องค์ประกอบที่เล็กที่สุด?

726
00:25:33,630 --> 00:25:37,060
ผมไม่กี่ขั้นตอนที่ต้องใช้เวลา
หาองค์ประกอบที่เล็กที่สุด?

727
00:25:37,060 --> 00:25:39,220
ผมมองทุกทาง
ที่สิ้นสุดใช่มั้ย?

728
00:25:39,220 --> 00:25:41,530
เพราะในกรณีที่เลวร้ายที่สุดว่าสิ่งที่
ถ้านีลถูกกว่าที่นี่?

729
00:25:41,530 --> 00:25:45,700
ดังนั้นเพียงแค่การค้นหาองค์ประกอบที่เล็กที่สุด
ฉันจะใช้เวลาขั้นตอน n หรือ n ลบ 1

730
00:25:45,700 --> 00:25:46,100
แต่ตกลง

731
00:25:46,100 --> 00:25:46,980
ดังนั้นการแก้ไขปัญหานีล

732
00:25:46,980 --> 00:25:48,740
โปรดจำไว้ว่านาทีหรือดังนั้นที่ผ่านมา

733
00:25:48,740 --> 00:25:51,680
>> แต่ฉันไม่หาวิธีต่อไป
องค์ประกอบที่เล็กที่สุด?

734
00:25:51,680 --> 00:25:54,830
มัน n ลบ 1 หรือ n ลบ 2 จริงๆ
จากหมายเลขของขั้นตอน

735
00:25:54,830 --> 00:25:55,440
ตกลงดังนั้น

736
00:25:55,440 --> 00:25:57,390
ดังนั้นผมจึงไม่ n ลบ 2

737
00:25:57,390 --> 00:25:57,600
ทั้งหมดขวา

738
00:25:57,600 --> 00:25:59,130
เพื่อให้รู้สึกดีขึ้นเล็กน้อย

739
00:25:59,130 --> 00:25:59,730
ทั้งหมดขวา

740
00:25:59,730 --> 00:26:03,270
กี่ครั้งต่อไปตามขั้นตอน
เพื่อหาเลขที่สาม?

741
00:26:03,270 --> 00:26:04,420
ดังนั้น n ลบ 4

742
00:26:04,420 --> 00:26:07,670
จึงลดลงน้อยกว่าหนึ่ง
ขั้นตอนในแต่ละซ้ำ

743
00:26:07,670 --> 00:26:08,740
ดังนั้นนี้ไม่รู้สึกดีขึ้นใช่มั้ย?

744
00:26:08,740 --> 00:26:13,450
ถ้าครั้งสุดท้ายที่มันเป็นประมาณ n n ครั้ง,
เวลานี้มันเป็น n ลบ 1 บวก n ลบ

745
00:26:13,450 --> 00:26:16,500
2, n บวกลบ 3 บวก n
ลบ 4 จุดจุดจุด

746
00:26:16,500 --> 00:26:18,750
แต่ถ้าคุณจำจากโรงเรียนมัธยมของคุณ
ตำราโกงเล็ก ๆ น้อย ๆ

747
00:26:18,750 --> 00:26:24,380
แผ่นหลังที่มีสูตรถ้า
คุณเพิ่มขึ้นของตัวเลขชุดนี้

748
00:26:24,380 --> 00:26:31,280
จำนวนรวมของขั้นตอนคือสิ่งที่
เป็นไปได้ว่าผมใช้ที่นี่?

749
00:26:31,280 --> 00:26:36,580
>> นี้เป็นหนึ่งในบรรดาเช่น n ลบ
1, n ครั้งโดยแบ่งออกเป็น 2

750
00:26:36,580 --> 00:26:39,040
เพื่อให้ฉันดูว่าฉันสามารถดึง
ขึ้นรอสักครู่นี้

751
00:26:39,040 --> 00:26:42,230
และอีกครั้งที่ฉันชนิดของการปัดเศษบาง
ตัวเลขเพียงเพื่อให้ชีวิตของเราง่าย

752
00:26:42,230 --> 00:26:47,830
แต่ที่ผมจำได้ว่ามันเป็นอะไรบางอย่างเช่นถ้า
ที่ฉันทำ n ลบ 1 สิ่ง n นั้นลบ

753
00:26:47,830 --> 00:26:53,570
2, n นั้นลบ 3 ก็ประมาณ
บางอย่างเช่นนี้กว่า 2 และถ้าฉัน

754
00:26:53,570 --> 00:26:55,510
คูณออกนี้ว่า
จริงตาราง n

755
00:26:55,510 --> 00:26:58,940
ที่ไม่ได้มีความรู้สึกที่ดีเกินไป
n ลบ n กว่า 2

756
00:26:58,940 --> 00:27:00,350
>> แต่นี่คือสิ่งที่

757
00:27:00,350 --> 00:27:03,720
ในวิทยาการคอมพิวเตอร์ปัญหาเมื่อ
เริ่มได้รับที่น่าสนใจคือเมื่อ n

758
00:27:03,720 --> 00:27:04,700
ได้รับขนาดใหญ่จริงๆ

759
00:27:04,700 --> 00:27:08,110
และเมื่อได้รับ n ขนาดใหญ่จริงๆซึ่ง
ค่าเหล่านี้เป็นไปครองทั้งหมด

760
00:27:08,110 --> 00:27:09,750
ของคนอื่น?

761
00:27:09,750 --> 00:27:10,990
เป็นชนิด n squared ขวา?

762
00:27:10,990 --> 00:27:13,340
ใช่หารด้วย 2 เป็นสิ่งที่ดีสวย

763
00:27:13,340 --> 00:27:16,740
แต่ถ้าคุณกำลังพูดถึงพันล้าน
จากชิ้นส่วนของข้อมูลหรือล้านล้าน

764
00:27:16,740 --> 00:27:18,700
ชิ้นส่วนของข้อมูล, OK เพื่อ
คุณสองครั้งเร็วที่สุดเท่าที่

765
00:27:18,700 --> 00:27:22,440
แต่จริงๆที่ใส่ใจถ้าจำนวนขนาดใหญ่ที่,
ถ้าปัจจัยนี้เป็นสิ่งที่ได้รับ

766
00:27:22,440 --> 00:27:23,040
ใหญ่และขนาดใหญ่

767
00:27:23,040 --> 00:27:25,990
และแน่นอนมันทำให้มากขึ้น
ความแตกต่างกว่าผู้ชายคนนี้

768
00:27:25,990 --> 00:27:29,120
ดังนั้นแม้ว่าพวกคุณมีสิทธิ
อัลกอริทึมที่สองเราจะเรียกมันว่า

769
00:27:29,120 --> 00:27:32,970
เรียงลำดับการคัดเลือกคือในโลกแห่งความจริง
บิตได้เร็วขึ้นอาจเพราะผม

770
00:27:32,970 --> 00:27:35,360
การน้อยลงและน้อยลง
ทำตามขั้นตอนในแต่ละครั้ง

771
00:27:35,360 --> 00:27:37,340
>> มันไม่จริงพื้นฐานได้เร็วขึ้น

772
00:27:37,340 --> 00:27:41,430
เพราะถ้าเราเล่นจริงนี้ออกมา
ค่าที่มากที่สุดในตอนท้ายของ

773
00:27:41,430 --> 00:27:44,750
วันสำหรับ n ขนาดใหญ่พอก็ยังคง
จะให้ความรู้สึกสวยช้า

774
00:27:44,750 --> 00:27:46,770
ดีให้ฉันใช้เวลาหนึ่ง
ผ่านล่าสุดที่ว่า

775
00:27:46,770 --> 00:27:48,920
นั่นคือสิ่งที่ฉันจะเรียก
เรียงลำดับการเลือก

776
00:27:48,920 --> 00:27:51,040
พวกคุณสามารถตั้งค่าด้วยตัวเอง
เป็นครั้งสุดท้าย?

777
00:27:51,040 --> 00:27:53,550
และในกรณีล่าสุดนี้ฉันจะ
เพื่อนำเสนอบางสิ่งบางอย่าง

778
00:27:53,550 --> 00:27:54,970
เรียกว่าจัดเรียงแทรก

779
00:27:54,970 --> 00:27:57,470
จัดเรียงแทรกเป็น, แนวคิด,
บิตที่แตกต่าง

780
00:27:57,470 --> 00:28:00,980
>> มากกว่าจะกลับมาและ
การเลือกองค์ประกอบที่เล็กที่สุดของผม

781
00:28:00,980 --> 00:28:05,030
เพียงจะจัดการกับแต่ละเหล่านี้
ผู้ชายที่ฉันพบพวกเขาและใส่

782
00:28:05,030 --> 00:28:06,850
พวกเขาเข้าไปในสถานที่ที่ถูกต้องของพวกเขา

783
00:28:06,850 --> 00:28:10,160
ดังนั้นฉันแค่จะเริ่มต้นกับเกรซ,
และฉันเห็นว่าเธอเป็นบ้านเลขที่สี่

784
00:28:10,160 --> 00:28:11,720
บ้านเลขที่สี่ที่ไม่เป็น?

785
00:28:11,720 --> 00:28:14,940
ผมยังไม่ได้เริ่มการเรียงลำดับอะไร
ดังนั้นเกรซได้รับจะอยู่ที่นั่น

786
00:28:14,940 --> 00:28:18,355
และตอนนี้ฉันจะเรียกร้องหากคุณสามารถ
จะใช้ขั้นตอนทางด้านขวาของคุณนี้

787
00:28:18,355 --> 00:28:21,650
รายการที่จัดเรียงของฉันนี้เป็นของฉัน
รายการที่เหลืออยู่คัดเลือก

788
00:28:21,650 --> 00:28:23,260
ดังนั้นตอนนี้ฉันจะไปดำเนินการต่อไป
และสิ่งที่ชื่อของคุณอีกครั้ง?

789
00:28:23,260 --> 00:28:23,700
>> แบรนสัน:

790
00:28:23,700 --> 00:28:24,150
>> เดวิดเจลัน: แบรนสัน

791
00:28:24,150 --> 00:28:25,375
ดังนั้นแบรนสันหมายเลขสองคือ

792
00:28:25,375 --> 00:28:27,490
ดังนั้นฉันจะนำคุณ
ออกสักครู่

793
00:28:27,490 --> 00:28:30,940
และตอนนี้คุณที่เป็น
ในอาร์เรย์นี้

794
00:28:30,940 --> 00:28:32,360
ดังนั้นทางด้านขวาของเกรซ

795
00:28:32,360 --> 00:28:35,670
ดังนั้นอีกครั้งเราไม่ชนิดของการทำ
เกรซทำมากของการทำงานที่นี่

796
00:28:35,670 --> 00:28:37,290
เราจะทำให้คุณได้ที่ไหน?

797
00:28:37,290 --> 00:28:40,120
ดังนั้นเรากำลังจะเลื่อนคุณไปยัง
ซ้ายและใส่แบรนสันมี

798
00:28:40,120 --> 00:28:41,680
แต่ตอนนี้ฉันอ้างว่า
พวกคุณจะทำ

799
00:28:41,680 --> 00:28:43,240
แต่แจ้งให้ทราบฉันไม่ได้ใช้พื้นที่พิเศษ

800
00:28:43,240 --> 00:28:45,130
ก็ยังคงองค์ประกอบ 2
ที่นี่ 5 กว่าที่นี่

801
00:28:45,130 --> 00:28:47,910
ขนาดอาร์เรย์รวมคือ 7 ดังนั้นฉัน
ไม่ได้โกงทั้งหมดใช่มั้ย?

802
00:28:47,910 --> 00:28:51,950
>> ดังนั้นตอนนี้เรามีกับเกบที่นี่
หมายเลขหกที่คุณเป็น?

803
00:28:51,950 --> 00:28:52,650
คุณโชคดีอีกครั้ง

804
00:28:52,650 --> 00:28:53,820
ดังนั้นคุณจะได้รับจะอยู่ที่นั่น

805
00:28:53,820 --> 00:28:57,210
เพียงใช้เวลาขั้นตอนเล็กน้อยไปทางขวา
เพียงเพื่อให้ชัดเจนว่าคุณกำลังจัดเรียง

806
00:28:57,210 --> 00:29:00,520
และตอนนี้เรามีนีลอีกครั้งจำนวน
หนึ่งคุณจะไปไหน?

807
00:29:00,520 --> 00:29:03,540
และตอนนี้เป็นที่ที่เราจะเริ่มที่จะเห็นว่า
ขั้นตอนวิธีนี้แม้ในครั้งแรก

808
00:29:03,540 --> 00:29:05,950
อย่างรวดเร็วรู้สึกสมาร์ทสวยดู
เกี่ยวกับการเกิดขึ้นสิ่ง

809
00:29:05,950 --> 00:29:07,370
หากคุณสามารถก้าวไปข้างหน้า

810
00:29:07,370 --> 00:29:09,260
>> เราไม่ต้องการที่จะนำนีลที่ไหน?

811
00:29:09,260 --> 00:29:11,830
ดังนั้นเห็นได้ชัดว่าที่นี่ดังนั้นวิธี
เราจะได้รับนีลมี?

812
00:29:11,830 --> 00:29:12,970
ขอทำขั้นตอนนี้โดยขั้นตอน

813
00:29:12,970 --> 00:29:15,620
เกบที่คุณจำเป็นต้องไป?

814
00:29:15,620 --> 00:29:19,590
อ้างเพื่อใช้ในขั้นตอนเดียวขนาดใหญ่
หรือขั้นตอนที่สองครึ่งหนึ่งที่จะทำให้

815
00:29:19,590 --> 00:29:20,820
ขั้นตอนหนึ่งที่นั่น

816
00:29:20,820 --> 00:29:21,750
เกรซ, คุณจะไปที่ไหน?

817
00:29:21,750 --> 00:29:22,510
ดี

818
00:29:22,510 --> 00:29:23,500
ขั้นตอนอื่นดังนั้น

819
00:29:23,500 --> 00:29:24,960
และในที่สุด? แบรนสัน

820
00:29:24,960 --> 00:29:25,460
ขั้นตอนอื่น

821
00:29:25,460 --> 00:29:27,190
และตอนนี้เราสามารถใส่เข้าไปในสถานที่นีล

822
00:29:27,190 --> 00:29:28,440
>> ดังนั้นตอนนี้ยังคงตรรกะนี้

823
00:29:28,440 --> 00:29:32,420
แม้ว่าเราจะไม่ได้ขยับนีล
มากกว่าและเหนือและมากกว่าที่จะใส่เขา

824
00:29:32,420 --> 00:29:36,420
ที่เขาจะไปในกรณีที่เลวร้ายที่สุด
หมายเลขถัดไปที่เราอาจพบได้

825
00:29:36,420 --> 00:29:42,220
เป็นหมายเลขกล่าวมีจำนวนเป็น
ศูนย์แล้วเราจะเปลี่ยนทุก

826
00:29:42,220 --> 00:29:42,730
คนเหล่านี้

827
00:29:42,730 --> 00:29:44,950
สมมติว่ามีจำนวนลบ
หนึ่งแล้วเราต้องเปลี่ยน

828
00:29:44,950 --> 00:29:46,080
ทั้งหมดของคนเหล่านี้

829
00:29:46,080 --> 00:29:48,500
ดังนั้นเราจริงๆเพียงแค่ชนิดของการพลิก
ปัญหาที่อยู่รอบตัวเช่นว่าเรา

830
00:29:48,500 --> 00:29:52,620
การถ่ายโอนค่าใช้จ่ายจาก
ขั้นตอนการคัดเลือกเพื่อแทรก

831
00:29:52,620 --> 00:29:56,930
กระบวนการดังกล่าวว่าพวกคุณก็มี
บางสิ่งบางอย่างที่จะย้ายประมาณ n ลบ

832
00:29:56,930 --> 00:29:57,940
จำนวนขั้นตอน

833
00:29:57,940 --> 00:30:01,200
และจำนวนของขั้นตอนที่เป็นเพียงการไป
ที่จะเพิ่มขึ้นในขณะที่ฉันเลือกตัวเลขมากขึ้น

834
00:30:01,200 --> 00:30:04,730
ถ้าฉันจะต้องเก็บผลักพวกคุณ
กลับมาและกลับไปและกลับ

835
00:30:04,730 --> 00:30:08,320
>> ดังนั้นสิ่งที่น่าเศร้าในขณะนี้คือสิ่งเหล่านี้
อัลกอริทึมที่มี n squared

836
00:30:08,320 --> 00:30:10,570
ให้ไปข้างหน้าและขอบคุณที่เหล่านี้
ผู้ชายและเห็นภาพเหล่านี้บิต

837
00:30:10,570 --> 00:30:11,090
ต่างกัน

838
00:30:11,090 --> 00:30:12,312
ทำได้ดีมาก

839
00:30:12,312 --> 00:30:14,120
>> [APPLAUSE]

840
00:30:14,120 --> 00:30:15,030
>> ทั้งหมดขวา

841
00:30:15,030 --> 00:30:16,280
มีคุณไป

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
ขอบคุณสำหรับ -

844
00:30:18,470 --> 00:30:19,190
>> แบรนสัน: [เงียบสงัด] ตัวเลขให้

845
00:30:19,190 --> 00:30:21,990
>> เดวิดเจลัน: ไม่มีคุณอาจ
เก็บตัวเลขเช่นกัน

846
00:30:21,990 --> 00:30:23,440
ทั้งหมดขวา

847
00:30:23,440 --> 00:30:24,100
ทำได้อย่างดี

848
00:30:24,100 --> 00:30:25,300
ทั้งหมดขวา

849
00:30:25,300 --> 00:30:30,510
ดังนั้นขอดูว่าเราสามารถสรุปได้ในขณะนี้
มากขึ้นอย่างรวดเร็วและอื่น ๆ สายตา

850
00:30:30,510 --> 00:30:33,410
สิ่งที่เพิ่งเกิดขึ้น
ที่นี่ดังต่อไปนี้

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
ฉันจะไปข้างหน้า
และดึงขึ้น Firefox

853
00:30:38,770 --> 00:30:41,310
เราจะเชื่อมโยงการสาธิตนี้
บนเว็บไซต์ของหลักสูตร

854
00:30:41,310 --> 00:30:43,870
Java เป็นบิตที่น่ารำคาญที่จะได้รับการทำงาน
ในเบราว์เซอร์บางวันนี้

855
00:30:43,870 --> 00:30:46,760
ดังนั้นหากคุณเล่นกับที่บ้าน,
ตระหนักถึงคุณอาจจำเป็นต้องใช้ Firefox

856
00:30:46,760 --> 00:30:47,990
เพื่อให้มันทำงาน

857
00:30:47,990 --> 00:30:50,440
และสิ่งที่ฉันจะทำอย่างไรกับนี้
การสาธิตเป็นดังต่อไปนี้

858
00:30:50,440 --> 00:30:54,875
>> ที่ด้านล่างที่ฉันมีทั้งกลุ่ม
ตัวเลือกเมนูรวมทั้งเริ่มต้นและ

859
00:30:54,875 --> 00:30:55,840
ปุ่มหยุด

860
00:30:55,840 --> 00:30:59,450
ยังเป็นกันดูเหมือนว่าจะมี
ข้อผิดพลาดในโปรแกรมเหล่านี้ whereby คุณ

861
00:30:59,450 --> 00:31:03,720
ไม่สามารถเห็นจริงเริ่มต้นหรือหยุด
ปุ่มถ้าคุณถือคำสั่งหรือ Alt

862
00:31:03,720 --> 00:31:06,560
บวกและซูมซึ่งอยากรู้อยากเห็น
จะแสดงปุ่มอื่น ๆ

863
00:31:06,560 --> 00:31:09,090
ดังนั้นเพียง FYI ถ้าคุณเล่น
กับเรื่องนี้ที่บ้าน

864
00:31:09,090 --> 00:31:12,870
ตอนนี้ฉันกำลังจะไปคลิกเริ่มต้นในเวลาเพียง
ช่วงเวลาหลังจากที่การระบุล่าช้า,

865
00:31:12,870 --> 00:31:16,810
เช่น 200 มิลลิเซกที่นี่เพียง
เพื่อให้เราสามารถดูสิ่งที่เกิดขึ้น

866
00:31:16,810 --> 00:31:20,180
>> ดังนั้นผมจึงเรียกร้องว่านี่คือการสร้างภาพ
ของขั้นตอนวิธีแรก

867
00:31:20,180 --> 00:31:23,730
คนเหล่านี้ไม่ได้เรียงลำดับฟองด้วยเหตุนี้
เราเปลี่ยนคนทั้งคู่ที่ชาญฉลาด

868
00:31:23,730 --> 00:31:27,490
ข้อมูลเชิงลึกที่สำคัญในการสร้างภาพ
คือความสูงของบาร์

869
00:31:27,490 --> 00:31:30,510
แสดงขนาดของจำนวน

870
00:31:30,510 --> 00:31:32,210
ดังนั้นสูงบาร์,
ขนาดใหญ่จำนวน

871
00:31:32,210 --> 00:31:33,680
สั้นบาร์ขนาดเล็กจำนวน

872
00:31:33,680 --> 00:31:38,630
และถ้าคุณสังเกตเห็นว่าเรากำลังจะผ่าน
ย้ำครั้งแรกของอัลกอริทึมนี้

873
00:31:38,630 --> 00:31:42,620
การแลกเปลี่ยนตัวเลขใหญ่และขนาดเล็กเพื่อที่ว่า
ขนาดเล็กจำนวนมากมาก่อนและ

874
00:31:42,620 --> 00:31:44,280
จำนวนมากไปขวา

875
00:31:44,280 --> 00:31:48,770
>> และทันทีที่เราได้รับในตอนท้ายของอาร์เรย์
ของตัวเลขอื่น ๆ อีกมากมายกว่าเจ็ดเราไม่

876
00:31:48,770 --> 00:31:49,900
จะไปกลับไปที่จุดเริ่มต้น

877
00:31:49,900 --> 00:31:51,140
และคาดว่าจะมีนี้

878
00:31:51,140 --> 00:31:54,860
บนซ้ายสุดที่แต่งตัวประหลาดเล็กน้อยที่เกิดขึ้น
สลับไปที่ด้านข้างและนี้

879
00:31:54,860 --> 00:31:56,010
กระบวนการซ้ำ

880
00:31:56,010 --> 00:31:59,450
ตอนนี้ภาพนี้ได้อย่างรวดเร็วได้รับ
น่าเบื่อเพื่อให้ฉันไปข้างหน้าและหยุด

881
00:31:59,450 --> 00:32:04,170
มันมีการเปลี่ยนแปลงบางสิ่งบางอย่างล่าช้ามาก
ได้เร็วขึ้นเพียงเพื่อให้ได้ตอนนี้ความรู้สึกสำหรับ

882
00:32:04,170 --> 00:32:05,060
ขั้นตอนวิธีนี้

883
00:32:05,060 --> 00:32:07,840
>> ดังนั้นแม้ว่าฉันเร่งความเร็วขึ้นนี้เป็น
เช่นเดียวกับการอัพเกรดโปรเซสเซอร์ของฉันซื้อ

884
00:32:07,840 --> 00:32:08,580
คอมพิวเตอร์เครื่องใหม่

885
00:32:08,580 --> 00:32:12,980
ฉันยังไม่ได้เปลี่ยนแปลงโดยพื้นฐานของฉัน
อัลกอริทึม แต่คุณแน่นอนสามารถดูรายละเอียดเพิ่มเติม

886
00:32:12,980 --> 00:32:16,800
อย่างเห็นได้ชัดกว่าด้วยมนุษย์ที่ใหญ่
ตัวเลขจะเดือดปุด ๆ ขึ้นไปด้านบน,

887
00:32:16,800 --> 00:32:20,900
และขนาดเล็กจำนวนมากกำลังเดือดปุด ๆ
ลงไปด้านล่าง

888
00:32:20,900 --> 00:32:22,390
และตอนนี้สิ่งนี้แยกที่นี่

889
00:32:22,390 --> 00:32:25,260
และในขณะที่ข้างในสี่เหลี่ยมมี
เพียงแค่ทำบัญชีมีบาง

890
00:32:25,260 --> 00:32:28,010
ช่วยให้คุณนับการเปรียบเทียบหลายวิธี
หรือกี่แลกเปลี่ยนได้

891
00:32:28,010 --> 00:32:28,950
กระทำจริง

892
00:32:28,950 --> 00:32:30,750
>> ดีขอลองหนึ่ง
คนอื่น ๆ ที่เราเห็น

893
00:32:30,750 --> 00:32:37,116
ให้ฉันคลิกที่การจัดเรียงฟองที่นี่และ
ให้ฉันเลือกและหน้าเว็บทั้งหมดนี้

894
00:32:37,116 --> 00:32:38,936
เป็นรถเล็ก ๆ น้อย ๆ

895
00:32:38,936 --> 00:32:41,155
ขอยอมรับความเสี่ยง
และเรียกใช้อีกครั้ง

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
มีที่เราไป

898
00:32:45,030 --> 00:32:47,180
ดังนั้นขอเรียงลำดับการเลือกทำ

899
00:32:47,180 --> 00:32:49,140
ผมไม่ทราบว่าทำไมเมนู
ปรากฏขึ้นที่นั่น

900
00:32:49,140 --> 00:32:54,070
ลองซูมในการแก้ไขปัญหาที่
ข้อผิดพลาดให้เปลี่ยนเป็น 50

901
00:32:54,070 --> 00:32:56,020
Ah ให้ทำจริง
ที่เร็วขึ้นมาก

902
00:32:56,020 --> 00:32:59,160
ห้ามิลลิวินาทีหรือดังนั้นและเริ่ม

903
00:32:59,160 --> 00:33:00,470
>> ดังนั้นนี่คือการจัดเรียงการเลือก

904
00:33:00,470 --> 00:33:03,070
ดังนั้นอีกครั้งคิดเกี่ยวกับสิ่งที่เรา
ทำกับมนุษย์ขึ้นที่นี่

905
00:33:03,070 --> 00:33:08,490
เราเดินผ่านแถวและเลือก
องค์ประกอบที่เล็กที่สุดอีกครั้ง

906
00:33:08,490 --> 00:33:09,250
และอีกครั้งและอีกครั้ง

907
00:33:09,250 --> 00:33:11,110
ตอนนี้ฉันอ้างว่ายังคงไม่ดีงาม

908
00:33:11,110 --> 00:33:15,010
มันเป็น n ยังคงยกให้หรือใช้เวลา,
แต่มันก็อยู่ในโลกแห่งความเป็นจริงบิต

909
00:33:15,010 --> 00:33:18,280
ได้เร็วขึ้นเพราะผมแน่นอนการ
เล็กน้อยน้อยลงตามขั้นตอนในแต่ละครั้ง

910
00:33:18,280 --> 00:33:19,800
แต่เรากำลังพูดถึงเฉพาะอะไร

911
00:33:19,800 --> 00:33:21,830
อาจจะ 40 หรือเพื่อให้แท่งที่นี่?

912
00:33:21,830 --> 00:33:23,200
เราไม่ได้พูดถึง 40 ล้าน

913
00:33:23,200 --> 00:33:27,430
ดังนั้นจึงเป็นไปไม่ได้โดยสิ้นเชิงชัดเจนกับผมว่า
เป็นจริงได้อย่างมีนัยสำคัญ

914
00:33:27,430 --> 00:33:32,530
>> ขอให้ข้าพเจ้ากลับไปและเปลี่ยนไปของเรา
อัลกอริทึมที่สามซึ่งได้รับการเลือก

915
00:33:32,530 --> 00:33:33,180
จัดเรียงแทรก

916
00:33:33,180 --> 00:33:36,380
และตอนนี้ก็เพราะรถจริงๆ
เมนูมันไม่ควรจะลงมี

917
00:33:36,380 --> 00:33:40,840
ดังนั้นตอนนี้เราจะเลื่อนกลับขึ้นไปที่นี่
และเริ่มขั้นตอนวิธีนี้

918
00:33:40,840 --> 00:33:43,270
โห่เริ่มต้นและหยุด

919
00:33:43,270 --> 00:33:47,160
ดังนั้นนี่คือชนิดหนึ่งมีรูปแบบสวย
กับมันด้วยเหตุนี้เราอีกครั้ง

920
00:33:47,160 --> 00:33:50,240
ใส่มนุษย์หรือใน
กรณีนี้เป็นแถบ

921
00:33:50,240 --> 00:33:52,620
ตำแหน่งที่เหมาะสมของพวกเขา

922
00:33:52,620 --> 00:33:55,430
และก็ทำมาแล้วก่อนที่จะ
ผมหันไปรอบ ๆ

923
00:33:55,430 --> 00:33:58,940
แต่คนนี้มากเกินไปในทางทฤษฎี
ยังคง n squared

924
00:33:58,940 --> 00:34:01,430
>> ดังนั้นขอดูว่าเราไม่สามารถสรุป
เหล่านี้ดังต่อไปนี้

925
00:34:01,430 --> 00:34:04,750
ฉันจะไปข้างหน้าและเพียงเพื่อให้
การจัดเรียงของเราวิธีการทั่วไปของการพูดคุย

926
00:34:04,750 --> 00:34:08,489
เกี่ยวกับสิ่งเหล่านี้ให้ฉันแนะนำ
เพียงเล็กน้อยของสัญกรณ์ที่นี่

927
00:34:08,489 --> 00:34:12,480
คุณกำลังจะได้เห็นสิ่งที่เรียกว่าใหญ่
O เพราะมันเป็นตัวอักษรขนาดใหญ่

928
00:34:12,480 --> 00:34:16,320
ทุมและนี่คือวิธีการที่คอมพิวเตอร์
นักวิทยาศาสตร์หรือนักคณิตศาสตร์แม้จะใช้

929
00:34:16,320 --> 00:34:19,230
เพื่ออธิบายถึงเวลาทำงาน
บางส่วนของขั้นตอนวิธี

930
00:34:19,230 --> 00:34:21,400
มันไม่กี่ขั้นตอนจริงใช้เวลา

931
00:34:21,400 --> 00:34:25,080
>> ตอนนี้ฉันกำลังจะไปทำให้เกิดปัญหากับตัวเอง
เขียนด้วยลายมือที่นี่ในช่วงเวลาเพียงแค่ฉัน

932
00:34:25,080 --> 00:34:29,020
แต่ให้ฉันไปข้างหน้าและบอกว่า
นี้จะเป็น O ขนาดใหญ่กว่าที่นี่

933
00:34:29,020 --> 00:34:33,610
และแจ้งให้เราแนะนำคนอื่น ๆ
สัญลักษณ์ทุนโอเมก้า

934
00:34:33,610 --> 00:34:37,080
โอเมก้าเป็นไปได้ที่ตรงข้าม,
เป็นหลักใหญ่ทุมขณะที่ O ใหญ่

935
00:34:37,080 --> 00:34:40,790
หมายถึงในกรณีที่เลวร้ายที่สุดในเวลาเท่าไร
อัลกอริทึมบางคนอาจจะใช้เวลาใน

936
00:34:40,790 --> 00:34:43,480
แง่ของ n, โอเมก้าจะไป
มีวิธีการมากเวลาที่มันอาจจะ

937
00:34:43,480 --> 00:34:45,409
ใช้ในกรณีที่ดีที่สุด

938
00:34:45,409 --> 00:34:48,090
และเราจะเห็นสิ่งที่เราหมายถึง
กรณีที่ดีที่สุดในเวลาเพียงสักครู่

939
00:34:48,090 --> 00:34:49,940
>> เพื่อขอเริ่มต้นสิ่งที่ง่าย

940
00:34:49,940 --> 00:34:54,719
ผมขอเริ่มต้นด้วยการค้นหาเชิงเส้น

941
00:34:54,719 --> 00:34:55,679
ดังนั้นไม่ได้เรียงลำดับ

942
00:34:55,679 --> 00:34:58,000
เราจะเรียกสิ่งนี้ว่าการค้นหาเชิงเส้น

943
00:34:58,000 --> 00:35:01,140
และตอนนี้ให้เล็ก ๆ น้อย ๆ
ตารางออกจากนี้

944
00:35:01,140 --> 00:35:06,600
และตอนนี้ในกรณีของการค้นหาเชิงเส้น,
ในกรณีที่เลวร้ายที่สุดวิธีการหลายขั้นตอนคือ

945
00:35:06,600 --> 00:35:11,770
มันจะพาฉันไปหา
จำนวนของทางเลือกโดยพล?

946
00:35:11,770 --> 00:35:14,540
และมีประตูทั้งหมดของ N
หรือ n ตัวเลขทั้งหมด

947
00:35:14,540 --> 00:35:15,940
กรณีที่เลวร้าย

948
00:35:15,940 --> 00:35:18,800
ฉันวิธีการหลายขั้นตอนที่จะต้อง
ใช้เวลาในการหาจำนวน 50 ในอาร์เรย์

949
00:35:18,800 --> 00:35:20,830
ของประตู n?

950
00:35:20,830 --> 00:35:21,410
และทำไม?

951
00:35:21,410 --> 00:35:23,680
เพราะมันอาจจะมีสิ่ง
วิธีลงบนปลาย

952
00:35:23,680 --> 00:35:27,120
ดังนั้นเหมือนเจนนิเฟอร์พบ
จำนวน 50 คนตลอดทางกว่าดังนั้นใน

953
00:35:27,120 --> 00:35:30,760
กรณีที่เลวร้ายที่สุดการค้นหาเชิงเส้น
เป็น O ใหญ่ของ n เราจะพูด

954
00:35:30,760 --> 00:35:33,430
>> สิ่งที่เกี่ยวกับกรณีที่ดีที่สุด
ถ้าคุณได้รับโชคดีจริงๆ

955
00:35:33,430 --> 00:35:36,200
มันก็จะใช้เวลาหนึ่งขั้นตอนที่
หรือเป็นจำนวนคงที่ของขั้นตอน

956
00:35:36,200 --> 00:35:37,830
ดังนั้นเราจะอธิบายว่าเ​​ป็น 1

957
00:35:37,830 --> 00:35:39,010
ดังนั้นนี่คือที่ดีงาม

958
00:35:39,010 --> 00:35:41,210
ตอนนี้สิ่งที่ถ้าเราทำอะไรบางอย่าง
ชอบค้นหา binary?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
การค้นหาแบบไบนารีดังนั้นในที่เลวร้ายที่สุด
กรณีเอาเวลาเท่าไร

961
00:35:47,846 --> 00:35:49,250
>> [interposing VOICES]

962
00:35:49,250 --> 00:35:51,310
>> เดวิดเจลัน: ดังนั้นจริงผม
ได้ยินมันในสถานที่ที่คู่

963
00:35:51,310 --> 00:35:56,390
ดังนั้นจึงเป็นจริง log N ให้หรือใช้,
เพราะในขณะที่เราแบ่งรายการในช่วงครึ่งปี

964
00:35:56,390 --> 00:36:00,730
อีกครั้งและอีกครั้งและอีกครั้งที่เราไม่สามารถ
เพื่อหาในที่สุดค่า

965
00:36:00,730 --> 00:36:04,750
ถ้ามันมี แต่มีการจับ

966
00:36:04,750 --> 00:36:08,590
สมมติฐานที่ว่าเราจะต้องมีอะไร
เหมาสำหรับการค้นหาแบบไบนารี?

967
00:36:08,590 --> 00:36:09,700
มันจะต้องมีการจัดเรียง

968
00:36:09,700 --> 00:36:12,770
มันไม่ได้เรียงลำดับคุณสามารถแยกสิ่งที่
ในช่วงครึ่งปีอีกครั้งและอีกครั้งและคุณ

969
00:36:12,770 --> 00:36:15,490
สามารถไปทางซ้ายและคุณสามารถไปทางขวาและ
คุณสามารถไปทางซ้ายและขวา แต่คุณ

970
00:36:15,490 --> 00:36:18,070
ไม่ได้ไปหาองค์ประกอบถ้า
รายการจะไม่เรียงเพราะ

971
00:36:18,070 --> 00:36:18,790
คุณอาจจะพลาดมัน

972
00:36:18,790 --> 00:36:22,120
เพราะการแก้ปัญหาของคุณสำหรับการไปซ้าย
หรือขวาเป็นไปได้ข้อบกพร่องถ้ามัน

973
00:36:22,120 --> 00:36:23,420
แน่นอนไม่เรียง

974
00:36:23,420 --> 00:36:26,110
ดังนั้นจึงมีการเรียงลำดับของค่าใช้จ่ายที่ซ่อนของ
ในการใช้บางอย่างเช่นนี้

975
00:36:26,110 --> 00:36:29,250
>> ตอนนี้ขอไปลงในการเรียงลำดับของเรา
อัลกอริทึมการค้นหาไม่ได้ -

976
00:36:29,250 --> 00:36:31,140
โอ้จริงให้เป็นไปในที่ว่างเปล่านี้

977
00:36:31,140 --> 00:36:33,190
การค้นหาแบบไบนารีในกรณีที่ดีที่สุด?

978
00:36:33,190 --> 00:36:36,290
นอกจากนี้ยังเป็น 1 ถ้ามันเพิ่งเกิดขึ้นเป็น
ตรงกลางของอาร์เรย์หรือ

979
00:36:36,290 --> 00:36:37,810
ตรงกลางของสมุดโทรศัพท์

980
00:36:37,810 --> 00:36:39,710
ตอนนี้เรามาจัดเรียงฟองทำ

981
00:36:39,710 --> 00:36:42,570
ดังนั้นอีกครั้งตอนนี้เรากำลังเข้าสู่
แปลก ๆ ไม่ได้ค้นหา

982
00:36:42,570 --> 00:36:47,220
>> ในกรณีที่เลวร้ายที่สุดวิธีการหลายขั้นตอนพวกเรา
จัดเรียงฟองเรียกร้องจะใช้เวลา?

983
00:36:47,220 --> 00:36:48,410
n squared

984
00:36:48,410 --> 00:36:49,200
ดังนั้นฉันจะวาดว่า

985
00:36:49,200 --> 00:36:51,710
Ooh, เขียนด้วยลายมือของฉันดูเหมือนยิ่งแย่ลง
เมื่อมันใหญ่คาดการณ์ว่า

986
00:36:51,710 --> 00:36:52,510
ทั้งหมดขวา

987
00:36:52,510 --> 00:36:53,570
ดังนั้นที่ n squared

988
00:36:53,570 --> 00:36:59,460
และในกรณีที่ดีที่สุดของการจัดเรียงฟอง
มันเป็นวิธีการหลายขั้นตอนจะใช้เวลา?

989
00:36:59,460 --> 00:37:00,980
1 ผมได้ยิน

990
00:37:00,980 --> 00:37:01,760
>> ลำโพง 1: n

991
00:37:01,760 --> 00:37:03,286
>> เดวิดเจลัน: n ผมได้ยิน

992
00:37:03,286 --> 00:37:04,200
>> ลำโพง 1: 2

993
00:37:04,200 --> 00:37:05,010
>> เดวิดเจลัน: 2, ที่ผมได้ยิน

994
00:37:05,010 --> 00:37:06,670
ฉันได้ยิน 3

995
00:37:06,670 --> 00:37:07,080
ทั้งหมดขวา

996
00:37:07,080 --> 00:37:11,390
ดังนั้นผมเคยได้ยิน 1, n, 2, แต่ขอเลือก
นอกเหนืออย่างน้อยเป็นครั้งแรกของเหล่านั้น

997
00:37:11,390 --> 00:37:12,330
ข้อเสนอแนะ 1

998
00:37:12,330 --> 00:37:15,370
มันไม่ได้เป็นสัญชาตญาณที่ไม่ดีเพราะ
ชนิดตามรูปแบบที่นี่

999
00:37:15,370 --> 00:37:19,670
แต่ถ้าจะใช้เวลาเพียง 1 ขั้นตอนวิธีการใน
โลกที่ฉันสามารถเรียกร้องว่ารายการ

1000
00:37:19,670 --> 00:37:22,900
จะเรียงลำดับตามเพราะถ้าฉันได้รับอนุญาตเท่านั้น
ที่จะใช้ขั้นตอนที่ 1 วิธีการหลายองค์ประกอบ

1001
00:37:22,900 --> 00:37:25,230
ที่จริงผมจะตรวจสอบให้แน่ใจว่า?

1002
00:37:25,230 --> 00:37:28,270
ดีเพียง 1 ซึ่งหมายความว่ามี n
ลบ 1 องค์ประกอบที่อาจจะออกจาก

1003
00:37:28,270 --> 00:37:31,310
คำสั่งและฉันแค่ไปหลังจากที่ความเชื่อ
กำลังมองหาที่ 1 องค์ประกอบที่

1004
00:37:31,310 --> 00:37:31,850
สิ่งที่จะเรียง

1005
00:37:31,850 --> 00:37:33,930
1 ดังนั้นไม่ถูกต้องที่นี่

1006
00:37:33,930 --> 00:37:35,710
ดังนั้นอย่างน้อยที่สุดกี่
ฉันต้องมองหา?

1007
00:37:35,710 --> 00:37:36,680
>> [interposing VOICES]

1008
00:37:36,680 --> 00:37:40,160
>> เดวิดเจลัน: n ลบ 1 หรือจริงๆ
n เพราะผมต้องดูที่ทุก

1009
00:37:40,160 --> 00:37:42,190
องค์ประกอบเพื่อให้แน่ใจว่า
ยังไม่ได้ออกคำสั่ง

1010
00:37:42,190 --> 00:37:44,750
แต่อีกครั้งเราจะเรียงลำดับของคลื่นของเรา
มือที่ขนาดเล็กจำนวนมากและ

1011
00:37:44,750 --> 00:37:47,100
สมมติว่าเป็น n ได้รับการขนาดใหญ่ที่พวกเขากำลัง
น่าทึ่งแล้ว

1012
00:37:47,100 --> 00:37:48,380
เพื่อให้การจัดเรียงฟอง

1013
00:37:48,380 --> 00:37:49,830
และตอนนี้เราจะมาทำเหล่านี้สองคนสุดท้าย

1014
00:37:49,830 --> 00:37:53,520
การจัดเรียงที่เลือกแล้วเราจะ
จะเรียงลำดับการแทรก

1015
00:37:53,520 --> 00:37:57,160
แล้วเราจะพัดของคุณ
จิตใจที่มีบางสิ่งบางอย่างมาก

1016
00:37:57,160 --> 00:37:58,926
ดีกว่าสิ่งเหล่านี้

1017
00:37:58,926 --> 00:38:00,410
ทั้งหมดขวา

1018
00:38:00,410 --> 00:38:04,700
>> กรณีที่เลวร้ายทำงานคืออะไร
เวลาของการจัดเรียงการเลือก?

1019
00:38:04,700 --> 00:38:05,680
>> 4 SPEAKER: n squared

1020
00:38:05,680 --> 00:38:06,710
>> เดวิดเจลัน: n ตารางผมได้ยิน

1021
00:38:06,710 --> 00:38:09,790
แต่ทำไม n ยืด, สังหรณ์ใจ?

1022
00:38:09,790 --> 00:38:11,170
>> 4 SPEAKER: เพราะเราก็ไม่ได้

1023
00:38:11,170 --> 00:38:12,260
>> เดวิดเจลัน: เพราะเราก็ไม่ได้

1024
00:38:12,260 --> 00:38:12,550
ตกลง

1025
00:38:12,550 --> 00:38:13,380
คำตอบที่ดี

1026
00:38:13,380 --> 00:38:16,660
แต่สังหรณ์ใจเลือกเป็นเหตุผลว่าทำไม
จัดเรียง n squared?

1027
00:38:16,660 --> 00:38:18,980
เราไม่ต้องทำอะไร
อีกครั้งและอีกครั้ง?

1028
00:38:18,980 --> 00:38:22,570
เราต้องให้ผ่านการสแกนเป็น
คุณเล็กคุณ

1029
00:38:22,570 --> 00:38:24,020
ที่เล็กที่สุดคุณจะมีขนาดเล็กที่สุด

1030
00:38:24,020 --> 00:38:27,480
รับและเราสามารถที่จะใช้ n
ขั้นตอนแล้ว n ลบ 1, n นั้นลบ 2

1031
00:38:27,480 --> 00:38:30,700
แต่ถ้าคุณเพิ่มชนิดของเหล่านั้นทั้งหมดขึ้น
หรือเอาไว้ในความเชื่อที่ว่าฉันได้เพิ่ม

1032
00:38:30,700 --> 00:38:34,810
พวกเขาขึ้นในอนาคตเราได้รับประมาณ n
squared ลบตัวเลขที่มีขนาดเล็กบาง

1033
00:38:34,810 --> 00:38:36,730
ดังนั้นฉันจะเรียก n นี้ squared

1034
00:38:36,730 --> 00:38:39,530
แต่มีการจัดเรียงในการเลือกที่ดีที่สุด
กรณีวิธีการหลายขั้นตอนมันเป็น

1035
00:38:39,530 --> 00:38:40,632
จะมาจับเรา

1036
00:38:40,632 --> 00:38:41,840
>> 5 SPEAKER: [ได้ยิน]

1037
00:38:41,840 --> 00:38:44,350
>> เดวิดเจลัน: มันน่าเสียดายที่
ยังคง n squared ขวา?

1038
00:38:44,350 --> 00:38:49,590
เพราะถ้าฉันเลือกที่เล็กที่สุด
องค์ประกอบและเรามีเจ็ดคนที่นี่

1039
00:38:49,590 --> 00:38:53,280
ฉันเพียงรู้เมื่อฉันได้รับไปมาก
ท้ายที่ฉันได้พบมีขนาดเล็กที่สุด

1040
00:38:53,280 --> 00:38:55,670
จำนวนใดก็ตามที่เขาหรือ
เธออาจจะรับ

1041
00:38:55,670 --> 00:38:58,820
แต่ฉันจะหาต่อไป
จำนวนที่เล็กที่สุด?

1042
00:38:58,820 --> 00:39:00,160
ที่ฉันต้องทำผ่านอื่น

1043
00:39:00,160 --> 00:39:04,810
ดังนั้นในกรณีที่ดีที่สุดคืออะไร
การป้อนข้อมูลในการเรียงลำดับการเลือก?

1044
00:39:04,810 --> 00:39:07,830
มันเป็นรายการที่จัดเรียงอยู่แล้วจำนวนหนึ่ง,
บ้านเลขที่สอง, สาม, สี่จำนวน

1045
00:39:07,830 --> 00:39:08,600
แต่ฉันคอมพิวเตอร์

1046
00:39:08,600 --> 00:39:10,190
ฉันสามารถมองไปที่หนึ่ง
สิ่งที่เวลา

1047
00:39:10,190 --> 00:39:12,465
ฉันไม่สามารถเรียงลำดับจากจะใช้ขั้นตอน
กลับเหมือนมนุษย์และพูดว่า

1048
00:39:12,465 --> 00:39:14,030
ooh นี้ลักษณะที่ถูกต้อง

1049
00:39:14,030 --> 00:39:17,580
>> ฉันเท่านั้นที่สามารถตัดสินความถูกต้องใน
เรียงลำดับการเลือกโดยการเลือก

1050
00:39:17,580 --> 00:39:18,370
จำนวนที่เล็กที่สุด

1051
00:39:18,370 --> 00:39:21,390
แต่ถึงแม้ว่าฉันพบจำนวนหนึ่งก่อน
ถ้าฉันไม่ได้รู้อะไรเกี่ยวกับคนอื่น

1052
00:39:21,390 --> 00:39:24,460
หมายเลขอื่น ๆ ที่ฉันทำไม่ได้ทั้งหมดที่ฉัน
รู้ว่าฉันได้รับการส่งมอบอาร์เรย์

1053
00:39:24,460 --> 00:39:27,930
หรือชุดของประตูหลังซึ่งเป็น
ตัวเลขวิธีเดียวที่ฉันรู้ว่าหนึ่ง

1054
00:39:27,930 --> 00:39:28,680
เป็นที่เล็กที่สุด?

1055
00:39:28,680 --> 00:39:32,440
ถ้าฉันได้รับทุกอย่างที่นี่และตระหนักถึง
แช่งหนึ่งเป็นจริงน้อยที่สุด

1056
00:39:32,440 --> 00:39:34,870
>> แต่ฉันจะทำอย่างไรแล้วตรวจสอบว่า
สองคือต่อไปที่เล็กที่สุด?

1057
00:39:34,870 --> 00:39:38,350
โดยการทำเช่นเดียวกันขาดประสิทธิภาพ
ครั้งแล้วครั้งเล่า

1058
00:39:38,350 --> 00:39:42,210
ดังนั้นในที่สุดก็มีการจัดเรียงแทรก
วิธีการในกรณีที่เลวร้ายที่สุด

1059
00:39:42,210 --> 00:39:44,990
พวกเราบอกว่าจะดำเนินการ?

1060
00:39:44,990 --> 00:39:49,100
มันก็เป็น n squared

1061
00:39:49,100 --> 00:39:53,020
และวิธีการเกี่ยวกับกับกรณีที่ดีที่สุด?

1062
00:39:53,020 --> 00:39:56,282
เราจะออกจากที่เป็นที่น่าตื่นเต้น

1063
00:39:56,282 --> 00:40:00,090
เราจะกรอกข้อมูลลงในครั้งถัดไปที่ว่างเปล่า
แต่แรกให้ฉันเสนอว่าเรา

1064
00:40:00,090 --> 00:40:02,620
พื้นฐานที่ทำได้ดีกว่า
ทั้งหมดเหล่านี้ขวาทั้งหมดหรือไม่

1065
00:40:02,620 --> 00:40:05,220
>> ดังนั้นคิดว่าสำหรับตัวเองว่าแทรก
จัดเรียงเป็นไปได้

1066
00:40:05,220 --> 00:40:06,910
ดีที่ไม่ได้เป็นที่น่าทึ่งมาก
เพราะฉันเพียงคนเดียว

1067
00:40:06,910 --> 00:40:08,970
ที่เห็นความเปลี่ยนแปลง

1068
00:40:08,970 --> 00:40:09,620
ว้าว

1069
00:40:09,620 --> 00:40:10,420
ตกลง

1070
00:40:10,420 --> 00:40:12,615
ดังนั้นที่นี่เรามีค่อนข้าง
การสาธิตที่แตกต่างกัน

1071
00:40:12,615 --> 00:40:16,580
ถ้าซูมในที่นี่คุณจะเห็นว่าเมื่อ
ด้านซ้ายเรามีการจัดเรียงฟองใน

1072
00:40:16,580 --> 00:40:20,740
กลางเรามีการเรียงลำดับการเลือกและ
ด้านขวาสุดเรามีสิ่งที่เรา

1073
00:40:20,740 --> 00:40:23,380
ไม่ได้มองที่ยัง
รวมเรียกว่าการจัดเรียง

1074
00:40:23,380 --> 00:40:26,080
แต่พิจารณาสิ่งที่เราได้รับ
ทำอะไรที่นี่ป่านนี้วันนี้

1075
00:40:26,080 --> 00:40:29,200
เมื่อเจนนิเฟอร์แรกขึ้นมาบนเวที
เราเดินผ่านแถวของตัวเลข

1076
00:40:29,200 --> 00:40:33,750
อีกครั้งและอีกครั้งกับการค้นหาเชิงเส้น
และเรามีเวลาทำงานเชิงเส้น O ใหญ่

1077
00:40:33,750 --> 00:40:35,100
ของ n เพื่อที่จะพูด

1078
00:40:35,100 --> 00:40:41,000
>> เมื่อเราพิจารณาในขณะนี้สัปดาห์แรกของ
ชั้นเมื่อเราได้แบ่งและพิชิต,

1079
00:40:41,000 --> 00:40:43,740
และสมุดโทรศัพท์ได้เราฉีกขาด,
เจนนิเฟอร์และเราเรียกรวมกัน

1080
00:40:43,740 --> 00:40:47,500
leveraged ว่าข้อมูลเชิงลึกที่สำคัญซึ่งจะ
ซ้ำตัวเองอีกครั้งและอีกครั้งโดย

1081
00:40:47,500 --> 00:40:50,930
อย่างใดทิ้งไปขว้างออกไป
ทิ้งไปครึ่งหนึ่งของปัญหาหรือ

1082
00:40:50,930 --> 00:40:55,320
โดยทั่วไปแบ่งปัญหาในช่วงครึ่งปี,
แล้วรักษาชิ้นส่วนขนาดเล็กของ

1083
00:40:55,320 --> 00:40:59,630
ปัญหาเป็นเทียบเท่าแนวคิด
ไปที่อื่น ๆ เราอย่างใดไม่

1084
00:40:59,630 --> 00:41:00,910
พื้นฐานที่ดีขึ้น

1085
00:41:00,910 --> 00:41:04,720
แต่มีการจัดเรียงฟองกับการเลือก
เรียงลำดับเรียงแทรกกับเราได้อาจ

1086
00:41:04,720 --> 00:41:06,560
ไม่มีข้อมูลเชิงลึกดังกล่าวว่าเจนนิเฟอร์ได้

1087
00:41:06,560 --> 00:41:10,220
เราสวยมากแค่เดินกลับมาและ
มามัดทั้งเวลาและเรา

1088
00:41:10,220 --> 00:41:12,650
สิ่งเอ็นดูนิด ๆ หน่อย ๆ การแลกเปลี่ยน
ในคำสั่งนี้อาจจะ

1089
00:41:12,650 --> 00:41:13,730
ใส่หรือเลือก

1090
00:41:13,730 --> 00:41:16,950
แต่ในตอนท้ายของวันที่ฉันได้มาก
การเดินที่น่าอึดอัดใจกลับมา

1091
00:41:16,950 --> 00:41:21,160
เราไม่ได้บางสิ่งบางอย่างใช้ประโยชน์จริงๆ
สมาร์ทเช่นเจนนิเฟอร์ไม่ต้องการแบ่ง

1092
00:41:21,160 --> 00:41:22,040
และชนะ

1093
00:41:22,040 --> 00:41:25,620
>> ดังนั้นรวมเรียงลำดับโดยคมชัดซึ่งเรา
จะไม่เห็นจนกว่าจะถึงสัปดาห์หน้าก็จะ

1094
00:41:25,620 --> 00:41:29,540
เพื่อยกระดับความคิดที่สำคัญโดยการหาร
การป้อนข้อมูลและจากนั้นลดลงครึ่งหนึ่งและจากนั้น

1095
00:41:29,540 --> 00:41:30,580
ลดลงครึ่งหนึ่งและจากนั้นลดลงครึ่งหนึ่ง

1096
00:41:30,580 --> 00:41:34,590
และในการทำซ้ำของวงที่แต่ละ
การเรียงลำดับซีกซ้ายและขวา

1097
00:41:34,590 --> 00:41:38,200
ครึ่งแล้วครึ่งซ้ายของครึ่งซ้าย,
และอีกครึ่งหนึ่งทางด้านขวาของด้านซ้ายจากนั้น

1098
00:41:38,200 --> 00:41:40,990
ครึ่งซ้ายของครึ่งด้านขวาและ
ครึ่งขวาของครึ่งขวา

1099
00:41:40,990 --> 00:41:42,840
และการทำซ้ำอีกครั้งและอีกครั้ง

1100
00:41:42,840 --> 00:41:46,170
>> ดังนั้นคุณจะเห็นนี้สายตา แต่ตอนนี้
คือสิ่งที่เรารอคอยสัปดาห์ถัดไป

1101
00:41:46,170 --> 00:41:49,760
และโดยทั่วไปเมื่อเราคิดว่าเล็ก ๆ น้อย ๆ
บิตยากขึ้นในการแก้ปัญหาดังกล่าว

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
เราได้ n เหลี่ยมด้านซ้าย, n
squared อยู่ตรงกลางและ n

1104
00:41:57,970 --> 00:41:59,400
log N ด้านขวา

1105
00:41:59,400 --> 00:42:00,590
จึงมีเรื่องราวที่น่าตื่นเต้นที่แท้จริงของคุณ

1106
00:42:00,590 --> 00:42:02,040
เราจะเห็นคุณในวันจันทร์

1107
00:42:02,040 --> 00:42:05,163
>> [APPLAUSE]