[عزف الموسيقى] DAVID مالان: حسنا. كل الحق، نرحب مرة. لذلك هذا هو الأسبوع 4، بداية منها، بالفعل. وعليك أن تتذكر أنه في الأسبوع الماضي، وضعنا رمز جانبا لقليلا فقط وبدأنا نتحدث أكثر من ذلك بقليل رفيع المستوى، حول أشياء مثل البحث والفرز، والتي على الرغم من أفكار بسيطة إلى حد ما، هي ممثل فئة من المشاكل سوف نبدأ في حل ولا سيما عندما تبدأ في التفكير في النهائي المشاريع والحلول للاهتمام لك قد تضطر إلى المشاكل في العالم الحقيقي. الآن هو فقاعة نوع واحد من أبسط هذه الخوارزميات، و عملت من خلال وجود هذه الأعداد الصغيرة في قائمة أو في مجموعة من نوع فقاعة طريقهم صعودا إلى الأعلى، و أرقام كبيرة تتحرك طريقهم وصولا الى نهاية تلك القائمة. 

وأذكر أننا يمكن أن تصور فقاعة نوع قليلا شيء من هذا القبيل. لذلك اسمحوا لي المضي قدما وانقر فوق ابدأ. لقد انتقاؤه فقاعة الفرز. وإذا كنت أذكر أن الأزرق أطول خطوط تمثل الأرقام الكبيرة والصغيرة الخطوط الزرقاء تمثل أعداد صغيرة، و نذهب من خلال هذا مرارا وتكرارا و مرة أخرى، المقارنة بين اثنين من القضبان بجانب بعضها أخرى باللون الأحمر، ونحن في طريقنا للمبادلة أكبر وأصغر إذا هم خارج الترتيب. 

ولذلك فإن هذا سوف يستمر ويستمر ويذهب على، وسترى أن أكبر عناصر ويشقون طريقهم إلى الحق، والعناصر هي أصغر يشقون طريقهم إلى اليسار. ولكن بدأنا في تحديد كفاءة، و نوعية هذه الخوارزمية. وقلنا أنه في أسوأ الحالة، استغرق هذه الخوارزمية تقريبا كم عدد الخطوات؟ 

حتى ن المربعة. وما كان ن؟ 

الحضور: عدد من العناصر. 

DAVID مالان: لذا كان ن عدد من العناصر. ولذا فإننا سوف نفعل ذلك في كثير من الأحيان. أي وقت نريد أن نتحدث عن حجم وجود مشكلة أو حجم ل المدخلات، أو مقدار الوقت الذي يستغرقه لإنتاج الإخراج، سنقوم فقط معمم مهما المدخلات كما ن. لذلك مرة أخرى في الأسبوع 0، عدد الصفحات في دفتر الهاتف وكان ن. عدد الطلاب في الغرفة كان ن. حتى هنا، أيضا، أننا التالية هذا النمط. 

الآن ن التربيعية ليس بشكل خاص بسرعة، لذلك حاولنا أن نفعل ما هو أفضل. وهكذا نحن ننظر في بضعة خوارزميات أخرى، من بينها كان اختيار نوع. لذلك كان اختيار نوع مختلفة قليلا. كان أبسط تقريبا، أجرؤ على القول، حيث بدأت في بداية قائمة المتطوعين لدينا وأنا فقط مرة أخرى ومرة أخرى ومرة ​​أخرى ذهبت من خلال القائمة، نتف من أصغر عنصر في وقت واحد، ووضع له أو لها في بداية القائمة. 

ولكن هذا، أيضا، بدأنا مرة واحدة للتفكير من خلال الرياضيات وأكبر الصورة، فكرت كم مرة كنت ذاهبا ذهابا وإيابا والعودة وهكذا، قلنا في أسوأ الحالات، اختيار نوع، أيضا، كان ماذا؟ ن المربعة. الآن في العالم الحقيقي، فإنه قد يكون في الواقع هامشية أسرع. لأن مرة أخرى، لم يكن لدي للحفاظ على التراجع مرة واحدة كنت قد فرز أصغر العناصر. ولكن إذا كنا نفكر ن كبير جدا، و إذا كنت نوع من القيام بها في الرياضيات كما فعلت على متن الطائرة، مع ن التربيعية ناقص شيء، كل شيء آخر إلى جانب ن التربيعية، مرة واحدة ن يحصل كبيرة حقا، لا حقا يهم بقدر. حتى علماء الكمبيوتر، ونحن نوع من تغض الطرف عن أصغر العوامل والتركيز فقط على عامل في تعبير ذاهب الى جعل أكبر الفرق. 

حسنا، أخيرا، ونحن ننظر في الإدراج الفرز. وكان هذا مماثلة في الروح، ولكن بدلا من الذهاب من خلال تكراري و حدد العنصر أصغر واحد في الوقت، وأنا بدلا من ذلك أخذت اليد التي أنا تم التعامل، وقررت، كل الحق، كنت تنتمي هنا. ثم انتقلت إلى العنصر التالي وقرر انه او لأنها تنتمي هنا. ثم انتقلت على وعلى. وأنا قد ل، على طول الطريق، تحول هؤلاء الرجال من أجل إفساح المجال لهم. لذلك كان هذا النوع من الانعكاس العقلي اختيار النوع الذي نحن دعا الإدراج الفرز. 

وبالتالي فإن هذه الموضوعات التي تحدث في العالم الحقيقي. قبل بضع سنوات، عندما معينة وكان عضو مجلس الشيوخ الترشح للرئاسة، إريك شميدت، في الوقت الرئيس التنفيذي ل جوجل، كان في الواقع الفرصة لإجراء مقابلة معه. وكنا نظن أننا سوف تتقاسم هذه يوتيوب مقطع بالنسبة لك هنا، إذا نحن يمكن أن يحضر وحدة التخزين. 

[تشغيل الفيديو] 

حتى الآن، عضو مجلس الشيوخ، وكنت هنا في جوجل، وأود أن أفكر في الرئاسة كما مقابلة عمل. 

[ضحك] 

حتى الآن كان من الصعب الحصول على وظيفة الرئيس. وأنت تسير من خلال قسوة الآن. كما انها من الصعب الحصول على وظيفة في جوجل. لدينا ونسأل الأسئلة المرشحين أسئلتنا. وهذا هو واحد من لاري شويمر. 

[ضحك] أنت رفاق أعتقد أنا تمزح؟ انها هنا. ما هي الطريقة الأكثر فعالية ل فرز الأعداد الصحيحة اثنين مليون بت؟ 

[ضحك] 

حسنا، اه - 

-أنا آسف. ربما ينبغي لنا - 

لا، لا، لا، لا، لا. 

ذلك ليس ل- موافق. 

-I أعتقد أن فقاعة سوف الفرز تكون طريقة خاطئة للذهاب. 

[ضحك] 

[هتاف والتصفيق] 

تعال، الذي قال له ذلك؟ موافق. 

[END تشغيل الفيديو] 

DAVID مالان: وهكذا فإنه يوجد لديك. لذلك بدأنا في تحديد هذه تشغيل مرات، إذا جاز التعبير، مع شيء دعا تدوين مقارب، وهو فقط في اشارة الى لدينا نوع من تحول غضت الطرف عن تلك العوامل أصغر و يبحث فقط في وقت التشغيل، أداء هذه الخوارزميات، كما ن يحصل كبيرة حقا مع مرور الوقت. وهكذا قدمنا ​​كبيرة وكبيرة O O. تمثل شيئا كنا نظن باعتبارها من الحد الأعلى. وفعلا، باري، يمكننا خفض من هيئة التصنيع العسكري قليلا؟ 

كنا نظن هذا هو الحد الأعلى. يعني يا كبيرة جدا ن المربعة التي في في أسوأ الحالات، شيء من هذا القبيل أن اختيار نوع اتخاذ ن التربيعية الخطوات. أو شيء من هذا القبيل الإدراج الفرز سوف ن التربيعية الخطوات. الآن لشيء من هذا القبيل الإدراج نوع، ما كان أسوأ الحالات؟ نظرا صفيف، ما هو أسوأ السيناريو المحتمل أنك قد تجد تواجه نفسك؟ 

انها الوراء تماما، أليس كذلك؟ لأنه إذا كان هذا الخلف تماما، ما عليك القيام به في مجموعها الكثير من العمل. لأنه إذا كنت الوراء تماما، وأنت تسير لتجد أكبر عنصر هنا، على الرغم من انه ينتمي الى هناك. لذلك كنت أريد أن أقول، كل الحق، في هذه اللحظة في الوقت المناسب، كنت تنتمي هنا، لذلك أنت تترك وحدها. 

ثم كنت أدرك، أوه، اللعنة، لقد ل نقل هذا العنصر أصغر قليلا ل يسار لك. ثم يجب أن أقوم به ذلك مرة أخرى ومرة أخرى ومرة ​​أخرى. وإذا مشيت ذهابا وإيابا، ل ستشعر نوع من أداء أن الخوارزمية، لأن أنا كنت باستمرار خلط الجميع لأسفل في مجموعة لإفساح المجال لذلك. ذلك أن أسوأ الحالات. 

على النقيض من ذلك - وكان هذا التشويق في المرة السابقة - قلنا أن الإدراج الفرز كان أوميغا ماذا؟ ما هو أفضل حالة تشغيل وقت الإدراج الفرز؟ حتى انها في الواقع ن. كان ذلك الفراغ الذي غادرنا على متن الطائرة آخر مرة. 

وانها أوميغا ن لماذا؟ حسنا، في أفضل حال، ما هو الإدراج الفرز ستكون سلم؟ كذلك، قائمة وهذا ما فرزها تماما بالفعل، والعمل الحد الأدنى للقيام به. ولكن ما هو أنيق حول نوع الإدراج هو أن لأنه يبدأ من هنا و يقرر، أوه، كنت عدد واحد، كنت تنتمي هنا. أوه، يا له من الحظ الجيد. 

