1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> ลำโพงอยู่ด้านขวาทั้งหมดนี้เป็น CS50

3
00:00:14,910 --> 00:00:19,020
นี่คือจุดสิ้นสุดของสัปดาห์ที่สามและถ้า
คุณยังไม่ได้ใช้ประโยชน์แล้ว

4
00:00:19,020 --> 00:00:21,790
ทราบว่าจะมีอาหารกลางวัน
วันศุกร์นี้ตามปกติท​​ี่

5
00:00:21,790 --> 00:00:25,430
คุณสามารถเพลิดเพลินกับการสนทนาที่ดี
และอาหารที่ไฟและน้ำแข็ง

6
00:00:25,430 --> 00:00:27,980
กับบางส่วนของ CS50 ของ
พนักงานและเพื่อนร่วมชั้น

7
00:00:27,980 --> 00:00:30,170
มุ่งหน้าไปยัง URL ที่นี่

8
00:00:30,170 --> 00:00:33,420
>> ตอนนี้คุณอาจจำหรือคุณ
อาจจะเร็ว ๆ นี้จะคุ้นเคยกับ

9
00:00:33,420 --> 00:00:35,970
สิ่งเหล่านี้ที่นี่ซึ่ง
จะได้รับออกมาในตอนท้าย

10
00:00:35,970 --> 00:00:37,850
ภาคการศึกษาสำหรับการเรียนหลาย

11
00:00:37,850 --> 00:00:40,870
ที่เรียกว่าสอบหนังสือสีฟ้าที่
คุณเขียนคำตอบของการสอบ

12
00:00:40,870 --> 00:00:44,240
ตอนนี้ฉันมีที่นี่ 26 ดังกล่าว
หนังสือสีฟ้าของเขาแต่ละคน

13
00:00:44,240 --> 00:00:47,580
เขียนชื่อถึง Z และ
แน่นอนชื่อที่ง่าย

14
00:00:47,580 --> 00:00:50,490
ถึง Z และหนึ่งใน
เป้าหมายที่อยู่ในมือวันนี้

15
00:00:50,490 --> 00:00:53,910
เป็นไปได้ที่จะดำเนินการสิ่งที่
เราเริ่มต้นในวันจันทร์ซึ่งไม่

16
00:00:53,910 --> 00:00:57,830
มากกำลังมองหาที่รหัส แต่จริงๆ
มองไปที่ความคิดและการแก้ปัญหา

17
00:00:57,830 --> 00:01:00,170
หนึ่งในเป้าหมายและ
สัญญาของหลักสูตรนี้

18
00:01:00,170 --> 00:01:02,985
คือการสอนให้คุณคิดว่ามากขึ้น
อย่างระมัดระวังมากขึ้นมีระบบ,

19
00:01:02,985 --> 00:01:05,400
และการแก้ปัญหาที่มีประสิทธิภาพมากขึ้น

20
00:01:05,400 --> 00:01:09,526
และแน่นอนเราสามารถทำอย่างนั้นจริงๆ
โดยไม่ต้องแตะบรรทัดของรหัส

21
00:01:09,526 --> 00:01:12,150
ดังนั้นผมจึงมีคู่ของช้าง
ที่นี่วันนี้สีส้มและสีฟ้า

22
00:01:12,150 --> 00:01:15,780
ถ้าเราสามารถได้รับหนึ่งอาสาสมัคร
อาจจะมาจากที่ไกลออกไปกลับกว่าปกติ

23
00:01:15,780 --> 00:01:18,070
วิธีการเกี่ยวกับสิทธิที่มีมาลง

24
00:01:18,070 --> 00:01:24,180
เป้าหมายที่เป็นไปได้ที่จะ
ช่วยบวกจัดการสอบที่นี่

25
00:01:24,180 --> 00:01:24,935
คุณชื่ออะไร?

26
00:01:24,935 --> 00:01:25,768
>> ผู้ชม: แมรี่เบ ธ

27
00:01:25,768 --> 00:01:27,560
ลำโพง: แมรี่เบ ธ มาขึ้น

28
00:01:27,560 --> 00:01:29,560
ให้ฉันได้รับไมโครโฟนที่นี่สำหรับคุณ

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
มีความสุขที่ได้พบคุณ

31
00:01:32,880 --> 00:01:34,005
>> ผู้ชม: ยินดีที่ได้พบคุณ

32
00:01:34,005 --> 00:01:36,790
ลำโพง: สิทธิทั้งหมดเพื่อให้ฉันมี
ที่นี่หนังสือสีฟ้าถึง Z

33
00:01:36,790 --> 00:01:41,680
และฉันจะแกล้งทำเป็นว่า
ฉันมีหนึ่งของนักเรียน

34
00:01:41,680 --> 00:01:45,770
และพวกเขากำลังมาค่อนข้างสุ่ม
ที่ส่วนท้ายของบล็อกสอบสามชั่วโมง

35
00:01:45,770 --> 00:01:49,400
ดังนั้นพวกเขาจึงกำลังสิ้นสุดขึ้นในบางส่วน
เพื่อกึ่งสุ่มเช่นนี้

36
00:01:49,400 --> 00:01:54,510
ตอนนี้งานของคุณในเวลาเพียงช่วงเวลาที่เกิด
เพื่อ be-- นี้เป็นจริงว่าพวกเขาได้รับ

37
00:01:54,510 --> 00:01:56,820
หันในตอนท้ายของ
ชั้นที่มีโอกาสมากที่สุด

38
00:01:56,820 --> 00:02:01,120
งานของคุณตอนนี้เป็นไปได้ค่อนข้าง
เพียงแค่การจัดเรียงหนังสือสีฟ้าเหล่านี้สำหรับเรา

39
00:02:01,120 --> 00:02:05,220
จากถึง Z

40
00:02:05,220 --> 00:02:08,400
>> ผู้ชม: โอ้นี้เป็น
จะใช้เวลาตลอด

41
00:02:08,400 --> 00:02:13,747
>> ลำโพง: และเราจะดู
ในขณะที่คุณทำเช่นนี้ไม่มีความกดดัน

42
00:02:13,747 --> 00:02:15,330
ผู้ชม: ไม่มีแรงกดดันหรืออะไร

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> ลำโพง: และเพื่อความสนุกสนาน
ขอนำค่าตัวจับเวลา

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> ผู้ชม: สนุกมากสนุกมาก

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> ลำโพง: ฉันสามารถถือไมค์สำหรับคุณ

49
00:02:38,574 --> 00:02:40,240
สิทธิทั้งหมดที่เราได้เพียงแค่สองเท่าความเร็วของเรา

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
ดังนั้นในระหว่างนี้ให้ฉันสิ่งที่ก่อให้เกิด
จะเป็นคำถามสำหรับแมรี่เบ ธ

52
00:02:49,060 --> 00:02:51,540
เป็นสิ่งที่เธอทำว่าเป็น
เธอจะเกี่ยวกับการแก้ปัญหานี้ได้อย่างไร

53
00:02:51,540 --> 00:02:54,040
และในความเป็นจริงคุณไม่อาจมี
เคยคิดเกี่ยวกับบางสิ่งบางอย่าง

54
00:02:54,040 --> 00:02:57,440
เพื่อให้ง่ายเมื่อคุณเลือก
เพิ่มขึ้น 26 หนังสือเช่นนี้

55
00:02:57,440 --> 00:02:59,350
ซึ่งจะมีตามธรรมชาติ
สั่งให้พวกเขา

56
00:02:59,350 --> 00:03:01,335
เป็นกระบวนการอะไร
จริงที่คุณใช้งานหรือไม่

57
00:03:01,335 --> 00:03:03,770
มันเป็นเพียงแค่การสุ่มอย่างเป็นธรรม
การเลือกคนแรกที่คุณเห็น

58
00:03:03,770 --> 00:03:05,250
และวางไว้ในสถานที่?

59
00:03:05,250 --> 00:03:09,680
อย่าแรกที่คุณย้ายมือของคุณไปรอบ
มองหาแล้วมองหา B?

60
00:03:09,680 --> 00:03:11,722
คุณจะดูที่
คู่ของพวกเขาด้านข้าง

61
00:03:11,722 --> 00:03:14,680
และเพียงแค่บอกว่ารอสักครู่นี้
ไม่ถูกต้องและจากนั้นสลับการสั่งซื้อหรือไม่

62
00:03:14,680 --> 00:03:16,960
เราเห็นแล้วในวันจันทร์ที่
ว่ามีหลายวิธี

63
00:03:16,960 --> 00:03:22,140
ที่เราสามารถทำเช่นนี้และ
แน่นอนในขณะที่เราใกล้จะจบที่นี่

64
00:03:22,140 --> 00:03:26,360
ผมจะรับทราบอาจจะ
ของสิ่งที่แมรี่เบ ธ จะทำ

65
00:03:26,360 --> 00:03:30,040
เรามีไม่กี่กองดูเหมือนว่า
หนึ่งที่ใหญ่กว่าสามคนเล็ก

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> ผู้ชม: ฉันสั่งให้พวกเขา
เมื่อผมพบจดหมายสองฉบับ

68
00:03:36,415 --> 00:03:39,540
ที่ฉันรู้ว่ามีอยู่ด้วยกันในลำดับ
ฉันทำให้พวกเขาร่วมกันเพื่อที่ฉันทำไม่ได้

69
00:03:39,540 --> 00:03:42,915
ต้องกังวลเกี่ยวกับการรักษา
ติดตามทั้งแถวของหนังสือ

70
00:03:42,915 --> 00:03:45,706
มันก็แค่โอเป็นครั้งแรก
ฉันมีสแต็คที่นี่

71
00:03:45,706 --> 00:03:47,580
ลำโพง: ดังนั้นเกือบจะเหมือน
ชิ้นส่วนปริศนาที่

72
00:03:47,580 --> 00:03:49,860
มีรูปร่างที่เหมาะสมที่จะ
ตรงกับแต่ละอื่น ๆ

73
00:03:49,860 --> 00:03:51,026
ผู้ชม: สวยมากจ้ะ

74
00:03:51,026 --> 00:03:55,320
ลำโพง: ตกลงที่ดีเยี่ยม

75
00:03:55,320 --> 00:03:59,850
และตอนนี้แต่ละเหล่านี้
กองจะถูกจัดเรียงอย่างน่า?

76
00:03:59,850 --> 00:04:00,990
>> ผู้ชม: ใช่

77
00:04:00,990 --> 00:04:09,900
>> ลำโพง: สิทธิทั้งหมดถึง Z ทั้งหมด
ที่ถูกต้องขอแสดงความยินดีที่คุณทำมัน

78
00:04:09,900 --> 00:04:11,461
คุณมีทางเลือกของคุณ

79
00:04:11,461 --> 00:04:11,960
สีฟ้า?

80
00:04:11,960 --> 00:04:13,530
สิทธิทั้งหมดขอบคุณที่

81
00:04:13,530 --> 00:04:16,679
ดังนั้นแมรี่เบ ธ ไม่เสนอ
สิ่งที่วิธีการของเธอคือ

82
00:04:16,679 --> 00:04:19,720
แต่คือสิ่งที่อีกวิธีหนึ่งวิธีการที่คุณ
อาจจะไปเกี่ยวกับการเรียงลำดับสิ่งเหล่านี้หรือไม่

83
00:04:19,720 --> 00:04:21,130
สิ่งที่คุณจะได้ทำ?

84
00:04:21,130 --> 00:04:24,060
บันทึกที่จะชนะจะได้รับ
หนึ่งนาทีและ 50 หรือดังนั้นวินาที

85
00:04:24,060 --> 00:04:26,039
บวกคนที่ฉันลืมที่จะนับ

86
00:04:26,039 --> 00:04:27,080
สิ่งที่คุณจะได้ทำ?

87
00:04:27,080 --> 00:04:27,579
ใช่?

88
00:04:27,579 --> 00:04:28,735
ผู้ชม: ใช้สแต็ค

89
00:04:28,735 --> 00:04:29,776
เริ่มต้นจากจุดเริ่มต้น

90
00:04:29,776 --> 00:04:32,284
ตรวจสอบเอกสารของคุณ

91
00:04:32,284 --> 00:04:36,586
และถ้าหนึ่งด้านบนที่สูง
กว่าบางทีที่พวกเขาเป็น

92
00:04:36,586 --> 00:04:38,980
หนึ่งล่างคือ
ที่สูงขึ้นแล้วสลับพวกเขา

93
00:04:38,980 --> 00:04:41,300
>> ลำโพง: OK เพื่อเริ่มต้น
ที่ด้านบนและด้านล่าง

94
00:04:41,300 --> 00:04:43,716
แล้ววิธีการทำงานของคุณ
ขาเข้าเช่นนั้นการแลกเปลี่ยนพวกเขา?

95
00:04:43,716 --> 00:04:46,580
OK เพื่อให้เล็ก ๆ น้อย ๆ ที่คล้ายกัน
ในจิตวิญญาณในการเรียงลำดับฟอง

96
00:04:46,580 --> 00:04:49,160
แต่เลือกขั้ว
ไม่ได้คู่ที่อยู่ติดกัน

97
00:04:49,160 --> 00:04:52,080
แต่ระยะสั้นของมันคือการที่มี
แน่นอนพวงของวิธีการที่แตกต่างกัน

98
00:04:52,080 --> 00:04:54,210
เราสามารถทำเช่นนี้และ
ตรงไปตรงมาผมคิดว่าคุณชนิดของ

99
00:04:54,210 --> 00:04:55,700
นำสองวิธีใช่มั้ย?

100
00:04:55,700 --> 00:05:00,567
คุณทำให้การจัดเรียงของสี่เรียงกองและ
จากนั้นได้อย่างมีประสิทธิภาพรวมเข้าด้วยกัน

101
00:05:00,567 --> 00:05:02,650
และที่, daresay อีก
เทคนิคทั้งหมด

102
00:05:02,650 --> 00:05:06,950
คุณไม่ได้รักษามันเป็นกองใหญ่หนึ่ง
คุณแบ่งปัญหาออกเป็นสี่คณะสี่คน,

103
00:05:06,950 --> 00:05:09,820
ถ้าคุณจะแล้วอย่างใด
รวมพวกเขาในท้ายที่สุด

104
00:05:09,820 --> 00:05:13,410
>> เพื่อให้พิจารณาในที่สุด
วิธีอื่นที่เราอาจจะทำเช่นนี้

105
00:05:13,410 --> 00:05:15,860
เรากรงเล็บความคิด
ของฟองเรียงครั้งสุดท้าย

106
00:05:15,860 --> 00:05:18,780
และการเรียกคืนการจัดเรียงฟองเป็น
อัลกอริทึมที่เรามองเห็น

107
00:05:18,780 --> 00:05:22,640
กับแปดของเพื่อนร่วมชั้นของคุณที่นี่
ดูเหมือนจะถูกจัดเรียงแบบสุ่มในตอนแรก

108
00:05:22,640 --> 00:05:26,110
และเราจึงตัดสินใจจับคู่ถ้า
สององค์ประกอบที่จะออกคำสั่ง

109
00:05:26,110 --> 00:05:26,950
เพียงแค่สลับพวกเขา

110
00:05:26,950 --> 00:05:28,930
ดังนั้นสี่และทั้งสองมี
เห็นได้ชัดว่าออกคำสั่ง

111
00:05:28,930 --> 00:05:31,080
ดังนั้นทั้งสองเพื่อนร่วมชั้น
ตำแหน่งเปลี่ยน

112
00:05:31,080 --> 00:05:35,390
แล้วเราซ้ำกับสี่และหก
จากนั้นหกและแปดในแต่ละซ้ำ,

113
00:05:35,390 --> 00:05:36,980
ย้ายไปทางขวา

114
00:05:36,980 --> 00:05:42,590
>> ให้ดังนั้นแปดคนกี่คู่
เปรียบเทียบผมทำในขณะที่เดินจาก

115
00:05:42,590 --> 00:05:45,220
จากซ้ายไปขวาในหนึ่งซ้ำเช่น?

116
00:05:45,220 --> 00:05:48,410
หลายวิธีการเปรียบเทียบ?

117
00:05:48,410 --> 00:05:49,197
เซเว่นใช่มั้ย?

118
00:05:49,197 --> 00:05:51,405
เพราะถ้ามีแปด
คน แต่คุณมีคู่

