1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [เล่นเพลง]

3
00:00:10,800 --> 00:00:13,500
DAVID ลัน: ทั้งหมดขวา

4
00:00:13,500 --> 00:00:14,670
ขวาทั้งหมดยินดีต้อนรับกลับ

5
00:00:14,670 --> 00:00:18,120
ดังนั้นนี้เป็นสัปดาห์ที่ 4, จุดเริ่มต้น
ดังกล่าวแล้ว

6
00:00:18,120 --> 00:00:21,320
และคุณจะจำได้ว่าสัปดาห์ที่ผ่านมาเราใส่
รหัสไว้สำหรับเพียงเล็กน้อย

7
00:00:21,320 --> 00:00:24,240
และเราเริ่มพูดถึงน้อยมาก
ระดับสูงเช่นเดียวกับสิ่งที่เกี่ยวกับ

8
00:00:24,240 --> 00:00:28,130
การค้นหาและการเรียงลำดับซึ่งแม้ว่า
ความคิดที่ค่อนข้างง่ายเป็น

9
00:00:28,130 --> 00:00:31,840
ตัวแทนของชั้นเรียนของปัญหา
คุณจะเริ่มต้นในการแก้ปัญหาโดยเฉพาะอย่างยิ่ง

10
00:00:31,840 --> 00:00:34,820
ในขณะที่คุณเริ่มคิดเกี่ยวกับขั้นสุดท้าย
โครงการและโซลูชั่นที่น่าสนใจคุณ

11
00:00:34,820 --> 00:00:36,760
อาจจะมีปัญหาในโลกจริง

12
00:00:36,760 --> 00:00:39,490
ขณะนี้การจัดเรียงฟองเป็นหนึ่งในที่ง่ายที่สุด
อัลกอริทึมดังกล่าวและมัน

13
00:00:39,490 --> 00:00:42,900
ทำงานโดยมีตัวเลขเล็ก ๆ เหล่านี้
ในรายการหรือในรูปแบบอาร์เรย์ของ

14
00:00:42,900 --> 00:00:46,530
ฟองทางของพวกเขาขึ้นไปด้านบนและ
ตัวเลขใหญ่ย้ายทางของพวกเขาลงไป

15
00:00:46,530 --> 00:00:47,930
ในตอนท้ายของรายการที่

16
00:00:47,930 --> 00:00:50,650
>> และจำได้ว่าเราจะได้เห็นภาพ
จัดเรียงฟองเล็ก ๆ น้อย ๆ

17
00:00:50,650 --> 00:00:52,310
บางอย่างเช่นนี้

18
00:00:52,310 --> 00:00:53,640
เพื่อให้ฉันไปข้างหน้าและคลิกเริ่ม

19
00:00:53,640 --> 00:00:55,350
ผมได้จัดเรียงไว้ล่วงหน้าฟอง

20
00:00:55,350 --> 00:00:58,920
และถ้าคุณจำได้ว่าสีฟ้าสูง
เส้นแสดงตัวเลขขนาดใหญ่ขนาดเล็ก

21
00:00:58,920 --> 00:01:03,300
เส้นสีฟ้าแทนตัวเลขขนาดเล็กเช่น
ที่เราไปผ่านทางนี้อีกครั้งและอีกครั้งและ

22
00:01:03,300 --> 00:01:07,680
อีกครั้งเมื่อเทียบกับสองแท่งถัดจากแต่ละ
อื่น ๆ ในสีแดงเราจะสลับ

23
00:01:07,680 --> 00:01:11,010
ที่ใหญ่ที่สุดและมีขนาดเล็กที่สุดถ้า
พวกเขาจะออกคำสั่ง

24
00:01:11,010 --> 00:01:14,150
>> ดังนั้นนี้จะไปและไปและไป
เมื่อและคุณจะเห็นว่ามีขนาดใหญ่

25
00:01:14,150 --> 00:01:16,700
องค์ประกอบจะทำให้ทางของพวกเขา
ขวาและองค์ประกอบที่มีขนาดเล็กเป็น

26
00:01:16,700 --> 00:01:17,900
การทำทางของพวกเขาไปทางซ้าย

27
00:01:17,900 --> 00:01:21,380
แต่เราก็เริ่มที่จะหาจำนวน
ที่มีประสิทธิภาพ,

28
00:01:21,380 --> 00:01:22,970
คุณภาพของขั้นตอนวิธีนี้

29
00:01:22,970 --> 00:01:25,200
และเรากล่าวว่าในที่เลวร้ายที่สุด
กรณีขั้นตอนวิธีนี้ใช้เวลา

30
00:01:25,200 --> 00:01:27,940
ประมาณกี่ขั้นตอน?

31
00:01:27,940 --> 00:01:28,980
>> ดังนั้น n squared

32
00:01:28,980 --> 00:01:30,402
และสิ่งที่เป็น n?

33
00:01:30,402 --> 00:01:31,650
>> ผู้ชม: จำนวนขององค์ประกอบ

34
00:01:31,650 --> 00:01:32,790
>> DAVID ลัน: ดังนั้น n คือ
จำนวนขององค์ประกอบ

35
00:01:32,790 --> 00:01:33,730
และดังนั้นเราจะทำเช่นนี้มักจะ

36
00:01:33,730 --> 00:01:36,650
เวลาที่เราต้องการพูดคุยเกี่ยวกับขนาดใด ๆ
ของปัญหาหรือขนาดของ

37
00:01:36,650 --> 00:01:39,140
การป้อนข้อมูลหรือปริมาณของเวลาที่ใช้
ในการผลิตส่งออกเราจะเพียงแค่

38
00:01:39,140 --> 00:01:41,610
สิ่งที่ทั่วไป
อินพุตเป็น n

39
00:01:41,610 --> 00:01:45,970
ดังนั้นกลับมาในสัปดาห์ 0 จำนวนหน้า
ในสมุดโทรศัพท์ n คือ

40
00:01:45,970 --> 00:01:47,550
จำนวนนักเรียน
ในห้องพักที่ได้รับการ n

41
00:01:47,550 --> 00:01:49,630
ดังนั้นที่นี่, เกินไปเรากำลังต่อไปนี้
ว่ารูปแบบ

42
00:01:49,630 --> 00:01:52,800
>> ตอนนี้ n ยกกำลังสองไม่ได้โดยเฉพาะอย่างยิ่ง
อย่างรวดเร็วดังนั้นเราจึงพยายามที่จะทำดีกว่า

43
00:01:52,800 --> 00:01:55,970
และเพื่อให้เรามองไปที่คู่ของ
ขั้นตอนวิธีการอื่น ๆ ในระหว่างที่

44
00:01:55,970 --> 00:01:57,690
เรียงลำดับการเลือกเป็น

45
00:01:57,690 --> 00:01:59,180
เรียงลำดับดังนั้นการเลือกเป็น
แตกต่างกันเล็กน้อย

46
00:01:59,180 --> 00:02:03,130
มันก็เกือบจะง่ายผมกล้าพูด,
ด้วยเหตุนี้ผมเริ่มที่จุดเริ่มต้นของ

47
00:02:03,130 --> 00:02:06,740
รายการของอาสาสมัครของเราและฉันเพียงแค่อีกครั้ง
และอีกครั้งและอีกครั้งที่เดินผ่าน

48
00:02:06,740 --> 00:02:10,060
รายการถอนขนออกที่เล็กที่สุด
องค์ประกอบในเวลาและทำให้เขาหรือ

49
00:02:10,060 --> 00:02:13,040
ของเธอที่จุดเริ่มต้นของรายการ

50
00:02:13,040 --> 00:02:16,410
>> แต่เรื่องนี้ก็เช่นกันเมื่อเราเริ่มคิดว่า
ผ่านทางคณิตศาสตร์และขนาดใหญ่

51
00:02:16,410 --> 00:02:19,860
ภาพความคิดเกี่ยวกับวิธีการหลายครั้ง
ผมก็จะกลับมาและกลับ

52
00:02:19,860 --> 00:02:24,090
มาเรากล่าวว่าในกรณีที่เลวร้ายที่สุด
เรียงลำดับการเลือกเกินไปคือสิ่งที่?

53
00:02:24,090 --> 00:02:24,960
n squared

54
00:02:24,960 --> 00:02:27,490
ขณะนี้อยู่ในโลกแห่งความจริงมันอาจ
เป็นจริงได้เร็วขึ้นเล็กน้อย

55
00:02:27,490 --> 00:02:30,620
เพราะอีกครั้งฉันไม่ได้มีเพื่อให้
ย้อนรอยเมื่อฉันได้เรียงลำดับ

56
00:02:30,620 --> 00:02:31,880
เป็นส่วนประกอบเล็ก ๆ

57
00:02:31,880 --> 00:02:35,090
แต่ถ้าเราคิดเกี่ยวกับการมีขนาดใหญ่มาก n และ
ถ้าคุณเรียงลำดับของการทำออกมาเป็นคณิตศาสตร์

58
00:02:35,090 --> 00:02:39,170
ฉันไม่ได้อยู่ในคณะกรรมการด้วย n squared
สิ่งที่ลบทุกอย่างอื่น

59
00:02:39,170 --> 00:02:41,850
นอกจาก n squared เมื่อ n
ได้รับมีขนาดใหญ่จริงๆไม่ได้

60
00:02:41,850 --> 00:02:42,850
จริงๆเรื่องมาก

61
00:02:42,850 --> 00:02:45,470
เพื่อให้เป็นนักวิทยาศาสตร์คอมพิวเตอร์เราจัดเรียงจาก
เอาหูไปนาเอาตามีขนาดเล็ก

62
00:02:45,470 --> 00:02:49,220
ปัจจัยและมุ่งเน้นเฉพาะปัจจัยใน
นิพจน์ที่จะทำให้

63
00:02:49,220 --> 00:02:50,330
ความแตกต่างที่ยิ่งใหญ่ที่สุด

64
00:02:50,330 --> 00:02:52,840
>> ดีสุดท้ายเรามอง
ที่จัดเรียงแทรก

65
00:02:52,840 --> 00:02:56,620
และนี่คือที่คล้ายกันในจิตวิญญาณ แต่
มากกว่าที่จะไปผ่านซ้ำและ

66
00:02:56,620 --> 00:03:01,250
เลือกองค์ประกอบหนึ่งที่เล็กที่สุดที่
เวลาที่ฉันแทนเอามือของผม

67
00:03:01,250 --> 00:03:04,070
ได้รับการจัดการและฉันตัดสินใจทั้งหมด
ขวาคุณอยู่ที่นี่

68
00:03:04,070 --> 00:03:06,160
จากนั้นผมย้ายไปยังองค์ประกอบต่อไป
และตัดสินใจว่าเขาหรือ

69
00:03:06,160 --> 00:03:07,470
เธอเป็นที่นี่

70
00:03:07,470 --> 00:03:08,810
และจากนั้นผมย้ายบนและบน

71
00:03:08,810 --> 00:03:11,780
และผมอาจจะไปพร้อมกัน
เปลี่ยนคนเหล่านี้เพื่อที่จะ

72
00:03:11,780 --> 00:03:13,030
ทำให้ห้องสำหรับพวกเขา

73
00:03:13,030 --> 00:03:16,880
เพื่อให้เป็นที่จัดเรียงของการกลับใจ
ของการจัดเรียงที่เราเลือก

74
00:03:16,880 --> 00:03:18,630
เรียกว่าจัดเรียงแทรก

75
00:03:18,630 --> 00:03:20,810
>> ดังนั้นเรื่องเหล่านี้จะเกิดขึ้น
ในโลกแห่งความจริง

76
00:03:20,810 --> 00:03:23,640
เพียงไม่กี่ปีที่ผ่านมาเมื่อบางอย่าง
สมาชิกวุฒิสภาได้รับการเลือกตั้งเป็นประธานาธิบดี,

77
00:03:23,640 --> 00:03:27,160
เอริคชมิดท์ในเวลานั้นซีอีโอของ
Google จริงมีโอกาส

78
00:03:27,160 --> 00:03:28,040
ที่จะสัมภาษณ์เขา

79
00:03:28,040 --> 00:03:32,010
และเราคิดว่าเราต้องการแบ่งปัน YouTube นี้
คลิปสำหรับคุณที่นี่ถ้าเราสามารถเปิดขึ้น

80
00:03:32,010 --> 00:03:32,950
ปริมาณ

81
00:03:32,950 --> 00:03:39,360
>> [เล่นภาพวิดีโอ]

82
00:03:39,360 --> 00:03:44,620
>> ตอนนี้วุฒิสมาชิกคุณที่นี่ที่ Google,
และผมชอบที่จะคิดว่าการเป็นประธานาธิบดี

83
00:03:44,620 --> 00:03:46,042
ในขณะที่การสัมภาษณ์งาน

84
00:03:46,042 --> 00:03:47,770
>> [เสียงหัวเราะ]

85
00:03:47,770 --> 00:03:50,800
>> ตอนนี้มันยากที่จะได้รับ
งานในฐานะประธาน

86
00:03:50,800 --> 00:03:52,480
และคุณกำลังจะผ่าน
ความโหดร้ายในขณะนี้

87
00:03:52,480 --> 00:03:54,330
นอกจากนี้ยังเป็นเรื่องยากที่จะได้งานที่ Google

88
00:03:54,330 --> 00:03:59,610
เรามีคำถามและเราขอ
คำถามที่ผู้สมัครของเรา

89
00:03:59,610 --> 00:04:02,250
และหนึ่งในนี้มาจาก Larry Schwimmer

90
00:04:02,250 --> 00:04:05,325
>> [เสียงหัวเราะ]

91
00:04:05,325 --> 00:04:06,400
-พวกคุณคิดว่าฉันล้อเล่น?

92
00:04:06,400 --> 00:04:08,750
มันถูกต้องที่นี่

93
00:04:08,750 --> 00:04:12,110
วิธีที่มีประสิทธิภาพมากที่สุดที่จะคืออะไร
จัดเรียงล้านจำนวนเต็มสองบิต?

94
00:04:12,110 --> 00:04:15,810
>> [เสียงหัวเราะ]

95
00:04:15,810 --> 00:04:18,260
>> ดี, UH -

96
00:04:18,260 --> 00:04:19,029
>> I'm-เสียใจ

97
00:04:19,029 --> 00:04:19,745
บางทีเราควร -

98
00:04:19,745 --> 00:04:21,000
>> ไม่มีไม่ไม่ไม่ไม่

99
00:04:21,000 --> 00:04:21,470
>> ที่ไม่ได้ -

100
00:04:21,470 --> 00:04:22,185
ตกลง

101
00:04:22,185 --> 00:04:25,328
>> ผมคิดว่าการจัดเรียงฟองจะ
เป็นวิธีที่ผิดไป

102
00:04:25,328 --> 00:04:26,792
>> [เสียงหัวเราะ]

103
00:04:26,792 --> 00:04:28,510
>> [โห่ร้องปรบมือ]

104
00:04:28,510 --> 00:04:31,211
>> -Come เมื่อใครบอกเขานี้

105
00:04:31,211 --> 00:04:32,155
ตกลง

106
00:04:32,155 --> 00:04:33,350
>> [เล่นวิดีโอจบ]

107
00:04:33,350 --> 00:04:35,070
>> DAVID ลัน: จึงมีคุณมีมัน

108
00:04:35,070 --> 00:04:39,600
ดังนั้นเราจึงเริ่มที่จะหาจำนวนเหล่านี้ทำงาน
ครั้งจึงจะพูดกับสิ่งที่

109
00:04:39,600 --> 00:04:43,480
ที่เรียกว่าสัญกรณ์เชิงซึ่งเป็น
เพียงหมายถึงการจัดเรียงของเราของการเปลี่ยน

110
00:04:43,480 --> 00:04:47,420
ตาบอดให้กับผู้ที่มีขนาดเล็กและปัจจัย
เพียงมองหาที่เวลาทำงาน,

111
00:04:47,420 --> 00:04:51,250
ประสิทธิภาพการทำงานของอัลกอริทึมเหล่านี้
เป็น n ได้รับขนาดใหญ่จริงๆเมื่อเวลาผ่านไป

112
00:04:51,250 --> 00:04:55,110
และเพื่อให้เรานำใหญ่ทุมและ O ใหญ่
สิ่งที่แสดงว่าเราคิดว่า

113
00:04:55,110 --> 00:04:57,000
ในฐานะที่เป็นขีด จำกัด บน

114
00:04:57,000 --> 00:04:59,570
และที่จริงแบร์​​รี่เราสามารถลด
กว่าไมค์นิด ๆ หน่อย ๆ ?

115
00:04:59,570 --> 00:05:01,040
>> เราคิดว่าของที่นี่คือขีด จำกัด บน

116
00:05:01,040 --> 00:05:04,710
ดังนั้น Big O หมายถึง squared n ว่าใน
กรณีที่เลวร้ายบางอย่างเช่น

117
00:05:04,710 --> 00:05:07,780
เรียงลำดับการเลือกที่จะใช้เวลา
n ขั้นตอน squared

118
00:05:07,780 --> 00:05:10,310
หรือสิ่งที่ต้องการจัดเรียงแทรก
n squared ขั้นตอนจะ

119
00:05:10,310 --> 00:05:15,150
ตอนนี้สำหรับสิ่งที่ต้องการแทรก
เรียงลำดับสิ่งที่เป็นกรณีที่เลวร้าย?

120
00:05:15,150 --> 00:05:18,200
ให้อาร์เรย์ที่เลวร้ายที่สุดสิ่ง
สถานการณ์ที่เป็นไปได้ที่คุณอาจพบ

121
00:05:18,200 --> 00:05:20,650
ตัวเองต้องเผชิญกับ?

122
00:05:20,650 --> 00:05:21,860
>> มันสมบูรณ์ไปข้างหลังใช่มั้ย?

123
00:05:21,860 --> 00:05:24,530
เพราะถ้ามันสมบูรณ์ไปข้างหลัง
ที่คุณต้องทำมากทั้งจากการทำงาน

124
00:05:24,530 --> 00:05:26,420
เพราะถ้าคุณไม่สมบูรณ์ไปข้างหลัง
คุณกำลังจะไปหา

125
00:05:26,420 --> 00:05:28,840
องค์ประกอบที่ใหญ่ที่สุดของที่นี่แม้ว่า
มันเป็นของที่นั่น

126
00:05:28,840 --> 00:05:31,140
ดังนั้นคุณจะพูดขวาทั้งหมดที่
ขณะนี้ในเวลาที่คุณอยู่ที่นี่,

127
00:05:31,140 --> 00:05:32,310
เพื่อให้คุณทิ้งไว้คนเดียว

128
00:05:32,310 --> 00:05:35,425
>> แล้วคุณจะรู้ว่าโอ้แช่งฉันต้อง
ย้ายองค์ประกอบเล็ก ๆ น้อย ๆ ไป

129
00:05:35,425 --> 00:05:36,470
ทางด้านซ้ายของคุณ

130
00:05:36,470 --> 00:05:38,770
แล้วฉันต้องทำเช่นนั้นอีกครั้ง
และอีกครั้งและอีกครั้ง

131
00:05:38,770 --> 00:05:41,410
และถ้าผมเดินกลับมาที่คุณ
จะเรียงลำดับจากความรู้สึกประสิทธิภาพการทำงานของ

132
00:05:41,410 --> 00:05:45,540
อัลกอริทึมที่เพราะตลอดเวลาที่ฉัน
สับคนอื่นลงไปใน

133
00:05:45,540 --> 00:05:46,510
อาร์เรย์เพื่อให้ห้องพักสำหรับมัน

134
00:05:46,510 --> 00:05:47,750
ดังนั้นกรณีที่เลวร้ายที่สุด

135
00:05:47,750 --> 00:05:48,570
>> ตรงกันข้าม -

136
00:05:48,570 --> 00:05:50,320
และนี่ก็เป็นที่น่าตื่นเต้นเป็นครั้งสุดท้าย -

137
00:05:50,320 --> 00:05:54,065
เรากล่าวว่าเรียงแทรกว่า
โอเมก้าของสิ่งที่เป็น?

138
00:05:54,065 --> 00:05:57,530
การทำงานกรณีที่ดีที่สุดคืออะไร
ช่วงเวลาของการจัดเรียงแทรก?

139
00:05:57,530 --> 00:05:58,520
ดังนั้นจึงไม่ระบุจริง

140
00:05:58,520 --> 00:06:00,980
นั่นคือว่างที่เราเหลือ
บนกระดานครั้งสุดท้าย

141
00:06:00,980 --> 00:06:03,160
>> และมันก็เป็นของโอเมก้า n เพราะทำไม?

142
00:06:03,160 --> 00:06:06,630
ทั้งในกรณีที่ดีที่สุดคืออะไร
จัดเรียงแทรกจะส่ง?