كنت في المركز الثاني. أنت أيضا تنتمي هنا. رقم ثلاثة، وحتى أفضل، كنت تنتمي هنا. بمجرد أن يحصل على نهاية القائمة، في هذا النوع الإدراج شبة الكود أن مشينا من خلال لفظيا آخر مرة، انها فعلت. ولكن اختيار نوع، على النقيض من ذلك، أبقى يفعل ماذا؟ 

تبقى مستمرة من خلال قائمة مرة أخرى ومرة ​​أخرى ومرة ​​أخرى. لأن الفكرة الرئيسية لم يكن هناك سوى مرة واحدة كنت قد بحثت عن وسيلة ل نهاية القائمة يمكنك أن تكون على يقين أن العنصر الذي حددته كان في الواقع أصغر عنصر حاليا. لذلك فان هذه النماذج العقلية مختلفة انهاء تصل الغلة بعض جدا في العالم الحقيقي الاختلافات بالنسبة لنا، وكذلك هذه الاختلافات مقارب النظرية. 

وذلك فقط لخلاصة، إذن، يا كبير من ن مربع، شاهدنا عدد قليل من هذه خوارزميات حتى الآن. O كبيرة من ن؟ ما هو خوارزمية التي يمكن أن أن يقال أن تكون يا كبير من ن؟ في أسوأ الحالات، فإنه يأخذ عدد خطية من الخطوات. 

موافق، والبحث الخطي. وفي أسوأ الحالات، حيث هو العنصر الذي تبحث عنه عند تطبيق البحث الخطي؟ 

حسنا، في أسوأ الحالات، انها ليست حتى هناك. أو في أسوأ الحالات الثانية، انها كل وسيلة في نهاية المطاف، وهو زائد أو ناقص فرق من خطوة واحدة. حتى في نهاية المطاف، يمكننا القول انها خطية. سوف يا كبير من ن يكون البحث الخطي، لأنه في أسوأ الحالات، و العنصر ليس حتى هناك أو انها كل وسيلة في نهاية المطاف. 

حسنا، يا كبير من سجل ن. لم نتحدث بقدر كبير من التفصيل حول هذا، ولكن شاهدنا هذا من قبل. ما يعمل في ما يسمى لوغاريتمي الوقت، في أسوأ الحالات؟ 

نعم، البحث الثنائي بذلك. والبحث الثنائي في أسوأ الحالات قد يكون العنصر في مكان ما الوسط، أو في مكان ما داخل مجموعة. ولكن فقط تجد أنه بمجرد تقسيم القائمة إلى النصف، في النصف، في النصف، في النصف. ثم فويلا، انها هناك. أو مرة أخرى، أسوأ الحالات، انها ليست حتى هناك. ولكن كنت لا تعرف أنه ليس هناك حتى يمكنك الوصول إلى هذا النوع من الماضي من أسفل إلى معظم العناصر عن طريق خفض وبمقدار النصف وبمقدار النصف. 

O كبيرة من 1. ولذا فإننا يمكن يا كبير من 2 يا كبير 3. في أي وقت كنت ترغب فقط في عدد ثابت، نحن مجرد نوع من مجرد تبسيط أن يا كبير اعتبارا من 1. على الرغم من واقعية إذا، فإنه يأخذ 2 أو حتى 100 الخطوات، لو كان عدد ثابت من الخطوات، نحن نقول فقط يا كبير 1. ما هو خوارزمية هذا في O الكبيرة من 1؟ 

الحضور: العثور على طول من متغير. 

DAVID مالان: العثور على طول متغير؟ 

الحضور: لا، وطول إذا تم فرزها بالفعل. 

DAVID مالان: جيد. موافق، حتى العثور على طول شيء إذا كان طول أن شيئا ما، مثل صفيف، يتم تخزينها في بعض متغير. لأنك يمكن أن مجرد قراءة المتغير، أو طباعة المتغير، أو فقط الوصول إلى هذا المتغير عموما. وفويلا، وهذا يستغرق وقتا ثابتا. 

على النقيض من ذلك، والتفكير مرة أخرى إلى نقطة الصفر. التفكير مرة أخرى إلى الأسبوع الأول من C، الدعوة فقط والطباعة printf شيء ما على الشاشة يمكن القول وقت ثابت، لأنه يأخذ فقط بعض عدد من دورات وحدة المعالجة المركزية لإظهار أن النص على الشاشة. أو الانتظار - أليس كذلك؟ وإلا كيف يمكن لنا نموذج ل أداء printf؟ شخص ما من شأنه أحب أن نختلف، أن ربما انها ليست حقا وقت ثابت؟ في ما تشغيل القوة printf إحساس الوقت، الطباعة الواقع على سلسلة الشاشة، يكون شيئا غير ثابتة. 

الحضور: [غير مسموع]. 

DAVID مالان: نعم. لذلك يعتمد على وجهة نظرنا. إذا كنا نعتقد فعلا من المدخلات ل printf بأنها السلسلة، و وبالتالي نقيس حجم هذا مساهمة من قبل طوله - السماح لذلك ندعو أن طول ن وكذلك - يمكن القول، هو في حد ذاته printf يا كبير من ن لأنه ذاهب الى اتخاذ لكم ن الخطوات لطباعة كل تلك ن حرفا، على الأرجح. على الأقل إلى حد أن نفترض أنه ربما انها تستخدم لحلقة تحت غطاء محرك السيارة. 

ولكن علينا أن ننظر في ذلك رمز لنفهم على نحو أفضل. وبالفعل، بمجرد بدء الرجال تحليل الخوارزميات الخاصة بك، عليك تفعل ذلك تماما حرفيا. نوع من مقلة العين التعليمة البرمجية الخاصة بك والتفكير عن - كل الحق، ولدي هذه الحلقة هنا أو لدي حلقات متداخلة هنا، وهذا ما تنوي القيام به ن ن الأشياء مرات، ويمكنك نوع من التفكير طريقك خلال التعليمات البرمجية، حتى لو كان شبة الكود ورمز لا الفعلي. 

فكيف أوميغا ن التربيعية؟ ما كان خوارزمية في أفضل الحالة، لا يزال استغرق ن التربيعية الخطوات؟ نعم؟ 

الحضور: [غير مسموع]. 

DAVID مالان: حتى اختيار نوع. لأنه في هذه المشكلة خفضت حقا إلى حقيقة أن مرة أخرى، وأنا لا أعرف لقد وجدت أصغر الحالية حتى لقد راجعت جميع العناصر الرتق. حتى أوميغا، ويقول، ن، ونحن جاء للتو مع واحد. الإدراج الفرز. إذا حدث القائمة ليتم فرزها بالفعل، في أفضل الأحوال لدينا فقط لجعل مرور واحد من خلال ذلك، وعند هذه النقطة نحن على يقين. ثم ما يمكن أن يقال أن تكون خطية، لعلى يقين. 

ماذا عن أوميغا من 1؟ ما هي، في أفضل الأحوال، قد يستغرق عدد ثابت من الخطوات؟ البحث الخطي ذلك، إذا كنت مجرد الحصول على محظوظ وعنصر كنت تبحث هو الحق في بداية القائمة، إذا كان هذا هو المكان الذي بدأنا الخاص اجتياز خطية من تلك القائمة. 

وهذا صحيح ل عدد من الأمور. على سبيل المثال، حتى ثنائي البحث هو أوميغا 1. لأن ما إذا كنت تحصل على الرتق حقا الحظ وصفعة، الداب في منتصف الصفيف الخاص بك هو رقم كنت تبحث عنه؟ حتى تتمكن من الحصول على الحظ هناك، كذلك. 

هذا واحد، أخيرا، أوميغا ن ن سجل. حتى ن ن تسجيل، ونحن لم أكن حقا الحديث عن بعد، ولكن - 

الحضور: دمج النوع؟ 

DAVID مالان: دمج النوع. كان هذا هو التشويق من الزمن الماضي، حيث اقترحنا، وأظهرنا بصريا، أن هناك الخوارزميات. ودمج نوع واحد فقط من هذا القبيل الخوارزمية التي هي في الأساس أسرع من بعض هؤلاء الرجال الآخرين. في الواقع، ودمج القصير ليس فقط في أفضل الأحوال ن ن تسجيل، في أسوأ حالة ن ن سجل. وعندما يكون لديك هذا صدفة من أوميغا ويا كبير يجري نفس الشيء؟ نحن يمكن أن تصف الواقع أنه ما دعا ثيتا، على الرغم من انها أقل قليلا المشتركة. ولكن هذا يعني فقط أن حدود اثنين، في هذه الحالة، هي نفسها. 

لذلك دمج النوع، ما معنى هذا يغلي في الواقع إلى بالنسبة لنا؟ كذلك، تذكر الدافع. اسمحوا لي سحب ما يصل الرسوم المتحركة أخرى ونحن لم ننظر في الوقت الماضي. هذا واحد، نفس الفكرة، ولكن انها أكبر قليلا. وانا ذاهب الى المضي قدما ونشير أولا - لدينا الإدراج الفرز على أعلى اليسار، ثم اختيار نوع، فقاعة النوع، وزوجين من أنواع أخرى - قذيفة وسريعة - أننا لم تحدث حول، وكومة ودمج النوع. 

وذلك على الأقل في محاولة للتركيز عينيك على المراكز الثلاثة الاولى على اليسار ومن ثم دمج النوع عندما كنت فوق هذا السهم الأخضر. لكني ساترك كل منهم تشغيل، فقط ل تعطيك إحساسا للتنوع الخوارزميات التي توجد في العالم. انا ذاهب الى السماح لهذا المدى لثوان معدودة. وإذا كنت تركز عينيك - اختيار ل الخوارزمية، والتركيز على ذلك لمجرد ثانية - عليك أن تبدأ في رؤية النمط الذي انها المنفذة. 

