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

2
00:00:00,488 --> 00:00:10,800
>> [عزف الموسيقى]

3
00:00:10,800 --> 00:00:13,500
DAVID مالان: حسنا.

4
00:00:13,500 --> 00:00:14,670
كل الحق، نرحب مرة.

5
00:00:14,670 --> 00:00:18,120
لذلك هذا هو الأسبوع 4، بداية
منها، بالفعل.

6
00:00:18,120 --> 00:00:21,320
وعليك أن تتذكر أنه في الأسبوع الماضي، وضعنا
رمز جانبا لقليلا فقط

7
00:00:21,320 --> 00:00:24,240
وبدأنا نتحدث أكثر من ذلك بقليل
رفيع المستوى، حول أشياء مثل

8
00:00:24,240 --> 00:00:28,130
البحث والفرز، والتي على الرغم من
أفكار بسيطة إلى حد ما، هي

9
00:00:28,130 --> 00:00:31,840
ممثل فئة من المشاكل
سوف نبدأ في حل ولا سيما

10
00:00:31,840 --> 00:00:34,820
عندما تبدأ في التفكير في النهائي
المشاريع والحلول للاهتمام لك

11
00:00:34,820 --> 00:00:36,760
قد تضطر إلى المشاكل في العالم الحقيقي.

12
00:00:36,760 --> 00:00:39,490
الآن هو فقاعة نوع واحد من أبسط
هذه الخوارزميات، و

13
00:00:39,490 --> 00:00:42,900
عملت من خلال وجود هذه الأعداد الصغيرة
في قائمة أو في مجموعة من نوع

14
00:00:42,900 --> 00:00:46,530
فقاعة طريقهم صعودا إلى الأعلى، و
أرقام كبيرة تتحرك طريقهم وصولا الى

15
00:00:46,530 --> 00:00:47,930
نهاية تلك القائمة.

16
00:00:47,930 --> 00:00:50,650
>> وأذكر أننا يمكن أن تصور
فقاعة نوع قليلا

17
00:00:50,650 --> 00:00:52,310
شيء من هذا القبيل.

18
00:00:52,310 --> 00:00:53,640
لذلك اسمحوا لي المضي قدما وانقر فوق ابدأ.

19
00:00:53,640 --> 00:00:55,350
لقد انتقاؤه فقاعة الفرز.

20
00:00:55,350 --> 00:00:58,920
وإذا كنت أذكر أن الأزرق أطول
خطوط تمثل الأرقام الكبيرة والصغيرة

21
00:00:58,920 --> 00:01:03,300
الخطوط الزرقاء تمثل أعداد صغيرة، و
نذهب من خلال هذا مرارا وتكرارا و

22
00:01:03,300 --> 00:01:07,680
مرة أخرى، المقارنة بين اثنين من القضبان بجانب بعضها
أخرى باللون الأحمر، ونحن في طريقنا للمبادلة

23
00:01:07,680 --> 00:01:11,010
أكبر وأصغر إذا
هم خارج الترتيب.

24
00:01:11,010 --> 00:01:14,150
>> ولذلك فإن هذا سوف يستمر ويستمر ويذهب
على، وسترى أن أكبر

25
00:01:14,150 --> 00:01:16,700
عناصر ويشقون طريقهم إلى
الحق، والعناصر هي أصغر

26
00:01:16,700 --> 00:01:17,900
يشقون طريقهم إلى اليسار.

27
00:01:17,900 --> 00:01:21,380
ولكن بدأنا في تحديد
كفاءة، و

28
00:01:21,380 --> 00:01:22,970
نوعية هذه الخوارزمية.

29
00:01:22,970 --> 00:01:25,200
وقلنا أنه في أسوأ
الحالة، استغرق هذه الخوارزمية

30
00:01:25,200 --> 00:01:27,940
تقريبا كم عدد الخطوات؟

31
00:01:27,940 --> 00:01:28,980
>> حتى ن المربعة.

32
00:01:28,980 --> 00:01:30,402
وما كان ن؟

33
00:01:30,402 --> 00:01:31,650
>> الحضور: عدد من العناصر.

34
00:01:31,650 --> 00:01:32,790
>> DAVID مالان: لذا كان ن
عدد من العناصر.

35
00:01:32,790 --> 00:01:33,730
ولذا فإننا سوف نفعل ذلك في كثير من الأحيان.

36
00:01:33,730 --> 00:01:36,650
أي وقت نريد أن نتحدث عن حجم
وجود مشكلة أو حجم ل

37
00:01:36,650 --> 00:01:39,140
المدخلات، أو مقدار الوقت الذي يستغرقه
لإنتاج الإخراج، سنقوم فقط

38
00:01:39,140 --> 00:01:41,610
معمم مهما
المدخلات كما ن.

39
00:01:41,610 --> 00:01:45,970
لذلك مرة أخرى في الأسبوع 0، عدد الصفحات
في دفتر الهاتف وكان ن.

40
00:01:45,970 --> 00:01:47,550
عدد الطلاب
في الغرفة كان ن.

41
00:01:47,550 --> 00:01:49,630
حتى هنا، أيضا، أننا التالية
هذا النمط.

42
00:01:49,630 --> 00:01:52,800
>> الآن ن التربيعية ليس بشكل خاص
بسرعة، لذلك حاولنا أن نفعل ما هو أفضل.

43
00:01:52,800 --> 00:01:55,970
وهكذا نحن ننظر في بضعة
خوارزميات أخرى، من بينها

44
00:01:55,970 --> 00:01:57,690
كان اختيار نوع.

45
00:01:57,690 --> 00:01:59,180
لذلك كان اختيار نوع
مختلفة قليلا.

46
00:01:59,180 --> 00:02:03,130
كان أبسط تقريبا، أجرؤ على القول،
حيث بدأت في بداية

47
00:02:03,130 --> 00:02:06,740
قائمة المتطوعين لدينا وأنا فقط مرة أخرى
ومرة أخرى ومرة ​​أخرى ذهبت من خلال

48
00:02:06,740 --> 00:02:10,060
القائمة، نتف من أصغر
عنصر في وقت واحد، ووضع له أو

49
00:02:10,060 --> 00:02:13,040
لها في بداية القائمة.

50
00:02:13,040 --> 00:02:16,410
>> ولكن هذا، أيضا، بدأنا مرة واحدة للتفكير
من خلال الرياضيات وأكبر

51
00:02:16,410 --> 00:02:19,860
الصورة، فكرت كم مرة
كنت ذاهبا ذهابا وإيابا والعودة

52
00:02:19,860 --> 00:02:24,090
وهكذا، قلنا في أسوأ الحالات،
اختيار نوع، أيضا، كان ماذا؟

53
00:02:24,090 --> 00:02:24,960
ن المربعة.

54
00:02:24,960 --> 00:02:27,490
الآن في العالم الحقيقي، فإنه قد
يكون في الواقع هامشية أسرع.

55
00:02:27,490 --> 00:02:30,620
لأن مرة أخرى، لم يكن لدي للحفاظ على
التراجع مرة واحدة كنت قد فرز

56
00:02:30,620 --> 00:02:31,880
أصغر العناصر.

57
00:02:31,880 --> 00:02:35,090
ولكن إذا كنا نفكر ن كبير جدا، و
إذا كنت نوع من القيام بها في الرياضيات كما

58
00:02:35,090 --> 00:02:39,170
فعلت على متن الطائرة، مع ن التربيعية
ناقص شيء، كل شيء آخر

59
00:02:39,170 --> 00:02:41,850
إلى جانب ن التربيعية، مرة واحدة ن
يحصل كبيرة حقا، لا

60
00:02:41,850 --> 00:02:42,850
حقا يهم بقدر.

61
00:02:42,850 --> 00:02:45,470
حتى علماء الكمبيوتر، ونحن نوع من
تغض الطرف عن أصغر

62
00:02:45,470 --> 00:02:49,220
العوامل والتركيز فقط على عامل في
تعبير ذاهب الى جعل

63
00:02:49,220 --> 00:02:50,330
أكبر الفرق.

64
00:02:50,330 --> 00:02:52,840
>> حسنا، أخيرا، ونحن ننظر
في الإدراج الفرز.

65
00:02:52,840 --> 00:02:56,620
وكان هذا مماثلة في الروح، ولكن
بدلا من الذهاب من خلال تكراري و

66
00:02:56,620 --> 00:03:01,250
حدد العنصر أصغر واحد في
الوقت، وأنا بدلا من ذلك أخذت اليد التي أنا

67
00:03:01,250 --> 00:03:04,070
تم التعامل، وقررت، كل
الحق، كنت تنتمي هنا.

68
00:03:04,070 --> 00:03:06,160
ثم انتقلت إلى العنصر التالي
وقرر انه او

69
00:03:06,160 --> 00:03:07,470
لأنها تنتمي هنا.

70
00:03:07,470 --> 00:03:08,810
ثم انتقلت على وعلى.

71
00:03:08,810 --> 00:03:11,780
وأنا قد ل، على طول الطريق،
تحول هؤلاء الرجال من أجل

72
00:03:11,780 --> 00:03:13,030
إفساح المجال لهم.

73
00:03:13,030 --> 00:03:16,880
لذلك كان هذا النوع من الانعكاس العقلي
اختيار النوع الذي نحن

74
00:03:16,880 --> 00:03:18,630
دعا الإدراج الفرز.

75
00:03:18,630 --> 00:03:20,810
>> وبالتالي فإن هذه الموضوعات التي تحدث
في العالم الحقيقي.

76
00:03:20,810 --> 00:03:23,640
قبل بضع سنوات، عندما معينة
وكان عضو مجلس الشيوخ الترشح للرئاسة،

77
00:03:23,640 --> 00:03:27,160
إريك شميدت، في الوقت الرئيس التنفيذي ل
جوجل، كان في الواقع الفرصة

78
00:03:27,160 --> 00:03:28,040
لإجراء مقابلة معه.

79
00:03:28,040 --> 00:03:32,010
وكنا نظن أننا سوف تتقاسم هذه يوتيوب
مقطع بالنسبة لك هنا، إذا نحن يمكن أن يحضر

80
00:03:32,010 --> 00:03:32,950
وحدة التخزين.

81
00:03:32,950 --> 00:03:39,360
>> [تشغيل الفيديو]

82
00:03:39,360 --> 00:03:44,620
>> حتى الآن، عضو مجلس الشيوخ، وكنت هنا في جوجل،
وأود أن أفكر في الرئاسة

83
00:03:44,620 --> 00:03:46,042
كما مقابلة عمل.

84
00:03:46,042 --> 00:03:47,770
>> [ضحك]

85
00:03:47,770 --> 00:03:50,800
>> حتى الآن كان من الصعب الحصول على
وظيفة الرئيس.

86
00:03:50,800 --> 00:03:52,480
وأنت تسير من خلال
قسوة الآن.

87
00:03:52,480 --> 00:03:54,330
كما انها من الصعب الحصول على وظيفة في جوجل.

88
00:03:54,330 --> 00:03:59,610
لدينا ونسأل الأسئلة
المرشحين أسئلتنا.

89
00:03:59,610 --> 00:04:02,250
وهذا هو واحد من لاري شويمر.

90
00:04:02,250 --> 00:04:05,325
>> [ضحك]

91
00:04:05,325 --> 00:04:06,400
أنت رفاق أعتقد أنا تمزح؟

92
00:04:06,400 --> 00:04:08,750
انها هنا.

93
00:04:08,750 --> 00:04:12,110
ما هي الطريقة الأكثر فعالية ل
فرز الأعداد الصحيحة اثنين مليون بت؟

94
00:04:12,110 --> 00:04:15,810
>> [ضحك]

95
00:04:15,810 --> 00:04:18,260
>> حسنا، اه -

96
00:04:18,260 --> 00:04:19,029
>> -أنا آسف.

97
00:04:19,029 --> 00:04:19,745
ربما ينبغي لنا -

98
00:04:19,745 --> 00:04:21,000
>> لا، لا، لا، لا، لا.

99
00:04:21,000 --> 00:04:21,470
>> ذلك ليس ل-

100
00:04:21,470 --> 00:04:22,185
موافق.

101
00:04:22,185 --> 00:04:25,328
>> -I أعتقد أن فقاعة سوف الفرز
تكون طريقة خاطئة للذهاب.

102
00:04:25,328 --> 00:04:26,792
>> [ضحك]

103
00:04:26,792 --> 00:04:28,510
>> [هتاف والتصفيق]

104
00:04:28,510 --> 00:04:31,211
>> تعال، الذي قال له ذلك؟

105
00:04:31,211 --> 00:04:32,155
موافق.

106
00:04:32,155 --> 00:04:33,350
>> [END تشغيل الفيديو]

107
00:04:33,350 --> 00:04:35,070
>> DAVID مالان: وهكذا فإنه يوجد لديك.

108
00:04:35,070 --> 00:04:39,600
لذلك بدأنا في تحديد هذه تشغيل
مرات، إذا جاز التعبير، مع شيء

109
00:04:39,600 --> 00:04:43,480
دعا تدوين مقارب، وهو
فقط في اشارة الى لدينا نوع من تحول

110
00:04:43,480 --> 00:04:47,420
غضت الطرف عن تلك العوامل أصغر و
يبحث فقط في وقت التشغيل،

111
00:04:47,420 --> 00:04:51,250
أداء هذه الخوارزميات،
كما ن يحصل كبيرة حقا مع مرور الوقت.

112
00:04:51,250 --> 00:04:55,110
وهكذا قدمنا ​​كبيرة وكبيرة O O.
تمثل شيئا كنا نظن

113
00:04:55,110 --> 00:04:57,000
باعتبارها من الحد الأعلى.

114
00:04:57,000 --> 00:04:59,570
وفعلا، باري، يمكننا خفض
من هيئة التصنيع العسكري قليلا؟

115
00:04:59,570 --> 00:05:01,040
>> كنا نظن هذا هو الحد الأعلى.

116
00:05:01,040 --> 00:05:04,710
يعني يا كبيرة جدا ن المربعة التي في
في أسوأ الحالات، شيء من هذا القبيل

117
00:05:04,710 --> 00:05:07,780
أن اختيار نوع اتخاذ
ن التربيعية الخطوات.

118
00:05:07,780 --> 00:05:10,310
أو شيء من هذا القبيل الإدراج الفرز
سوف ن التربيعية الخطوات.

119
00:05:10,310 --> 00:05:15,150
الآن لشيء من هذا القبيل الإدراج
نوع، ما كان أسوأ الحالات؟

120
00:05:15,150 --> 00:05:18,200
نظرا صفيف، ما هو أسوأ
السيناريو المحتمل أنك قد تجد

121
00:05:18,200 --> 00:05:20,650
تواجه نفسك؟

122
00:05:20,650 --> 00:05:21,860
>> انها الوراء تماما، أليس كذلك؟

123
00:05:21,860 --> 00:05:24,530
لأنه إذا كان هذا الخلف تماما،
ما عليك القيام به في مجموعها الكثير من العمل.

124
00:05:24,530 --> 00:05:26,420
لأنه إذا كنت الوراء تماما،
وأنت تسير لتجد

125
00:05:26,420 --> 00:05:28,840
أكبر عنصر هنا، على الرغم من
انه ينتمي الى هناك.

126
00:05:28,840 --> 00:05:31,140
لذلك كنت أريد أن أقول، كل الحق، في
هذه اللحظة في الوقت المناسب، كنت تنتمي هنا،

127
00:05:31,140 --> 00:05:32,310
لذلك أنت تترك وحدها.

128
00:05:32,310 --> 00:05:35,425
>> ثم كنت أدرك، أوه، اللعنة، لقد ل
نقل هذا العنصر أصغر قليلا ل

129
00:05:35,425 --> 00:05:36,470
يسار لك.

130
00:05:36,470 --> 00:05:38,770
ثم يجب أن أقوم به ذلك مرة أخرى
ومرة أخرى ومرة ​​أخرى.

131
00:05:38,770 --> 00:05:41,410
وإذا مشيت ذهابا وإيابا، ل
ستشعر نوع من أداء

132
00:05:41,410 --> 00:05:45,540
أن الخوارزمية، لأن أنا كنت باستمرار
خلط الجميع لأسفل في

133
00:05:45,540 --> 00:05:46,510
مجموعة لإفساح المجال لذلك.

134
00:05:46,510 --> 00:05:47,750
ذلك أن أسوأ الحالات.

135
00:05:47,750 --> 00:05:48,570
>> على النقيض من ذلك -

136
00:05:48,570 --> 00:05:50,320
وكان هذا التشويق في المرة السابقة -

137
00:05:50,320 --> 00:05:54,065
قلنا أن الإدراج الفرز
كان أوميغا ماذا؟

138
00:05:54,065 --> 00:05:57,530
ما هو أفضل حالة تشغيل
وقت الإدراج الفرز؟

139
00:05:57,530 --> 00:05:58,520
حتى انها في الواقع ن.

140
00:05:58,520 --> 00:06:00,980
كان ذلك الفراغ الذي غادرنا
على متن الطائرة آخر مرة.

141
00:06:00,980 --> 00:06:03,160
>> وانها أوميغا ن لماذا؟

142
00:06:03,160 --> 00:06:06,630
حسنا، في أفضل حال، ما هو
الإدراج الفرز ستكون سلم؟

143
00:06:06,630 --> 00:06:09,830
كذلك، قائمة وهذا ما فرزها تماما
بالفعل، والعمل الحد الأدنى للقيام به.

144
00:06:09,830 --> 00:06:12,460
ولكن ما هو أنيق حول نوع الإدراج
هو أن لأنه يبدأ من هنا و

145
00:06:12,460 --> 00:06:15,340
يقرر، أوه، كنت عدد
واحد، كنت تنتمي هنا.