143
00:06:06,630 --> 00:06:09,830
ดีรายการที่จัดเรียงอย่างสมบูรณ์
แล้วการทำงานน้อยที่สุดที่จะทำ

144
00:06:09,830 --> 00:06:12,460
แต่สิ่งที่เกี่ยวกับระเบียบเรียงแทรกสิ่ง
ว่าเป็นเพราะมันเริ่มต้นที่นี่และ

145
00:06:12,460 --> 00:06:15,340
ตัดสินใจโอ้คุณเป็นจำนวน
หนึ่งคุณอยู่ที่นี่

146
00:06:15,340 --> 00:06:16,970
โอ้สิ่งที่โชคดี

147
00:06:16,970 --> 00:06:17,740
>> คุณหมายเลขสอง

148
00:06:17,740 --> 00:06:19,030
นอกจากนี้คุณยังเป็นส่วนหนึ่งของที่นี่

149
00:06:19,030 --> 00:06:21,010
บ้านเลขที่สามดียิ่งขึ้น
คุณอยู่ที่นี่

150
00:06:21,010 --> 00:06:25,210
ทันทีที่ได้รับไปยังจุดสิ้นสุดของ
pseudocode รายการจัดเรียงแทรกต่อของ

151
00:06:25,210 --> 00:06:28,010
ที่เราเดินผ่านด้วยวาจา
ครั้งสุดท้ายที่มันทำ

152
00:06:28,010 --> 00:06:32,790
แต่การเลือกจัดเรียงโดยคมชัด,
เก็บไว้ทำในสิ่งที่?

153
00:06:32,790 --> 00:06:35,260
>> เก็บไปผ่านรายการ
อีกครั้งและอีกครั้งและอีกครั้ง

154
00:06:35,260 --> 00:06:39,160
เพราะข้อมูลเชิงลึกที่สำคัญมีเพียง
เมื่อคุณมองไปทาง

155
00:06:39,160 --> 00:06:42,500
ตอนท้ายของรายการที่คุณสามารถแน่ใจได้
ว่าองค์ประกอบที่คุณเลือกคือ

156
00:06:42,500 --> 00:06:45,560
แน่นอนองค์ประกอบที่เล็กที่สุดในปัจจุบัน

157
00:06:45,560 --> 00:06:48,920
เหล่านี้แตกต่างกันในตอนท้ายรุ่นจิตดังนั้น
ขึ้นน่วมบางมากโลกแห่งความจริง

158
00:06:48,920 --> 00:06:53,130
ความแตกต่างสำหรับเราเช่นเดียวกับเหล่านี้
ความแตกต่างเชิงทฤษฎี

159
00:06:53,130 --> 00:06:56,910
>> ดังนั้นเพียงเพื่อปะยางรถแล้ว O ใหญ่ของ n
เหลี่ยมที่เราเคยเห็นไม่กี่เช่น

160
00:06:56,910 --> 00:06:58,350
อัลกอริทึมป่านนี้

161
00:06:58,350 --> 00:06:59,580
O ใหญ่ของ n?

162
00:06:59,580 --> 00:07:02,870
อัลกอริทึมที่ได้มีอะไร
จะกล่าวว่าเป็น O ใหญ่ของ n?

163
00:07:02,870 --> 00:07:06,930
ในกรณีที่เลวร้ายที่สุดก็จะใช้เวลา
จำนวนเชิงเส้นของขั้นตอน

164
00:07:06,930 --> 00:07:07,810
>> ตกลงค้นหาเชิงเส้น

165
00:07:07,810 --> 00:07:10,470
และในกรณีที่เลวร้ายที่สุดที่เป็น
องค์ประกอบที่คุณกำลังมองหาเมื่อ

166
00:07:10,470 --> 00:07:12,950
ใช้ค้นหาเชิงเส้น?

167
00:07:12,950 --> 00:07:14,680
>> ตกลงในกรณีที่เลวร้ายที่สุด
ก็ไม่ได้มี

168
00:07:14,680 --> 00:07:17,000
หรือในกรณีที่เลวร้ายที่สุดที่สองก็
ทุกวิธีในท้ายที่สุดซึ่งเป็น

169
00:07:17,000 --> 00:07:18,880
บวกหรือลบแตกต่างขั้นตอนเดียว

170
00:07:18,880 --> 00:07:21,180
ดังนั้นในตอนท้ายของวันที่
เราสามารถบอกว่ามันเป็นเชิงเส้น

171
00:07:21,180 --> 00:07:23,910
O ใหญ่ของ n จะค้นหาเชิงเส้น,
เพราะในกรณีที่เลวร้ายที่สุด

172
00:07:23,910 --> 00:07:26,610
องค์ประกอบที่ไม่ได้มีหรือเป็น
ทุกทางที่สิ้นสุด

173
00:07:26,610 --> 00:07:29,370
>> ดี O ใหญ่ของบันทึกของ n

174
00:07:29,370 --> 00:07:32,760
เราไม่ได้พูดคุยในรายละเอียดที่ดีเกี่ยวกับ
นี้ แต่เราเคยเห็นแบบนี้มาก่อน

175
00:07:32,760 --> 00:07:36,840
ทำงานในสิ่งที่เรียกว่าลอการิทึมอะไร
เวลาในกรณีที่เลวร้ายที่สุด?

176
00:07:36,840 --> 00:07:38,500
>> บันทึกการค้นหาแบบไบนารีดังนั้น

177
00:07:38,500 --> 00:07:42,930
และการค้นหาแบบไบนารีในกรณีที่เลวร้ายที่สุด
อาจจะมีองค์ประกอบบางแห่งใน

178
00:07:42,930 --> 00:07:45,640
กลางหรือที่ไหนสักแห่ง
ภายในอาร์เรย์

179
00:07:45,640 --> 00:07:48,040
แต่คุณจะพบว่ามันเมื่อคุณ
แบ่งรายการในครึ่งปีใน

180
00:07:48,040 --> 00:07:48,940
ครึ่งหนึ่งในช่วงครึ่งในช่วงครึ่ง

181
00:07:48,940 --> 00:07:50,200
แล้ว voila, ก็มี

182
00:07:50,200 --> 00:07:52,500
หรืออีกกรณีที่เลวร้ายที่สุด
ก็ไม่ได้มี

183
00:07:52,500 --> 00:07:56,770
แต่คุณไม่ได้รู้ว่ามันไม่ได้มี
จนกว่าคุณจะเรียงลำดับของการเข้าถึงที่ล่าสุด

184
00:07:56,770 --> 00:08:00,470
องค์ประกอบด้านล่างมากที่สุดโดยลดลงครึ่งหนึ่ง
และลดลงครึ่งหนึ่งและลดลงครึ่งหนึ่ง

185
00:08:00,470 --> 00:08:01,400
>> Big O 1

186
00:08:01,400 --> 00:08:03,540
ดังนั้นเราจึง O ใหญ่ 2, O ใหญ่จาก 3

187
00:08:03,540 --> 00:08:06,260
เวลาที่คุณต้องการเพียงจำนวนคงที่
เราเพียงแค่การจัดเรียงของเพียงแค่ลดความซับซ้อน

188
00:08:06,260 --> 00:08:07,280
ที่เป็นใหญ่ O 1

189
00:08:07,280 --> 00:08:10,440
ถึงแม้ว่าถ้าแนบเนียนก็จะใช้เวลา
2 หรือ 100 ขั้นตอนถ้ามัน

190
00:08:10,440 --> 00:08:13,680
จำนวนคงที่ของขั้นตอน
เราเพียงแค่พูดว่า O ใหญ่จากทั้งหมด 1

191
00:08:13,680 --> 00:08:15,930
อัลกอริทึมที่อะไร
ใน O ใหญ่ 1?

192
00:08:15,930 --> 00:08:18,350
>> ผู้ชม: การหาระยะเวลา
ของตัวแปร

193
00:08:18,350 --> 00:08:21,090
>> DAVID ลัน: การหา
ความยาวของตัวแปร?

194
00:08:21,090 --> 00:08:23,870
>> ผู้ชม: ไม่มีระยะเวลา
ถ้ามันเรียงแล้ว

195
00:08:23,870 --> 00:08:24,160
>> DAVID ลัน: ดี

196
00:08:24,160 --> 00:08:27,850
OK เพื่อหาระยะเวลาของบางสิ่งบางอย่าง
ถ้าความยาวของสิ่งที่เหมือน

197
00:08:27,850 --> 00:08:30,020
อาร์เรย์จะถูกเก็บไว้ในตัวแปรบาง

198
00:08:30,020 --> 00:08:33,380
เพราะคุณก็สามารถอ่านตัวแปร,
หรือพิมพ์ตัวแปรหรือ

199
00:08:33,380 --> 00:08:34,960
เพียงทั่วไปเข้าถึงตัวแปรที่

200
00:08:34,960 --> 00:08:37,299
และ voila, ที่ต้องใช้เวลาคงที่

201
00:08:37,299 --> 00:08:38,909
>> ตรงกันข้ามกลับคิดว่าที่จะเกา

202
00:08:38,909 --> 00:08:42,460
คิดกลับไปในสัปดาห์แรกของ C,
เพียงโทร printf และการพิมพ์

203
00:08:42,460 --> 00:08:46,240
บางสิ่งบางอย่างบนหน้าจอเป็น arguably
เวลาคงเพราะมันใช้เวลาเพียง

204
00:08:46,240 --> 00:08:50,880
บางส่วนของจำนวนรอบการทำงานที่จะแสดง
ข้อความบนหน้าจอว่า

205
00:08:50,880 --> 00:08:52,720
หรือรอ - ไม่ได้หรือไม่

206
00:08:52,720 --> 00:08:56,430
วิธีการอื่นที่เราอาจจะสร้างแบบจำลอง
ประสิทธิภาพการทำงานของ printf?

207
00:08:56,430 --> 00:09:00,420
ใครบางคนต้องการที่จะไม่เห็นด้วยที่
บางทีมันอาจจะไม่ได้ตลอดเวลาจริงๆ

208
00:09:00,420 --> 00:09:03,600
สิ่งที่รู้สึกอาจ printf ทำงาน
เวลาพิมพ์จริงสตริง

209
00:09:03,600 --> 00:09:05,580
หน้าจอเป็นสิ่งที่
อื่นที่ไม่ใช่ค่าคงที่

210
00:09:05,580 --> 00:09:07,860
>> ผู้ชม: [ได้ยิน]

211
00:09:07,860 --> 00:09:08,230
>> DAVID ลัน: ใช่

212
00:09:08,230 --> 00:09:09,300
ดังนั้นมันขึ้นอยู่กับมุมมองของเรา

213
00:09:09,300 --> 00:09:13,390
ถ้าเราคิดว่าจริงของท่านไป
printf เป็นสตริงและ

214
00:09:13,390 --> 00:09:16,380
ดังนั้นเราจึงวัดขนาดจากที่
ป้อนข้อมูลตามความยาวของมัน - ดังนั้นขอเรียก

215
00:09:16,380 --> 00:09:17,780
ระยะเวลาที่ n เช่นกัน -

216
00:09:17,780 --> 00:09:21,990
เนื้อหา printf ตัวเองเป็น O ใหญ่ของ n
เพราะมันจะนำคุณ n ขั้นตอน

217
00:09:21,990 --> 00:09:24,750
เพื่อพิมพ์แต่ละ n เหล่านั้น
ตัวอักษรได้มากที่สุด

218
00:09:24,750 --> 00:09:27,730
อย่างน้อยที่สุดเท่าที่เราคิด
ว่าบางทีมันอาจจะใช้สำหรับวง

219
00:09:27,730 --> 00:09:28,560
ภายใต้ฝากระโปรง

220
00:09:28,560 --> 00:09:30,860
>> แต่เราจะต้องมองไปที่ว่า
รหัสที่จะเข้าใจมันได้ดียิ่งขึ้น

221
00:09:30,860 --> 00:09:33,650
และแน่นอนเมื่อพวกคุณเริ่มต้น
การวิเคราะห์ขั้นตอนวิธีการของตัวเองของคุณคุณจะ

222
00:09:33,650 --> 00:09:34,900
แท้จริงทำแค่นั้น

223
00:09:34,900 --> 00:09:37,765
เรียงจากลูกตาและคิดว่ารหัสของคุณ
เกี่ยวกับ - สิทธิทั้งหมดที่ฉันมีห่วงนี้

224
00:09:37,765 --> 00:09:41,870
ที่นี่หรือฉันมีลูปซ้อนกันที่นี่
ที่จะทำในสิ่งที่ n n ครั้ง

225
00:09:41,870 --> 00:09:46,050
และคุณสามารถเรียงลำดับของเหตุผลในแบบของคุณ
รหัสผ่าน, แม้ว่าจะเป็น

226
00:09:46,050 --> 00:09:47,980
รหัสเทียมและไม่ได้เกิดขึ้นจริง

227
00:09:47,980 --> 00:09:49,730
>> ดังนั้นสิ่งที่เกี่ยวกับโอเมก้าของ n squared?

228
00:09:49,730 --> 00:09:53,582
สิ่งที่อัลกอริทึมคือการที่ดีที่สุดใน
กรณีที่ยังคงเอา n squared ขั้นตอน?

229
00:09:53,582 --> 00:09:54,014
อ้าง?

230
00:09:54,014 --> 00:09:54,880
>> ผู้ชม: [ได้ยิน]

231
00:09:54,880 --> 00:09:55,900
>> DAVID ลัน: เรียงลำดับการเลือกดังนั้น

232
00:09:55,900 --> 00:09:59,150
เพราะปัญหาที่ลดลงจริงๆ
ความจริงที่ว่าอีกครั้งผมไม่ทราบว่า

233
00:09:59,150 --> 00:10:02,600
ฉันได้พบจนถึงปัจจุบันมีขนาดเล็กที่สุด
ผมได้ตรวจสอบทุกองค์ประกอบสาป

234
00:10:02,600 --> 00:10:08,050
โอเมก้าดังนั้นจากการพูด, n เรา
เพียงแค่ขึ้นมาด้วยหนึ่ง

235
00:10:08,050 --> 00:10:09,300
จัดเรียงแทรก

236
00:10:09,300 --> 00:10:12,370
ถ้ารายการที่เกิดขึ้นต้องเรียงลำดับ
แล้วในกรณีที่ดีที่สุดที่เราเพียงแค่มี

237
00:10:12,370 --> 00:10:15,090
ที่จะทำให้หนึ่งผ่านมัน
จุดที่เราแน่ใจว่า

238
00:10:15,090 --> 00:10:17,890
แล้วว่าอาจจะพูดได้
เป็นเชิงเส้นเพื่อตรวจสอบว่า

239
00:10:17,890 --> 00:10:20,570
>> สิ่งที่เกี่ยวกับโอเมก้าจาก 1?

240
00:10:20,570 --> 00:10:23,790
ว่าในกรณีที่ดีที่สุดอาจใช้เวลา
จำนวนคงที่ของขั้นตอน?

241
00:10:23,790 --> 00:10:27,220
ค้นหาเชิงเส้นดังนั้นถ้าคุณเพิ่งได้รับโชคดี
และองค์ประกอบที่คุณกำลังมองหา

242
00:10:27,220 --> 00:10:31,000
เป็นสิทธิที่จุดเริ่มต้นของรายการ,
ถ้านั่นคือสิ่งที่คุณจะเริ่มต้นของคุณ

243
00:10:31,000 --> 00:10:33,070
ตรงข้ามของรายการที่

244
00:10:33,070 --> 00:10:35,180
>> และนี่คือที่แท้จริงของ
จำนวนของสิ่งที่

245
00:10:35,180 --> 00:10:37,660
ยกตัวอย่างเช่นไบนารีแม้
ค้นหาเป็นโอเมก้าจาก 1

246
00:10:37,660 --> 00:10:40,310
เพราะสิ่งที่ถ้าคุณได้รับยี้จริงๆ
โชคดีและตี-ตบเบา ๆ ในช่วงกลางของ

247
00:10:40,310 --> 00:10:42,950
อาร์เรย์ของคุณคือจำนวน
คุณกำลังมองหา?

248
00:10:42,950 --> 00:10:45,730
เพื่อให้คุณสามารถได้รับโชคดีที่นั่นเช่นกัน

249
00:10:45,730 --> 00:10:49,190
>> หนึ่งในที่สุดของโอเมก้า n log n

250
00:10:49,190 --> 00:10:52,573
ดังนั้น n log n, ที่เราทำไม่ได้จริงๆ
พูดคุยเกี่ยวกับ แต่ -

251
00:10:52,573 --> 00:10:53,300
>> ผู้ชม: ผสานเรียงลำดับ?

252
00:10:53,300 --> 00:10:53,960
>> DAVID ลัน: จัดเรียงผสาน

253
00:10:53,960 --> 00:10:56,920
นั่นคือเรื่องราวที่น่าตื่นเต้นของเวลาที่ผ่านมา
ที่เรานำเสนอและเราแสดงให้เห็นว่า

254
00:10:56,920 --> 00:10:58,600
สายตาว่ามีขั้นตอนวิธีการเป็น

255
00:10:58,600 --> 00:11:02,470
และผสานการเรียงลำดับของเพียงหนึ่งเช่น
อัลกอริทึมที่เป็นพื้นฐานได้เร็วขึ้น

256
00:11:02,470 --> 00:11:03,450
กว่าบางส่วนของคนอื่น ๆ เหล่านี้

257
00:11:03,450 --> 00:11:07,800
ในความเป็นจริงผสานสั้นไม่เพียง แต่ใน
กรณีที่ดีที่สุด n n log ในที่เลวร้ายที่สุด

258
00:11:07,800 --> 00:11:09,460
กรณี n log n

259
00:11:09,460 --> 00:11:14,540
และเมื่อคุณมีความบังเอิญนี้
โอเมก้าและ O ใหญ่เป็นสิ่งเดียวกัน

260
00:11:14,540 --> 00:11:17,310
จริงเราสามารถอธิบายได้ว่าเป็นอะไร
ที่เรียกว่าทีแม้ว่าจะ

261
00:11:17,310 --> 00:11:18,220
เล็ก ๆ น้อย ๆ ร่วมกันน้อยลง

262
00:11:18,220 --> 00:11:21,730
แต่นั่นก็หมายความสองขอบเขต
ในกรณีนี้จะเหมือนกัน

263
00:11:21,730 --> 00:11:25,770
>> ดังนั้นผสานการเรียงลำดับนี้ไม่สิ่งที่
จริงๆเดือดลงไปสำหรับเรา?

264
00:11:25,770 --> 00:11:27,000
ดีจำแรงจูงใจ

265
00:11:27,000 --> 00:11:30,340
ผมขอดึงภาพเคลื่อนไหวที่อื่น
เราไม่ได้มองไปที่ครั้งสุดท้าย

266
00:11:30,340 --> 00:11:33,390
อันนี้ความคิดที่เหมือนกัน แต่
มันเป็นน้อยใหญ่

267
00:11:33,390 --> 00:11:36,160
และฉันจะไปข้างหน้าและชี้ให้เห็น
ครั้งแรก - เรามีการจัดเรียงแทรกเมื่อ

268
00:11:36,160 --> 00:11:39,410
ด้านซ้ายบนเรียงลำดับการเลือกแล้ว
จัดเรียงฟองคู่ของประเภทอื่น ๆ -

269
00:11:39,410 --> 00:11:42,670
เปลือกและรวดเร็ว - ที่เราไม่ได้พูดคุย
เกี่ยวกับกองและตัดจัดเรียง

270
00:11:42,670 --> 00:11:47,090
>> ดังนั้นอย่างน้อยพยายามที่จะมุ่งเน้นไปที่ตาของคุณเมื่อ
สามด้านบนด้านซ้ายและแล้ว

271
00:11:47,090 --> 00:11:49,120
ผสานการเรียงลำดับเมื่อฉันคลิก
นี้ลูกศรสีเขียว

272
00:11:49,120 --> 00:11:51,900
แต่ฉันจะให้ทั้งหมดของพวกเขาทำงานเพียงเพื่อ
ให้ความรู้สึกของความหลากหลายของ

273
00:11:51,900 --> 00:11:53,980
อัลกอริทึมที่มีอยู่ในโลก

274
00:11:53,980 --> 00:11:56,180
ฉันจะปล่อยให้การทำงานนี้
สำหรับเพียงไม่กี่วินาที

275
00:11:56,180 --> 00:11:59,640
และถ้าคุณมุ่งเน้นไปที่ตาของคุณ - เลือก
อัลกอริทึมมุ่งเน้นไปที่มันเพียง

276
00:11:59,640 --> 00:12:02,970
วินาที - คุณจะเริ่มเห็น
รูปแบบที่จะดำเนินการ