دمج النوع، لاحظ، هو القيام به. نوع الكومة، النوع السريع، وشركة شل - هكذا يبدو قدمنا ​​ثلاثة أسوأ خوارزميات الاسبوع الماضي. ولكن هذا امر جيد اننا هنا اليوم ل ننظر في دمج النوع، والتي هي واحدة من أسهل منها هو أن ننظر إلى، حتى على الرغم من أنه من المحتمل أن ينحني عقلك قليلا فقط. هنا يمكننا أن نرى فقط كم تمتص اختيار نوع. 

ولكن على الجانب الآخر، انها حقا من السهل تنفيذها. وربما لمجموعة P 3، وهذا هو واحد من خوارزميات اخترت لتنفيذ للطبعة القياسية. ما يرام تماما، صحيح تماما. 

ولكن مرة أخرى، كما ن يحصل كبيرة، إذا كنت اختيار لتنفيذ خوارزمية أسرع مثل دمج النوع، الاحتمالات هي في أكبر و المدخلات أكبر، التعليمات البرمجية الخاصة بك هو مجرد الذهاب لتشغيل أسرع. موقع الويب الخاص بك هو الذهاب إلى العمل أفضل. المستخدمين ستكون أكثر سعادة. وحتى لا تكون هذه الآثار إعطاء الواقع لنا بعض أعمق الفكر. 

لذلك دعونا نلقي نظرة على ما الدمج نوع هو في الواقع كل شيء. الشيء هو أن تبرد دمج هذا النوع فقط. وهذا هو، مرة أخرى، ما كنا يسمى شبة الكود، يجري شبة الكود الإنجليزية مثل بناء الجملة. والبساطة هي نوع من رائعة. 

لذلك على المدخلات من العناصر ن - بحيث يعني فقط، وهنا صفيف. انها حصلت على ن الأشياء فيه. هذا كل ما نقوله هناك. 

إذا كان n أقل من 2، والعودة. لذلك كان هذا هو الحال تافهة فقط. إذا كان n أقل من 2، ثم من الواضح انها 1 أو 0، وفي هذه الحالة الشيء يتم فرز بالفعل أو غير موجودة، حتى مجرد العودة. هناك شيء للقيام به. ذلك أن حالة بسيطة لنتف قبالة. 

آخر، لدينا ثلاث خطوات. فرز النصف الأيسر من العناصر، نوع النصف الأيمن من العناصر، ثم دمج شطري فرزها. ما هو مثير للاهتمام هنا هو أن أنا نوع من التسيير، أليس كذلك؟ هناك نوع من تعريف دائري لهذه الخوارزمية. بأي معنى هذا الخوارزمية التعميم التعريف؟ 

الحضور: [غير مسموع]. 

DAVID مالان: نعم، خوارزمية الفرز بلدي، اثنين من خطواتها هي "نوع شيء ما ". وبحيث يطرح السؤال، حسنا، ما أنا ذاهب الى استخدام لفرز النصف الأيسر والنصف الأيمن؟ والجمال هنا هو أنه على الرغم من مرة أخرى، وهذا هو العقل والانحناء جزء يحتمل، يمكنك استخدام نفس خوارزمية لفرز النصف الأيسر. 

ولكن الانتظار لمدة دقيقة. عندما كنت وقال لفرز النصف الأيسر، ما هما الخطوات ستكون في المرة القادمة؟ سنقوم فرز النصف الأيسر من النصف الأيسر والأيمن نصف النصف الأيسر. اللعنة، كيف يمكنني فرز هذين نصفين، أو أرباع، والآن؟ 

ولكن هذا موافق. لدينا خوارزمية الفرز هنا. وعلى الرغم من أنك قد تقلق في أولا هذا هو نوع من لانهائية حلقة، انها دورة هذا أبدا الذهاب الى النهاية - هو ذاهب ل ينتهي بمجرد ما يحدث؟ مرة واحدة n هو أقل من 2. التي في النهاية سوف يحدث، لأنه إذا واصلتم بمقدار النصف و تخفيض في تخفيض هذه نصفين، وبالتأكيد في نهاية المطاف وأنت تسير لانهاء مع فقط 1 أو 0 العناصر. وعند هذه النقطة، هذه الخوارزمية يقول الانتهاء من ذلك. 

وبالتالي فإن السحر الحقيقي في هذا يبدو خوارزمية ليكون في أن الخطوة النهائية، ودمج. هذه الفكرة بسيطة دمج اثنين فقط الأشياء، وهذا ما يحدث في نهاية المطاف للسماح لنا لفرز مجموعة من، دعنا نقول، ثمانية عناصر. وذلك لدي ثماني كرات المزيد من الضغط حتى هنا، ثماني قطع من الورق، واحد جوجل زجاج - الذي أحصل على الاحتفاظ بها. 

[ضحك] 

DAVID مالان: إذا كنا قد يستغرق ثمانية المتطوعين، ودعونا نرى ما اذا كنا نستطيع تلعب هذه، لذلك. نجاح باهر، موافق. علوم الكمبيوتر هو الحصول على المتعة. حسنا. فكيف لك ثلاث، أكبر تصل ناحية هناك. أربعة في الخلف. وكيف حول سنفعل لك ثلاثة في هذا الصف؟ وأربعة في الجبهة. حتى تتمكن ثمانية، وتأتي على ما يصل. 

[ضحك] 

DAVID مالان: أنا فعلا لست متأكدا ما هو عليه. هو الكرات الإجهاد؟ مصابيح المنضدة؟ المادة؟ الإنترنت؟ 

موافق. ويأتي ذلك على ما يصل. أن الذين يحبون - تبقي الخروج. دعونا نرى. وهذا يضعك في موقع - كنت في مكان واحد. أه أوه، انتظر لحظة. 1، 2، 3، 4، 5، 6، 7 - أوه، جيد. كل الحق، نحن في حالة جيدة. كل الحق، لذلك الجميع لديها مقعد، ولكن ليس على زجاج جوجل. اسمحوا لي أن قائمة الانتظار هذه المباراة. ما اسمك؟ 

MICHELLE: ميشيل. 

DAVID مالان: ميشيل؟ كل الحق، وتحصل لتبدو وكأنها المهوس، إذا كان هذا هو موافق. حسنا، أنا لا جدا، وأنا أفترض، لمجرد لحظة. كل الحق، والاستعداد. كنا تحاول الخروج مع استخدام القضية لجوجل الزجاج، ونحن اعتقد انه سيكون من متعة القيام به فقط هذا عندما يكون الناس على خشبة المسرح. سنقوم بتسجيل العالم من وجهة نظرهم. حسنا. لا على الأرجح ما المقصود جوجل. كل الحق، إذا كنت لا تمانع في ارتداء هذه لدقائق محرجا المقبل، التي من شأنها أن تكون رائعة. 

كل الحق، لذلك لدينا هنا مجموعة من العناصر، وأن مجموعة، وفقا ل قطعة من الورق في هؤلاء الناس ' الأيدي، ويتم فرزها حاليا. 

MICHELLE: أوه، هذا غريب جدا. 

DAVID مالان: انها عشوائية الى حد كبير. ومجرد لحظة، ونحن ذاهبون لمحاولة لتنفيذ دمج النوع معا ونرى فيها أن الفكرة الرئيسية هي. والخدعة هنا مع دمج النوع هو شيء أننا لم يفترض حتى الآن. ونحن في الواقع بحاجة الى بعض مساحة إضافية. وذلك ما سيكون ولا سيما مثيرة للاهتمام في هذا هو أن هذه الرجال تسير على التحرك قليلا قليلا، لأنني ذاهب لنفترض أن هناك مجموعة إضافية من الفضاء، أقول، الحق وراءها. 

حتى لو انهم وراء كرسي، و هذا هو مجموعة الثانوية. لو انهم يجلس هنا، وهذا مجموعة الابتدائية. ولكن هذا هو المورد الذي لدينا لا الاستدانة حتى الآن مع فقاعة نوع، مع اختيار نوع، مع الإدراج الفرز. أذكر الأسبوع الماضي، والجميع فقط نوع من أسكن في المكان. أنها لم تستخدم أي ذاكرة إضافية. التي قطعناها على أنفسنا مجالا للناس من قبل نقل الناس حولها. 

لذلك هذا هو الفكرة الرئيسية، أيضا. هناك هذا مفاضلة، وبشكل عام في علوم الكمبيوتر، والموارد. إذا كنت ترغب في تسريع شيء مثل الوقت، وأنت تسير ل لديك لدفع ثمن. واحدة من تلك الأسعار هي في كثير من الأحيان الفضاء، مقدار الذاكرة أو الثابت مساحة القرص الذي تستخدمه. أو، بصراحة، فإن المبلغ الوقت مبرمج. كم من الوقت يستغرق لك، والإنسان، في الواقع لتنفيذ بعض أكثر خوارزمية معقدة. ولكن لهذا اليوم، والمفاضلة هو الزمان والمكان. 

إذا كان الأمر كذلك يا رفاق يمكن أن مجرد تصمد الخاص أرقام حتى يمكننا أن نرى أن كنت في الواقع مطابقة 4، 2، 6، 1، 3، 7، 8. ممتازة. لذلك أنا ذاهب الى محاولة لتنسيق الأشياء، إذا يا رفاق يمكن فقط اتبع بلدي الرصاص هنا. 

لذلك أنا ذاهب لتنفيذ، أولا، الخطوة الأولى من شبة الكود، وهو على المدخلات من العناصر ن، إذا كان n هو أقل من 2، ثم العودة. من الواضح، أن لا تطبيق، لذلك نحن على هذه الخطوة. حتى فرز النصف الأيسر من العناصر. وهذا يعني انا ذاهب الى التركيز بلدي الانتباه لمجرد لحظة على هذه أربعة رفاق هنا. كل الحق، ما يمكنني القيام به القادم؟ 

الجمهور: فرز النصف الأيسر. 

DAVID مالان: حتى الآن لا بد لي من فرز النصف الأيسر من هؤلاء الرجال. لأن مرة أخرى، تفترض لنفسك الهدف من ذلك هو لفرز النصف الأيسر. كيف يمكنك أن تفعل ذلك؟ ما عليك سوى اتباع التعليمات، حتى على الرغم من أننا نفعل ذلك مرة أخرى. حتى فرز النصف الأيسر. الآن أنا الفرز هذين اللاعبين. ماذا يأتي بعد ذلك؟ 

