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

2
00:00:11,904 --> 00:00:12,910
>> ศาสตราจารย์: สิทธิทั้งหมด

3
00:00:12,910 --> 00:00:16,730
นี่คือ CS50 และนี่คือ
ในตอนท้ายของสัปดาห์ที่สาม

4
00:00:16,730 --> 00:00:20,230
ดังนั้นเราอยู่ที่นี่ในวันนี้ไม่ได้อยู่ในแซนเดอ
โรงละครแทนใน Weidner ห้องสมุด

5
00:00:20,230 --> 00:00:23,170
ภายในซึ่งเป็นสตูดิโอ
ที่รู้จักกันเป็น Hauser สตูดิโอ,

6
00:00:23,170 --> 00:00:28,310
หรือเราจะว่าสตูดิโอ H หรือจะ
เรา say-- ถ้าคุณชอบเรื่องตลกที่

7
00:00:28,310 --> 00:00:30,540
ก็จริงจาก
เพื่อนร่วมชั้นมาร์คออนไลน์

8
00:00:30,540 --> 00:00:32,420
ที่แนะนำให้มากที่สุดผ่านทาง Twitter

9
00:00:32,420 --> 00:00:34,270
ตอนนี้สิ่งที่ดีๆเกี่ยวกับ
มาอยู่ที่นี่ในสตูดิโอ

10
00:00:34,270 --> 00:00:38,410
คือว่าผมกำลังล้อมรอบด้วยสีเขียวเหล่านี้
ผนังหน้าจอสีเขียวหรือ chromakey,

11
00:00:38,410 --> 00:00:43,290
เพื่อที่จะพูดซึ่งหมายความว่า CS50 ของ
ทีมผู้ผลิตถิ่นกับผม

12
00:00:43,290 --> 00:00:47,380
ตอนนี้อาจจะมีการวาง
ผมมากที่สุดที่ใดก็ได้ในโลก

13
00:00:47,380 --> 00:00:48,660
ให้ดีขึ้นหรือแย่ลง

14
00:00:48,660 --> 00:00:51,800
>> ตอนนี้สิ่งที่อยู่ข้างหน้าปัญหาตั้ง
ทั้งสองอยู่ในมือของคุณในสัปดาห์นี้

15
00:00:51,800 --> 00:00:53,830
แต่ที่มีปัญหาตั้ง
สามสัปดาห์นี้มา

16
00:00:53,830 --> 00:00:56,600
คุณจะได้รับการท้าทายกับ
เกมที่เรียกว่า 15

17
00:00:56,600 --> 00:00:58,960
ความโปรดปรานของบุคคลที่เก่าที่
คุณอาจได้รับจำ

18
00:00:58,960 --> 00:01:02,030
เป็นเด็กที่มีพวงทั้งหมด
ของตัวเลขที่สามารถเลื่อนขึ้นลง

19
00:01:02,030 --> 00:01:05,790
ซ้ายและขวาและมีหนึ่งช่องว่าง
ภายในปริศนาลงไปในที่ที่คุณ

20
00:01:05,790 --> 00:01:07,840
จริงสามารถเลื่อนชิ้นส่วนปริศนาเหล่านั้น

21
00:01:07,840 --> 00:01:11,150
ในท้ายที่สุดคุณจะได้รับนี้
ปริศนาในการสุ่มบางกึ่ง

22
00:01:11,150 --> 00:01:12,940
และมีเป้าหมายที่จะ
จัดเรียงบนลงล่าง

23
00:01:12,940 --> 00:01:16,310
จากซ้ายไปขวาจากที่หนึ่ง
ตลอดทางขึ้นถึง 15

24
00:01:16,310 --> 00:01:19,360
>> แต่น่าเสียดายที่การดำเนินการ
คุณจะมีที่อยู่ในมือ

25
00:01:19,360 --> 00:01:21,590
เป็นไปได้ซอฟแวร์
ตามร่างกายไม่ได้

26
00:01:21,590 --> 00:01:25,280
คุณจริงจะต้องมีการเขียน
รหัสที่เป็นนักศึกษาหรือผู้ใช้สามารถ

27
00:01:25,280 --> 00:01:26,760
เล่นเกมที่ 15

28
00:01:26,760 --> 00:01:29,030
และในความเป็นจริงในแฮ็กเกอร์
รุ่นของเกมที่ 15

29
00:01:29,030 --> 00:01:32,155
คุณจะเป็นสิ่งที่ท้าทายในการดำเนินการ
ไม่ได้เป็นเพียงการเล่นของโรงเรียนเก่า

30
00:01:32,155 --> 00:01:35,010
เกม แต่แก้
ของมันการใช้โหมดพระเจ้า

31
00:01:35,010 --> 00:01:38,280
เพื่อที่จะพูดที่จริง
แก้ปริศนาสำหรับมนุษย์

32
00:01:38,280 --> 00:01:41,080
โดยให้พวกเขาด้วยคำแนะนำ,
หลังจากที่คำแนะนำหลังจากที่คำใบ้

33
00:01:41,080 --> 00:01:42,280
ดังนั้นเพิ่มเติมว่าในสัปดาห์หน้า

34
00:01:42,280 --> 00:01:43,720
แต่นั่นคือสิ่งที่อยู่ข้างหน้า

35
00:01:43,720 --> 00:01:47,610
>> สำหรับตอนนี้จำได้ว่าสัปดาห์ก่อนหน้านี้
เรามีเรื่องราวที่น่าตื่นเต้นนี้ถ้าคุณจะ

36
00:01:47,610 --> 00:01:52,560
โดยที่ดีที่สุดที่เรากำลังทำเรียงลำดับ
ฉลาดเป็นขีด จำกัด บนของขนาดใหญ่ของ n o

37
00:01:52,560 --> 00:01:53,210
ยกกำลังสอง

38
00:01:53,210 --> 00:01:56,520
ในคำอื่น ๆ , การจัดเรียงฟอง
เลือกการเรียงลำดับเรียงลำดับแทรก

39
00:01:56,520 --> 00:01:59,120
ทั้งหมดของพวกเขาในขณะที่ที่แตกต่างกัน
ในการดำเนินงานของพวกเขา

40
00:01:59,120 --> 00:02:03,480
เงินทองเป็น n ยืดทำงาน
เวลาในกรณีที่เลวร้ายที่สุดมาก

41
00:02:03,480 --> 00:02:06,010
และเรามักจะคิดว่า
กรณีที่เลวร้ายที่สุดสำหรับการเรียงลำดับ

42
00:02:06,010 --> 00:02:08,814
เป็นสิ่งหนึ่งที่ปัจจัยการผลิตของคุณ
จะสมบูรณ์ไปข้างหลัง

43
00:02:08,814 --> 00:02:11,980
และแน่นอนมันต้องใช้เวลาค่อนข้างไม่กี่ขั้นตอน
ในการดำเนินการแต่ละขั้นตอนวิธีการเหล่านั้น

44
00:02:11,980 --> 00:02:15,110
>> ตอนนี้ที่ปลายสุดของชั้น
การเรียกคืนเราเมื่อเทียบกับการจัดเรียงฟอง

45
00:02:15,110 --> 00:02:19,390
กับการจัดเรียงตัวเลือกกับคนอื่น ๆ
ที่เราเรียกว่าการจัดเรียงผสานในเวลานั้น

46
00:02:19,390 --> 00:02:22,120
และผมเสนอว่าจะพา
ประโยชน์จากบทเรียนจากสัปดาห์

47
00:02:22,120 --> 00:02:24,060
ศูนย์แบ่งและพิชิต

48
00:02:24,060 --> 00:02:28,810
และอย่างใดบรรลุชนิดของ
ลอการิทึมเวลาทำงานที่สุด

49
00:02:28,810 --> 00:02:31,024
แทนการบางสิ่งบางอย่าง
ที่ล้วนกำลังสอง

50
00:02:31,024 --> 00:02:33,440
และก็ไม่ได้ลอการิทึมมาก
มันเป็นบิตมากขึ้นกว่าที่

51
00:02:33,440 --> 00:02:36,520
แต่ถ้าคุณจำได้จากชั้นเรียน
มันเป็นมากเร็ว

52
00:02:36,520 --> 00:02:38,210
ลองมาดูที่ที่เราปล่อยออกมา

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> เมื่อเทียบกับการจัดเรียงฟองเลือก
เมื่อเทียบกับการจัดเรียงผสานการเรียงลำดับ

55
00:02:45,370 --> 00:02:47,700
ตอนนี้พวกเขากำลังทั้งหมดที่ทำงานใน
ทฤษฎีในเวลาเดียวกัน

56
00:02:47,700 --> 00:02:50,510
ซีพียูทำงานที่ความเร็วเท่ากัน

57
00:02:50,510 --> 00:02:54,990
แต่คุณสามารถรู้สึกว่าน่าเบื่อนี้
เป็นอย่างมากได้อย่างรวดเร็วจะกลายเป็น

58
00:02:54,990 --> 00:02:58,790
และเพียงแค่วิธีการที่รวดเร็วเมื่อเราฉีด
บิตของขั้นตอนวิธีการศูนย์สัปดาห์,

59
00:02:58,790 --> 00:03:00,080
เราสามารถเร็วขึ้น

60
00:03:00,080 --> 00:03:01,630
>> ดังนั้นการจัดเรียงเครื่องหมายลักษณะที่น่าตื่นตาตื่นใจ

61
00:03:01,630 --> 00:03:05,220
วิธีการที่เราสามารถใช้ประโยชน์จากมันในการสั่งซื้อ
การเรียงลำดับจำนวนขึ้นอย่างรวดเร็ว

62
00:03:05,220 --> 00:03:07,140
ดีขอคิดว่ากลับ
ส่วนผสมที่เรา

63
00:03:07,140 --> 00:03:10,380
ได้กลับมาในสัปดาห์ที่ศูนย์ของ
หาคนที่อยู่ในสมุดโทรศัพท์

64
00:03:10,380 --> 00:03:12,380
และจำได้ว่า
pseudocode ที่เรานำเสนอ

65
00:03:12,380 --> 00:03:14,560
ผ่านทางที่เราสามารถหา
คนที่ชอบไมค์สมิ ธ

66
00:03:14,560 --> 00:03:16,310
มองสิ่งเล็กน้อยเช่นนี้

67
00:03:16,310 --> 00:03:20,820
>> ตอนนี้มาดูโดยเฉพาะ
ที่เส้น 7 และ 8 และ 10 และ 11,

68
00:03:20,820 --> 00:03:25,240
ซึ่งก่อให้เกิดห่วงว่าด้วยเหตุนี้เราเก็บไว้
จะกลับไปที่สาย 3 อีกครั้งและอีกครั้ง

69
00:03:25,240 --> 00:03:26,520
และอีกครั้ง.

70
00:03:26,520 --> 00:03:31,790
แต่มันกลับกลายเป็นว่าเราสามารถดู
อัลกอริทึมนี้ที่นี่ใน pseudocode,

71
00:03:31,790 --> 00:03:33,620
เล็ก ๆ น้อย ๆ แบบองค์รวม

72
00:03:33,620 --> 00:03:35,960
ในความเป็นจริงสิ่งที่ฉันกำลังมองหา
ที่นี่บนหน้าจอ

73
00:03:35,960 --> 00:03:41,180
เป็นอัลกอริทึมสำหรับการค้นหาสำหรับ
ไมค์สมิ ธ ในชุดของบางหน้า

74
00:03:41,180 --> 00:03:45,520
และแน่นอนเราสามารถลดความซับซ้อนนี้
อัลกอริทึมในเส้นที่ 7 และ 8

75
00:03:45,520 --> 00:03:49,860
และ 10 และ 11 ที่จะเพียงแค่พูดแบบนี้
ซึ่งผมได้นำเสนอที่นี่ในสีเหลือง

76
00:03:49,860 --> 00:03:52,210
ในคำอื่น ๆ ถ้าไมค์
สมิ ธ เป็นก่อนหน้านี้ในหนังสือเล่มนี้

77
00:03:52,210 --> 00:03:55,004
เราไม่จำเป็นต้องระบุขั้นตอน
โดยขั้นตอนในขณะนี้ว่าจะไปหาเขา

78
00:03:55,004 --> 00:03:56,920
เราไม่ได้มีการระบุ
ที่จะกลับไปสาย 3

79
00:03:56,920 --> 00:03:58,960
ทำไมเราไม่เพียง แต่
พูดมากกว่าปกติ

80
00:03:58,960 --> 00:04:01,500
ค้นหาไมค์ใน
ครึ่งซ้ายของหนังสือเล่มนี้

81
00:04:01,500 --> 00:04:03,960
>> ตรงกันข้ามถ้าไมค์เป็น
จริงต่อมาในหนังสือเล่มนี้

82
00:04:03,960 --> 00:04:07,540
ทำไมเราไม่เพียงแค่พูดค้นหาได้นำมาอ้าง
สำหรับไมค์ในช่วงครึ่งขวาของหนังสือเล่มนี้

83
00:04:07,540 --> 00:04:11,030
ในคำอื่น ๆ ว่าทำไมเราไม่เพียง
การเรียงลำดับของถ่อกับตัวเองว่า

84
00:04:11,030 --> 00:04:13,130
ค้นหาไมค์ในครั้งนี้
ส่วนหนึ่งของหนังสือเล่มนี้

85
00:04:13,130 --> 00:04:16,279
และปล่อยให้มีอยู่ของเรา
ขั้นตอนวิธีการที่จะบอกเรา

86
00:04:16,279 --> 00:04:18,750
วิธีการค้นหาในไมค์
ว่าครึ่งหนึ่งทางด้านซ้ายของหนังสือเล่มนี้

87
00:04:18,750 --> 00:04:20,750
ในคำอื่น ๆ ของเรา
ขั้นตอนวิธีการทำงานไม่ว่าจะเป็น

88
00:04:20,750 --> 00:04:24,670
สมุดโทรศัพท์ของความหนานี้นี้
ความหนาหรือความหนาใด ๆ

89
00:04:24,670 --> 00:04:27,826
เพื่อให้เราสามารถซ้ำ
กำหนดขั้นตอนวิธีนี้

90
00:04:27,826 --> 00:04:29,950
ในคำอื่น ๆ ที่
หน้าจอที่นี่เป็นอัลกอริทึม

91
00:04:29,950 --> 00:04:33,130
สำหรับการค้นหาสำหรับไมค์สมิ ธ
หมู่หน้าของหนังสือเล่มโทรศัพท์

92
00:04:33,130 --> 00:04:37,410
ดังนั้นในบรรทัดที่ 7 และ 10 ขอ
เพียงแค่บอกว่าที่

93
00:04:37,410 --> 00:04:40,250
และฉันจะใช้ระยะเวลาสักครู่นี้
ที่ผ่านมาและแน่นอนการเรียกซ้ำ

94
00:04:40,250 --> 00:04:42,450
เป็น buzzword สำหรับตอนนี้
และเป็นขั้นตอนนี้