146
00:06:15,340 --> 00:06:16,970
أوه، يا له من الحظ الجيد.

147
00:06:16,970 --> 00:06:17,740
>> كنت في المركز الثاني.

148
00:06:17,740 --> 00:06:19,030
أنت أيضا تنتمي هنا.

149
00:06:19,030 --> 00:06:21,010
رقم ثلاثة، وحتى أفضل،
كنت تنتمي هنا.

150
00:06:21,010 --> 00:06:25,210
بمجرد أن يحصل على نهاية
القائمة، في هذا النوع الإدراج شبة الكود

151
00:06:25,210 --> 00:06:28,010
أن مشينا من خلال لفظيا
آخر مرة، انها فعلت.

152
00:06:28,010 --> 00:06:32,790
ولكن اختيار نوع، على النقيض من ذلك،
أبقى يفعل ماذا؟

153
00:06:32,790 --> 00:06:35,260
>> تبقى مستمرة من خلال قائمة
مرة أخرى ومرة ​​أخرى ومرة ​​أخرى.

154
00:06:35,260 --> 00:06:39,160
لأن الفكرة الرئيسية لم يكن هناك سوى
مرة واحدة كنت قد بحثت عن وسيلة ل

155
00:06:39,160 --> 00:06:42,500
نهاية القائمة يمكنك أن تكون على يقين
أن العنصر الذي حددته كان

156
00:06:42,500 --> 00:06:45,560
في الواقع أصغر عنصر حاليا.

157
00:06:45,560 --> 00:06:48,920
لذلك فان هذه النماذج العقلية مختلفة انهاء
تصل الغلة بعض جدا في العالم الحقيقي

158
00:06:48,920 --> 00:06:53,130
الاختلافات بالنسبة لنا، وكذلك هذه
الاختلافات مقارب النظرية.

159
00:06:53,130 --> 00:06:56,910
>> وذلك فقط لخلاصة، إذن، يا كبير من ن
مربع، شاهدنا عدد قليل من هذه

160
00:06:56,910 --> 00:06:58,350
خوارزميات حتى الآن.

161
00:06:58,350 --> 00:06:59,580
O كبيرة من ن؟

162
00:06:59,580 --> 00:07:02,870
ما هو خوارزمية التي يمكن أن
أن يقال أن تكون يا كبير من ن؟

163
00:07:02,870 --> 00:07:06,930
في أسوأ الحالات، فإنه يأخذ
عدد خطية من الخطوات.

164
00:07:06,930 --> 00:07:07,810
>> موافق، والبحث الخطي.

165
00:07:07,810 --> 00:07:10,470
وفي أسوأ الحالات، حيث هو
العنصر الذي تبحث عنه عند

166
00:07:10,470 --> 00:07:12,950
تطبيق البحث الخطي؟

167
00:07:12,950 --> 00:07:14,680
>> حسنا، في أسوأ الحالات،
انها ليست حتى هناك.

168
00:07:14,680 --> 00:07:17,000
أو في أسوأ الحالات الثانية، انها
كل وسيلة في نهاية المطاف، وهو

169
00:07:17,000 --> 00:07:18,880
زائد أو ناقص فرق من خطوة واحدة.

170
00:07:18,880 --> 00:07:21,180
حتى في نهاية المطاف،
يمكننا القول انها خطية.

171
00:07:21,180 --> 00:07:23,910
سوف يا كبير من ن يكون البحث الخطي،
لأنه في أسوأ الحالات، و

172
00:07:23,910 --> 00:07:26,610
العنصر ليس حتى هناك أو انها
كل وسيلة في نهاية المطاف.

173
00:07:26,610 --> 00:07:29,370
>> حسنا، يا كبير من سجل ن.

174
00:07:29,370 --> 00:07:32,760
لم نتحدث بقدر كبير من التفصيل حول
هذا، ولكن شاهدنا هذا من قبل.

175
00:07:32,760 --> 00:07:36,840
ما يعمل في ما يسمى لوغاريتمي
الوقت، في أسوأ الحالات؟

176
00:07:36,840 --> 00:07:38,500
>> نعم، البحث الثنائي بذلك.

177
00:07:38,500 --> 00:07:42,930
والبحث الثنائي في أسوأ الحالات
قد يكون العنصر في مكان ما

178
00:07:42,930 --> 00:07:45,640
الوسط، أو في مكان ما
داخل مجموعة.

179
00:07:45,640 --> 00:07:48,040
ولكن فقط تجد أنه بمجرد
تقسيم القائمة إلى النصف، في

180
00:07:48,040 --> 00:07:48,940
النصف، في النصف، في النصف.

181
00:07:48,940 --> 00:07:50,200
ثم فويلا، انها هناك.

182
00:07:50,200 --> 00:07:52,500
أو مرة أخرى، أسوأ الحالات،
انها ليست حتى هناك.

183
00:07:52,500 --> 00:07:56,770
ولكن كنت لا تعرف أنه ليس هناك
حتى يمكنك الوصول إلى هذا النوع من الماضي

184
00:07:56,770 --> 00:08:00,470
من أسفل إلى معظم العناصر عن طريق خفض
وبمقدار النصف وبمقدار النصف.

185
00:08:00,470 --> 00:08:01,400
>> O كبيرة من 1.

186
00:08:01,400 --> 00:08:03,540
ولذا فإننا يمكن يا كبير من 2 يا كبير 3.

187
00:08:03,540 --> 00:08:06,260
في أي وقت كنت ترغب فقط في عدد ثابت،
نحن مجرد نوع من مجرد تبسيط

188
00:08:06,260 --> 00:08:07,280
أن يا كبير اعتبارا من 1.

189
00:08:07,280 --> 00:08:10,440
على الرغم من واقعية إذا، فإنه يأخذ
2 أو حتى 100 الخطوات، لو كان

190
00:08:10,440 --> 00:08:13,680
عدد ثابت من الخطوات،
نحن نقول فقط يا كبير 1.

191
00:08:13,680 --> 00:08:15,930
ما هو خوارزمية هذا
في O الكبيرة من 1؟

192
00:08:15,930 --> 00:08:18,350
>> الحضور: العثور على طول
من متغير.

193
00:08:18,350 --> 00:08:21,090
>> DAVID مالان: العثور على
طول متغير؟

194
00:08:21,090 --> 00:08:23,870
>> الحضور: لا، وطول
إذا تم فرزها بالفعل.

195
00:08:23,870 --> 00:08:24,160
>> DAVID مالان: جيد.

196
00:08:24,160 --> 00:08:27,850
موافق، حتى العثور على طول شيء
إذا كان طول أن شيئا ما، مثل

197
00:08:27,850 --> 00:08:30,020
صفيف، يتم تخزينها في بعض متغير.

198
00:08:30,020 --> 00:08:33,380
لأنك يمكن أن مجرد قراءة المتغير،
أو طباعة المتغير، أو

199
00:08:33,380 --> 00:08:34,960
فقط الوصول إلى هذا المتغير عموما.

200
00:08:34,960 --> 00:08:37,299
وفويلا، وهذا يستغرق وقتا ثابتا.

201
00:08:37,299 --> 00:08:38,909
>> على النقيض من ذلك، والتفكير مرة أخرى إلى نقطة الصفر.

202
00:08:38,909 --> 00:08:42,460
التفكير مرة أخرى إلى الأسبوع الأول من C،
الدعوة فقط والطباعة printf

203
00:08:42,460 --> 00:08:46,240
شيء ما على الشاشة يمكن القول
وقت ثابت، لأنه يأخذ فقط

204
00:08:46,240 --> 00:08:50,880
بعض عدد من دورات وحدة المعالجة المركزية لإظهار
أن النص على الشاشة.

205
00:08:50,880 --> 00:08:52,720
أو الانتظار - أليس كذلك؟

206
00:08:52,720 --> 00:08:56,430
وإلا كيف يمكن لنا نموذج ل
أداء printf؟

207
00:08:56,430 --> 00:09:00,420
شخص ما من شأنه أحب أن نختلف، أن
ربما انها ليست حقا وقت ثابت؟

208
00:09:00,420 --> 00:09:03,600
في ما تشغيل القوة printf إحساس
الوقت، الطباعة الواقع على سلسلة

209
00:09:03,600 --> 00:09:05,580
الشاشة، يكون شيئا
غير ثابتة.

210
00:09:05,580 --> 00:09:07,860
>> الحضور: [غير مسموع].

211
00:09:07,860 --> 00:09:08,230
>> DAVID مالان: نعم.

212
00:09:08,230 --> 00:09:09,300
لذلك يعتمد على وجهة نظرنا.

213
00:09:09,300 --> 00:09:13,390
إذا كنا نعتقد فعلا من المدخلات ل
printf بأنها السلسلة، و

214
00:09:13,390 --> 00:09:16,380
وبالتالي نقيس حجم هذا
مساهمة من قبل طوله - السماح لذلك ندعو

215
00:09:16,380 --> 00:09:17,780
أن طول ن وكذلك -

216
00:09:17,780 --> 00:09:21,990
يمكن القول، هو في حد ذاته printf يا كبير من ن
لأنه ذاهب الى اتخاذ لكم ن الخطوات

217
00:09:21,990 --> 00:09:24,750
لطباعة كل تلك ن
حرفا، على الأرجح.

218
00:09:24,750 --> 00:09:27,730
على الأقل إلى حد أن نفترض
أنه ربما انها تستخدم لحلقة

219
00:09:27,730 --> 00:09:28,560
تحت غطاء محرك السيارة.

220
00:09:28,560 --> 00:09:30,860
>> ولكن علينا أن ننظر في ذلك
رمز لنفهم على نحو أفضل.

221
00:09:30,860 --> 00:09:33,650
وبالفعل، بمجرد بدء الرجال
تحليل الخوارزميات الخاصة بك، عليك

222
00:09:33,650 --> 00:09:34,900
تفعل ذلك تماما حرفيا.

223
00:09:34,900 --> 00:09:37,765
نوع من مقلة العين التعليمة البرمجية الخاصة بك والتفكير
عن - كل الحق، ولدي هذه الحلقة

224
00:09:37,765 --> 00:09:41,870
هنا أو لدي حلقات متداخلة هنا،
وهذا ما تنوي القيام به ن ن الأشياء مرات،

225
00:09:41,870 --> 00:09:46,050
ويمكنك نوع من التفكير طريقك
خلال التعليمات البرمجية، حتى لو كان

226
00:09:46,050 --> 00:09:47,980
شبة الكود ورمز لا الفعلي.

227
00:09:47,980 --> 00:09:49,730
>> فكيف أوميغا ن التربيعية؟

228
00:09:49,730 --> 00:09:53,582
ما كان خوارزمية في أفضل
الحالة، لا يزال استغرق ن التربيعية الخطوات؟

229
00:09:53,582 --> 00:09:54,014
نعم؟

230
00:09:54,014 --> 00:09:54,880
>> الحضور: [غير مسموع].

231
00:09:54,880 --> 00:09:55,900
>> DAVID مالان: حتى اختيار نوع.

232
00:09:55,900 --> 00:09:59,150
لأنه في هذه المشكلة خفضت حقا
إلى حقيقة أن مرة أخرى، وأنا لا أعرف

233
00:09:59,150 --> 00:10:02,600
لقد وجدت أصغر الحالية حتى
لقد راجعت جميع العناصر الرتق.

234
00:10:02,600 --> 00:10:08,050
حتى أوميغا، ويقول، ن، ونحن
جاء للتو مع واحد.

235
00:10:08,050 --> 00:10:09,300
الإدراج الفرز.

236
00:10:09,300 --> 00:10:12,370
إذا حدث القائمة ليتم فرزها
بالفعل، في أفضل الأحوال لدينا فقط

237
00:10:12,370 --> 00:10:15,090
لجعل مرور واحد من خلال ذلك،
وعند هذه النقطة نحن على يقين.

238
00:10:15,090 --> 00:10:17,890
ثم ما يمكن أن يقال
أن تكون خطية، لعلى يقين.

239
00:10:17,890 --> 00:10:20,570
>> ماذا عن أوميغا من 1؟

240
00:10:20,570 --> 00:10:23,790
ما هي، في أفضل الأحوال، قد يستغرق
عدد ثابت من الخطوات؟

241
00:10:23,790 --> 00:10:27,220
البحث الخطي ذلك، إذا كنت مجرد الحصول على محظوظ
وعنصر كنت تبحث

242
00:10:27,220 --> 00:10:31,000
هو الحق في بداية القائمة،
إذا كان هذا هو المكان الذي بدأنا الخاص

243
00:10:31,000 --> 00:10:33,070
اجتياز خطية من تلك القائمة.

244
00:10:33,070 --> 00:10:35,180
>> وهذا صحيح ل
عدد من الأمور.

245
00:10:35,180 --> 00:10:37,660
على سبيل المثال، حتى ثنائي
البحث هو أوميغا 1.

246
00:10:37,660 --> 00:10:40,310
لأن ما إذا كنت تحصل على الرتق حقا
الحظ وصفعة، الداب في منتصف

247
00:10:40,310 --> 00:10:42,950
الصفيف الخاص بك هو رقم
كنت تبحث عنه؟

248
00:10:42,950 --> 00:10:45,730
حتى تتمكن من الحصول على الحظ هناك، كذلك.

249
00:10:45,730 --> 00:10:49,190
>> هذا واحد، أخيرا، أوميغا ن ن سجل.

250
00:10:49,190 --> 00:10:52,573
حتى ن ن تسجيل، ونحن لم أكن حقا
الحديث عن بعد، ولكن -

251
00:10:52,573 --> 00:10:53,300
>> الحضور: دمج النوع؟

252
00:10:53,300 --> 00:10:53,960
>> DAVID مالان: دمج النوع.

253
00:10:53,960 --> 00:10:56,920
كان هذا هو التشويق من الزمن الماضي،
حيث اقترحنا، وأظهرنا

254
00:10:56,920 --> 00:10:58,600
بصريا، أن هناك الخوارزميات.

255
00:10:58,600 --> 00:11:02,470
ودمج نوع واحد فقط من هذا القبيل
الخوارزمية التي هي في الأساس أسرع

256
00:11:02,470 --> 00:11:03,450
من بعض هؤلاء الرجال الآخرين.

257
00:11:03,450 --> 00:11:07,800
في الواقع، ودمج القصير ليس فقط في
أفضل الأحوال ن ن تسجيل، في أسوأ

258
00:11:07,800 --> 00:11:09,460
حالة ن ن سجل.

259
00:11:09,460 --> 00:11:14,540
وعندما يكون لديك هذا صدفة من
أوميغا ويا كبير يجري نفس الشيء؟

260
00:11:14,540 --> 00:11:17,310
نحن يمكن أن تصف الواقع أنه ما
دعا ثيتا، على الرغم من انها

261
00:11:17,310 --> 00:11:18,220
أقل قليلا المشتركة.

262
00:11:18,220 --> 00:11:21,730
ولكن هذا يعني فقط أن حدود اثنين،
في هذه الحالة، هي نفسها.

263
00:11:21,730 --> 00:11:25,770
>> لذلك دمج النوع، ما معنى هذا
يغلي في الواقع إلى بالنسبة لنا؟

264
00:11:25,770 --> 00:11:27,000
كذلك، تذكر الدافع.

265
00:11:27,000 --> 00:11:30,340
اسمحوا لي سحب ما يصل الرسوم المتحركة أخرى
ونحن لم ننظر في الوقت الماضي.

266
00:11:30,340 --> 00:11:33,390
هذا واحد، نفس الفكرة، ولكن
انها أكبر قليلا.

267
00:11:33,390 --> 00:11:36,160
وانا ذاهب الى المضي قدما ونشير
أولا - لدينا الإدراج الفرز على

268
00:11:36,160 --> 00:11:39,410
أعلى اليسار، ثم اختيار نوع،
فقاعة النوع، وزوجين من أنواع أخرى -

269
00:11:39,410 --> 00:11:42,670
قذيفة وسريعة - أننا لم تحدث
حول، وكومة ودمج النوع.

270
00:11:42,670 --> 00:11:47,090
>> وذلك على الأقل في محاولة للتركيز عينيك على
المراكز الثلاثة الاولى على اليسار ومن ثم

271
00:11:47,090 --> 00:11:49,120
دمج النوع عندما كنت فوق
هذا السهم الأخضر.

272
00:11:49,120 --> 00:11:51,900
لكني ساترك كل منهم تشغيل، فقط ل
تعطيك إحساسا للتنوع

273
00:11:51,900 --> 00:11:53,980
الخوارزميات التي توجد في العالم.

274
00:11:53,980 --> 00:11:56,180
انا ذاهب الى السماح لهذا المدى
لثوان معدودة.

275
00:11:56,180 --> 00:11:59,640
وإذا كنت تركز عينيك - اختيار ل
الخوارزمية، والتركيز على ذلك لمجرد

276
00:11:59,640 --> 00:12:02,970
ثانية - عليك أن تبدأ في رؤية
النمط الذي انها المنفذة.

277
00:12:02,970 --> 00:12:04,530
>> دمج النوع، لاحظ، هو القيام به.

278
00:12:04,530 --> 00:12:06,430
نوع الكومة، النوع السريع، وشركة شل -

279
00:12:06,430 --> 00:12:09,480
هكذا يبدو قدمنا ​​ثلاثة
أسوأ خوارزميات الاسبوع الماضي.

280
00:12:09,480 --> 00:12:12,960
ولكن هذا امر جيد اننا هنا اليوم ل
ننظر في دمج النوع، والتي هي واحدة من

281
00:12:12,960 --> 00:12:16,500
أسهل منها هو أن ننظر إلى، حتى
على الرغم من أنه من المحتمل أن ينحني عقلك