الجمهور: فرز النصف الأيسر. 

DAVID مالان: فرز النصف الأيسر. وحتى الآن هذه، هذا المقعد هنا، هي قائمة حجم 1. وما اسمك مرة أخرى؟ 

PRINCESS ديزي: الأميرة ديزي. 

DAVID مالان: الأميرة ديزي هنا. وحتى أنها يتم فرز بالفعل، ل القائمة هو من حجم 1. ما يمكنني القيام به القادم؟ موافق، والعودة، لأن هذا هو قائمة من حجم 1، والذي هو أقل من 2. ثم ما هي الخطوة التالية؟ والآن لديك لنوع من التراجع في عقلك. 

فرز النصف الأيمن، والذي هو - ما اسمك؟ 

ليندا: ليندا. 

DAVID مالان: ليندا. وهكذا ماذا نفعل الآن بعد أن لدينا قائمة من حجم 1؟ 

الحضور: العودة. 

DAVID مالان: الدقيق. نعود الأولى، والآن ثالث خطوة - وإذا أنا نوع من تصور من قبل احتضان مقعدين الآن، وأنا الآن يجب أن دمج هذين العنصرين. وحتى الآن للأسف، العناصر هي خارج الترتيب. ولكن حيث ان عملية دمج يبدأ للحصول على مقنعة. 

إذا كان الأمر كذلك يا رفاق يمكن الوقوف فقط ل لحظة، وانا ذاهب لحاجة، في لحظة، إلى الخطوة راء مقعدك. وإذا ليندا، وذلك لأن 2 هو أصغر من 4، لماذا لا جئت في جميع أنحاء الأول؟ البقاء هناك. حتى ليندا، جئت في جميع أنحاء الأول. 

الآن في الواقع لو كان مجرد مجموعة أننا يمكن أن مجرد تحرك لها في الوقت الحقيقي من هذا الكرسي إلى هذه البقعة. لذلك أتصور أن أخذت بعض مستمر عدد من الخطوات 1. والآن - ولكن نحن بحاجة إلى وضعك في الموقع الأول هنا. 

والآن إذا كنت يمكن أن يأتي حولها، كذلك، ونحن في طريقنا ل تكون في موقع اثنين. وعلى الرغم من أن هذا يبدو وكأنه انها أخذ بعض الوقت، ما هو جميل الآن أن النصف الأيسر من الآن يتم فرز النصف الأيسر. فما كانت الخطوة التالية، واذا كنا الآن مزيد من الترجيع في القصة؟ 

الحضور: نصف الحق. 

DAVID مالان: فرز النصف الأيمن. لذلك يا رفاق لديهم للقيام بذلك، كذلك. حتى إذا كنت يمكن الوقوف لمجرد لحظة؟ وما هو اسمك؟ 

JESS: جيس. 

DAVID مالان: جيس. حسنا، الآن جيس اليسار نصف النصف الأيمن. وحتى انها قائمة من حجم 1. انها فرز واضح. واسمك مرة أخرى؟ 

MICHELLE: ميشيل. 

DAVID مالان: من الواضح أن ميشيل قائمة حجم 1. انها بالفعل فرزها. وحتى الآن السحر يحدث، عملية دمج. ذلك الذي يحدث أن يأتي أولا؟ ومن الواضح أن ميشيل. حتى إذا كنت يمكن أن يأتي حوالي الظهر. المساحة المتوفرة لدينا بالنسبة لها الآن هو حق وراء هذا الكرسي هنا. والآن إذا كنت يمكن أن يعود كذلك، لدينا الآن، أن تكون واضحة، وهما نصفين، كل من حجم 2 - وفقط من أجل تصوير، وإذا كنت يمكن أن قليلا من مساحة - واحد النصف الأيسر هنا، واحد النصف الأيمن هنا. 

مزيد من الترجيع في القصة. ما الخطوة التالية؟ 

الجمهور: دمج. 

DAVID مالان: حتى الآن لدينا لدمج. لذلك موافق، وحتى الآن، والحمد لله، ونحن حررت للتو أربعة كراسي. ولذا فإننا قد استخدمت مرتين قدر الذاكرة، ولكن نحن يمكن أن تعطي الوجه التخبط بين اثنين من المصفوفات. لذلك ما هو الرقم الذي هو يأتي أولا؟ حتى ميشيل، ومن الواضح. حتى يأتي حولها واتخاذ مقعدك هنا. ثم عدد 2 ومن الواضح المقبل، لذلك جئت هنا. عدد 4، رقم 6. ومرة أخرى، على الرغم من هناك قليلا من المشي المعنية، حقا، هذه يمكن أن يحدث على الفور، عن طريق تحريك واحد - موافق، لعبنا بشكل جيد. 

[ضحك] 

DAVID مالان: والآن نحن في حالة جيدة جدا. النصف الأيسر من كامل وقد تم الآن فرز المدخلات. كل الحق، لذلك كان لهؤلاء الرجال الاستفادة من بلدي - كيف أنه في نهاية المطاف جميع الفتيات على وغادر جميع الأولاد على حق؟ 

موافق، لذلك بدوره الرجال 'الآن. ولذا فإنني لن المشي لكم من خلال هذه الخطوات. سنرى ما اذا كنا نستطيع تطبيق نفس شبة الكود. إذا كنت ترغب في المضي قدما والوقوف، ويا رفاق، واسمحوا لي أن أقدم لكم هيئة التصنيع العسكري. معرفة ما اذا كنت لا يمكن تكرار ما نحن فقط لم هنا على الطرف الآخر من القائمة. الذي يحتاج إلى الكلام الأول، استنادا إلى خوارزمية؟ لذلك شرح ما تفعلونه قبل إجراء أية تحركات القدم. 

سرور 1: كل الحق، وذلك منذ أنا النصف الأيسر من ترك النصف، أعود. أليس كذلك؟ 

DAVID مالان: جيد. 

سرور 1: وبعد ذلك - 

DAVID مالان: من يفعل هيئة التصنيع العسكري انتقل إلى الخطوة التالية؟ 

سرور 1: عدد التالي. 

المتحدث 2: لذلك أنا النصف الأيمن من النصف الأيسر من ترك النصف، وأعود. 

DAVID مالان: جيد. عودتك. وحتى الآن ما هو القادم بالنسبة لك حتى اثنين؟ 

المتحدث 2: نريد معرفة من هو أصغر. 

DAVID مالان: بالضبط. نريد دمجها. الفضاء ونحن في طريقنا إلى استخدامها لدمج كنت في، على الرغم من انهم من الواضح فرز بالفعل، ونحن في طريقنا لمتابعة نفس الخوارزمية. ذلك الذي يذهب في الظهر أولا؟ حتى 3 ثم 7. والآن يذهب هيئة التصنيع العسكري لهؤلاء الرجال، موافق؟ 

SPEAKER 3: لذلك أنا النصف الأيمن من غادر نصف، وبلدي n هو أقل من 1، لذلك أنا ذاهب لمجرد تمرير - 

DAVID مالان: جيد. 

سرور 4: أنا النصف الأيمن من النصف الأيمن من النصف الأيمن، وأنا أيضا شخص واحد، لذلك أنا الذهاب الى العودة. حتى الآن نحن دمجها. 

SPEAKER 3: حتى نعود. 

DAVID مالان: حتى تذهب إلى الخلف. حتى 5 يذهب أولا، ثم 8. والآن الجمهور، الذي هو خطوة علينا أن الترجيع الآن العودة إلى في عقولنا؟ 

الجمهور: دمج. 

DAVID مالان: دمج النصف الأيسر والأيمن نصف النصف الأيسر الأصلي. وحتى الآن - وفقط لجعل هذا واضحا، جعل قليلا من الفضاء بينك اثنين من اللاعبين. وحتى الآن هذا القائمتين، اليسار واليمين. لذلك كيف يمكننا الآن دمج يا رفاق في الصف الأمامي من المقاعد مرة أخرى؟ 

3 يذهب أولا. ثم 5، ومن الواضح. ثم 7، والآن 8. حسنا، والآن نحن؟ 

الحضور: ليس القيام به. 

DAVID مالان: غير ذلك، وذلك لأن من الواضح، هناك خطوة واحدة المتبقية. ولكن مرة أخرى، والسبب أنا باستخدام هذا المصطلحات مثل "الترجيع في عقلك،" انها لأن هذا هو حقا ما يحدث. ونحن في طريقنا من خلال كل هذه الخطوات، ولكننا نوع من التوقف ل لحظة، والغوص أعمق في الخوارزمية، والتوقف للحظة واحدة، الغوص أعمق في الخوارزمية، و الآن لدينا لترجيع نوع من خلال موقعنا العقول والتراجع عن كل من هذه الطبقات بعد أن قمنا نوع من تأجيلها. 

حتى الآن لدينا قائمتين من حجم 4. إذا يا رفاق يمكن الوقوف مرة الأخيرة وجعل قليلا من مساحة هنا ل نوضح أن هذا هو اليسار نصف الأصلي، و النصف الأيمن من الأصلي. من هو الرقم الأول أننا تحتاج إلى سحب في الظهر؟ ميشيل، بطبيعة الحال. 

لذلك وضعنا ميشيل هنا. والذي لديه عدد 2؟ عدد 2 يأتي على ظهره أيضا. عدد 3؟ ممتازة. عدد 4، رقم 5، رقم 6، عدد 7، وعدد 8. 