95
00:04:42,450 --> 00:04:47,210
การทำสิ่งใดโดยวัฏจักร
โดยใช้รหัสที่คุณมีอยู่แล้ว

96
00:04:47,210 --> 00:04:49,722
และเรียกมันอีกครั้ง
และอีกครั้งและอีกครั้ง

97
00:04:49,722 --> 00:04:51,930
ตอนนี้ก็จะมีความสำคัญ
ที่เราด้านล่างอย่างใด

98
00:04:51,930 --> 00:04:53,821
ออกและไม่ได้ทำมานานแล้วว่าเพียบ

99
00:04:53,821 --> 00:04:56,070
มิฉะนั้นเรากำลังจะไป
มีแน่นอนวง จำกัด

100
00:04:56,070 --> 00:04:59,810
แต่ขอดูว่าเราสามารถยืมความคิดนี้
เรียกซ้ำของการทำอะไรบางอย่างอีกครั้ง

101
00:04:59,810 --> 00:05:03,600
และอีกครั้งและอีกครั้งที่จะแก้ปัญหา
ปัญหาที่เกิดขึ้นผ่านทางผสานการเรียงลำดับ

102
00:05:03,600 --> 00:05:05,900
เรียงลำดับทั้งหมดที่มีประสิทธิภาพมากขึ้น

103
00:05:05,900 --> 00:05:06,970
>> ดังนั้นผมจึงให้คุณผสานการเรียงลำดับ

104
00:05:06,970 --> 00:05:07,920
ลองมาดู

105
00:05:07,920 --> 00:05:10,850
ดังนั้นนี่คือรหัสจำลองด้วย
ซึ่งเราสามารถใช้การเรียงลำดับ

106
00:05:10,850 --> 00:05:12,640
โดยใช้วิธีที่เรียกว่าการจัดเรียงผสาน

107
00:05:12,640 --> 00:05:13,880
และมันก็เป็นมากเพียงนี้

108
00:05:13,880 --> 00:05:15,940
กับการป้อนข้อมูลขององค์ประกอบ n,
ในคำอื่น ๆ ถ้าคุณ

109
00:05:15,940 --> 00:05:18,830
รับ n องค์ประกอบและตัวเลขและ
จดหมายหรือสิ่งที่นำเข้าคือ

110
00:05:18,830 --> 00:05:22,430
ถ้าคุณได้รับองค์ประกอบ n ถ้า
n คือน้อยกว่า 2 ผลตอบแทนเ​​พียง

111
00:05:22,430 --> 00:05:22,930
ใช่มั้ย?

112
00:05:22,930 --> 00:05:26,430
เพราะถ้า n เป็นน้อยกว่า 2 ที่
หมายความว่ารายชื่อขององค์ประกอบของฉัน

113
00:05:26,430 --> 00:05:30,446
มีทั้งขนาด 0 หรือ 1 และ
ในทั้งสองกรณีที่น่ารำคาญเหล่านั้น

114
00:05:30,446 --> 00:05:31,570
รายการจะถูกจัดเรียงอยู่แล้ว

115
00:05:31,570 --> 00:05:32,810
หากมีรายชื่อไม่ก็เรียง

116
00:05:32,810 --> 00:05:35,185
และถ้ามีรายชื่อของความยาว
1 ก็เรียงอย่างเห็นได้ชัด

117
00:05:35,185 --> 00:05:38,280
ดังนั้นขั้นตอนวิธีเพียงต้องการที่จะ
จริงๆทำอะไรบางอย่างที่น่าสนใจ

118
00:05:38,280 --> 00:05:40,870
ถ้าเรามีสองคนหรือมากกว่า
องค์ประกอบให้กับเรา

119
00:05:40,870 --> 00:05:42,440
ดังนั้นให้ดูที่วิเศษแล้ว

120
00:05:42,440 --> 00:05:47,500
เรียงลำดับอื่นครึ่งซ้ายขององค์ประกอบ
แล้วเรียงครึ่งขวาขององค์ประกอบ

121
00:05:47,500 --> 00:05:49,640
รวมแล้วครึ่งเรียง

122
00:05:49,640 --> 00:05:52,440
และสิ่งที่ชนิดของใจดัด
ที่นี่เป็นที่ฉันทำไม่ได้จริงๆ

123
00:05:52,440 --> 00:05:56,190
ดูเหมือนจะได้บอกคุณ
อะไรเพียง แต่ใช่มั้ย?

124
00:05:56,190 --> 00:05:59,560
ทั้งหมดที่ฉันได้กล่าวว่าจะได้รับรายชื่อของ
n องค์ประกอบเรียงลำดับครึ่งซ้าย

125
00:05:59,560 --> 00:06:01,800
แล้วครึ่งขวาแล้ว
รวมครึ่งเรียงที่

126
00:06:01,800 --> 00:06:03,840
แต่ที่เป็นซอสลับที่เกิดขึ้นจริง?

127
00:06:03,840 --> 00:06:05,260
ที่ไหนขั้นตอนวิธีการคืออะไร?

128
00:06:05,260 --> 00:06:09,150
ดีปรากฎว่าทั้งสองเส้น
ครั้งแรกครึ่งหนึ่งที่เหลือการเรียงลำดับขององค์ประกอบ

129
00:06:09,150 --> 00:06:13,970
และจัดเรียงทางขวาครึ่งหนึ่งขององค์ประกอบ
สาย recursive เพื่อที่จะพูด

130
00:06:13,970 --> 00:06:16,120
>> หลังจากที่ทุกคนที่นี้
จุดในเวลาที่ฉันต้อง

131
00:06:16,120 --> 00:06:18,950
อัลกอริทึมที่ไปยัง
เรียงลำดับทั้งกลุ่มขององค์ประกอบ?

132
00:06:18,950 --> 00:06:19,450
ใช่

133
00:06:19,450 --> 00:06:20,620
มันอยู่ที่นี่

134
00:06:20,620 --> 00:06:25,180
มันอยู่ที่นี่ในหน้าจอและ
เพื่อให้สามารถใช้ชุดเดียวกับขั้นตอน

135
00:06:25,180 --> 00:06:28,500
การจัดเรียงครึ่งซ้าย
เท่าที่จะทำได้ครึ่งหนึ่งที่เหมาะสม

136
00:06:28,500 --> 00:06:30,420
และแน่นอนอีกครั้งและอีกครั้ง

137
00:06:30,420 --> 00:06:34,210
ดังนั้นอย่างใดหรืออื่น ๆ และเราจะเร็ว ๆ นี้
เห็นนี้ความมหัศจรรย์ของการเรียงลำดับการผสาน

138
00:06:34,210 --> 00:06:37,967
ถูกฝังอยู่ในที่สุดท้ายมาก
สายการรวมครึ่งเรียง

139
00:06:37,967 --> 00:06:39,300
และที่ดูเหมือนว่าค่อนข้างใช้งานง่าย

140
00:06:39,300 --> 00:06:41,050
คุณจะใช้สองส่วนและคุณ
อย่างใดรวมเข้าด้วยกัน

141
00:06:41,050 --> 00:06:43,260
และเราจะเห็นนี้
เป็นรูปธรรมในช่วงเวลาที่

142
00:06:43,260 --> 00:06:45,080
>> แต่นี้เป็นขั้นตอนวิธีการที่สมบูรณ์แบบ

143
00:06:45,080 --> 00:06:46,640
และเรามาดูกันว่าทำไม

144
00:06:46,640 --> 00:06:50,912
ดีสมมติว่าเรากำลังได้รับเหล่านี้เหมือนกัน
แปดองค์ประกอบที่นี่บนหน้าจอหนึ่ง

145
00:06:50,912 --> 00:06:53,120
ถึงแปด แต่พวกเขากำลัง
เพื่อสุ่ม

146
00:06:53,120 --> 00:06:55,320
และเป้าหมายที่อยู่ในมือคือ
การจัดเรียงองค์ประกอบเหล่านี้

147
00:06:55,320 --> 00:06:58,280
ดีฉันจะไปเกี่ยวกับ
ทำมันใช้อีกครั้ง

148
00:06:58,280 --> 00:07:00,407
ผสานเรียงลำดับตาม pseudocode นี้หรือไม่?

149
00:07:00,407 --> 00:07:02,740
และอีกครั้งในนี้ติดตัว
ใจของคุณเพื่อรอสักครู่

150
00:07:02,740 --> 00:07:05,270
กรณีแรกสวย
เล็ก ๆ น้อย ๆ ถ้ามันน้อยกว่า 2,

151
00:07:05,270 --> 00:07:07,060
เพียงแค่กลับมามีงานที่จะทำไม่มี

152
00:07:07,060 --> 00:07:09,290
ดังนั้นจริงๆมีเพียงสาม
ขั้นตอนจริงๆที่จะเก็บไว้ในใจ

153
00:07:09,290 --> 00:07:11,081
อีกครั้งและอีกครั้งผม
จะต้องการที่จะมี

154
00:07:11,081 --> 00:07:13,980
การจัดเรียงครึ่งซ้าย
เรียงลำดับครึ่งขวา

155
00:07:13,980 --> 00:07:15,890
และครั้งเดียวของพวกเขาแล้ว
ทั้งสองส่วนมีการเรียงลำดับ

156
00:07:15,890 --> 00:07:18,710
ฉันต้องการที่จะผสานเข้าด้วยกัน
เข้าไปในรายการที่เรียงลำดับหนึ่ง

157
00:07:18,710 --> 00:07:19,940
ดังนั้นเก็บที่ในใจ

158
00:07:19,940 --> 00:07:21,310
>> ดังนั้นนี่คือรายการเดิม

159
00:07:21,310 --> 00:07:23,510
ขอรักษานี้เป็น
อาร์เรย์ที่เราเริ่มที่จะ

160
00:07:23,510 --> 00:07:25,800
ในสัปดาห์ที่สองซึ่งเป็น
บล็อกติดกันของหน่วยความจำ

161
00:07:25,800 --> 00:07:28,480
ในกรณีนี้มีแปด
ตัวเลขกลับไปกลับไปกลับ

162
00:07:28,480 --> 00:07:30,700
และให้นำไปใช้ในขณะนี้การจัดเรียงผสาน

163
00:07:30,700 --> 00:07:33,300
ดังนั้นครั้งแรกที่ผมต้องการเรียงลำดับ
ครึ่งทางด้านซ้ายของรายการนี​​้

164
00:07:33,300 --> 00:07:37,370
และขอดังนั้น
มุ่งเน้นไปที่ 4, 8, 6, และ 2

165
00:07:37,370 --> 00:07:41,000
>> ตอนนี้ฉันจะไปเกี่ยวกับ
การเรียงลำดับรายการขนาด 4 หรือไม่?

166
00:07:41,000 --> 00:07:45,990
ดีฉันจะต้องพิจารณาในขณะนี้
เรียงลำดับทางด้านซ้ายของครึ่งซ้าย

167
00:07:45,990 --> 00:07:47,720
อีกครั้งขอย้อนกลับเพื่อรอสักครู่

168
00:07:47,720 --> 00:07:51,010
ถ้าเป็น pseudocode นี้
และฉันได้รับแปดองค์ประกอบ

169
00:07:51,010 --> 00:07:53,230
8 มากขึ้นอย่างเห็นได้ชัดคือ
มากกว่าหรือเท่ากับ 2

170
00:07:53,230 --> 00:07:54,980
ดังนั้นด้วยกรณีแรกใช้ไม่ได้

171
00:07:54,980 --> 00:07:58,120
ดังนั้นในการจัดเรียงแปดองค์ประกอบแรกที่ผม
เรียงลำดับครึ่งซ้ายขององค์ประกอบ

172
00:07:58,120 --> 00:08:01,930
แล้วผมเรียงลำดับครึ่งขวาแล้วผมผสาน
ทั้งสองส่วนที่เรียงลำดับแต่ละขนาด 4

173
00:08:01,930 --> 00:08:02,470
ตกลง.

174
00:08:02,470 --> 00:08:07,480
>> แต่ถ้าคุณได้เพียงแค่บอกผมว่าเรียงลำดับ
ซีกซ้ายซึ่งขณะนี้มีขนาด 4

175
00:08:07,480 --> 00:08:09,350
ฉันจะเรียงลำดับครึ่งซ้าย?

176
00:08:09,350 --> 00:08:11,430
ดีถ้าฉันมี
ป้อนข้อมูลของธาตุทั้งสี่

177
00:08:11,430 --> 00:08:14,590
ครั้งแรกที่ผมเรียงลำดับซ้าย
สองแล้วขวาสอง

178
00:08:14,590 --> 00:08:16,210
และจากนั้นผมผสานเข้าด้วยกัน

179
00:08:16,210 --> 00:08:18,700
ดังนั้นอีกครั้งมันจะกลายเป็นบิต
ของจิตใจดัดเกมที่นี่

180
00:08:18,700 --> 00:08:21,450
เพราะคุณชนิดของต้อง
จำได้ว่าคุณจะอยู่ที่ไหนในเรื่อง

181
00:08:21,450 --> 00:08:23,620
แต่ในตอนท้ายของวัน
กำหนดจำนวนขององค์ประกอบใด ๆ

182
00:08:23,620 --> 00:08:25,620
ก่อนอื่นคุณต้องการที่จะเรียงลำดับ
ครึ่งซ้ายแล้วครึ่งขวา

183
00:08:25,620 --> 00:08:26,661
แล้วผสานเข้าด้วยกัน

184
00:08:26,661 --> 00:08:28,630
ขอเริ่มต้นที่จะทำตรงนั้น

185
00:08:28,630 --> 00:08:30,170
นี่คือการป้อนข้อมูลของแปดองค์ประกอบ

186
00:08:30,170 --> 00:08:31,910
ตอนนี้เรากำลังมองหาที่ซีกซ้ายที่นี่

187
00:08:31,910 --> 00:08:33,720
ฉันจะเรียงลำดับธาตุทั้งสี่ได้อย่างไร?

188
00:08:33,720 --> 00:08:35,610
ดีครั้งแรกที่ผมเรียงลำดับครึ่งซ้าย

189
00:08:35,610 --> 00:08:37,720
ตอนนี้ฉันจะเรียงลำดับครึ่งซ้าย?

190
00:08:37,720 --> 00:08:39,419
ดีฉันได้รับสององค์ประกอบ

191
00:08:39,419 --> 00:08:41,240
ดังนั้นขอเรียงลำดับทั้งสององค์ประกอบ

192
00:08:41,240 --> 00:08:44,540
2 มากกว่าหรือ
เท่ากับ 2 ของหลักสูตร

193
00:08:44,540 --> 00:08:46,170
ดังนั้นกรณีแรกที่ใช้ไม่ได้

194
00:08:46,170 --> 00:08:49,010
>> ดังนั้นตอนนี้ผมมีการจัดเรียงซ้าย
ครึ่งหนึ่งของทั้งสององค์ประกอบ

195
00:08:49,010 --> 00:08:50,870
ครึ่งซ้ายของหลักสูตรเพียง 4