277
00:12:02,970 --> 00:12:04,530
>> ผสานเรียงลำดับการแจ้งให้ทราบจะทำ

278
00:12:04,530 --> 00:12:06,430
จัดเรียงกองเรียงลำดับเปลือกรวดเร็ว -

279
00:12:06,430 --> 00:12:09,480
จึงดูเหมือนว่าเราได้นำสาม
ขั้นตอนวิธีการที่เลวร้ายที่สุดสัปดาห์ที่ผ่านมา

280
00:12:09,480 --> 00:12:12,960
แต่ที่ดีที่เราอยู่ที่นี่ในวันนี้เพื่อ
มองไปที่การจัดเรียงผสานซึ่งเป็นหนึ่งใน

281
00:12:12,960 --> 00:12:16,500
คนที่ง่ายคือดูที่แม้
แม้ว่ามันอาจจะเบนความคิดของคุณ

282
00:12:16,500 --> 00:12:17,490
เพียงเล็กน้อย

283
00:12:17,490 --> 00:12:21,130
ที่นี่เราสามารถมองเห็นเพียงเท่าใด
เรียงลำดับการเลือกครับ

284
00:12:21,130 --> 00:12:24,600
>> แต่เมื่อพลิกด้านที่เป็น
เรื่องง่ายที่จะดำเนินการ

285
00:12:24,600 --> 00:12:28,160
และอาจจะสำหรับการตั้งค่า P ​​3 ที่หนึ่งของ
ขั้นตอนวิธีการที่คุณเลือกที่จะใช้

286
00:12:28,160 --> 00:12:28,960
สำหรับรุ่นมาตรฐาน

287
00:12:28,960 --> 00:12:30,970
สมบูรณ์ดีถูกต้องสมบูรณ์

288
00:12:30,970 --> 00:12:35,210
>> แต่อีกครั้งเป็น n ได้รับใหญ่ถ้าคุณ
เลือกที่จะใช้ขั้นตอนวิธีการได้เร็วขึ้น

289
00:12:35,210 --> 00:12:39,020
ชอบผสานการเรียงลำดับในราคาที่มีขนาดใหญ่และ
ปัจจัยการผลิตที่มีขนาดใหญ่รหัสของคุณเป็นเพียง

290
00:12:39,020 --> 00:12:39,800
จะไปทำงานได้เร็วขึ้น

291
00:12:39,800 --> 00:12:41,090
เว็บไซต์ของคุณจะทำงานได้ดีขึ้น

292
00:12:41,090 --> 00:12:42,650
ผู้ใช้ของคุณจะมีความสุขมากขึ้น

293
00:12:42,650 --> 00:12:45,280
และเพื่อให้มีผลกระทบเหล่านี้
ของจริงให้

294
00:12:45,280 --> 00:12:47,350
เราบางคิดลึก

295
00:12:47,350 --> 00:12:49,990
>> ดังนั้นลองมาดูที่สิ่งที่ผสาน
จัดเรียงเป็นจริงทั้งหมดเกี่ยวกับการ

296
00:12:49,990 --> 00:12:52,992
เป็นสิ่งดีๆที่ผสานการ
จัดเรียงเป็นเพียงนี้

297
00:12:52,992 --> 00:12:56,300
นี่คืออีกสิ่งที่เราเรียกว่า
pseudocode เป็น pseudocode

298
00:12:56,300 --> 00:12:57,720
ไวยากรณ์ภาษาอังกฤษอย่าง

299
00:12:57,720 --> 00:12:59,890
และความเรียบง่ายคือ
การจัดเรียงของที่น่าสนใจ

300
00:12:59,890 --> 00:13:02,840
>> ดังนั้นกับการป้อนข้อมูลขององค์ประกอบ n - เพื่อให้
เพียงแค่หมายความว่านี่คืออาร์เรย์

301
00:13:02,840 --> 00:13:04,000
มันมีสิ่งที่ n ในนั้น

302
00:13:04,000 --> 00:13:05,370
นั่นคือทั้งหมดที่เรากำลังจะบอกว่ามี

303
00:13:05,370 --> 00:13:07,560
>> ถ้า n เป็นน้อยกว่า 2 กลับ

304
00:13:07,560 --> 00:13:08,640
ดังนั้นนี่เป็นเพียงกรณีเล็กน้อย

305
00:13:08,640 --> 00:13:12,580
ถ้า n เป็นน้อยกว่า 2 แล้วเห็นได้ชัดว่ามันเป็น
1 หรือ 0 ซึ่งในกรณีนี้สิ่งที่

306
00:13:12,580 --> 00:13:14,780
เรียงลำดับแล้วหรือดำรงอยู่
ดังนั้นเพียงกลับ

307
00:13:14,780 --> 00:13:15,900
มีอะไรที่จะทำอะไร

308
00:13:15,900 --> 00:13:18,360
เพื่อให้เป็นกรณีที่ง่ายต่อการฉีก

309
00:13:18,360 --> 00:13:20,110
>> อื่นเรามีสามขั้นตอน

310
00:13:20,110 --> 00:13:23,650
เรียงซีกซ้ายขององค์ประกอบการจัดเรียง
ครึ่งขวาขององค์ประกอบ,

311
00:13:23,650 --> 00:13:26,650
แล้วตัดแบ่งเท่า ๆ กันเรียงลำดับ

312
00:13:26,650 --> 00:13:29,400
มีอะไรที่น่าสนใจที่นี่เป็นที่
ผมชนิดเตะขวา?

313
00:13:29,400 --> 00:13:32,300
มีชนิดของคำนิยามของวงกลม
ขั้นตอนวิธีการนี​​้

314
00:13:32,300 --> 00:13:35,986
สิ่งที่ความรู้สึกนี้เป็นอัลกอริทึม
นิยามวงกลม?

315
00:13:35,986 --> 00:13:37,850
>> ผู้ชม: [ได้ยิน]

316
00:13:37,850 --> 00:13:41,670
>> DAVID ลัน: ใช่ขั้นตอนวิธีการเรียงลำดับของฉัน
สองขั้นตอนที่มีการเรียงลำดับ "

317
00:13:41,670 --> 00:13:44,640
บางสิ่งบางอย่าง. "และอื่น ๆ ที่ไม่มีความประสงค์
คำถามดีสิ่งที่ฉันจะใช้

318
00:13:44,640 --> 00:13:46,460
ในการจัดเรียงซีกซ้าย
และอีกครึ่งหนึ่งใช่มั้ย?

319
00:13:46,460 --> 00:13:49,600
และความงามของที่นี่ก็คือว่าแม้ว่า
อีกครั้งนี้เป็นใจดัด

320
00:13:49,600 --> 00:13:54,030
ส่วนหนึ่งที่อาจเกิดขึ้นคุณสามารถใช้เดียวกัน
อัลกอริทึมในการจัดเรียงซีกซ้าย

321
00:13:54,030 --> 00:13:54,700
>> แต่รอสักครู่

322
00:13:54,700 --> 00:13:57,070
เมื่อคุณบอกว่าในการจัดเรียง
ซีกซ้ายสิ่งที่เป็นสอง

323
00:13:57,070 --> 00:13:58,240
ขั้นตอนจะมีต่อไปหรือไม่

324
00:13:58,240 --> 00:14:00,550
เราจะเรียงลำดับครึ่งซ้ายของ
ครึ่งซ้ายและขวา

325
00:14:00,550 --> 00:14:01,420
ครึ่งหนึ่งของซีกซ้าย

326
00:14:01,420 --> 00:14:04,430
ประณามฉันจะจัดเรียงทั้งสอง
ครึ่งหนึ่งหรือไตรมาสในขณะนี้?

327
00:14:04,430 --> 00:14:05,260
>> แต่ที่ตกลง

328
00:14:05,260 --> 00:14:07,830
เรามีขั้นตอนวิธีการเรียงลำดับที่นี่

329
00:14:07,830 --> 00:14:10,660
และถึงแม้คุณอาจจะกังวล
นี่เป็นครั้งแรกเป็นชนิดที่ไม่มีที่สิ้นสุด

330
00:14:10,660 --> 00:14:12,780
ห่วงก็วงจรที่ไม่เคย
จะจบ - มันเป็นไป

331
00:14:12,780 --> 00:14:15,770
สิ้นสุดเมื่อสิ่งที่เกิดขึ้น?

332
00:14:15,770 --> 00:14:16,970
เมื่อ n คือน้อยกว่า 2

333
00:14:16,970 --> 00:14:19,180
ซึ่งท้ายที่สุดก็จะเกิดขึ้น,
เพราะถ้าคุณให้ลดลงครึ่งหนึ่งและ

334
00:14:19,180 --> 00:14:23,020
ลดลงครึ่งหนึ่งในส่วนที่ลดลงครึ่งหนึ่งเหล่านี้แน่นอน
ในที่สุดคุณกำลังจะจบ

335
00:14:23,020 --> 00:14:25,350
ขึ้นมีเพียง 1 หรือ 0 องค์ประกอบ

336
00:14:25,350 --> 00:14:28,500
จุดที่อัลกอริทึมนี้
พูดว่าคุณทำเสร็จแล้ว

337
00:14:28,500 --> 00:14:31,020
>> ดังนั้นมายากลจริงในเรื่องนี้
อัลกอริทึมน่าจะเป็นใน

338
00:14:31,020 --> 00:14:33,470
ที่ขั้นตอนสุดท้ายการควบรวม

339
00:14:33,470 --> 00:14:37,190
ที่ความคิดง่ายเพียงแค่การรวมสอง
สิ่งที่สิ่งที่เกิดขึ้นในที่สุด

340
00:14:37,190 --> 00:14:40,920
เพื่อช่วยให้เราสามารถจัดเรียงแถวของ,
สมมติว่าแปดองค์ประกอบ

341
00:14:40,920 --> 00:14:44,410
ดังนั้นผมจึงมีอีกแปดลูกความเครียดขึ้น
ที่นี่แปดชิ้นส่วนของกระดาษและหนึ่ง

342
00:14:44,410 --> 00:14:45,500
แก้ว Google -

343
00:14:45,500 --> 00:14:46,140
ซึ่งผมได้รับเพื่อให้

344
00:14:46,140 --> 00:14:46,960
>> [เสียงหัวเราะ]

345
00:14:46,960 --> 00:14:48,970
>> ลันเดวิด: ถ้าเราอาจจะใช้เวลาแปด
อาสาสมัครและขอดูถ้าเราสามารถ

346
00:14:48,970 --> 00:14:51,430
เล่นนี้ออกดังนั้น

347
00:14:51,430 --> 00:14:52,500
ว้าว, โอคลาโฮมา

348
00:14:52,500 --> 00:14:53,565
วิทยาการคอมพิวเตอร์จะได้รับความสนุกสนาน

349
00:14:53,565 --> 00:14:54,320
ทั้งหมดขวา

350
00:14:54,320 --> 00:14:57,770
ดังนั้นวิธีการเกี่ยวกับคุณสาม,
มือที่ใหญ่ที่สุดมีขึ้น

351
00:14:57,770 --> 00:14:58,580
สี่ในด้านหลัง

352
00:14:58,580 --> 00:15:02,220
และวิธีการเกี่ยวกับเราจะทำคุณ
สามแถวนี้?

353
00:15:02,220 --> 00:15:03,390
และสี่ในด้านหน้า

354
00:15:03,390 --> 00:15:04,920
ดังนั้นคุณแปดมาขึ้น

355
00:15:04,920 --> 00:15:12,060
>> [เสียงหัวเราะ]

356
00:15:12,060 --> 00:15:13,450
>> DAVID ลัน: ฉันจริง
ไม่แน่ใจว่ามันคืออะไร

357
00:15:13,450 --> 00:15:14,810
มันเป็นลูกความเครียด

358
00:15:14,810 --> 00:15:16,510
โคมไฟโต๊ะ?

359
00:15:16,510 --> 00:15:18,650
วัสดุ?

360
00:15:18,650 --> 00:15:19,680
อินเทอร์เน็ตหรือไม่

361
00:15:19,680 --> 00:15:20,160
>> ตกลง

362
00:15:20,160 --> 00:15:21,310
เพื่อมาขึ้น

363
00:15:21,310 --> 00:15:22,310
ที่ต้องการ -

364
00:15:22,310 --> 00:15:23,570
ให้มา

365
00:15:23,570 --> 00:15:24,240
ลองมาดูกัน

366
00:15:24,240 --> 00:15:26,460
และสิ่งนี้ทำให้คุณอยู่ในสถานที่ -

367
00:15:26,460 --> 00:15:27,940
คุณอยู่ในสถานที่หนึ่ง

368
00:15:27,940 --> 00:15:28,670
UH-โอ้รอสักครู่

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - โอ้ดี

370
00:15:30,760 --> 00:15:31,310
สิทธิทั้งหมดที่เราไม่ดี

371
00:15:31,310 --> 00:15:35,130
ทั้งหมดถูกต้องทุกคนเพื่อให้มีที่นั่ง,
แต่ไม่ได้อยู่บน Google แก้ว

372
00:15:35,130 --> 00:15:36,475
ผมขอคิวขึ้นเหล่านี้

373
00:15:36,475 --> 00:15:37,115
คุณชื่ออะไร?

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: มิเชลล์

375
00:15:37,440 --> 00:15:38,090
>> DAVID ลัน: Michelle?

376
00:15:38,090 --> 00:15:42,000
สิทธิทั้งหมดที่คุณได้รับให้มีลักษณะเหมือน
geek หากที่ตกลง

377
00:15:42,000 --> 00:15:44,625
ดีฉันเกินไปฉันคิดว่า
รอสักครู่

378
00:15:44,625 --> 00:15:45,875
ทั้งหมดสแตนด์บายขวา

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
เราได้รับการพยายามที่จะเกิดขึ้นกับ
ใช้กรณีสำหรับ Google แก้วและเรา

381
00:15:50,950 --> 00:15:53,750
คิดว่ามันจะสนุกกับการทำ
นี้เมื่อคนที่อยู่บนเวที

382
00:15:53,750 --> 00:15:57,120
เราจะบันทึกโลก
จากมุมมองของพวกเขา

383
00:15:57,120 --> 00:15:58,410
ทั้งหมดขวา

384
00:15:58,410 --> 00:15:59,830
อาจไม่ได้สิ่งที่ Google ตั้งใจ

385
00:15:59,830 --> 00:16:02,260
ขวาทั้งหมดถ้าคุณไม่รังเกียจที่จะสวมใส่
นี้สำหรับนาทีที่น่าอึดอัดใจต่อไป

386
00:16:02,260 --> 00:16:03,150
ที่จะเป็นที่ยอดเยี่ยม

387
00:16:03,150 --> 00:16:08,620
>> ขวาทั้งหมดเพื่อให้เรามีที่นี่ array ของ
องค์ประกอบและอาร์เรย์ที่เป็นต่อ

388
00:16:08,620 --> 00:16:11,480
ชิ้นส่วนของกระดาษในคนเหล่านี้ '
มือไม่ได้เรียงปัจจุบัน

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: โอ้ที่แปลก

390
00:16:12,050 --> 00:16:12,810
>> DAVID ลัน: มันสวยมากแบบสุ่ม

391
00:16:12,810 --> 00:16:15,760
และในเพียงช่วงเวลาที่เรากำลังจะไปลอง
ในการดำเนินการรวมการจัดเรียงกัน

392
00:16:15,760 --> 00:16:17,950
และดูว่ามีความเข้าใจที่สำคัญคือ

393
00:16:17,950 --> 00:16:21,970
และเคล็ดลับที่นี่มีการจัดเรียงผสาน
สิ่งที่เรายังไม่ได้คิดว่ายัง

394
00:16:21,970 --> 00:16:24,030
เราจำเป็นต้องใช้จริงบางอย่าง
พื้นที่เพิ่มเติม

395
00:16:24,030 --> 00:16:26,650
ดังนั้นสิ่งที่เป็นไปได้โดยเฉพาะอย่างยิ่ง
ที่น่าสนใจเกี่ยวกับเรื่องนี้คือการที่เหล่านี้

396
00:16:26,650 --> 00:16:29,270
ผมกำลังจะย้ายไปรอบ ๆ เล็ก ๆ น้อย ๆ
บิตเพราะฉันจะสมมติว่า

397
00:16:29,270 --> 00:16:31,880
มีอาร์เรย์พิเศษของพื้นที่ของ
พูดขวาที่อยู่เบื้องหลังพวกเขา

398
00:16:31,880 --> 00:16:34,570
>> ดังนั้นหากพวกเขากำลังของพวกเขาที่อยู่เบื้องหลังเก้าอี้,
ที่แถวที่สอง

399
00:16:34,570 --> 00:16:36,960
หากพวกเขากำลังนั่งอยู่ที่นี่ว่า
อาร์เรย์หลัก

400
00:16:36,960 --> 00:16:40,170
แต่นี้เป็นทรัพยากรที่เรามี
ไม่ leveraged ป่านนี้กับฟอง

401
00:16:40,170 --> 00:16:42,040
เรียงลำดับการจัดเรียงที่มีการเลือก
มีการจัดเรียงแทรก

402
00:16:42,040 --> 00:16:44,600
จำสัปดาห์ที่ผ่านมาทุกคนเพียงแค่
ชนิดของสับในสถานที่

403
00:16:44,600 --> 00:16:46,840
พวกเขาไม่ได้ใช้ใด ๆ หน่วยความจำเพิ่มเติม

404
00:16:46,840 --> 00:16:49,310
ที่เราได้ทำห้องพักสำหรับคนโดย
การเคลื่อนย้ายผู้คนรอบข้าง

405
00:16:49,310 --> 00:16:50,580
>> ดังนั้นนี่คือข้อมูลเชิงลึกที่สำคัญเกินไป

406
00:16:50,580 --> 00:16:53,410
มีการค้านี้ออกอะไรโดยทั่วไปใน
วิทยาการคอมพิวเตอร์ของทรัพยากร

407
00:16:53,410 --> 00:16:55,800
ถ้าคุณต้องการเพื่อเพิ่มความเร็วในบางสิ่งบางอย่าง
เช่นเดียวกับเวลาที่คุณกำลังจะ

408
00:16:55,800 --> 00:16:56,900
ต้องจ่ายราคา

409
00:16:56,900 --> 00:17:00,750
และเป็นหนึ่งในราคาที่มากมักจะ
พื้นที่ปริมาณของหน่วยความจำหรือยาก

410
00:17:00,750 --> 00:17:01,700
พื้นที่ดิสก์ที่คุณกำลังใช้

411
00:17:01,700 --> 00:17:03,640
หรือตรงไปตรงมาจำนวน
ของเวลาโปรแกรมเมอร์

412
00:17:03,640 --> 00:17:06,700
เท่าใดเวลาที่คุณ, มนุษย์,
ที่จริงการดำเนินการบางอย่างเพิ่มเติม

413
00:17:06,700 --> 00:17:07,829
อัลกอริทึมที่มีความซับซ้อน

414
00:17:07,829 --> 00:17:09,760
แต่สำหรับวันนี้การปิด
คือเวลาและพื้นที่

415
00:17:09,760 --> 00:17:11,930
>> ดังนั้นถ้าพวกคุณก็อาจถือได้ของคุณ
ตัวเลขดังนั้นเราจะเห็นว่าคุณ

416
00:17:11,930 --> 00:17:15,839
แน่นอนการจับคู่ 4, 2, 6, 1, 3, 7, 8

417
00:17:15,839 --> 00:17:16,599
ยอดเยี่ยม

418
00:17:16,599 --> 00:17:19,520
ดังนั้นฉันจะพยายามที่จะ orchestrate
สิ่งที่ถ้าพวกคุณก็สามารถ

419
00:17:19,520 --> 00:17:21,800
ทำตามนำของฉันที่นี่

420
00:17:21,800 --> 00:17:26,650
>> ดังนั้นฉันจะใช้เป็นครั้งแรก,
ขั้นตอนแรกของ pseudocode ซึ่งเป็น

421
00:17:26,650 --> 00:17:29,440
กับการป้อนข้อมูลขององค์ประกอบ n ถ้า n คือ
น้อยกว่า 2 แล้วกลับ

422
00:17:29,440 --> 00:17:31,370
เห็นได้ชัดว่าไม่
นำไปใช้เพื่อให้เราเดินหน้าต่อไป

423
00:17:31,370 --> 00:17:33,340
ดังนั้นจัดเรียงซีกซ้ายขององค์ประกอบ

424
00:17:33,340 --> 00:17:36,220
ดังนั้นนั่นหมายความว่าฉันจะมุ่งเน้นไปที่ของฉัน
ความสนใจเพียงแค่ช่วงเวลาเหล่านี้

425
00:17:36,220 --> 00:17:37,310
สี่หนุ่มที่นี่