119
00:05:51,405 --> 00:05:53,880
พวกเขาและคุณให้ย้าย
หนึ่งกระโดดไปทางขวา

120
00:05:53,880 --> 00:05:56,060
คุณไม่ได้จะมีแปด
เปรียบเทียบเพราะคุณไม่สามารถเปรียบเทียบ

121
00:05:56,060 --> 00:05:59,226
องค์ประกอบกับตัวเองหรือมันจะ
เพียงแค่จะไม่มีจุดหมายเพื่อให้คุณมีเจ็ด

122
00:05:59,226 --> 00:06:01,290
หรือมากกว่าโดยทั่วไปถ้า
เรามี n คนเรา

123
00:06:01,290 --> 00:06:04,300
ทำ n ลบ 1 การเปรียบเทียบ
ด้วยการจัดเรียงฟอง

124
00:06:04,300 --> 00:06:08,150
>> เพื่อให้พิจารณาตอนนี้วิธีที่ดีหรือ
ฟองไม่ดีการจัดเรียงเป็นจริงและพยายาม

125
00:06:08,150 --> 00:06:13,570
เพื่อให้ตัวเองกับคำศัพท์
ซึ่งขั้นตอนวิธีการวิจารณ์เช่นนี้

126
00:06:13,570 --> 00:06:14,430
และเร็ว ๆ นี้ของเราเอง

127
00:06:14,430 --> 00:06:16,970
เพื่อให้ผ่านครั้งแรกผ่าน
การจัดเรียงฟองเป็นครั้งแรกที่

128
00:06:16,970 --> 00:06:20,909
ผมเดินจากซ้ายไปทางขวาข้าม
เวทีเอาฉัน n ลบ 1 การเปรียบเทียบ

129
00:06:20,909 --> 00:06:22,950
และนั่นจะเป็นของฉัน
หน่วยของการวัดใช่มั้ย?

130
00:06:22,950 --> 00:06:26,170
ผมชนิดของการพูดคุยและเดินเล่น
ค่อนข้างรวดเร็วค่อนข้างช้า

131
00:06:26,170 --> 00:06:29,300
เพื่อนับจำนวนของวินาที
ไม่ได้โดยเฉพาะอย่างยิ่งบอก

132
00:06:29,300 --> 00:06:32,260
แต่นับจำนวนของ
การดำเนินงานที่ผมทำในวันจันทร์ที่

133
00:06:32,260 --> 00:06:35,900
เปรียบเทียบคนสองคนที่รู้สึก
เช่นหน่วยที่ดีของวัด

134
00:06:35,900 --> 00:06:40,980
>> ดังนั้น n ลบ 1 ขั้นตอนที่เป็นครั้งแรกที่
แต่แล้วสิ่งที่เกิดขึ้นหลังจากที่?

135
00:06:40,980 --> 00:06:46,610
สิ่งหนึ่ง upside อีกหนึ่งผ่าน
ผ่านรายการที่ไม่ได้เรียงลำดับอย่างอื่น?

136
00:06:46,610 --> 00:06:49,840
สิ่งที่คุณสามารถบอกฉันเกี่ยวกับองค์ประกอบ
ซึ่งเป็นทางไปที่นั่นหรือไม่

137
00:06:49,840 --> 00:06:51,300
ใช่?

138
00:06:51,300 --> 00:06:52,870
นั่นเป็นองค์ประกอบที่ใหญ่ที่สุดใช่มั้ย?

139
00:06:52,870 --> 00:06:55,710
หมายเลขแปดแม้ว่าเธอ
เริ่มที่นี่ทุกครั้งที่ผม

140
00:06:55,710 --> 00:06:57,860
เมื่อเทียบกับของเธอกับ
เพื่อนบ้านของเธอเก็บไว้

141
00:06:57,860 --> 00:07:00,480
เดือดปุด ๆ ขึ้นไปทางขวา
ด้านซ้ายมือของรายการ

142
00:07:00,480 --> 00:07:02,710
และแน่นอนว่าเป็นที่
อัลกอริทึมที่ได้รับชื่อของมัน

143
00:07:02,710 --> 00:07:07,630
>> โดยตรรกะที่กี่เปรียบเทียบ
ฉันต้องทำในครั้งที่สอง

144
00:07:07,630 --> 00:07:09,800
ผมให้ผ่านจากซ้ายไปขวา?

145
00:07:09,800 --> 00:07:10,730
n ลบ 2 ใช่มั้ย?

146
00:07:10,730 --> 00:07:14,297
มันก็จะเสียเวลาของฉันหากฉัน
ให้เปรียบเทียบแปดกับใครบางคน

147
00:07:14,297 --> 00:07:16,630
อื่นเพราะเรารู้อยู่แล้ว
เธออยู่ในสถานที่ที่เหมาะสม

148
00:07:16,630 --> 00:07:19,760
เพื่อให้เป็นบิตของ
การเพิ่มประสิทธิภาพเพื่อให้ผ่านไป

149
00:07:19,760 --> 00:07:23,899
เป็นไปได้บวก n ลบสองขั้นตอน
ที่ n คือจำนวนของผู้คน

150
00:07:23,899 --> 00:07:26,940
ตอนนี้คุณชนิดของสามารถคาดการณ์ได้
ถ้าคุณไม่ได้เป็นนักวิทยาศาสตร์คอมพิวเตอร์

151
00:07:26,940 --> 00:07:27,680
วิธีนี้จะสิ้นสุดลง

152
00:07:27,680 --> 00:07:31,259
ในตอนท้ายของขั้นตอนวิธีนี้สันนิษฐาน
คุณได้มีเพียงแค่การเปรียบเทียบหนึ่งที่เหลือ

153
00:07:31,259 --> 00:07:33,800
คุณมีชนิดของการแก้ไขปัญหา
จุดเริ่มต้นของรายการในกรณีที่สอง

154
00:07:33,800 --> 00:07:36,540
และมีการออกคำสั่ง
และควรจะเป็นหนึ่งและสอง

155
00:07:36,540 --> 00:07:40,330
ดังนั้นนี้ bottoms ออกที่
บวก 1 เปรียบเทียบสุดท้าย

156
00:07:40,330 --> 00:07:44,500
>> ตอนนี้จุดจุด, จุดชนิดของคลื่นมัน
มือที่บางส่วนของรายละเอียด juicier,

157
00:07:44,500 --> 00:07:46,452
แต่ขอเพียงไปข้างหน้าและลดความซับซ้อน

158
00:07:46,452 --> 00:07:48,660
ถ้าคุณจำจากที่สูง
โรงเรียนตรงไปตรงมามากของคุณ

159
00:07:48,660 --> 00:07:50,340
มีหนังสือคณิตศาสตร์ที่มี
แผ่นโกงเล็ก ๆ น้อย ๆ

160
00:07:50,340 --> 00:07:52,550
บนหน้าปกหรือ
ปกหลังแสดงให้เห็นว่าคุณ

161
00:07:52,550 --> 00:07:56,400
summations สิ่งที่ชุดเช่น
ท้ายที่สุดนี้ได้เพิ่มขึ้นถึง

162
00:07:56,400 --> 00:07:59,600
ในกรณีทั่วไปถ้าคุณมี
เช่นตัวแปร n และแน่นอนคนนี้

163
00:07:59,600 --> 00:08:01,634
ถ้าคุณมองไปที่ของคุณ
หนังสือคณิตศาสตร์โรงเรียนเก่า

164
00:08:01,634 --> 00:08:04,050
คุณจะเห็นว่านี้จริง
เพิ่มขึ้นจำนวนนี้ที่นี่

165
00:08:04,050 --> 00:08:07,970
ครั้ง n n ลบ 1 ทั้งหมดหารด้วย 2

166
00:08:07,970 --> 00:08:11,172
ดังนั้นสำหรับตอนนี้ให้ฉันเพียงกำหนด
นี้เป็นจริงดังนั้นในการก้าวกระโดดของความเชื่อที่

167
00:08:11,172 --> 00:08:12,880
นั่นคือสิ่งที่สรุปนี้
ขึ้นไปและที่เราจะทำได้

168
00:08:12,880 --> 00:08:14,341
พิสูจน์ให้เห็นว่าในกรณีทั่วไปมากขึ้น

169
00:08:14,341 --> 00:08:15,590
แต่ตอนนี้ขอขยายออกไปนี้

170
00:08:15,590 --> 00:08:19,920
ดังนั้นลองคูณนี้ออกมาเพื่อให้เป็น
n กำลังสองลบ n แบ่งออกทุก 2

171
00:08:19,920 --> 00:08:23,200
ที่จริง n ยกกำลัง
หารด้วย 2 ลบ n กว่า 2

172
00:08:23,200 --> 00:08:25,010
ดังนั้นนั่นคือทั้งหมดที่ดีและน่าสนใจ

173
00:08:25,010 --> 00:08:27,060
แต่สิ่งที่เกิดขึ้นถ้าเรา
ตอนนี้ plug-in มูลค่า?

174
00:08:27,060 --> 00:08:29,724
สมมติว่าผมไม่ได้มีแปด
คน แต่บอกว่าล้าน

175
00:08:29,724 --> 00:08:31,890
และล้านเพียงเพราะ
มันเป็นจำนวนมากสวย

176
00:08:31,890 --> 00:08:34,039
ให้เสียบที่และดูสิ่งที่เกิดขึ้น

177
00:08:34,039 --> 00:08:39,039
ดังนั้นถ้าผมเสียบล้านเป็นสูตรที่
ฉันจะได้รับล้านยกกำลัง

178
00:08:39,039 --> 00:08:42,868
หารด้วย 2 ลบ
ล้านบาทโดยแบ่งออกเป็น 2

179
00:08:42,868 --> 00:08:44,159
ตอนนี้สิ่งที่ว่าจะเท่ากับ?

180
00:08:44,159 --> 00:08:47,354
ดังนั้น 500000000000 ลบ 500,000

181
00:08:47,354 --> 00:08:49,270
และถ้าผมทำจริง
คณิตศาสตร์ให้เห็นว่าวิธีการที่

182
00:08:49,270 --> 00:08:53,920
ที่เรียงลำดับล้าน
คนที่มีการจัดเรียงฟอง

183
00:08:53,920 --> 00:09:01,800
อาจจะใช้เวลาฉัน 499999500000
ขั้นตอนหรือการเปรียบเทียบในท้ายที่สุด

184
00:09:01,800 --> 00:09:02,900
เราเพียงแค่คะเน

185
00:09:02,900 --> 00:09:06,860
>> ที่ให้ความรู้สึกช้าสวย แต่ตรงไปตรงมา
การวัดกำลังหนึ่งโดยเฉพาะ

186
00:09:06,860 --> 00:09:09,160
เช่นนี้ไม่ได้ทั้งหมดบอกว่า

187
00:09:09,160 --> 00:09:14,050
แต่จริง ๆ แล้วมันไม่แสดงให้เห็นว่าเป็น n
ได้รับขั้นตอนวิธีนี้มีขนาดใหญ่และขนาดใหญ่

188
00:09:14,050 --> 00:09:16,280
ชนิดของความรู้สึกที่แย่ลงและ
แย่ลงหรือคุณจริงๆ

189
00:09:16,280 --> 00:09:20,450
เริ่มที่จะรู้สึกเจ็บปวดจากการที่
แทน, n ที่ยกกำลัง

190
00:09:20,450 --> 00:09:21,770
ซึ่งจะเพิ่มขึ้นอย่างรวดเร็ว

191
00:09:21,770 --> 00:09:25,340
และรายละเอียดที่นี้ไม่ได้
หายไปกับคนที่ในความเป็นจริง

192
00:09:25,340 --> 00:09:29,640
บางปีที่ผ่านมาสมาชิกวุฒิสภาบางคนที่เป็น
รณรงค์นั่งลงสำหรับการสัมภาษณ์

193
00:09:29,640 --> 00:09:32,180
ด้วย Google ของเอริค
มิดท์ซีอีโอในเวลานั้น

194
00:09:32,180 --> 00:09:36,380
และกำลังถูกท้าทายด้วยคำถาม
เหมือนเรากำลังสำรวจวันนี้

195
00:09:36,380 --> 00:09:38,468
ลองมาดู

196
00:09:38,468 --> 00:09:45,280
>> [วิดีโอเล่นภาพ]

197
00:09:45,280 --> 00:09:48,560
>> -Senator คุณอยู่ที่นี่
ที่ Google และผมชอบ

198
00:09:48,560 --> 00:09:53,382
ที่จะคิดของประธานาธิบดี
เช่นการสัมภาษณ์งาน

199
00:09:53,382 --> 00:09:56,434
ตอนนี้มันเป็นเรื่องยากที่จะได้รับ
งานเป็นประธาน

200
00:09:56,434 --> 00:09:58,100
และคุณกำลังจะผ่านความโหดร้ายนี้

201
00:09:58,100 --> 00:10:01,860
นอกจากนี้ยังเป็นเรื่องยากที่จะได้รับงานที่ Google

202
00:10:01,860 --> 00:10:05,490
เรามีคำถามและเรา
ขอให้ผู้สมัครคำถามของเรา

203
00:10:05,490 --> 00:10:09,770
และหนึ่งนี้จากลาร์รีชวิมเม

204
00:10:09,770 --> 00:10:14,760
What-- พวกคุณคิดว่าฉัน
ล้อเล่นมันเป็นสิทธิที่นี่

205
00:10:14,760 --> 00:10:17,930
สิ่งที่เป็นวิธีที่มีประสิทธิภาพที่สุดในการ
ค้นหาล้านจำนวนเต็ม 32 บิต?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -I'm ขอโทษ maybe--

209
00:10:25,200 --> 00:10:27,400
>> ไม่มีไม่มีไม่มี

210
00:10:27,400 --> 00:10:30,700
ผมคิดว่าการจัดเรียงฟอง
จะเป็นวิธีที่ผิดไป

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -Come ที่ใครบอกเขานี้

213
00:10:38,180 --> 00:10:40,590
ฉันไม่เห็นคอมพิวเตอร์
วิทยาศาสตร์ในพื้นหลังของคุณ

214
00:10:40,590 --> 00:10:42,130
>> -We've มีสายลับของเราในการมี

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK ให้ถามที่แตกต่างกัน
คำถามสัมภาษณ์

217
00:10:48,444 --> 00:10:49,300
>> [จบการเล่นวิดีโอ]

218
00:10:49,300 --> 00:10:52,290
>> ลำโพง: ดังนั้นการพูดคุยเกี่ยวกับ
ตัวเลขที่ระบุว่า

219
00:10:52,290 --> 00:10:53,890
จะไม่เป็นสิ่งที่มีประโยชน์

220
00:10:53,890 --> 00:10:56,810
มันไม่ได้เป็นบทเรียนชีวิตที่ฟอง
การจัดเรียงให้ล้านปัจจัยการผลิต

221
00:10:56,810 --> 00:10:58,590
อาจจะใช้เวลามากที่สุดเท่าที่ 500000000000 ขั้นตอน

222
00:10:58,590 --> 00:11:01,120
คุณไม่สามารถพูดคุยจริงๆ
ได้อย่างมีประสิทธิภาพเกินไปจากที่

223
00:11:01,120 --> 00:11:03,560
และการตัดสินใจการออกแบบที่ดี
เมื่อเขียนโปรแกรม

224
00:11:03,560 --> 00:11:07,070
ดังนั้นขอเน้นว่าวิธีการที่
เราอาจจะลดความซับซ้อนของผลนี้

225
00:11:07,070 --> 00:11:11,780
>> ดังนั้นผมจึงได้เน้นสีเหลืองที่นี่
ผลของ n สองหารด้วย 2

226
00:11:11,780 --> 00:11:14,330
ดังนั้นล้านกำลังสอง
หารด้วย 2 แล้ว

227
00:11:14,330 --> 00:11:16,710
ผมได้เน้นสิ่งที่
ตอบที่ดีที่สุดคือ

228
00:11:16,710 --> 00:11:20,180
เมื่อเราหักออก n หารด้วย 2

229
00:11:20,180 --> 00:11:24,850
และเรียกร้องที่ฉันจะทำตอนนี้คือ
ที่ห่าใส่ใจถ้าคุณลบออก

230
00:11:24,850 --> 00:11:30,060
n อายุน้อยกว่า 2 ครั้งแรกเมื่อ
ส่วนหนึ่งของสูตรนี้จึงใหญ่มาก?