196
00:08:50,870 --> 00:08:54,020
ดังนั้นฉันจะเรียงลำดับรายชื่อขององค์ประกอบหนึ่งหรือไม่?

197
00:08:54,020 --> 00:08:57,960
ดีตอนนี้ที่ฐานกรณีพิเศษ
ขึ้นด้านบนเพื่อที่จะพูด, มีผลบังคับใช้

198
00:08:57,960 --> 00:09:01,470
1 น้อยกว่า 2 และของฉัน
ย่อมเป็นรายการที่มีขนาด 1

199
00:09:01,470 --> 00:09:02,747
ดังนั้นฉันเพิ่งกลับมา

200
00:09:02,747 --> 00:09:03,580
ฉันไม่ได้ทำอะไร

201
00:09:03,580 --> 00:09:06,770
และแน่นอนมองสิ่งที่ฉันได้
ทำ 4 จะถูกจัดเรียงอยู่แล้ว

202
00:09:06,770 --> 00:09:09,220
เหมือนฉันแล้ว
ที่ประสบความสำเร็จบางส่วนที่นี่

203
00:09:09,220 --> 00:09:11,750
>> ตอนนี้ที่ดูเหมือนว่าชนิดของโง่
ที่จะเรียกร้อง แต่มันเป็นความจริง

204
00:09:11,750 --> 00:09:13,700
4 เป็นรายการขนาด 1

205
00:09:13,700 --> 00:09:15,090
มันเรียงแล้ว

206
00:09:15,090 --> 00:09:16,270
นั่นเป็นครึ่งซ้าย

207
00:09:16,270 --> 00:09:18,010
ตอนนี้ผมเรียงลำดับครึ่งหนึ่งที่เหมาะสม

208
00:09:18,010 --> 00:09:22,310
การป้อนข้อมูลของฉันเป็นหนึ่งในองค์ประกอบที่ 8
ในทำนองเดียวกันเรียงแล้ว

209
00:09:22,310 --> 00:09:25,170
โง่เกินไป แต่อีกครั้ง
หลักการพื้นฐานนี้

210
00:09:25,170 --> 00:09:28,310
เป็นไปเพื่อช่วยให้เราสามารถสร้างตอนนี้
ด้านบนของนี้ประสบความสำเร็จ

211
00:09:28,310 --> 00:09:32,260
เรียง 4, 8 เรียงตอนนี้
สิ่งที่เป็นขั้นตอนสุดท้ายที่?

212
00:09:32,260 --> 00:09:35,330
ดังนั้นขั้นตอนที่สามและครั้งสุดท้ายใด ๆ
เวลาที่คุณกำลังเรียงลำดับรายการการเรียกคืน

213
00:09:35,330 --> 00:09:38,310
คือการผสานสองครึ่ง
ด้านซ้ายและด้านขวา

214
00:09:38,310 --> 00:09:39,900
ดังนั้นเรามาทำตรงนั้น

215
00:09:39,900 --> 00:09:41,940
ครึ่งซ้ายของฉันคือของหลักสูตร 4

216
00:09:41,940 --> 00:09:43,310
ครึ่งขวาของฉันคือ 8

217
00:09:43,310 --> 00:09:44,100
>> ถ้าอย่างนั้นเราทำเช่นนี้

218
00:09:44,100 --> 00:09:46,410
ครั้งแรกที่ฉันกำลังจะไปจัดสรร
บางหน่วยความจำเพิ่มเติม

219
00:09:46,410 --> 00:09:48,680
ที่ฉันจะได้เป็นตัวแทนของที่นี่
เช่นเดียวกับอาร์เรย์รอง

220
00:09:48,680 --> 00:09:49,660
ที่มีขนาดใหญ่พอที่จะใส่นี้

221
00:09:49,660 --> 00:09:52,243
แต่คุณสามารถจินตนาการขยาย
ที่สี่เหลี่ยมความยาวทั้งหมด

222
00:09:52,243 --> 00:09:53,290
ถ้าเราต้องการเพิ่มเติมในภายหลัง

223
00:09:53,290 --> 00:09:58,440
ผมใช้เวลา 4 และ 8 วิธีและผสาน
ทั้งสองรายการที่มีขนาด 1 ด้วยกันไหม?

224
00:09:58,440 --> 00:10:00,270
นี่เกินไปง่ายสวย

225
00:10:00,270 --> 00:10:03,300
4 มาก่อนแล้วก็มาถึง 8

226
00:10:03,300 --> 00:10:07,130
เพราะถ้าผมต้องการที่จะเรียงลำดับ
ครึ่งซ้ายแล้วครึ่งขวา

227
00:10:07,130 --> 00:10:09,900
แล้วรวมทั้งสองส่วน
ร่วมกันในการเรียงลำดับ

228
00:10:09,900 --> 00:10:11,940
4 มาก่อนแล้วก็มาถึง 8

229
00:10:11,940 --> 00:10:15,810
>> ดังนั้นเราจึงดูเหมือนจะทำให้ความคืบหน้าแม้
แต่ผมยังไม่ได้ทำงานจริงใด ๆ

230
00:10:15,810 --> 00:10:17,800
แต่อย่าลืมว่าเราอยู่ที่ไหนในเรื่อง

231
00:10:17,800 --> 00:10:19,360
เราเดิมเอาแปดองค์ประกอบ

232
00:10:19,360 --> 00:10:21,480
เราเรียงครึ่งซ้ายซึ่งเป็น 4

233
00:10:21,480 --> 00:10:24,450
จากนั้นเราก็เรียงครึ่งซ้าย
ครึ่งซ้ายซึ่งเป็น 2

234
00:10:24,450 --> 00:10:25,270
และที่นี่เราไป

235
00:10:25,270 --> 00:10:26,920
เรากำลังทำตามขั้นตอนที่ว่า

236
00:10:26,920 --> 00:10:29,930
>> ดังนั้นหากเราได้เรียง
ครึ่งซ้ายของ 2, ตอนนี้เรา

237
00:10:29,930 --> 00:10:32,130
ต้องจัดเรียงครึ่งขวา 2

238
00:10:32,130 --> 00:10:35,710
ดังนั้นในช่วงครึ่งขวาของ 2
ทั้งสองค่าที่นี่, 6 และ 2

239
00:10:35,710 --> 00:10:40,620
ดังนั้นตอนนี้ให้มาใส่ของขนาด
2 และเรียงลำดับครึ่งซ้ายแล้ว

240
00:10:40,620 --> 00:10:42,610
ครึ่งขวาแล้ว
ผสานเข้าด้วยกัน

241
00:10:42,610 --> 00:10:45,722
ดีฉันจะเรียงลำดับรายการที่มีขนาด
1, ที่มีเพียงหมายเลข 6 ได้หรือไม่?

242
00:10:45,722 --> 00:10:46,430
ฉันทำมาแล้ว

243
00:10:46,430 --> 00:10:48,680
รายการที่มีขนาด 1 ที่จะถูกจัดเรียง

244
00:10:48,680 --> 00:10:52,140
>> ฉันไม่เรียงลำดับรายชื่อของผู้อื่นอย่างไร
ขนาด 1 ครึ่งขวาที่เรียกว่า

245
00:10:52,140 --> 00:10:54,690
ดีมันมากเกินไปจะถูกจัดเรียงอยู่แล้ว

246
00:10:54,690 --> 00:10:56,190
หมายเลข 2 คือคนเดียว

247
00:10:56,190 --> 00:11:00,160
ดังนั้นตอนนี้ฉันมีสองส่วนซ้ายและ
ขวาฉันต้องผสานเข้าด้วยกัน

248
00:11:00,160 --> 00:11:01,800
ผมขอให้ตัวเองบางพื้นที่พิเศษ

249
00:11:01,800 --> 00:11:05,580
และใส่ 2 ในนั้น
แล้ว 6 ในนั้นจึง

250
00:11:05,580 --> 00:11:10,740
การเรียงลำดับรายการที่ซ้ายและขวา
และการรวมกันในที่สุด

251
00:11:10,740 --> 00:11:12,160
ดังนั้นผมอยู่ในรูปร่างที่ดีขึ้นเล็กน้อย

252
00:11:12,160 --> 00:11:16,250
ฉันไม่ได้ทำเพราะอย่างชัดเจน 4, 8, 2,
6 ไม่ได้สั่งซื้อสุดท้ายที่ฉันต้องการ

253
00:11:16,250 --> 00:11:20,640
แต่ตอนนี้ผมมีสองรายการที่มีขนาด 2 ที่
ทั้งสองตามลำดับการเรียง

254
00:11:20,640 --> 00:11:24,580
ดังนั้นถ้าคุณย้อนกลับในใจของคุณ
ตาที่ไม่ว่าปล่อยให้เรา?

255
00:11:24,580 --> 00:11:28,520
ฉันเริ่มต้นด้วยแปดองค์ประกอบแล้วฉัน
เหลาลงไปครึ่งซ้ายของ 4

256
00:11:28,520 --> 00:11:31,386
แล้วครึ่งทางด้านซ้ายของ 2
แล้วครึ่งขวาของ 2,

257
00:11:31,386 --> 00:11:34,510
ฉันเสร็จแล้วจึงเรียงลำดับซ้าย
ครึ่งหนึ่งของที่ 2 และครึ่งขวาของ 2,

258
00:11:34,510 --> 00:11:37,800
ดังนั้นสิ่งที่เป็นขั้นตอนที่สามและครั้งสุดท้ายที่นี่?

259
00:11:37,800 --> 00:11:41,290
ฉันต้องรวมกัน
สองรายการที่มีขนาด 2

260
00:11:41,290 --> 00:11:42,040
ถ้าอย่างนั้นเราไปข้างหน้า

261
00:11:42,040 --> 00:11:43,940
และบนหน้าจอที่นี่ให้
ฉันบางหน่วยความจำเพิ่มเติม

262
00:11:43,940 --> 00:11:47,170
แม้ว่าในทางเทคนิคสังเกตเห็นว่าฉันได้
มีทั้งกลุ่มของช่องว่างขึ้นด้านบน

263
00:11:47,170 --> 00:11:47,670
ที่นั่น

264
00:11:47,670 --> 00:11:50,044
ถ้าผมต้องการที่จะเป็นโดยเฉพาะอย่างยิ่ง
พื้นที่ที่มีประสิทธิภาพที่ชาญฉลาด

265
00:11:50,044 --> 00:11:52,960
ฉันจะเริ่มต้นการย้ายองค์ประกอบ
ไปมาบนและด้านล่าง

266
00:11:52,960 --> 00:11:55,460
แต่เพื่อความชัดเจนภาพ
ฉันจะวางมันลงด้านล่าง

267
00:11:55,460 --> 00:11:56,800
เพื่อให้สิ่งที่ดีและสะอาด

268
00:11:56,800 --> 00:11:58,150
>> ดังนั้นผมจึงได้มีสองรายการที่มีขนาด 2

269
00:11:58,150 --> 00:11:59,770
รายการแรกมี 4 และ 8

270
00:11:59,770 --> 00:12:01,500
รายการที่สองมี 2 และ 6

271
00:12:01,500 --> 00:12:03,950
ลองผสานเหล่านั้น
ร่วมกันในการเรียงลำดับ

272
00:12:03,950 --> 00:12:09,910
2 ของหลักสูตรมาก่อน
แล้ว 4 แล้ว 6 จากนั้น 8

273
00:12:09,910 --> 00:12:12,560
และตอนนี้เราดูเหมือนจะได้รับ
ที่ไหนสักแห่งที่น่าสนใจ

274
00:12:12,560 --> 00:12:15,720
ตอนนี้ผมได้เรียงครึ่งหนึ่งของ
รายการและบังเอิญมัน

275
00:12:15,720 --> 00:12:18,650
ทั้งหมดแม้ตัวเลข แต่ที่
เป็นจริงเพียงแค่เรื่องบังเอิญ

276
00:12:18,650 --> 00:12:22,220
และตอนนี้ผมได้เรียงซ้าย
ครึ่งหนึ่งเพื่อที่จะเป็น 2, 4, 6, และ 8

277
00:12:22,220 --> 00:12:23,430
ไม่มีอะไรออกมาของการสั่งซื้อ

278
00:12:23,430 --> 00:12:24,620
ที่รู้สึกเหมือนความคืบหน้า

279
00:12:24,620 --> 00:12:26,650
>> ตอนนี้มันรู้สึกเหมือนฉัน
รับการพูดคุยตลอดไปตอนนี้

280
00:12:26,650 --> 00:12:29,850
ดังนั้นสิ่งที่คงที่จะเห็นว่านี้
อัลกอริทึมเป็นจริงมีประสิทธิภาพมากขึ้น

281
00:12:29,850 --> 00:12:31,766
แต่เรากำลังจะผ่าน
มันสุดยอดระบบ

282
00:12:31,766 --> 00:12:34,060
คอมพิวเตอร์ของหลักสูตร
จะทำเช่นนั้น

283
00:12:34,060 --> 00:12:34,840
เพื่อที่เรามีอะไรบ้าง

284
00:12:34,840 --> 00:12:36,180
เราเริ่มต้นด้วยแปดองค์ประกอบ

285
00:12:36,180 --> 00:12:37,840
ผมเรียงครึ่งซ้ายของ 4

286
00:12:37,840 --> 00:12:39,290
ฉันดูเหมือนจะทำได้ด้วยการที่

287
00:12:39,290 --> 00:12:42,535
ดังนั้นตอนนี้ขั้นตอนต่อไปคือการ
เรียงลำดับครึ่งขวา 4

288
00:12:42,535 --> 00:12:44,410
และส่วนนี้เราสามารถไป
ผ่านน้อยมาก

289
00:12:44,410 --> 00:12:47,140
ได้อย่างรวดเร็วถึงแม้ว่าคุณ
ยินดีที่จะย้อนกลับหรือหยุดเพียง

290
00:12:47,140 --> 00:12:49,910
คิดว่าผ่านได้ที่
ก้าวของคุณเอง แต่สิ่งที่

291
00:12:49,910 --> 00:12:53,290
เรามีตอนนี้เป็นโอกาสให้กับ
ขั้นตอนวิธีการทำเดียวกันแน่นอนสี่

292
00:12:53,290 --> 00:12:54,380
ตัวเลขที่แตกต่าง

293
00:12:54,380 --> 00:12:57,740
>> ถ้าอย่างนั้นเราไปข้างหน้าและมุ่งเน้นไปที่
ครึ่งขวาซึ่งเราอยู่ที่นี่

294
00:12:57,740 --> 00:13:01,260
ครึ่งที่ด้านซ้ายของ
ครึ่งขวาและตอนนี้

295
00:13:01,260 --> 00:13:04,560
ครึ่งซ้ายของด้านซ้าย
ครึ่งหนึ่งของครึ่งที่เหมาะสมนั้น

296
00:13:04,560 --> 00:13:08,030
และฉันจะเรียงลำดับรายการที่มีขนาด
1 ที่มีเพียงหมายเลข 1?

297
00:13:08,030 --> 00:13:09,030
มันทำมาแล้ว