426
00:17:37,310 --> 00:17:39,774
ขวาทั้งหมดสิ่งที่ฉันจะไปทำอะไร?

427
00:17:39,774 --> 00:17:40,570
>> ผู้ชม: เรียงซีกซ้าย

428
00:17:40,570 --> 00:17:42,780
>> DAVID ลัน: ดังนั้นตอนนี้ฉันต้องจัดเรียง
ครึ่งซ้ายของคนเหล่านี้

429
00:17:42,780 --> 00:17:45,580
เพราะอีกครั้งสมมติให้กับตัวเอง
เป้าหมายคือการจัดเรียงซีกซ้าย

430
00:17:45,580 --> 00:17:46,440
คุณจะทำอย่างไรที่?

431
00:17:46,440 --> 00:17:49,140
เพียงทำตามคำแนะนำได้
แม้ว่าเรากำลังทำมันอีกครั้ง

432
00:17:49,140 --> 00:17:50,160
ดังนั้นจัดเรียงซีกซ้าย

433
00:17:50,160 --> 00:17:52,030
ตอนนี้ฉันกำลังเรียงลำดับเหล่านี้สองคน

434
00:17:52,030 --> 00:17:53,563
ที่มาต่อไปคืออะไร?

435
00:17:53,563 --> 00:17:54,510
>> ผู้ชม: เรียงซีกซ้าย

436
00:17:54,510 --> 00:17:55,460
>> DAVID ลัน: เรียงซีกซ้าย

437
00:17:55,460 --> 00:18:00,680
ดังนั้นตอนนี้เหล่านี้นั่งที่นี่,
เป็นรายการของขนาด 1

438
00:18:00,680 --> 00:18:01,365
และสิ่งที่ชื่อของคุณอีกครั้ง?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: เจ้าหญิงเดซี่

440
00:18:02,390 --> 00:18:03,690
>> DAVID ลัน: เจ้าหญิงเดซี่อยู่ที่นี่

441
00:18:03,690 --> 00:18:07,470
และเพื่อที่เธอจะถูกจัดเรียงอยู่แล้วเพราะ
รายการเป็นขนาด 1

442
00:18:07,470 --> 00:18:09,490
ฉันจะทำอะไรต่อไปทำอะไร?

443
00:18:09,490 --> 00:18:13,680
ตกลงกลับเนื่องจากรายการที่เป็น
ขนาด 1 ซึ่งน้อยกว่า 2

444
00:18:13,680 --> 00:18:14,320
แล้วขั้นตอนต่อไปคืออะไร

445
00:18:14,320 --> 00:18:17,490
และตอนนี้คุณมีชนิดของ
เปลี่ยนใจในใจของคุณ

446
00:18:17,490 --> 00:18:19,340
>> เรียงครึ่งขวาซึ่งเป็น -

447
00:18:19,340 --> 00:18:19,570
คุณชื่ออะไร?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: ลินดา

449
00:18:20,220 --> 00:18:20,980
>> DAVID ลัน: ลินดา

450
00:18:20,980 --> 00:18:23,210
และเพื่อให้เราทำในสิ่งที่ทำตอนนี้ว่า
เรามีรายชื่อของขนาด 1?

451
00:18:23,210 --> 00:18:24,440
>> ผู้ชม: ย้อนกลับ

452
00:18:24,440 --> 00:18:24,760
>> DAVID ลัน: ระวัง

453
00:18:24,760 --> 00:18:29,540
เรากลับมาเป็นครั้งแรกและตอนที่สาม
ขั้นตอน - ชนิดและถ้าฉันเห็นภาพของมันด้วย

454
00:18:29,540 --> 00:18:33,490
กอดสองที่นั่งในขณะนี้ตอนนี้ฉัน
มีการผสานทั้งสององค์ประกอบ

455
00:18:33,490 --> 00:18:35,530
ดังนั้นตอนนี้น่าเสียดายที่องค์ประกอบ
มีการออกคำสั่ง

456
00:18:35,530 --> 00:18:39,920
แต่ที่ที่กระบวนการควบรวมกิจการ
เริ่มที่จะได้รับที่น่าสนใจ

457
00:18:39,920 --> 00:18:42,410
>> ดังนั้นถ้าพวกคุณสามารถลุกขึ้นยืนเพื่อเพียง
ช่วงเวลาที่ผมจะต้องคุณใน

458
00:18:42,410 --> 00:18:44,170
ช่วงเวลาที่จะก้าวหลังเก้าอี้ของคุณ

459
00:18:44,170 --> 00:18:46,480
และถ้าลินดาเพราะ 2
มีขนาดเล็กกว่า 4 ทำไมไม่

460
00:18:46,480 --> 00:18:48,130
คุณมารอบแรก

461
00:18:48,130 --> 00:18:48,690
อยู่ที่นั่น

462
00:18:48,690 --> 00:18:50,520
ดังนั้น Linda คุณมารอบแรก

463
00:18:50,520 --> 00:18:53,820
>> ตอนนี้ในความเป็นจริงจะเป็นเพียงอาร์เรย์
เราก็สามารถย้ายของเธอในเวลาจริง

464
00:18:53,820 --> 00:18:55,360
จากเก้าอี้นี้ไปยังจุดนี้

465
00:18:55,360 --> 00:18:57,770
ดังนั้นคิดว่าคงใช้เวลาบางส่วน
จำนวนของขั้นตอนที่ 1

466
00:18:57,770 --> 00:18:58,480
และตอนนี้ -

467
00:18:58,480 --> 00:19:01,490
แต่เราต้องการที่จะนำคุณในการ
สถานที่แรกที่นี่

468
00:19:01,490 --> 00:19:03,930
>> และตอนนี้ถ้าคุณสามารถมารอบ,
เช่นกันที่เรากำลังจะ

469
00:19:03,930 --> 00:19:06,300
จะอยู่ในสองสถานที่

470
00:19:06,300 --> 00:19:09,120
และแม้ว่านี้รู้สึกเหมือนมัน
ใช้เวลาสักครู่เป็นสิ่งที่ดีในขณะนี้คือ

471
00:19:09,120 --> 00:19:14,710
ที่ครึ่งทางด้านซ้ายของ
ซีกซ้ายจะถูกจัดเรียงในขณะนี้

472
00:19:14,710 --> 00:19:18,010
ดังนั้นสิ่งที่ขั้นตอนต่อไปคือถ้าเราขณะนี้
ย้อนกลับไปในเรื่อง?

473
00:19:18,010 --> 00:19:18,980
>> ผู้ชม: ครึ่งขวา

474
00:19:18,980 --> 00:19:19,900
>> DAVID ลัน: เรียงครึ่งขวา

475
00:19:19,900 --> 00:19:21,320
ดังนั้นพวกคุณต้องทำเช่นนี้เช่นกัน

476
00:19:21,320 --> 00:19:23,510
ดังนั้นหากคุณสามารถลุกขึ้นยืน
รอสักครู่?

477
00:19:23,510 --> 00:19:25,192
และสิ่งที่ your name?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess

479
00:19:25,540 --> 00:19:25,870
>> DAVID ลัน: Jess

480
00:19:25,870 --> 00:19:29,720
OK เพื่อให้ Jess คือตอนนี้ทางด้านซ้าย
ครึ่งหนึ่งของครึ่งขวา

481
00:19:29,720 --> 00:19:31,400
และเพื่อให้เธอเป็นรายการขนาด 1

482
00:19:31,400 --> 00:19:32,380
เธอจัดเรียงอย่างเห็นได้ชัด

483
00:19:32,380 --> 00:19:33,070
และชื่อของคุณอีกครั้ง?

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: มิเชลล์

485
00:19:33,630 --> 00:19:35,340
>> DAVID ลัน: มิเชลจะเห็นได้ชัด
รายการของขนาด 1

486
00:19:35,340 --> 00:19:36,050
เธอเรียงแล้ว

487
00:19:36,050 --> 00:19:38,690
ดังนั้นตอนนี้ความมหัศจรรย์ที่เกิดขึ้น
กระบวนการควบรวมกิจการ

488
00:19:38,690 --> 00:19:39,790
ดังนั้นใครจะมาก่อน

489
00:19:39,790 --> 00:19:41,560
เห็นได้ชัดว่ามิเชลล์

490
00:19:41,560 --> 00:19:43,280
ดังนั้นถ้าคุณจะมารอบกลับ

491
00:19:43,280 --> 00:19:47,090
พื้นที่ที่เรามีสำหรับเธอในขณะนี้
คือด้านหลังของเก้าอี้นี้ที่นี่

492
00:19:47,090 --> 00:19:51,580
และตอนนี้ถ้าคุณสามารถกลับมาเป็นอย่างดี
ขณะนี้เรามีเพื่อให้มีความชัดเจนสอง

493
00:19:51,580 --> 00:19:53,810
ครึ่งหนึ่งของแต่ละขนาด 2 -

494
00:19:53,810 --> 00:19:57,090
และเพียงเพื่อประโยชน์ของภาพถ้าคุณ
สามารถทำนิด ๆ หน่อย ๆ ของพื้นที่ -

495
00:19:57,090 --> 00:19:59,780
คนเดียวที่เหลือครึ่งหนึ่งของที่นี่หนึ่ง
ครึ่งหนึ่งของที่นี่

496
00:19:59,780 --> 00:20:01,160
>> ย้อนกลับไปในเรื่อง

497
00:20:01,160 --> 00:20:02,270
สิ่งที่เป็นขั้นตอนต่อไปหรือไม่

498
00:20:02,270 --> 00:20:03,030
>> ผู้ชม: ผสาน

499
00:20:03,030 --> 00:20:04,160
>> DAVID ลัน: ดังนั้นตอนนี้เรามีการผสาน

500
00:20:04,160 --> 00:20:07,490
ตกลงดังนั้นตอนนี้โชคดีที่เรา
ปล่อยให้เป็นอิสระขึ้นเพียงเก้าอี้สี่

501
00:20:07,490 --> 00:20:11,480
ดังนั้นเราจึงใช้สองเท่าของหน่วยความจำมาก แต่
เราสามารถให้พลิกดิ้นระหว่าง

502
00:20:11,480 --> 00:20:12,330
สองอาร์เรย์

503
00:20:12,330 --> 00:20:14,190
ดังนั้นเลขที่ไปมาก่อน

504
00:20:14,190 --> 00:20:14,850
ดังนั้นมิเชลล์อย่างเห็นได้ชัด

505
00:20:14,850 --> 00:20:16,680
ดังนั้นมารอบและใช้
ที่นั่งของคุณที่นี่

506
00:20:16,680 --> 00:20:19,120
แล้วหมายเลข 2 จะเห็นได้ชัด
ต่อไปเพื่อให้คุณมาที่นี่

507
00:20:19,120 --> 00:20:21,520
หมายเลข 4 หมายเลข 6

508
00:20:21,520 --> 00:20:23,390
และอีกครั้งแม้ว่าจะมี
นิด ๆ หน่อย ๆ ของการเดินที่เกี่ยวข้องกับ

509
00:20:23,390 --> 00:20:26,010
จริงๆเหล่านี้อาจเกิดขึ้นได้ทันที
โดยการย้ายหนึ่ง -

510
00:20:26,010 --> 00:20:26,880
ตกลงกันเล่น

511
00:20:26,880 --> 00:20:28,350
>> [เสียงหัวเราะ]

512
00:20:28,350 --> 00:20:29,680
>> DAVID ลัน: และตอนนี้เรากำลัง
ในรูปทรงที่ดีงาม

513
00:20:29,680 --> 00:20:34,910
ครึ่งซ้ายของทั้ง
การป้อนข้อมูลขณะนี้ได้รับเรียง

514
00:20:34,910 --> 00:20:37,370
ขวาทั้งหมดเพื่อให้คนเหล่านี้มี
ความได้เปรียบของฉัน -

515
00:20:37,370 --> 00:20:40,340
มันก็จบลงด้วยวิธีการที่เด็กผู้หญิงทั้งหมดใน
ซ้ายและชายเมื่อถูกต้องหรือไม่

516
00:20:40,340 --> 00:20:42,450
>> ตกลงดังนั้นพวก 'เปิดในขณะนี้

517
00:20:42,450 --> 00:20:44,680
ดังนั้นฉันจะไม่เดินคุณผ่าน
ขั้นตอนเหล่านี้

518
00:20:44,680 --> 00:20:46,550
เราจะดูว่าเราสามารถนำไปใช้ใหม่
pseudocode เดียวกัน

519
00:20:46,550 --> 00:20:50,050
ถ้าคุณต้องการที่จะไปข้างหน้าและยืนขึ้น
และพวกคุณให้ฉันให้คุณไมค์

520
00:20:50,050 --> 00:20:52,990
ดูถ้าคุณไม่สามารถทำซ้ำในสิ่งที่
เราก็ไม่ได้ที่นี่

521
00:20:52,990 --> 00:20:53,880
ปลายอีกด้านหนึ่งของรายการ

522
00:20:53,880 --> 00:20:59,530
ความต้องการที่จะพูดเป็นครั้งแรกที่
ขึ้นอยู่กับขั้นตอนวิธี?

523
00:20:59,530 --> 00:21:03,210
ดังนั้นการอธิบายสิ่งที่คุณทำก่อน
คุณทำให้การเคลื่อนไหวของเท้าใด ๆ

524
00:21:03,210 --> 00:21:05,930
>> 1 SPEAKER: ทั้งหมดขวาดังนั้นตั้งแต่
ผมครึ่งซ้ายของ

525
00:21:05,930 --> 00:21:07,790
ครึ่งซ้ายฉันกลับ

526
00:21:07,790 --> 00:21:08,730
ใช่ไหม?

527
00:21:08,730 --> 00:21:09,250
>> DAVID ลัน: ดี

528
00:21:09,250 --> 00:21:10,350
>> ลำโพง 1: และจากนั้น -

529
00:21:10,350 --> 00:21:11,800
>> DAVID ลัน: ใคร
ไมค์ไปที่ต่อไปหรือไม่

530
00:21:11,800 --> 00:21:12,920
>> 1 SPEAKER: หมายเลขถัดไป

531
00:21:12,920 --> 00:21:14,720
>> ลำโพง 2: ดังนั้นฉันครึ่งขวา
ในช่วงครึ่งซ้ายของ

532
00:21:14,720 --> 00:21:17,830
ครึ่งซ้ายและเราจะกลับมา

533
00:21:17,830 --> 00:21:18,050
>> DAVID ลัน: ดี

534
00:21:18,050 --> 00:21:18,550
คุณจะกลับไป

535
00:21:18,550 --> 00:21:21,855
ดังนั้นตอนนี้ขึ้นต่อไปสำหรับคุณสองคืออะไร

536
00:21:21,855 --> 00:21:23,740
>> 2 SPEAKER: เราต้องการดูว่ามีใครที่มีขนาดเล็ก

537
00:21:23,740 --> 00:21:24,200
>> DAVID ลัน: ว่า

538
00:21:24,200 --> 00:21:24,940
เราต้องการที่จะผสาน

539
00:21:24,940 --> 00:21:27,590
พื้นที่ที่เราจะใช้ในการผสาน
คุณเข้าสู่แม้ว่าพวกเขากำลัง

540
00:21:27,590 --> 00:21:30,250
จัดเรียงอย่างเห็นได้ชัดแล้วเราจะ
ที่จะทำตามขั้นตอนวิธีการเดียวกัน

541
00:21:30,250 --> 00:21:31,560
ดังนั้นไปในครั้งแรกที่?

542
00:21:31,560 --> 00:21:35,720
ดังนั้น 3 แล้ว 7

543
00:21:35,720 --> 00:21:38,570
และตอนนี้ไมค์ไป
เพื่อคนเหล่านี้, OK?

544
00:21:38,570 --> 00:21:43,590
>> 3 SPEAKER: ดังนั้นฉันครึ่งทางด้านขวาของ
ครึ่งซ้ายและ n ของฉันมีค่าน้อยกว่า

545
00:21:43,590 --> 00:21:45,048
1 ดังนั้นฉันเพียงแค่จะผ่านไป -

546
00:21:45,048 --> 00:21:46,380
>> DAVID ลัน: ดี

547
00:21:46,380 --> 00:21:49,450
>> 4 SPEAKER: ฉันครึ่งทางด้านขวาของ
ครึ่งขวาของครึ่งขวาและฉัน

548
00:21:49,450 --> 00:21:51,740
นอกจากนี้ยังมีคนคนหนึ่งดังนั้นฉัน
ไปกลับ

549
00:21:51,740 --> 00:21:52,990
ดังนั้นตอนนี้เรารวม

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> 3 ลำโพงดังนั้นเราจึงกลับไป

552
00:21:56,150 --> 00:21:57,160
>> DAVID ลัน: คุณกลับไปเป็น

553
00:21:57,160 --> 00:21:59,200
ดังนั้น 5 ไปก่อนแล้ว 8

554
00:21:59,200 --> 00:22:01,240
และผู้ชมในขณะนี้ซึ่งเป็น
ขั้นตอนที่เราต้องย้อนกลับในขณะนี้

555
00:22:01,240 --> 00:22:02,200
กลับไปยังอยู่ในใจของเราหรือไม่

556
00:22:02,200 --> 00:22:02,940
>> ผู้ชม: ผสาน

557
00:22:02,940 --> 00:22:07,270
>> DAVID ลัน: ซีกซ้ายและขวาผสาน
ครึ่งหนึ่งของซีกซ้ายเดิม

558
00:22:07,270 --> 00:22:08,840
ดังนั้นตอนนี้ -

559
00:22:08,840 --> 00:22:10,520
และเพียงแค่นี้เพื่อให้ชัดเจน
ทำนิด ๆ หน่อย ๆ ของพื้นที่

560
00:22:10,520 --> 00:22:11,690
ระหว่างคุณสองคน

561
00:22:11,690 --> 00:22:13,800
ดังนั้นขณะนี้ที่ทั้งสองรายการ
ซ้ายและขวา

562
00:22:13,800 --> 00:22:18,320
ดังนั้นทำอย่างไรเราตอนนี้คุณผสานเป็นผู้ชาย
แถวหน้าของที่นั่งอีกครั้ง?

563
00:22:18,320 --> 00:22:19,600
>> 3 ไปคร​​ั้งแรก

564
00:22:19,600 --> 00:22:20,850
แล้ว 5 อย่างเห็นได้ชัด

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
แล้ว 7 และตอนนี้ 8

567
00:22:27,330 --> 00:22:28,710
ตกลงตอนนี้เรามีอะไรบ้าง

568
00:22:28,710 --> 00:22:29,650
>> ผู้ชม: ไม่ได้ทำ

569
00:22:29,650 --> 00:22:32,440
>> DAVID ลัน: ไม่ได้ทำเพราะ
เห็นได้ชัดว่ามีขั้นตอนเดียวที่เหลืออยู่ของ

570
00:22:32,440 --> 00:22:35,720
แต่อีกเหตุผลที่ผมใช้นี้
ศัพท์แสงเช่น "ย้อนกลับในใจของคุณ"

571
00:22:35,720 --> 00:22:37,160
มันเป็นเพราะที่จริง
สิ่งที่เกิดขึ้น

572
00:22:37,160 --> 00:22:39,610
เรากำลังจะผ่านทุกขั้นตอนเหล่านี้
แต่เราเรียงลำดับของการหยุดชั่วคราวสำหรับ

573
00:22:39,610 --> 00:22:42,480
ขณะดำน้ำลึกเข้าไปใน
อัลกอริทึมหยุดสักครู่

574
00:22:42,480 --> 00:22:45,840
ดำน้ำลึกลงไปในขั้นตอนวิธีการและ
ตอนนี้เราต้องจัดเรียงย้อนกลับจากในของเรา

575
00:22:45,840 --> 00:22:49,430
จิตใจและยกเลิกทั้งหมดของชั้นเหล่านี้
ที่เราได้จัดเรียงของไว้

576
00:22:49,430 --> 00:22:51,790
>> ดังนั้นตอนนี้เรามีสองรายการจาก 4 ขนาด

577
00:22:51,790 --> 00:22:54,790
ถ้าพวกคุณสามารถยืนขึ้นเป็นครั้งสุดท้าย
และทำให้บิตของพื้นที่ที่นี่เพื่อ

578
00:22:54,790 --> 00:22:57,230
ทำให้เห็นได้ชัดว่านี่คือทางด้านซ้าย
ครึ่งหนึ่งของเดิม

579
00:22:57,230 --> 00:22:58,620
ครึ่งขวาของเดิม

580
00:22:58,620 --> 00:23:01,060
เป็นหมายเลขแรกที่ว่าเรา
ต้องดึงเข้าด้านหลัง?

581
00:23:01,060 --> 00:23:01,870
มิเชลล์แน่นอน