282
00:12:16,500 --> 00:12:17,490
قليلا فقط.

283
00:12:17,490 --> 00:12:21,130
هنا يمكننا أن نرى فقط كم
تمتص اختيار نوع.

284
00:12:21,130 --> 00:12:24,600
>> ولكن على الجانب الآخر، انها
حقا من السهل تنفيذها.

285
00:12:24,600 --> 00:12:28,160
وربما لمجموعة P 3، وهذا هو واحد من
خوارزميات اخترت لتنفيذ

286
00:12:28,160 --> 00:12:28,960
للطبعة القياسية.

287
00:12:28,960 --> 00:12:30,970
ما يرام تماما، صحيح تماما.

288
00:12:30,970 --> 00:12:35,210
>> ولكن مرة أخرى، كما ن يحصل كبيرة، إذا كنت
اختيار لتنفيذ خوارزمية أسرع

289
00:12:35,210 --> 00:12:39,020
مثل دمج النوع، الاحتمالات هي في أكبر و
المدخلات أكبر، التعليمات البرمجية الخاصة بك هو مجرد

290
00:12:39,020 --> 00:12:39,800
الذهاب لتشغيل أسرع.

291
00:12:39,800 --> 00:12:41,090
موقع الويب الخاص بك هو الذهاب إلى العمل أفضل.

292
00:12:41,090 --> 00:12:42,650
المستخدمين ستكون أكثر سعادة.

293
00:12:42,650 --> 00:12:45,280
وحتى لا تكون هذه الآثار
إعطاء الواقع

294
00:12:45,280 --> 00:12:47,350
لنا بعض أعمق الفكر.

295
00:12:47,350 --> 00:12:49,990
>> لذلك دعونا نلقي نظرة على ما الدمج
نوع هو في الواقع كل شيء.

296
00:12:49,990 --> 00:12:52,992
الشيء هو أن تبرد دمج
هذا النوع فقط.

297
00:12:52,992 --> 00:12:56,300
وهذا هو، مرة أخرى، ما كنا يسمى
شبة الكود، يجري شبة الكود

298
00:12:56,300 --> 00:12:57,720
الإنجليزية مثل بناء الجملة.

299
00:12:57,720 --> 00:12:59,890
والبساطة هي
نوع من رائعة.

300
00:12:59,890 --> 00:13:02,840
>> لذلك على المدخلات من العناصر ن - بحيث
يعني فقط، وهنا صفيف.

301
00:13:02,840 --> 00:13:04,000
انها حصلت على ن الأشياء فيه.

302
00:13:04,000 --> 00:13:05,370
هذا كل ما نقوله هناك.

303
00:13:05,370 --> 00:13:07,560
>> إذا كان n أقل من 2، والعودة.

304
00:13:07,560 --> 00:13:08,640
لذلك كان هذا هو الحال تافهة فقط.

305
00:13:08,640 --> 00:13:12,580
إذا كان n أقل من 2، ثم من الواضح انها
1 أو 0، وفي هذه الحالة الشيء

306
00:13:12,580 --> 00:13:14,780
يتم فرز بالفعل أو غير موجودة،
حتى مجرد العودة.

307
00:13:14,780 --> 00:13:15,900
هناك شيء للقيام به.

308
00:13:15,900 --> 00:13:18,360
ذلك أن حالة بسيطة لنتف قبالة.

309
00:13:18,360 --> 00:13:20,110
>> آخر، لدينا ثلاث خطوات.

310
00:13:20,110 --> 00:13:23,650
فرز النصف الأيسر من العناصر، نوع
النصف الأيمن من العناصر،

311
00:13:23,650 --> 00:13:26,650
ثم دمج شطري فرزها.

312
00:13:26,650 --> 00:13:29,400
ما هو مثير للاهتمام هنا هو أن
أنا نوع من التسيير، أليس كذلك؟

313
00:13:29,400 --> 00:13:32,300
هناك نوع من تعريف دائري
لهذه الخوارزمية.

314
00:13:32,300 --> 00:13:35,986
بأي معنى هذا الخوارزمية
التعميم التعريف؟

315
00:13:35,986 --> 00:13:37,850
>> الحضور: [غير مسموع].

316
00:13:37,850 --> 00:13:41,670
>> DAVID مالان: نعم، خوارزمية الفرز بلدي،
اثنين من خطواتها هي "نوع

317
00:13:41,670 --> 00:13:44,640
شيء ما ". وبحيث يطرح
السؤال، حسنا، ما أنا ذاهب الى استخدام

318
00:13:44,640 --> 00:13:46,460
لفرز النصف الأيسر
والنصف الأيمن؟

319
00:13:46,460 --> 00:13:49,600
والجمال هنا هو أنه على الرغم من
مرة أخرى، وهذا هو العقل والانحناء

320
00:13:49,600 --> 00:13:54,030
جزء يحتمل، يمكنك استخدام نفس
خوارزمية لفرز النصف الأيسر.

321
00:13:54,030 --> 00:13:54,700
>> ولكن الانتظار لمدة دقيقة.

322
00:13:54,700 --> 00:13:57,070
عندما كنت وقال لفرز
النصف الأيسر، ما هما

323
00:13:57,070 --> 00:13:58,240
الخطوات ستكون في المرة القادمة؟

324
00:13:58,240 --> 00:14:00,550
سنقوم فرز النصف الأيسر من
النصف الأيسر والأيمن

325
00:14:00,550 --> 00:14:01,420
نصف النصف الأيسر.

326
00:14:01,420 --> 00:14:04,430
اللعنة، كيف يمكنني فرز هذين
نصفين، أو أرباع، والآن؟

327
00:14:04,430 --> 00:14:05,260
>> ولكن هذا موافق.

328
00:14:05,260 --> 00:14:07,830
لدينا خوارزمية الفرز هنا.

329
00:14:07,830 --> 00:14:10,660
وعلى الرغم من أنك قد تقلق في
أولا هذا هو نوع من لانهائية

330
00:14:10,660 --> 00:14:12,780
حلقة، انها دورة هذا أبدا
الذهاب الى النهاية - هو ذاهب ل

331
00:14:12,780 --> 00:14:15,770
ينتهي بمجرد ما يحدث؟

332
00:14:15,770 --> 00:14:16,970
مرة واحدة n هو أقل من 2.

333
00:14:16,970 --> 00:14:19,180
التي في النهاية سوف يحدث،
لأنه إذا واصلتم بمقدار النصف و

334
00:14:19,180 --> 00:14:23,020
تخفيض في تخفيض هذه نصفين، وبالتأكيد
في نهاية المطاف وأنت تسير لانهاء

335
00:14:23,020 --> 00:14:25,350
مع فقط 1 أو 0 العناصر.

336
00:14:25,350 --> 00:14:28,500
وعند هذه النقطة، هذه الخوارزمية
يقول الانتهاء من ذلك.

337
00:14:28,500 --> 00:14:31,020
>> وبالتالي فإن السحر الحقيقي في هذا
يبدو خوارزمية ليكون في

338
00:14:31,020 --> 00:14:33,470
أن الخطوة النهائية، ودمج.

339
00:14:33,470 --> 00:14:37,190
هذه الفكرة بسيطة دمج اثنين فقط
الأشياء، وهذا ما يحدث في نهاية المطاف

340
00:14:37,190 --> 00:14:40,920
للسماح لنا لفرز مجموعة من،
دعنا نقول، ثمانية عناصر.

341
00:14:40,920 --> 00:14:44,410
وذلك لدي ثماني كرات المزيد من الضغط حتى
هنا، ثماني قطع من الورق، واحد

342
00:14:44,410 --> 00:14:45,500
جوجل زجاج -

343
00:14:45,500 --> 00:14:46,140
الذي أحصل على الاحتفاظ بها.

344
00:14:46,140 --> 00:14:46,960
>> [ضحك]

345
00:14:46,960 --> 00:14:48,970
>> DAVID مالان: إذا كنا قد يستغرق ثمانية
المتطوعين، ودعونا نرى ما اذا كنا نستطيع

346
00:14:48,970 --> 00:14:51,430
تلعب هذه، لذلك.

347
00:14:51,430 --> 00:14:52,500
نجاح باهر، موافق.

348
00:14:52,500 --> 00:14:53,565
علوم الكمبيوتر هو الحصول على المتعة.

349
00:14:53,565 --> 00:14:54,320
حسنا.

350
00:14:54,320 --> 00:14:57,770
فكيف لك ثلاث،
أكبر تصل ناحية هناك.

351
00:14:57,770 --> 00:14:58,580
أربعة في الخلف.

352
00:14:58,580 --> 00:15:02,220
وكيف حول سنفعل لك
ثلاثة في هذا الصف؟

353
00:15:02,220 --> 00:15:03,390
وأربعة في الجبهة.

354
00:15:03,390 --> 00:15:04,920
حتى تتمكن ثمانية، وتأتي على ما يصل.

355
00:15:04,920 --> 00:15:12,060
>> [ضحك]

356
00:15:12,060 --> 00:15:13,450
>> DAVID مالان: أنا فعلا
لست متأكدا ما هو عليه.

357
00:15:13,450 --> 00:15:14,810
هو الكرات الإجهاد؟

358
00:15:14,810 --> 00:15:16,510
مصابيح المنضدة؟

359
00:15:16,510 --> 00:15:18,650
المادة؟

360
00:15:18,650 --> 00:15:19,680
الإنترنت؟

361
00:15:19,680 --> 00:15:20,160
>> موافق.

362
00:15:20,160 --> 00:15:21,310
ويأتي ذلك على ما يصل.

363
00:15:21,310 --> 00:15:22,310
أن الذين يحبون -

364
00:15:22,310 --> 00:15:23,570
تبقي الخروج.

365
00:15:23,570 --> 00:15:24,240
دعونا نرى.

366
00:15:24,240 --> 00:15:26,460
وهذا يضعك في موقع -

367
00:15:26,460 --> 00:15:27,940
كنت في مكان واحد.

368
00:15:27,940 --> 00:15:28,670
أه أوه، انتظر لحظة.

369
00:15:28,670 --> 00:15:30,760
1، 2، 3، 4، 5، 6، 7 - أوه، جيد.

370
00:15:30,760 --> 00:15:31,310
كل الحق، نحن في حالة جيدة.

371
00:15:31,310 --> 00:15:35,130
كل الحق، لذلك الجميع لديها مقعد،
ولكن ليس على زجاج جوجل.

372
00:15:35,130 --> 00:15:36,475
اسمحوا لي أن قائمة الانتظار هذه المباراة.

373
00:15:36,475 --> 00:15:37,115
ما اسمك؟

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE: ميشيل.

375
00:15:37,440 --> 00:15:38,090
>> DAVID مالان: ميشيل؟

376
00:15:38,090 --> 00:15:42,000
كل الحق، وتحصل لتبدو وكأنها
المهوس، إذا كان هذا هو موافق.

377
00:15:42,000 --> 00:15:44,625
حسنا، أنا لا جدا، وأنا أفترض،
لمجرد لحظة.

378
00:15:44,625 --> 00:15:45,875
كل الحق، والاستعداد.

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

380
00:15:48,510 --> 00:15:50,950
كنا تحاول الخروج مع
استخدام القضية لجوجل الزجاج، ونحن

381
00:15:50,950 --> 00:15:53,750
اعتقد انه سيكون من متعة القيام به فقط
هذا عندما يكون الناس على خشبة المسرح.

382
00:15:53,750 --> 00:15:57,120
سنقوم بتسجيل العالم
من وجهة نظرهم.

383
00:15:57,120 --> 00:15:58,410
حسنا.

384
00:15:58,410 --> 00:15:59,830
لا على الأرجح ما المقصود جوجل.

385
00:15:59,830 --> 00:16:02,260
كل الحق، إذا كنت لا تمانع في ارتداء
هذه لدقائق محرجا المقبل،

386
00:16:02,260 --> 00:16:03,150
التي من شأنها أن تكون رائعة.

387
00:16:03,150 --> 00:16:08,620
>> كل الحق، لذلك لدينا هنا مجموعة من
العناصر، وأن مجموعة، وفقا ل

388
00:16:08,620 --> 00:16:11,480
قطعة من الورق في هؤلاء الناس '
الأيدي، ويتم فرزها حاليا.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: أوه، هذا غريب جدا.

390
00:16:12,050 --> 00:16:12,810
>> DAVID مالان: انها عشوائية الى حد كبير.

391
00:16:12,810 --> 00:16:15,760
ومجرد لحظة، ونحن ذاهبون لمحاولة
لتنفيذ دمج النوع معا

392
00:16:15,760 --> 00:16:17,950
ونرى فيها أن الفكرة الرئيسية هي.

393
00:16:17,950 --> 00:16:21,970
والخدعة هنا مع دمج النوع هو
شيء أننا لم يفترض حتى الآن.

394
00:16:21,970 --> 00:16:24,030
ونحن في الواقع بحاجة الى بعض
مساحة إضافية.

395
00:16:24,030 --> 00:16:26,650
وذلك ما سيكون ولا سيما
مثيرة للاهتمام في هذا هو أن هذه

396
00:16:26,650 --> 00:16:29,270
الرجال تسير على التحرك قليلا
قليلا، لأنني ذاهب لنفترض أن

397
00:16:29,270 --> 00:16:31,880
هناك مجموعة إضافية من الفضاء،
أقول، الحق وراءها.

398
00:16:31,880 --> 00:16:34,570
>> حتى لو انهم وراء كرسي، و
هذا هو مجموعة الثانوية.

399
00:16:34,570 --> 00:16:36,960
لو انهم يجلس هنا، وهذا
مجموعة الابتدائية.

400
00:16:36,960 --> 00:16:40,170
ولكن هذا هو المورد الذي لدينا
لا الاستدانة حتى الآن مع فقاعة

401
00:16:40,170 --> 00:16:42,040
نوع، مع اختيار نوع،
مع الإدراج الفرز.

402
00:16:42,040 --> 00:16:44,600
أذكر الأسبوع الماضي، والجميع فقط
نوع من أسكن في المكان.

403
00:16:44,600 --> 00:16:46,840
أنها لم تستخدم أي ذاكرة إضافية.

404
00:16:46,840 --> 00:16:49,310
التي قطعناها على أنفسنا مجالا للناس من قبل
نقل الناس حولها.

405
00:16:49,310 --> 00:16:50,580
>> لذلك هذا هو الفكرة الرئيسية، أيضا.

406
00:16:50,580 --> 00:16:53,410
هناك هذا مفاضلة، وبشكل عام في
علوم الكمبيوتر، والموارد.

407
00:16:53,410 --> 00:16:55,800
إذا كنت ترغب في تسريع شيء
مثل الوقت، وأنت تسير ل

408
00:16:55,800 --> 00:16:56,900
لديك لدفع ثمن.

409
00:16:56,900 --> 00:17:00,750
واحدة من تلك الأسعار هي في كثير من الأحيان
الفضاء، مقدار الذاكرة أو الثابت

410
00:17:00,750 --> 00:17:01,700
مساحة القرص الذي تستخدمه.

411
00:17:01,700 --> 00:17:03,640
أو، بصراحة، فإن المبلغ
الوقت مبرمج.

412
00:17:03,640 --> 00:17:06,700
كم من الوقت يستغرق لك، والإنسان،
في الواقع لتنفيذ بعض أكثر

413
00:17:06,700 --> 00:17:07,829
خوارزمية معقدة.

414
00:17:07,829 --> 00:17:09,760
ولكن لهذا اليوم، والمفاضلة
هو الزمان والمكان.

415
00:17:09,760 --> 00:17:11,930
>> إذا كان الأمر كذلك يا رفاق يمكن أن مجرد تصمد الخاص
أرقام حتى يمكننا أن نرى أن كنت

416
00:17:11,930 --> 00:17:15,839
في الواقع مطابقة 4، 2، 6، 1، 3، 7، 8.

417
00:17:15,839 --> 00:17:16,599
ممتازة.

418
00:17:16,599 --> 00:17:19,520
لذلك أنا ذاهب الى محاولة لتنسيق
الأشياء، إذا يا رفاق يمكن فقط

419
00:17:19,520 --> 00:17:21,800
اتبع بلدي الرصاص هنا.

420
00:17:21,800 --> 00:17:26,650
>> لذلك أنا ذاهب لتنفيذ، أولا،
الخطوة الأولى من شبة الكود، وهو

421
00:17:26,650 --> 00:17:29,440
على المدخلات من العناصر ن، إذا كان n هو
أقل من 2، ثم العودة.

422
00:17:29,440 --> 00:17:31,370
من الواضح، أن لا
تطبيق، لذلك نحن على هذه الخطوة.

423
00:17:31,370 --> 00:17:33,340
حتى فرز النصف الأيسر من العناصر.

424
00:17:33,340 --> 00:17:36,220
وهذا يعني انا ذاهب الى التركيز بلدي
الانتباه لمجرد لحظة على هذه

425
00:17:36,220 --> 00:17:37,310
أربعة رفاق هنا.

426
00:17:37,310 --> 00:17:39,774
كل الحق، ما يمكنني القيام به القادم؟

427
00:17:39,774 --> 00:17:40,570
>> الجمهور: فرز النصف الأيسر.

428
00:17:40,570 --> 00:17:42,780
>> DAVID مالان: حتى الآن لا بد لي من فرز
النصف الأيسر من هؤلاء الرجال.

429
00:17:42,780 --> 00:17:45,580
لأن مرة أخرى، تفترض لنفسك
الهدف من ذلك هو لفرز النصف الأيسر.

430
00:17:45,580 --> 00:17:46,440
كيف يمكنك أن تفعل ذلك؟

431
00:17:46,440 --> 00:17:49,140
ما عليك سوى اتباع التعليمات، حتى
على الرغم من أننا نفعل ذلك مرة أخرى.