298
00:13:09,030 --> 00:13:11,830
ฉันจะทำเช่นเดียวกันสำหรับรายการ
ขนาด 1 ที่มีเพียง 7?

299
00:13:11,830 --> 00:13:12,840
มันทำมาแล้ว

300
00:13:12,840 --> 00:13:16,790
ขั้นตอนที่สามสำหรับครึ่งนี้แล้ว
คือการที่จะรวมทั้งสององค์ประกอบ

301
00:13:16,790 --> 00:13:20,889
เป็นรายการใหม่ของขนาด 2, 1 และ 7

302
00:13:20,889 --> 00:13:23,180
ดูเหมือนจะไม่ได้ทำทุก
งานที่น่าสนใจมาก

303
00:13:23,180 --> 00:13:24,346
ลองดูสิ่งที่เกิดขึ้นต่อไป

304
00:13:24,346 --> 00:13:29,210
ฉันเพียงแค่เรียงครึ่งซ้ายของ
ครึ่งขวาของการป้อนข้อมูลเดิมของฉัน

305
00:13:29,210 --> 00:13:32,360
ตอนนี้ขอเรียงลำดับที่ถูกต้อง
ครึ่งหนึ่งซึ่งมี 5 และ 3

306
00:13:32,360 --> 00:13:35,740
ลองมาดูอีกครั้งด้านซ้าย
ครึ่งเรียงครึ่งขวาเรียงลำดับ

307
00:13:35,740 --> 00:13:39,120
และรวมทั้งสองเข้าด้วยกัน
ในบางส่วนพื้นที่เพิ่มเติม

308
00:13:39,120 --> 00:13:41,670
3 มาก่อนแล้วก็มาถึง 5

309
00:13:41,670 --> 00:13:46,190
ดังนั้นตอนนี้เราได้เรียง
ครึ่งซ้ายของครึ่งที่เหมาะสม

310
00:13:46,190 --> 00:13:49,420
ของปัญหาเดิมและ
ครึ่งขวาของครึ่งปีที่ที่เหมาะสม

311
00:13:49,420 --> 00:13:50,800
ของปัญหาเดิม

312
00:13:50,800 --> 00:13:52,480
ขั้นตอนที่สามและครั้งสุดท้ายคืออะไร?

313
00:13:52,480 --> 00:13:54,854
ดีที่จะรวมทั้งสองส่วนเข้าด้วยกัน

314
00:13:54,854 --> 00:13:57,020
เพื่อให้ฉันได้รับตัวเองบางส่วน
พื้นที่พิเศษ แต่อีกครั้งฉัน

315
00:13:57,020 --> 00:13:58,699
อาจจะใช้พื้นที่ว่างขึ้นด้านบน

316
00:13:58,699 --> 00:14:00,490
แต่เรากำลังจะเก็บ
มันง่ายสายตา

317
00:14:00,490 --> 00:14:07,070
ผมขอรวมในตอนที่ 1 และ
แล้ว 3 แล้ว 5 แล้ว 7

318
00:14:07,070 --> 00:14:10,740
จึงทิ้งฉันตอนนี้มี
ครึ่งขวาของปัญหาเดิม

319
00:14:10,740 --> 00:14:12,840
ที่เรียงได้อย่างสมบูรณ์แบบ

320
00:14:12,840 --> 00:14:13,662
>> ดังนั้นสิ่งที่เหลืออยู่?

321
00:14:13,662 --> 00:14:16,120
ฉันรู้สึกเหมือนฉันให้บอกว่า
สิ่งเดียวกันอีกครั้งและอีกครั้ง

322
00:14:16,120 --> 00:14:18,700
แต่ที่สะท้อนแสงของ
ความจริงที่ว่าเรากำลังใช้เรียกซ้ำ

323
00:14:18,700 --> 00:14:21,050
กระบวนการของการใช้
ขั้นตอนวิธีการอีกครั้งและอีกครั้ง

324
00:14:21,050 --> 00:14:23,940
ในส่วนย่อยขนาดเล็ก
ปัญหาเดิม

325
00:14:23,940 --> 00:14:27,580
ดังนั้นตอนนี้ผมได้เรียงซ้าย
ครึ่งหนึ่งของปัญหาเดิม

326
00:14:27,580 --> 00:14:30,847
ฉันมีครึ่งเรียงที่เหมาะสม
ของปัญหาเดิม

327
00:14:30,847 --> 00:14:32,180
อะไรคือขั้นตอนที่สามและครั้งสุดท้าย?

328
00:14:32,180 --> 00:14:33,590
โอ้มันผสาน

329
00:14:33,590 --> 00:14:34,480
ดังนั้นขอให้ทำอย่างนั้น

330
00:14:34,480 --> 00:14:36,420
ขอจัดสรรเพิ่มเติมบางอย่าง
หน่วยความจำ แต่พระเจ้าของเรา

331
00:14:36,420 --> 00:14:37,503
สามารถใส่ได้ทุกที่ในขณะนี้

332
00:14:37,503 --> 00:14:40,356
เรามีพื้นที่มากจึงมี
ให้เรา แต่เราจะให้มันง่าย

333
00:14:40,356 --> 00:14:42,730
แทนที่จะไปกลับ
มากับหน่วยความจำเดิมของเรา

334
00:14:42,730 --> 00:14:44,480
ขอเพียงแค่ทำมัน
สายตาลงที่นี่ด้านล่าง

335
00:14:44,480 --> 00:14:47,240
ที่จะเสร็จสิ้นการรวม
ซีกซ้ายและอีกครึ่งหนึ่งที่เหมาะสม

336
00:14:47,240 --> 00:14:49,279
>> ดังนั้นโดยการรวมสิ่งที่ฉันต้องทำอย่างไร

337
00:14:49,279 --> 00:14:50,820
ฉันต้องการที่จะใช้องค์ประกอบในการสั่งซื้อ

338
00:14:50,820 --> 00:14:53,230
ดังนั้นมองที่ครึ่งซ้าย
ผมเห็นตัวเลขแรกคือ 2

339
00:14:53,230 --> 00:14:55,230
ฉันมองไปที่ครึ่งขวา
ผมเห็นตัวเลขแรก

340
00:14:55,230 --> 00:14:58,290
1 เพื่อให้ชัดซึ่ง
จำนวนฉันต้องการที่จะถอนออก

341
00:14:58,290 --> 00:15:00,430
และใส่ครั้งแรกในรายการสุดท้ายของฉันได้อย่างไร

342
00:15:00,430 --> 00:15:01,449
แน่นอน 1

343
00:15:01,449 --> 00:15:02,990
ตอนนี้ผมต้องการที่จะถามคำถามเดียวกันว่า

344
00:15:02,990 --> 00:15:05,040
ในครึ่งซ้ายฉัน
ยังคงมีจำนวน 2

345
00:15:05,040 --> 00:15:07,490
ในครึ่งขวา
ฉันมีจำนวน 3

346
00:15:07,490 --> 00:15:08,930
ฉันจะเป็นที่หนึ่งต้องการที่จะเลือก?

347
00:15:08,930 --> 00:15:11,760
แน่นอนจำนวน 2
ตอนนี้สังเกตเห็นผู้สมัคร

348
00:15:11,760 --> 00:15:13,620
4 ด้านซ้าย 3 ด้านขวา

349
00:15:13,620 --> 00:15:15,020
ลองของหลักสูตรให้เลือก 3

350
00:15:15,020 --> 00:15:18,020
ตอนนี้มีผู้สมัคร 4
ซ้าย 5 ด้านขวา

351
00:15:18,020 --> 00:15:19,460
เราแน่นอนให้เลือก 4

352
00:15:19,460 --> 00:15:21,240
6 ด้านซ้าย 5 ด้านขวา

353
00:15:21,240 --> 00:15:22,730
เราแน่นอนให้เลือก 5

354
00:15:22,730 --> 00:15:25,020
6 ด้านซ้าย 7 ด้านขวา

355
00:15:25,020 --> 00:15:29,320
เราเลือก 6 และจากนั้นเรา
เลือก 7 แล้วเราเลือกที่ 8

356
00:15:29,320 --> 00:15:30,100
Voila

357
00:15:30,100 --> 00:15:34,370
>> ดังนั้นจำนวนมากของคำพูดต่อมาเรา
ได้เรียงรายการแปดองค์ประกอบนี้

358
00:15:34,370 --> 00:15:38,450
เข้าไปในรายการหนึ่งถึงแปด
ที่เพิ่มขึ้นกับแต่ละขั้นตอน

359
00:15:38,450 --> 00:15:40,850
แต่วิธีการมากเวลาได้
มันพาเราไปทำอย่างนั้น

360
00:15:40,850 --> 00:15:43,190
ดีฉันได้จงใจ
สิ่งที่ออกมาวาง pictorially

361
00:15:43,190 --> 00:15:46,330
ที่นี่เพื่อให้เราสามารถชนิดของ
เห็นหรือชื่นชมส่วน

362
00:15:46,330 --> 00:15:49,060
ในการชนะที่ได้รับการเกิดขึ้น

363
00:15:49,060 --> 00:15:52,830
>> อันที่จริงถ้าคุณมองย้อนกลับไปที่การปลุก,
ฉันซ้ายทั้งหมดของเส้นประเหล่านี้

364
00:15:52,830 --> 00:15:55,660
ในผู้ถือสถานที่ที่คุณสามารถจะทำได้
ชนิดของการมองเห็นในการสั่งซื้อกลับ

365
00:15:55,660 --> 00:15:58,800
ถ้าคุณชนิดของการมองย้อนกลับไปใน
ประวัติศาสตร์ตอนนี้รายการเดิมของฉัน

366
00:15:58,800 --> 00:16:00,250
เป็นของหลักสูตรที่มีขนาด 8

367
00:16:00,250 --> 00:16:03,480
และจากนั้นก่อนหน้านี้ผมก็
การจัดการกับสองรายการที่มีขนาด 4

368
00:16:03,480 --> 00:16:08,400
และจากนั้นสี่รายการที่มีขนาด 2
แล้วแปดรายการขนาด 1

369
00:16:08,400 --> 00:16:10,151
>> ดังนั้นนี้ไม่ทำอะไร
ชนิดของการเตือนของคุณ?

370
00:16:10,151 --> 00:16:11,858
ดีจริงใด ๆ
ขั้นตอนวิธีการที่เราได้

371
00:16:11,858 --> 00:16:14,430
มองไปที่ป่านนี้ที่เรา
หารและหารและหาร

372
00:16:14,430 --> 00:16:19,500
ให้มีสิ่งอีกครั้งและ
อีกครั้งส่งผลให้ในความคิดทั่วไปนี้

373
00:16:19,500 --> 00:16:23,100
และเพื่อให้มีบางสิ่งบางอย่าง
ลอการิทึมเกิดขึ้นที่นี่

374
00:16:23,100 --> 00:16:26,790
และก็ไม่ได้เข้าสู่ระบบค่อนข้าง n แต่
มีองค์ประกอบลอการิทึม

375
00:16:26,790 --> 00:16:28,280
กับสิ่งที่เราได้ทำเพียงแค่

376
00:16:28,280 --> 00:16:31,570
>> ตอนนี้ขอพิจารณาวิธีการที่เป็นจริง

377
00:16:31,570 --> 00:16:34,481
ดังนั้นการเข้าสู่ระบบของ n อีกครั้งเป็น
เป็นเวลาการทำงานที่ดี

378
00:16:34,481 --> 00:16:36,980
เมื่อเราได้สิ่งที่ต้องการ
การค้นหาแบบไบนารีที่เราตอนนี้เรียกว่า

379
00:16:36,980 --> 00:16:40,090
แบ่งและพิชิตกลยุทธ์
ผ่านทางที่เราพบไมค์สมิ ธ

380
00:16:40,090 --> 00:16:41,020
ตอนนี้ในทางเทคนิค

381
00:16:41,020 --> 00:16:43,640
นั่นเป็นฐานเข้าสู่ระบบที่ 2 ของ n แม้
แต่ในส่วนการเรียนคณิตศาสตร์

382
00:16:43,640 --> 00:16:45,770
10 มักจะเป็นฐานที่คุณสมมติ

383
00:16:45,770 --> 00:16:48,940
แต่นักวิทยาศาสตร์คอมพิวเตอร์เกือบตลอดเวลา
คิดและพูดคุยในแง่ของฐานที่ 2

384
00:16:48,940 --> 00:16:52,569
ดังนั้นโดยทั่วไปเราก็บอกว่าเข้าสู่ระบบของ
n แทนการเข้าสู่ระบบฐานที่ 2 ของ n,

385
00:16:52,569 --> 00:16:55,110
แต่พวกเขากำลังว่าหนึ่งและ
เหมือนกันในโลกของคอมพิวเตอร์

386
00:16:55,110 --> 00:16:57,234
วิทยาศาสตร์และเป็นกัน
มีปัจจัยคง

387
00:16:57,234 --> 00:17:01,070
ความแตกต่างระหว่างทั้งสองจึงเป็น
สงสัยต่อไปด้วยเหตุผลที่เป็นทางการมากขึ้น

388
00:17:01,070 --> 00:17:04,520
>> แต่ตอนนี้สิ่งที่เราสนใจ
เกี่ยวกับการเป็นตัวอย่างนี้

389
00:17:04,520 --> 00:17:08,520
ถ้าอย่างนั้นเราได้พิสูจน์โดยตัวอย่าง แต่ใน
อย่างน้อยใช้ตัวอย่างของตัวเลขที่

390
00:17:08,520 --> 00:17:10,730
ที่อยู่ในมือการตรวจสอบสติถ้าคุณจะ

391
00:17:10,730 --> 00:17:14,510
ก่อนหน้านี้ดังนั้นสูตรเป็นฐานเข้าสู่ระบบ
2 n แต่สิ่งที่เป็น n ในกรณีนี้

392
00:17:14,510 --> 00:17:18,526
ผมมีตัวเลขเดิม n หรือ 8
จำนวนเดิมโดยเฉพาะ

393
00:17:18,526 --> 00:17:20,359
ตอนนี้จะได้รับเพียงเล็กน้อย
ในขณะที่ แต่ฉันรัก

394
00:17:20,359 --> 00:17:25,300
แน่ใจว่าการเข้าสู่ระบบฐาน 2
ของมูลค่า 8 3

395
00:17:25,300 --> 00:17:29,630
และแน่นอนสิ่งที่ดีเกี่ยวกับการที่
ที่ 3 คือว่าจำนวนครั้งที่

396
00:17:29,630 --> 00:17:33,320
ที่คุณสามารถแบ่งรายการ
ความยาว 8 อีกครั้งและอีกครั้ง

397
00:17:33,320 --> 00:17:36,160
และอีกครั้งจนกว่าคุณจะเหลือ
กับรายการที่มีขนาดเพียง 1

398
00:17:36,160 --> 00:17:36,660
ใช่มั้ย?

399
00:17:36,660 --> 00:17:40,790
8 ไป 4 ไป 2
ไปที่ 1 และที่