582
00:23:01,870 --> 00:23:03,230
>> ดังนั้นเราจึงวางมิเชลล์ที่นี่

583
00:23:03,230 --> 00:23:05,080
และมี 2 จำนวนผู้ที่?

584
00:23:05,080 --> 00:23:06,440
2 จำนวนมาที่ด้านหลังเช่นกัน

585
00:23:06,440 --> 00:23:07,800
3 จำนวน?

586
00:23:07,800 --> 00:23:08,510
ยอดเยี่ยม

587
00:23:08,510 --> 00:23:16,570
4 จำนวนจำนวน 5 หมายเลข 6,
หมายเลข 7, 8 และจำนวน

588
00:23:16,570 --> 00:23:18,850
>> ตกลงดังนั้นมันให้ความรู้สึกว่าชอบมาก
ของขั้นตอนเพื่อตรวจสอบว่า

589
00:23:18,850 --> 00:23:22,390
แต่ตอนนี้ขอดูว่าเราไม่สามารถยืนยันได้
การเรียงลำดับของอย่างสังหรณ์ใจที่นี้

590
00:23:22,390 --> 00:23:26,190
อัลกอริทึมพื้นฐานโดยเฉพาะอย่างยิ่ง
n ได้รับขนาดใหญ่จริงๆอย่างที่เราเคยเห็น

591
00:23:26,190 --> 00:23:29,170
ที่มีภาพเคลื่อนไหวเป็น
พื้นฐานได้เร็วขึ้น

592
00:23:29,170 --> 00:23:33,400
ดังนั้นผมจึงเรียกร้องขั้นตอนวิธีนี้ในที่เลวร้ายที่สุด
กรณีและแม้กระทั่งในกรณีที่ดีที่สุด

593
00:23:33,400 --> 00:23:36,160
O ใหญ่ของครั้ง n log n คือ

594
00:23:36,160 --> 00:23:39,160
นั่นคือมีลักษณะของการนี​​้บางส่วนของ
อัลกอริทึมที่ใช้ขั้นตอนที่ n แต่

595
00:23:39,160 --> 00:23:43,110
มีมุมมองของผู้อื่นที่ไหนสักแห่งใน
ย้ำว่าการวนลูปที่ว่า

596
00:23:43,110 --> 00:23:44,410
ใช้ขั้นตอนที่ n log

597
00:23:44,410 --> 00:23:49,154
เราสามารถนำลายนิ้วมือข​​องเรากับสิ่งเหล่านั้น
ตัวเลขสองหมายถึง?

598
00:23:49,154 --> 00:23:51,320
ดีที่ -

599
00:23:51,320 --> 00:23:54,160
หมอนไมค์ไป?

600
00:23:54,160 --> 00:23:58,660
>> 1 ลำโพงจะ log n จะ
ทำลายเราขึ้นเป็นสอง -

601
00:23:58,660 --> 00:23:59,630
หารด้วยสองหลัก

602
00:23:59,630 --> 00:24:00,120
>> DAVID ลัน: ว่า

603
00:24:00,120 --> 00:24:03,000
เวลาที่เราเห็นในอัลกอริทึมจึงใด
ไกลมีการรูปแบบนี้

604
00:24:03,000 --> 00:24:04,200
หาร, หาร, หาร

605
00:24:04,200 --> 00:24:05,700
และจะลดลงเป็นปกติ
บางสิ่งบางอย่างที่

606
00:24:05,700 --> 00:24:07,100
ลอการิทึม log ฐาน 2

607
00:24:07,100 --> 00:24:10,180
แต่จริงๆมันอาจเป็นอะไร,
แต่เข้าสู่ระบบฐาน 2

608
00:24:10,180 --> 00:24:11,330
>> ตอนนี้สิ่งที่เกี่ยวกับ n?

609
00:24:11,330 --> 00:24:14,550
ฉันสามารถเห็นว่าเราแบ่งชนิดของคุณ
พวก - แบ่งออกคุณแบ่งคุณ,

610
00:24:14,550 --> 00:24:15,910
แบ่งออกคุณคุณแบ่ง

611
00:24:15,910 --> 00:24:18,760
ปลายไม่มาจากไหน

612
00:24:18,760 --> 00:24:19,810
>> ดังนั้นจึงเป็นความกลมกลืน

613
00:24:19,810 --> 00:24:20,610
เพราะคิดเกี่ยวกับมัน

614
00:24:20,610 --> 00:24:25,420
เมื่อคุณผสานแปดคนด้วยกัน
โดยครึ่งหนึ่งของพวกเขาเป็นชุดของสี่

615
00:24:25,420 --> 00:24:27,770
และอีกครึ่งหนึ่งเป็นอีก
ชุดของสี่คุณจะไป

616
00:24:27,770 --> 00:24:28,820
เกี่ยวกับการทำผสม?

617
00:24:28,820 --> 00:24:30,830
กันพวกคุณทำมัน
เป็นธรรมอย่างสังหรณ์ใจ

618
00:24:30,830 --> 00:24:34,140
>> แต่ถ้าฉันแทนมันเล็ก ๆ น้อย ๆ
มีระบบ, ฉันอาจจะชี้ไปที่

619
00:24:34,140 --> 00:24:38,090
คนซ้ายมือสุดเป็นครั้งแรกกับซ้ายของฉัน
มือชี้ไปที่คนที่อยู่ทางซ้าย

620
00:24:38,090 --> 00:24:42,080
ของครึ่งปีที่ว่าด้วยมือขวาของฉันและ
เพียงแค่เดินผ่านมา

621
00:24:42,080 --> 00:24:46,990
รายการชี้ไปที่องค์ประกอบที่เล็กที่สุด
ในแต่ละครั้งที่จะย้ายนิ้วมือข​​องฉันไปและ

622
00:24:46,990 --> 00:24:48,970
กว่าที่จำเป็นตลอดรายการ

623
00:24:48,970 --> 00:24:51,890
แต่สิ่งที่สำคัญเกี่ยวกับเรื่องนี้รวมสิ่ง
กระบวนการคือผมเปรียบเทียบคู่เหล่านี้

624
00:24:51,890 --> 00:24:53,460
ขององค์ประกอบ

625
00:24:53,460 --> 00:24:57,270
จากครึ่งด้านขวาและด้านซ้าย
ครึ่งผมไม่เคยย้อนรอย

626
00:24:57,270 --> 00:25:00,570
>> ดังนั้นการรวมตัวของมันเองคือการ
ไม่เกิน n ขั้นตอน

627
00:25:00,570 --> 00:25:03,250
และกี่ครั้งก็ฉันมี
จะทำอย่างไรที่การควบรวมกิจการ?

628
00:25:03,250 --> 00:25:07,150
ดีไม่เกิน n และเราเพียงแค่
เห็นว่ามีคนสุดท้ายที่ผสาน

629
00:25:07,150 --> 00:25:13,120
ดังนั้นถ้าคุณทำบางสิ่งบางอย่างที่เกิดขึ้น
เข้าสู่ระบบขั้นตอน n N ครั้งหรือในทางกลับกัน

630
00:25:13,120 --> 00:25:15,210
มันจะให้เราครั้ง n log n

631
00:25:15,210 --> 00:25:16,310
>> และนี่คือเหตุผลที่ดีกว่า

632
00:25:16,310 --> 00:25:19,600
ดีถ้าเรารู้อยู่แล้วว่าบันทึกที่
n คือดีกว่า n - ขวา?

633
00:25:19,600 --> 00:25:22,590
ที่เราเห็นในการค้นหาแบบไบนารี, สมุดโทรศัพท์
ตัวอย่างเช่น log n แน่นอน

634
00:25:22,590 --> 00:25:23,760
ดีกว่าเป็นเส้นตรง

635
00:25:23,760 --> 00:25:28,420
ดังนั้นนั่นหมายความว่าครั้ง n log n คือ
แน่นอนดีกว่า n ครั้งอื่น

636
00:25:28,420 --> 00:25:30,390
n, AKA n squared

637
00:25:30,390 --> 00:25:32,400
และนั่นคือสิ่งที่เรารู้สึกว่าในที่สุด

638
00:25:32,400 --> 00:25:34,928
>> รอบใหญ่ดังนั้นจากเสียงปรบมือถ้า
เราจะทำได้สำหรับคนเหล่านี้

639
00:25:34,928 --> 00:25:38,920
>> [APPLAUSE]

640
00:25:38,920 --> 00:25:41,550
>> DAVID ลัน: พรากจากกันและของขวัญของคุณ -
คุณอาจจะให้ตัวเลข

641
00:25:41,550 --> 00:25:44,010
หากคุณต้องการ

642
00:25:44,010 --> 00:25:45,620
และของที่ระลึกพรากจากกันของคุณได้ตามปกติ

643
00:25:45,620 --> 00:25:47,290
Oh, และเราจะส่ง
ภาพมิเชลล์

644
00:25:47,290 --> 00:25:48,343
ขอบคุณ

645
00:25:48,343 --> 00:25:49,250
ทั้งหมดขวา

646
00:25:49,250 --> 00:25:50,400
ช่วยตัวเองเพื่อลูกความเครียด

647
00:25:50,400 --> 00:25:54,110
>> และแจ้งให้เราดึงขึ้นในขณะเดียวกัน
เพื่อนของเราร็อบโบว์ที่จะนำเสนอ

648
00:25:54,110 --> 00:25:59,520
มุมมองที่แตกต่างกันบ้างเกี่ยวกับเรื่องนี้
ตั้งแต่ที่คุณสามารถคิดเกี่ยวกับเหล่านี้

649
00:25:59,520 --> 00:26:01,280
ขั้นตอนที่เกิดขึ้นในบางส่วน
วิธีการที่แตกต่างกัน

650
00:26:01,280 --> 00:26:04,750
ในความเป็นจริงการตั้งค่าสำหรับสิ่งที่เกี่ยวกับร็อบ
เพื่อแสดงให้เราสมมติว่าเราได้

651
00:26:04,750 --> 00:26:09,030
ทำมาแล้วแบ่งของ
รายการใหญ่เป็นแปดรายการขนาดเล็ก

652
00:26:09,030 --> 00:26:10,570
แต่ละขนาด 1

653
00:26:10,570 --> 00:26:13,350
>> ดังนั้นเรากำลังจะเปลี่ยน pseudocode
เพียงเล็กน้อยในการจัดเรียงของที่ได้รับ

654
00:26:13,350 --> 00:26:15,320
แนวคิดหลักของวิธีการทำงานของการควบรวมกิจการ

655
00:26:15,320 --> 00:26:17,600
แต่เวลาการทำงานของสิ่งที่
เขากำลังจะทำคือการยังคง

656
00:26:17,600 --> 00:26:19,110
เป็นไปได้เหมือนกัน

657
00:26:19,110 --> 00:26:23,540
และอีกครั้งการตั้งค่าที่นี่เป็นที่ของเขา
เริ่มต้นด้วยแปดรายการขนาด 1

658
00:26:23,540 --> 00:26:27,730
เพื่อให้คุณได้พลาดส่วนหนึ่งที่เขาเป็น
ทำจริง log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
หารของท่าน

660
00:26:31,205 --> 00:26:32,120
>> [เล่นภาพวิดีโอ]

661
00:26:32,120 --> 00:26:33,615
>> ที่มันสำหรับขั้นตอนเดียว

662
00:26:33,615 --> 00:26:38,270
สำหรับขั้นที่สองซ้ำแล้วซ้ำเล่า
รวมคู่ของรายการ

663
00:26:38,270 --> 00:26:39,210
>> DAVID ลัน: อืมมม

664
00:26:39,210 --> 00:26:41,270
เสียงเท่านั้นที่จะมา
ออกจากคอมพิวเตอร์ของฉัน

665
00:26:41,270 --> 00:26:42,520
ลองนี้อีกครั้ง

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> เพียงแค่เลือกที่พล -
ตอนนี้เรามีสี่รายการ

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
ก่อนที่จะเรียนรู้

670
00:26:52,120 --> 00:26:53,040
>> DAVID ลัน: มีที่เราไป

671
00:26:53,040 --> 00:27:00,510
>> ผสาน-108 และ 15 เราจบ
กับรายการ 15 108

672
00:27:00,510 --> 00:27:07,170
ผสาน 50 และ 4 เรา
จบลงด้วย 4, 50

673
00:27:07,170 --> 00:27:12,990
ผสาน 8 และ 42 เรา
จบลงด้วย 8, 42

674
00:27:12,990 --> 00:27:19,970
และการรวม 23 และ 16 เรา
จบลงด้วย 16, 23

675
00:27:19,970 --> 00:27:23,270
>> ตอนนี้สิ่งที่รายการของเรามี 2 ขนาด

676
00:27:23,270 --> 00:27:26,690
ขอให้สังเกตว่าแต่ละ
สี่รายการจะเรียงลำดับตาม

677
00:27:26,690 --> 00:27:29,450
ดังนั้นเราจึงสามารถเริ่มต้นการควบรวมกิจการ
คู่ของรายการอีกครั้ง

678
00:27:29,450 --> 00:27:38,420
ผสาน 15 และ 108 และ 4 และ 50 เรา
ครั้งแรก 4 แล้ว 15 แล้ว

679
00:27:38,420 --> 00:27:41,500
50 แล้ว 108

680
00:27:41,500 --> 00:27:50,610
ผสาน 8, 42 และ 16, 23, ครั้งแรกที่เราใช้
8 แล้ว 16 แล้ว 23,

681
00:27:50,610 --> 00:27:52,700
แล้ว 42

682
00:27:52,700 --> 00:27:57,600
>> ดังนั้นตอนนี้เรามีเพียงสองรายการขนาด
4 ซึ่งแต่ละอย่างจะถูกจัดเรียง

683
00:27:57,600 --> 00:28:01,170
ดังนั้นตอนนี้เรารวมทั้งสองรายการ

684
00:28:01,170 --> 00:28:11,835
ครั้งแรกที่เราใช้เวลา 4 แล้วเราใช้
8 แล้วเราใช้เวลา 15 แล้ว 16 แล้ว

685
00:28:11,835 --> 00:28:19,456
23 แล้ว 42 แล้ว 50 แล้ว 108

686
00:28:19,456 --> 00:28:19,872
>> [เล่นวิดีโอจบ]

687
00:28:19,872 --> 00:28:23,430
>> DAVID ลัน: อีกครั้งแจ้งให้ทราบล่วงหน้าเขาไม่เคย
สัมผัสถ้วยที่กำหนดมากกว่าหนึ่งครั้ง

688
00:28:23,430 --> 00:28:24,860
หลังจากที่ก้าวหน้าเกินกว่าที่มัน

689
00:28:24,860 --> 00:28:26,200
ดังนั้นเขาจึงไม่เคยซ้ำ

690
00:28:26,200 --> 00:28:29,850
ดังนั้นเขาจึงมักจะย้ายไปที่ด้านข้าง,
และนั่นคือสิ่งที่เราได้ n ของเรา

691
00:28:29,850 --> 00:28:33,290
>> ทำไมไม่ให้ฉันดึงขึ้นหนึ่งภาพเคลื่อนไหว
ที่เราเห็นก่อนหน้านี้ แต่ในเวลานี้

692
00:28:33,290 --> 00:28:35,110
เน้นเฉพาะในการจัดเรียงที่ผสาน

693
00:28:35,110 --> 00:28:38,030
ให้ฉันไปข้างหน้าและซูม
ในเมื่อที่นี่

694
00:28:38,030 --> 00:28:42,530
แรกให้ฉันเลือกการป้อนข้อมูลแบบสุ่ม
ขยายนี้และคุณสามารถเรียงลำดับจากดู

695
00:28:42,530 --> 00:28:46,600
สิ่งที่เราได้รับมาก่อนหน้านี้,
เรียงลำดับรวมเป็นจริงทำ

696
00:28:46,600 --> 00:28:50,330
>> ดังนั้นสังเกตเห็นว่าคุณจะได้รับครึ่งหนึ่งเหล่านี้หรือ
สี่เหล่านี้หรือ eighths เหล่านี้

697
00:28:50,330 --> 00:28:53,140
ปัญหาที่ทั้งหมดในทันที
เริ่มต้นที่จะใช้รูปทรงที่ดี

698
00:28:53,140 --> 00:28:57,070
และแล้วในที่สุดคุณจะเห็นที่
ปลายมากที่แบม,

699
00:28:57,070 --> 00:28:58,860
ทุกอย่างรวมกัน

700
00:28:58,860 --> 00:29:01,690
>> ดังนั้นเหล่านี้เป็นเพียงสามที่แตกต่างกัน
จะใช้เวลาในความคิดเดียวกัน

701
00:29:01,690 --> 00:29:05,980
แต่ข้อมูลเชิงลึกที่สำคัญเช่นเดียวกับการแบ่ง
และพิชิตในชั้นแรกมาก,

702
00:29:05,980 --> 00:29:10,640
คือการที่เราตัดสินใจที่จะแบ่งอย่างใด
ปัญหาเป็นสิ่งที่ใหญ่เป็น

703
00:29:10,640 --> 00:29:14,760
เรียงลำดับสิ่งที่เหมือนกันในจิตวิญญาณ
แต่มีขนาดเล็กและขนาดเล็กและขนาดเล็ก

704
00:29:14,760 --> 00:29:15,660
และมีขนาดเล็ก

705
00:29:15,660 --> 00:29:18,420
>> ตอนนี้อีกวิธีหนึ่งที่สนุกกับการจัดเรียงของคิด
เกี่ยวกับเหล่านี้แม้ว่ามันจะไม่ได้

706
00:29:18,420 --> 00:29:20,520
จะให้คุณเดียวกันใช้งานง่าย
ความเข้าใจคือ

707
00:29:20,520 --> 00:29:21,640
การเคลื่อนไหวดังต่อไปนี้

708
00:29:21,640 --> 00:29:25,400
ดังนั้นนี่คือคนวิดีโอใส่กัน
ที่เกี่ยวข้องที่แตกต่างกัน

709
00:29:25,400 --> 00:29:29,970
เสียงกับการดำเนินงานต่างๆสำหรับ
จัดเรียงแทรกสำหรับตัดจัดเรียงและ

710
00:29:29,970 --> 00:29:31,150
สำหรับคู่ของคนอื่น ๆ

711
00:29:31,150 --> 00:29:32,330
ดังนั้นในช่วงเวลาที่ผมจะตีเล่น

712
00:29:32,330 --> 00:29:33,600
มันเกี่ยวกับนาทีเป็นเวลานาน

713
00:29:33,600 --> 00:29:37,410
และถึงแม้คุณจะยังคงสามารถมองเห็นได้
รูปแบบที่เกิดขึ้นทุกครั้งที่คุณไม่ได้เป็นสมาชิก

714
00:29:37,410 --> 00:29:41,420
ยังได้ยินว่าอัลกอริทึมเหล่านี้
การดำเนินการที่แตกต่างกันและมี

715
00:29:41,420 --> 00:29:43,950
รูปแบบที่แตกต่างกันบ้าง

716
00:29:43,950 --> 00:29:45,830
>> นี้จะเรียงลำดับการแทรก

717
00:29:45,830 --> 00:29:50,400
>> [เสียง PLAYING]

718
00:29:50,400 --> 00:29:52,400
>> DAVID ลัน: อีกครั้งพยายาม
แทรกแต่ละองค์ประกอบ

719
00:29:52,400 --> 00:29:52,900
ในที่ที่มันเป็น

720
00:29:52,900 --> 00:29:54,628
นี้จะเรียงลำดับฟอง

721
00:29:54,628 --> 00:30:10,097
>> [เสียง PLAYING]

722
00:30:10,097 --> 00:30:13,630
>> DAVID ลัน: และคุณสามารถเรียงลำดับจากความรู้สึก
วิธีการที่ค่อนข้างน้อยทำงานก็ทำ

723
00:30:13,630 --> 00:30:15,834
แต่ละขั้นตอน

724
00:30:15,834 --> 00:30:20,470
นี่คือสิ่งที่น่าเบื่อเสียงเหมือน

725
00:30:20,470 --> 00:30:21,472
>> [เสียง PLAYING]

726
00:30:21,472 --> 00:30:25,222
>> DAVID ลัน: นี้จะเรียงลำดับการเลือก,
ที่เราเลือกองค์ประกอบที่เราต้องการโดย

727
00:30:25,222 --> 00:30:28,845
จะผ่านอีกครั้งและอีกครั้งและอีกครั้ง
และวางไว้ที่จุดเริ่มต้น

728
00:30:28,845 --> 00:30:37,674
>> [เสียง PLAYING]

729
00:30:37,674 --> 00:30:43,970
>> DAVID ลัน: นี่คือการจัดเรียงรวมกันซึ่ง
จริงๆคุณสามารถเริ่มต้นที่จะรู้สึก