231
00:11:30,060 --> 00:11:33,910
มันครอบงำอื่น ๆ
ระยะ n สองหารด้วย 2

232
00:11:33,910 --> 00:11:37,510
เป็นสิ่งที่ใหญ่กว่ามากอย่างเห็นได้ชัดเช่น
n ได้รับขนาดใหญ่เช่นล้าน

233
00:11:37,510 --> 00:11:41,450
ที่มีจริงๆความแตกต่างใหญ่ที่
ตอนท้ายของวันระหว่าง 500,000,000,000

234
00:11:41,450 --> 00:11:45,730
และ 499999500000?

235
00:11:45,730 --> 00:11:46,349
ไม่ได้จริงๆ

236
00:11:46,349 --> 00:11:48,640
และเพื่อให้สิ่งที่เรากำลังจะไป
ทำตามที่นักวิทยาศาสตร์คอมพิวเตอร์

237
00:11:48,640 --> 00:11:53,270
ไม่สนใจคำสั่งของผู้ที่ต่ำกว่าและ
ใช้บางอย่างเช่นนี้จริงๆ

238
00:11:53,270 --> 00:11:56,050
เพียงแค่ลดความซับซ้อนของมันไป
ระยะที่จะมีความสำคัญ

239
00:11:56,050 --> 00:12:00,315
ชุดข้อมูลขนาดใหญ่ของเราได้รับที่ใหญ่กว่า
ฐานข้อมูลของเราได้รับที่หน้าเว็บ

240
00:12:00,315 --> 00:12:02,690
เรามีการค้นหามากขึ้น
เพื่อนที่คุณมีใน Facebook

241
00:12:02,690 --> 00:12:07,340
>> เป็น n ได้รับใหญ่เราไม่ได้จริงๆ
จะดูแลเกี่ยวกับการที่ใหญ่ที่สุด

242
00:12:07,340 --> 00:12:11,560
ระยะในการวิเคราะห์ดังกล่าว
ประสิทธิภาพการทำงานของอัลกอริทึมของเรา

243
00:12:11,560 --> 00:12:16,230
และฉันจะบอกว่าคุณรู้ว่าสิ่งที่
การจัดเรียงฟองเป็นคำสั่งของโอใหญ่

244
00:12:16,230 --> 00:12:18,060
โดยคำสั่งของ n กำลังสอง

245
00:12:18,060 --> 00:12:20,090
มันไม่ตรง n
กำลังสองในขณะที่เราได้เห็น

246
00:12:20,090 --> 00:12:22,060
แต่ผู้ที่ใส่ใจจริงๆ
เกี่ยวกับคำที่มีขนาดเล็กเหล่านั้น

247
00:12:22,060 --> 00:12:24,390
และตรงไปตรงมาที่จริงๆ
ใส่ใจถ้าเราหารด้วย 2 หรือไม่?

248
00:12:24,390 --> 00:12:25,870
นั่นเป็นเพียงปัจจัยคง

249
00:12:25,870 --> 00:12:29,480
และเป็น 500,000,000,000 เมื่อเทียบกับ 250
พันล้านจริงๆที่ใหญ่ของการจัดการหรือไม่

250
00:12:29,480 --> 00:12:32,190
ฉันจะรอหนึ่งปี
ให้แล็ปท็อปของฉันอย่างแท้จริง

251
00:12:32,190 --> 00:12:34,810
ได้รับสองครั้งที่รวดเร็วในด้านฮาร์ดแวร์
และการเรียงลำดับของความแตกต่างที่

252
00:12:34,810 --> 00:12:36,650
เพียงแค่ออกไปตามธรรมชาติเมื่อเวลาผ่านไป

253
00:12:36,650 --> 00:12:39,300
>> สิ่งที่เราสนใจคือ
การแสดงออกเป็นส่วนหนึ่ง

254
00:12:39,300 --> 00:12:42,489
ในการแสดงออกที่จะแตกต่างกันไป
เป็นอินพุทของเราได้รับใหญ่และขนาดใหญ่

255
00:12:42,489 --> 00:12:45,280
และแน่นอนในโลกจริง
นั่นคือสิ่งที่เกิดขึ้นมากขึ้น

256
00:12:45,280 --> 00:12:48,330
เป็นปัจจัยการผลิตในการแก้ไขปัญหาของเราและ
อัลกอริทึมที่มีการเดินทางที่ใหญ่กว่า

257
00:12:48,330 --> 00:12:53,470
ดังนั้น O ใหญ่จะเป็นสัญกรณ์ที่
สัญกรณ์เชิงว่าเราเพียงแค่

258
00:12:53,470 --> 00:12:57,160
ใช้เป็นนักวิทยาศาสตร์คอมพิวเตอร์ที่จะอธิบาย
ประสิทธิภาพการทำงานหรือเวลาทำงานที่

259
00:12:57,160 --> 00:12:58,130
ของอัลกอริทึม

260
00:12:58,130 --> 00:13:00,800
เพื่อให้เราสามารถเปรียบเทียบอัลกอริทึม
บนเครื่องคอมพิวเตอร์ที่แตกต่างกันเป็นลายลักษณ์อักษร

261
00:13:00,800 --> 00:13:04,170
โดยคนที่แตกต่างกันโดยใช้
บางตัวชี้วัดพื้นฐานที่คล้ายกัน

262
00:13:04,170 --> 00:13:07,557
เช่นจำนวนของการเปรียบเทียบคุณ
การทำหรืออาจจะจำนวนของสัญญาแลกเปลี่ยน

263
00:13:07,557 --> 00:13:08,140
คุณกำลังทำ

264
00:13:08,140 --> 00:13:11,910
>> สิ่งที่เราไม่ได้ไป
นับเป็นระยะเวลาที่

265
00:13:11,910 --> 00:13:13,981
ที่ผ่านบนนาฬิกา
บนผนังโดยทั่วไป

266
00:13:13,981 --> 00:13:16,230
สิ่งที่เราจะไม่ต้องกังวล
เกี่ยวกับการเป็นหน่วยความจำเท่าใด

267
00:13:16,230 --> 00:13:17,820
ที่คุณใช้ในวันนี้ที่
น้อย แต่ที่

268
00:13:17,820 --> 00:13:19,370
ทรัพยากรที่เราอาจจะวัดอื่น

269
00:13:19,370 --> 00:13:23,610
เราจะพยายามที่จะฐานการวิเคราะห์ของเรา
เพียงการดำเนินงานพื้นฐานคนที่

270
00:13:23,610 --> 00:13:25,930
ตรงไปตรงมาเห็นว่าคุณสามารถเห็นส่วนใหญ่

271
00:13:25,930 --> 00:13:30,700
ดังนั้นกับสิ่งที่ต้องการ O ใหญ่ของ n
กำลังสองผมอ้างว่า O ของ n กำลังสอง

272
00:13:30,700 --> 00:13:35,820
เป็นขอบเขตบนที่เรียกว่า
ใช้เวลาของการจัดเรียงฟอง

273
00:13:35,820 --> 00:13:38,820
ในคำอื่น ๆ ถ้าคุณ
ต้องการที่จะอ้างว่ามี

274
00:13:38,820 --> 00:13:41,370
ขีด จำกัด บนนี้ในหลายวิธี
ขั้นตอนวิธีการอาจจะใช้เวลา

275
00:13:41,370 --> 00:13:46,240
มันจะอยู่ในโอใหญ่ของ n
กำลังสองในกรณีนี้บนปก

276
00:13:46,240 --> 00:13:49,710
>> ถ้าฉันเปลี่ยนแทน
เรื่องราวจะเป็นไม่เกี่ยวกับการจัดเรียงฟอง

277
00:13:49,710 --> 00:13:50,910
แต่เกี่ยวกับเรื่องนี้บนปก

278
00:13:50,910 --> 00:13:54,030
คุณสามารถคิดของอัลกอริทึม
ที่เราได้มองที่แล้ว

279
00:13:54,030 --> 00:13:59,530
บนปกสูงสุดที่มี,
วัดเวลาหรือการดำเนินงาน

280
00:13:59,530 --> 00:14:04,300
จะได้รับการบอกว่าจะกระโดด
ด้วย n ฟังก์ชันเชิงเส้น

281
00:14:04,300 --> 00:14:07,260
ไม่หนึ่งกำลังสองที่โค้ง?

282
00:14:07,260 --> 00:14:10,780
คือสิ่งที่อัลกอริทึมที่
มักจะใช้เวลาไม่มาก

283
00:14:10,780 --> 00:14:12,860
กว่าเหมือนขั้นตอนที่ n หรือ
ขั้นตอน 2n หรือขั้นตอน 3n?

284
00:14:12,860 --> 00:14:13,360
ใช่?

285
00:14:13,360 --> 00:14:15,030
>> ผู้ชม: หา
จำนวนที่ใหญ่ที่สุดในรายการหรือไม่

286
00:14:15,030 --> 00:14:16,930
>> ลำโพง: ที่สมบูรณ์แบบในการค้นหา
หมายเลขที่ใหญ่ที่สุดในรายการ

287
00:14:16,930 --> 00:14:18,940
ถ้าฉันได้รับรายชื่อของ
คนเช่น

288
00:14:18,940 --> 00:14:21,440
แต่ละที่มีการถือครองหมายเลข
สิ่งที่เป็นจำนวนสูงสุด

289
00:14:21,440 --> 00:14:23,770
ในขั้นตอนที่มันควรจะใช้เวลาฉัน
เป็นคนที่สมาร์ทพอสมควร

290
00:14:23,770 --> 00:14:27,530
ที่จะหาคนที่ใหญ่ที่สุดในรายการที่?

291
00:14:27,530 --> 00:14:28,100
n ขวา?

292
00:14:28,100 --> 00:14:31,320
เพราะในกรณีที่เลวร้ายที่สุดที่
ค่าที่ใหญ่ที่สุดอาจจะมี?

293
00:14:31,320 --> 00:14:32,700
ขวาตลอดทางที่สิ้นสุด

294
00:14:32,700 --> 00:14:34,575
ดังนั้นในกรณีที่เลวร้ายที่สุด
บนผูกพันฉันอาจ

295
00:14:34,575 --> 00:14:36,450
ต้องไปตลอดทาง
กว่าที่นี่และมีความเหมือน

296
00:14:36,450 --> 00:14:39,170
โอ้นี่เป็นจำนวนแปด
หรืออะไรก็ตามที่ค่าที่

297
00:14:39,170 --> 00:14:41,330
ตอนนี้ก็เพียงแค่จะโง่
ถ้าฉันยังคงต้องไปใช่มั้ย?

298
00:14:41,330 --> 00:14:43,840
มองหาองค์ประกอบมากขึ้นและมากขึ้น
ถ้าสุดท้ายคือที่นั่น?

299
00:14:43,840 --> 00:14:45,340
ดังนั้นแน่นอน n คือบนผูกพัน

300
00:14:45,340 --> 00:14:47,420
ฉันไม่ต้องการที่จะใช้
ขั้นตอนที่มากไปกว่านั้น

301
00:14:47,420 --> 00:14:51,580
>> ดังนั้นสิ่งที่ถ้าแทนฉันเสนอว่า
มีขั้นตอนวิธีการในโลกนี้ที่

302
00:14:51,580 --> 00:14:57,750
มีเวลาในการทำงานที่
จำกัด โดย O ใหญ่ของล็อก n, log n?

303
00:14:57,750 --> 00:15:00,390
ที่เราได้เห็นนี้มาก่อนหรือไม่

304
00:15:00,390 --> 00:15:00,890
ใช่?

305
00:15:00,890 --> 00:15:03,309
>> ผู้ชม: ในปัญหาสมุดโทรศัพท์?

306
00:15:03,309 --> 00:15:04,850
ลำโพง: ชอบปัญหาสมุดโทรศัพท์

307
00:15:04,850 --> 00:15:07,754
สิ่งที่เป็นตัวชี้วัดของวิธีการ
เวลามากหรือจำนวนน้ำตามัน

308
00:15:07,754 --> 00:15:10,170
เอาผมที่จะหาคนอย่าง
ไมค์สมิ ธ ในสมุดโทรศัพท์ได้หรือไม่

309
00:15:10,170 --> 00:15:13,212
เราอ้างว่ามันเป็นบันทึกของ n และ
แม้ว่าที่ไม่คุ้นเคยหรือมันจะเป็น

310
00:15:13,212 --> 00:15:15,170
หมอกเล็ก ๆ น้อย ๆ สิ่งที่
ลอการิทึมหรือสัญลักษณ์เป็น

311
00:15:15,170 --> 00:15:17,650
เพียงจำบันทึก n ที่
โดยทั่วไปหมายถึงกระบวนการที่

312
00:15:17,650 --> 00:15:20,790
ในกรณีนี้การแบ่ง
บางสิ่งบางอย่างในช่วงครึ่งปีอีกครั้งและอีกครั้ง

313
00:15:20,790 --> 00:15:25,790
และอีกครั้งและอีกครั้งดังกล่าวว่า
ได้รับขนาดเล็กเพิ่มมากขึ้นในขณะที่คุณทำเช่นนั้น

314
00:15:25,790 --> 00:15:28,470
>> เพื่อให้เข้าสู่ระบบของ n หมายถึงแน่ใจว่า
กับตัวอย่างสมุดโทรศัพท์

315
00:15:28,470 --> 00:15:32,662
เพื่อค้นหา binary ในทางทฤษฎีเมื่อเรา
มีประตูเสมือนบนกระดาน

316
00:15:32,662 --> 00:15:34,370
หรือเมื่อฌอนเป็น
ค้นหาสิ่งที่

317
00:15:34,370 --> 00:15:37,374
ถ้าเขาใช้ค้นหา binary, log n
จะเป็นขอบเขตบนเท่าใด

318
00:15:37,374 --> 00:15:38,040
เวลาที่ใช้เวลา

319
00:15:38,040 --> 00:15:44,027
แต่อัลกอริทึมที่วิ่งเข้าไปในห้อง
log N สันนิษฐานว่ารายละเอียดที่สำคัญ?

320
00:15:44,027 --> 00:15:45,360
ว่ารายการที่ถูกจัดเรียงใช่มั้ย?

321
00:15:45,360 --> 00:15:47,789
อัลกอริทึมของคุณเป็นสิ่งที่ผิดถ้า
การป้อนข้อมูลของคุณไม่ได้เรียงลำดับ

322
00:15:47,789 --> 00:15:49,830
และยังคุณกำลังใช้
สิ่งที่ต้องการค้นหา binary

323
00:15:49,830 --> 00:15:51,704
เพราะคุณอาจจะกระโดด
ที่เหมาะสมกว่าองค์ประกอบ

324
00:15:51,704 --> 00:15:53,600
โดยไม่ทราบว่ามันมีจริง

325
00:15:53,600 --> 00:15:55,600
>> ตอนนี้สิ่งที่นี้อาจหมายถึงโอใหญ่ของหนึ่ง?

326
00:15:55,600 --> 00:15:59,117
นี้ไม่ได้หมายความว่าอัลกอริทึมของคุณ
ใช้เวลาหนึ่งและมีเพียงขั้นตอนเดียว

327
00:15:59,117 --> 00:16:01,200
มันก็หมายความว่ามันจะใช้เวลา
จำนวนคงที่ของขั้นตอน

328
00:16:01,200 --> 00:16:04,060
อาจจะเป็นที่ 1 อาจจะเป็น
10 อาจจะถึง 1,000

329
00:16:04,060 --> 00:16:07,750
แต่มันก็เป็นอิสระจาก
ขนาดของปัญหา

330
00:16:07,750 --> 00:16:10,850
ไม่ว่าใหญ่ n คือ
อัลกอริทึมเวลาคงที่

331
00:16:10,850 --> 00:16:12,747
มักจะใช้หมายเลขเดียวกันของขั้นตอน

332
00:16:12,747 --> 00:16:15,080
ดังนั้นสิ่งที่อาจจะมีอัลกอริทึม
เราได้พูดคุยเกี่ยวกับหรือเพียงแค่

333
00:16:15,080 --> 00:16:20,418
สังหรณ์ใจที่มาพร้อมกับคุณว่า
มักจะทำงานในที่เรียกว่าเวลาคงที่?

334
00:16:20,418 --> 00:16:20,918
ใช่?

335
00:16:20,918 --> 00:16:22,001
>> ผู้ชม: เพ​​ิ่มตัวเลขสอง