432
00:17:49,140 --> 00:17:50,160
حتى فرز النصف الأيسر.

433
00:17:50,160 --> 00:17:52,030
الآن أنا الفرز هذين اللاعبين.

434
00:17:52,030 --> 00:17:53,563
ماذا يأتي بعد ذلك؟

435
00:17:53,563 --> 00:17:54,510
>> الجمهور: فرز النصف الأيسر.

436
00:17:54,510 --> 00:17:55,460
>> DAVID مالان: فرز النصف الأيسر.

437
00:17:55,460 --> 00:18:00,680
وحتى الآن هذه، هذا المقعد هنا،
هي قائمة حجم 1.

438
00:18:00,680 --> 00:18:01,365
وما اسمك مرة أخرى؟

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS ديزي: الأميرة ديزي.

440
00:18:02,390 --> 00:18:03,690
>> DAVID مالان: الأميرة ديزي هنا.

441
00:18:03,690 --> 00:18:07,470
وحتى أنها يتم فرز بالفعل، ل
القائمة هو من حجم 1.

442
00:18:07,470 --> 00:18:09,490
ما يمكنني القيام به القادم؟

443
00:18:09,490 --> 00:18:13,680
موافق، والعودة، لأن هذا هو قائمة من
حجم 1، والذي هو أقل من 2.

444
00:18:13,680 --> 00:18:14,320
ثم ما هي الخطوة التالية؟

445
00:18:14,320 --> 00:18:17,490
والآن لديك لنوع من
التراجع في عقلك.

446
00:18:17,490 --> 00:18:19,340
>> فرز النصف الأيمن، والذي هو -

447
00:18:19,340 --> 00:18:19,570
ما اسمك؟

448
00:18:19,570 --> 00:18:20,220
>> ليندا: ليندا.

449
00:18:20,220 --> 00:18:20,980
>> DAVID مالان: ليندا.

450
00:18:20,980 --> 00:18:23,210
وهكذا ماذا نفعل الآن بعد أن
لدينا قائمة من حجم 1؟

451
00:18:23,210 --> 00:18:24,440
>> الحضور: العودة.

452
00:18:24,440 --> 00:18:24,760
>> DAVID مالان: الدقيق.

453
00:18:24,760 --> 00:18:29,540
نعود الأولى، والآن ثالث
خطوة - وإذا أنا نوع من تصور من قبل

454
00:18:29,540 --> 00:18:33,490
احتضان مقعدين الآن، وأنا الآن
يجب أن دمج هذين العنصرين.

455
00:18:33,490 --> 00:18:35,530
وحتى الآن للأسف، العناصر
هي خارج الترتيب.

456
00:18:35,530 --> 00:18:39,920
ولكن حيث ان عملية دمج
يبدأ للحصول على مقنعة.

457
00:18:39,920 --> 00:18:42,410
>> إذا كان الأمر كذلك يا رفاق يمكن الوقوف فقط ل
لحظة، وانا ذاهب لحاجة، في

458
00:18:42,410 --> 00:18:44,170
لحظة، إلى الخطوة راء مقعدك.

459
00:18:44,170 --> 00:18:46,480
وإذا ليندا، وذلك لأن 2 هو
أصغر من 4، لماذا لا

460
00:18:46,480 --> 00:18:48,130
جئت في جميع أنحاء الأول؟

461
00:18:48,130 --> 00:18:48,690
البقاء هناك.

462
00:18:48,690 --> 00:18:50,520
حتى ليندا، جئت في جميع أنحاء الأول.

463
00:18:50,520 --> 00:18:53,820
>> الآن في الواقع لو كان مجرد مجموعة
أننا يمكن أن مجرد تحرك لها في الوقت الحقيقي

464
00:18:53,820 --> 00:18:55,360
من هذا الكرسي إلى هذه البقعة.

465
00:18:55,360 --> 00:18:57,770
لذلك أتصور أن أخذت بعض مستمر
عدد من الخطوات 1.

466
00:18:57,770 --> 00:18:58,480
والآن -

467
00:18:58,480 --> 00:19:01,490
ولكن نحن بحاجة إلى وضعك في
الموقع الأول هنا.

468
00:19:01,490 --> 00:19:03,930
>> والآن إذا كنت يمكن أن يأتي حولها،
كذلك، ونحن في طريقنا ل

469
00:19:03,930 --> 00:19:06,300
تكون في موقع اثنين.

470
00:19:06,300 --> 00:19:09,120
وعلى الرغم من أن هذا يبدو وكأنه انها
أخذ بعض الوقت، ما هو جميل الآن

471
00:19:09,120 --> 00:19:14,710
أن النصف الأيسر من
الآن يتم فرز النصف الأيسر.

472
00:19:14,710 --> 00:19:18,010
فما كانت الخطوة التالية، واذا كنا الآن
مزيد من الترجيع في القصة؟

473
00:19:18,010 --> 00:19:18,980
>> الحضور: نصف الحق.

474
00:19:18,980 --> 00:19:19,900
>> DAVID مالان: فرز النصف الأيمن.

475
00:19:19,900 --> 00:19:21,320
لذلك يا رفاق لديهم للقيام بذلك، كذلك.

476
00:19:21,320 --> 00:19:23,510
حتى إذا كنت يمكن الوقوف
لمجرد لحظة؟

477
00:19:23,510 --> 00:19:25,192
وما هو اسمك؟

478
00:19:25,192 --> 00:19:25,540
>> JESS: جيس.

479
00:19:25,540 --> 00:19:25,870
>> DAVID مالان: جيس.

480
00:19:25,870 --> 00:19:29,720
حسنا، الآن جيس اليسار
نصف النصف الأيمن.

481
00:19:29,720 --> 00:19:31,400
وحتى انها قائمة من حجم 1.

482
00:19:31,400 --> 00:19:32,380
انها فرز واضح.

483
00:19:32,380 --> 00:19:33,070
واسمك مرة أخرى؟

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE: ميشيل.

485
00:19:33,630 --> 00:19:35,340
>> DAVID مالان: من الواضح أن ميشيل
قائمة حجم 1.

486
00:19:35,340 --> 00:19:36,050
انها بالفعل فرزها.

487
00:19:36,050 --> 00:19:38,690
وحتى الآن السحر يحدث،
عملية دمج.

488
00:19:38,690 --> 00:19:39,790
ذلك الذي يحدث أن يأتي أولا؟

489
00:19:39,790 --> 00:19:41,560
ومن الواضح أن ميشيل.

490
00:19:41,560 --> 00:19:43,280
حتى إذا كنت يمكن أن يأتي حوالي الظهر.

491
00:19:43,280 --> 00:19:47,090
المساحة المتوفرة لدينا بالنسبة لها الآن
هو حق وراء هذا الكرسي هنا.

492
00:19:47,090 --> 00:19:51,580
والآن إذا كنت يمكن أن يعود كذلك،
لدينا الآن، أن تكون واضحة، وهما

493
00:19:51,580 --> 00:19:53,810
نصفين، كل من حجم 2 -

494
00:19:53,810 --> 00:19:57,090
وفقط من أجل تصوير، وإذا كنت
يمكن أن قليلا من مساحة -

495
00:19:57,090 --> 00:19:59,780
واحد النصف الأيسر هنا، واحد
النصف الأيمن هنا.

496
00:19:59,780 --> 00:20:01,160
>> مزيد من الترجيع في القصة.

497
00:20:01,160 --> 00:20:02,270
ما الخطوة التالية؟

498
00:20:02,270 --> 00:20:03,030
>> الجمهور: دمج.

499
00:20:03,030 --> 00:20:04,160
>> DAVID مالان: حتى الآن لدينا لدمج.

500
00:20:04,160 --> 00:20:07,490
لذلك موافق، وحتى الآن، والحمد لله، ونحن
حررت للتو أربعة كراسي.

501
00:20:07,490 --> 00:20:11,480
ولذا فإننا قد استخدمت مرتين قدر الذاكرة، ولكن
نحن يمكن أن تعطي الوجه التخبط بين

502
00:20:11,480 --> 00:20:12,330
اثنين من المصفوفات.

503
00:20:12,330 --> 00:20:14,190
لذلك ما هو الرقم الذي هو يأتي أولا؟

504
00:20:14,190 --> 00:20:14,850
حتى ميشيل، ومن الواضح.

505
00:20:14,850 --> 00:20:16,680
حتى يأتي حولها واتخاذ
مقعدك هنا.

506
00:20:16,680 --> 00:20:19,120
ثم عدد 2 ومن الواضح
المقبل، لذلك جئت هنا.

507
00:20:19,120 --> 00:20:21,520
عدد 4، رقم 6.

508
00:20:21,520 --> 00:20:23,390
ومرة أخرى، على الرغم من هناك
قليلا من المشي المعنية،

509
00:20:23,390 --> 00:20:26,010
حقا، هذه يمكن أن يحدث على الفور،
عن طريق تحريك واحد -

510
00:20:26,010 --> 00:20:26,880
موافق، لعبنا بشكل جيد.

511
00:20:26,880 --> 00:20:28,350
>> [ضحك]

512
00:20:28,350 --> 00:20:29,680
>> DAVID مالان: والآن نحن
في حالة جيدة جدا.

513
00:20:29,680 --> 00:20:34,910
النصف الأيسر من كامل
وقد تم الآن فرز المدخلات.

514
00:20:34,910 --> 00:20:37,370
كل الحق، لذلك كان لهؤلاء الرجال
الاستفادة من بلدي -

515
00:20:37,370 --> 00:20:40,340
كيف أنه في نهاية المطاف جميع الفتيات على
وغادر جميع الأولاد على حق؟

516
00:20:40,340 --> 00:20:42,450
>> موافق، لذلك بدوره الرجال 'الآن.

517
00:20:42,450 --> 00:20:44,680
ولذا فإنني لن المشي لكم من خلال
هذه الخطوات.

518
00:20:44,680 --> 00:20:46,550
سنرى ما اذا كنا نستطيع تطبيق
نفس شبة الكود.

519
00:20:46,550 --> 00:20:50,050
إذا كنت ترغب في المضي قدما والوقوف،
ويا رفاق، واسمحوا لي أن أقدم لكم هيئة التصنيع العسكري.

520
00:20:50,050 --> 00:20:52,990
معرفة ما اذا كنت لا يمكن تكرار ما
نحن فقط لم هنا على

521
00:20:52,990 --> 00:20:53,880
الطرف الآخر من القائمة.

522
00:20:53,880 --> 00:20:59,530
الذي يحتاج إلى الكلام الأول،
استنادا إلى خوارزمية؟

523
00:20:59,530 --> 00:21:03,210
لذلك شرح ما تفعلونه قبل
إجراء أية تحركات القدم.

524
00:21:03,210 --> 00:21:05,930
>> سرور 1: كل الحق، وذلك منذ
أنا النصف الأيسر من

525
00:21:05,930 --> 00:21:07,790
ترك النصف، أعود.

526
00:21:07,790 --> 00:21:08,730
أليس كذلك؟

527
00:21:08,730 --> 00:21:09,250
>> DAVID مالان: جيد.

528
00:21:09,250 --> 00:21:10,350
>> سرور 1: وبعد ذلك -

529
00:21:10,350 --> 00:21:11,800
>> DAVID مالان: من يفعل
هيئة التصنيع العسكري انتقل إلى الخطوة التالية؟

530
00:21:11,800 --> 00:21:12,920
>> سرور 1: عدد التالي.

531
00:21:12,920 --> 00:21:14,720
>> المتحدث 2: لذلك أنا النصف الأيمن
من النصف الأيسر من

532
00:21:14,720 --> 00:21:17,830
ترك النصف، وأعود.

533
00:21:17,830 --> 00:21:18,050
>> DAVID مالان: جيد.

534
00:21:18,050 --> 00:21:18,550
عودتك.

535
00:21:18,550 --> 00:21:21,855
وحتى الآن ما هو القادم بالنسبة لك حتى اثنين؟

536
00:21:21,855 --> 00:21:23,740
>> المتحدث 2: نريد معرفة من هو أصغر.

537
00:21:23,740 --> 00:21:24,200
>> DAVID مالان: بالضبط.

538
00:21:24,200 --> 00:21:24,940
نريد دمجها.

539
00:21:24,940 --> 00:21:27,590
الفضاء ونحن في طريقنا إلى استخدامها لدمج
كنت في، على الرغم من انهم

540
00:21:27,590 --> 00:21:30,250
من الواضح فرز بالفعل، ونحن في طريقنا
لمتابعة نفس الخوارزمية.

541
00:21:30,250 --> 00:21:31,560
ذلك الذي يذهب في الظهر أولا؟

542
00:21:31,560 --> 00:21:35,720
حتى 3 ثم 7.

543
00:21:35,720 --> 00:21:38,570
والآن يذهب هيئة التصنيع العسكري
لهؤلاء الرجال، موافق؟

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: لذلك أنا النصف الأيمن من
غادر نصف، وبلدي n هو أقل من

545
00:21:43,590 --> 00:21:45,048
1، لذلك أنا ذاهب لمجرد تمرير -

546
00:21:45,048 --> 00:21:46,380
>> DAVID مالان: جيد.

547
00:21:46,380 --> 00:21:49,450
>> سرور 4: أنا النصف الأيمن من
النصف الأيمن من النصف الأيمن، وأنا

548
00:21:49,450 --> 00:21:51,740
أيضا شخص واحد، لذلك أنا
الذهاب الى العودة.

549
00:21:51,740 --> 00:21:52,990
حتى الآن نحن دمجها.

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

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: حتى نعود.

552
00:21:56,150 --> 00:21:57,160
>> DAVID مالان: حتى تذهب إلى الخلف.

553
00:21:57,160 --> 00:21:59,200
حتى 5 يذهب أولا، ثم 8.

554
00:21:59,200 --> 00:22:01,240
والآن الجمهور، الذي هو
خطوة علينا أن الترجيع الآن

555
00:22:01,240 --> 00:22:02,200
العودة إلى في عقولنا؟

556
00:22:02,200 --> 00:22:02,940
>> الجمهور: دمج.

557
00:22:02,940 --> 00:22:07,270
>> DAVID مالان: دمج النصف الأيسر والأيمن
نصف النصف الأيسر الأصلي.

558
00:22:07,270 --> 00:22:08,840
وحتى الآن -

559
00:22:08,840 --> 00:22:10,520
وفقط لجعل هذا واضحا،
جعل قليلا من الفضاء

560
00:22:10,520 --> 00:22:11,690
بينك اثنين من اللاعبين.

561
00:22:11,690 --> 00:22:13,800
وحتى الآن هذا القائمتين،
اليسار واليمين.

562
00:22:13,800 --> 00:22:18,320
لذلك كيف يمكننا الآن دمج يا رفاق في
الصف الأمامي من المقاعد مرة أخرى؟

563
00:22:18,320 --> 00:22:19,600
>> 3 يذهب أولا.

564
00:22:19,600 --> 00:22:20,850
ثم 5، ومن الواضح.

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

566
00:22:23,110 --> 00:22:27,330
ثم 7، والآن 8.

567
00:22:27,330 --> 00:22:28,710
حسنا، والآن نحن؟

568
00:22:28,710 --> 00:22:29,650
>> الحضور: ليس القيام به.

569
00:22:29,650 --> 00:22:32,440
>> DAVID مالان: غير ذلك، وذلك لأن
من الواضح، هناك خطوة واحدة المتبقية.

570
00:22:32,440 --> 00:22:35,720
ولكن مرة أخرى، والسبب أنا باستخدام هذا
المصطلحات مثل "الترجيع في عقلك،"

571
00:22:35,720 --> 00:22:37,160
انها لأن هذا هو حقا
ما يحدث.

572
00:22:37,160 --> 00:22:39,610
ونحن في طريقنا من خلال كل هذه الخطوات،
ولكننا نوع من التوقف ل

573
00:22:39,610 --> 00:22:42,480
لحظة، والغوص أعمق في
الخوارزمية، والتوقف للحظة واحدة،

574
00:22:42,480 --> 00:22:45,840
الغوص أعمق في الخوارزمية، و
الآن لدينا لترجيع نوع من خلال موقعنا

575
00:22:45,840 --> 00:22:49,430
العقول والتراجع عن كل من هذه الطبقات
بعد أن قمنا نوع من تأجيلها.

576
00:22:49,430 --> 00:22:51,790
>> حتى الآن لدينا قائمتين من حجم 4.

577
00:22:51,790 --> 00:22:54,790
إذا يا رفاق يمكن الوقوف مرة الأخيرة
وجعل قليلا من مساحة هنا ل

578
00:22:54,790 --> 00:22:57,230
نوضح أن هذا هو اليسار
نصف الأصلي، و

579
00:22:57,230 --> 00:22:58,620
النصف الأيمن من الأصلي.

580
00:22:58,620 --> 00:23:01,060
من هو الرقم الأول أننا
تحتاج إلى سحب في الظهر؟

581
00:23:01,060 --> 00:23:01,870
ميشيل، بطبيعة الحال.

582
00:23:01,870 --> 00:23:03,230
>> لذلك وضعنا ميشيل هنا.

583
00:23:03,230 --> 00:23:05,080
والذي لديه عدد 2؟

584
00:23:05,080 --> 00:23:06,440
عدد 2 يأتي على ظهره أيضا.

585
00:23:06,440 --> 00:23:07,800
عدد 3؟

586
00:23:07,800 --> 00:23:08,510
ممتازة.

587
00:23:08,510 --> 00:23:16,570
عدد 4، رقم 5، رقم 6،
عدد 7، وعدد 8.

588
00:23:16,570 --> 00:23:18,850
>> موافق، لذلك شعرت الكثير
من الخطوات، لعلى يقين.