موافق، لذلك شعرت الكثير من الخطوات، لعلى يقين. ولكن الآن دعونا نرى إذا كنا لا يمكن تأكيد نوع من حدسي أن هذه الخوارزمية بشكل أساسي، لا سيما ن يحصل كبيرة حقا، كما رأينا مع الرسوم المتحركة، هو جوهريا أسرع. لذلك أزعم هذه الخوارزمية، في أسوأ القضية وحتى في أفضل الأحوال، ويا كبير من المرات ن ن تسجيل. وهذا هو، وهناك بعض جوانب هذا الخوارزمية التي تأخذ ن الخطوات، ولكن هناك جانب آخر في مكان ما أن التكرار، أن حلقات، أن يأخذ السجل ن الخطوات. يمكن أن نضع الإصبع على ما لدينا تلك ورقمين في اشارة الى؟ كذلك، حيث - من أين هيئة التصنيع العسكري تذهب؟ 

سرور 1: هل سجل ن يكون كسر لنا الى قسمين - تقسيم من قبل اثنين، أساسا. 

DAVID مالان: بالضبط. أي وقت نراه في أي خوارزمية بالتالي الآن، كان هناك هذا النمط من تقسيم، تقسيم، تقسيم. وانها خفضت عادة لشيء أن يكون لوغاريتمي، تسجيل قاعدة 2. ولكن يمكن أن يكون حقا أي شيء، ولكن تسجيل قاعدة 2. 

الآن ماذا عن ن؟ أستطيع أن أرى أننا نوع من تقسيم لك الرجال - تقسيم لك، وتنقسم لك، قسمت لك، وتنقسم لك. حيث لا نهاية تأتي من؟ 

لذلك فمن دمج. لأن التفكير في الامر. عند دمج ثمانية أشخاص معا، حيث نصفهم من مجموعة من أربعة والنصف الآخر هي آخر مجموعة من أربعة، كيف يمكنك أن تذهب عن القيام دمج؟ حسنا، فعلت ذلك يا رفاق إلى حد ما بشكل حدسي. 

ولكن إذا كنت فعلت هذا بدلا أكثر من ذلك بقليل منهجي، وأنا قد أشار في في أقصى اليسار أول شخص مع يساري ناحية، وأشار في أقصى اليسار شخص من أن نصف مع يدي اليمنى، و فقط مشى في وقت لاحق من خلال القائمة، مشيرا في الوقت ذاته أصغر عنصر في كل مرة، والانتقال إصبعي على و أكثر حسب الحاجة في جميع أنحاء القائمة. ولكن ما هو مفتاح عن هذا الدمج العملية هي أنا بمقارنة هذه الأزواج من العناصر. من النصف الأيمن من الجهة اليسرى و نصف، وأنا أبدا التراجع مرة واحدة. 

وبالتالي فإن دمج نفسها مع الأخذ لا يزيد عن ن الخطوات. وعدد المرات لم لدي للقيام بذلك الدمج؟ كذلك، أي أكثر من ن، ونحن فقط ورأى أنه مع دمج النهائي. وحتى إذا كنت تفعل شيئا أن يأخذ تسجيل ن الخطوات n مرة، أو العكس، انها سوف تعطينا n مرة تسجيل ن. 

ولماذا هذا أفضل؟ حسنا، إذا كنا نعرف بالفعل أن سجل n هو أفضل من ن - أليس كذلك؟ رأينا في البحث الثنائي، دليل الهاتف سبيل المثال، كان سجل ن بالتأكيد أفضل من الخطية. وهذا يعني ن مرات تسجيل الدخول n هو بالتأكيد أفضل من مرات ن آخر ن، ن AKA المربعة. وهذا ما نشعر به في نهاية المطاف. 

جولة كبيرة جدا من التصفيق، إذا نستطيع، لهؤلاء الرجال. 

[تصفيق] 

DAVID مالان: والهدايا الخاصة بك فراق - كنت قد تبقي الأرقام، إذا كنت ترغب. وهدية فراق الخاص، كما جرت العادة. أوه، وسوف نرسل لك لقطات، ميشيل. شكرا لك. حسنا. تساعد نفسك في الكرة الإجهاد. 

واسمحوا لي أن سحب ما يصل، في هذه الأثناء، صديقنا روب بودين لتقديم وجهة نظر مختلفة نوعا ما في هذا الشأن، حيث يمكنك التفكير في هذه الخطوات يحدث في بعض الشيء بطريقة مختلفة. في الواقع، فإن مجموعة المتابعة لماذا عن روب لتبين لنا يفترض أن قمنا فعلت ما يصل الفاصل لل قائمة كبيرة إلى ثماني قوائم صغيرة، كل من حجم 1. 

لذلك نحن تغيير شبة الكود ل قليلا فقط لنوع من الحصول على الفكرة الأساسية لكيفية عمل دمج. ولكن وقت تشغيل ما انه على وشك القيام به هو لا يزال سوف تكون هي نفسها. ومرة أخرى، فإن مجموعة المتابعة هنا هو أنه بدأت مع ثماني قوائم حجم 1. لذلك كنت قد غاب عن الجزء حيث انه فعلت فعلا سجل ن، ن تسجيل، تسجيل ن الفاصل من المدخلات. 

[تشغيل الفيديو] 

لذالك لخطوة واحدة. لخطوتين، مرارا وتكرارا دمج أزواج من القوائم. 

DAVID مالان: صاحبة الجلالة. فقط الصوت قادم من جهاز الكمبيوتر الخاص بي. دعونا نحاول هذا مرة أخرى. 

، فقط اختيار تعسفي التي - الآن لدينا أربع قوائم. تعلم قبل. 

DAVID مالان: هناك نذهب. 

دمج-108 و 15، ونحن في نهاية مع لائحة 15، 108. دمج 50 و 4، ونحن في نهاية المطاف مع 4، 50. دمج 8 و 42، ونحن في نهاية المطاف مع 8، 42. ودمج 23 و 16، ونحن في نهاية المطاف مع 16 و 23. 

الآن جميع القوائم لدينا هي من حجم 2. لاحظ أن كل من يتم فرز أربع قوائم. حتى نتمكن من البدء في دمج أزواج من القوائم مرة أخرى. دمج 15 و 108 و 4 و 50، ونحن أولا نلقي ال 4، ثم 15، ثم 50، ثم 108. دمج 8 و 42 و 16 و 23، ونحن نأخذ الأولى 8، ثم 16، ثم 23، ثم 42. 

حتى الآن لدينا اثنين فقط من حجم القوائم 4، كل منها تم فرزها. حتى الآن نحن دمج هاتين القائمتين. الأولى، ونحن نأخذ ال 4، ثم أخذنا 8، ثم نأخذ 15، ثم 16، ثم 23، ثم 42، ثم 50، ثم 108. 

[END تشغيل الفيديو] 

DAVID مالان: مرة أخرى، لاحظ، لم يسبق له تطرق كوب تعطى أكثر من مرة واحدة بعد التقدم أبعد من ذلك. حتى انه لم التكرار. لذلك فهو يتحرك دائما إلى الجانب، وحيث ان وصلنا لدينا ن. 

لماذا لا يسمح لي سحب ما يصل للرسوم المتحركة واحد التي رأيناها في وقت سابق، ولكن هذه المرة التركيز فقط على دمج النوع. اسمحوا لي المضي قدما والتكبير في على هذا هنا. أولا اسمحوا لي أن اختيار المدخلات العشوائية، تضخيم هذا، ويمكنك معرفة نوع من ما اتخذنا من المسلمات، في وقت سابق، دمج النوع يقوم به فعلا. 

لذلك تلاحظ أن تحصل هذه نصفين أو هذه أرباع أو أثمان هذه ل المشكلة التي مفاجئة للجميع تبدأ في التبلور جيدة. ثم أخيرا، ترى في نهاية جدا أن بام، يتم دمج كل شيء معا. 

لذلك فان هذه هي مختلفة ثلاثة فقط يأخذ على نفس الفكرة. ولكن الفكرة الرئيسية، تماما مثل الفجوة وقهر في الدرجة الأولى، كان ذلك قررنا تقسيم بطريقة أو بأخرى المشكلة في شيء كبير، في شيء نوع من متطابقة في الروح، ولكن أصغر وأصغر وأصغر وأصغر. 

الآن وسيلة أخرى متعة لنوع من التفكير حول هذه، على الرغم من انها ليست سوف تعطيك نفس بديهية فهم، هو الحركة التالية. لذلك هذا هو شخص وضع الفيديو معا أن يرتبط مختلفة يبدو مع عمليات مختلفة ل نوع الإدراج، لدمج النوع، و لاثنين آخرين. حتى في لحظة، وانا ذاهب لضرب اللعب. انها حوالي دقيقة واحدة طويلة. وعلى الرغم من لا يزال بإمكانك رؤية أنماط يحدث، وهذه المرة يمكنك أيضا نسمع كيف هي هذه الخوارزميات أداء مختلف ومع أنماط مختلفة إلى حد ما. 

هذا هو الإدراج الفرز. 

[TONES PLAYING] 

DAVID مالان: إنه يحاول مرة أخرى لإدراج كل عنصر إلى حيث تنتمي. هذا هو نوع فقاعة. 

[TONES PLAYING] 

DAVID مالان: ويمكنك أن تشعر نوع من كيفية عمل القليل نسبيا تقوم به على كل خطوة. هذا هو ما يبدو الإضجار مثل. 

[TONES PLAYING] 

DAVID مالان: هذا هو اختيار نوع، حيث نقوم باختيار عنصر نريد من خلال يمر مرة أخرى ومرة ​​أخرى ومرة ​​أخرى ووضعه في البداية. 

[TONES PLAYING] 

DAVID مالان: هذا هو دمج النوع الذي يمكنك البدء ليشعر حقا. 

[TONES PLAYING] 

[ضحك] 

DAVID مالان: شيء يسمى جنوم نوع، وهو ما لم ينظر في. 

[TONES PLAYING] 