336
00:16:22,001 --> 00:16:25,320
ลำโพง: เพิ่มสองตัวเลข
2 บวก 2 เท่ากับ 4 ทำ

337
00:16:25,320 --> 00:16:27,227
เพื่อที่จะทำงานอะไร?

338
00:16:27,227 --> 00:16:28,560
วิธีการเกี่ยวกับโลกแห่งความจริงมากขึ้นใช่?

339
00:16:28,560 --> 00:16:30,686
>> ผู้ชม: หา
สิ่งแรกที่อยู่ในรายชื่อ

340
00:16:30,686 --> 00:16:32,810
ลำโพง: หาครั้งแรก
องค์ประกอบในรายการนั่นเอง

341
00:16:32,810 --> 00:16:34,540
เราได้รับการพูดจริง
เกี่ยวกับอาร์เรย์แล้ว

342
00:16:34,540 --> 00:16:36,540
คุณจะได้รับที่
องค์ประกอบแรกในอาร์เรย์

343
00:16:36,540 --> 00:16:40,465
ไม่ว่านาน
อาร์เรย์ที่อยู่ในรหัส C?

344
00:16:40,465 --> 00:16:43,090
คุณเพียงแค่ใช้เช่นวงเล็บ
ศูนย์สัญกรณ์, แบม, คุณอยู่ที่นั่น

345
00:16:43,090 --> 00:16:46,120
และแน่นอนอาร์เรย์เช่นกัน
สิ่งที่สนับสนุนรู้จักกันโดยทั่วไป

346
00:16:46,120 --> 00:16:49,240
การเข้าถึงแบบสุ่มเข้าถึงโดยสุ่ม
หน่วยความจำเพราะคุณสามารถอย่างแท้จริง

347
00:16:49,240 --> 00:16:50,284
ข้ามไปที่ใดสถานที่หนึ่ง

348
00:16:50,284 --> 00:16:52,700
เราสามารถทำเช่นนี้ได้มากยิ่งขึ้นเพียงแค่
เราสามารถย้อนกลับไปเมื่อสัปดาห์ที่ศูนย์

349
00:16:52,700 --> 00:16:53,900
เมื่อเราได้ Scratch

350
00:16:53,900 --> 00:16:59,707
เวลาเท่าไหร่มันใช้เวลาสำหรับ
กล่าวว่าในบล็อก Scratch ที่จะดำเนินการ?

351
00:16:59,707 --> 00:17:00,790
เวลาคงที่เพียงแค่ใช่มั้ย?

352
00:17:00,790 --> 00:17:03,960
กล่าวว่าสิ่งที่พูด
บางสิ่งบางอย่างมันไม่สำคัญ

353
00:17:03,960 --> 00:17:07,359
ว่าโลกรอยขีดข่วนขนาดใหญ่ก็มักจะ
จะใช้จำนวนเงินเดียวกันของเวลา

354
00:17:07,359 --> 00:17:08,490
เพียงแค่พูดอะไรบางอย่าง

355
00:17:08,490 --> 00:17:11,089
>> เพื่อให้ถึงเวลาที่คงที่
แต่เป็นด้านพลิกอะไร

356
00:17:11,089 --> 00:17:13,030
ถ้าเป็นบน
ขอบเขตสิ่งที่ถ้าเราต้องการ

357
00:17:13,030 --> 00:17:17,089
เพื่ออธิบายขอบเขตที่ต่ำกว่า
อัลกอริทึมของเราทำงานเวลา?

358
00:17:17,089 --> 00:17:19,852
เกือบกรณีที่ดีที่สุด
อาจถ้าคุณจะ

359
00:17:19,852 --> 00:17:23,060
แต่คำเหล่านี้สามารถนำไปใช้ที่ดีที่สุด
กรณีที่เลวร้ายที่สุดกรณีกรณีเฉลี่ยมากกว่า

360
00:17:23,060 --> 00:17:26,359
ทั่วไป แต่ขอเพียงมุ่งเน้น
ในขอบเขตที่ลดลงมากกว่าปกติ

361
00:17:26,359 --> 00:17:31,920
คือสิ่งที่อัลกอริทึมที่มี
ขีด จำกัด ล่างของขั้นตอนที่ n,

362
00:17:31,920 --> 00:17:33,350
หรือขั้นตอน 2n หรือขั้นตอน 3n?

363
00:17:33,350 --> 00:17:36,241
ปัจจัยบางขั้นตอน n,
นั่นคือขอบเขตที่ต่ำของ

364
00:17:36,241 --> 00:17:36,740
ใช่?

365
00:17:36,740 --> 00:17:37,910
>> ผู้ชม: จัดเรียงฟอง?

366
00:17:37,910 --> 00:17:41,610
>> ลำโพง: จัดเรียงฟองใช้เวลา
ขั้นตอนน้อยที่สุด n, ทำไม?

367
00:17:41,610 --> 00:17:42,279
ทำไมจึงเป็นเช่นนั้น

368
00:17:42,279 --> 00:17:45,320
เริ่มต้นที่ควรทำไมมาให้คุณ
สังหรณ์ใจแม้ว่าจะไม่ได้เพียงแค่

369
00:17:45,320 --> 00:17:46,530
หรือยัง?

370
00:17:46,530 --> 00:17:47,030
ใช่?

371
00:17:47,030 --> 00:17:47,990
>> ผู้ชม: [ไม่ได้ยิน]

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
ลำโพง: แน่นอน

374
00:17:52,360 --> 00:17:55,810
ในสถานการณ์ที่ดีที่สุดของ
การจัดเรียงฟองและมากของขั้นตอนวิธีการ

375
00:17:55,810 --> 00:17:58,769
ถ้าผมมือคุณแปดคน
ที่จะจัดเรียงแล้ว

376
00:17:58,769 --> 00:18:00,560
มันจะโง่
สำหรับคุณขั้นตอนวิธี

377
00:18:00,560 --> 00:18:02,202
ที่จะกลับไปมา
มากกว่าหนึ่งครั้งใช่มั้ย?

378
00:18:02,202 --> 00:18:04,285
เพราะทันทีที่คุณ
เดินผ่านรายการครั้งเดียว

379
00:18:04,285 --> 00:18:08,090
คุณควรตระหนักถึงโอ้ฉันทำไม่มี
แลกเปลี่ยนรายการนี​​้จะถูกจัดเรียงออก

380
00:18:08,090 --> 00:18:09,700
แต่ที่จะพาคุณ n ขั้นตอน

381
00:18:09,700 --> 00:18:12,033
>> และตรงกันข้ามสิ่งที่เป็นอีก
วิธีคิดเกี่ยวกับมันได้หรือไม่

382
00:18:12,033 --> 00:18:15,240
การจัดเรียงฟองเป็นโอเมก้า,
ดังนั้นการพูดของ n,

383
00:18:15,240 --> 00:18:19,050
เพราะถ้าคุณมองไปที่
น้อยกว่า n องค์ประกอบสิ่งที่

384
00:18:19,050 --> 00:18:23,009
เป็นปัญหาพื้นฐานที่มี?

385
00:18:23,009 --> 00:18:24,550
คุณไม่ทราบว่าถ้ามันแยกขวา

386
00:18:24,550 --> 00:18:26,800
เรามนุษย์อาจได้อย่างรวดเร็วที่แปด
ผู้คนและเป็นเช่นโอ้ก็เรียงลำดับ

387
00:18:26,800 --> 00:18:28,430
ที่ไม่ได้พาฉัน n ขั้นตอน แต่มันก็

388
00:18:28,430 --> 00:18:30,810
ดวงตาของคุณแม้ว่าคุณชนิด
ของมีสนามขนาดใหญ่ของวิสัยทัศน์

389
00:18:30,810 --> 00:18:33,184
คุณมองไปที่แปดองค์ประกอบ
คุณมองไปที่แปดคน

390
00:18:33,184 --> 00:18:34,610
ที่แปดขั้นตอนได้อย่างมีประสิทธิภาพ

391
00:18:34,610 --> 00:18:38,612
และถ้าผมเดินผ่านทั้ง
รายการฉันรู้ใช่เรียงลำดับ

392
00:18:38,612 --> 00:18:41,320
ถ้าผมหยุดครึ่งทางความคิดทั้งหมด
ขวาก็ถูกจัดเรียงสวยเพื่อให้ห่างไกล

393
00:18:41,320 --> 00:18:42,520
สิ่งที่ราคาก็ไม่ได้ถูกจัดเรียงมีอะไรบ้าง

394
00:18:42,520 --> 00:18:44,186
ขั้นตอนวิธีที่จะไม่ถูกต้อง

395
00:18:44,186 --> 00:18:46,250
อาจจะเร็วขึ้น แต่ไม่ถูกต้อง

396
00:18:46,250 --> 00:18:48,500
>> ดังนั้นตอนนี้เรามีวิธีการ
อธิบายขอบเขตที่ต่ำกว่า

397
00:18:48,500 --> 00:18:49,710
และสิ่งที่เกี่ยวกับเวลาคงที่?

398
00:18:49,710 --> 00:18:54,565
คือสิ่งที่อัลกอริทึมที่มีลดลง
ผูกพันกับเวลาทำงานของหนึ่ง?

399
00:18:54,565 --> 00:18:58,350
1 ขั้นตอนที่ 2 ขั้นตอน 10 ขั้นตอน แต่
คงที่เป็นอิสระจาก n,

400
00:18:58,350 --> 00:18:59,310
ขนาดของการป้อนข้อมูลหรือไม่

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
ใช่ในด้านหลัง

403
00:19:04,600 --> 00:19:05,309
>> ผู้ชม: Printf?

404
00:19:05,309 --> 00:19:06,183
ลำโพง: มีอะไรที่?

405
00:19:06,183 --> 00:19:07,184
ผู้ชม: Printf?

406
00:19:07,184 --> 00:19:07,850
ลำโพง: Printf

407
00:19:07,850 --> 00:19:08,400
ตกลงนั่นเอง

408
00:19:08,400 --> 00:19:10,720
ดังนั้นก็จะใช้เวลาเป็นจำนวนคงที่ของขั้นตอน

409
00:19:10,720 --> 00:19:13,170
และฉันควร now-- ตอนนี้ที่
เรากำลังพูดถึงรหัส C

410
00:19:13,170 --> 00:19:16,040
และไม่ Scratch บางสิ่งบางอย่าง
เหมือนพูดกับ printf,

411
00:19:16,040 --> 00:19:17,710
เราควรจะเริ่มต้นที่จะได้รับอย่างรอบคอบ

412
00:19:17,710 --> 00:19:21,090
เพราะ printf จะใช้เวลา
ใส่มันเป็นสตริง

413
00:19:21,090 --> 00:19:23,220
และสตริงในทางเทคนิคจะมีความยาว

414
00:19:23,220 --> 00:19:25,530
ดังนั้นถ้าตอนนี้เราต้องการที่จะเลือก
กับคุณถ้าคุณไม่ทราบ

415
00:19:25,530 --> 00:19:29,430
ในทางเทคนิคเราสามารถยืนยัน printf ที่
จะใช้ระยะเวลาในการป้อนข้อมูลตัวแปร

416
00:19:29,430 --> 00:19:32,270
และแน่นอนมันอาจจะใช้เวลามากขึ้น
เวลาในการพิมพ์สายนี้ยาว

417
00:19:32,270 --> 00:19:33,560
ยาวกว่านี้

418
00:19:33,560 --> 00:19:36,570
>> ดังนั้นสิ่งที่ถ้าเราพิจารณาเพียง
การเรียงลำดับและการค้นหาตัวอย่าง?

419
00:19:36,570 --> 00:19:40,450
สิ่งที่เกี่ยวกับไมค์สมิ ธ ในโทรศัพท์
หนังสือหรือค้นหา binary มากกว่าปกติ?

420
00:19:40,450 --> 00:19:42,220
ในกรณีที่ดีที่สุดสิ่งที่อาจเกิดขึ้นได้อย่างไร

421
00:19:42,220 --> 00:19:45,577
ฉันเปิดสมุดโทรศัพท์และแบม
มีจำนวนไมค์สมิ ธ เป็น

422
00:19:45,577 --> 00:19:46,660
ฉันจะโทรไปหาเขาทันที

423
00:19:46,660 --> 00:19:49,390
>> เอาหนึ่งขั้นตอนที่อาจจะสองขั้นตอน
แต่จำนวนคงที่ของขั้นตอน

424
00:19:49,390 --> 00:19:50,230
ถ้าฉันได้รับโชคดี

425
00:19:50,230 --> 00:19:52,570
และตรงไปตรงมาเราเห็นใน
จันทร์เพื่อนร่วมชั้นของคุณ

426
00:19:52,570 --> 00:19:54,710
ได้รับโชคดีมากเป็นครั้งที่สองในแถว

427
00:19:54,710 --> 00:19:57,050
และที่เป็นจริงอย่างต่อเนื่อง
เวลาอยู่ในขอบเขตที่ต่ำกว่า

428
00:19:57,050 --> 00:20:01,280
อัลกอริทึมในคำถามสำหรับการค้นหา
จำนวน 50 หลังที่ปิด

429
00:20:01,280 --> 00:20:01,830
ประตู

430
00:20:01,830 --> 00:20:06,400
>> ตอนนี้เป็นกันถ้าคุณพบ
ว่าทั้งสอง O ใหญ่บนปก

431
00:20:06,400 --> 00:20:09,310
และโอเมก้า, ที่ถูกผูกไว้ที่ต่ำกว่า
เป็นหนึ่งในเดียวกันว่า

432
00:20:09,310 --> 00:20:11,830
เป็นสูตรเดียวกันใน
วงเล็บคุณยังสามารถ

433
00:20:11,830 --> 00:20:15,170
พูดเพียงว่าเป็นแฟนซี
บางสิ่งบางอย่างที่อยู่ในที

434
00:20:15,170 --> 00:20:18,270
ของ n หรือ theta ของบางค่าอื่น

435
00:20:18,270 --> 00:20:20,661
ที่เพียงแค่หมายความว่าเมื่อขนาดใหญ่
O และโอเมก้าเหมือนกัน

436
00:20:20,661 --> 00:20:21,910
ตอนนี้สิ่งที่เกี่ยวกับการจัดเรียงตัวเลือก?

437
00:20:21,910 --> 00:20:23,400
ลองใช้คำศัพท์ใหม่นี้

438
00:20:23,400 --> 00:20:27,407
ในการเรียงลำดับตัวเลือกสิ่งที่เป็นเรา
ทำอีกครั้งและอีกครั้งและอีกครั้งหรือไม่

439
00:20:27,407 --> 00:20:29,990
ผมก็จะกลับมาผ่าน
รายการที่กำลังมองหาใคร?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
จำนวนน้อยที่สุด

442
00:20:34,730 --> 00:20:37,560
>> ดังนั้นวิธีการหลายขั้นตอนวิธี
การเปรียบเทียบจำนวนมากไม่ฉัน

443
00:20:37,560 --> 00:20:43,250
จะต้องทำเพื่อที่จะคิดออกที่
องค์ประกอบที่เล็กที่สุดในรายการคืออะไร

444
00:20:43,250 --> 00:20:44,437
n ลบ 1 ใช่มั้ย?

445
00:20:44,437 --> 00:20:47,770
เพราะถ้าฉันเพียงแค่เริ่มต้นด้วยหนึ่งฉัน
ที่กำหนดและฉันเริ่มเปรียบเทียบเขาหรือเธอ

446
00:20:47,770 --> 00:20:49,519
จากนั้นเขาหรือเธอให้เขา
หรือเธอเขาหรือเธอฉัน

447
00:20:49,519 --> 00:20:52,010
สามารถจับคู่องค์ประกอบ
ร่วมกัน n ลบ 1 คูณ

448
00:20:52,010 --> 00:20:55,630
ดังนั้นตัวเลือกการจัดเรียงกันจะใช้เวลา
n ลบ 1 ขั้นตอนที่เป็นครั้งแรกที่

449
00:20:55,630 --> 00:20:59,540
>> มันไม่กี่ขั้นตอนพาฉันไปที่
พบว่าองค์ประกอบที่สองมีขนาดเล็กที่สุดหรือไม่

450
00:20:59,540 --> 00:21:02,920
n ลบ 2 เพราะฉันเป็นใบ้
ถ้าฉันให้มองไปที่คนคนเดียวกัน