589
00:23:18,850 --> 00:23:22,390
ولكن الآن دعونا نرى إذا كنا لا يمكن تأكيد
نوع من حدسي أن هذه

590
00:23:22,390 --> 00:23:26,190
الخوارزمية بشكل أساسي، لا سيما
ن يحصل كبيرة حقا، كما رأينا

591
00:23:26,190 --> 00:23:29,170
مع الرسوم المتحركة، هو
جوهريا أسرع.

592
00:23:29,170 --> 00:23:33,400
لذلك أزعم هذه الخوارزمية، في أسوأ
القضية وحتى في أفضل الأحوال،

593
00:23:33,400 --> 00:23:36,160
ويا كبير من المرات ن ن تسجيل.

594
00:23:36,160 --> 00:23:39,160
وهذا هو، وهناك بعض جوانب هذا
الخوارزمية التي تأخذ ن الخطوات، ولكن

595
00:23:39,160 --> 00:23:43,110
هناك جانب آخر في مكان ما
أن التكرار، أن حلقات، أن

596
00:23:43,110 --> 00:23:44,410
يأخذ السجل ن الخطوات.

597
00:23:44,410 --> 00:23:49,154
يمكن أن نضع الإصبع على ما لدينا تلك
ورقمين في اشارة الى؟

598
00:23:49,154 --> 00:23:51,320
كذلك، حيث -

599
00:23:51,320 --> 00:23:54,160
من أين هيئة التصنيع العسكري تذهب؟

600
00:23:54,160 --> 00:23:58,660
>> سرور 1: هل سجل ن يكون
كسر لنا الى قسمين -

601
00:23:58,660 --> 00:23:59,630
تقسيم من قبل اثنين، أساسا.

602
00:23:59,630 --> 00:24:00,120
>> DAVID مالان: بالضبط.

603
00:24:00,120 --> 00:24:03,000
أي وقت نراه في أي خوارزمية بالتالي
الآن، كان هناك هذا النمط من

604
00:24:03,000 --> 00:24:04,200
تقسيم، تقسيم، تقسيم.

605
00:24:04,200 --> 00:24:05,700
وانها خفضت عادة
لشيء أن يكون

606
00:24:05,700 --> 00:24:07,100
لوغاريتمي، تسجيل قاعدة 2.

607
00:24:07,100 --> 00:24:10,180
ولكن يمكن أن يكون حقا أي شيء،
ولكن تسجيل قاعدة 2.

608
00:24:10,180 --> 00:24:11,330
>> الآن ماذا عن ن؟

609
00:24:11,330 --> 00:24:14,550
أستطيع أن أرى أننا نوع من تقسيم لك
الرجال - تقسيم لك، وتنقسم لك،

610
00:24:14,550 --> 00:24:15,910
قسمت لك، وتنقسم لك.

611
00:24:15,910 --> 00:24:18,760
حيث لا نهاية تأتي من؟

612
00:24:18,760 --> 00:24:19,810
>> لذلك فمن دمج.

613
00:24:19,810 --> 00:24:20,610
لأن التفكير في الامر.

614
00:24:20,610 --> 00:24:25,420
عند دمج ثمانية أشخاص معا،
حيث نصفهم من مجموعة من أربعة

615
00:24:25,420 --> 00:24:27,770
والنصف الآخر هي آخر
مجموعة من أربعة، كيف يمكنك أن تذهب

616
00:24:27,770 --> 00:24:28,820
عن القيام دمج؟

617
00:24:28,820 --> 00:24:30,830
حسنا، فعلت ذلك يا رفاق
إلى حد ما بشكل حدسي.

618
00:24:30,830 --> 00:24:34,140
>> ولكن إذا كنت فعلت هذا بدلا أكثر من ذلك بقليل
منهجي، وأنا قد أشار في

619
00:24:34,140 --> 00:24:38,090
في أقصى اليسار أول شخص مع يساري
ناحية، وأشار في أقصى اليسار شخص

620
00:24:38,090 --> 00:24:42,080
من أن نصف مع يدي اليمنى، و
فقط مشى في وقت لاحق من خلال

621
00:24:42,080 --> 00:24:46,990
القائمة، مشيرا في الوقت ذاته أصغر عنصر
في كل مرة، والانتقال إصبعي على و

622
00:24:46,990 --> 00:24:48,970
أكثر حسب الحاجة في جميع أنحاء القائمة.

623
00:24:48,970 --> 00:24:51,890
ولكن ما هو مفتاح عن هذا الدمج
العملية هي أنا بمقارنة هذه الأزواج

624
00:24:51,890 --> 00:24:53,460
من العناصر.

625
00:24:53,460 --> 00:24:57,270
من النصف الأيمن من الجهة اليسرى و
نصف، وأنا أبدا التراجع مرة واحدة.

626
00:24:57,270 --> 00:25:00,570
>> وبالتالي فإن دمج نفسها مع الأخذ
لا يزيد عن ن الخطوات.

627
00:25:00,570 --> 00:25:03,250
وعدد المرات لم لدي
للقيام بذلك الدمج؟

628
00:25:03,250 --> 00:25:07,150
كذلك، أي أكثر من ن، ونحن فقط
ورأى أنه مع دمج النهائي.

629
00:25:07,150 --> 00:25:13,120
وحتى إذا كنت تفعل شيئا أن يأخذ
تسجيل ن الخطوات n مرة، أو العكس،

630
00:25:13,120 --> 00:25:15,210
انها سوف تعطينا n مرة تسجيل ن.

631
00:25:15,210 --> 00:25:16,310
>> ولماذا هذا أفضل؟

632
00:25:16,310 --> 00:25:19,600
حسنا، إذا كنا نعرف بالفعل أن سجل
n هو أفضل من ن - أليس كذلك؟

633
00:25:19,600 --> 00:25:22,590
رأينا في البحث الثنائي، دليل الهاتف
سبيل المثال، كان سجل ن بالتأكيد

634
00:25:22,590 --> 00:25:23,760
أفضل من الخطية.

635
00:25:23,760 --> 00:25:28,420
وهذا يعني ن مرات تسجيل الدخول n هو
بالتأكيد أفضل من مرات ن آخر

636
00:25:28,420 --> 00:25:30,390
ن، ن AKA المربعة.

637
00:25:30,390 --> 00:25:32,400
وهذا ما نشعر به في نهاية المطاف.

638
00:25:32,400 --> 00:25:34,928
>> جولة كبيرة جدا من التصفيق، إذا
نستطيع، لهؤلاء الرجال.

639
00:25:34,928 --> 00:25:38,920
>> [تصفيق]

640
00:25:38,920 --> 00:25:41,550
>> DAVID مالان: والهدايا الخاصة بك فراق -
كنت قد تبقي الأرقام،

641
00:25:41,550 --> 00:25:44,010
إذا كنت ترغب.

642
00:25:44,010 --> 00:25:45,620
وهدية فراق الخاص، كما جرت العادة.

643
00:25:45,620 --> 00:25:47,290
أوه، وسوف نرسل لك
لقطات، ميشيل.

644
00:25:47,290 --> 00:25:48,343
شكرا لك.

645
00:25:48,343 --> 00:25:49,250
حسنا.

646
00:25:49,250 --> 00:25:50,400
تساعد نفسك في الكرة الإجهاد.

647
00:25:50,400 --> 00:25:54,110
>> واسمحوا لي أن سحب ما يصل، في هذه الأثناء،
صديقنا روب بودين لتقديم

648
00:25:54,110 --> 00:25:59,520
وجهة نظر مختلفة نوعا ما في هذا الشأن،
حيث يمكنك التفكير في هذه

649
00:25:59,520 --> 00:26:01,280
الخطوات يحدث في بعض الشيء
بطريقة مختلفة.

650
00:26:01,280 --> 00:26:04,750
في الواقع، فإن مجموعة المتابعة لماذا عن روب
لتبين لنا يفترض أن قمنا

651
00:26:04,750 --> 00:26:09,030
فعلت ما يصل الفاصل لل
قائمة كبيرة إلى ثماني قوائم صغيرة،

652
00:26:09,030 --> 00:26:10,570
كل من حجم 1.

653
00:26:10,570 --> 00:26:13,350
>> لذلك نحن تغيير شبة الكود ل
قليلا فقط لنوع من الحصول على

654
00:26:13,350 --> 00:26:15,320
الفكرة الأساسية لكيفية عمل دمج.

655
00:26:15,320 --> 00:26:17,600
ولكن وقت تشغيل ما
انه على وشك القيام به هو لا يزال

656
00:26:17,600 --> 00:26:19,110
سوف تكون هي نفسها.

657
00:26:19,110 --> 00:26:23,540
ومرة أخرى، فإن مجموعة المتابعة هنا هو أنه
بدأت مع ثماني قوائم حجم 1.

658
00:26:23,540 --> 00:26:27,730
لذلك كنت قد غاب عن الجزء حيث انه
فعلت فعلا سجل ن، ن تسجيل، تسجيل ن

659
00:26:27,730 --> 00:26:31,205
الفاصل من المدخلات.

660
00:26:31,205 --> 00:26:32,120
>> [تشغيل الفيديو]

661
00:26:32,120 --> 00:26:33,615
>> لذالك لخطوة واحدة.

662
00:26:33,615 --> 00:26:38,270
لخطوتين، مرارا وتكرارا
دمج أزواج من القوائم.

663
00:26:38,270 --> 00:26:39,210
>> DAVID مالان: صاحبة الجلالة.

664
00:26:39,210 --> 00:26:41,270
فقط الصوت قادم
من جهاز الكمبيوتر الخاص بي.

665
00:26:41,270 --> 00:26:42,520
دعونا نحاول هذا مرة أخرى.

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

667
00:26:45,330 --> 00:26:48,310
>> ، فقط اختيار تعسفي التي -
الآن لدينا أربع قوائم.

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

669
00:26:51,590 --> 00:26:52,120
تعلم قبل.

670
00:26:52,120 --> 00:26:53,040
>> DAVID مالان: هناك نذهب.

671
00:26:53,040 --> 00:27:00,510
>> دمج-108 و 15، ونحن في نهاية
مع لائحة 15، 108.

672
00:27:00,510 --> 00:27:07,170
دمج 50 و 4، ونحن
في نهاية المطاف مع 4، 50.

673
00:27:07,170 --> 00:27:12,990
دمج 8 و 42، ونحن
في نهاية المطاف مع 8، 42.

674
00:27:12,990 --> 00:27:19,970
ودمج 23 و 16، ونحن
في نهاية المطاف مع 16 و 23.

675
00:27:19,970 --> 00:27:23,270
>> الآن جميع القوائم لدينا هي من حجم 2.

676
00:27:23,270 --> 00:27:26,690
لاحظ أن كل من
يتم فرز أربع قوائم.

677
00:27:26,690 --> 00:27:29,450
حتى نتمكن من البدء في دمج
أزواج من القوائم مرة أخرى.

678
00:27:29,450 --> 00:27:38,420
دمج 15 و 108 و 4 و 50، ونحن
أولا نلقي ال 4، ثم 15، ثم

679
00:27:38,420 --> 00:27:41,500
50، ثم 108.

680
00:27:41,500 --> 00:27:50,610
دمج 8 و 42 و 16 و 23، ونحن نأخذ الأولى
8، ثم 16، ثم 23،

681
00:27:50,610 --> 00:27:52,700
ثم 42.

682
00:27:52,700 --> 00:27:57,600
>> حتى الآن لدينا اثنين فقط من حجم القوائم
4، كل منها تم فرزها.

683
00:27:57,600 --> 00:28:01,170
حتى الآن نحن دمج هاتين القائمتين.

684
00:28:01,170 --> 00:28:11,835
الأولى، ونحن نأخذ ال 4، ثم أخذنا
8، ثم نأخذ 15، ثم 16، ثم

685
00:28:11,835 --> 00:28:19,456
23، ثم 42، ثم 50، ثم 108.

686
00:28:19,456 --> 00:28:19,872
>> [END تشغيل الفيديو]

687
00:28:19,872 --> 00:28:23,430
>> DAVID مالان: مرة أخرى، لاحظ، لم يسبق له
تطرق كوب تعطى أكثر من مرة واحدة

688
00:28:23,430 --> 00:28:24,860
بعد التقدم أبعد من ذلك.

689
00:28:24,860 --> 00:28:26,200
حتى انه لم التكرار.

690
00:28:26,200 --> 00:28:29,850
لذلك فهو يتحرك دائما إلى الجانب،
وحيث ان وصلنا لدينا ن.

691
00:28:29,850 --> 00:28:33,290
>> لماذا لا يسمح لي سحب ما يصل للرسوم المتحركة واحد
التي رأيناها في وقت سابق، ولكن هذه المرة

692
00:28:33,290 --> 00:28:35,110
التركيز فقط على دمج النوع.

693
00:28:35,110 --> 00:28:38,030
اسمحوا لي المضي قدما والتكبير
في على هذا هنا.

694
00:28:38,030 --> 00:28:42,530
أولا اسمحوا لي أن اختيار المدخلات العشوائية،
تضخيم هذا، ويمكنك معرفة نوع من

695
00:28:42,530 --> 00:28:46,600
ما اتخذنا من المسلمات، في وقت سابق،
دمج النوع يقوم به فعلا.

696
00:28:46,600 --> 00:28:50,330
>> لذلك تلاحظ أن تحصل هذه نصفين أو
هذه أرباع أو أثمان هذه ل

697
00:28:50,330 --> 00:28:53,140
المشكلة التي مفاجئة للجميع
تبدأ في التبلور جيدة.

698
00:28:53,140 --> 00:28:57,070
ثم أخيرا، ترى في
نهاية جدا أن بام،

699
00:28:57,070 --> 00:28:58,860
يتم دمج كل شيء معا.

700
00:28:58,860 --> 00:29:01,690
>> لذلك فان هذه هي مختلفة ثلاثة فقط
يأخذ على نفس الفكرة.

701
00:29:01,690 --> 00:29:05,980
ولكن الفكرة الرئيسية، تماما مثل الفجوة
وقهر في الدرجة الأولى،

702
00:29:05,980 --> 00:29:10,640
كان ذلك قررنا تقسيم بطريقة أو بأخرى
المشكلة في شيء كبير، في

703
00:29:10,640 --> 00:29:14,760
شيء نوع من متطابقة في الروح،
ولكن أصغر وأصغر وأصغر

704
00:29:14,760 --> 00:29:15,660
وأصغر.

705
00:29:15,660 --> 00:29:18,420
>> الآن وسيلة أخرى متعة لنوع من التفكير
حول هذه، على الرغم من انها ليست

706
00:29:18,420 --> 00:29:20,520
سوف تعطيك نفس بديهية
فهم، هو

707
00:29:20,520 --> 00:29:21,640
الحركة التالية.

708
00:29:21,640 --> 00:29:25,400
لذلك هذا هو شخص وضع الفيديو معا
أن يرتبط مختلفة

709
00:29:25,400 --> 00:29:29,970
يبدو مع عمليات مختلفة ل
نوع الإدراج، لدمج النوع، و

710
00:29:29,970 --> 00:29:31,150
لاثنين آخرين.

711
00:29:31,150 --> 00:29:32,330
حتى في لحظة، وانا ذاهب لضرب اللعب.

712
00:29:32,330 --> 00:29:33,600
انها حوالي دقيقة واحدة طويلة.

713
00:29:33,600 --> 00:29:37,410
وعلى الرغم من لا يزال بإمكانك رؤية
أنماط يحدث، وهذه المرة يمكنك

714
00:29:37,410 --> 00:29:41,420
أيضا نسمع كيف هي هذه الخوارزميات
أداء مختلف ومع

715
00:29:41,420 --> 00:29:43,950
أنماط مختلفة إلى حد ما.

716
00:29:43,950 --> 00:29:45,830
>> هذا هو الإدراج الفرز.

717
00:29:45,830 --> 00:29:50,400
>> [TONES PLAYING]

718
00:29:50,400 --> 00:29:52,400
>> DAVID مالان: إنه يحاول مرة أخرى
لإدراج كل عنصر

719
00:29:52,400 --> 00:29:52,900
إلى حيث تنتمي.

720
00:29:52,900 --> 00:29:54,628
هذا هو نوع فقاعة.

721
00:29:54,628 --> 00:30:10,097
>> [TONES PLAYING]

722
00:30:10,097 --> 00:30:13,630
>> DAVID مالان: ويمكنك أن تشعر نوع من
كيفية عمل القليل نسبيا تقوم به

723
00:30:13,630 --> 00:30:15,834
على كل خطوة.

724
00:30:15,834 --> 00:30:20,470
هذا هو ما يبدو الإضجار مثل.

725
00:30:20,470 --> 00:30:21,472
>> [TONES PLAYING]

726
00:30:21,472 --> 00:30:25,222
>> DAVID مالان: هذا هو اختيار نوع،
حيث نقوم باختيار عنصر نريد من خلال

727
00:30:25,222 --> 00:30:28,845
يمر مرة أخرى ومرة ​​أخرى ومرة ​​أخرى
ووضعه في البداية.

728
00:30:28,845 --> 00:30:37,674
>> [TONES PLAYING]

729
00:30:37,674 --> 00:30:43,970
>> DAVID مالان: هذا هو دمج النوع الذي
يمكنك البدء ليشعر حقا.

730
00:30:43,970 --> 00:30:51,810
>> [TONES PLAYING]

731
00:30:51,810 --> 00:30:54,770
>> [ضحك]

732
00:30:54,770 --> 00:30:58,395
>> DAVID مالان: شيء يسمى جنوم
نوع، وهو ما لم ينظر في.

733
00:30:58,395 --> 00:31:13,630
>> [TONES PLAYING]