DAVID مالان: لذا اسمحوا لي أن نرى، الآن، يصرف كما كنت أمل من قبل الموسيقى، إذا أنا يمكن أن تنزلق قليلا قليلا من الرياضيات هنا. حتى لا يكون هناك وسيلة الرابع ما في وسعنا نفكر في ما يعنيه هذه وظائف لتكون أسرع من تلك التي شهدناها من قبل. وإذا كنت قادما في الدورة من خلفية الرياضيات، كنت نعرف في الواقع ربما بالفعل التي يمكن صفعة مصطلح على هذه التقنية - وهي العودية، وهي وظيفة التي تطلق على نفسها بطريقة أو بأخرى. 

ومرة أخرى، أذكر أن دمج النوع كان شبة الكود العودية بمعنى أن واحدة من الخطوات دمج النوع في وكان لاستدعاء نوع - وهذا هو، في حد ذاته. ولكن لحسن الحظ، لأننا أبقى داعيا نوع، أو دمج النوع، على وجه التحديد، على أصغر وأصغر وقائمة أصغر، ونحن في نهاية المطاف ينتعش بفضل ما سنتصل قضية القاعدة، حالة الثابت تلوينها أن وقال إذا كانت قائمة صغيرة، أقل من 2 في هذه الحالة، والعودة فقط على الفور. إذا لم يكن لدينا هذه الحالة الخاصة، و سوف خوارزمية أبدا القاع، وسوف تحصل في الواقع إلى حلقة لا نهائية إلى الأبد حقا. 

ولكن لنفترض أننا نريد أن يضع الآن بعض الأرقام في هذا، مرة أخرى، وذلك باستخدام ن ويبلغ حجم المدخلات. وأنا أريد أن أطلب منكم، ما هو إجمالي الوقت تشارك في تشغيلها دمج النوع؟ أو بشكل أعم، ما هو تكلفة منه في الوقت المناسب؟ 

كذلك فإنه من السهل جدا لقياس ذلك. إذا كان n أقل من 2، والوقت الذي يتطلبه في فرز العناصر ن، حيث n هو 2، 0. لأن نعود فقط. ليس هناك عمل ينبغي القيام به. الآن يمكن القول، وربما انها خطوة واحدة أو اثنتين خطوات لمعرفة كمية العمل، لكنها قريبة بما فيه الكفاية ل0 أن أنا فقط أريد أن أقول أي عمل هو مطلوب إذا كانت قائمة صغيرة جدا أن يكون رتيبا. 

ولكن هذه الحالة هي مثيرة للاهتمام. كان الحال العودية فرع في شبة الكود الذي قال آخر، نوع النصف الأيسر، فرز الحق نصف، ودمج شطري. الآن لماذا يفعل هذا التعبير تمثل تلك النفقات؟ كذلك، تي ن يعني مجرد الوقت لفرز العناصر ن. ثم على الجانب الأيمن من علامة التساوي هناك، تي ن تقسيم بنسبة 2 يشير إلى تكلفة ماذا؟ فرز النصف الأيسر. تي غيرها ن مقسوما على 2 هو مشيرا يفترض أن تكلفة ل فرز نصف الحق. 

ثم زائد ن؟ هو الدمج. لأنه إذا كان لديك قائمتين، واحدة من ن حجم أكثر من 2 وآخر من حجم ن أكثر من 2، لديك أساسا للمس كل من تلك العناصر، تماما مثل روب وتطرق كل من الكؤوس، وعادل كما أشرنا في كل من المتطوعين على خشبة المسرح. لذلك n هو حساب دمج. 

الآن للأسف، هذه الصيغة هو أيضا نفسه العودية. لذلك إذا طرح السؤال، إذا n هو، كما يقول، 16، إذا كان هناك 16 شخصا على خشبة المسرح أو 16 أكواب في شريط الفيديو، كم من مجموع الخطوات التي يستغرقها فرزها مع دمج النوع؟ انها في الواقع ليست جوابا واضحا، لأنه الآن لديك لفرز من الإجابة بشكل متكرر هذه الصيغة. 

ولكن هذا موافق، لأن اسمحوا لي أن أقترح ما نقوم به ما يلي. الوقت الذي يتطلبه لفرز 16 شخصا أو 16 أكواب ستكون ممثلة عموما كما T 16. ولكن الذي يساوي، وفقا لدينا الصيغة السابقة، 2 أضعاف المبلغ الوقت الذي يستغرقه لفرز 8 أكواب زائد 16. ومرة أخرى، بالإضافة إلى 16 هو الوقت المناسب لدمج، ومرتين T من 8 هو الوقت لفرز النصف الأيسر والنصف الأيمن. 

ولكن مرة أخرى، هذا لا يكفي. علينا أن الغوص في أعمق. هذا يعني ان لدينا للرد على السؤال، ما هو T من 8؟ كذلك T من 8 هو مجرد 2 T من 4 مرات بالإضافة إلى 8. حسنا، ما هو T من 4؟ T من 4 مرات فقط 2 من 2 T زائد 4. حسنا، ما هو T من 2؟ T من 2 هو مجرد 2 مرات T من 1 زائد 2. 

ومرة أخرى، نحن نوع من الحصول على عالقا في هذه الدورة. ولكن هذا على وشك أن تصل ما يسمى الحالة الأساسية. لأن ما هو من T 1، لم ندعي؟ 0. وحتى الآن أخيرا، يمكننا العمل الوراء. 

إذا T من 1 0، يمكنني أن أذهب الآن نسخة احتياطية واحدة خط لهذا الرجل هنا، ويمكنني سد العجز في لT 0 1. وهذا يعني أنه يساوي 2 مرات الصفر، والمعروف باسم 0، بالإضافة إلى 2. وبحيث التعبير كله 2. 

الآن إذا كنت تأخذ من T 2، الذي الجواب و2، بتوصيله خط الوسط، T من 4، وهذا يعطيني 2 مرات 2 زائد 4، لذلك 8. إذا كنت ثم سد العجز في 8 إلى السابق خط، وهذا يعطيني 2 مرة 8، 16. وإذا كنا ثم تابع أنه مع 24، مضيفا في 16، ونصل أخيرا قيمة 64. 

الآن أنه في حد ذاته نوع من يتحدث لا شيء لتدوين ن، و O كبيرة، أوميغا التي قمنا تم الحديث عنه. ولكن اتضح أن 64 هو في الواقع 16، وحجم المدخلات، تسجيل قاعدة 2 من 16. وإذا كان هذا هو غير مألوف قليلا، فقط التفكير مرة أخرى، وأنه سوف يعود لك في نهاية المطاف. إذا كان هذا هو الأساس سجل 2، انها مثل 2 مرفوعة إلى ما يمنحك 16؟ أوه، هذا هو 4، لذلك فمن 16 مرة 4. 

ومرة أخرى، انها ليست صفقة كبيرة إذا كان هذا هو نوع من ذاكرة ضبابية الآن. لكنه الآن، تأخذ على الإيمان أن 16 سجل 16 هو 64. وهكذا في الواقع، مع هذا العقل البسيط تحقق، لقد أكد - ولكن لم يثبت رسميا - أن وقت تشغيل الدمج هو في الواقع نوع ن ن تسجيل. 

لذلك ليس سيئا. انها بالتأكيد أفضل من خوارزميات رأيناه حتى الآن، و انها لاننا الاستدانة، واحد، تقنية تسمى العودية. ولكن أكثر إثارة للاهتمام من ذلك، أن فكرة تقسيم وقهر. مرة أخرى، في الأسبوع حقا 0 الاشياء التي حتى الآن المتكررة في طريقة أكثر إقناعا. 

الآن ممارسة القليل متعة، وإذا كنت قد لم تفعل هذا - وربما كنت لن يكون، لأن نوع من العادي الناس لا يفكرون في القيام بذلك. ولكن إذا ذهبت إلى google.com وإذا أريد أن أتعلم شيئا عن العودية، أدخل. 

[ضحك] [المزيد ضحك] DAVID مالان: سيئ نكتة تنتشر ببطء. [ضحك] DAVID مالان: عادل في القضية، انها هناك. لم أكن توضيح ذلك الخطأ، وهناك نكتة. حسنا. تفسير ذلك للشعب إلى جانبك إذا أنها لم النقر جدا فقط حتى الآن. ولكن العودية، وبصورة أعم، يشير لعملية من استدعاء وظيفة في حد ذاته، أو أكثر عموما، تقسيم المشكلة في شيء يمكن أن يكون حل تدريجي من خلال حل متطابقة مشاكل ممثل. 

حسنا، دعونا تغيير التروس لمجرد لحظة. نود أن تنتهي في بعض cliffhangers، لذلك دعونا نبدأ لتعيين المسرح، لعدة دقائق، على فكرة بسيطة جدا - أن مبادلة عنصرين، أليس كذلك؟ كل من هذه الخوارزميات كنا الحديث عن القليلة الماضية تنطوي بعض المحاضرات نوع من مقايضة. اليوم وقد تصور من قبل لهم الحصول على للخروج من كراسيهم و يتجول، ولكن في التعليمات البرمجية، كنا تأخذ فقط عنصر من مجموعة واحدة وصوت نزول المطر عليه في آخر. 

لذلك كيف نذهب عن القيام بذلك؟ حسنا، اسمحوا لي أن المضي قدما في الكتابة برنامج سريع هنا. انا ذاهب الى المضي قدما والقيام هذا على النحو التالي. دعونا نسمي هذا - ماذا نريد لهذه الكلمة واحدة؟ 

في الواقع، لا. اسمحوا لي الترجيع. أنا لا أريد أن نفعل ذلك التشويق حتى الآن. وسوف أفسد متعة. دعونا نفعل ذلك بدلا من ذلك. 

لنفترض أنني أريد أن أكتب قليلا البرنامج والتي تحتضن الآن هذا فكرة العودية. النوع الأول من حصلت قبل نفسي هناك. انا ذاهب الى القيام بما يلي. 

الأولى، وتشمل سريعة من io.h القياسية، وكذلك التضمين من cs50.h. ثم انا ذاهب الى المضي قدما وتعلن باطلة الرئيسي الباحث بالطريقة المعتادة. أدركت أنني كنت ذات التسمية المضللة الملف، لذلك اسمحوا لي أن أضيف ملحق ج هنا حتى نتمكن من ترجمة عليه بشكل صحيح. تبدأ هذه المهمة قبالة. 