451
00:21:02,920 --> 00:21:06,280
อีกครั้งถ้าผมได้เลือกเขาแล้ว
หรือเธอและนำพวกเขาในสถานที่ของพวกเขา

452
00:21:06,280 --> 00:21:09,270
และขั้นตอนที่สาม n
ลบ 3 แล้ว n ลบ 4

453
00:21:09,270 --> 00:21:11,020
เราได้เห็นรูปแบบนี้
ก่อนและแน่นอน

454
00:21:11,020 --> 00:21:13,460
ตัวเลือกการจัดเรียงกัน
มีขีด จำกัด บน

455
00:21:13,460 --> 00:21:16,210
ของ n กำลังสองถ้าเราทำขึ้นบวกว่า

456
00:21:16,210 --> 00:21:19,790
ขีด จำกัด ล่างเรียงลำดับการเลือกคืออะไร

457
00:21:19,790 --> 00:21:25,350
น้อยที่สุดเท่าไหร่ต้องเลือกเวลา
การจัดเรียงเวลาที่เรากำหนดไว้ว่าในวันจันทร์ที่?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
เสนอตัวเลือกที่สอง

460
00:21:30,490 --> 00:21:32,360
อาจจะเป็น n เป็นมาก่อน

461
00:21:32,360 --> 00:21:35,040
บางทีมันอาจจะเป็น n กำลังสองมัน
คือตอนนี้เป็นขีด จำกัด บน

462
00:21:35,040 --> 00:21:35,874
>> ผู้ชม: n กำลังสอง

463
00:21:35,874 --> 00:21:36,664
ลำโพง: n กำลังสอง

464
00:21:36,664 --> 00:21:37,368
ทำไม?

465
00:21:37,368 --> 00:21:40,060
>> ผู้ชม: เพ​​ราะคุณมี
เพื่อกำหนด [ไม่ได้ยิน]

466
00:21:40,060 --> 00:21:41,510
>> ลำโพง: แน่นอน

467
00:21:41,510 --> 00:21:45,077
อย่างน้อยที่สุดเท่าที่จะกำหนดตัวเลือกการจัดเรียง
มันก็ไร้เดียงสาสวยเก็บไป

468
00:21:45,077 --> 00:21:46,160
พบว่าองค์ประกอบที่เล็กที่สุด

469
00:21:46,160 --> 00:21:47,770
ไปอีกครั้งพบว่าองค์ประกอบที่เล็กที่สุด

470
00:21:47,770 --> 00:21:49,490
ไปอีกครั้งพบว่าองค์ประกอบที่เล็กที่สุด

471
00:21:49,490 --> 00:21:51,700
มีการเรียงลำดับของไม่ได้
การเพิ่มประสิทธิภาพในการมีที่

472
00:21:51,700 --> 00:21:54,350
อาจจะให้ฉันยกเลิกหลังจากที่
เพียง n หรือเพื่อให้ขั้นตอน

473
00:21:54,350 --> 00:21:57,080
ดังนั้นแน่นอนการเลือก
เรียงลำดับของโอเมก้า n กำลังสอง

474
00:21:57,080 --> 00:22:00,667
>> สิ่งที่เกี่ยวกับการจัดเรียงแทรกที่ผมเอา
ที่ผมได้รับแล้วผม plopped เขา

475
00:22:00,667 --> 00:22:01,750
หรือเธออยู่ในสถานที่ที่เหมาะสมหรือไม่

476
00:22:01,750 --> 00:22:04,958
จากนั้นผมก็เดินไปที่คนที่สอง
plopped เขาหรือเธอในสถานที่ที่เหมาะสม

477
00:22:04,958 --> 00:22:07,910
แล้วคนต่อไป plopped
เขาหรือเธอในสถานที่ที่เหมาะสม

478
00:22:07,910 --> 00:22:10,537
ขอให้สังเกตว่านี้เป็นอย่างมาก
เชิงเส้นจึงจะพูด

479
00:22:10,537 --> 00:22:12,620
ผมเป็นเส้นตรงผม
จะไม่กลับมา

480
00:22:12,620 --> 00:22:16,080
ผมไม่เคยมองย้อนกลับไปจริงๆ แต่
สิ่งที่เกิดขึ้นเมื่อฉันใส่เขา

481
00:22:16,080 --> 00:22:20,302
หรือเธอเป็นจุดเริ่มต้นของ
รายการที่เราได้ในวันจันทร์ที่?

482
00:22:20,302 --> 00:22:21,010
สิ่งที่เกิดขึ้น?

483
00:22:21,010 --> 00:22:21,510
ใช่?

484
00:22:21,510 --> 00:22:23,122
ผู้ชม: [ไม่ได้ยิน]

485
00:22:23,122 --> 00:22:24,830
ลำโพง: ใ​​ช่ว่า
ก็จับได้ใช่มั้ย?

486
00:22:24,830 --> 00:22:26,746
คุณอาจจำจาก
เพื่อนร่วมชั้นของคุณหากพวกเขา

487
00:22:26,746 --> 00:22:29,670
ได้ทำให้การเคลื่อนไหวใด ๆ
เท้าของพวกเขาที่ได้รับการดำเนินการ

488
00:22:29,670 --> 00:22:33,610
ดังนั้นถ้ามีอยู่สามคนที่นี่และ
คนใหม่เป็นวิธีการที่นั่น

489
00:22:33,610 --> 00:22:37,360
บนเวทีนานเช่นนี้นั่นเองเขา
หรือเธอก็สามารถไปให้มาก

490
00:22:37,360 --> 00:22:40,074
แต่ถ้าเรากำลังคิดเกี่ยวกับ
คอมพิวเตอร์และอาเรย์ของหน่วยความจำ,

491
00:22:40,074 --> 00:22:41,990
คนเหล่านี้จะไป
ที่จะมีการสับเปลี่ยนกว่า

492
00:22:41,990 --> 00:22:43,260
ที่จะทำให้ห้องพักสำหรับคนที่

493
00:22:43,260 --> 00:22:46,930
และเพื่อให้ n ลบ 1 shufflings,
n ลบ 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
ลบ 3 shufflings เป็นเพียงชนิดของ
สิ่งที่เกิดขึ้นข้างหลังผมไม่ได้อยู่ในด้านหน้าของฉัน

495
00:22:50,660 --> 00:22:52,710
เหมือนก่อนหน้านี้ในความรู้สึกบาง

499
00:22:52,557 --> 00:22:54,640
ตอนนี้เป็นกันและเป็น
คุณอาจได้เห็นออนไลน์

500
00:22:54,640 --> 00:22:57,699
หากคุณเริ่มต้น poking รอบเกี่ยวกับ
ทุกประเภทมีคนที่แตกต่างกันมากมาย

501
00:22:57,699 --> 00:22:59,490
ออกมีบางส่วนของพวกเขา
ดีกว่าคนอื่น

502
00:22:59,490 --> 00:23:02,200
อันที่จริง bogosort เป็นหนึ่ง
นั่นคือความสนุกสนานของการที่จะมองขึ้น

503
00:23:02,200 --> 00:23:06,650
Bogosort ใช้ชุดของ
ตัวเลขหรือพูดสำรับไพ่,

504
00:23:06,650 --> 00:23:09,870
สุ่ม shuffles พวกเขาและ
ตรวจสอบว่าพวกเขากำลังถูกจัดเรียง

505
00:23:09,870 --> 00:23:12,130
และถ้าคุณไม่ได้ทำมันอีกครั้ง

506
00:23:12,130 --> 00:23:14,140
และถ้าคุณไม่ได้ทำมันอีกครั้ง

507
00:23:14,140 --> 00:23:15,440
ถ้าไม่ทำมันอีกครั้ง

508
00:23:15,440 --> 00:23:17,060
โง่อย่างไม่น่าเชื่อ

509
00:23:17,060 --> 00:23:19,520
>> และแน่นอนถ้าคุณอ่าน
เช่นบทความวิกิพีเดีย

510
00:23:19,520 --> 00:23:21,200
ชื่อเล่นคือโง่จัดเรียง

511
00:23:21,200 --> 00:23:25,180
ในที่สุดมันก็จะทำงาน
หวังว่าให้เวลาพอ

512
00:23:25,180 --> 00:23:28,240
แต่เวลาที่
อาจจะใช้เวลาค่อนข้างบางเวลา

513
00:23:28,240 --> 00:23:31,650
ดังนั้นถ้าผมจะให้สิ่งที่ความเร็ว
เพิ่มขึ้นจากตัวอย่างที่แมรี่เบ ธ ที่ก่อนหน้านี้

514
00:23:31,650 --> 00:23:35,150
โดยมีองค์ประกอบอื่น ๆ อีกไม่กี่
แต่ทั้งสองหน่วยประมวลผลมากขึ้น

515
00:23:35,150 --> 00:23:37,100
คนสองคนที่ถ้าคุณ
จะไม่คิดร่วมงานกับผม

516
00:23:37,100 --> 00:23:40,972
วิธีการเกี่ยวกับ 1 กว่าที่นี่และ
ขอ go-- หนึ่งไปที่นั่นหรือไม่

517
00:23:40,972 --> 00:23:41,722
ไม่มีใครที่นั่น?

518
00:23:41,722 --> 00:23:42,221
ตกลง

519
00:23:42,221 --> 00:23:44,190
คุณมีสีดำ
เสื้อใช่มาลง

520
00:23:44,190 --> 00:23:45,000
ขวาทุกสิ่งที่เป็นชื่อของคุณ?

521
00:23:45,000 --> 00:23:45,720
>> ผู้ชม: ปีเตอร์

522
00:23:45,720 --> 00:23:46,100
>> ลำโพง: มีอะไรที่?

523
00:23:46,100 --> 00:23:46,766
>> ผู้ชม: ปีเตอร์

524
00:23:46,766 --> 00:23:49,450
ลำโพง: ปีเตอร์เดวิดมีความสุขที่ได้พบคุณ

525
00:23:49,450 --> 00:23:53,670
สิทธิทั้งหมดที่เรามีปีเตอร์ที่นี่ถ้าคุณ
ต้องการที่จะเข้ามาสู่โต๊ะกว่าที่นี่

526
00:23:53,670 --> 00:23:54,550
และสิ่งที่ชื่อของคุณ?

527
00:23:54,550 --> 00:23:55,216
>> ผู้ชม: เอเลน่า

528
00:23:55,216 --> 00:23:55,970
ลำโพง: เอเลน่า

529
00:23:55,970 --> 00:23:57,030
ตกลงที่ดีที่จะได้พบคุณ

530
00:23:57,030 --> 00:23:58,060
Elena พบปีเตอร์

531
00:23:58,060 --> 00:23:59,170
ปีเตอร์เอเลน่า

532
00:23:59,170 --> 00:24:02,290
และเราจะต้องแอนดรู
ขึ้นที่นี่เช่นกันโปรด

533
00:24:02,290 --> 00:24:06,107
และความท้าทายของคุณเป็นไป
ที่จะมีการเรียงลำดับของการ์ด

534
00:24:06,107 --> 00:24:08,190
และหากไม่คุ้นเคยดาดฟ้า
ของบัตรควรในที่สุด

535
00:24:08,190 --> 00:24:11,064
จะแยกสิ่งเล็กน้อยเช่น
นี้ที่เราจะทำสโมสรแล้ว

536
00:24:11,064 --> 00:24:13,660
เสียแล้วหัวใจและ
เพชรจากเอซเป็นหนึ่ง

537
00:24:13,660 --> 00:24:15,570
ทั้งหมดทางขึ้นไปยังพระมหากษัตริย์

538
00:24:15,570 --> 00:24:20,890
>> บัตรฉันจะให้คุณ
จะไปเป็น 52 ในปริมาณที่

539
00:24:20,890 --> 00:24:23,160
เรากำลังจะไปกัน
ทุกครั้งที่คุณในเวลาเพียงสักครู่

540
00:24:23,160 --> 00:24:26,410
เรากำลังจะไปโยนแอนดรู
ขึ้นบนหน้าจอที่นี่

541
00:24:26,410 --> 00:24:28,170
เพื่อที่จะดูเป็นคุณทำเช่นนี้

542
00:24:28,170 --> 00:24:31,070
และอื่น ๆ ว่าทั้งหมดนี้
คือทั้งหมดที่มองเห็นได้มากขึ้น

543
00:24:31,070 --> 00:24:33,490
เหล่านี้เป็นบัตรที่ผมได้รับใน Amazon

544
00:24:33,490 --> 00:24:42,861
ดังนั้นพวกเขามีอยู่แล้วแบบสุ่ม
เรียงลำดับและเรากำลังจะไปทุกครั้งที่คุณ

545
00:24:42,861 --> 00:24:44,610
และเรากำลังจะไป
ให้มันจริงเวลานี้

546
00:24:44,610 --> 00:24:47,820
ดังนั้นเราจะพยายามที่จะกดดันคุณ
เพราะมิฉะนั้นจะได้รับน่าเบื่อ

547
00:24:47,820 --> 00:24:48,460
ได้อย่างรวดเร็ว

548
00:24:48,460 --> 00:24:53,860
หากคุณสามารถดำเนินการต่อไปที่จะจัดเรียง 52
องค์ประกอบเข้าด้วยกันผ่านวิธีการบางอย่างตอนนี้

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> และอีกครั้งในขณะที่เราดูเหล่านี้
คนทำในสิ่งที่ในท้ายที่สุด

551
00:25:07,180 --> 00:25:10,200
ที่เกิดขึ้นในการผลิตที่เห็นได้ชัด
ผลคิดเกี่ยวกับจริงๆ

552
00:25:10,200 --> 00:25:12,962
ว่าพวกเขากำลังแต่ละทำมัน
วิธีการที่คุณอาจจะบอกว่ามัน

553
00:25:12,962 --> 00:25:15,045
เพราะอีกครั้งเหล่านี้เป็น
ทุกกระบวนการขั้นตอนวิธี

554
00:25:15,045 --> 00:25:17,090
ที่เราจะได้รับความเป็นมนุษย์

555
00:25:17,090 --> 00:25:22,349
แต่คุณอาจจะมีความยาว
ปรีชานานก่อนที่คุณจะ

556
00:25:22,349 --> 00:25:24,390
คิดเกี่ยวกับการ
ชั้นเรียนวิทยาศาสตร์คอมพิวเตอร์คุณ

557
00:25:24,390 --> 00:25:27,223
อาจจะมีสัญชาตญาณที่มี
ซึ่งในการแก้ปัญหาเช่นนี้

558
00:25:27,223 --> 00:25:29,560
แต่เมื่อคุณได้รับรู้
รูปแบบและเริ่มต้น

559
00:25:29,560 --> 00:25:32,407
ให้เป็นระเบียบแบบแผนขั้นตอนที่
คุณกำลังแก้ปัญหาเหล​​่านี้

560
00:25:32,407 --> 00:25:35,490
คุณจะพบว่าคุณสามารถแก้มาก
ที่น่าสนใจมากขึ้นและซับซ้อนมากขึ้น

561
00:25:35,490 --> 00:25:39,190
ปัญหาได้อย่างรวดเร็ว

562
00:25:39,190 --> 00:25:42,351
ดังนั้นใครบางคนจากผู้ชมสิ่งที่เป็น
อย่างน้อยหนึ่งองค์ประกอบของอัลกอริทึม

563
00:25:42,351 --> 00:25:43,350
ที่พวกเขากำลังใช้ที่นี่?

564
00:25:43,350 --> 00:25:44,275
>> ผู้ชม: [ไม่ได้ยิน]

565
00:25:44,275 --> 00:25:45,150
ลำโพง: มีอะไรที่?

566
00:25:45,150 --> 00:25:47,062
ผู้ชม: โดยชุด

567
00:25:47,062 --> 00:25:47,770
ลำโพง: โดยชุด

568
00:25:47,770 --> 00:25:50,630
ดังนั้นครั้งแรกที่พวกเขาจะถูกจัดกลุ่ม
ทั้งหมดของเพชรด้วยกัน

569
00:25:50,630 --> 00:25:52,560
ดูเหมือนว่าทั้งหมดของ
หัวใจด้วยกันดูเหมือนว่า

570
00:25:52,560 --> 00:25:56,520
และอื่น ๆ โดยไม่ต้องเคารพ
สำหรับตัวเลขบนบัตร