734
00:31:13,630 --> 00:31:17,910
>> DAVID مالان: لذا اسمحوا لي أن نرى، الآن،
يصرف كما كنت أمل من قبل

735
00:31:17,910 --> 00:31:21,110
الموسيقى، إذا أنا يمكن أن تنزلق قليلا
قليلا من الرياضيات هنا.

736
00:31:21,110 --> 00:31:24,850
حتى لا يكون هناك وسيلة الرابع ما في وسعنا
نفكر في ما يعنيه هذه

737
00:31:24,850 --> 00:31:29,210
وظائف لتكون أسرع من تلك
التي شهدناها من قبل.

738
00:31:29,210 --> 00:31:32,470
وإذا كنت قادما في الدورة من
خلفية الرياضيات، كنت

739
00:31:32,470 --> 00:31:36,030
نعرف في الواقع ربما بالفعل التي
يمكن صفعة مصطلح على هذه التقنية -

740
00:31:36,030 --> 00:31:40,400
وهي العودية، وهي وظيفة
التي تطلق على نفسها بطريقة أو بأخرى.

741
00:31:40,400 --> 00:31:44,780
>> ومرة أخرى، أذكر أن دمج النوع
كان شبة الكود العودية بمعنى

742
00:31:44,780 --> 00:31:48,460
أن واحدة من الخطوات دمج النوع في
وكان لاستدعاء نوع -

743
00:31:48,460 --> 00:31:49,740
وهذا هو، في حد ذاته.

744
00:31:49,740 --> 00:31:52,480
ولكن لحسن الحظ، لأننا أبقى
داعيا نوع، أو دمج النوع،

745
00:31:52,480 --> 00:31:55,880
على وجه التحديد، على أصغر وأصغر
وقائمة أصغر، ونحن في نهاية المطاف

746
00:31:55,880 --> 00:32:00,005
ينتعش بفضل ما سنتصل
قضية القاعدة، حالة الثابت تلوينها أن

747
00:32:00,005 --> 00:32:04,270
وقال إذا كانت قائمة صغيرة، أقل من 2
في هذه الحالة، والعودة فقط على الفور.

748
00:32:04,270 --> 00:32:07,550
إذا لم يكن لدينا هذه الحالة الخاصة، و
سوف خوارزمية أبدا القاع،

749
00:32:07,550 --> 00:32:11,010
وسوف تحصل في الواقع إلى
حلقة لا نهائية إلى الأبد حقا.

750
00:32:11,010 --> 00:32:14,330
>> ولكن لنفترض أننا نريد أن يضع الآن
بعض الأرقام في هذا، مرة أخرى، وذلك باستخدام ن

751
00:32:14,330 --> 00:32:15,660
ويبلغ حجم المدخلات.

752
00:32:15,660 --> 00:32:18,680
وأنا أريد أن أطلب منكم، ما هو
إجمالي الوقت تشارك في

753
00:32:18,680 --> 00:32:19,800
تشغيلها دمج النوع؟

754
00:32:19,800 --> 00:32:22,960
أو بشكل أعم، ما هو
تكلفة منه في الوقت المناسب؟

755
00:32:22,960 --> 00:32:24,730
>> كذلك فإنه من السهل جدا لقياس ذلك.

756
00:32:24,730 --> 00:32:29,010
إذا كان n أقل من 2، والوقت الذي يتطلبه
في فرز العناصر ن،

757
00:32:29,010 --> 00:32:30,480
حيث n هو 2، 0.

758
00:32:30,480 --> 00:32:31,410
لأن نعود فقط.

759
00:32:31,410 --> 00:32:32,510
ليس هناك عمل ينبغي القيام به.

760
00:32:32,510 --> 00:32:35,660
الآن يمكن القول، وربما انها خطوة واحدة أو اثنتين
خطوات لمعرفة كمية

761
00:32:35,660 --> 00:32:38,420
العمل، لكنها قريبة بما فيه الكفاية ل0 أن
أنا فقط أريد أن أقول أي عمل هو

762
00:32:38,420 --> 00:32:40,940
مطلوب إذا كانت قائمة صغيرة جدا
أن يكون رتيبا.

763
00:32:40,940 --> 00:32:42,580
>> ولكن هذه الحالة هي مثيرة للاهتمام.

764
00:32:42,580 --> 00:32:47,320
كان الحال العودية فرع
في شبة الكود الذي قال آخر، نوع

765
00:32:47,320 --> 00:32:52,000
النصف الأيسر، فرز الحق
نصف، ودمج شطري.

766
00:32:52,000 --> 00:32:55,530
الآن لماذا يفعل هذا التعبير
تمثل تلك النفقات؟

767
00:32:55,530 --> 00:32:58,690
كذلك، تي ن يعني مجرد
الوقت لفرز العناصر ن.

768
00:32:58,690 --> 00:33:03,070
ثم على الجانب الأيمن من
علامة التساوي هناك، تي ن تقسيم

769
00:33:03,070 --> 00:33:06,600
بنسبة 2 يشير إلى تكلفة ماذا؟

770
00:33:06,600 --> 00:33:07,570
فرز النصف الأيسر.

771
00:33:07,570 --> 00:33:10,990
تي غيرها ن مقسوما على 2 هو
مشيرا يفترض أن تكلفة ل

772
00:33:10,990 --> 00:33:12,390
فرز نصف الحق.

773
00:33:12,390 --> 00:33:14,590
>> ثم زائد ن؟

774
00:33:14,590 --> 00:33:15,420
هو الدمج.

775
00:33:15,420 --> 00:33:19,120
لأنه إذا كان لديك قائمتين، واحدة من
ن حجم أكثر من 2 وآخر من حجم ن

776
00:33:19,120 --> 00:33:22,580
أكثر من 2، لديك أساسا للمس
كل من تلك العناصر، تماما مثل روب

777
00:33:22,580 --> 00:33:24,990
وتطرق كل من الكؤوس، وعادل
كما أشرنا في كل من

778
00:33:24,990 --> 00:33:26,310
المتطوعين على خشبة المسرح.

779
00:33:26,310 --> 00:33:28,790
لذلك n هو حساب دمج.

780
00:33:28,790 --> 00:33:31,780
>> الآن للأسف، هذه الصيغة
هو أيضا نفسه العودية.

781
00:33:31,780 --> 00:33:36,390
لذلك إذا طرح السؤال، إذا n هو، كما يقول،
16، إذا كان هناك 16 شخصا على خشبة المسرح

782
00:33:36,390 --> 00:33:40,670
أو 16 أكواب في شريط الفيديو، كم من مجموع
الخطوات التي يستغرقها فرزها

783
00:33:40,670 --> 00:33:41,550
مع دمج النوع؟

784
00:33:41,550 --> 00:33:45,790
انها في الواقع ليست جوابا واضحا،
لأنه الآن لديك لفرز من

785
00:33:45,790 --> 00:33:48,500
الإجابة بشكل متكرر هذه الصيغة.

786
00:33:48,500 --> 00:33:51,190
>> ولكن هذا موافق، لأن اسمحوا لي أن أقترح
ما نقوم به ما يلي.

787
00:33:51,190 --> 00:33:56,670
الوقت الذي يتطلبه لفرز 16 شخصا أو
16 أكواب ستكون ممثلة

788
00:33:56,670 --> 00:33:58,020
عموما كما T 16.

789
00:33:58,020 --> 00:34:01,400
ولكن الذي يساوي، وفقا لدينا
الصيغة السابقة، 2 أضعاف المبلغ

790
00:34:01,400 --> 00:34:04,780
الوقت الذي يستغرقه لفرز
8 أكواب زائد 16.

791
00:34:04,780 --> 00:34:08,590
ومرة أخرى، بالإضافة إلى 16 هو الوقت المناسب لدمج،
ومرتين T من 8 هو

792
00:34:08,590 --> 00:34:10,790
الوقت لفرز النصف الأيسر والنصف الأيمن.

793
00:34:10,790 --> 00:34:11,989
>> ولكن مرة أخرى، هذا لا يكفي.

794
00:34:11,989 --> 00:34:13,210
علينا أن الغوص في أعمق.

795
00:34:13,210 --> 00:34:16,409
هذا يعني ان لدينا للرد على
السؤال، ما هو T من 8؟

796
00:34:16,409 --> 00:34:19,610
كذلك T من 8 هو مجرد 2
T من 4 مرات بالإضافة إلى 8.

797
00:34:19,610 --> 00:34:20,520
حسنا، ما هو T من 4؟

798
00:34:20,520 --> 00:34:23,780
T من 4 مرات فقط 2 من 2 T زائد 4.

799
00:34:23,780 --> 00:34:25,489
حسنا، ما هو T من 2؟

800
00:34:25,489 --> 00:34:29,030
T من 2 هو مجرد 2 مرات T من 1 زائد 2.

801
00:34:29,030 --> 00:34:31,940
>> ومرة أخرى، نحن نوع من الحصول على
عالقا في هذه الدورة.

802
00:34:31,940 --> 00:34:34,790
ولكن هذا على وشك أن تصل
ما يسمى الحالة الأساسية.

803
00:34:34,790 --> 00:34:37,310
لأن ما هو من T 1، لم ندعي؟

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
وحتى الآن أخيرا، يمكننا العمل الوراء.

806
00:34:39,730 --> 00:34:44,290
>> إذا T من 1 0، يمكنني أن أذهب الآن نسخة احتياطية واحدة
خط لهذا الرجل هنا، ويمكنني

807
00:34:44,290 --> 00:34:46,330
سد العجز في لT 0 1.

808
00:34:46,330 --> 00:34:51,770
وهذا يعني أنه يساوي 2 مرات الصفر،
والمعروف باسم 0، بالإضافة إلى 2.

809
00:34:51,770 --> 00:34:53,739
وبحيث التعبير كله 2.

810
00:34:53,739 --> 00:34:58,740
>> الآن إذا كنت تأخذ من T 2، الذي الجواب
و2، بتوصيله خط الوسط، T

811
00:34:58,740 --> 00:35:02,740
من 4، وهذا يعطيني 2 مرات
2 زائد 4، لذلك 8.

812
00:35:02,740 --> 00:35:07,080
إذا كنت ثم سد العجز في 8 إلى السابق
خط، وهذا يعطيني 2 مرة 8، 16.

813
00:35:07,080 --> 00:35:12,470
وإذا كنا ثم تابع أنه مع
24، مضيفا في 16، ونصل أخيرا

814
00:35:12,470 --> 00:35:13,820
قيمة 64.

815
00:35:13,820 --> 00:35:18,480
>> الآن أنه في حد ذاته نوع من يتحدث
لا شيء لتدوين ن، و

816
00:35:18,480 --> 00:35:20,700
O كبيرة، أوميغا التي قمنا
تم الحديث عنه.

817
00:35:20,700 --> 00:35:24,890
ولكن اتضح أن 64 هو في الواقع
16، وحجم المدخلات،

818
00:35:24,890 --> 00:35:27,110
تسجيل قاعدة 2 من 16.

819
00:35:27,110 --> 00:35:30,200
وإذا كان هذا هو غير مألوف قليلا، فقط
التفكير مرة أخرى، وأنه سوف يعود

820
00:35:30,200 --> 00:35:30,700
لك في نهاية المطاف.

821
00:35:30,700 --> 00:35:33,775
إذا كان هذا هو الأساس سجل 2، انها مثل 2
مرفوعة إلى ما يمنحك 16؟

822
00:35:33,775 --> 00:35:36,380
أوه، هذا هو 4، لذلك فمن 16 مرة 4.

823
00:35:36,380 --> 00:35:39,380
>> ومرة أخرى، انها ليست صفقة كبيرة إذا كان هذا
هو نوع من ذاكرة ضبابية الآن.

824
00:35:39,380 --> 00:35:43,720
لكنه الآن، تأخذ على الإيمان
أن 16 سجل 16 هو 64.

825
00:35:43,720 --> 00:35:46,590
وهكذا في الواقع، مع هذا العقل البسيط
تحقق، لقد أكد -

826
00:35:46,590 --> 00:35:48,250
ولكن لم يثبت رسميا -

827
00:35:48,250 --> 00:35:52,800
أن وقت تشغيل الدمج
هو في الواقع نوع ن ن تسجيل.

828
00:35:52,800 --> 00:35:53,790
>> لذلك ليس سيئا.

829
00:35:53,790 --> 00:35:57,260
انها بالتأكيد أفضل من
خوارزميات رأيناه حتى الآن، و

830
00:35:57,260 --> 00:36:00,710
انها لاننا الاستدانة، واحد،
تقنية تسمى العودية.

831
00:36:00,710 --> 00:36:03,880
ولكن أكثر إثارة للاهتمام من ذلك، أن
فكرة تقسيم وقهر.

832
00:36:03,880 --> 00:36:07,460
مرة أخرى، في الأسبوع حقا 0 الاشياء التي
حتى الآن المتكررة في

833
00:36:07,460 --> 00:36:08,740
طريقة أكثر إقناعا.

834
00:36:08,740 --> 00:36:11,750
>> الآن ممارسة القليل متعة، وإذا كنت قد
لم تفعل هذا - وربما كنت

835
00:36:11,750 --> 00:36:14,660
لن يكون، لأن نوع من العادي
الناس لا يفكرون في القيام بذلك.

836
00:36:14,660 --> 00:36:20,650
ولكن إذا ذهبت إلى google.com وإذا
أريد أن أتعلم شيئا عن

837
00:36:20,650 --> 00:36:22,356
العودية، أدخل.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [ضحك]

840
00:36:29,058 --> 00:36:32,030
[المزيد ضحك]

841
00:36:32,030 --> 00:36:33,385
DAVID مالان: سيئ نكتة تنتشر ببطء.

842
00:36:33,385 --> 00:36:34,450
[ضحك]

843
00:36:34,450 --> 00:36:36,970
DAVID مالان: عادل في القضية، انها هناك.

844
00:36:36,970 --> 00:36:38,710
لم أكن توضيح ذلك الخطأ،
وهناك نكتة.

845
00:36:38,710 --> 00:36:40,810
حسنا.

846
00:36:40,810 --> 00:36:42,950
تفسير ذلك للشعب إلى جانبك إذا
أنها لم النقر جدا فقط حتى الآن.

847
00:36:42,950 --> 00:36:47,650
ولكن العودية، وبصورة أعم، يشير
لعملية من استدعاء وظيفة

848
00:36:47,650 --> 00:36:51,430
في حد ذاته، أو أكثر عموما، تقسيم
المشكلة في شيء يمكن أن يكون

849
00:36:51,430 --> 00:36:56,220
حل تدريجي من خلال حل متطابقة
مشاكل ممثل.

850
00:36:56,220 --> 00:36:58,400
>> حسنا، دعونا تغيير التروس
لمجرد لحظة.

851
00:36:58,400 --> 00:37:00,840
نود أن تنتهي في بعض cliffhangers،
لذلك دعونا نبدأ لتعيين

852
00:37:00,840 --> 00:37:05,870
المسرح، لعدة دقائق،
على فكرة بسيطة جدا -

853
00:37:05,870 --> 00:37:07,620
أن مبادلة عنصرين، أليس كذلك؟

854
00:37:07,620 --> 00:37:10,040
كل من هذه الخوارزميات كنا
الحديث عن القليلة الماضية

855
00:37:10,040 --> 00:37:12,420
تنطوي بعض المحاضرات
نوع من مقايضة.

856
00:37:12,420 --> 00:37:14,630
اليوم وقد تصور من قبل لهم الحصول على
للخروج من كراسيهم و

857
00:37:14,630 --> 00:37:18,570
يتجول، ولكن في التعليمات البرمجية، كنا
تأخذ فقط عنصر من مجموعة واحدة

858
00:37:18,570 --> 00:37:20,370
وصوت نزول المطر عليه في آخر.

859
00:37:20,370 --> 00:37:21,880
>> لذلك كيف نذهب عن القيام بذلك؟

860
00:37:21,880 --> 00:37:24,850
حسنا، اسمحوا لي أن المضي قدما في الكتابة
برنامج سريع هنا.

861
00:37:24,850 --> 00:37:31,600
انا ذاهب الى المضي قدما والقيام
هذا على النحو التالي.

862
00:37:31,600 --> 00:37:33,910
دعونا نسمي هذا -

863
00:37:33,910 --> 00:37:38,070
ماذا نريد لهذه الكلمة واحدة؟

864
00:37:38,070 --> 00:37:38,650
>> في الواقع، لا.

865
00:37:38,650 --> 00:37:39,420
اسمحوا لي الترجيع.

866
00:37:39,420 --> 00:37:41,220
أنا لا أريد أن نفعل ذلك
التشويق حتى الآن.

867
00:37:41,220 --> 00:37:42,270
وسوف أفسد متعة.

868
00:37:42,270 --> 00:37:43,600
دعونا نفعل ذلك بدلا من ذلك.

869
00:37:43,600 --> 00:37:47,430
>> لنفترض أنني أريد أن أكتب قليلا
البرنامج والتي تحتضن الآن هذا

870
00:37:47,430 --> 00:37:48,700
فكرة العودية.

871
00:37:48,700 --> 00:37:50,370
النوع الأول من حصلت قبل نفسي هناك.

872
00:37:50,370 --> 00:37:51,420
انا ذاهب الى القيام بما يلي.

873
00:37:51,420 --> 00:38:00,220
>> الأولى، وتشمل سريعة من io.h القياسية،
وكذلك التضمين من cs50.h.

874
00:38:00,220 --> 00:38:03,200
ثم انا ذاهب الى المضي قدما
وتعلن باطلة الرئيسي الباحث

875
00:38:03,200 --> 00:38:04,360
بالطريقة المعتادة.