400
00:17:40,790 --> 00:17:43,470
สะท้อนของว่าที่
ภาพที่เรามีเพียงแค่ช่วงเวลาที่ผ่านมา

401
00:17:43,470 --> 00:17:47,160
ดังนั้นการตรวจสอบสุขภาพจิตดีเล็ก ๆ น้อย ๆ เป็นที่ที่
ลอการิทึมที่มีส่วนเกี่ยวข้องจริง

402
00:17:47,160 --> 00:17:50,180
>> ดังนั้นตอนนี้สิ่งอื่นที่เกี่ยวข้องกับที่นี่? n

403
00:17:50,180 --> 00:17:53,440
แจ้งให้ทราบเพื่อให้ทุก
เวลาที่ฉันแยกรายการ

404
00:17:53,440 --> 00:17:58,260
แม้ว่าในลำดับที่กลับในประวัติศาสตร์
ที่นี่ผมก็ยังคงทำสิ่งที่ n

405
00:17:58,260 --> 00:18:02,320
ขั้นตอนการควบรวมต้องมี
ฉันสัมผัสทุกคนของตัวเลข

406
00:18:02,320 --> 00:18:05,060
เพื่อที่จะเลื่อนลง
ตำแหน่งที่เหมาะสมของ

407
00:18:05,060 --> 00:18:10,760
ดังนั้นแม้ว่าความสูงนี้
แผนภาพเป็น n ล็อกขนาดของ n หรือ 3

408
00:18:10,760 --> 00:18:13,860
โดยเฉพาะในคำอื่น ๆ
ฉันไม่สามฝ่ายที่นี่

409
00:18:13,860 --> 00:18:18,800
วิธีการทำงานมากผมทำในแนวนอน
พร้อมแผนภูมิแต่ละครั้งนี้หรือไม่

410
00:18:18,800 --> 00:18:21,110
>> ดีฉันไม่ได้ทำตามขั้นตอนของ n
ทำงานเพราะถ้าฉันได้

411
00:18:21,110 --> 00:18:24,080
มีธาตุทั้งสี่และสี่องค์ประกอบ
และฉันต้องการที่จะรวมเข้าด้วยกัน

412
00:18:24,080 --> 00:18:26,040
ฉันจะต้องไปผ่าน
สี่เหล่านี้และสิ่งเหล่านี้สี่

413
00:18:26,040 --> 00:18:28,123
ท้ายที่สุดจะผสานพวกเขา
กลับเข้ามาในแปดองค์ประกอบ

414
00:18:28,123 --> 00:18:32,182
ตรงกันข้ามถ้าฉันมีแปดนิ้ว
มากกว่าที่นี่ซึ่งผมไม่ได้และแปด

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- ถ้าฉันได้
มีสี่นิ้วกว่าที่นี่

416
00:18:34,390 --> 00:18:37,380
ซึ่งผมทำสี่นิ้ว
มากกว่าที่นี่ซึ่งผมทำ

417
00:18:37,380 --> 00:18:40,590
แล้วที่เดียวกัน
ตัวอย่างเช่นเมื่อก่อนถ้าผมทำ

418
00:18:40,590 --> 00:18:44,010
มีแปดนิ้วแม้ว่าจะอยู่ใน
ทั้งหมดที่ฉันสามารถชนิดของการทำ

419
00:18:44,010 --> 00:18:47,950
ผมว่าสามารถทำที่นี่
แล้วฉันสามารถอย่างแน่นอน

420
00:18:47,950 --> 00:18:50,370
รวมทั้งหมดของรายการเหล่านี้
ขนาด 1 ร่วมกัน

421
00:18:50,370 --> 00:18:54,050
แต่แน่นอนฉันต้องมอง
ที่แต่ละองค์ประกอบครั้งว่า

422
00:18:54,050 --> 00:18:59,640
ดังนั้นความสูงของกระบวนการนี​​้คือ n บันทึก
ความกว้างของขั้นตอนนี้เพื่อที่จะพูด

423
00:18:59,640 --> 00:19:02,490
เป็น n ดังนั้นสิ่งที่เราดูเหมือน
ที่จะมีในที่สุดคือ

424
00:19:02,490 --> 00:19:06,470
เป็นเวลาการทำงานของขนาด n log n ครั้ง

425
00:19:06,470 --> 00:19:08,977
>> ในคำอื่น ๆ ที่เราแบ่งออก
รายการบันทึก n ครั้ง

426
00:19:08,977 --> 00:19:11,810
แต่ทุกครั้งที่เราทำที่เรามี
สัมผัสทุกหนึ่งในองค์ประกอบ

427
00:19:11,810 --> 00:19:13,560
เพื่อที่จะตัดพวกเขา
ทั้งหมดเข้าด้วยกันซึ่ง

428
00:19:13,560 --> 00:19:18,120
ถูก n ขั้นตอนเพื่อให้เรามีเวลา n log n,
หรือเป็นนักวิทยาศาสตร์คอมพิวเตอร์จะพูดว่า

429
00:19:18,120 --> 00:19:20,380
asymptotically ซ​​ึ่ง
จะเป็นคำที่ยิ่งใหญ่

430
00:19:20,380 --> 00:19:22,810
เพื่ออธิบายบน
ผูกพันในเวลาทำงาน,

431
00:19:22,810 --> 00:19:28,010
เรากำลังทำงานในขนาดใหญ่ o
ของบันทึก n เวลาเพื่อที่จะพูด

432
00:19:28,010 --> 00:19:31,510
>> ตอนนี้มีความสำคัญเพราะ
จำสิ่งที่เวลาทำงานได้

433
00:19:31,510 --> 00:19:34,120
มีการจัดเรียงฟองและการเลือก
เรียงลำดับและการจัดเรียงแทรก

434
00:19:34,120 --> 00:19:38,200
และแม้กระทั่งไม่กี่คนอื่น ๆ ที่มีอยู่
n squared คือที่ที่เราอยู่ที่

435
00:19:38,200 --> 00:19:39,990
และคุณสามารถชนิดของโปรดดูที่นี่

436
00:19:39,990 --> 00:19:45,720
ถ้า n ยกกำลังสองจะเห็นได้ชัด n ครั้ง
n แต่ที่นี่เรามีครั้ง n log n,

437
00:19:45,720 --> 00:19:48,770
และเรารู้อยู่แล้วว่าจากสัปดาห์
ศูนย์ n บันทึกที่ลอการิทึมที่

438
00:19:48,770 --> 00:19:50,550
จะดีกว่าการเชิงเส้นบางสิ่งบางอย่าง

439
00:19:50,550 --> 00:19:52,930
หลังจากที่ทุกคนจำภาพ
ที่มีสีแดงและสีเหลือง

440
00:19:52,930 --> 00:19:56,500
และสายสีเขียวที่เราเข้ามาที่
สายสีเขียวลอการิทึมเป็นที่ต่ำกว่ามาก

441
00:19:56,500 --> 00:20:00,920
และดังนั้นจึงดีมากขึ้นและเร็วขึ้น
กว่าเส้นเหลืองและสีแดงตรง

442
00:20:00,920 --> 00:20:05,900
ครั้ง n log n มีจริงดีกว่า
กว่าครั้ง n n หรือ n ยกกำลังสอง

443
00:20:05,900 --> 00:20:09,110
>> ดังนั้นเราจึงดูเหมือนจะมี
ระบุผสานอัลกอริทึม

444
00:20:09,110 --> 00:20:11,870
การจัดเรียงที่ทำงานในมาก
เวลาที่เร็วกว่าและแน่นอน

445
00:20:11,870 --> 00:20:16,560
นั่นคือเหตุผลที่สัปดาห์ก่อนหน้านี้เมื่อ
เราเห็นการแข่งขันระหว่างฟองที่

446
00:20:16,560 --> 00:20:20,750
การเรียงลำดับเรียงลำดับการเลือกและผสาน
เรียงลำดับผสานเรียงจริงๆได้รับรางวัลจริงๆ

447
00:20:20,750 --> 00:20:23,660
และแน่นอนเราไม่ได้รอ
สำหรับการจัดเรียงฟองและการเรียงลำดับการเลือก

448
00:20:23,660 --> 00:20:24,790
จะเสร็จสิ้น

449
00:20:24,790 --> 00:20:27,410
>> ตอนนี้ขอใช้เวลาหนึ่งผ่านอื่น ๆ
นี้จากเล็กน้อย

450
00:20:27,410 --> 00:20:31,030
มุมมองอย่างเป็นทางการใน
กรณีนี้สะท้อนที่ดีขึ้น

451
00:20:31,030 --> 00:20:33,380
กว่าการอภิปรายระดับที่สูงขึ้น

452
00:20:33,380 --> 00:20:34,880
ดังนั้นนี่คือขั้นตอนวิธีการอีกครั้ง

453
00:20:34,880 --> 00:20:36,770
ลองถามตัวเอง
สิ่งที่เวลาทำงาน

454
00:20:36,770 --> 00:20:39,287
เป็นขั้นตอนนี้ขั้นตอนวิธีการที่แตกต่างกัน?

455
00:20:39,287 --> 00:20:41,620
ขอแบ่งออกเป็นครั้งแรก
กรณีและกรณีที่สอง

456
00:20:41,620 --> 00:20:46,280
ถ้าและอื่นในกรณีที่หาก
ถ้า n เป็นน้อยกว่า 2 ผลตอบแทนเ​​พียง

457
00:20:46,280 --> 00:20:47,580
รู้สึกเหมือนเวลาคง

458
00:20:47,580 --> 00:20:50,970
มันเป็นชนิดของเช่นเดียวกับขั้นตอนที่สอง
ถ้า n เป็นน้อยกว่า 2 แล้วกลับ

459
00:20:50,970 --> 00:20:54,580
แต่ที่เรากล่าวว่าในวันจันทร์ที่
เวลาคงที่หรือใหญ่ o 1,

460
00:20:54,580 --> 00:20:57,130
สามารถเป็นสองขั้นตอนที่สาม
ขั้นตอนแม้ 1,000 ขั้นตอน

461
00:20:57,130 --> 00:20:59,870
สิ่งที่สำคัญคือว่ามันเป็น
จำนวนคงที่ของขั้นตอน

462
00:20:59,870 --> 00:21:03,240
ดังนั้นสีเหลืองเน้น pseudocode
ที่นี่ทำงานในเราจะเรียกว่า

463
00:21:03,240 --> 00:21:04,490
เวลาคง

464
00:21:04,490 --> 00:21:06,780
เพื่อให้มากขึ้นอย่างเป็นทางการและ
เรากำลังจะ to-- นี้

465
00:21:06,780 --> 00:21:09,910
จะมีขอบเขตที่เรา
พิธีสิทธินี้ now-- T ของ n,

466
00:21:09,910 --> 00:21:15,030
เวลาทำงานของปัญหา
ที่ใช้เวลา somethings n เป็น input

467
00:21:15,030 --> 00:21:19,150
เท่ากับใหญ่ o หนึ่ง
ถ้า n เป็นน้อยกว่า 2

468
00:21:19,150 --> 00:21:20,640
ดังนั้นจึงเป็นเงื่อนไขในการที่

469
00:21:20,640 --> 00:21:24,150
ดังนั้นเพื่อให้มีความชัดเจนถ้า n มีค่าน้อยกว่า
2 เรามีรายการสั้นมากแล้ว

470
00:21:24,150 --> 00:21:29,151
เวลาทำงาน, เสื้อของ n โดยที่ n คือ
1 หรือ 0 ในกรณีที่เฉพาะเจาะจงมากนี้

471
00:21:29,151 --> 00:21:30,650
มันเป็นเพียงแค่จะเป็นเวลาอย่างต่อเนื่อง

472
00:21:30,650 --> 00:21:32,691
มันจะใช้เวลาหนึ่ง
ขั้นตอนที่สองขั้นตอนใด

473
00:21:32,691 --> 00:21:33,950
มันเป็นจำนวนคงที่ของขั้นตอน

474
00:21:33,950 --> 00:21:38,840
>> ดังนั้นส่วนฉ่ำก็จะต้องอยู่ใน
กรณีอื่น ๆ ใน pseudocode

475
00:21:38,840 --> 00:21:40,220
กรณีอื่น

476
00:21:40,220 --> 00:21:44,870
เรียงครึ่งซ้ายขององค์ประกอบจัดเรียงทางขวา
ครึ่งหนึ่งขององค์ประกอบรวม​​ครึ่งเรียง

477
00:21:44,870 --> 00:21:46,800
นานเท่าไหร่ในแต่ละขั้นตอนเหล่านั้นใช้เวลา?

478
00:21:46,800 --> 00:21:49,780
ดีถ้าการทำงาน
เวลาในการจัดเรียงองค์ประกอบ n

479
00:21:49,780 --> 00:21:53,010
คือขอเรียกว่ามาก
ทั่วไป, เสื้อของ n,

480
00:21:53,010 --> 00:21:55,500
แล้วคัดแยกซ้าย
ครึ่งหนึ่งขององค์ประกอบ

481
00:21:55,500 --> 00:21:59,720
เป็นชนิดของเช่นว่า
T ของ n หารด้วย 2

482
00:21:59,720 --> 00:22:03,000
และในทำนองเดียวกันการเรียงลำดับครึ่งหนึ่งที่เหมาะสม
ขององค์ประกอบที่เป็นชนิดของเช่นว่า

483
00:22:03,000 --> 00:22:06,974
T ของ n แบ่งออก 2 แล้ว
ผสานครึ่งเรียง

484
00:22:06,974 --> 00:22:08,890
ดีถ้าฉันมีบางอย่าง
จำนวนขององค์ประกอบที่นี่

485
00:22:08,890 --> 00:22:11,230
เช่นสี่และจำนวนบางส่วน
ขององค์ประกอบที่นี่เช่นสี่

486
00:22:11,230 --> 00:22:14,650
และฉันต้องผสานแต่ละเหล่านี้สี่
ในและแต่ละเหล่านี้สี่หนึ่ง

487
00:22:14,650 --> 00:22:17,160
หลังจากที่อื่น ๆ เพื่อให้
ในที่สุดฉันมีแปดองค์ประกอบ

488
00:22:17,160 --> 00:22:20,230
มันให้ความรู้สึกเช่นเดียวกับที่มีขนาดใหญ่ o ขั้นตอน n?

489
00:22:20,230 --> 00:22:23,500
ถ้าฉันมีนิ้วมือและแต่ละ n
พวกเขาจะต้องมีการควบรวมกิจการในสถานที่

490
00:22:23,500 --> 00:22:25,270
ที่เหมือนขั้นตอน n อีก

491
00:22:25,270 --> 00:22:27,360
>> ดังนั้น formulaically แน่นอน
เราสามารถแสดงนี้

492
00:22:27,360 --> 00:22:29,960
แม้ว่า scarily เล็ก ๆ น้อย ๆ ในตอนแรก
ได้อย่างรวดเร็ว แต่มันเป็นบางสิ่งบางอย่าง

493
00:22:29,960 --> 00:22:31,600
ที่จับตรรกะที่ว่า