وظيفة أريد أن أكتب، تماما ببساطة، هو الذي يسأل المستخدم لعدد ثم يضيف جميع الأرقام بين أن عدد و، ويقول، 0. لذلك أول وأنا ذاهب إلى المضي قدما وتعلن ن الباحث. ثم أقوم بنسخ بعض التعليمات البرمجية التي استخدمنا لفترة من الوقت. بينما هناك شيئا صحيحا. سأعود إلى ذلك في لحظة. 

ماذا أريد أن أفعل؟ أريد أن أقول printf إيجابية عدد صحيح من فضلك. ثم أنا ذاهب ل يقول ن يحصل على الحصول على كثافة العمليات. ذلك مرة أخرى، بعض رمز المتداول أننا قد استخدمت من قبل. وانا ذاهب للقيام بذلك بينما n هو أقل من 1. ولذلك فإن هذا سوف تأكد من أن المستخدم يعطيني عددا صحيحا موجبا. 

والآن انا ذاهب الى القيام بما يلي. أريد أن تضيف ما يصل كل الأرقام بين 1 و n و، أو 0 و ن، مكافئ، للحصول على المبلغ الإجمالي. وبالتالي فإن رمز سيغما كبيرة التي قد تذكر. لذلك أنا ذاهب الى القيام بذلك عن طريق الدعوة الأولى وظيفة تسمى سيغما، فمررها في ن، ثم انا ذاهب الى يقول printf، فإن الجواب هو الحق هناك. 

لذلك باختصار، وأحصل على و الباحث من المستخدم. أنا ضمان انها ايجابية. أعلن متغير يسمى إجابة ل نوع int وتخزين في ذلك عودة قيمة سيغما، ويمر في ن كإدخال. وبعد ذلك طباعة هذا الجواب. 

للأسف، على الرغم من الأصوات سيغما وكأنه شيء قد يكون في ملف math.h، إعلانها، انها في الواقع لا. بحيث لا بأس. يمكنني تنفيذ هذا بنفسي. أنا ذاهب لتنفيذ وظيفة تسمى سيغما، وانها سوف تأخذ المعلمة - دعونا نسميها م فقط، فقط لذلك فمن مختلفة. ثم هنا، انا ذاهب الى القول، حسنا، إذا م هو أقل من 1 - هذا هو برنامج رتيبا جدا. لذلك انا ذاهب الى المضي قدما و 0 العودة فورا. انها فقط لا معنى لتضيف ما يصل جميع الأرقام بين 1 و م إذا م هو في حد ذاته 0 أو سلبية. 

ثم انا ذاهب الى المضي قدما والقيام بذلك تكراري جدا. انا ذاهب للقيام بذلك النوع من المدرسة القديمة، وانا ذاهب الى المضي قدما وأقول إنني ذاهب ل تعلن مبلغ أن يكون 0. ثم أنا ذاهب لديك لحلقة من كثافة العمليات - واسمحوا لي أن تفعل ذلك لمطابقة دينا كود التوزيع، بحيث يكون لديك نسخة في المنزل. كثافة العمليات ط 1 يحصل على ما يصل إلى ط أقل من أو يساوي متر. ط زائد زائد. ثم داخل هذه لحلقة - نحن تقريبا هناك - المبلغ يحصل مبلغ زائد 1. ثم أنا ذاهب لإرجاع المبلغ. 

هكذا فعلت ذلك بسرعة، من المسلم به تماما. ولكن مرة أخرى، والوظيفة الرئيسية جميلة واضحة، تقوم على قواعد لدينا مكتوبة حتى الآن. يستخدم حلقة المزدوج للحصول على الإيجابية الباحث من المستخدم. وبعد ذلك تمرير هذا الباحث إلى وظيفة جديدة دعا سيغما، واصفا ذلك، مرة أخرى، ن. وأنا تخزين قيمة الإرجاع، والجواب من الصندوق الاسود حاليا المعروفة باسم سيغما، في متغير دعا الجواب. ثم أنا طباعته. 

إذا كنا الآن لا تزال هذه القصة، كيف يتم تطبيق سيجما؟ أقترح لتنفيذ على النحو التالي. أولا، قليلا من تدقيق الأخطاء للتأكد من أن المستخدم ليس العبث معي ويمر في بعض سلبية أو القيمة 0. ثم أعلن متغير يسمى المبلغ وتعيينها إلى 0. 

وأنا الآن تبدأ في التحرك من التساوي ط 1 كل وسيلة وبما يصل إلى متر، لأنني أريد أن تشمل جميع الأرقام من واحد من خلال م، ضمنا. وداخل هذا للحلقة، وأنا مجرد القيام مبلغ يحصل ما هو عليه الآن، بالإضافة إلى قيمة ط. بالإضافة إلى قيمة ط. 

بوصفها جانبا، وإذا كنت لم أر هذا من قبل، هناك بعض السكر النحوية لهذا الخط. أستطيع كتابة هذا النحو زائد يساوي ط، فقط لانقاذ نفسي بضع ضربات المفاتيح وتبدو برودة قليلا. ولكن هذا كل شيء. انها وظيفيا نفس الشيء. 

للأسف، هذا الرمز هو لن تجميع حتى الآن. إذا قمت بتشغيل جعل سيغما 0، كيف أنا أنا ذاهب للحصول على صرخ في و؟ ما تسير الأمور ليست مثل؟ 

الحضور: [غير مسموع]. 

DAVID مالان: نعم، لم أكن تعلن وظيفة حتى أعلى، أليس كذلك؟ C هو نوع من الغباء، لأنه فقط لا ما كنت أقول أن تفعله، وأنت يجب أن نفعل ذلك في هذا النظام. وحتى لو كنت هاهنا هنا، وانا ذاهب ل الحصول على تحذير حول سيغما الضمني الإعلان. 

أوه، لا مشكلة. أستطيع أن ترتفع إلى الأعلى، ويمكنني ويقول، كل الحق، والانتظار لمدة دقيقة. سيغما هو دالة تقوم بإرجاع عدد صحيح وانها تتوقع ل الباحث كمدخل، منقوطة. أو يمكن أن أضع وظيفة كاملة الرئيسية أعلاه، ولكن بصفة عامة، فما استقاموا لكم فاستقيموا يوصي ضد ذلك، لأنه من الجميل أن يكون دائما الرئيسي في أعلى ذلك يمكنك الغوص في الحق وتعرف ما هو البرنامج به من خلال قراءة أول الرئيسي. 

وحتى الآن اسمحوا لي أن مسح الشاشة. إعادة تشكيل سيغما 0. يبدو أن جميع إجراءات المغادرة. اسمحوا لي أن تشغيل سيغما 0. أمور إيجابية. سوف تقدم له عدد 3 أن يبقيه بسيط. بحيث ينبغي أن تعطيني 3 زائد 2 زائد 1، لذلك 6. تدخل، وبالفعل أحصل 6. 

أستطيع أن أفعل شيئا أكبر - 50، 12، 75. تماما كما الظل، وانا ذاهب للقيام شيء مثير للسخرية وكأنه كبيرة حقا العدد، أوه، التي عملت فعلا - إيه، وأنا لا أعتقد أن هذا صحيح. دعونا نرى. دعونا حقا فوضى معها. 

وهذا هو المشكلة. ما الذي يحدث؟ رمز ليست بهذا السوء. انها لا تزال الخطية. صفير هو تأثير جيد، على الرغم من. ما الذي يحدث؟ 

ليس متأكدا مما اذا سمعت ذلك. حتى اتضح - و هذا هو باعتباره جانبا. هذا ليس الأساسية ل فكرة العودية. كما تبين، لأنني أحاول أن تمثل هذا العدد الكبير، ومعظم من المرجح يجري يساء تفسيرها بواسطة C كرقم يست إيجابية، ولكن رقم سالب. 

نحن لم تحدثنا عن هذا، ولكنه تبين وجود أعداد السلبية في العالم بالإضافة إلى أرقام إيجابية. والوسائل التي يمكنك تمثل رقما سالبا أساسا غير، يمكنك استخدام واحد بت خاصة للإشارة إلى الإيجابية على السلبية. انها قليلا أكثر تعقيدا من ذلك، ولكن هذه هي الفكرة الأساسية. 

ذلك لسوء الحظ، إذا C هو واحد مربك من هذه البتات يعني كما في الواقع، أوه، هذا هو رقم سلبي، حلقة بلدي هنا، على سبيل المثال، هو في الواقع أبدا ذاهب لإنهاء. حتى لو كنت تطبع في الواقع شيئا مرارا وتكرارا، كنا نرى الكثير كله. ولكن مرة أخرى، وهذا هو جانب هذه النقطة. هذا هو في الحقيقة مجرد نوع من الفضول الفكري أننا سوف يأتي إلى نهاية المطاف. لكنه الآن، وهذا هو الصحيح تنفيذ إذا افترضنا أن وسوف توفر للمستخدم رجات التي تدخل ضمن رجات. 

ولكن أزعم أن هذا الرمز، بصراحة، يمكن القيام به أكثر من ذلك بكثير ببساطة. إذا كان الهدف في متناول اليد هو اتخاذ عدد مثل م وتضيف ما يصل كل من أرقام بينه و 1، أو العكس بين 1 و عليه، أزعم أستطيع أن تقترض هذا فكرة أن دمج كان نوعا، والتي تتخذ مشكلة من هذا الحجم وتقسيمه إلى شيء أصغر. ربما ليس النصف، ولكنها أصغر حجما، ولكن تمثيلي نفسه. نفس الفكرة، ولكن مشكلة صغيرة. 

لذلك أنا في الواقع - اسمحوا لي حفظ هذا الملف مع رقم إصدار مختلف. وسوف ندعو هذا الإصدار 1 بدلا من 0. وأزعم أنني يمكن في الواقع reimplement هذا في هذا النوع من طريقة الانحناء العقل. 