876
00:38:04,360 --> 00:38:07,920
أدركت أنني كنت ذات التسمية المضللة الملف، لذلك
اسمحوا لي أن أضيف ملحق ج هنا حتى

877
00:38:07,920 --> 00:38:09,510
نتمكن من ترجمة عليه بشكل صحيح.

878
00:38:09,510 --> 00:38:10,970
تبدأ هذه المهمة قبالة.

879
00:38:10,970 --> 00:38:13,290
>> وظيفة أريد أن أكتب، تماما
ببساطة، هو الذي يسأل

880
00:38:13,290 --> 00:38:16,210
المستخدم لعدد ثم يضيف
جميع الأرقام بين أن

881
00:38:16,210 --> 00:38:19,920
عدد و، ويقول، 0.

882
00:38:19,920 --> 00:38:22,510
لذلك أول وأنا ذاهب إلى المضي قدما
وتعلن ن الباحث.

883
00:38:22,510 --> 00:38:24,760
ثم أقوم بنسخ بعض التعليمات البرمجية التي
استخدمنا لفترة من الوقت.

884
00:38:24,760 --> 00:38:26,660
بينما هناك شيئا صحيحا.

885
00:38:26,660 --> 00:38:28,000
سأعود إلى ذلك في لحظة.

886
00:38:28,000 --> 00:38:29,010
>> ماذا أريد أن أفعل؟

887
00:38:29,010 --> 00:38:33,460
أريد أن أقول printf إيجابية
عدد صحيح من فضلك.

888
00:38:33,460 --> 00:38:36,130
ثم أنا ذاهب ل
يقول ن يحصل على الحصول على كثافة العمليات.

889
00:38:36,130 --> 00:38:38,800
ذلك مرة أخرى، بعض رمز المتداول
أننا قد استخدمت من قبل.

890
00:38:38,800 --> 00:38:40,810
وانا ذاهب للقيام بذلك
بينما n هو أقل من 1.

891
00:38:40,810 --> 00:38:44,120
ولذلك فإن هذا سوف تأكد من أن المستخدم
يعطيني عددا صحيحا موجبا.

892
00:38:44,120 --> 00:38:45,490
>> والآن انا ذاهب الى القيام بما يلي.

893
00:38:45,490 --> 00:38:51,020
أريد أن تضيف ما يصل كل الأرقام
بين 1 و n و، أو 0 و ن،

894
00:38:51,020 --> 00:38:52,570
مكافئ، للحصول على المبلغ الإجمالي.

895
00:38:52,570 --> 00:38:55,100
وبالتالي فإن رمز سيغما كبيرة
التي قد تذكر.

896
00:38:55,100 --> 00:38:59,050
لذلك أنا ذاهب الى القيام بذلك عن طريق الدعوة الأولى
وظيفة تسمى سيغما،

897
00:38:59,050 --> 00:39:06,030
فمررها في ن، ثم انا ذاهب الى
يقول printf، فإن الجواب هو الحق هناك.

898
00:39:06,030 --> 00:39:08,180
>> لذلك باختصار، وأحصل على و
الباحث من المستخدم.

899
00:39:08,180 --> 00:39:09,280
أنا ضمان انها ايجابية.

900
00:39:09,280 --> 00:39:12,700
أعلن متغير يسمى إجابة ل
نوع int وتخزين في ذلك عودة

901
00:39:12,700 --> 00:39:15,610
قيمة سيغما، ويمر في ن كإدخال.

902
00:39:15,610 --> 00:39:17,060
وبعد ذلك طباعة هذا الجواب.

903
00:39:17,060 --> 00:39:19,550
>> للأسف، على الرغم من الأصوات سيغما
وكأنه شيء قد يكون في

904
00:39:19,550 --> 00:39:24,040
ملف math.h، إعلانها،
انها في الواقع لا.

905
00:39:24,040 --> 00:39:24,690
بحيث لا بأس.

906
00:39:24,690 --> 00:39:26,170
يمكنني تنفيذ هذا بنفسي.

907
00:39:26,170 --> 00:39:29,160
أنا ذاهب لتنفيذ وظيفة تسمى
سيغما، وانها سوف تأخذ

908
00:39:29,160 --> 00:39:29,900
المعلمة -

909
00:39:29,900 --> 00:39:32,100
دعونا نسميها م فقط، فقط
لذلك فمن مختلفة.

910
00:39:32,100 --> 00:39:35,910
ثم هنا، انا ذاهب الى القول،
حسنا، إذا م هو أقل من 1 - هذا هو

911
00:39:35,910 --> 00:39:38,180
برنامج رتيبا جدا.

912
00:39:38,180 --> 00:39:41,700
لذلك انا ذاهب الى المضي قدما و
0 العودة فورا.

913
00:39:41,700 --> 00:39:45,920
انها فقط لا معنى لتضيف ما يصل جميع
الأرقام بين 1 و م إذا م

914
00:39:45,920 --> 00:39:48,470
هو في حد ذاته 0 أو سلبية.

915
00:39:48,470 --> 00:39:50,900
>> ثم انا ذاهب الى المضي قدما
والقيام بذلك تكراري جدا.

916
00:39:50,900 --> 00:39:53,090
انا ذاهب للقيام بذلك النوع من المدرسة القديمة،
وانا ذاهب الى المضي قدما

917
00:39:53,090 --> 00:39:57,150
وأقول إنني ذاهب ل
تعلن مبلغ أن يكون 0.

918
00:39:57,150 --> 00:39:59,630
ثم أنا ذاهب لديك
لحلقة من كثافة العمليات -

919
00:39:59,630 --> 00:40:02,820
واسمحوا لي أن تفعل ذلك لمطابقة دينا
كود التوزيع، بحيث يكون لديك نسخة

920
00:40:02,820 --> 00:40:07,500
في المنزل. كثافة العمليات ط 1 يحصل على ما يصل إلى
ط أقل من أو يساوي متر.

921
00:40:07,500 --> 00:40:09,430
ط زائد زائد.

922
00:40:09,430 --> 00:40:11,430
ثم داخل هذه لحلقة -

923
00:40:11,430 --> 00:40:12,440
نحن تقريبا هناك -

924
00:40:12,440 --> 00:40:15,810
المبلغ يحصل مبلغ زائد 1.

925
00:40:15,810 --> 00:40:17,670
ثم أنا ذاهب لإرجاع المبلغ.

926
00:40:17,670 --> 00:40:19,420
>> هكذا فعلت ذلك بسرعة،
من المسلم به تماما.

927
00:40:19,420 --> 00:40:22,775
ولكن مرة أخرى، والوظيفة الرئيسية جميلة
واضحة، تقوم على قواعد لدينا

928
00:40:22,775 --> 00:40:23,190
مكتوبة حتى الآن.

929
00:40:23,190 --> 00:40:25,610
يستخدم حلقة المزدوج للحصول على الإيجابية
الباحث من المستخدم.

930
00:40:25,610 --> 00:40:29,870
وبعد ذلك تمرير هذا الباحث إلى وظيفة جديدة
دعا سيغما، واصفا ذلك، مرة أخرى، ن.

931
00:40:29,870 --> 00:40:33,100
وأنا تخزين قيمة الإرجاع، والجواب
من الصندوق الاسود حاليا

932
00:40:33,100 --> 00:40:35,460
المعروفة باسم سيغما، في متغير
دعا الجواب.

933
00:40:35,460 --> 00:40:36,580
ثم أنا طباعته.

934
00:40:36,580 --> 00:40:39,090
>> إذا كنا الآن لا تزال هذه القصة،
كيف يتم تطبيق سيجما؟

935
00:40:39,090 --> 00:40:40,840
أقترح لتنفيذ على النحو التالي.

936
00:40:40,840 --> 00:40:43,560
أولا، قليلا من تدقيق الأخطاء
للتأكد من أن المستخدم ليس

937
00:40:43,560 --> 00:40:46,480
العبث معي ويمر في
بعض سلبية أو القيمة 0.

938
00:40:46,480 --> 00:40:49,710
ثم أعلن متغير يسمى
المبلغ وتعيينها إلى 0.

939
00:40:49,710 --> 00:40:55,910
>> وأنا الآن تبدأ في التحرك من التساوي ط
1 كل وسيلة وبما يصل إلى متر،

940
00:40:55,910 --> 00:41:00,130
لأنني أريد أن تشمل جميع
الأرقام من واحد من خلال م، ضمنا.

941
00:41:00,130 --> 00:41:04,350
وداخل هذا للحلقة، وأنا مجرد القيام
مبلغ يحصل ما هو عليه الآن، بالإضافة إلى

942
00:41:04,350 --> 00:41:08,900
قيمة ط.

943
00:41:08,900 --> 00:41:10,370
بالإضافة إلى قيمة ط.

944
00:41:10,370 --> 00:41:14,090
>> بوصفها جانبا، وإذا كنت لم أر هذا
من قبل، هناك بعض السكر النحوية

945
00:41:14,090 --> 00:41:14,870
لهذا الخط.

946
00:41:14,870 --> 00:41:21,120
أستطيع كتابة هذا النحو زائد يساوي ط،
فقط لانقاذ نفسي بضع ضربات المفاتيح

947
00:41:21,120 --> 00:41:22,570
وتبدو برودة قليلا.

948
00:41:22,570 --> 00:41:23,140
ولكن هذا كل شيء.

949
00:41:23,140 --> 00:41:24,660
انها وظيفيا نفس الشيء.

950
00:41:24,660 --> 00:41:26,710
>> للأسف، هذا الرمز هو
لن تجميع حتى الآن.

951
00:41:26,710 --> 00:41:31,600
إذا قمت بتشغيل جعل سيغما 0، كيف أنا
أنا ذاهب للحصول على صرخ في و؟

952
00:41:31,600 --> 00:41:33,473
ما تسير الأمور ليست مثل؟

953
00:41:33,473 --> 00:41:35,740
>> الحضور: [غير مسموع].

954
00:41:35,740 --> 00:41:37,800
>> DAVID مالان: نعم، لم أكن تعلن
وظيفة حتى أعلى، أليس كذلك؟

955
00:41:37,800 --> 00:41:40,590
C هو نوع من الغباء، لأنه فقط
لا ما كنت أقول أن تفعله، وأنت

956
00:41:40,590 --> 00:41:41,880
يجب أن نفعل ذلك في هذا النظام.

957
00:41:41,880 --> 00:41:45,910
وحتى لو كنت هاهنا هنا، وانا ذاهب ل
الحصول على تحذير حول سيغما الضمني

958
00:41:45,910 --> 00:41:46,860
الإعلان.

959
00:41:46,860 --> 00:41:48,120
>> أوه، لا مشكلة.

960
00:41:48,120 --> 00:41:50,370
أستطيع أن ترتفع إلى الأعلى، ويمكنني
ويقول، كل الحق، والانتظار لمدة دقيقة.

961
00:41:50,370 --> 00:41:54,240
سيغما هو دالة تقوم بإرجاع
عدد صحيح وانها تتوقع ل

962
00:41:54,240 --> 00:41:56,620
الباحث كمدخل، منقوطة.

963
00:41:56,620 --> 00:41:59,550
أو يمكن أن أضع وظيفة كاملة
الرئيسية أعلاه، ولكن بصفة عامة، فما استقاموا لكم فاستقيموا

964
00:41:59,550 --> 00:42:02,260
يوصي ضد ذلك، لأنه
من الجميل أن يكون دائما الرئيسي في أعلى ذلك

965
00:42:02,260 --> 00:42:06,310
يمكنك الغوص في الحق وتعرف ما هو
البرنامج به من خلال قراءة أول الرئيسي.

966
00:42:06,310 --> 00:42:07,930
>> وحتى الآن اسمحوا لي أن مسح الشاشة.

967
00:42:07,930 --> 00:42:09,330
إعادة تشكيل سيغما 0.

968
00:42:09,330 --> 00:42:10,340
يبدو أن جميع إجراءات المغادرة.

969
00:42:10,340 --> 00:42:11,970
اسمحوا لي أن تشغيل سيغما 0.

970
00:42:11,970 --> 00:42:12,770
أمور إيجابية.

971
00:42:12,770 --> 00:42:15,580
سوف تقدم له عدد
3 أن يبقيه بسيط.

972
00:42:15,580 --> 00:42:18,710
بحيث ينبغي أن تعطيني 3
زائد 2 زائد 1، لذلك 6.

973
00:42:18,710 --> 00:42:20,750
تدخل، وبالفعل أحصل 6.

974
00:42:20,750 --> 00:42:21,820
>> أستطيع أن أفعل شيئا أكبر -

975
00:42:21,820 --> 00:42:24,080
50، 12، 75.

976
00:42:24,080 --> 00:42:27,690
تماما كما الظل، وانا ذاهب للقيام
شيء مثير للسخرية وكأنه كبيرة حقا

977
00:42:27,690 --> 00:42:30,375
العدد، أوه، التي عملت فعلا -

978
00:42:30,375 --> 00:42:31,600
إيه، وأنا لا أعتقد أن هذا صحيح.

979
00:42:31,600 --> 00:42:32,810
دعونا نرى.

980
00:42:32,810 --> 00:42:34,060
دعونا حقا فوضى معها.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> وهذا هو المشكلة.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
ما الذي يحدث؟

985
00:42:44,970 --> 00:42:46,050
رمز ليست بهذا السوء.

986
00:42:46,050 --> 00:42:48,470
انها لا تزال الخطية.

987
00:42:48,470 --> 00:42:50,810
صفير هو تأثير جيد، على الرغم من.

988
00:42:50,810 --> 00:42:52,060
ما الذي يحدث؟

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> ليس متأكدا مما اذا سمعت ذلك.

991
00:42:55,620 --> 00:42:57,620
حتى اتضح - و
هذا هو باعتباره جانبا.

992
00:42:57,620 --> 00:42:59,400
هذا ليس الأساسية ل
فكرة العودية.

993
00:42:59,400 --> 00:43:02,480
كما تبين، لأنني أحاول أن
تمثل هذا العدد الكبير، ومعظم

994
00:43:02,480 --> 00:43:06,980
من المرجح يجري يساء تفسيرها
بواسطة C كرقم يست إيجابية،

995
00:43:06,980 --> 00:43:09,980
ولكن رقم سالب.

996
00:43:09,980 --> 00:43:12,690
>> نحن لم تحدثنا عن هذا، ولكنه
تبين وجود أعداد السلبية

997
00:43:12,690 --> 00:43:14,210
في العالم بالإضافة
إلى أرقام إيجابية.

998
00:43:14,210 --> 00:43:16,290
والوسائل التي يمكنك
تمثل رقما سالبا

999
00:43:16,290 --> 00:43:19,530
أساسا غير، يمكنك استخدام واحد
بت خاصة للإشارة إلى

1000
00:43:19,530 --> 00:43:20,400
الإيجابية على السلبية.

1001
00:43:20,400 --> 00:43:22,950
انها قليلا أكثر تعقيدا من ذلك،
ولكن هذه هي الفكرة الأساسية.

1002
00:43:22,950 --> 00:43:26,740
>> ذلك لسوء الحظ، إذا C هو واحد مربك
من هذه البتات يعني كما في الواقع،

1003
00:43:26,740 --> 00:43:30,790
أوه، هذا هو رقم سلبي، حلقة بلدي
هنا، على سبيل المثال، هو في الواقع أبدا

1004
00:43:30,790 --> 00:43:31,740
ذاهب لإنهاء.

1005
00:43:31,740 --> 00:43:33,850
حتى لو كنت تطبع في الواقع شيئا
مرارا وتكرارا، كنا

1006
00:43:33,850 --> 00:43:34,650
نرى الكثير كله.

1007
00:43:34,650 --> 00:43:36,220
ولكن مرة أخرى، وهذا هو جانب هذه النقطة.

1008
00:43:36,220 --> 00:43:38,590
هذا هو في الحقيقة مجرد نوع من
الفضول الفكري أننا سوف يأتي

1009
00:43:38,590 --> 00:43:39,550
إلى نهاية المطاف.

1010
00:43:39,550 --> 00:43:43,400
لكنه الآن، وهذا هو الصحيح
تنفيذ إذا افترضنا أن

1011
00:43:43,400 --> 00:43:45,970
وسوف توفر للمستخدم رجات
التي تدخل ضمن رجات.

1012
00:43:45,970 --> 00:43:49,370
>> ولكن أزعم أن هذا الرمز، بصراحة،
يمكن القيام به أكثر من ذلك بكثير ببساطة.

1013
00:43:49,370 --> 00:43:54,060
إذا كان الهدف في متناول اليد هو اتخاذ عدد
مثل م وتضيف ما يصل كل من

1014
00:43:54,060 --> 00:43:59,510
أرقام بينه و 1، أو العكس
بين 1 و عليه، أزعم

1015
00:43:59,510 --> 00:44:03,380
أستطيع أن تقترض هذا فكرة أن دمج
كان نوعا، والتي تتخذ مشكلة

1016
00:44:03,380 --> 00:44:05,660
من هذا الحجم وتقسيمه
إلى شيء أصغر.

1017
00:44:05,660 --> 00:44:09,875
ربما ليس النصف، ولكنها أصغر حجما، ولكن
تمثيلي نفسه.

1018
00:44:09,875 --> 00:44:12,130
نفس الفكرة، ولكن مشكلة صغيرة.

1019
00:44:12,130 --> 00:44:15,470
>> لذلك أنا في الواقع - اسمحوا لي حفظ هذا الملف
مع رقم إصدار مختلف.

1020
00:44:15,470 --> 00:44:17,670
وسوف ندعو هذا الإصدار
1 بدلا من 0.

1021
00:44:17,670 --> 00:44:20,790
وأزعم أنني يمكن في الواقع
reimplement هذا في هذا النوع من