571
00:25:56,520 --> 00:26:00,900
และตอนนี้พวกเขาจะปรากฏตัวอย่างเช่น
ที่จะให้พวกเขาโดยการเรียงลำดับจำนวน

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
ที่ดีมาก

574
00:26:08,910 --> 00:26:12,370
>> ขวาทั้งหมดดังนั้นสิ่งที่จะ
เป็นขั้นตอนสุดท้ายแล้วที่นี่?

575
00:26:12,370 --> 00:26:16,950
เมื่อเรามีสี่ชุดที่เรียงลำดับสิ่งที่
เราจะต้องทำเพื่อสี่กอง

576
00:26:16,950 --> 00:26:20,059
เพื่อให้บรรลุหนึ่ง
แยกดาดฟ้าค่อนข้างง่าย?

577
00:26:20,059 --> 00:26:21,350
ดังนั้นเราจึงจำเป็นที่จะรวมพวกเขาอีกครั้ง

578
00:26:21,350 --> 00:26:25,160
>> จึงมีความคิดที่น่าสนใจที่
อีกครั้ง daresay คือใช้งานง่ายมากแม้

579
00:26:25,160 --> 00:26:28,140
ถ้าคุณอาจไม่เคยตบ
ชนิดของฉลากบนมัน

580
00:26:28,140 --> 00:26:31,900
นี้ความคิดพื้นฐานของการหาร
ปัญหาไม่ได้อยู่ในครึ่งเวลานี้

581
00:26:31,900 --> 00:26:33,410
แต่อย่างน้อยเป็นสี่ชิ้น

582
00:26:33,410 --> 00:26:36,810
แก้สวยมาก
ปัญหาพื้นฐานเหมือนกัน

583
00:26:36,810 --> 00:26:40,480
ในการแยกจากกัน
แล้วรวมผล

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
และที่ยอดเยี่ยมทำ

586
00:26:50,140 --> 00:26:52,140
สิทธิทั้งหมดรอบใหญ่
เสียงปรบมือถ้าเราสามารถทำได้

587
00:26:52,140 --> 00:26:56,480
>> [APPLAUSE]

588
00:26:56,480 --> 00:26:59,740
>> ลำโพง: ฉันมีความคิดสิ่งที่คุณจะ
ทำอย่างไรกับเหล่านี้ แต่ที่นี่คุณไป

589
00:26:59,740 --> 00:27:01,690
ขอบคุณมาก

590
00:27:01,690 --> 00:27:04,660
ดังนั้นเรามาดูสองนาที
และแปดวินาที

591
00:27:04,660 --> 00:27:07,490
ถ้าคุณต้องการที่จะท้าทายเพื่อนของคุณ

592
00:27:07,490 --> 00:27:12,160
แล้วอะไรเป็นไปได้
จะนำมาใช้จากนี้

593
00:27:12,160 --> 00:27:13,830
ที่เราสามารถใช้ประโยชน์ได้มากขึ้นโดยทั่วไป?

594
00:27:13,830 --> 00:27:16,080
ดีคิดว่ากลับไป
อาร์เรย์นี้ของตัวเลข

595
00:27:16,080 --> 00:27:19,060
และคิดว่าตอนนี้กลับไปบางส่วนของ
pseudocode เราได้เขียนในอดีตที่ผ่านมา

596
00:27:19,060 --> 00:27:22,080
และนี่คือ pseudocode สำหรับ
การแก้ปัญหาสมุดโทรศัพท์

597
00:27:22,080 --> 00:27:25,150
โดยใน pseudocode ฉัน
แจกแจงวิธีการระเบียบมากขึ้น

598
00:27:25,150 --> 00:27:28,400
ในการอธิบายวิธีการที่ฉันได้ง่ายมาก
อัลกอริทึมของมนุษย์แบ่งโทรศัพท์

599
00:27:28,400 --> 00:27:31,650
หนังสือเล่มนี้ในครึ่งซ้ำทำซ้ำทำซ้ำ
จนกว่าฉันจะหาใครสักคนเหมือนไมค์สมิ ธ

600
00:27:31,650 --> 00:27:33,790
ถ้าเขาเป็นจริงในสมุดโทรศัพท์

601
00:27:33,790 --> 00:27:37,610
>> แต่ฉันชนิดของใช้สิ่งที่ฉันจะเรียก
วิธีการซ้ำแล้วซ้ำอีกมากที่นี่

602
00:27:37,610 --> 00:27:42,160
ในบรรทัดที่แจ้งให้ทราบล่วงหน้าโดยเฉพาะอย่างยิ่ง 8 และสาย 11

603
00:27:42,160 --> 00:27:46,750
เหล่านี้คือหลักฐานของซ้ำ
วิธีการวิธีการวนลูป,

604
00:27:46,750 --> 00:27:49,040
เพราะที่ว่า
พฤติกรรมของพวกเขาก่อให้เกิด

605
00:27:49,040 --> 00:27:52,910
เส้นที่ทั้งสองพูดไป
ชนิดสายสามและคุณสามารถของ

606
00:27:52,910 --> 00:27:55,140
คิดว่าของที่อยู่ในของคุณ
ตาใจเป็นห่วง

607
00:27:55,140 --> 00:27:59,080
มันบอกให้คุณกลับไปถึงขั้นตอน
สามและทำซ้ำอีกครั้งและอีกครั้ง

608
00:27:59,080 --> 00:28:00,010
และอีกครั้ง

609
00:28:00,010 --> 00:28:04,410
>> แต่ถ้าเราใช้ประโยชน์จากความคิดที่สำคัญ
ที่นี่เราไม่ได้ครั้งสุดท้าย

610
00:28:04,410 --> 00:28:10,280
และลดความซับซ้อนและสาย 8
สาย 11 และเพื่อนบ้านของพวกเขา

611
00:28:10,280 --> 00:28:12,840
เป็นเพียงแค่นี้สีเหลือง

612
00:28:12,840 --> 00:28:16,480
มันไม่ได้เป็นพื้นฐานการตัดทอน
pseudocode มาก

613
00:28:16,480 --> 00:28:20,530
แต่มันเปลี่ยนแปลงพื้นฐาน
ธรรมชาติของอัลกอริทึมของฉัน

614
00:28:20,530 --> 00:28:24,220
ตอนนี้สิ่งที่ฉันพูด
ในขั้นตอนที่ 7 ในขั้นตอนที่ 10,

615
00:28:24,220 --> 00:28:29,140
คือการค้นหาสำหรับไมค์
ในลักษณะเดียวกับที่แน่นอน

616
00:28:29,140 --> 00:28:31,580
แต่ในทางด้านซ้าย
ครึ่งหนึ่งหรือครึ่งหนึ่งทางด้านขวา

617
00:28:31,580 --> 00:28:33,420
>> ดังนั้นในคำอื่น ๆ หาก
ผมเริ่มต้นจากขั้นตอนที่หนึ่ง

618
00:28:33,420 --> 00:28:36,150
รับสมุดโทรศัพท์เปิดไปตรงกลาง
สมุดโทรศัพท์ดูที่ชื่อ

619
00:28:36,150 --> 00:28:39,010
ถ้าสมิ ธ เป็นหนึ่งใน
ชื่อของโทรไมค์อื่น

620
00:28:39,010 --> 00:28:44,340
ถ้าสมิ ธ เป็นก่อนหน้านี้ในหนังสือที่ขั้นตอนที่เจ็ด
ค้นหาไมค์ในช่วงครึ่งปีที่เหลือของหนังสือเล่ม

621
00:28:44,340 --> 00:28:47,130
แต่ที่ชนิดของความรู้สึกเหมือน
มันทิ้งฉันแขวนอยู่ใช่มั้ย?

622
00:28:47,130 --> 00:28:49,240
สีเหลืองเป็น
การเรียนการสอน แต่วิธีการทำผม

623
00:28:49,240 --> 00:28:51,870
ค้นหาไมค์ซ้าย
ครึ่งหนึ่งของสมุดโทรศัพท์หรือไม่

624
00:28:51,870 --> 00:28:54,210
ฉันจะมีที่
อัลกอริทึมที่ฉัน

625
00:28:54,210 --> 00:28:57,100
สามารถค้นหาคนที่ชอบไมค์สมิ ธ ?

626
00:28:57,100 --> 00:28:58,980
ดีก็จ้องมองเราในหน้า

627
00:28:58,980 --> 00:29:03,090
แท้จริงฉันสามารถใช้เดียวกันแน่นอน
โปรแกรมได้อย่างมีประสิทธิภาพจะขึ้นไปด้านบน

628
00:29:03,090 --> 00:29:06,490
อีกครั้งและอีกครั้งที่ทำงาน
สายเดียวกันของรหัส

629
00:29:06,490 --> 00:29:10,610
>> ดังนั้นแม้ว่านี้จะรู้สึก
เช่นบิตของคำนิยามวงจร

630
00:29:10,610 --> 00:29:13,480
ที่คุณตอบคนเป็น
คำถามโดยเพียงแค่การเรียงลำดับของการถาม

631
00:29:13,480 --> 00:29:15,990
คำถามเดียวกันอีกครั้ง
เช่นทำไมทำไมทำไม?

632
00:29:15,990 --> 00:29:21,580
ความจริงก็คือเพราะเราเขียนยาก
คู่ของสายพิเศษขั้นตอนที่ 4

633
00:29:21,580 --> 00:29:25,320
ซึ่งเป็นกรณีที่และขั้นตอนที่ 12 ซึ่ง
มีประสิทธิภาพสาขาอื่น

634
00:29:25,320 --> 00:29:30,120
เพราะเรามีผู้ที่มาตรการชั่วคราว,
ขั้นตอนวิธีนี้จะยุติถ้าเรา

635
00:29:30,120 --> 00:29:32,050
หาไมค์หรือถ้าเราทำไม่ได้

636
00:29:32,050 --> 00:29:36,810
แต่ในขั้นตอนที่ 7 และ 10 ตอนนี้เรามี
สิ่งที่เราจะเรียกอัลกอริทึมแบบทั่วถึง

637
00:29:36,810 --> 00:29:40,420
และเรียกซ้ำตัวเองย่อมเป็นความคิดที่มีประสิทธิภาพ
นั่นเป็นความคิดเล็ก ๆ น้อย ๆ การดัดในตอนแรก

638
00:29:40,420 --> 00:29:42,500
ว่าตอนนี้เราสามารถใช้ดังต่อไปนี้

639
00:29:42,500 --> 00:29:46,600
>> รวมการจัดเรียงจะเรียงลำดับสุดท้ายที่
เรามองไปที่อย่างน้อยในชั้นเรียนอย่างเป็นทางการ

640
00:29:46,600 --> 00:29:50,040
และมันก็แตกต่างกันลึกซึ้ง
จากที่ผ่านมาสามและแน่นอน

641
00:29:50,040 --> 00:29:52,140
สี่ถ้าเรารวม bogosort

642
00:29:52,140 --> 00:29:54,810
ที่นี่ pseudocode สำหรับการจัดเรียงผสานเป็น

643
00:29:54,810 --> 00:30:00,170
เมื่อป้อนข้อมูลขององค์ประกอบ n ให้เพื่อให้
อาร์เรย์ของขนาด n ถ้า n น้อยกว่า 2,

644
00:30:00,170 --> 00:30:01,040
ผลตอบแทน

645
00:30:01,040 --> 00:30:03,610
ดังนั้นผมจึงมีเหตุผลที่ว่า
สติตรวจสอบก่อน?

646
00:30:03,610 --> 00:30:09,477
อะไรคือความหมายถ้าฉันมือคุณ
อาร์เรย์ที่มี n ระยะเวลาน้อยกว่า 2?

647
00:30:09,477 --> 00:30:11,060
มันถูกจัดเรียงอยู่แล้วเห็นได้ชัดว่าใช่มั้ย?

648
00:30:11,060 --> 00:30:13,640
เนื่องจากรายการทั้งสองมี
องค์ประกอบหนึ่งซึ่งเป็นนิด ๆ

649
00:30:13,640 --> 00:30:15,180
ห่างเพราะมันเป็น
สิ่งเดียวที่มี

650
00:30:15,180 --> 00:30:18,138
หรือมันเป็นเรื่องของขนาดเป็นศูนย์ซึ่งหมายถึง
ไม่มีอะไรที่จะเรียงลำดับได้ดังนั้นโดยธรรมชาติ

651
00:30:18,138 --> 00:30:18,720
มันจะถูกจัดเรียง

652
00:30:18,720 --> 00:30:20,410
มีอะไรผิดปกติเพียงแค่มี

653
00:30:20,410 --> 00:30:22,310
เพื่อให้เป็นกรณีฐานของเราที่เรียกว่า

654
00:30:22,310 --> 00:30:24,440
>> ที่คล้ายในจิตวิญญาณ
กับสิ่งที่เราทำกับไมค์

655
00:30:24,440 --> 00:30:26,023
ถ้าไมค์ในสมุดโทรศัพท์ที่โทรไปหาเขา

656
00:30:26,023 --> 00:30:27,740
ถ้าเขาไม่ได้มีให้ขึ้น

657
00:30:27,740 --> 00:30:31,240
เป็นกรณีฐานที่เรียกว่าเพื่อให้แน่ใจว่า
อัลกอริทึมในตอนท้ายของวันที่

658
00:30:31,240 --> 00:30:33,540
จะหยุดในบางสถานการณ์

659
00:30:33,540 --> 00:30:37,890
>> แต่นี่เป็นก้าวกระโดดของความเชื่อในขณะนี้อื่น
ค้นหาครึ่งซ้ายขององค์ประกอบ

660
00:30:37,890 --> 00:30:39,740
แล้วเรียงขวา
ครึ่งหนึ่งขององค์ประกอบ

661
00:30:39,740 --> 00:30:41,189
แล้วตัดส่วนแยก

662
00:30:41,189 --> 00:30:43,230
และนี่คือสิ่งที่มันให้ความรู้สึก
เหมือนเรากำลัง copping ออก

663
00:30:43,230 --> 00:30:46,900
ฉันขอให้คุณที่จะเรียงลำดับ
n องค์ประกอบและฉัน

664
00:30:46,900 --> 00:30:50,712
บอกว่าตกลงไม่ได้โดยการเรียงลำดับ
ซ้ายและขวาเรียงลำดับ

665
00:30:50,712 --> 00:30:52,420
แต่ที่ฉันพูดอย่างใดอย่างหนึ่ง
สิ่งอื่น ๆ และนี่

666
00:30:52,420 --> 00:30:55,530
เป็นรูปแบบที่สำคัญดูเหมือนว่า
ในสัญชาตญาณป่านนี้

667
00:30:55,530 --> 00:30:57,380
มีขั้นตอนที่สามของการรวม

668
00:30:57,380 --> 00:31:00,430
ซึ่งแม้ว่ามันจะ
ดูเหมือนใบ้ในจิตวิญญาณ

669
00:31:00,430 --> 00:31:02,320
เช่นเดียวกับที่รวมสิ่งที่
ด้วยกันก็ดูเหมือนว่า

670
00:31:02,320 --> 00:31:05,380
จะเป็นขั้นตอนสำคัญต่อ
reassembly สองปัญหาที่

671
00:31:05,380 --> 00:31:07,330
ถูกแบ่งออกในที่สุดในช่วงครึ่งปี

672
00:31:07,330 --> 00:31:12,090
>> ดังนั้นรวมการจัดเรียงให้ทำเช่นนี้ถ้าคุณจะ
ขบขันฉันด้วยการสาธิตเพิ่มเติม

673
00:31:12,090 --> 00:31:14,730
เพียงเพื่อให้เรามีบาง
ตัวเลขที่จะทำงานกับ

674
00:31:14,730 --> 00:31:19,470
ฉันสามารถแลกเปลี่ยนแปดความเครียด
ลูกแปดคน?

675
00:31:19,470 --> 00:31:29,320
ขวาทั้งหมดเกี่ยวกับวิธีการที่คุณสามสี่
ในส่วนนี้ห้าหกและขอ

676
00:31:29,320 --> 00:31:30,720
ไม่ 7, 8, มาขึ้น

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
ตกลงใช่ตกลง

679
00:31:36,520 --> 00:31:38,640
ลบ 8 มีเราไปบวก 1

680
00:31:38,640 --> 00:31:39,150
ที่ดีเยี่ยม

681
00:31:39,150 --> 00:31:42,000
สิ่งที่ถูกต้องมาขึ้นให้
ได้อย่างรวดเร็วให้คุณหมายเลข