730
00:30:43,970 --> 00:30:51,810
>> [เสียง PLAYING]

731
00:30:51,810 --> 00:30:54,770
>> [เสียงหัวเราะ]

732
00:30:54,770 --> 00:30:58,395
>> DAVID ลัน: สิ่งที่เรียกว่าคำพังเพย
เรียงลำดับซึ่งเราไม่ได้มองที่

733
00:30:58,395 --> 00:31:13,630
>> [เสียง PLAYING]

734
00:31:13,630 --> 00:31:17,910
>> DAVID ลัน: เพื่อให้ฉันเห็นตอนนี้
ฟุ้งซ่านในขณะที่คุณหวังว่าจะเป็นโดย

735
00:31:17,910 --> 00:31:21,110
เพลงถ้าฉันสามารถลื่นเล็กน้อย
บิตของคณิตศาสตร์ที่นี่

736
00:31:21,110 --> 00:31:24,850
ดังนั้นมีวิธีที่สี่ที่เราสามารถอะไร
คิดเกี่ยวกับสิ่งเหล่านี้มันหมายความว่า

737
00:31:24,850 --> 00:31:29,210
ฟังก์ชั่นจะเร็วกว่าคน
ที่เราได้เห็นมาก่อน

738
00:31:29,210 --> 00:31:32,470
และถ้าคุณมาที่สนามจาก
พื้นหลังคณิตศาสตร์คุณ

739
00:31:32,470 --> 00:31:36,030
รู้จริงบางทีแล้วว่าคุณ
สามารถตบยาวกับเทคนิคนี้ -

740
00:31:36,030 --> 00:31:40,400
เรียกซ้ำตัวเองคือฟังก์ชั่น
ที่เรียกตัวเองอย่างใด

741
00:31:40,400 --> 00:31:44,780
>> และอีกครั้งจำได้ว่าตัดจัดเรียง
pseudocode เป็นซ้ำในความรู้สึก

742
00:31:44,780 --> 00:31:48,460
ว่าเป็นหนึ่งในขั้นตอนการตัดจัดเรียงของ
คือการเรียกการเรียงลำดับ -

743
00:31:48,460 --> 00:31:49,740
ซึ่งก็คือตัวเอง

744
00:31:49,740 --> 00:31:52,480
แต่โชคดีเพราะเราเก็บไว้
เรียกการเรียงลำดับหรือผสานเรียงลำดับ

745
00:31:52,480 --> 00:31:55,880
โดยเฉพาะเมื่อมีขนาดเล็กและขนาดเล็ก
และรายการที่มีขนาดเล็กที่สุดเราก็

746
00:31:55,880 --> 00:32:00,005
ขอบคุณจุดต่ำสุดไปกับสิ่งที่เราจะเรียก
กรณีฐานกรณีที่กำหนดค่าตายตัวว่า

747
00:32:00,005 --> 00:32:04,270
กล่าวว่าถ้ารายการที่มีขนาดเล็กน้อยกว่า 2
ในกรณีที่เพียงแค่กลับทันที

748
00:32:04,270 --> 00:32:07,550
ถ้าเราไม่ได้มีที่กรณีพิเศษ
อัลกอริทึมจะไม่เคยออกด้านล่าง,

749
00:32:07,550 --> 00:32:11,010
และแน่นอนคุณจะได้รับเป็น
ห่วงอนันต์อย่างแท้จริงตลอดไป

750
00:32:11,010 --> 00:32:14,330
>> แต่คิดว่าเราต้องการที่จะใส่ในขณะนี้
ตัวเลขบางอย่างเกี่ยวกับเรื่องนี้อีกครั้งโดยใช้ n

751
00:32:14,330 --> 00:32:15,660
เป็นขนาดของการป้อนข้อมูล

752
00:32:15,660 --> 00:32:18,680
และผมอยากจะถามคุณว่ามีอะไร
เวลาทั้งหมดที่มีส่วนร่วมใน

753
00:32:18,680 --> 00:32:19,800
วิ่งตัดจัดเรียง?

754
00:32:19,800 --> 00:32:22,960
หรือมากกว่าโดยทั่วไปสิ่งที่
ค่าใช้จ่ายของมันในเวลาหรือไม่

755
00:32:22,960 --> 00:32:24,730
>> ดีมันสวยง่ายที่จะวัดว่า

756
00:32:24,730 --> 00:32:29,010
ถ้า n เป็นน้อยกว่า 2 ครั้งที่เกี่ยวข้อง
ในการเรียงลำดับองค์ประกอบ n,

757
00:32:29,010 --> 00:32:30,480
โดยที่ n คือ 2 เท่ากับ 0

758
00:32:30,480 --> 00:32:31,410
เพราะเราเพิ่งกลับมา

759
00:32:31,410 --> 00:32:32,510
มีงานที่จะทำไม่ได้

760
00:32:32,510 --> 00:32:35,660
ตอนนี้เนื้อหาอาจจะเป็นขั้นตอนหนึ่งหรือสอง
ขั้นตอนที่จะคิดออกจำนวน

761
00:32:35,660 --> 00:32:38,420
ทำงาน แต่ก็ใกล้พอที่จะว่า 0
ฉันแค่ไปที่จะบอกว่าการทำงานไม่เป็น

762
00:32:38,420 --> 00:32:40,940
จำเป็นต้องใช้ถ้ารายการที่มีขนาดเล็กดังนั้น
ที่จะต้องทึ่ง

763
00:32:40,940 --> 00:32:42,580
>> แต่กรณีนี้เป็นที่น่าสนใจ

764
00:32:42,580 --> 00:32:47,320
กรณี recursive เป็นสาขาของ
pseudocode อื่นที่กล่าวว่าการจัดเรียง

765
00:32:47,320 --> 00:32:52,000
ครึ่งซ้าย, ขวาจัดเรียง
ครึ่งควบรวมทั้งสองส่วน

766
00:32:52,000 --> 00:32:55,530
ตอนนี้ทำไมการแสดงออกนี้จะ
เป็นตัวแทนของค่าใช้จ่ายที่

767
00:32:55,530 --> 00:32:58,690
ดีของ T n เพียงหมายถึง
เวลาในการจัดเรียงองค์ประกอบ n

768
00:32:58,690 --> 00:33:03,070
และจากนั้นในด้านขวามือของ
เท่ากับมี T ของ n แบ่ง

769
00:33:03,070 --> 00:33:06,600
2 หมายถึงค่าใช้จ่ายในสิ่งที่?

770
00:33:06,600 --> 00:33:07,570
การเรียงลำดับซีกซ้าย

771
00:33:07,570 --> 00:33:10,990
T อื่น ๆ ของ n หารด้วย 2
น่าจะหมายถึงค่าใช้จ่าย

772
00:33:10,990 --> 00:33:12,390
จัดเรียงครึ่งขวา

773
00:33:12,390 --> 00:33:14,590
>> แล้วบวก n?

774
00:33:14,590 --> 00:33:15,420
มีการควบรวมกิจการ

775
00:33:15,420 --> 00:33:19,120
เพราะถ้าคุณมีสองรายการหนึ่ง
n ขนาดกว่า 2 และอื่น ๆ ที่มีขนาด n

776
00:33:19,120 --> 00:33:22,580
กว่า 2 คุณต้องสัมผัสเป็นหลัก
แต่ละองค์ประกอบเหล่านั้นเช่นเดียวกับร็อบ

777
00:33:22,580 --> 00:33:24,990
สัมผัสแต่ละถ้วยและเพียง
ในขณะที่เราชี้ไปที่แต่ละ

778
00:33:24,990 --> 00:33:26,310
อาสาสมัครบนเวที

779
00:33:26,310 --> 00:33:28,790
ดังนั้น n เป็นค่าใช้จ่ายในการควบรวมกิจการ

780
00:33:28,790 --> 00:33:31,780
>> ตอนนี้โชคไม่ดีที่สูตรนี้
ยังเป็นตัวเองซ้ำ

781
00:33:31,780 --> 00:33:36,390
ดังนั้นถ้าถามคำถามถ้า n คือการพูด,
16 ถ้ามี 16 คนบนเวที

782
00:33:36,390 --> 00:33:40,670
หรือ 16 ถ้วยในวิดีโอทั้งหมดกี่
มันไม่ขั้นตอนใช้เวลาในการจัดเรียงพวกเขา

783
00:33:40,670 --> 00:33:41,550
มีการจัดเรียงที่ผสาน?

784
00:33:41,550 --> 00:33:45,790
เป็นจริงไม่ได้คำตอบที่ชัดเจน,
เพราะตอนนี้คุณต้องจัดเรียงของ

785
00:33:45,790 --> 00:33:48,500
ซ้ำคำตอบสูตรนี้

786
00:33:48,500 --> 00:33:51,190
>> แต่ที่ตกลงเพราะให้ฉันเสนอ
ที่เราทำดังต่อไปนี้

787
00:33:51,190 --> 00:33:56,670
เวลาที่เกี่ยวข้องในการจัดเรียง 16 คนหรือ
16 ถ้วยเป็นไปได้ที่เป็นตัวแทนของ

788
00:33:56,670 --> 00:33:58,020
โดยทั่วไปเป็น T จาก 16

789
00:33:58,020 --> 00:34:01,400
แต่นั่นเท่ากับเป็นไปตามของเรา
สูตรก่อนหน้านี้ 2 ครั้งจำนวน

790
00:34:01,400 --> 00:34:04,780
เวลาที่ใช้ในการจัดเรียง
8 ถ้วยบวก 16

791
00:34:04,780 --> 00:34:08,590
และอีกครั้งบวก 16 เป็นเวลาที่จะผสาน
และครั้งที่สอง T จาก 8 เป็น

792
00:34:08,590 --> 00:34:10,790
เวลาในการจัดเรียงครึ่งครึ่งซ้ายและขวา

793
00:34:10,790 --> 00:34:11,989
>> แต่อีกครั้งนี้ยังไม่เพียงพอ

794
00:34:11,989 --> 00:34:13,210
เราต้องดำน้ำลึกลงไปใน

795
00:34:13,210 --> 00:34:16,409
ซึ่งหมายความว่าเราจะต้องตอบ
คำถามสิ่งที่เป็นของ T-8?

796
00:34:16,409 --> 00:34:19,610
ดี T จาก 8 เพียง 2
ครั้ง T จาก 4 บวก 8

797
00:34:19,610 --> 00:34:20,520
ดีว่า T จาก 4 อะไร

798
00:34:20,520 --> 00:34:23,780
T จาก 4 เป็นเพียงครั้ง T 2 จาก 2 บวก 4

799
00:34:23,780 --> 00:34:25,489
ดี T จาก 2 อะไร

800
00:34:25,489 --> 00:34:29,030
T จาก 2 เป็นเพียง 2 ครั้งที 1 บวก 2

801
00:34:29,030 --> 00:34:31,940
>> และอีกครั้งที่เราไม่ชนิดของการ
ติดอยู่ในวงจรนี้

802
00:34:31,940 --> 00:34:34,790
แต่มันเกี่ยวกับการที่จะตีว่า
กรณีฐานที่เรียกว่า

803
00:34:34,790 --> 00:34:37,310
เพราะสิ่งที่ T 1 เราไม่เรียกร้อง?

804
00:34:37,310 --> 00:34:37,810
0

805
00:34:37,810 --> 00:34:39,730
ดังนั้นตอนนี้ในที่สุดเราสามารถทำงานไปข้างหลัง

806
00:34:39,730 --> 00:34:44,290
>> ถ้า T จาก 1 เป็น 0 ตอนนี้ผมสามารถกลับไปขึ้นหนึ่ง
สายผู้ชายคนนี้ที่นี่และฉันสามารถ

807
00:34:44,290 --> 00:34:46,330
เสียบ 0 T 1

808
00:34:46,330 --> 00:34:51,770
ดังนั้นหมายความว่าเท่ากับครั้งที่ 2 ศูนย์
หรือที่เรียกว่า 0, บวก 2

809
00:34:51,770 --> 00:34:53,739
และเพื่อให้การแสดงออกของทั้ง 2

810
00:34:53,739 --> 00:34:58,740
>> ตอนนี้ถ้าฉันใช้เวลา T 2, คำตอบ
เป็น 2 เสียบลงในสายกลาง, T

811
00:34:58,740 --> 00:35:02,740
จาก 4 ที่ทำให้ผม 2 ครั้ง
2 บวก 4 ดังนั้น 8

812
00:35:02,740 --> 00:35:07,080
ถ้าฉันแล้วเสียบใน 8 ถึงหน้าที่แล้ว
เส้นที่ทำให้ผม 2 ครั้ง 8, 16

813
00:35:07,080 --> 00:35:12,470
และถ้าเราแล้วดำเนินการต่อว่าด้วยความ
24 เพิ่ม 16 ในที่สุดเราได้รับ

814
00:35:12,470 --> 00:35:13,820
ค่าของ 64

815
00:35:13,820 --> 00:35:18,480
>> ขณะที่การจัดเรียงในและของตัวเองจากที่พูด
ไม่มีอะไรที่จะสัญกรณ์ n,

816
00:35:18,480 --> 00:35:20,700
O ใหญ่, โอเมก้าที่เราได้
ได้พูดคุยเกี่ยวกับ

817
00:35:20,700 --> 00:35:24,890
แต่มันกลับกลายเป็นว่า 64 แน่นอน
16 ขนาดของอินพุท,

818
00:35:24,890 --> 00:35:27,110
เข้าสู่ระบบฐาน 2 จาก 16

819
00:35:27,110 --> 00:35:30,200
และถ้าเป็นเพียงเล็กน้อยที่ไม่คุ้นเคยเพียง
กลับคิดว่ามันจะกลับมา

820
00:35:30,200 --> 00:35:30,700
กับคุณในที่สุด

821
00:35:30,700 --> 00:35:33,775
ถ้าเป็น log ฐาน 2 ก็เช่น 2
ยกสิ่งที่ช่วยให้คุณ 16?

822
00:35:33,775 --> 00:35:36,380
โอ้ที่ 4 ดังนั้นจึงเป็นครั้ง 16 4

823
00:35:36,380 --> 00:35:39,380
>> และอีกครั้งก็ไม่ได้เป็นเรื่องใหญ่ถ้านี้
การเรียงลำดับของหน่วยความจำมีหมอกอยู่ในขณะนี้

824
00:35:39,380 --> 00:35:43,720
แต่ตอนนี้ใช้เวลาในการศรัทธา
ที่ 16 ล็อก 16 คือ 64

825
00:35:43,720 --> 00:35:46,590
ดังนั้นแน่นอนมีสติแบบนี้
ตรวจสอบเราได้รับการยืนยัน -

826
00:35:46,590 --> 00:35:48,250
แต่ไม่ได้รับการพิสูจน์อย่างเป็นทางการ -

827
00:35:48,250 --> 00:35:52,800
ที่เวลาทำงานของจดหมายเวียน
เรียงลำดับเป็นที่แน่นอน n log n

828
00:35:52,800 --> 00:35:53,790
>> ดังนั้นไม่เลว

829
00:35:53,790 --> 00:35:57,260
มันแน่นอนดีกว่า
ขั้นตอนวิธีการที่เราได้เห็นป่านนี้และ

830
00:35:57,260 --> 00:36:00,710
มันเป็นเพราะเราได้ยกระดับหนึ่ง
เทคนิคที่เรียกว่าการเรียกซ้ำ

831
00:36:00,710 --> 00:36:03,880
แต่ที่น่าสนใจมากไปกว่านั้นว่า
ความคิดของการหารและชนะ

832
00:36:03,880 --> 00:36:07,460
อีกครั้งสัปดาห์อย่างแท้จริง 0 สิ่งที่
แม้ตอนนี้จะเกิดขึ้นใน

833
00:36:07,460 --> 00:36:08,740
วิธีที่น่าสนใจ

834
00:36:08,740 --> 00:36:11,750
>> ตอนนี้ออกกำลังกายน้อยความสนุกหากเราได้
เคยกระทำเช่นนี้ - และคุณอาจ

835
00:36:11,750 --> 00:36:14,660
จะได้ไม่ต้องเพราะการจัดเรียงของปกติ
คนไม่คิดว่าการทำเช่นนี้

836
00:36:14,660 --> 00:36:20,650
แต่ถ้าฉันไปที่ google.com และถ้า
ฉันต้องการที่จะเรียนรู้บางสิ่งบางอย่างเกี่ยวกับ

837
00:36:20,650 --> 00:36:22,356
เรียกซ้ำตัวเองใส่

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [เสียงหัวเราะ]

840
00:36:29,058 --> 00:36:32,030
[มีเสียงหัวเราะ]

841
00:36:32,030 --> 00:36:33,385
DAVID ลัน: ตลกร้ายแพร่กระจายอย่างช้าๆ

842
00:36:33,385 --> 00:36:34,450
[เสียงหัวเราะ]

843
00:36:34,450 --> 00:36:36,970
DAVID ลัน: ในกรณีที่มันมี

844
00:36:36,970 --> 00:36:38,710
ฉันไม่ได้สะกดผิด
และมีเรื่องตลกของ

845
00:36:38,710 --> 00:36:40,810
ทั้งหมดขวา

846
00:36:40,810 --> 00:36:42,950
อธิบายให้คนต่อไปกับคุณหาก
มันไม่ได้คลิกมากเพียง แต่

847
00:36:42,950 --> 00:36:47,650
แต่เรียกซ้ำตัวเองมากกว่าโดยทั่วไปหมายถึง
ถึงกระบวนการของการเรียกฟังก์ชัน

848
00:36:47,650 --> 00:36:51,430
เองหรือมากกว่าปกติหาร
ปัญหาเป็นสิ่งที่สามารถจะ

849
00:36:51,430 --> 00:36:56,220
แก้ทีละน้อยโดยการแก้เหมือนกัน
ปัญหาแทน

850
00:36:56,220 --> 00:36:58,400
>> ดีขอเปลี่ยนเกียร์
รอสักครู่

851
00:36:58,400 --> 00:37:00,840
เราต้องการที่จะสิ้นสุดใน cliffhangers บาง
ดังนั้นขอเริ่มต้นในการตั้งค่า

852
00:37:00,840 --> 00:37:05,870
เวทีหลายนาที
อยู่กับความคิดที่ง่ายมาก -

853
00:37:05,870 --> 00:37:07,620
ว่าจากการแลกเปลี่ยนสององค์ประกอบขวา?

854
00:37:07,620 --> 00:37:10,040
ทั้งหมดของขั้นตอนวิธีเหล่านี้เราได้รับ
พูดคุยเกี่ยวกับคู่ที่ผ่านมาของ

855
00:37:10,040 --> 00:37:12,420
การบรรยายเกี่ยวกับการบางอย่าง
การเรียงลำดับของการแลกเปลี่ยน

856
00:37:12,420 --> 00:37:14,630
วันนี้มันจะถูกมองเห็นโดยพวกเขาได้รับ
ขึ้นมาจากเก้าอี้ของพวกเขาและ

857
00:37:14,630 --> 00:37:18,570
เดินไปรอบ ๆ แต่ในรหัสเราจะ
เพียงแค่ใช้องค์ประกอบจากที่หนึ่งอาร์เรย์

858
00:37:18,570 --> 00:37:20,370
และป๋อมมันลงไปอีก

859
00:37:20,370 --> 00:37:21,880
>> เราดังนั้นวิธีการไปเกี่ยวกับการทำเช่นนี้?

860
00:37:21,880 --> 00:37:24,850
ดีให้ฉันไปข้างหน้าและเขียน
โปรแกรมด่วนที่นี่

861
00:37:24,850 --> 00:37:31,600
ฉันจะไปข้างหน้าและทำ
นี้ดังต่อไปนี้

862
00:37:31,600 --> 00:37:33,910
ขอเรียกนี้ -

863
00:37:33,910 --> 00:37:38,070
สิ่งที่เราต้องการเรียกนี้หนึ่ง?

864
00:37:38,070 --> 00:37:38,650
>> ที่จริงไม่มี

865
00:37:38,650 --> 00:37:39,420
ผมขอย้อนกลับ

866
00:37:39,420 --> 00:37:41,220
ฉันไม่ต้องการที่จะทำ
ยังน่าตื่นเต้น

867
00:37:41,220 --> 00:37:42,270
มันจะเสียความสนุกสนาน

868
00:37:42,270 --> 00:37:43,600
ขอทำนี้แทน

869
00:37:43,600 --> 00:37:47,430
>> สมมติว่าผมอยากจะเขียนเล็ก ๆ น้อย ๆ
และโปรแกรมที่ตอนนี้อ้อมกอดนี้

870
00:37:47,430 --> 00:37:48,700
ความคิดของการเรียกซ้ำ