494
00:22:31,600 --> 00:22:35,710
เวลาทำงาน, เสื้อของ n ถ้า n
มีค่ามากกว่าหรือเท่ากับ 2

495
00:22:35,710 --> 00:22:42,500
ในกรณีนี้กรณีอื่นที่เป็นเสื้อของ n
โดยแบ่งออกเป็น 2 บวกของ n T หารด้วย 2

496
00:22:42,500 --> 00:22:45,320
บวกใหญ่ของ n o บาง
จำนวนเชิงเส้นของขั้นตอน

497
00:22:45,320 --> 00:22:51,630
อาจจะตรง n อาจจะ 2 ครั้ง
n แต่ก็ประมาณลำดับของ n

498
00:22:51,630 --> 00:22:54,060
เพื่อที่ว่าก็เป็นวิธีการที่เราสามารถ
แสดง formulaically นี้

499
00:22:54,060 --> 00:22:56,809
ตอนนี้คุณจะไม่ทราบว่านี้นอกจาก
คุณได้บันทึกไว้ในใจของคุณ

500
00:22:56,809 --> 00:22:58,710
หรือมองมันได้ใน
ด้านหลังของตำราเรียนที่

501
00:22:58,710 --> 00:23:00,501
อาจจะมีเล็ก ๆ น้อย ๆ
โกงแผ่นที่สิ้นสุด

502
00:23:00,501 --> 00:23:03,940
แต่นี่คือจริงไป
ทำให้เรามีขนาดใหญ่ o ของ n n ล็อก,

503
00:23:03,940 --> 00:23:06,620
เพราะการเกิดซ้ำที่
คุณเห็นที่นี่ในหน้าจอ

504
00:23:06,620 --> 00:23:09,550
ถ้าคุณไม่จริงมันออกมาด้วย
จำนวนอนันต์ของตัวอย่าง

505
00:23:09,550 --> 00:23:13,000
หรือคุณคิดว่ามัน formulaically คุณจะ
เห็นว่านี้เพราะสูตรนี้

506
00:23:13,000 --> 00:23:17,100
ตัวเองเป็น recursive กับเสื้อของ
n มากกว่าสิ่งที่ด้านขวา

507
00:23:17,100 --> 00:23:21,680
และเสื้อของ n มากกว่าด้านซ้ายนี้สามารถ
จะแสดงจริงในที่สุด

508
00:23:21,680 --> 00:23:24,339
เป็นไปใหญ่ของ n ล็อก n

509
00:23:24,339 --> 00:23:26,130
ถ้าไม่เชื่อว่า
ดีสำหรับตอนนี้เพียงแค่

510
00:23:26,130 --> 00:23:28,960
ใช้เวลาบนความเชื่อที่ว่าเป็นจริง
สิ่งที่เกิดซ้ำที่นำไปสู่​​,

511
00:23:28,960 --> 00:23:31,780
แต่เป็นเพียงเล็กน้อยของ
วิธีการทางคณิตศาสตร์ที่จะมอง

512
00:23:31,780 --> 00:23:36,520
ในเวลาทำงานของการจัดเรียงผสาน
ขึ้นอยู่กับ pseudocode เพียงอย่างเดียว

513
00:23:36,520 --> 00:23:39,030
>> ตอนนี้ขอใช้เวลาบิตของการเป็น
ชีวิตจากทุกที่

514
00:23:39,030 --> 00:23:41,710
และดูที่หนึ่ง
สมาชิกวุฒิสภาบางอย่างในอดีตที่

515
00:23:41,710 --> 00:23:44,260
อาจจะดูคุ้นเคยเล็ก ๆ น้อย ๆ
ที่ทรุดตัวลงนั่งกับเอริคของ Google

516
00:23:44,260 --> 00:23:48,410
ชมิดท์เวลาที่ผ่านมาสำหรับการสัมภาษณ์
บนเวทีในด้านหน้าของทั้งกลุ่ม

517
00:23:48,410 --> 00:23:53,710
ของคนที่พูดคุยเกี่ยวกับในท้ายที่สุด
หัวข้อที่สวยตอนนี้คุ้นเคย

518
00:23:53,710 --> 00:23:54,575
ลองมาดู

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Sc​​hmidt: ตอนนี้สมาชิกวุฒิสภา
คุณอยู่ที่นี่ที่ Google,

521
00:24:03,890 --> 00:24:09,490
และผมชอบที่จะคิดว่า
ประธานาธิบดีเป็นการสัมภาษณ์งาน

522
00:24:09,490 --> 00:24:11,712
ตอนนี้มันเป็นเรื่องยากที่จะได้รับงานเป็นประธาน

523
00:24:11,712 --> 00:24:12,670
ประธานาธิบดีโอบามา: ขวา

524
00:24:12,670 --> 00:24:13,940
Eric Sc​​hmidt: และคุณ
จะทำ [ไม่ได้ยิน] ในขณะนี้

525
00:24:13,940 --> 00:24:15,523
นอกจากนี้ยังเป็นเรื่องยากที่จะได้รับงานที่ใช้ Google

526
00:24:15,523 --> 00:24:17,700
ประธานาธิบดีโอบามา: ขวา

527
00:24:17,700 --> 00:24:21,330
>> Eric Sc​​hmidt: เรามีคำถาม
และเราถามคำถามที่ผู้สมัครของเรา

528
00:24:21,330 --> 00:24:24,310
และเป็นหนึ่งในนี้มาจากลาร์รีชวิมเม

529
00:24:24,310 --> 00:24:25,890
>> ประธานาธิบดีโอบามา: OK

530
00:24:25,890 --> 00:24:27,005
>> Eric Sc​​hmidt: อะไรนะ?

531
00:24:27,005 --> 00:24:28,130
พวกคุณคิดว่าฉันล้อเล่น?

532
00:24:28,130 --> 00:24:30,590
มันอยู่ที่นี่

533
00:24:30,590 --> 00:24:33,490
วิธีที่มีประสิทธิภาพมากที่สุดในการคืออะไร
เรียงลำดับล้านจำนวนเต็ม 32 bit?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> ประธานาธิบดีโอบามา: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Sc​​hmidt: บางครั้ง
บางทีฉันขอโทษ maybe--

537
00:24:41,020 --> 00:24:42,750
ประธานาธิบดีโอบามา: ไม่มีไม่มี
ไม่มีไม่ฉัน think--

538
00:24:42,750 --> 00:24:43,240
Eric Sc​​hmidt: ที่ไม่ it--

539
00:24:43,240 --> 00:24:45,430
ประธานาธิบดีโอบามา: ฉัน
คิดว่าผมคิดว่าฟอง

540
00:24:45,430 --> 00:24:46,875
การเรียงลำดับจะเป็นวิธีที่ผิดไป

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Sc​​hmidt: มา

543
00:24:50,535 --> 00:24:52,200
ใครบอกเขาว่านี้หรือไม่?

544
00:24:52,200 --> 00:24:54,020
ตกลง.

545
00:24:54,020 --> 00:24:55,590
ฉันไม่ได้วิทยาศาสตร์คอมพิวเตอร์ on--

546
00:24:55,590 --> 00:24:58,986
>> ประธานาธิบดีโอบามา: เราได้
มีสายลับของเราในการมี

547
00:24:58,986 --> 00:24:59,860
ศาสตราจารย์: สิทธิทั้งหมด

548
00:24:59,860 --> 00:25:03,370
ขอปล่อยให้อยู่ข้างหลังเราตอนนี้
โลกทฤษฎีของขั้นตอนวิธี

549
00:25:03,370 --> 00:25:06,520
ในการวิเคราะห์เชิง
ดังกล่าวและกลับไปที่หัวข้อ

550
00:25:06,520 --> 00:25:09,940
จากสัปดาห์ที่ศูนย์และหนึ่งและเริ่มต้น
ที่จะเอาล้อการฝึกอบรมบาง

551
00:25:09,940 --> 00:25:10,450
ถ้าคุณจะ.

552
00:25:10,450 --> 00:25:13,241
เพื่อให้คุณเข้าใจจริงๆ
ในท้ายที่สุดจากพื้นดินขึ้นสิ่งที่

553
00:25:13,241 --> 00:25:16,805
ที่เกิดขึ้นภายใต้ประทุนเมื่อคุณ
เขียนรวบรวมและรันโปรแกรม

554
00:25:16,805 --> 00:25:19,680
จำโดยเฉพาะอย่างยิ่งว่านี่คือ
โปรแกรม C แรกที่เรามองไปที่

555
00:25:19,680 --> 00:25:22,840
ยอมรับโปรแกรมใช้งานง่าย
แปลกค่อนข้างพูด

556
00:25:22,840 --> 00:25:24,620
นั้น, พิมพ์มัน Hello World

557
00:25:24,620 --> 00:25:27,610
และจำได้ว่าผมพูดว่ากระบวนการ
รหัสแหล่งที่มาที่ไปผ่าน

558
00:25:27,610 --> 00:25:28,430
คือตรงนี้

559
00:25:28,430 --> 00:25:31,180
คุณจะใช้รหัสต้นฉบับของคุณผ่าน
มันผ่านการคอมไพเลอร์เช่นเสียงดังกราว,

560
00:25:31,180 --> 00:25:34,650
และออกมาพร้อมรหัสวัตถุที่
อาจมีลักษณะเช่นนี้ศูนย์และคน

561
00:25:34,650 --> 00:25:37,880
ที่ CPU ของคอมพิวเตอร์ของกลาง
หน่วยประมวลผลหรือสมอง

562
00:25:37,880 --> 00:25:39,760
ในที่สุดเข้าใจ

563
00:25:39,760 --> 00:25:42,460
>> ปรากฎว่าที่เป็น
บิตของเปลือกที่

564
00:25:42,460 --> 00:25:44,480
ว่าเราอยู่ในขณะนี้
ตำแหน่งที่จะหยอกล้อออกจากกัน

565
00:25:44,480 --> 00:25:46,720
จะเข้าใจสิ่งที่ได้รับจริงๆ
ที่เกิดขึ้นภายใต้ฝากระโปรง

566
00:25:46,720 --> 00:25:48,600
เวลาที่คุณทำงานทุก
เสียงดังกราวหรือมากกว่าปกติ

567
00:25:48,600 --> 00:25:53,040
เวลาที่คุณทำให้โปรแกรมทุก
ใช้ตรวจและ CF 50 IDE

568
00:25:53,040 --> 00:25:56,760
โดยเฉพาะอย่างยิ่งสิ่งที่ชอบ
นี้ถูกสร้างขึ้นครั้งแรก

569
00:25:56,760 --> 00:25:58,684
เมื่อคุณรวบรวมโปรแกรมของคุณ

570
00:25:58,684 --> 00:26:00,600
ในคำอื่น ๆ เมื่อคุณ
ใช้รหัสต้นฉบับของคุณ

571
00:26:00,600 --> 00:26:04,390
และรวบรวมสิ่งที่เป็นครั้งแรก
ถูกออกมาโดยเสียงดังกราว

572
00:26:04,390 --> 00:26:06,370
เป็นสิ่งที่รู้จักกันในชื่อรหัสการชุมนุม

573
00:26:06,370 --> 00:26:08,990
และในความเป็นจริงมันมีลักษณะเหมือนกับนี้

574
00:26:08,990 --> 00:26:11,170
>> ฉันวิ่งคำสั่งที่
บรรทัดคำสั่งก่อนหน้านี้

575
00:26:11,170 --> 00:26:16,260
รีบเสียงดังกราวทุน s hello.c,
และสร้างไฟล์

576
00:26:16,260 --> 00:26:19,490
สำหรับผมเรียกว่า hello.s,
ภายในซึ่งเป็นว่า

577
00:26:19,490 --> 00:26:22,290
เนื้อหาเหล​​่านี้และน้อยมาก
ด้านบนและด้านล่างขึ้นเล็ก ๆ น้อย ๆ

578
00:26:22,290 --> 00:26:25,080
แต่ฉันได้ใส่ฉ่ำ
ที่นี่ข้อมูลบนหน้าจอ

579
00:26:25,080 --> 00:26:29,190
และถ้าคุณมองอย่างใกล้ชิดคุณจะเห็น
อย่างน้อยไม่กี่คำหลักที่คุ้นเคย

580
00:26:29,190 --> 00:26:31,330
เรามีหลักที่ด้านบน

581
00:26:31,330 --> 00:26:35,140
เราได้ printf ลงตรงกลาง

582
00:26:35,140 --> 00:26:38,670
และเรายังมีทักทายโลก
n เครื่องหมายในเครื่องหมายคำพูดลงมาด้านล่าง

583
00:26:38,670 --> 00:26:42,450
>> และทุกอย่างอื่นในที่นี่
เป็นคำแนะนำระดับที่ต่ำมาก

584
00:26:42,450 --> 00:26:45,500
ที่ CPU ของคอมพิวเตอร์เข้าใจ

585
00:26:45,500 --> 00:26:50,090
คำแนะนำของ CPU ที่ย้ายหน่วยความจำ
รอบที่สายโหลดจากหน่วยความจำ

586
00:26:50,090 --> 00:26:52,750
และท้ายที่สุดการพิมพ์
สิ่งที่อยู่บนหน้าจอ

587
00:26:52,750 --> 00:26:56,780
ตอนนี้สิ่งที่เกิดขึ้น แต่หลังจากที่
รหัสการชุมนุมนี้ถูกสร้างขึ้น?

588
00:26:56,780 --> 00:26:59,964
ในที่สุดคุณจะทำจริง
ยังคงสร้างรหัสวัตถุ

589
00:26:59,964 --> 00:27:02,630
แต่ขั้นตอนที่มีจริงๆ
รับไปในใต้ฝากระโปรง

590
00:27:02,630 --> 00:27:04,180
ดูเล็ก ๆ น้อย ๆ เช่นนี้

591
00:27:04,180 --> 00:27:08,390
รหัสที่มาจะกลายเป็นรหัสการชุมนุม
ซึ่งก็จะกลายเป็นรหัสวัตถุ

592
00:27:08,390 --> 00:27:11,930
และทำงานที่นี่มีคำว่า
เมื่อคุณรวบรวมซอร์สโค้ดของคุณ

593
00:27:11,930 --> 00:27:16,300
ออกมาพร้อมรหัสการชุมนุมแล้ว
เมื่อคุณรวบรวมรหัสการชุมนุมของคุณ

594
00:27:16,300 --> 00:27:17,800
ออกมารหัสวัตถุ

595
00:27:17,800 --> 00:27:20,360
>> ตอนนี้เสียงดังกราวมีความซับซ้อนสุด
ชอบมากของคอมไพเลอร์ที่

596
00:27:20,360 --> 00:27:23,151
และมันไม่ทุกขั้นตอนเหล่านี้
ร่วมกันและมันไม่จำเป็นต้อง

597
00:27:23,151 --> 00:27:25,360
ออกกลางใด ๆ
ไฟล์ที่คุณยังสามารถดู

598
00:27:25,360 --> 00:27:28,400
มันก็จะรวบรวมสิ่งที่
ซึ่งเป็นคำทั่วไปที่