682
00:31:42,000 --> 00:31:50,800
จำนวนสองจำนวนสามบ้านเลขที่สี่
จำนวนห้าหกเจ็ดและแปด

683
00:31:50,800 --> 00:31:52,140
ฉันไม่แปดอย่างถูกต้องในครั้งนี้

684
00:31:52,140 --> 00:31:56,390
>> ตกลงเพื่อไปข้างหน้าถ้าคุณสามารถและ
ให้เรียงคำสั่งเดิม

685
00:31:56,390 --> 00:31:59,810
ว่าเรามีเมื่อวานนี้ซึ่งมอง
เช่นนี้ถ้าคุณจะไม่ทราบ

686
00:31:59,810 --> 00:32:03,620
และขอให้ทำมันในด้านหน้าของโต๊ะ

687
00:32:03,620 --> 00:32:06,510
ขวาทั้งหมดเพื่อรวมการจัดเรียง

688
00:32:06,510 --> 00:32:08,820
ซึ่งเป็นที่ที่มันจะ
ที่จะได้รับชนิดของที่น่าสนใจ

689
00:32:08,820 --> 00:32:12,800
เพราะผมดูเหมือนจะให้ตัวเอง
มากข้อมูลน้อยลงในวันนี้

690
00:32:12,800 --> 00:32:15,149
>> ดังนั้นการผสานการเรียงลำดับแรกของทุกคน
กับการป้อนข้อมูลขององค์ประกอบ n,

691
00:32:15,149 --> 00:32:18,440
และจะเห็นได้ชัดไม่น้อยกว่าสองก็
แปดดังนั้นฉันมีบางงานที่ต้องทำ

692
00:32:18,440 --> 00:32:21,140
ดังนั้นตอนนี้จิตใจเราเป็นชั้น
ขณะนี้อยู่ในสาขาอื่นที่

693
00:32:21,140 --> 00:32:22,540
ซึ่งหมายถึงขั้นตอนที่สาม

694
00:32:22,540 --> 00:32:25,017
ครั้งแรกผมต้องจัดเรียง
ซีกซ้ายขององค์ประกอบ

695
00:32:25,017 --> 00:32:26,350
ดังนั้นฉันจะไปเกี่ยวกับการทำเช่นนี้?

696
00:32:26,350 --> 00:32:28,950
ดีฉันจะชนิดของ
จิตใจแบ่งรายการที่นี่

697
00:32:28,950 --> 00:32:30,700
คุณจะได้ไม่ต้อง
ร่างกายย้ายและฉัน

698
00:32:30,700 --> 00:32:33,180
จะมุ่งเน้นเฉพาะใน
ซีกซ้ายขององค์ประกอบที่นี่

699
00:32:33,180 --> 00:32:36,770
ดังนั้นฉันจะไปเกี่ยวกับการเรียงลำดับ
รายการตอนนี้ที่มีขนาดสี่

700
00:32:36,770 --> 00:32:38,730
คืออะไร? ขั้นตอนวิธีของฉัน

701
00:32:38,730 --> 00:32:42,580
ครั้งแรกที่ผมตรวจสอบ n น้อยกว่าสองไม่มี
ดังนั้นผมจึงดำเนินการต่อไปบล็อกอื่นอีกครั้ง

702
00:32:42,580 --> 00:32:43,900
ครึ่งเรียงซ้ายขององค์ประกอบ

703
00:32:43,900 --> 00:32:45,608
>> ดังนั้นตอนนี้อีกครั้งจิตใจ
และนี่คือที่

704
00:32:45,608 --> 00:32:49,550
คุณต้องได้รับจำนวนมาก
ประวัติศาสตร์ทางจิตถ้าคุณจะ

705
00:32:49,550 --> 00:32:51,940
ตอนนี้ฉันกำลังเรียงลำดับด้านซ้าย
ครึ่งหนึ่งของซีกซ้าย

706
00:32:51,940 --> 00:32:57,000
สิทธิทั้งหมดดังนั้นตอนนี้ที่ผมเรียกรวมกันของฉัน
การเรียงลำดับขั้นตอนวิธีเป็น n น้อยกว่าสอง?

707
00:32:57,000 --> 00:33:00,590
ไม่เป็นสองดังนั้นฉันต้องจัดเรียง
ครึ่งซ้ายและครึ่งขวา

708
00:33:00,590 --> 00:33:02,042
ดังนั้นที่นี่เราไปจัดเรียงซีกซ้าย

709
00:33:02,042 --> 00:33:03,750
ทำไมคุณไม่เพียงแค่
ใช้เวลาหนึ่งก้าวไปข้างหน้า

710
00:33:03,750 --> 00:33:04,415
คุณชื่ออะไร?

711
00:33:04,415 --> 00:33:04,860
>> ผู้ชม: คาร์เรน

712
00:33:04,860 --> 00:33:05,260
>> ลำโพง: แดน

713
00:33:05,260 --> 00:33:06,040
และได้ก้าวไปข้างหน้า

714
00:33:06,040 --> 00:33:06,748
>> ผู้ชม: คาร์เรน

715
00:33:06,748 --> 00:33:09,000
ลำโพง: คาร์เรนทำ

716
00:33:09,000 --> 00:33:10,090
คุณพูดว่าคาร์เรนแดนหรือ?

717
00:33:10,090 --> 00:33:10,550
>> ผู้ชม: คาร์เรน

718
00:33:10,550 --> 00:33:11,216
>> ลำโพง: คาร์เรน

719
00:33:11,216 --> 00:33:14,422
ตกลงคาร์เรนได้ก้าว
ไปข้างหน้าและเขาจะเรียงตอนนี้

720
00:33:14,422 --> 00:33:16,130
และนี่คือเกือบ
เรียกร้องขาดความผิดใช่มั้ย?

721
00:33:16,130 --> 00:33:18,862
ฉันไม่ได้จริงๆดูเหมือนจะประสบความสำเร็จ
อะไร แต่ให้ดำเนินการต่อไป

722
00:33:18,862 --> 00:33:20,820
ตอนนี้ให้ฉันค้นหาที่พักที่เหมาะสม
ครึ่งหนึ่งขององค์ประกอบ

723
00:33:20,820 --> 00:33:21,200
คุณชื่ออะไร?

724
00:33:21,200 --> 00:33:21,690
>> ผู้ชม: ลุค

725
00:33:21,690 --> 00:33:22,273
>> ลำโพง: ลุค

726
00:33:22,273 --> 00:33:23,400
Come on, ก้าวไปข้างหน้า

727
00:33:23,400 --> 00:33:25,640
ทำผมได้แยกลุค

728
00:33:25,640 --> 00:33:28,570
ซีกซ้ายจะเรียงตอนนี้และ
ครึ่งขวาจะถูกจัดเรียงในขณะนี้

729
00:33:28,570 --> 00:33:30,770
อีกครั้ง แต่มีขั้นตอนที่สำคัญที่นี่

730
00:33:30,770 --> 00:33:32,940
ฉันจะทำอะไรต่อไปจะต้องทำอย่างไร

731
00:33:32,940 --> 00:33:33,941
รวมครึ่งแยก

732
00:33:33,941 --> 00:33:36,648
ตอนนี้เรากำลังจะมีเพียง
ทุกคนกลับมาในทางนี้

733
00:33:36,648 --> 00:33:38,620
เพราะผมชนิดของจำเ​​ป็น
พื้นที่รอยขีดข่วนบาง

734
00:33:38,620 --> 00:33:40,411
มันเกือบจะเหมือนเหล่านี้
พวกที่อยู่บนโต๊ะ

735
00:33:40,411 --> 00:33:42,460
และฉันต้องการห้องพักบางส่วน
ที่จะย้ายพวกเขาไปรอบ ๆ

736
00:33:42,460 --> 00:33:44,170
ดังนั้นฉันจะรวม
พวกคุณโดยการมอง

737
00:33:44,170 --> 00:33:45,960
ที่ครึ่งซ้ายและครึ่งขวา

738
00:33:45,960 --> 00:33:48,740
และผู้ที่เห็นได้ชัดมาก่อน
ครึ่งซ้ายหรือครึ่งหนึ่งใช่มั้ย?

739
00:33:48,740 --> 00:33:52,710
ดังนั้นครึ่งหนึ่งที่เหมาะสมจึงขอย้ายไปลุค
ที่นี่ไปยังตำแหน่งเดิมของคาร์เรน

740
00:33:52,710 --> 00:33:57,640
และตอนนี้ที่จะรวมครึ่งซ้ายของพวกเขาใน
คาร์เรนจะย้ายไปทางขวามี

741
00:33:57,640 --> 00:33:59,750
>> เพื่อให้ความรู้สึกเหมือนเกือบ
ผลการจัดเรียงฟอง

742
00:33:59,750 --> 00:34:02,482
แต่อัลกอริทึมพื้นฐานของฉัน
แตกต่างกันมากในเวลานี้

743
00:34:02,482 --> 00:34:04,815
แต่ตอนนี้เป็นสิ่งที่ได้รับ
ที่น่ารำคาญเล็ก ๆ น้อย ๆ เพราะคุณ

744
00:34:04,815 --> 00:34:06,810
ต้องย้อนกลับใจ
ที่ฉันไม่ทิ้ง

745
00:34:06,810 --> 00:34:09,893
ฉันได้รวมเพียงครึ่งเรียงลำดับ
ซึ่งหมายความว่าผมอยู่ในขั้นตอนวิธีของฉันได้อย่างไร

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
ฉันต้องจัดเรียงครึ่งขวา?

748
00:34:13,770 --> 00:34:15,910
>> ถ้าคุณย้อนกลับอย่างแท้จริง
ในวิดีโอที่คุณจะ

749
00:34:15,910 --> 00:34:18,339
เห็นว่าเราได้ไปนี้
จุดของลุคและคาร์เรน

750
00:34:18,339 --> 00:34:21,370
โดยเรียงลำดับจากซ้าย
ครึ่งหนึ่งของซีกซ้าย

751
00:34:21,370 --> 00:34:23,430
จากนั้นเรารวมผู้ที่
ส่วนที่เรียงลำดับที่

752
00:34:23,430 --> 00:34:27,941
หมายถึงขั้นตอนต่อไปคือการจัดเรียง
ครึ่งขวาของซีกซ้าย

753
00:34:27,941 --> 00:34:29,649
สิทธิทั้งหมดเพื่อให้
ทำเช่นนี้ได้อย่างรวดเร็วมากขึ้น

754
00:34:29,649 --> 00:34:33,282
สิทธิทั้งหมดหกฉันจะเรียกร้อง
คุณจะจัดเรียงในขณะนี้มาข้างหน้า

755
00:34:33,282 --> 00:34:33,990
คุณชื่ออะไร?

756
00:34:33,990 --> 00:34:34,589
>> ผู้ชม: Adriano

757
00:34:34,589 --> 00:34:35,200
>> ลำโพง: Adriano

758
00:34:35,200 --> 00:34:36,010
Adriano จะเรียงตอนนี้

759
00:34:36,010 --> 00:34:36,450
และสิ่งที่ชื่อของคุณ?

760
00:34:36,450 --> 00:34:37,080
>> ผู้ชม: อเล็กซ์

761
00:34:37,080 --> 00:34:38,379
>> ลำโพง: อเล็กซ์จะเรียงตอนนี้

762
00:34:38,379 --> 00:34:40,750
ครึ่งซ้ายครึ่งขวา
สิ่งที่อยู่ในขั้นตอนสุดท้าย?

763
00:34:40,750 --> 00:34:41,250
การผสาน

764
00:34:41,250 --> 00:34:44,310
สวยน่ารำคาญดังนั้นฉัน
จะไปรวมอยู่ในที่หก,

765
00:34:44,310 --> 00:34:46,930
ใช้ขั้นตอนกลับ
แปดใช้ขั้นตอนกลับ

766
00:34:46,930 --> 00:34:49,530
และตอนนี้แจ้งให้ทราบนี้เป็น
Takeaway มีประโยชน์อะไร

767
00:34:49,530 --> 00:34:53,930
ขณะนี้เป็นจริงประมาณครึ่งหนึ่งทางด้านซ้ายของ
รายการโดยไม่คำนึงถึงวิธีการที่เราเริ่ม?

768
00:34:53,930 --> 00:34:55,090
มันจะถูกจัดเรียง

769
00:34:55,090 --> 00:34:57,750
>> ตอนนี้มันไม่ได้เรียงลำดับใน
โครงการขนาดใหญ่ของสิ่งที่

770
00:34:57,750 --> 00:35:00,250
แต่มันจะถูกจัดเรียงอย่างเป็นอิสระ
ของอีกครึ่งหนึ่ง

771
00:35:00,250 --> 00:35:04,100
ตอนนี้สิ่งที่ขั้นตอนที่ฉันอยู่กับว่าฉันเก็บ
rewinding ว่าเรื่องเริ่ม?

772
00:35:04,100 --> 00:35:05,680
ตอนนี้ฉันต้องจัดเรียงครึ่งขวา

773
00:35:05,680 --> 00:35:07,630
ดังนั้นตอนนี้เรากำลังย้อนกลับไปที่
จุดเริ่มต้นของเรื่อง

774
00:35:07,630 --> 00:35:08,921
และขอให้ทำเช่นนี้มากขึ้นอย่างรวดเร็ว

775
00:35:08,921 --> 00:35:11,320
ดังนั้นฉันจะต้องเรียงลำดับ
ครึ่งขวาของรายชื่อทั้งหมด

776
00:35:11,320 --> 00:35:13,060
สิ่งที่ขั้นตอนต่อไปหรือไม่

777
00:35:13,060 --> 00:35:15,840
เรียงครึ่งที่เหลือของครึ่งขวา

778
00:35:15,840 --> 00:35:18,715
เรียงครึ่งทางด้านซ้ายของ
ครึ่งซ้ายครึ่งขวา

779
00:35:18,715 --> 00:35:19,590
และสิ่งที่ชื่อของคุณ?

780
00:35:19,590 --> 00:35:20,230
>> ผู้ชม: โอมาร์

781
00:35:20,230 --> 00:35:21,970
>> ลำโพง: โอมาร์ก้าวไปข้างหน้าทำ

782
00:35:21,970 --> 00:35:22,860
ซีกซ้ายจะเรียง

783
00:35:22,860 --> 00:35:23,330
และสิ่งที่ชื่อของคุณ?

784
00:35:23,330 --> 00:35:23,820
>> ผู้ชม: คริส

785
00:35:23,820 --> 00:35:25,620
>> ลำโพง: คริสจะใช้ขั้นตอน
ข้างหน้าคุณจะจัดเรียงตอนนี้

786
00:35:25,620 --> 00:35:27,010
อะไรคือขั้นตอนสำคัญตอนนี้หรือไม่

787
00:35:27,010 --> 00:35:27,510
การผสาน

788
00:35:27,510 --> 00:35:30,509
ดังนั้นหนึ่งจะไปรวมอยู่ในสถานที่
ที่นี่ถ้าคุณจะใช้ขั้นตอนกลับ

789
00:35:30,509 --> 00:35:32,930
และสามเป็นไปได้
ใช้ขั้นตอนกลับผสาน

790
00:35:32,930 --> 00:35:38,080
ดังนั้นครึ่งหนึ่งทางด้านซ้ายของ
ครึ่งขวาจะเรียงตอนนี้

791
00:35:38,080 --> 00:35:41,747
ตรงไปตรงมาขั้นตอนนี้รู้สึกเหมือนเรา
จะเสียเวลามากกว่าก่อน

792
00:35:41,747 --> 00:35:44,830
แต่ถ้าเราทำอย่างนี้ในเวลาจริงเราจะ
ดูสิ่งที่คบจะเป็น

793
00:35:44,830 --> 00:35:47,970
ตอนนี้ที่นี่ฉันขวา
ครึ่งหนึ่งของครึ่งขวา

794
00:35:47,970 --> 00:35:50,170
ให้ฉันไปข้างหน้าและจัดเรียงครึ่งที่เหลือ

795
00:35:50,170 --> 00:35:51,482
ก้าวไปข้างหน้าสิ่งที่ชื่อของคุณ?

796
00:35:51,482 --> 00:35:52,190
ผู้ชม: แรมซีย์

797
00:35:52,190 --> 00:35:53,210
ลำโพง: แรมซีย์จะเรียงตอนนี้