871
00:37:48,700 --> 00:37:50,370
ชนิดของฉันได้ไปข้างหน้าของตัวเองมี

872
00:37:50,370 --> 00:37:51,420
ฉันจะทำต่อไปนี้

873
00:37:51,420 --> 00:38:00,220
>> ครั้งแรกอย่างรวดเร็วรวมถึงมาตรฐาน io.h,
เช่นเดียวกับการรวมของ cs50.h.

874
00:38:00,220 --> 00:38:03,200
แล้วฉันจะไปข้างหน้า
และประกาศเป็นโมฆะหลัก int

875
00:38:03,200 --> 00:38:04,360
ในทางปกติ

876
00:38:04,360 --> 00:38:07,920
ฉันตระหนักฉันได้ misnamed ไฟล์ดังนั้น
ให้ฉันเพียงแค่เพิ่ม. ขยายคที่นี่เพื่อให้

877
00:38:07,920 --> 00:38:09,510
ที่เราสามารถรวบรวมได้อย่างถูกต้อง

878
00:38:09,510 --> 00:38:10,970
เริ่มฟังก์ชั่นนี้ออกไป

879
00:38:10,970 --> 00:38:13,290
>> และฟังก์ชั่นที่ผมต้องการที่จะเขียนค่อนข้าง
ก็เป็นหนึ่งที่ถาม

880
00:38:13,290 --> 00:38:16,210
สำหรับจำนวนผู้ใช้และจากนั้นเพิ่มขึ้น
ตัวเลขทั้งหมดระหว่างที่

881
00:38:16,210 --> 00:38:19,920
จำนวนและการพูด, 0

882
00:38:19,920 --> 00:38:22,510
ดังนั้นครั้งแรกที่ฉันจะไปข้างหน้า
และประกาศ int n

883
00:38:22,510 --> 00:38:24,760
แล้วผมก็คัดลอกโค้ดบางอย่างที่
เราได้ใช้สำหรับในขณะที่

884
00:38:24,760 --> 00:38:26,660
ในขณะที่บางสิ่งบางอย่างเป็นความจริง

885
00:38:26,660 --> 00:38:28,000
ฉันจะกลับมาเพื่อที่ว่าในช่วงเวลาที่

886
00:38:28,000 --> 00:38:29,010
>> อะไรที่ฉันต้องการทำอะไร?

887
00:38:29,010 --> 00:38:33,460
ฉันต้องการจะบอกบวก printf
กรุณาจำนวนเต็ม

888
00:38:33,460 --> 00:38:36,130
แล้วฉันจะไป
พูด n ได้รับได้รับ int

889
00:38:36,130 --> 00:38:38,800
ดังนั้นอีกครั้งรหัสสำเร็จรูปบาง
ที่เราได้ใช้มาก่อน

890
00:38:38,800 --> 00:38:40,810
และฉันจะทำเช่นนี้
ในขณะที่ n คือน้อยกว่า 1

891
00:38:40,810 --> 00:38:44,120
ดังนั้นนี้จะให้แน่ใจว่าผู้ใช้
ให้ฉันเป็นจำนวนเต็มบวก

892
00:38:44,120 --> 00:38:45,490
>> และตอนนี้ฉันจะทำต่อไปนี้

893
00:38:45,490 --> 00:38:51,020
ฉันต้องการเพิ่มขึ้นทั้งหมดของตัวเลขที่
ระหว่างวันที่ 1 และ n หรือ 0 และ n,

894
00:38:51,020 --> 00:38:52,570
เท่ากันเพื่อให้ได้ผลรวม

895
00:38:52,570 --> 00:38:55,100
ดังนั้นสัญลักษณ์ซิกใหญ่
ที่คุณอาจจำ

896
00:38:55,100 --> 00:38:59,050
ดังนั้นฉันจะทำเช่นนี้โดยการโทรครั้งแรก
ฟังก์ชันที่เรียกว่าซิกม่า,

897
00:38:59,050 --> 00:39:06,030
ผ่านมันใน n และจากนั้นฉันจะไป
พูด printf คำตอบคือมีสิทธิ์

898
00:39:06,030 --> 00:39:08,180
>> ดังนั้นในระยะสั้นผมได้รับและ
int จากผู้ใช้

899
00:39:08,180 --> 00:39:09,280
ผมมั่นใจว่ามันเป็นบวก

900
00:39:09,280 --> 00:39:12,700
ฉันประกาศคำตอบที่เรียกว่าตัวแปร
ชนิด int และเก็บในมันกลับมา

901
00:39:12,700 --> 00:39:15,610
ค่าของซิกผ่านใน n เป็น input

902
00:39:15,610 --> 00:39:17,060
แล้วฉันพิมพ์ออกมาตอบว่า

903
00:39:17,060 --> 00:39:19,550
>> แต่น่าเสียดายที่แม้ว่าซิกเสียง
เหมือนบางสิ่งบางอย่างที่อาจจะมีใน

904
00:39:19,550 --> 00:39:24,040
ไฟล์ math.h การประกาศของ
มันไม่จริง

905
00:39:24,040 --> 00:39:24,690
เพื่อที่ว่าตกลง

906
00:39:24,690 --> 00:39:26,170
ฉันสามารถใช้นี้เอง

907
00:39:26,170 --> 00:39:29,160
ฉันจะใช้ฟังก์ชั่นที่เรียกว่า
ซิกและมันจะใช้เวลา

908
00:39:29,160 --> 00:39:29,900
พารามิเตอร์ -

909
00:39:29,900 --> 00:39:32,100
ให้เพียงเรียกมันเมตรเพียง
ดังนั้นจึงเป็นเรื่องที่แตกต่างกัน

910
00:39:32,100 --> 00:39:35,910
แล้วขึ้นที่นี่ฉันจะบอกว่า
ดีถ้า m มีค่าน้อยกว่า 1 - นี้เป็น

911
00:39:35,910 --> 00:39:38,180
น่าทึ่งมากโปรแกรม

912
00:39:38,180 --> 00:39:41,700
ดังนั้นฉันจะไปข้างหน้าและ
ทันทีกลับ 0

913
00:39:41,700 --> 00:39:45,920
มันก็ไม่ได้ทำให้ความรู้สึกที่จะเพิ่มขึ้นทั้งหมด
ตัวเลขระหว่าง 1 และ ม. ถ้าเมตร

914
00:39:45,920 --> 00:39:48,470
ตัวเองเป็น 0 หรือเชิงลบ

915
00:39:48,470 --> 00:39:50,900
>> แล้วฉันจะไปข้างหน้า
และทำซ้ำมาก

916
00:39:50,900 --> 00:39:53,090
ฉันจะทำเรียงลำดับของโรงเรียนเก่านี้
และฉันจะไปข้างหน้า

917
00:39:53,090 --> 00:39:57,150
และบอกว่าฉันกำลังจะไป
ประกาศผลรวมเป็น 0

918
00:39:57,150 --> 00:39:59,630
แล้วฉันจะมี
สำหรับวงของ int -

919
00:39:59,630 --> 00:40:02,820
และแจ้งให้เราทำมันเพื่อให้ตรงกับของเรา
รหัสการกระจายเพื่อให้คุณมีสำเนา

920
00:40:02,820 --> 00:40:07,500
ที่บ้าน int i ได้รับ 1 เมื่อขึ้นไป
i น้อยกว่าหรือเท่ากับเมตร

921
00:40:07,500 --> 00:40:09,430
ผมบวกบวก

922
00:40:09,430 --> 00:40:11,430
แล้วภายในของนี้สำหรับวง -

923
00:40:11,430 --> 00:40:12,440
เราเกือบจะมี -

924
00:40:12,440 --> 00:40:15,810
ผลรวมจะได้รับผลบวกบวก 1

925
00:40:15,810 --> 00:40:17,670
แล้วฉันจะกลับมารวมกัน

926
00:40:17,670 --> 00:40:19,420
>> ดังนั้นผมจึงทำอย่างนี้ได้อย่างรวดเร็ว
ค่อนข้างเป็นที่ยอมรับ

927
00:40:19,420 --> 00:40:22,775
แต่อีกครั้งที่ทำงานหลักสวย
ตรงไปตรงมาบนพื้นฐานของรหัสเราได้

928
00:40:22,775 --> 00:40:23,190
เขียนป่านนี้

929
00:40:23,190 --> 00:40:25,610
ใช้ห่วงคู่จะได้รับการบวก
int จากผู้ใช้

930
00:40:25,610 --> 00:40:29,870
จากนั้นผมก็ผ่าน int ที่ฟังก์ชั่นใหม่
ที่เรียกว่าซิกม่าเรียกมันอีกครั้ง n

931
00:40:29,870 --> 00:40:33,100
และฉันเก็บค่าตอบแทนคำตอบ
จากกล่องสีดำในขณะนี้

932
00:40:33,100 --> 00:40:35,460
หรือที่เรียกว่าซิกม่าในตัวแปร
คำตอบที่เรียกว่า

933
00:40:35,460 --> 00:40:36,580
แล้วฉันพิมพ์มัน

934
00:40:36,580 --> 00:40:39,090
>> ถ้าตอนนี้เรายังคงเรื่อง
วิธีการที่เป็นซิกดำเนินการ?

935
00:40:39,090 --> 00:40:40,840
ผมเสนอที่จะดำเนินการดังต่อไปนี้

936
00:40:40,840 --> 00:40:43,560
ก่อนนิด ๆ หน่อย ๆ ของข้อผิดพลาดการตรวจสอบ
เพื่อให้แน่ใจว่าผู้ใช้ไม่ได้

937
00:40:43,560 --> 00:40:46,480
messing กับฉันและผ่านใน
บางค่าลบหรือ 0

938
00:40:46,480 --> 00:40:49,710
แล้วผมประกาศตัวแปรที่เรียกว่า
สรุปผลและตั้งค่าให้ 0

939
00:40:49,710 --> 00:40:55,910
>> และตอนนี้ฉันเริ่มที่จะย้ายจาก i เท่ากับ
1 ตลอดทางขึ้นและรวมถึงเมตร

940
00:40:55,910 --> 00:41:00,130
เพราะฉันต้องการที่จะรวมทั้งหมด
ตัวเลขจากหนึ่งถึงเมตรรวม

941
00:41:00,130 --> 00:41:04,350
และภายในของสำหรับวงนี้ผมเพียงแค่ทำ
ผลรวมจะได้รับสิ่งที่มันเป็นอยู่ในปัจจุบันบวก

942
00:41:04,350 --> 00:41:08,900
ค่าของ i

943
00:41:08,900 --> 00:41:10,370
บวกค่าของ i

944
00:41:10,370 --> 00:41:14,090
>> เช่นกันถ้าคุณไม่เคยเห็นนี้
ก่อนที่จะมีบางประโยคน้ำตาลของ

945
00:41:14,090 --> 00:41:14,870
สำหรับบรรทัดนี้

946
00:41:14,870 --> 00:41:21,120
ฉันสามารถเขียนนี้เป็นบวกเท่ากับ i,
เพียงเพื่อประหยัดการกดแป้นพิมพ์ไม่กี่ตัวเอง

947
00:41:21,120 --> 00:41:22,570
และจะดูเย็นบิต

948
00:41:22,570 --> 00:41:23,140
แต่นั่นคือทั้งหมดที่

949
00:41:23,140 --> 00:41:24,660
มันเป็นหน้าที่ในสิ่งเดียวกัน

950
00:41:24,660 --> 00:41:26,710
>> แต่น่าเสียดายที่รหัสนี้ของ
ไม่ได้ไปรวบรวมยัง

951
00:41:26,710 --> 00:41:31,600
หากฉันใช้ทำซิก 0 วิธี am
ผมจะได้รับตะโกนใส่?

952
00:41:31,600 --> 00:41:33,473
มันเป็นสิ่งที่จะไม่ชอบ?

953
00:41:33,473 --> 00:41:35,740
>> ผู้ชม: [ได้ยิน]

954
00:41:35,740 --> 00:41:37,800
>> DAVID ลัน: ใช่ฉันไม่ได้ประกาศ
ฟังก์ชั่นขึ้นด้านบนขวา?

955
00:41:37,800 --> 00:41:40,590
C เป็นชนิดของโง่ในการที่จะเพียง
ไม่สิ่งที่คุณบอกให้ทำและคุณ

956
00:41:40,590 --> 00:41:41,880
ต้องทำมันในลำดับที่

957
00:41:41,880 --> 00:41:45,910
ดังนั้นถ้าผมกด Enter ที่นี่ฉันจะไป
ได้รับการเตือนเกี่ยวกับซิกม่าโดยปริยาย

958
00:41:45,910 --> 00:41:46,860
การประกาศ

959
00:41:46,860 --> 00:41:48,120
>> โอ้ไม่ได้มีปัญหา

960
00:41:48,120 --> 00:41:50,370
ฉันจะไปขึ้นไปด้านบนและฉันสามารถ
พูดขวาทั้งหมดรอสักครู่

961
00:41:50,370 --> 00:41:54,240
ซิกม่าเป็นฟังก์ชันที่ส่งกลับ
int และคาดว่า

962
00:41:54,240 --> 00:41:56,620
int เป็น input อัฒภาค

963
00:41:56,620 --> 00:41:59,550
หรือฉันสามารถใส่ฟังก์ชั่นทั้ง
หลักดังกล่าวข้างต้น แต่โดยทั่วไปผม

964
00:41:59,550 --> 00:42:02,260
แนะนำต่อว่าเพราะ
ดีเสมอมีหลักที่ด้านบนดังนั้น

965
00:42:02,260 --> 00:42:06,310
คุณสามารถดำน้ำที่ถูกต้องและรู้ว่าสิ่งที่
โปรแกรมทำโดยการอ่านหลักแรก

966
00:42:06,310 --> 00:42:07,930
>> ดังนั้นตอนนี้ให้ฉันล้างหน้าจอ

967
00:42:07,930 --> 00:42:09,330
remake 0 ซิก

968
00:42:09,330 --> 00:42:10,340
ทั้งหมดดูเหมือนว่าจะตรวจสอบออก

969
00:42:10,340 --> 00:42:11,970
ให้ฉันทำงานซิก 0

970
00:42:11,970 --> 00:42:12,770
บวกระหว่าง

971
00:42:12,770 --> 00:42:15,580
ฉันจะให้มันจำนวน
3 ให้มันง่าย

972
00:42:15,580 --> 00:42:18,710
ดังนั้นที่ควรให้ฉัน 3
บวก 2 บวก 1 ดังนั้น 6

973
00:42:18,710 --> 00:42:20,750
ใส่และแน่นอนฉันได้รับ 6

974
00:42:20,750 --> 00:42:21,820
>> ฉันสามารถทำสิ่งที่ใหญ่กว่า -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75

976
00:42:24,080 --> 00:42:27,690
เช่นเดียวกับที่สัมผัสผมจะทำ
บางสิ่งบางอย่างที่ไร้สาระเช่นใหญ่จริงๆ

977
00:42:27,690 --> 00:42:30,375
จำนวน Oh, ที่จริงออกไปทำงาน -

978
00:42:30,375 --> 00:42:31,600
เอ๊ะฉันไม่คิดที่เหมาะสม

979
00:42:31,600 --> 00:42:32,810
ลองมาดูกัน

980
00:42:32,810 --> 00:42:34,060
Let 's ยุ่งกับมันจริงๆ

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> นั่นเป็นปัญหา

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
สิ่งที่เกิดขึ้น?

985
00:42:44,970 --> 00:42:46,050
รหัสไม่ใช่ว่าไม่ดี

986
00:42:46,050 --> 00:42:48,470
ก็ยังคงเป็นเส้นตรง

987
00:42:48,470 --> 00:42:50,810
Whistling เป็นผลดี แต่

988
00:42:50,810 --> 00:42:52,060
สิ่งที่เกิดขึ้น?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> ไม่แน่ใจว่าฉันได้ยินมัน

991
00:42:55,620 --> 00:42:57,620
ดังนั้นมันจะเปิดออก - และ
นี้เป็นกัน

992
00:42:57,620 --> 00:42:59,400
นี้ไม่ได้เป็นหลัก
ความคิดของการเรียกซ้ำ

993
00:42:59,400 --> 00:43:02,480
มันจะเปิดออกเพราะฉันพยายามที่จะ
เป็นตัวแทนของดังกล่าวเป็นจำนวนที่ใหญ่ที่สุด

994
00:43:02,480 --> 00:43:06,980
มีแนวโน้มที่จะมีการตีความผิด
โดย C เป็นตัวเลขที่ไม่ดี,

995
00:43:06,980 --> 00:43:09,980
แต่จำนวนลบ

996
00:43:09,980 --> 00:43:12,690
>> เราไม่ได้พูดคุยเกี่ยวกับเรื่องนี้ แต่มัน
จะเปิดออกมีตัวเลขติดลบ

997
00:43:12,690 --> 00:43:14,210
ในโลกนอกจากนี้
ตัวเลขบวก

998
00:43:14,210 --> 00:43:16,290
และวิธีการที่คุณสามารถ
เป็นตัวแทนของจำนวนลบ

999
00:43:16,290 --> 00:43:19,530
หลักคือคุณใช้
บิตพิเศษที่จะระบุ

1000
00:43:19,530 --> 00:43:20,400
บวกลบ

1001
00:43:20,400 --> 00:43:22,950
มันเป็นเพียงเล็กน้อยที่ซับซ้อนมากขึ้นกว่าที่
แต่ที่แนวคิดพื้นฐาน

1002
00:43:22,950 --> 00:43:26,740
>> ดังนั้นโชคร้าย c ถ้าเป็นความสับสนหนึ่ง
ของบิตที่เป็นจริงความหมาย

1003
00:43:26,740 --> 00:43:30,790
โอ้นี้เป็นจำนวนลบห่วงฉัน
ที่นี่ตัวอย่างเช่นเป็นจริงไม่เคย

1004
00:43:30,790 --> 00:43:31,740
จะไปบอกเลิก

1005
00:43:31,740 --> 00:43:33,850
ดังนั้นถ้าฉันถูกพิมพ์จริงบางสิ่งบางอย่าง
อีกครั้งและอีกครั้งเราจะ

1006
00:43:33,850 --> 00:43:34,650
ดูเป็นจำนวนมากทั้ง

1007
00:43:34,650 --> 00:43:36,220
แต่อีกครั้งนี้นอกเหนือจากจุด

1008
00:43:36,220 --> 00:43:38,590
นี้เป็นจริงเพียงแค่การจัดเรียงของ
อยากรู้อยากเห็นทางปัญญาที่เราจะมา

1009
00:43:38,590 --> 00:43:39,550
กลับไปยังในที่สุด

1010
00:43:39,550 --> 00:43:43,400
แต่ตอนนี้ถูกต้อง
การดำเนินการถ้าเราคิดว่า

1011
00:43:43,400 --> 00:43:45,970
ผู้ใช้จะให้ ints
พอดีภายใน ints ว่า

1012
00:43:45,970 --> 00:43:49,370
>> แต่ผมเรียกร้องว่ารหัสนี้ตรงไปตรงมา
สามารถทำได้มากขึ้นเพียง

1013
00:43:49,370 --> 00:43:54,060
ถ้าเป้าหมายที่อยู่ในมือคือการใช้เป็นจำนวนมาก
เมตรเหมือนและเพิ่มขึ้นทั้งหมดของ

1014
00:43:54,060 --> 00:43:59,510
ตัวเลขระหว่างมันและ 1 หรือตรงกันข้าม
ระหว่างวันที่ 1 และมันก็เรียกร้อง

1015
00:43:59,510 --> 00:44:03,380
ที่ฉันสามารถยืมความคิดที่ผสานการนี​​้
เรียงลำดับได้ซึ่งเป็นปัญหาการ

1016
00:44:03,380 --> 00:44:05,660
ขนาดนี้แล้วหาร
เป็นสิ่งที่มีขนาดเล็กลง

1017
00:44:05,660 --> 00:44:09,875
บางทีไม่ได้ครึ่งหนึ่ง แต่มีขนาดเล็กลง แต่
representatively เดียวกัน

1018
00:44:09,875 --> 00:44:12,130
ความคิดที่เหมือนกัน แต่เป็นปัญหาที่มีขนาดเล็ก

1019
00:44:12,130 --> 00:44:15,470
>> ดังนั้นฉันจริง - ให้ฉันบันทึกแฟ้มนี้
ที่มีจำนวนรุ่นที่แตกต่างกัน

1020
00:44:15,470 --> 00:44:17,670
เราจะเรียกรุ่นนี้
1 แทน 0

1021
00:44:17,670 --> 00:44:20,790
และผมก็อ้างว่าฉันสามารถจริง
reimplement นี้ในการเรียงลำดับของเรื่องนี้

1022
00:44:20,790 --> 00:44:22,160
ทางใจดัด