599
00:27:28,400 --> 00:27:30,000
อธิบายถึงกระบวนการทั้งหมดนี้

600
00:27:30,000 --> 00:27:32,000
แต่ถ้าคุณต้องการจริงๆ
โดยเฉพาะอย่างยิ่งที่จะได้มี

601
00:27:32,000 --> 00:27:34,330
มากขึ้นที่เกิดขึ้นมีทั้ง

602
00:27:34,330 --> 00:27:38,860
>> แต่ขอยังพิจารณาว่าแม้ในขณะนี้
ว่าโปรแกรมง่ายสุด hello.c,

603
00:27:38,860 --> 00:27:40,540
เรียกว่าฟังก์ชั่น

604
00:27:40,540 --> 00:27:41,870
มันเรียกว่า printf

605
00:27:41,870 --> 00:27:46,900
แต่ผมไม่ได้เขียน printf จริง
ที่มาพร้อมกับคเพื่อที่จะพูด

606
00:27:46,900 --> 00:27:51,139
มันเป็นฟังก์ชั่นการเรียกคืนที่
ประกาศใน io.h มาตรฐานซึ่ง

607
00:27:51,139 --> 00:27:53,180
ไฟล์ส่วนหัวที่
เป็นเรื่องที่เราจะได้จริง

608
00:27:53,180 --> 00:27:55,780
ดำน้ำในระดับความลึกมากขึ้นก่อนที่จะยาว

609
00:27:55,780 --> 00:27:58,000
แต่ไฟล์ส่วนหัวเป็น
มักจะมาพร้อมกับ

610
00:27:58,000 --> 00:28:02,920
โดยไฟล์รหัสแฟ้มรหัสต้นฉบับดังนั้น
เหมือนมีอยู่ io.h. มาตรฐาน

611
00:28:02,920 --> 00:28:05,930
>> บางครั้งที่ผ่านมาใครบางคน
หรือใครบางคนยังเขียน

612
00:28:05,930 --> 00:28:11,040
ไฟล์ที่เรียกว่า io.c มาตรฐานใน
ซึ่งคำจำกัดความที่เกิดขึ้นจริง

613
00:28:11,040 --> 00:28:15,220
หรือการใช้งานของ printf,
และอัดแน่นของฟังก์ชั่นอื่น ๆ

614
00:28:15,220 --> 00:28:16,870
ถูกเขียนจริง

615
00:28:16,870 --> 00:28:22,140
เพื่อให้ได้รับถ้าเราพิจารณามี
ที่นี่ด้านซ้าย, hello.c ว่าเมื่อ

616
00:28:22,140 --> 00:28:26,250
รวบรวมจะช่วยให้เรา hello.s แม้ว่า
เสียงดังกราวไม่รำคาญประหยัดในสถานที่

617
00:28:26,250 --> 00:28:31,360
เราสามารถมองเห็นมันและรหัสการชุมนุมว่า
ได้รับการประกอบเป็น hello.o ซึ่ง

618
00:28:31,360 --> 00:28:34,630
เป็นแท้จริงชื่อเริ่มต้น
เมื่อใดก็ตามที่คุณได้รับการรวบรวมแหล่งที่มา

619
00:28:34,630 --> 00:28:39,350
รหัสลงในรหัสวัตถุ แต่ไม่
ค่อนข้างพร้อมที่จะดำเนินการมันยัง

620
00:28:39,350 --> 00:28:41,460
เพราะขั้นตอนอื่น
ที่เกิดขึ้นและมี

621
00:28:41,460 --> 00:28:44,440
ที่เกิดขึ้นที่ผ่านมาไม่กี่คน
สัปดาห์ถิ่นอาจจะอยู่กับคุณ

622
00:28:44,440 --> 00:28:47,290
>> โดยเฉพาะที่ใดที่หนึ่ง
ใน CS50 IDE และนี้

623
00:28:47,290 --> 00:28:49,870
เกินไปจะเป็นบิตของ
เปลือกสักครู่

624
00:28:49,870 --> 00:28:54,670
มีหรืออยู่กับเวลา
ไฟล์ที่เรียกว่ามาตรฐาน io.c,

625
00:28:54,670 --> 00:28:58,440
ว่าคนที่เรียบเรียง
io.s มาตรฐานหรือเทียบเท่า

626
00:28:58,440 --> 00:29:02,010
ว่าคนที่ประกอบแล้ว
เข้า io.o มาตรฐาน

627
00:29:02,010 --> 00:29:04,600
หรือมันจะเปิดออกเป็น
ไฟล์ที่แตกต่างกันเล็กน้อย

628
00:29:04,600 --> 00:29:07,220
รูปแบบที่สามารถมีที่แตกต่างกัน
ไฟล์นามสกุลทั้งหมด

629
00:29:07,220 --> 00:29:11,720
แต่ในทางทฤษฎีและแนวคิดว่า
ขั้นตอนเหล่านั้นจะเกิดขึ้นได้ในบางรูปแบบ

630
00:29:11,720 --> 00:29:14,060
ซึ่งก็คือการกล่าวว่าในขณะนี้
เมื่อผมเขียนโปรแกรม

631
00:29:14,060 --> 00:29:17,870
hello.c ที่เพิ่งพูดว่าสวัสดีโลก
และฉันใช้รหัสของคนอื่น

632
00:29:17,870 --> 00:29:22,480
เช่น printf ซึ่งครั้งหนึ่งเคยอยู่บน
เวลาในไฟล์ที่เรียกว่ามาตรฐาน io.c,

633
00:29:22,480 --> 00:29:26,390
แล้วอย่างใดฉันต้องใช้เวลาของฉัน
รหัสวัตถุศูนย์ของฉันและคน

634
00:29:26,390 --> 00:29:29,260
และวัตถุของบุคคลนั้น
รหัสหรือศูนย์และคน,

635
00:29:29,260 --> 00:29:34,970
และอย่างใดเชื่อมโยงพวกเขาเข้าด้วยกันเป็น
หนึ่งไฟล์สุดท้ายที่เรียกว่าสวัสดีที่

636
00:29:34,970 --> 00:29:38,070
มีทั้งหมดของศูนย์และ
คนจากฟังก์ชั่นหลักของฉัน

637
00:29:38,070 --> 00:29:40,830
และทั้งหมดของค่าศูนย์
และคนสำหรับ printf

638
00:29:40,830 --> 00:29:44,900
>> และแน่นอนว่าขั้นตอนสุดท้ายคือ
ที่เรียกว่าการเชื่อมโยงรหัสวัตถุของคุณ

639
00:29:44,900 --> 00:29:47,490
การส่งออกของที่
เป็นแฟ้มที่ปฏิบัติการ

640
00:29:47,490 --> 00:29:49,780
ดังนั้นในความเป็นธรรมที่
ท้ายของวันที่ไม่มีอะไร

641
00:29:49,780 --> 00:29:52,660
มีการเปลี่ยนแปลงตั้งแต่หนึ่งสัปดาห์เมื่อเรา
แรกเริ่มรวบรวมโปรแกรม

642
00:29:52,660 --> 00:29:55,200
อันที่จริงทั้งหมดนี้ได้รับการ
ที่เกิดขึ้นภายใต้ประทุน

643
00:29:55,200 --> 00:29:57,241
แต่ตอนนี้เราอยู่ในตำแหน่ง
ที่เราสามารถทำได้จริง

644
00:29:57,241 --> 00:29:58,794
หยอกล้อออกจากกันตามขั้นตอนต่างๆเหล่านี้

645
00:29:58,794 --> 00:30:00,710
และแน่นอนในตอนท้าย
ในวันนี้เราก็ยังคง

646
00:30:00,710 --> 00:30:04,480
ทิ้งให้อยู่กับศูนย์และคนที่
เป็นจริงทำต่อดีในขณะนี้

647
00:30:04,480 --> 00:30:08,620
ความสามารถของ C อีกว่า
เราไม่ได้มีการใช้ประโยชน์จากโอกาสมากที่สุด

648
00:30:08,620 --> 00:30:11,250
ถึงวันที่รู้จักในฐานะผู้ประกอบการระดับบิต

649
00:30:11,250 --> 00:30:15,220
ในคำอื่น ๆ ป่านนี้เราได้ทุกที่ทุกเวลา
จัดการกับข้อมูลใน C หรือตัวแปรใน C,

650
00:30:15,220 --> 00:30:17,660
เราได้มีสิ่งที่ต้องการ
และตัวอักษรลอยและอิน

651
00:30:17,660 --> 00:30:21,990
และปรารถนาและคู่ผสมและชอบ แต่
ทุกคนเป็นอย่างน้อยแปดบิต

652
00:30:21,990 --> 00:30:25,550
เราไม่เคยยังสามารถที่จะ
จัดการบิตของแต่ละบุคคล

653
00:30:25,550 --> 00:30:28,970
แม้ว่าบิตของแต่ละบุคคลเรา
รู้ว่าสามารถเป็นตัวแทนของ 0 และ 1

654
00:30:28,970 --> 00:30:32,640
ตอนนี้ก็ปรากฎว่าใน C คุณ
สามารถได้รับการเข้าถึงบิตของแต่ละบุคคล

655
00:30:32,640 --> 00:30:35,530
ถ้าคุณรู้ไวยากรณ์
ที่จะได้รับพวกเขา

656
00:30:35,530 --> 00:30:38,010
>> ดังนั้นลองมาดู
ผู้ประกอบการที่ค่าที่เหมาะสม

657
00:30:38,010 --> 00:30:41,700
ภาพดังนั้นที่นี่เป็นสัญลักษณ์ไม่กี่ที่
เราได้ชนิดของการเรียงลำดับของ, เห็นมาก่อน

658
00:30:41,700 --> 00:30:45,580
ฉันเห็นเครื่องหมายเป็นแนวตั้ง
บาร์และอื่น ๆ ได้เป็นอย่างดี

659
00:30:45,580 --> 00:30:49,430
และจำได้ว่าเครื่องหมายเครื่องหมาย
เป็นสิ่งที่เราได้เห็นมาก่อน

660
00:30:49,430 --> 00:30:54,060
ตรรกะและผู้ประกอบการที่คุณมี
พวกเขาทั้งสองร่วมกันหรือตรรกะหรือ

661
00:30:54,060 --> 00:30:56,300
ผู้ประกอบการที่คุณ
มีสองแถบแนวตั้ง

662
00:30:56,300 --> 00:31:00,550
ผู้ประกอบการระดับบิตซึ่งเราจะ
เห็นทำงานบนบิตเป็นรายบุคคล

663
00:31:00,550 --> 00:31:03,810
เพียงแค่ใช้เครื่องหมายเดียว
แถบแนวตั้งเดียวสัญลักษณ์ลูกศร

664
00:31:03,810 --> 00:31:06,620
ที่มาต่อไปเล็ก ๆ น้อย ๆ
ตัวหนอนและทิ้งแล้ว

665
00:31:06,620 --> 00:31:08,990
วงเล็บวงเล็บซ้ายหรือ
วงเล็บวงเล็บที่ถูกต้องเหมาะสม

666
00:31:08,990 --> 00:31:10,770
แต่ละเหล่านี้มีความหมายที่แตกต่างกัน

667
00:31:10,770 --> 00:31:11,950
>> ในความเป็นจริงลองดู

668
00:31:11,950 --> 00:31:16,560
ให้เป็นไปในวันนี้โรงเรียนเก่าและใช้งาน
หน้าจอสัมผัสจากปีกลายที่

669
00:31:16,560 --> 00:31:18,002
ที่รู้จักกันเป็นกระดานไวท์บอร์ด

670
00:31:18,002 --> 00:31:19,710
และคณะกรรมการนี​​้สีขาว
เป็นไปเพื่อให้เรา

671
00:31:19,710 --> 00:31:27,360
ในการแสดงสัญลักษณ์บางอย่างที่ค่อนข้างง่าย
หรือค่อนข้างบางสูตรที่ค่อนข้างง่าย

672
00:31:27,360 --> 00:31:29,560
ที่เราสามารถทำได้ในท้ายที่สุดแล้ว
ใช้ประโยชน์ในการสั่งซื้อ

673
00:31:29,560 --> 00:31:33,230
ในการเข้าถึงของแต่ละบุคคล
บิตภายในโปรแกรม C

674
00:31:33,230 --> 00:31:34,480
ในคำอื่น ๆ ขอให้ทำเช่นนี้

675
00:31:34,480 --> 00:31:37,080
การพูดคุยครั้งแรกลองหา
ช่วงเวลาที่เกี่ยวกับเครื่องหมาย,

676
00:31:37,080 --> 00:31:39,560
ซึ่งเป็นค่าที่เหมาะสมและผู้ประกอบการ

677
00:31:39,560 --> 00:31:42,130
ในคำอื่น ๆ นี้
ผู้ประกอบการที่ช่วยให้

678
00:31:42,130 --> 00:31:45,930
ผมที่จะมีตัวแปรซ้าย
โดยทั่วไปและตัวแปรทางด้านขวามือ

679
00:31:45,930 --> 00:31:50,640
หรือค่าของแต่ละบุคคลว่าถ้าเราและ
พวกเขาร่วมกันให้ฉันผลสุดท้าย

680
00:31:50,640 --> 00:31:51,560
ดังนั้นสิ่งที่ฉันหมายความว่าอย่างไร

681
00:31:51,560 --> 00:31:54,840
ถ้าในโปรแกรมคุณมีตัวแปร
ว่าร้านค้าหนึ่งในค่าเหล่านี้

682
00:31:54,840 --> 00:31:58,000
หรือขอให้มันง่ายและเพียงแค่
เขียนออกศูนย์และคนเป็นรายบุคคล

683
00:31:58,000 --> 00:32:00,940
นี่คือวิธีการทำงานของผู้ประกอบเครื่องหมาย

684
00:32:00,940 --> 00:32:06,400
0 0 เครื่องหมายเป็นไปเท่ากับ 0

685
00:32:06,400 --> 00:32:07,210
ตอนนี้ทำไมเป็นอย่างนั้น?

686
00:32:07,210 --> 00:32:09,291
>> มันคล้ายกับ
การแสดงออกบูลีน

687
00:32:09,291 --> 00:32:10,540
ที่เราได้กล่าวถึงป่านนี้

688
00:32:10,540 --> 00:32:15,800
หากคุณคิดว่าหลังจากทั้งหมด 0
เท็จ 0 เป็นเท็จเท็จและเท็จ

689
00:32:15,800 --> 00:32:18,720
เป็นอย่างที่เราได้กล่าวถึง
เหตุผลยังเท็จ

690
00:32:18,720 --> 00:32:20,270
ดังนั้นเราจึงได้รับ 0 ที่นี่เช่นกัน

691
00:32:20,270 --> 00:32:24,390
ถ้าคุณใช้เครื่องหมาย 0
1, ดีว่ามากเกินไป

692
00:32:24,390 --> 00:32:29,890
เป็นไปได้ที่ 0 เพราะนี้
การแสดงออกทางด้านซ้ายมือจะเป็นจริงหรือ 1