1022
00:44:20,790 --> 00:44:22,160
طريقة الانحناء العقل.

1023
00:44:22,160 --> 00:44:23,710
>> أنا ذاهب إلى ترك جزء منه وحده.

1024
00:44:23,710 --> 00:44:27,710
انا ذاهب الى القول إذا م هو أقل
من أو حتى يساوي 0 -

1025
00:44:27,710 --> 00:44:29,280
أنا ذاهب لمجرد أن يكون قليلا
مزيد من الشرج وهذه المرة

1026
00:44:29,280 --> 00:44:30,520
مع التحقق من الخطأ بلدي -

1027
00:44:30,520 --> 00:44:33,190
انا ذاهب الى المضي قدما والعودة 0.

1028
00:44:33,190 --> 00:44:34,490
هذا هو إجراء تعسفي.

1029
00:44:34,490 --> 00:44:37,500
أنا ببساطة تحديد ما إذا كان المستخدم
يعطيني رقم سالب، وأنا

1030
00:44:37,500 --> 00:44:41,490
العودة 0، وكان ينبغي أن تقرأ
وثائق عن كثب.

1031
00:44:41,490 --> 00:44:42,170
>> آخر -

1032
00:44:42,170 --> 00:44:44,070
لاحظ ما أنا ذاهب الى القيام به.

1033
00:44:44,070 --> 00:44:49,260
آخر وانا ذاهب الى العودة متر زائد -

1034
00:44:49,260 --> 00:44:51,010
ما هو سيغما من م؟

1035
00:44:51,010 --> 00:44:56,710
حسنا، سيجما للمتر زائد ناقص 1 م،
بالإضافة إلى 3 م ناقص 2، بالإضافة إلى م ناقص.

1036
00:44:56,710 --> 00:44:58,030
أنا لا أريد أن أكتب كل ذلك الخروج.

1037
00:44:58,030 --> 00:44:59,120
لماذا لا أنا فقط البونت؟

1038
00:44:59,120 --> 00:45:05,080
أسمي نفسي متكرر مع قليلا
المشكلة أصغر، الفاصلة المنقوطة،

1039
00:45:05,080 --> 00:45:06,840
ويطلق عليه اليوم؟

1040
00:45:06,840 --> 00:45:07,040
>> أليس كذلك؟

1041
00:45:07,040 --> 00:45:10,980
الآن هنا، أيضا، قد تشعر أو تقلق
أن هذا هو حلقة لا نهائية أنني

1042
00:45:10,980 --> 00:45:15,450
حمل، حيث إنني تنفيذ
سيغما بالدعوة سيغما.

1043
00:45:15,450 --> 00:45:20,342
ولكن هذا موافق تماما، لأنني
التفكير في المستقبل والتي خطوط المضافة؟

1044
00:45:20,342 --> 00:45:22,600
>> الحضور: [غير مسموع].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID مالان: 23 إلى 26، والتي
هي لغتي إذا كان الشرط.

1046
00:45:25,430 --> 00:45:28,390
لأن ما هو لطيف حول
الطرح هنا، لأن أظل

1047
00:45:28,390 --> 00:45:31,180
تسليم سيغما مشاكل أصغر، أصغر
مشاكل، أصغر - انها ليست

1048
00:45:31,180 --> 00:45:31,870
نصف حجم.

1049
00:45:31,870 --> 00:45:34,380
انها فقط خطوة الطفل أصغر،
ولكن هذا موافق.

1050
00:45:34,380 --> 00:45:38,050
لأن في نهاية المطاف، وسوف نعمل
طريقنا إلى 1 أو 0.

1051
00:45:38,050 --> 00:45:41,630
وبمجرد ان تصل 0، سيغما ليست
سوف تسمي نفسها بعد الآن.

1052
00:45:41,630 --> 00:45:43,590
انها تسير على العودة فورا 0.

1053
00:45:43,590 --> 00:45:47,960
>> وبالتالي فإن تأثير، إذا كنت نوع من الرياح هذا
حتى في عقلك، هي إضافة م زائد

1054
00:45:47,960 --> 00:45:52,740
م ناقص 1، بالإضافة إلى ناقص 2 م، بالإضافة إلى م ناقص
3، بالإضافة إلى نقطة، نقطة، نقطة، م ناقص

1055
00:45:52,740 --> 00:45:57,820
م، وإعطاء في نهاية المطاف لك 0، و
أثر هو في نهاية المطاف إلى إضافة كافة

1056
00:45:57,820 --> 00:45:59,070
هذه الأشياء معا.

1057
00:45:59,070 --> 00:46:02,380
لذلك ليس لدينا، مع العودية،
حل المشكلة أننا

1058
00:46:02,380 --> 00:46:03,470
لا يمكن أن تحل من قبل.

1059
00:46:03,470 --> 00:46:06,840
في الواقع، نسخة 0 من هذا، وعلى كل
المشكلة حتى الآن، كانت قابلة للحل

1060
00:46:06,840 --> 00:46:09,980
مع مجرد استخدام للحلقات أو أثناء
الحلقات أو بنيات مماثلة.

1061
00:46:09,980 --> 00:46:13,150
>> ولكن العودية، ونحسب، يعطينا
طريقة مختلفة في التفكير

1062
00:46:13,150 --> 00:46:17,010
مشاكل، حيث ما اذا كنا نستطيع اتخاذ
المشكلة، نقسمه من شيء

1063
00:46:17,010 --> 00:46:22,340
كبيرة نوعا ما إلى شيء إلى حد ما
أصغر، أزعم أننا يمكن أن تحل على

1064
00:46:22,340 --> 00:46:26,040
أكثر ربما قليلا من حيث بأناقة
من التصميم، مع أقل الرمز،

1065
00:46:26,040 --> 00:46:30,980
وربما حتى حل المشاكل التي من شأنها أن
يكون من الصعب، كما سنقوم في نهاية المطاف

1066
00:46:30,980 --> 00:46:33,280
ترى، حل تكراري بحتة.

1067
00:46:33,280 --> 00:46:35,980
>> ولكن التشويق التي فعلت
تريد أن تترك لنا على هذا كان.

1068
00:46:35,980 --> 00:46:40,720
اسمحوا لي المضي قدما وفتح
حتى ملف من -

1069
00:46:40,720 --> 00:46:44,300
في الواقع، اسمحوا لي ان اذهب و
القيام بذلك بسرعة حقيقية.

1070
00:46:44,300 --> 00:46:46,875
اسمحوا لي المضي قدما واقتراح
ما يلي.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
بين كود اليوم هو هذا الملف هنا.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
هذا واحد هنا، noswap.

1075
00:47:03,050 --> 00:47:06,260
>> لذلك هذا هو برنامج غبي القليل الذي
أنا جلد حتى التي تدعي القيام به

1076
00:47:06,260 --> 00:47:06,940
ما يلي.

1077
00:47:06,940 --> 00:47:10,140
في الرئيسي، فإنها تعلن أولا
دعا الباحث العاشر ويسند

1078
00:47:10,140 --> 00:47:11,100
قيمة 1.

1079
00:47:11,100 --> 00:47:13,520
بعد ذلك يعلن الباحث ذ و
يسند قيمة 2.

1080
00:47:13,520 --> 00:47:15,310
بعد ذلك بطباعة ما x و y هو.

1081
00:47:15,310 --> 00:47:17,781
ثم تقول، مبادلة، نقطة نقطة نقطة.

1082
00:47:17,781 --> 00:47:21,670
>> ثم يدعي أن استدعاء دالة
دعا المبادلة، ويمر في العاشر و

1083
00:47:21,670 --> 00:47:24,290
ذ، فكرة وهي أن نأمل
x و y سوف يعود

1084
00:47:24,290 --> 00:47:25,620
مختلفة، والعكس.

1085
00:47:25,620 --> 00:47:27,110
بعد ذلك يدعون تبادلت!

1086
00:47:27,110 --> 00:47:28,420
مع علامة تعجب.

1087
00:47:28,420 --> 00:47:30,190
بعد ذلك بطباعة x و y.

1088
00:47:30,190 --> 00:47:33,480
>> ولكن تبين أن هذا جدا
مظاهرة بسيطة أسفل

1089
00:47:33,480 --> 00:47:35,570
هنا هو عربات التي تجرها الدواب في الواقع.

1090
00:47:35,570 --> 00:47:38,870
على الرغم من أنني إعلان مؤقتة
متغير ووضع مؤقتا في

1091
00:47:38,870 --> 00:47:42,010
ذلك، ثم أنا إعادة تعيين
وقيمة ب -

1092
00:47:42,010 --> 00:47:45,080
الذي يشعر معقولة، لأن لدي
حفظ نسخة من في درجة الحرارة.

1093
00:47:45,080 --> 00:47:48,410
ثم أقوم بتحديث ب على قدم المساواة
كل ما كان في درجة الحرارة.

1094
00:47:48,410 --> 00:47:51,610
هذا النوع من لعبة قذيفة من تحريك
إلى ب وب في باستخدام هذا

1095
00:47:51,610 --> 00:47:54,360
يشعر رجل في منتصف تسمى درجة الحرارة
معقول تماما.

1096
00:47:54,360 --> 00:47:57,270
>> ولكن أزعم أنني عندما تشغيل هذا
رمز، كما سأفعل الآن -

1097
00:47:57,270 --> 00:47:59,490
اسمحوا لي أن تمضي قدما والصقه هنا.

1098
00:47:59,490 --> 00:48:01,995
سأتصل هذا noswap.c.

1099
00:48:01,995 --> 00:48:05,630
وكما يوحي اسمها، وهذا ليس
سيكون البرنامج الصحيح.

1100
00:48:05,630 --> 00:48:09,460
جعل noswap. / لا المبادلة.

1101
00:48:09,460 --> 00:48:12,110
x هو 1، ص 2، مبادلة، تبادلت.

1102
00:48:12,110 --> 00:48:14,220
x هو 1، ص 2.

1103
00:48:14,220 --> 00:48:16,920
هذا هو خطأ جوهري، حتى
رغم أن هذا يبدو تماما

1104
00:48:16,920 --> 00:48:17,730
معقول بالنسبة لي.

1105
00:48:17,730 --> 00:48:21,330
وهناك سبب، ولكن نحن لسنا
سوف تكشف عن السبب فقط حتى الآن.

1106
00:48:21,330 --> 00:48:24,610
>> الآن والتشويق الثانية أردت
أن أترككم مع هذا، و

1107
00:48:24,610 --> 00:48:27,120
إعلان من نوع ما على رموز القسيمة.

1108
00:48:27,120 --> 00:48:31,590
لدينا الابتكار مع الأيام أواخر هذا العام
أثارت عددا غير تافهة

1109
00:48:31,590 --> 00:48:33,830
من الأسئلة، والتي كان
وليس لدينا النية.

1110
00:48:33,830 --> 00:48:36,590
نية هذه رموز القسيمة،
حيث إذا قمت بذلك جزءا من المشكلة

1111
00:48:36,590 --> 00:48:39,850
تعيين في وقت مبكر، وبالتالي الحصول على يوم إضافي،
كان حقا للمساعدة يا رفاق مساعدة

1112
00:48:39,850 --> 00:48:42,420
نفسك تبدأ في وقت مبكر، نوع
من قبل تحفيز لك.

1113
00:48:42,420 --> 00:48:44,880
يساعدنا على توزيع التحميل عبر
ساعات العمل أفضل بحيث

1114
00:48:44,880 --> 00:48:45,740
انها نوع من الفوز.

1115
00:48:45,740 --> 00:48:48,860
>> للأسف، أعتقد تعليماتي
لم تكن، حتى الآن، واضحة جدا، لذلك

1116
00:48:48,860 --> 00:48:52,230
عدت في نهاية هذا الاسبوع وتحديثها
المواصفات في أكبر وأكثر جرأة النص ل

1117
00:48:52,230 --> 00:48:53,600
شرح الرصاص مثل هذه.

1118
00:48:53,600 --> 00:48:56,900
ومجرد أن أقول ذلك علنا ​​أكثر، من خلال
الافتراضي، ومجموعات مشكلة من المقرر الخميس

1119
00:48:56,900 --> 00:48:58,400
عند الظهر، في المنهج.

1120
00:48:58,400 --> 00:49:02,030
إذا كنت تبدأ في وقت مبكر، والانتهاء من جزء من
مشكلة تعيين بحلول يوم الأربعاء في تمام الساعة 12:00

1121
00:49:02,030 --> 00:49:05,170
مساء، الجزء الذي يتصل قسيمة
رمز، والفكرة هي أنك يمكن أن تمتد

1122
00:49:05,170 --> 00:49:07,710
آخر موعد للحصول على
تعيين P حتى يوم الجمعة.

1123
00:49:07,710 --> 00:49:10,890
وهذا هو، قضم جزء صغير من P
تعيين نسبة إلى ما هو عادة

1124
00:49:10,890 --> 00:49:13,200
مشكلة أكبر، وتشتري
نفسك يوما إضافيا.

1125
00:49:13,200 --> 00:49:15,190
مرة أخرى، فإنه يحصل لك التفكير
مشكلة تعيين، ويحصل لك

1126
00:49:15,190 --> 00:49:16,380
ساعات العمل عاجلا.

1127
00:49:16,380 --> 00:49:20,670
ولكن المشكلة لا تزال رمز القسيمة
المطلوبة، حتى لو كنت لا تضعها.

1128
00:49:20,670 --> 00:49:23,340
>> ولكن أكثر مقنع هو هذا.

1129
00:49:23,340 --> 00:49:26,520
(STAGE WHISPER) وهؤلاء الناس ترك
وستعمل يندم عليه في وقت مبكر.

1130
00:49:26,520 --> 00:49:28,620
وكذلك الناس على الشرفة.

1131
00:49:28,620 --> 00:49:32,510
أعتذر مقدما الى الناس على
الشرفة لأسباب من شأنها أن تكون

1132
00:49:32,510 --> 00:49:33,920
مسح في مجرد لحظة.

1133
00:49:33,920 --> 00:49:37,050
>> لذلك نحن محظوظون لأن لدينا واحدة من
السابق زملاء التدريس في الرأس CS50 في

1134
00:49:37,050 --> 00:49:39,302
شركة تدعى dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
تبرعوا بسخاء جدا لديهم
رمز القسيمة هنا لهذه المساحة من ذلك بكثير،

1136
00:49:45,500 --> 00:49:48,180
وهو ما يصل من
2 غيغابايت المعتادة.

1137
00:49:48,180 --> 00:49:51,740
ذلك ما كنت أعتقد أننا سوف نفعل على هذا
ملاحظة أخيرة هي تفعل شيئا من الهبات،

1138
00:49:51,740 --> 00:49:55,380
حيث في مجرد لحظة، ونحن سوف تكشف
الفائز والذي لديه القسيمة

1139
00:49:55,380 --> 00:49:57,980
التعليمات البرمجية التي يمكنك ثم انتقل إلى هم
الموقع، اكتب في ذلك، وفويلا، والحصول على

1140
00:49:57,980 --> 00:50:01,370
أكثر بأسره الكثير قطاف الفضاء الخاصة بك
الأجهزة والملفات الشخصية.

1141
00:50:01,370 --> 00:50:05,690
>> والأولى، الذين يرغبون في المشاركة
في هذا الرسم؟

1142
00:50:05,690 --> 00:50:09,630
حسنا، الآن أن يجعلها أكثر متعة.

1143
00:50:09,630 --> 00:50:14,010
الشخص الذي يتلقى هذا 25 غيغابايت
رمز القسيمة - والتي هي الآن

1144
00:50:14,010 --> 00:50:16,150
أكثر إقناعا من أواخر
أيام الآن، وربما -

1145
00:50:16,150 --> 00:50:20,620
هو الذي يجلس على قمة
التي تحت وسادة المقعد هناك

1146
00:50:20,620 --> 00:50:21,620
أن رمز القسيمة.

1147
00:50:21,620 --> 00:50:23,480
أنت الآن قد تبدو تحت
وسادة المقعد الخاص بك.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [تشغيل الفيديو]

1150
00:50:29,680 --> 00:50:31,620
>> واحد، اثنان، ثلاثة.

1151
00:50:31,620 --> 00:50:35,015
>> [صراخ]

1152
00:50:35,015 --> 00:50:35,985
>> أنت تحصل على سيارة!

1153
00:50:35,985 --> 00:50:36,670
تحصل على سيارة!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID مالان: سنرى
كنت يوم الاربعاء.

1155
00:50:37,970 --> 00:50:38,904
>> أنت تحصل على سيارة!

1156
00:50:38,904 --> 00:50:39,371
تحصل على سيارة!

1157
00:50:39,371 --> 00:50:40,305
تحصل على سيارة!

1158
00:50:40,305 --> 00:50:41,706
تحصل على سيارة!

1159
00:50:41,706 --> 00:50:43,107
تحصل على سيارة!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID مالان: الناس شرفة، وتأتي
إلى هنا إلى الجبهة،

1161
00:50:45,530 --> 00:50:46,866
حيث لدينا اشياء.

1162
00:50:46,866 --> 00:50:50,282
>> -كل شخص يحصل على سيارة!

1163
00:50:50,282 --> 00:50:52,234
الجميع يحصل على السيارة!

1164
00:50:52,234 --> 00:50:52,722
>> [END تشغيل الفيديو]

1165
00:50:52,722 --> 00:50:54,590
>> المعلق: في CS50 المقبل -

1166
00:50:54,590 --> 00:51:00,374
>> سرور 5: يا إلهي يا إلهي يا إلهي يا إلهي
إلهي إلهي إلهي إلهي إلهي إلهي -

1167
00:51:00,374 --> 00:51:02,106
>> [[أوكلل] يلعب]