أنا ذاهب إلى ترك جزء منه وحده. انا ذاهب الى القول إذا م هو أقل من أو حتى يساوي 0 - أنا ذاهب لمجرد أن يكون قليلا مزيد من الشرج وهذه المرة مع التحقق من الخطأ بلدي - انا ذاهب الى المضي قدما والعودة 0. هذا هو إجراء تعسفي. أنا ببساطة تحديد ما إذا كان المستخدم يعطيني رقم سالب، وأنا العودة 0، وكان ينبغي أن تقرأ وثائق عن كثب. 

آخر - لاحظ ما أنا ذاهب الى القيام به. آخر وانا ذاهب الى العودة متر زائد - ما هو سيغما من م؟ حسنا، سيجما للمتر زائد ناقص 1 م، بالإضافة إلى 3 م ناقص 2، بالإضافة إلى م ناقص. أنا لا أريد أن أكتب كل ذلك الخروج. لماذا لا أنا فقط البونت؟ أسمي نفسي متكرر مع قليلا المشكلة أصغر، الفاصلة المنقوطة، ويطلق عليه اليوم؟ 

أليس كذلك؟ الآن هنا، أيضا، قد تشعر أو تقلق أن هذا هو حلقة لا نهائية أنني حمل، حيث إنني تنفيذ سيغما بالدعوة سيغما. ولكن هذا موافق تماما، لأنني التفكير في المستقبل والتي خطوط المضافة؟ 

الحضور: [غير مسموع]. 

DAVID مالان: 23 إلى 26، والتي هي لغتي إذا كان الشرط. لأن ما هو لطيف حول الطرح هنا، لأن أظل تسليم سيغما مشاكل أصغر، أصغر مشاكل، أصغر - انها ليست نصف حجم. انها فقط خطوة الطفل أصغر، ولكن هذا موافق. لأن في نهاية المطاف، وسوف نعمل طريقنا إلى 1 أو 0. وبمجرد ان تصل 0، سيغما ليست سوف تسمي نفسها بعد الآن. انها تسير على العودة فورا 0. 

وبالتالي فإن تأثير، إذا كنت نوع من الرياح هذا حتى في عقلك، هي إضافة م زائد م ناقص 1، بالإضافة إلى ناقص 2 م، بالإضافة إلى م ناقص 3، بالإضافة إلى نقطة، نقطة، نقطة، م ناقص م، وإعطاء في نهاية المطاف لك 0، و أثر هو في نهاية المطاف إلى إضافة كافة هذه الأشياء معا. لذلك ليس لدينا، مع العودية، حل المشكلة أننا لا يمكن أن تحل من قبل. في الواقع، نسخة 0 من هذا، وعلى كل المشكلة حتى الآن، كانت قابلة للحل مع مجرد استخدام للحلقات أو أثناء الحلقات أو بنيات مماثلة. 

ولكن العودية، ونحسب، يعطينا طريقة مختلفة في التفكير مشاكل، حيث ما اذا كنا نستطيع اتخاذ المشكلة، نقسمه من شيء كبيرة نوعا ما إلى شيء إلى حد ما أصغر، أزعم أننا يمكن أن تحل على أكثر ربما قليلا من حيث بأناقة من التصميم، مع أقل الرمز، وربما حتى حل المشاكل التي من شأنها أن يكون من الصعب، كما سنقوم في نهاية المطاف ترى، حل تكراري بحتة. 

ولكن التشويق التي فعلت تريد أن تترك لنا على هذا كان. اسمحوا لي المضي قدما وفتح حتى ملف من - في الواقع، اسمحوا لي ان اذهب و القيام بذلك بسرعة حقيقية. اسمحوا لي المضي قدما واقتراح ما يلي. بين كود اليوم هو هذا الملف هنا. هذا واحد هنا، noswap. 

لذلك هذا هو برنامج غبي القليل الذي أنا جلد حتى التي تدعي القيام به ما يلي. في الرئيسي، فإنها تعلن أولا دعا الباحث العاشر ويسند قيمة 1. بعد ذلك يعلن الباحث ذ و يسند قيمة 2. بعد ذلك بطباعة ما x و y هو. ثم تقول، مبادلة، نقطة نقطة نقطة. 

ثم يدعي أن استدعاء دالة دعا المبادلة، ويمر في العاشر و ذ، فكرة وهي أن نأمل x و y سوف يعود مختلفة، والعكس. بعد ذلك يدعون تبادلت! مع علامة تعجب. بعد ذلك بطباعة x و y. 

ولكن تبين أن هذا جدا مظاهرة بسيطة أسفل هنا هو عربات التي تجرها الدواب في الواقع. على الرغم من أنني إعلان مؤقتة متغير ووضع مؤقتا في ذلك، ثم أنا إعادة تعيين وقيمة ب - الذي يشعر معقولة، لأن لدي حفظ نسخة من في درجة الحرارة. ثم أقوم بتحديث ب على قدم المساواة كل ما كان في درجة الحرارة. هذا النوع من لعبة قذيفة من تحريك إلى ب وب في باستخدام هذا يشعر رجل في منتصف تسمى درجة الحرارة معقول تماما. 

ولكن أزعم أنني عندما تشغيل هذا رمز، كما سأفعل الآن - اسمحوا لي أن تمضي قدما والصقه هنا. سأتصل هذا noswap.c. وكما يوحي اسمها، وهذا ليس سيكون البرنامج الصحيح. جعل noswap. / لا المبادلة. x هو 1، ص 2، مبادلة، تبادلت. x هو 1، ص 2. هذا هو خطأ جوهري، حتى رغم أن هذا يبدو تماما معقول بالنسبة لي. وهناك سبب، ولكن نحن لسنا سوف تكشف عن السبب فقط حتى الآن. 

الآن والتشويق الثانية أردت أن أترككم مع هذا، و إعلان من نوع ما على رموز القسيمة. لدينا الابتكار مع الأيام أواخر هذا العام أثارت عددا غير تافهة من الأسئلة، والتي كان وليس لدينا النية. نية هذه رموز القسيمة، حيث إذا قمت بذلك جزءا من المشكلة تعيين في وقت مبكر، وبالتالي الحصول على يوم إضافي، كان حقا للمساعدة يا رفاق مساعدة نفسك تبدأ في وقت مبكر، نوع من قبل تحفيز لك. يساعدنا على توزيع التحميل عبر ساعات العمل أفضل بحيث انها نوع من الفوز. 

للأسف، أعتقد تعليماتي لم تكن، حتى الآن، واضحة جدا، لذلك عدت في نهاية هذا الاسبوع وتحديثها المواصفات في أكبر وأكثر جرأة النص ل شرح الرصاص مثل هذه. ومجرد أن أقول ذلك علنا ​​أكثر، من خلال الافتراضي، ومجموعات مشكلة من المقرر الخميس عند الظهر، في المنهج. إذا كنت تبدأ في وقت مبكر، والانتهاء من جزء من مشكلة تعيين بحلول يوم الأربعاء في تمام الساعة 12:00 مساء، الجزء الذي يتصل قسيمة رمز، والفكرة هي أنك يمكن أن تمتد آخر موعد للحصول على تعيين P حتى يوم الجمعة. وهذا هو، قضم جزء صغير من P تعيين نسبة إلى ما هو عادة مشكلة أكبر، وتشتري نفسك يوما إضافيا. مرة أخرى، فإنه يحصل لك التفكير مشكلة تعيين، ويحصل لك ساعات العمل عاجلا. ولكن المشكلة لا تزال رمز القسيمة المطلوبة، حتى لو كنت لا تضعها. 

ولكن أكثر مقنع هو هذا. (STAGE WHISPER) وهؤلاء الناس ترك وستعمل يندم عليه في وقت مبكر. وكذلك الناس على الشرفة. أعتذر مقدما الى الناس على الشرفة لأسباب من شأنها أن تكون مسح في مجرد لحظة. 

لذلك نحن محظوظون لأن لدينا واحدة من السابق زملاء التدريس في الرأس CS50 في شركة تدعى dropbox.com. تبرعوا بسخاء جدا لديهم رمز القسيمة هنا لهذه المساحة من ذلك بكثير، وهو ما يصل من 2 غيغابايت المعتادة. ذلك ما كنت أعتقد أننا سوف نفعل على هذا ملاحظة أخيرة هي تفعل شيئا من الهبات، حيث في مجرد لحظة، ونحن سوف تكشف الفائز والذي لديه القسيمة التعليمات البرمجية التي يمكنك ثم انتقل إلى هم الموقع، اكتب في ذلك، وفويلا، والحصول على أكثر بأسره الكثير قطاف الفضاء الخاصة بك الأجهزة والملفات الشخصية. 

والأولى، الذين يرغبون في المشاركة في هذا الرسم؟ حسنا، الآن أن يجعلها أكثر متعة. الشخص الذي يتلقى هذا 25 غيغابايت رمز القسيمة - والتي هي الآن أكثر إقناعا من أواخر أيام الآن، وربما - هو الذي يجلس على قمة التي تحت وسادة المقعد هناك أن رمز القسيمة. أنت الآن قد تبدو تحت وسادة المقعد الخاص بك. 

[تشغيل الفيديو] 

واحد، اثنان، ثلاثة. 

[صراخ] 

أنت تحصل على سيارة! تحصل على سيارة! 

DAVID مالان: سنرى كنت يوم الاربعاء. 

أنت تحصل على سيارة! تحصل على سيارة! تحصل على سيارة! تحصل على سيارة! تحصل على سيارة! 

DAVID مالان: الناس شرفة، وتأتي إلى هنا إلى الجبهة، حيث لدينا اشياء. 

-كل شخص يحصل على سيارة! الجميع يحصل على السيارة! 

[END تشغيل الفيديو] 

المعلق: في CS50 المقبل - 

سرور 5: يا إلهي يا إلهي يا إلهي يا إلهي إلهي إلهي إلهي إلهي إلهي إلهي - 

[[أوكلل] يلعب]