693
00:32:29,890 --> 00:32:32,360
มันจะต้องเป็นจริงและเป็นความจริง

694
00:32:32,360 --> 00:32:36,320
แต่ที่นี่เรามีที่ผิดพลาด
และเป็นความจริงหรือ 0 และ 1

695
00:32:36,320 --> 00:32:42,000
ตอนนี้อีกครั้งถ้าเรามี 1 เครื่องหมาย
0 ที่มากเกินไปจะเป็น 0,

696
00:32:42,000 --> 00:32:47,240
และถ้าเรามี 1 เครื่องหมาย 1,
ในที่สุดเราก็จะมี 1 บิต

697
00:32:47,240 --> 00:32:50,340
ดังนั้นในคำอื่น ๆ ที่เราไม่ได้ทำ
สิ่งที่น่าสนใจกับผู้ประกอบการนี​​้

698
00:32:50,340 --> 00:32:51,850
เพียง แต่ผู้ประกอบการเครื่องหมายนี้

699
00:32:51,850 --> 00:32:53,780
มันเป็นค่าที่เหมาะสมและผู้ประกอบการ

700
00:32:53,780 --> 00:32:57,290
แต่เหล่านี้เป็นส่วนผสม
ผ่านทางที่เราสามารถทำได้

701
00:32:57,290 --> 00:32:59,240
สิ่งที่น่าสนใจที่เราจะเห็นทันที

702
00:32:59,240 --> 00:33:02,790
>> ตอนนี้ให้ดูที่เพียงแค่คนเดียว
แถบแนวตั้งมากกว่าที่นี่ด้านขวา

703
00:33:02,790 --> 00:33:06,710
ถ้าฉันมีบิต 0 และฉัน
หรือมันกับค่าที่เหมาะสม

704
00:33:06,710 --> 00:33:11,030
หรือผู้ประกอบการอีก 0 บิต
ที่จะให้ฉัน 0

705
00:33:11,030 --> 00:33:17,540
ถ้าผมใช้เวลา 0 บิตและหรือมันด้วย
1 บิตแล้วฉันจะได้รับ 1

706
00:33:17,540 --> 00:33:19,830
และในความเป็นจริงเพียงเพื่อ
ความคมชัดให้ฉันกลับไป

707
00:33:19,830 --> 00:33:23,380
เพื่อให้แถบแนวตั้งของฉัน
ไม่ได้เข้าใจผิดว่าเป็น 1

708
00:33:23,380 --> 00:33:26,560
ผมขอเขียนทั้งหมดของ
1 ของฉันน้อยมาก

709
00:33:26,560 --> 00:33:32,700
อย่างชัดเจนเพื่อที่เราจะได้เห็นต่อไปถ้าผม
มี 1 หรือ 0, ที่จะเป็นที่ 1,

710
00:33:32,700 --> 00:33:39,060
และถ้าผมมี 1 หรือ 1 ที่
เกินไปเป็นไปได้ที่ 1

711
00:33:39,060 --> 00:33:42,900
ดังนั้นคุณจะเห็นว่ามีเหตุผลหรือ
ผู้ประกอบการทำงานแตกต่างกันมาก

712
00:33:42,900 --> 00:33:48,070
นี้จะช่วยให้ฉันหรือ 0 0 0 ให้ฉัน แต่
ทุกชุดอื่น ๆ ทำให้ผม 1

713
00:33:48,070 --> 00:33:52,480
ตราบใดที่ฉันมีหนึ่ง 1 ใน
สูตรผลที่เป็นไปได้ที่ 1

714
00:33:52,480 --> 00:33:55,580
>> ในทางตรงกันข้ามกับและ
ผู้ประกอบการ, เครื่องหมาย,

715
00:33:55,580 --> 00:34:00,940
แต่ถ้าฉันมีสอง 1 ใน
สมการไม่จริงผมได้รับ 1

716
00:34:00,940 --> 00:34:02,850
ตอนนี้มีไม่กี่อื่น ๆ
ผู้ประกอบการเป็นอย่างดี

717
00:34:02,850 --> 00:34:04,810
หนึ่งในนั้นคือมีส่วนร่วมน้อยมาก

718
00:34:04,810 --> 00:34:07,980
เพื่อให้ฉันไปข้างหน้าและลบ
นี้เพื่อเพิ่มพื้นที่ว่างบาง

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
และขอใช้เวลาดูที่
สัญลักษณ์ลูกศรเพื่อรอสักครู่

721
00:34:16,460 --> 00:34:18,210
นี้เป็นปกติ
ตัวอักษรที่คุณสามารถพิมพ์

722
00:34:18,210 --> 00:34:21,420
บนแป้นพิมพ์ของคุณกด Shift ถือครองและ
จากนั้นหนึ่งของตัวเลขที่อยู่บนยอดของสหรัฐ

723
00:34:21,420 --> 00:34:22,250
แป้นพิมพ์

724
00:34:22,250 --> 00:34:26,190
>> ดังนั้นนี้เป็นพิเศษ
หรือผู้ประกอบการ แต่เพียงผู้เดียวหรือ

725
00:34:26,190 --> 00:34:27,790
ดังนั้นเราจึงเห็นผู้ประกอบการหรือ

726
00:34:27,790 --> 00:34:29,348
นี้เป็นพิเศษหรือผู้ประกอบการ

727
00:34:29,348 --> 00:34:30,639
สิ่งที่เป็นจริงแตกต่างกันอย่างไร

728
00:34:30,639 --> 00:34:34,570
ดีขอเพียงแค่มองไปที่สูตร
และใช้เป็นส่วนผสมในท้ายที่สุด

729
00:34:34,570 --> 00:34:37,690
0 0 แฮคเกอร์

730
00:34:37,690 --> 00:34:39,650
ฉันจะพูดอยู่เสมอ 0

731
00:34:39,650 --> 00:34:41,400
นั่นคือความหมายของการ XOR

732
00:34:41,400 --> 00:34:47,104
0 แฮคเกอร์ 1 เป็นไปได้ที่ 1

733
00:34:47,104 --> 00:34:58,810
แฮคเกอร์ 1 0 เป็นไปได้ที่ 1,
และแฮคเกอร์ 1 1 เป็นไปได้?

734
00:34:58,810 --> 00:34:59,890
ผิด?

735
00:34:59,890 --> 00:35:00,520
หรือขวา?

736
00:35:00,520 --> 00:35:01,860
ฉันไม่รู้

737
00:35:01,860 --> 00:35:02,810
0

738
00:35:02,810 --> 00:35:04,700
ตอนนี้สิ่งที่เกิดขึ้นที่นี่?

739
00:35:04,700 --> 00:35:06,630
ดีคิดเกี่ยวกับ
ชื่อของผู้ประกอบการนี​​้

740
00:35:06,630 --> 00:35:09,980
แต่เพียงผู้เดียวหรือเพื่อให้เป็น
ชื่อชนิดของการแสดงให้เห็น,

741
00:35:09,980 --> 00:35:13,940
คำตอบคือได้เพียงไปได้
1 ถ้าปัจจัยการผลิตที่มี แต่เพียงผู้เดียว

742
00:35:13,940 --> 00:35:15,560
ที่แตกต่างกันโดยเฉพาะ

743
00:35:15,560 --> 00:35:18,170
ดังนั้นนี่คือปัจจัยการผลิตที่มี
เดียวกันเพื่อการส่งออกเป็น 0

744
00:35:18,170 --> 00:35:20,700
นี่คือปัจจัยการผลิตที่มี
เดียวกันเพื่อการส่งออกเป็น 0

745
00:35:20,700 --> 00:35:25,640
นี่คือผลที่มีแตกต่างกันพวกเขา
เป็นพิเศษและเพื่อการส่งออกเป็น 1

746
00:35:25,640 --> 00:35:28,190
ดังนั้นจึงเป็นคล้ายกับ
และก็คล้ายกันมาก

747
00:35:28,190 --> 00:35:32,760
หรือค่อนข้างจะคล้ายกับ
หรือ แต่เพียงในวิธีพิเศษ

748
00:35:32,760 --> 00:35:36,210
หนึ่งนี้จะไม่เป็นที่ 1,
เพราะเรามีสอง 1,

749
00:35:36,210 --> 00:35:38,621
และไม่เฉพาะเพียงหนึ่งของพวกเขา

750
00:35:38,621 --> 00:35:39,120
ทั้งหมดขวา

751
00:35:39,120 --> 00:35:40,080
สิ่งที่เกี่ยวกับคนอื่น ๆ ?

752
00:35:40,080 --> 00:35:44,220
ตัวหนอนดีในขณะเดียวกันคือ
จริงที่ดีและง่ายขอบคุณ

753
00:35:44,220 --> 00:35:46,410
และนี่คือเอก
ผู้ประกอบการซึ่งหมายความว่า

754
00:35:46,410 --> 00:35:50,400
ก็นำไปใช้เพียงคนเดียวที่ป้อนข้อมูล
ถูกดำเนินการอย่างใดอย่างหนึ่งเพื่อที่จะพูด

755
00:35:50,400 --> 00:35:51,800
ไม่ไปทางซ้ายและขวา

756
00:35:51,800 --> 00:35:56,050
ในคำอื่น ๆ ถ้าคุณใช้ตัวหนอนของ
0 คำตอบจะเป็นตรงข้าม

757
00:35:56,050 --> 00:35:59,710
และถ้าคุณใช้ตัวหนอนของ 1,
คำตอบจะมีตรงข้าม

758
00:35:59,710 --> 00:36:02,570
ดังนั้นผู้ประกอบการเป็นตัวหนอน
วิธีการกวนเล็กน้อยที่

759
00:36:02,570 --> 00:36:06,000
หรือพลิกบิตจาก
0-1 หรือ 1-0

760
00:36:06,000 --> 00:36:09,820
>> และนั่นทำให้เราที่สุด
มีเพียงสองผู้ประกอบการขั้นสุดท้าย

761
00:36:09,820 --> 00:36:13,840
การเปลี่ยนแปลงทางด้านซ้ายที่เรียกว่าและ
ผู้ประกอบการที่เหมาะสมเพื่อการเปลี่ยนแปลงที่เรียกว่า

762
00:36:13,840 --> 00:36:16,620
ลองมาดูที่วิธีการทำงานเหล่านั้น

763
00:36:16,620 --> 00:36:20,780
ผู้ประกอบการเปลี่ยนแปลงซ้ายเขียน
กับสองวงเล็บมุมเช่นนั้น

764
00:36:20,780 --> 00:36:22,110
ดำเนินดังต่อไปนี้

765
00:36:22,110 --> 00:36:27,390
ถ้าใส่ฉันหรือถูกดำเนินการของฉันไปทางซ้าย
ผู้ประกอบการเปลี่ยนแปลงค่อนข้างเป็นเพียง 1

766
00:36:27,390 --> 00:36:33,750
และจากนั้นผมก็บอกกับคอมพิวเตอร์
ซ้ายกะที่ 1 กล่าวว่าเจ็ดสถานที่

767
00:36:33,750 --> 00:36:37,150
ผลที่ได้คือว่าผม
ใช้เวลาที่ 1 และย้ายไป

768
00:36:37,150 --> 00:36:40,160
เจ็ดสถานที่ไปยัง
ซ้ายและตามค่าเริ่มต้น

769
00:36:40,160 --> 00:36:42,270
เรากำลังจะไปคิดว่า
พื้นที่ที่จะเหมาะสม

770
00:36:42,270 --> 00:36:44,080
เป็นไปได้ที่เบาะด้วยศูนย์

771
00:36:44,080 --> 00:36:50,316
ในคำอื่น ๆ ที่เหลือ 1 กะ 7 ที่เกิดขึ้น
จะให้ฉันที่ 1 ตามมาด้วย 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 ศูนย์

773
00:36:54,060 --> 00:36:57,380
ดังนั้นในทางที่จะช่วยให้คุณ
ใช้จำนวนเล็ก ๆ เช่น 1,

774
00:36:57,380 --> 00:37:00,740
อย่างเห็นได้ชัดและทำให้มันมาก
มากมีขนาดใหญ่ในลักษณะนี้

775
00:37:00,740 --> 00:37:06,460
แต่เราจริงจะไปดู
วิธีการที่ชาญฉลาดมากขึ้นนั้น

776
00:37:06,460 --> 00:37:08,080
แทนที่จะเป็นอย่างดี

777
00:37:08,080 --> 00:37:08,720
>> ทั้งหมดขวา

778
00:37:08,720 --> 00:37:10,060
นั่นมันสำหรับสัปดาห์ที่สาม

779
00:37:10,060 --> 00:37:11,400
เราจะเห็นคุณในครั้งต่อไป

780
00:37:11,400 --> 00:37:12,770
นี่คือ CS50

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [เล่นเพลง]

783
00:37:22,243 --> 00:37:25,766
>> ลำโพงที่ 1: เขาเป็นที่ว่าง
บาร์กินไอศกรีมใส่ผลไม้ร้อนเหลวไหล

784
00:37:25,766 --> 00:37:28,090
เขามีให้ทั่วใบหน้าของเขา

785
00:37:28,090 --> 00:37:30,506
เขาสวมใส่เช่นช็อคโกแลตที่เครา

786
00:37:30,506 --> 00:37:31,756
ลำโพง 2: สิ่งที่คุณกำลังทำอะไร?

787
00:37:31,756 --> 00:37:32,422
ลำโพงที่ 3: อืม?

788
00:37:32,422 --> 00:37:33,500
อะไร?

789
00:37:33,500 --> 00:37:36,800
>> ลำโพงที่ 2: คุณไม่เพียงแค่จุ่มคู่?

790
00:37:36,800 --> 00:37:38,585
คุณดับเบิลจุ่มชิป

791
00:37:38,585 --> 00:37:39,460
ลำโพงที่ 3: ขอโทษนะ

792
00:37:39,460 --> 00:37:44,440
ลำโพงที่ 2: คุณจุ่มชิปคุณ
เอากัดและคุณจุ่มลงอีกครั้ง

793
00:37:44,440 --> 00:37:44,940
ลำโพงที่ 3:

794
00:37:44,940 --> 00:37:48,440
ลำโพง 2: เพื่อให้เป็นเหมือนกับการใส่
ปากของคุณทั้งหมดที่ถูกต้องในกรมทรัพย์สินทางปัญญา

795
00:37:48,440 --> 00:37:52,400
ครั้งต่อไปที่คุณจะใช้ชิป
เพียงจุ่มครั้งและจบมัน

796
00:37:52,400 --> 00:37:53,890
>> ลำโพงที่ 3: คุณรู้ว่าสิ่งที่แดน?

797
00:37:53,890 --> 00:37:58,006
คุณจุ่มวิธีการที่คุณต้องการที่จะจุ่ม

798
00:37:58,006 --> 00:38:01,900
ฉันจะจุ่มวิธีการที่ฉันต้องการที่จะจุ่ม

799
00:38:01,900 --> 00:38:03,194