798
00:35:53,210 --> 00:35:53,570
คุณชื่ออะไร?

799
00:35:53,570 --> 00:35:54,200
>> ผู้ชม: มารีน่า

800
00:35:54,200 --> 00:35:57,033
>> ลำโพง: มารีน่าจะถูกจัดเรียงในขณะนี้
ดีถ้าคุณใช้เวลาหนึ่งก้าวไปข้างหน้า

801
00:35:57,033 --> 00:36:00,690
ขั้นตอนที่สำคัญที่นี่คือตอนนี้ผสานฉัน
จะถอนจากสองรายการของฉัน

802
00:36:00,690 --> 00:36:01,720
ซ้ายและขวา

803
00:36:01,720 --> 00:36:05,150
ห้าเป็นไปได้มาก่อน
และเจ็ดจะมาต่อไป

804
00:36:05,150 --> 00:36:06,410
และอีกครั้งนี้เป็นเจตนา

805
00:36:06,410 --> 00:36:08,535
ความจริงที่ว่าพวกเขากำลังทำ
ก้าวไปข้างหน้าและย้อนกลับ

806
00:36:08,535 --> 00:36:12,997
มีขึ้นเพื่อแสดงว่าเราไม่สามารถ
ทำขั้นตอนนี้ในสถานที่ได้อย่างง่ายดาย

807
00:36:12,997 --> 00:36:15,830
เป็นประเภทฟองและการจัดเรียงเลือก
และการจัดเรียงแทรกที่เราเพียงแค่

808
00:36:15,830 --> 00:36:16,960
เก็บไว้คนแลกเปลี่ยน

809
00:36:16,960 --> 00:36:19,940
แท้จริงฉันจำเป็นต้องเรียงลำดับ
กระดาษรอยขีดข่วนที่

810
00:36:19,940 --> 00:36:21,827
ที่จะทำให้คนเหล่านี้
ในขณะที่ผมทำรวมกันที่

811
00:36:21,827 --> 00:36:23,410
แล้วผมจะสามารถนำพวกเขากลับมาอยู่ในสถานที่

812
00:36:23,410 --> 00:36:27,260
และที่สำคัญเพราะฉันใช้
ทรัพยากรใหม่พื้นที่ไม่ได้เป็นเวลาเพียงแค่

813
00:36:27,260 --> 00:36:28,270
>> ตกลงนี้เป็นที่น่าตื่นตาตื่นใจ

814
00:36:28,270 --> 00:36:32,050
ครึ่งที่เหลือจะถูกจัดเรียงครึ่งหนึ่งที่ถูกต้องคือ
เรียงลำดับตอนนี้ที่สำคัญการรวมขั้นตอนที่

815
00:36:32,050 --> 00:36:33,450
วิธีที่ฉันจะไปรวมนี้ได้อย่างไร

816
00:36:33,450 --> 00:36:35,470
ดังนั้นถ้าคุณจะทำตามฉัน
มือซ้ายและขวามือ

817
00:36:35,470 --> 00:36:38,930
ฉันจะชี้มือซ้ายของฉัน
ที่ครึ่งซ้ายขวามือของเรา

818
00:36:38,930 --> 00:36:42,680
ที่ครึ่งขวาและตอนนี้ฉันต้อง
ตัดสินใจขั้นตอนโดยขั้นตอนที่จะรวมอยู่ใน

819
00:36:42,680 --> 00:36:44,650
ที่เห็นได้ชัดมาก่อน?

820
00:36:44,650 --> 00:36:45,150
จำนวนหนึ่ง

821
00:36:45,150 --> 00:36:47,327
ดังนั้นเมื่อมากว่าที่นี่
นี่เป็นแผ่นรอยขีดข่วนของเรา

822
00:36:47,327 --> 00:36:49,910
ดังนั้นตอนนี้อันดับหนึ่งและแจ้งให้ทราบล่วงหน้า
สิ่งที่ฉันจะทำอย่างไรกับขวามือของเรา

823
00:36:49,910 --> 00:36:54,152
ฉันจะย้ายที่ขวามือของเรา
ก้าวข้ามไปยังจุดที่บ้านเลขที่สาม

824
00:36:54,152 --> 00:36:55,860
และตอนนี้ฉันจะต้องทำ
การตัดสินใจที่เดียวกัน

825
00:36:55,860 --> 00:36:58,387
และที่จริงการยืนที่ถูกต้องใน
ด้านหน้าของลุคที่นี่หากคุณทำได้

826
00:36:58,387 --> 00:36:59,720
เพราะเป็นแผ่นรอยขีดข่วนของเรา

827
00:36:59,720 --> 00:37:00,610
ดังนั้นผู้ที่มาต่อไปหรือไม่

828
00:37:00,610 --> 00:37:05,000
เรามีลุคที่มีหมายเลขสอง
หรือคริสที่มีบ้านเลขที่สาม

829
00:37:05,000 --> 00:37:07,460
เห็นได้ชัดว่าลุคจำนวน
สองเพื่อให้คุณมาที่นี่

830
00:37:07,460 --> 00:37:11,270
>> แต่มือซ้ายของฉันตอนนี้เป็นไปได้
จะเพิ่มขึ้นไปยังจุดที่คาร์เรน

831
00:37:11,270 --> 00:37:15,160
และนี่คือกุญแจสำคัญที่นำมาใช้กับ
รวมฉันจะให้ทำเช่นนี้

832
00:37:15,160 --> 00:37:17,340
เห็นได้ชัดว่าถ้าคุณชนิด
ของตามตรรกะ

833
00:37:17,340 --> 00:37:19,670
แต่มือของฉันที่ไม่เคย
จะไปข้างหลัง

834
00:37:19,670 --> 00:37:23,861
ซึ่งหมายความว่าฉันไม่เคยที่จะย้ายไป
ทิ้งให้อยู่กับขั้นตอนการผสมของฉัน

835
00:37:23,861 --> 00:37:26,360
และนั่นจะเป็นกุญแจสำคัญในการ
การวิเคราะห์ของเราในเวลาเพียงสักครู่

836
00:37:26,360 --> 00:37:27,859
>> ดังนั้นตอนนี้ให้เสร็จสิ้นนี้ขึ้นอย่างรวดเร็ว

837
00:37:27,859 --> 00:37:31,650
ดังนั้นสามมาต่อไป
แล้วสี่มาต่อไป

838
00:37:31,650 --> 00:37:38,750
และตอนนี้ห้ามาต่อไปแล้วหก
เจ็ดและแปดแล้วในที่สุด

839
00:37:38,750 --> 00:37:42,960
รู้สึกเหมือนอัลกอริทึมที่ช้าที่สุด
แต่ถ้าเราไม่ได้จริง

840
00:37:42,960 --> 00:37:45,510
เรียกใช้ในการจัดเรียงเดียวกัน
ความเร็วนาฬิกาดังนั้นเพื่อ

841
00:37:45,510 --> 00:37:48,106
พูดแบบเดียวกับ
ฟ้องนาฬิกาเหมือนก่อน

842
00:37:48,106 --> 00:37:48,605
ทำไม?

843
00:37:48,605 --> 00:37:51,100
ดีลองมา
มองไปที่ผลสุดท้าย

844
00:37:51,100 --> 00:37:56,990
>> ลองย้อนกลับไปกว่าที่นี่ให้ฉัน
ดึงสาธิตสายตา

845
00:37:56,990 --> 00:37:59,030
ของสิ่งที่เราได้ทำ

846
00:37:59,030 --> 00:38:06,110
ซูมในที่นี่เกี่ยวกับเรื่องนี้
หน้าที่นี่บอก Firefox

847
00:38:06,110 --> 00:38:08,200
ว่าเราต้องการที่จะคิว
ในกล่องนี้ขอ

848
00:38:08,200 --> 00:38:11,260
กล่าวว่าการจัดเรียงฟองที่
เราคุ้นเคยกันดี

849
00:38:11,260 --> 00:38:14,130
การจัดเรียงตัวเลือกซึ่งเป็นอีกหนึ่ง
ค่อนข้างตรงไปตรงมาอย่างใดอย่างหนึ่ง

850
00:38:14,130 --> 00:38:18,250
และตอนนี้วันนี้การจัดเรียงผสานที่
จะจบยอดของเรา

851
00:38:18,250 --> 00:38:21,530
เหตุผลที่มันต้องใช้เวลามากอีกต่อไป
ที่นี่กับมนุษย์และฉันด้วยวาจาเป็น

852
00:38:21,530 --> 00:38:23,480
เห็นได้ชัดว่าผมอธิบายทุกขั้นตอน

853
00:38:23,480 --> 00:38:26,920
แต่ถ้าคุณเพียงแค่ดำเนินการนี​​้มาก
เหมือนอย่างที่เราได้จัดเรียงฟองและการเลือก

854
00:38:26,920 --> 00:38:30,890
ไม่เพียง แต่การจัดเรียงสายตาดู
เพียงวิธีที่มีประสิทธิภาพมากขึ้น

855
00:38:30,890 --> 00:38:33,330
ใช้ประโยชน์จากการนี​​้
การแบ่งและพิชิต

856
00:38:33,330 --> 00:38:39,150
สามารถเมื่อนำไปใช้กับชุดข้อมูลที่
ไม่ได้ขนาดแปด แต่แม้มาก

857
00:38:39,150 --> 00:38:39,970
มีขนาดใหญ่มาก

858
00:38:39,970 --> 00:38:44,585
ฉันให้คุณผสานเรียงลำดับเคียง
ข้างกับอัลกอริทึมอื่น ๆ เหล่านี้

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
นี้จะได้รับความเจ็บปวด
ได้อย่างรวดเร็วและจบ

861
00:38:58,530 --> 00:39:00,890
ไม่ได้ยอดโดยเฉพาะอย่างยิ่ง
พวกเขาก็จบลงด้วยการแยก

862
00:39:00,890 --> 00:39:05,280
แต่ที่สำคัญนำมาใช้ก็คือ
ดูวิธีการได้เร็วขึ้นมากรวมการจัดเรียง

863
00:39:05,280 --> 00:39:08,110
คือถ้าคุณคิดว่าฉัน
เพียงชนิดของล้อเล่นกับคุณ

864
00:39:08,110 --> 00:39:13,100
ถ้าเราทำเช่นนี้เป็นครั้งสุดท้าย,
เรามาโหลดนี้ขอกลับไป

865
00:39:13,100 --> 00:39:14,960
และเลือกการจัดเรียงฟอง
และเพียงเพื่อความบันเทิง

866
00:39:14,960 --> 00:39:17,330
ให้เลือกแทรก
จัดเรียงเพียงการวัดที่ดี

867
00:39:17,330 --> 00:39:20,020
และในครั้งนี้อีกครั้งให้
เลือกตัดจัดเรียงและขอ

868
00:39:20,020 --> 00:39:21,595
ทำงานจริงข้างเคียงเหล่านี้อยู่เคียงข้าง

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> และยังไม่ได้ในความเป็นจริงความบังเอิญ

871
00:39:26,930 --> 00:39:31,140
สิ่งที่ฉันได้ทำอย่างมีประสิทธิภาพเป็นฉัน
แบ่งใส่ของฉันในช่วงครึ่งปีอีกครั้ง

872
00:39:31,140 --> 00:39:32,240
และอีกครั้งและอีกครั้ง

873
00:39:32,240 --> 00:39:35,590
และมีเพียงหลายครั้งที่คุณสามารถ
แบ่งการป้อนข้อมูลของคุณลงในครึ่งซ้าย

874
00:39:35,590 --> 00:39:36,240
และขวา

875
00:39:36,240 --> 00:39:39,425
อะไรคือสูตรที่เราให้เห็น
ที่อธิบายส่วนในช่วงครึ่งปี

876
00:39:39,425 --> 00:39:41,050
อีกครั้งและอีกครั้งและอีกครั้งและอีกครั้งหรือไม่

877
00:39:41,050 --> 00:39:41,890
>> ผู้ชม: เข้าสู่ระบบ n

878
00:39:41,890 --> 00:39:42,760
>> ลำโพง: เข้าสู่ระบบ n

879
00:39:42,760 --> 00:39:46,300
แต่ก็มีขั้นตอนหนึ่งที่สำคัญอื่น ๆ
อัลกอริทึมนี้ไม่ได้เข้าสู่ระบบขั้นตอน n

880
00:39:46,300 --> 00:39:48,992
ถ้ามันเป็นเพียง log n ขั้นตอน
เราจะอยู่ในปัญหาเดียวกัน

881
00:39:48,992 --> 00:39:51,200
เหมือนก่อนหน้านี้ที่เราไม่สามารถ
แน่ใจว่าทุกอย่างของการจัดเรียง

882
00:39:51,200 --> 00:39:54,480
คุณต้องมองไปที่น้อยที่สุดองค์ประกอบ n
เพื่อให้แน่ใจว่า n องค์ประกอบเรียงลำดับ

883
00:39:54,480 --> 00:39:55,950
มิฉะนั้นมันเป็นก้าวกระโดดของความศรัทธา

884
00:39:55,950 --> 00:39:59,810
>> ดังนั้นจึงเป็นบันทึกน้อยที่สุด n ขั้นตอน แต่
สิ่งที่เกี่ยวกับขั้นตอนการผสมคีย์นี้

885
00:39:59,810 --> 00:40:04,370
ที่ผมรวมครึ่งซ้ายและขวา
ครึ่งและเดินข้ามเวที?

886
00:40:04,370 --> 00:40:06,980
วิธีการหลายขั้นตอนที่จะรวมคืออะไร?

887
00:40:06,980 --> 00:40:10,150
มันเป็น n แต่ฉันไม่ได้เพียงแค่
รวมครั้งสุดท้าย

888
00:40:10,150 --> 00:40:15,089
ในแต่ละสายซ้อนเหล่านั้นในแต่ละ
ของผสานซ้อนกันนั้นผมก็ยังห่าง

889
00:40:15,089 --> 00:40:18,380
ฉันรวมทั้งสองคนแล้วสองคนนี้
คนจากนั้นทั้งสองคนและอื่น ๆ

890
00:40:18,380 --> 00:40:19,955
>> ดังนั้นผมจึงไม่รวมอีกครั้งและอีกครั้ง

891
00:40:19,955 --> 00:40:20,580
กี่ครั้ง?

892
00:40:20,580 --> 00:40:23,510
ดังนั้นทุกครั้งที่ผมแบ่ง
รายการในช่วงครึ่งปีที่ฉันได้ผสาน

893
00:40:23,510 --> 00:40:25,460
แบ่งรายการในช่วงครึ่งปีทำผสาน

894
00:40:25,460 --> 00:40:28,570
ดังนั้นหากการแบ่งรายการ
สามารถทำได้ล็อก n ครั้ง

895
00:40:28,570 --> 00:40:33,880
และการรวมกันในท้ายที่สุดจะใช้เวลา n
ขั้นตอนสิ่งที่อาจจะตอนบน

896
00:40:33,880 --> 00:40:37,000
ผูกพันในการทำงาน
เวลาของขั้นตอนวิธีของเราหรือไม่

897
00:40:37,000 --> 00:40:37,980
n log n

898
00:40:37,980 --> 00:40:40,560
>> และแน่นอนว่าเป็นสิ่งที่
เราได้ประสบความสำเร็จที่นี่

899
00:40:40,560 --> 00:40:44,650
ดังนั้นความรู้สึกที่คุณเห็นสายตาเมื่อ
ทั้งสามสิ่งที่ทำงานเคียงข้าง

900
00:40:44,650 --> 00:40:47,930
เป็นกำลังสองกับ n n
กำลังสองกับ n บันทึก n

901
00:40:47,930 --> 00:40:51,010
ซึ่งพื้นฐานที่เราจะเห็น
วันนี้ไม่เพียง แต่ในอนาคต

902
00:40:51,010 --> 00:40:52,760
เป็นมากได้เร็วขึ้นมาก

903
00:40:52,760 --> 00:40:56,010
รอบของเสียงปรบมือสำหรับผู้ชายเหล่านี้
ผมจะตอบแทนพวกเขากับลูกความเครียด

904
00:40:56,010 --> 00:41:00,260
ขอเลื่อนการที่นี่ในวันนี้และ
เราจะเห็นคุณในวันจันทร์ที่

905
00:41:00,260 --> 00:41:02,255