1023
00:44:22,160 --> 00:44:23,710
>> ฉันจะออกจากส่วนหนึ่งของมันคนเดียว

1024
00:44:23,710 --> 00:44:27,710
ฉันจะบอกว่า ม. น้อย
กว่าหรือแม้กระทั่งเท่ากับ 0 -

1025
00:44:27,710 --> 00:44:29,280
ฉันแค่จะเล็ก ๆ น้อย ๆ
เวลานี้ทางทวารหนั​​กมากขึ้น

1026
00:44:29,280 --> 00:44:30,520
ที่มีการตรวจสอบข้อผิดพลาดของฉัน -

1027
00:44:30,520 --> 00:44:33,190
ฉันจะไปข้างหน้าและกลับ 0

1028
00:44:33,190 --> 00:44:34,490
นี้โดยพลการ

1029
00:44:34,490 --> 00:44:37,500
ฉันเพียงแค่การตัดสินใจหากผู้ใช้
ให้ฉันเป็นจำนวนลบผม

1030
00:44:37,500 --> 00:44:41,490
กลับ 0 และพวกเขาควรจะได้อ่าน
เอกสารที่ใกล้ชิดมากขึ้น

1031
00:44:41,490 --> 00:44:42,170
>> อื่น ๆ -

1032
00:44:42,170 --> 00:44:44,070
สังเกตเห็นสิ่งที่ฉันจะทำ

1033
00:44:44,070 --> 00:44:49,260
อื่นฉันจะกลับมาเอ็มพลัส -

1034
00:44:49,260 --> 00:44:51,010
ของ Sigma เมตรคืออะไร?

1035
00:44:51,010 --> 00:44:56,710
ดีของ Sigma เมตรบวกลบ 1 เมตร,
บวกลบ 2 เมตรบวกลบ 3 เมตร

1036
00:44:56,710 --> 00:44:58,030
ฉันไม่ต้องการที่จะเขียนทั้งหมดออกว่า

1037
00:44:58,030 --> 00:44:59,120
ทำไม่ได้เพราะเหตุใดฉันเพียงแค่ถ่อ?

1038
00:44:59,120 --> 00:45:05,080
recursively เรียกตัวเองด้วยเล็กน้อย
ปัญหาเล็กอัฒภาค

1039
00:45:05,080 --> 00:45:06,840
และเรียกได้ว่าเป็นวัน?

1040
00:45:06,840 --> 00:45:07,040
>> ใช่ไหม?

1041
00:45:07,040 --> 00:45:10,980
ตอนนี้ที่นี่, เกินไปคุณอาจจะรู้สึกหรือกังวล
ว่าเป็นห่วงอนันต์ว่าฉัน

1042
00:45:10,980 --> 00:45:15,450
เหนี่ยวนำด้วยเหตุนี้ฉันใช้
ซิกซิกม่าโทร

1043
00:45:15,450 --> 00:45:20,342
แต่ที่ตกลงอย่างสมบูรณ์เพราะฉัน
คิดไปข้างหน้าเพิ่มเส้นที่?

1044
00:45:20,342 --> 00:45:22,600
>> ผู้ชม: [ได้ยิน]

1045
00:45:22,600 --> 00:45:25,430
>> DAVID ลัน: 23-26 ซึ่ง
คือถ้าเงื่อนไขของฉัน

1046
00:45:25,430 --> 00:45:28,390
เพราะมีอะไรที่ดีเกี่ยวกับ
ลบที่นี่เพราะผมเก็บ

1047
00:45:28,390 --> 00:45:31,180
ส่งซิกปัญหาที่มีขนาดเล็กมีขนาดเล็ก
ปัญหาที่มีขนาดเล็ก - ยังไม่ได้

1048
00:45:31,180 --> 00:45:31,870
ครึ่งหนึ่งของขนาด

1049
00:45:31,870 --> 00:45:34,380
เป็นเพียงขั้นตอนที่ทารกมีขนาดเล็กลง
แต่ที่ตกลง

1050
00:45:34,380 --> 00:45:38,050
เพราะในที่สุดเราจะทำงาน
ทางลง 1 หรือ 0 ของเรา

1051
00:45:38,050 --> 00:45:41,630
และเมื่อเรากด 0, ซิกไม่
จะเรียกตัวเองอีกต่อไป

1052
00:45:41,630 --> 00:45:43,590
มันจะกลับทันที 0

1053
00:45:43,590 --> 00:45:47,960
>> ดังนั้นผลที่ออกมาถ้าคุณเรียงลำดับของลมนี้
ขึ้นมาในใจของคุณคือการเพิ่มเอ็มพลัส

1054
00:45:47,960 --> 00:45:52,740
ลบ 1 เมตรบวกลบ 2 เมตรบวกลบเมตร
3 บวกจุดจุดจุด, ม. ลบ

1055
00:45:52,740 --> 00:45:57,820
เมตรในท้ายที่สุดเพื่อให้คุณมี 0 และ
ผลท้ายที่สุดก็คือการเพิ่มของ

1056
00:45:57,820 --> 00:45:59,070
สิ่งเหล่านี้ร่วมกัน

1057
00:45:59,070 --> 00:46:02,380
ดังนั้นเราจึงยังไม่ได้มีการเรียกซ้ำ
แก้ปัญหาที่เรา

1058
00:46:02,380 --> 00:46:03,470
ไม่สามารถแก้ปัญหาก่อน

1059
00:46:03,470 --> 00:46:06,840
อันที่จริง 0 รุ่นนี้และทุก
ปัญหาถึงวันที่ได้รับแก้ไข

1060
00:46:06,840 --> 00:46:09,980
มีเพียงการใช้สำหรับลูปหรือในขณะที่
ลูปหรือโครงสร้างที่คล้ายกัน

1061
00:46:09,980 --> 00:46:13,150
>> แต่ recursion ผม daresay ทำให้เรา
เป็นวิธีที่แตกต่างกันของความคิดเกี่ยวกับ

1062
00:46:13,150 --> 00:46:17,010
ปัญหาที่เกิดขึ้นด้วยเหตุนี้ถ้าเราสามารถใช้
ปัญหาแบ่งมันออกมาจากบางสิ่งบางอย่าง

1063
00:46:17,010 --> 00:46:22,340
ค่อนข้างมีขนาดใหญ่เป็นสิ่งที่ค่อนข้าง
มีขนาดเล็กกว่าผมเรียกร้องว่าเราสามารถแก้ปัญหาได้

1064
00:46:22,340 --> 00:46:26,040
บางทีอาจจะเล็ก ๆ น้อย ๆ อย่างหรูหราในแง่
ของการออกแบบที่มีรหัสน้อย,

1065
00:46:26,040 --> 00:46:30,980
และอาจแก้ปัญหาที่จะ
จะยากที่เราจะไปในที่สุด

1066
00:46:30,980 --> 00:46:33,280
เห็นการแก้ปัญหาอย่างหมดจดซ้ำ

1067
00:46:33,280 --> 00:46:35,980
>> แต่ที่น่าตื่นเต้นที่ฉันไม่
ต้องการปล่อยให้เราเมื่อเป็นนี้

1068
00:46:35,980 --> 00:46:40,720
ให้ฉันไปข้างหน้าและเปิด
ไฟล์จาก -

1069
00:46:40,720 --> 00:46:44,300
จริงให้ฉันไปและ
ทำเช่นนี้ได้อย่างรวดเร็วจริง

1070
00:46:44,300 --> 00:46:46,875
ให้ฉันไปข้างหน้าและเสนอ
ดังต่อไปนี้

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
ในรหัสของวันนี้ไฟล์นี้อยู่ที่นี่

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
หนึ่งนี้ที่นี่ noswap

1075
00:47:03,050 --> 00:47:06,260
>> ดังนั้นนี่คือโปรแกรมเล็ก ๆ ที่โง่
วิปปิ้งขึ้นผมว่าการเรียกร้องที่จะทำ

1076
00:47:06,260 --> 00:47:06,940
ดังต่อไปนี้

1077
00:47:06,940 --> 00:47:10,140
ในหลักของมันเป็นครั้งแรกที่ประกาศ
เรียกว่า int x และกำหนดมัน

1078
00:47:10,140 --> 00:47:11,100
ค่า 1

1079
00:47:11,100 --> 00:47:13,520
จากนั้นก็จะประกาศ int y และ
จะกำหนดค่า 2

1080
00:47:13,520 --> 00:47:15,310
จากนั้นก็จะพิมพ์ออกจากสิ่งที่ x และ y คือ

1081
00:47:15,310 --> 00:47:17,781
จากนั้นก็กล่าวว่าการแลกเปลี่ยน, dot dot dot

1082
00:47:17,781 --> 00:47:21,670
>> จากนั้นก็จะอ้างว่าจะเรียกฟังก์ชั่น
ที่เรียกว่า swap ผ่านใน x และ

1083
00:47:21,670 --> 00:47:24,290
y, ความคิดของซึ่งเป็นที่หวัง
x และ y จะกลับมา

1084
00:47:24,290 --> 00:47:25,620
ที่แตกต่างกันตรงข้าม

1085
00:47:25,620 --> 00:47:27,110
จากนั้นก็จะเรียกร้องเปลี่ยน!

1086
00:47:27,110 --> 00:47:28,420
ที่มีเครื่องหมายอัศเจรีย์

1087
00:47:28,420 --> 00:47:30,190
จากนั้นก็จะพิมพ์ออก x และ y

1088
00:47:30,190 --> 00:47:33,480
>> แต่ปรากฎว่าเรื่องนี้มาก
สาธิตง่ายลง

1089
00:47:33,480 --> 00:47:35,570
ที่นี่เป็นจริงรถ

1090
00:47:35,570 --> 00:47:38,870
แม้ว่าฉันประกาศชั่วคราว
ตัวแปรชั่วคราวและวางใน

1091
00:47:38,870 --> 00:47:42,010
แล้วผม reassigning
ค่าของ b -

1092
00:47:42,010 --> 00:47:45,080
ซึ่งให้ความรู้สึกที่เหมาะสมเพราะฉัน
บันทึกสำเนาของอุณหภูมิใน

1093
00:47:45,080 --> 00:47:48,410
แล้วฉันจะปรับปรุงขเท่ากับ
อะไรก็ตามที่อยู่ในอุณหภูมิ

1094
00:47:48,410 --> 00:47:51,610
การจัดเรียงของเกมเปลือกของการย้ายนี้
เป็น B and B ลงโดยใช้นี้

1095
00:47:51,610 --> 00:47:54,360
กลางคนที่เรียกว่าอุณหภูมิรู้สึก
ที่เหมาะสมอย่างสมบูรณ์แบบ

1096
00:47:54,360 --> 00:47:57,270
>> แต่ผมเรียกร้องว่าเมื่อฉันทำงานนี้
รหัสที่ผมจะทำตอนนี้ -

1097
00:47:57,270 --> 00:47:59,490
ให้ฉันไปข้างหน้าและวางไว้ในที่นี่

1098
00:47:59,490 --> 00:48:01,995
ฉันจะเรียกนี้ noswap.c

1099
00:48:01,995 --> 00:48:05,630
และเป็นชื่อที่แนะนำนี้ไม่ได้เป็น
จะเป็นโปรแกรมที่ถูกต้อง

1100
00:48:05,630 --> 00:48:09,460
ทำให้ noswap. swap / ไม่มี

1101
00:48:09,460 --> 00:48:12,110
x 1, y คือ 2 แลกเปลี่ยน

1102
00:48:12,110 --> 00:48:14,220
x 1, y คือ 2

1103
00:48:14,220 --> 00:48:16,920
นี้เป็นธรรมพื้นฐานแม้
แม้ว่านี้ดูเหมือนว่าสมบูรณ์แบบ

1104
00:48:16,920 --> 00:48:17,730
ที่เหมาะสมกับผม

1105
00:48:17,730 --> 00:48:21,330
และมีเหตุผล แต่เราไม่
จะเผยให้เห็นเหตุผลเพียง แต่

1106
00:48:21,330 --> 00:48:24,610
>> สำหรับตอนที่สองที่น่าตื่นเต้นที่ฉันต้องการ
จะทำให้คุณมีวันนี้,

1107
00:48:24,610 --> 00:48:27,120
ประกาศของแปลก ๆ เกี่ยวกับรหัสคูปอง

1108
00:48:27,120 --> 00:48:31,590
นวัตกรรมกับวันช่วงปลายปีนี้ของเรา
มีเคืองเป็นจำนวนที่ไม่น่ารำคาญ

1109
00:48:31,590 --> 00:48:33,830
ของคำถามซึ่งเป็น
ไม่ใช่ความตั้งใจของเรา

1110
00:48:33,830 --> 00:48:36,590
ความตั้งใจของเหล่านี้รหัสคูปอง,
ด้วยเหตุนี้ถ้าคุณทำส่วนหนึ่งของปัญหา

1111
00:48:36,590 --> 00:48:39,850
ตั้งช่วงต้นจึงได้รับวันพิเศษ,
เป็นจริงที่จะช่วยให้พวกคุณช่วย

1112
00:48:39,850 --> 00:48:42,420
ตัวเองเริ่มต้นเรียงลำดับต้น
โดย incentivizing คุณ

1113
00:48:42,420 --> 00:48:44,880
ช่วยให้เรากระจายโหลดผ่าน
เวลาทำงานที่ดีขึ้นเพื่อให้

1114
00:48:44,880 --> 00:48:45,740
มันเรียงลำดับของชนะ

1115
00:48:45,740 --> 00:48:48,860
>> แต่น่าเสียดายที่ผมคิดว่าคำแนะนำของฉัน
ยังไม่ได้รับถึงวันที่ชัดเจนมากดังนั้น

1116
00:48:48,860 --> 00:48:52,230
ฉันก็กลับวันหยุดสุดสัปดาห์นี้และมีการปรับปรุง
ในสเปคที่ใหญ่กว่าข้อความที่โดดเด่นยิ่งขึ้นไป

1117
00:48:52,230 --> 00:48:53,600
อธิบายกระสุนเช่นนี้

1118
00:48:53,600 --> 00:48:56,900
และเพียงแค่จะบอกว่ามันขึ้นต่อสาธารณชนโดย
ค่าเริ่มต้นชุดปัญหาเนื่องจากพฤหัสบดี

1119
00:48:56,900 --> 00:48:58,400
ตอนเที่ยงต่อหลักสูตร

1120
00:48:58,400 --> 00:49:02,030
หากคุณเริ่มต้นเป็นส่วนหนึ่งของการตกแต่ง
ปัญหาที่กำหนดโดยพุธ at 12:00

1121
00:49:02,030 --> 00:49:05,170
PM เป็นส่วนหนึ่งที่เกี่ยวข้องกับคูปอง
รหัสความคิดคือการที่คุณสามารถขยาย

1122
00:49:05,170 --> 00:49:07,710
กำหนดเวลาของคุณสำหรับ
P กำหนดถึงวันศุกร์

1123
00:49:07,710 --> 00:49:10,890
นั่นคือบิตออกเป็นส่วนหนึ่งเล็ก ๆ ของ P
ตั้งญาติกับสิ่งที่มักจะเป็น

1124
00:49:10,890 --> 00:49:13,200
ปัญหาขนาดใหญ่และคุณซื้อ
ตัวเองในวันพิเศษ

1125
00:49:13,200 --> 00:49:15,190
อีกครั้งก็ทำให้คุณได้รับความคิดเกี่ยวกับ
ชุดปัญหาที่ทำให้คุณได้รับไป

1126
00:49:15,190 --> 00:49:16,380
เวลาทำงานเร็ว

1127
00:49:16,380 --> 00:49:20,670
แต่ปัญหาที่รหัสคูปองยังคงเป็น
ต้องแม้ว่าคุณจะไม่ได้ส่งมัน

1128
00:49:20,670 --> 00:49:23,340
>> แต่ที่ร้องขอนี้

1129
00:49:23,340 --> 00:49:26,520
(กระซิบ) และคนเหล่านั้นออก
ต้นจะไม่เสียใจมัน

1130
00:49:26,520 --> 00:49:28,620
ในฐานะที่เป็นคนบนระเบียงที่มี

1131
00:49:28,620 --> 00:49:32,510
ผมต้องขออภัยล่วงหน้าเพื่อ folks เมื่อ
ระเบียงสำหรับเหตุผลที่จะ

1132
00:49:32,510 --> 00:49:33,920
ล้างในเวลาเพียงสักครู่

1133
00:49:33,920 --> 00:49:37,050
>> เพื่อให้เรามีโชคดีที่มีหนึ่งใน
CS50 ของพวกอดีตหัวหน้าการเรียนการสอนที่

1134
00:49:37,050 --> 00:49:39,302
บริษัท ที่เรียกว่า dropbox.com

1135
00:49:39,302 --> 00:49:45,500
พวกเขาได้บริจาคเงินจำนวนมากอย่างไม่เห็นแก่ตัว
คูปองรหัสที่นี่สำหรับพื้นที่มากนี้

1136
00:49:45,500 --> 00:49:48,180
ซึ่งเพิ่มขึ้นจาก
ปกติ 2 กิกะไบต์

1137
00:49:48,180 --> 00:49:51,740
ดังนั้นสิ่งที่ฉันคิดว่าเราจะทำอะไรเกี่ยวกับเรื่องนี้
โน้ตตัวสุดท้ายคือทำบิตของแถม,

1138
00:49:51,740 --> 00:49:55,380
ด้วยเหตุนี้ในเวลาเพียงสักครู่เราจะเปิดเผย
ผู้ชนะและผู้ที่มีคูปอง

1139
00:49:55,380 --> 00:49:57,980
รหัสที่คุณแล้วสามารถไปของพวกเขา
เว็บไซต์พิมพ์ใน, และ voila รับ

1140
00:49:57,980 --> 00:50:01,370
พื้นที่ Dropbox มากทั้งมากขึ้นสำหรับคุณ
และเครื่องใช้สำหรับไฟล์ส่วนบุคคลของคุณ

1141
00:50:01,370 --> 00:50:05,690
>> และเป็นครั้งแรกที่ต้องการเข้าร่วม
ในรูปวาดนี้?

1142
00:50:05,690 --> 00:50:09,630
ตกลงตอนนี้ที่ทำให้มันสนุกมากยิ่งขึ้น

1143
00:50:09,630 --> 00:50:14,010
บุคคลที่ได้รับนี้กิกะไบต์ 25
รหัสคูปอง - ที่อยู่ไกล

1144
00:50:14,010 --> 00:50:16,150
น่าสนใจมากขึ้นกว่าช่วงปลายปี
วันนี้อาจจะเป็น -

1145
00:50:16,150 --> 00:50:20,620
คือคนที่จะนั่งอยู่ด้านบนของ
เบาะนั่งด้านล่างที่มี

1146
00:50:20,620 --> 00:50:21,620
รหัสคูปองที่

1147
00:50:21,620 --> 00:50:23,480
ตอนนี้คุณอาจดูด้านล่าง
เบาะที่นั่งของคุณ

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [เล่นภาพวิดีโอ]

1150
00:50:29,680 --> 00:50:31,620
>> หนึ่งสองสาม

1151
00:50:31,620 --> 00:50:35,015
>> [กรีดร้อง]

1152
00:50:35,015 --> 00:50:35,985
>> -คุณจะได้รับรถ!

1153
00:50:35,985 --> 00:50:36,670
คุณจะได้รับรถ!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID ลัน: เราจะเห็น
คุณในวันพุธที่

1155
00:50:37,970 --> 00:50:38,904
>> -คุณจะได้รับรถ!

1156
00:50:38,904 --> 00:50:39,371
คุณจะได้รับรถ!

1157
00:50:39,371 --> 00:50:40,305
คุณจะได้รับรถ!

1158
00:50:40,305 --> 00:50:41,706
คุณจะได้รับรถ!

1159
00:50:41,706 --> 00:50:43,107
คุณจะได้รับรถ!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID ลัน: folks, ระเบียงมา
ลงที่นี่ไปข้างหน้า

1161
00:50:45,530 --> 00:50:46,866
ที่เรามีความพิเศษ

1162
00:50:46,866 --> 00:50:50,282
>> ทุกคนได้รับรถ-!

1163
00:50:50,282 --> 00:50:52,234
ทุกคนได้รับรถ!

1164
00:50:52,234 --> 00:50:52,722
>> [เล่นวิดีโอจบ]

1165
00:50:52,722 --> 00:50:54,590
>> เล่าเรื่อง: ตอนต่อไป CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> 5 SPEAKER: โอ้พุทโธ่เอ้ยเอ้ย my gosh!
เอ้เอ้เอ้เอ้เอ้เอ้ย -

1167
00:51:00,374 --> 00:51:02,106
>> [เล่นกีตาร์]