[عزف الموسيقى] DAVID J. مالان: حسنا. لذلك نرحب مرة. هذا هو CS50، وغير نهاية الاسبوع الثلاثة. أذكر ذلك في الأسابيع القليلة الماضية، لقد تم انفاق قدرا كبيرا من الوقت على C، على البرمجة، على بناء الجملة. وأنه من الطبيعي تماما، وإذا كنت لا تزال تكافح مع مشكلة تعيين 2، لتكون ضجيجا رأسك بالحائط. انها رسائل الخطأ خفي المظهر والأخطاء التي كنت لا يمكن مطاردة تماما أسفل. لأنه، تطمئن، وذلك في مجرد غضون أسابيع قليلة "سوف ننظر إلى الوراء على أشياء مثل قيصر، و[؟ V-genair،؟] ربما حتى الكراك، و ندرك تماما مدى كنت قد وصلنا في فترة قصيرة من الزمن. حتى اذا كان هذا أي عزاء، شنق في هناك في الوقت الراهن. اليوم، على الرغم من أن نبدأ في الانتقال إلى الأشياء مستوى أعلى. ونبدأ في اتخاذ أمرا مفروغا منه أن يا رفاق تعرف كيف تبرمج، أو على الأقل بدايات هذا المستوى من الراحة. وسنبدأ في النظر في كيفية ما في وسعنا التوجه نحو تصميم برامج أكثر على نحو فعال. كيف يمكننا التوجه نحو تحسين كفاءة الخوارزميات لدينا، و حل عموما أكثر مشاكل مثيرة للاهتمام. وبدأت أمرا مفروغا منه ذلك، إذا أردنا، ونحن يمكن أن يصل أي رمز من الأمثلة لدينا في الاعتبار. حتى اليوم، ونحن لا تلمس لوحة المفاتيح عن أي شكل من التعليمات البرمجية. أنه سوف يكون مستوى أعلى من ذلك بكثير، و في نهاية المطاف، عن حل المشاكل. لذلك للوصول الى تلك النقطة، اسمحوا لي أن أقترح أن السبعة التالية المستطيلات تمثل سبعة أبواب، وراء والتي هي في مجمله مجموعة من الأرقام، من بينها عدد 50. اسمحوا لي على هذا المشروع هذا الشاشة هنا كذلك. وأقترح أن نحتاج إلى متطوعين ل مساعدة تجد لي عددا أمام الانترنت هنا لنرى. تأتي على ما يصل، في ردي. حسنا. ما اسمك؟ جنيفر: [غير مسموع] DAVID J. مالان: عذرا؟ جنيفر: جنيفر. DAVID J. مالان: جنيفر. كل الحق، وجنيفر. تشرفت بمقابلتك. تأتي على ما يصل. لذلك فان هذه هنا هي سبعة أبواب، وماذا أود منك أن تفعل بالنسبة لنا هنا، أمام كل من زملائك، وتجد لنا العدد، 50. العثور على عدد، يمكنك ملاعبة وراء أي من هذه الأبواب ببساطة عن طريق التنصت على أحد الأبواب، و سوف تكشف عن رقمه. ودعونا نرى مدى السرعة التي أن تجد لنا العدد، 50. 15. 16. 50. عمله بشكل جيد. حسنا. جولة من التصفيق لجنيفر. [تصفيق] حسنا. وذلك ما كان لديك استراتيجية لل العثور على العدد، 50؟ جنيفر: أم، فكرت ربما لو - [غير مسموع] DAVID J. مالان: أوه. تعطيه ثانية واحدة. كان ذلك الاستراتيجية الخاصة بك ل العثور على العدد، 50؟ جنيفر: لذلك أنا مجرد بداية في بدأنا نرى ما الرقم الأول كان، ثم فكرت، ربما لو انهم فرزها، سوف تبقي فقط التنصت على مستوى اعلى؟ DAVID J. مالان: OK. ويبدو أننا قد وجدت أن يكون لهذه القضية. على الرغم من، دعونا قشر العودة طبقات قليلا فقط، وتريد أن تذهب قدما وتكشف عن الأبواب الأخرى كنت قد اختار؟ جنيفر: أوه، يا عزيزي. DAVID J. مالان: آه. جنيفر: لذلك أنا فقط حصلت على الحظ. DAVID J. مالان: إذن أنت محظوظة. حسنا. لذلك ليس سيئا. ولكن هذا مثيرة للاهتمام البصيرة، أليس كذلك؟ إذا توليتم، وأنت لم تحصل، في الواقع، قليلا محظوظا هناك. ولكن إذا كنت افترض أن الأرقام كانت فرزها، يمكنك أن تكون أكثر دقة عن كيفية التي أثرت سلوكك؟ جنيفر: حتى إذا كانوا فرزها، وأنا يعتقد ربما الأصغر إلى الأكبر. DAVID J. مالان: OK. جنيفر: أو إذا انتهى هذا الأمر كبيرة حقا، ثم الأكبر إلى الأصغر. DAVID J. مالان: OK. لذلك من الأكبر إلى الأصغر، أو من الأصغر إلى الأكبر. ولكن اسمحوا لي أن أقترح، افترض أنك زيارتها حصلت سيئ الحظ، ونفترض أنهم لم تكن، في الواقع، وفرزها، وعدد من ربما كان لديك تلك الأبواب إلى نظرة خاطفة وراء في ذلك أسوأ الحالات؟ جنيفر: كل منهم. DAVID J. مالان: كل منهم. لذلك دعونا التعميم أنه ن. هناك يحدث أن تكون 7، ولكن دعونا أكثر يقول عموما هناك ن الأبواب على الشاشة هنا. حتى في أسوأ الحالات، عملتم لننظر وراء الأبواب 7، أو ن الأبواب. وحتى هذا هو حقا، انها قليلا من الحظ اليوم، لكنها في الحقيقة خطي خوارزمية من نوع ما، حتى ولو كنت ونوع من تخطي حولها. هل هذا عدل؟ جنيفر: نعم. DAVID J. مالان: حسنا، دعني أرى إذا كان لديك تغييرات استراتيجية إذا انتقلت لنا ل المثال الثاني لدينا هنا مع 7 أبواب مختلفة. الأرقام نفسها، ولكن هذا الوقت يتم فرزها. ما هو استراتيجيتك هنا ستكون، في محاولة لاخماد من عقلك ما كانت أرقام أخرى - جنيفر: OK. DAVID J. مالان: - في وقت سابق؟ جنيفر: لنبدأ مع أول واحد. DAVID J. مالان: حسنا. تبدأ مع أول واحد. 4. الآن أين أنت ذاهب للذهاب، ولماذا؟ جنيفر: 4 صغير حقا. حتى لو انهم ربما أصغر نوع لأكبر، ينبغي له يكون ضعف ذلك، و-. DAVID J. مالان: OK. دعونا نرى، والتي كنت تعتقد؟ جنيفر: حاول واحد آخر. لطيفة. DAVID J. مالان: جيد جدا القيام به. حسنا. [تصفيق] DAVID J. مالان: OK. لذلك كنت تفعل في الواقع هذا فظيعة، لأنك يفعلون ذلك بشكل جيد جدا. مما يترك لنا غير قادر على جعل بعض النقاط. لذلك دعونا في محاولة لدحر هنا. جنيفر: OK. DAVID J. مالان: جيد جدا القيام به، على الرغم من ذلك. لذلك أنت التي في البداية، رأيت أنه كان 4، فإنك انتقل الى النهاية. ولكن لنفترض أنك لم تحصل على الحظ هناك، وافترض 50 كان في مكان آخر. ما كانت الخطوة الثالثة لديك؟ جنيفر: العودة إلى البداية. DAVID J. مالان: العودة إلى بداية. موافق، لذلك كنت قد لمست هذا الباب، الذي كان 8. حسنا. بحيث ليس 50. حيث كنت قد بدا في المرة القادمة؟ جنيفر: إذا لم أكن تعلم أنها فرزها. DAVID J. مالان: صحيح. حسنا، إذا كنت لم أعرف كانوا فرز - جنيفر: أوه، لم تعرف، نعم. DAVID J. مالان: - ولكنك لم أعرف من أين كانت 50 حتى الآن؟ جنيفر: مجرد الاستمرار. DAVID J. مالان: حسنا. موافق. الاستمرار. موافق، وأنني يمكن أن تعمل مع. جنيفر: OK. DAVID J. مالان: الآن، إذا كنت فقط سوف تستمر، ما هو الخاص خوارزمية تفويض المدعومة في. جنيفر: الخطي -. DAVID J. مالان: انه نوع من الخطية. ولكن اسمحوا لي أن أقترح، والسماح لي أن أطرح على الفور. اسمحوا لي بتحديث الصفحة. نفس العدد، وبنفس الترتيب، نفس الأبواب. ولكن التفكير مرة أخرى إلى أن اليوم الأول في عندما الدرجة نحن مزق كتاب الهاتف في نصف، نوعا ما، وما كان استراتيجيتنا هناك؟ جينيفر: تبدأ في الوسط. DAVID J. مالان: OK. حتى يبدأ في منتصف الطريق. لذلك دعونا نمضي قدما ومحاكاة ذلك. تبدأ في منتصف كتبها وكشف عن أن الباب. وبالتالي فإن عدد 16. وذلك ما قد فعلت الرجل القوي، الذي مزق دفتر الهاتف في النصف، للوصول الى تخمين القادمة؟ جنيفر: الذهاب في هذا الشوط. DAVID J. مالان: ولماذا للحق؟ جنيفر: إذا كانت نوعا من أصغر لأكبر، ثم يجب أن تكون 50 في هذه الغاية. DAVID J. مالان: جيد. معقول تماما. ذلك مثل دليل الهاتف، تذهب إلى الحق في مقابل اليسار، ولكن هنا هو مفتاح الوجبات الجاهزة. يمكنك الآن رمي بعيدا، أو تمزيق، نصف هذه المشكلة، ويترك لك لا مع 7 أبواب، ولكن في الحقيقة مع فقط 3. وهو ما يقرب من نصف حجم المشكلة. حسنا. وحتى الآن ما عملتم فعلت بعد يسير في الاتجاه الصحيح؟ جنيفر: إذن 16 لا تزال صغيرة جدا، النسبية إلى 50، وربما لذلك سأحاول، مثل، هذا واحد. DAVID J. مالان: حسنا. 42. كل الحق، وحتى الآن ما هو الخاص غريزة أقول لك؟ جنيفر: أستطيع أن نرمي هذا وبعد ذلك فقط - DAVID J. مالان: OK. جيدة، يمكنك رمي بعيدا النصف الأيسر هناك. جنيفر: - اختيار هذا واحد. DAVID J. مالان: والحق. جنيفر: نعم. DAVID J. مالان: ذلك على الرغم من أنه من الصعب لمعرفة ربما، عندما يكون هناك فقط 7 أبواب، والتفكير، والآن، اتساق خوارزمية قمت بتطبيقه فقط. في الحالة السابقة، فعلت تحصل على الحظ، الذي كان كبيرا. ولكن هل استخدام ارشادي، وأود أن أقول. كنت تستخدم نوع من الغرائز الخاص بك، و مع العلم أنه فرزها، إذا انها جميلة صغيرة في البداية، من الواضح، لدينا يجب أن أذهب أكثر إلى اليمين. ولكن في بعض المعنى، كنت محظوظا، لأنه ربما كان هذا العدد 100، وربما كان أكثر من 50 في الوسط. ربما كان 50 حتى أكثر من هنا. ولكن ماذا فعلت بشكل مختلف قليلا كان هذا الوقت، فعلت الشيء نفسه مرارا وتكرارا. وأنا أزعم أن ما كنت للتو لم، وإن كان يتأثر الهاتف الكتاب سبيل المثال، هو شيء من ذلك بكثير مزيد من حسابي، والكثير أقل فتش الخاصة. أقل بكثير غريزية. حتى في نهاية اليوم، وكيف يمكن أن تصف كفاءة الخوارزمية الأولى، حيث ذهبت من اليسار إلى اليمين، مقابل الخوارزمية الثانية هنا؟ جنيفر: هذا واحد ينبغي، مثل، ربما خفض الوقت، أو حتى أكثر من ذلك، نعم. DAVID J. مالان: حسنا، ربما حتى أكثر من ذلك. دعونا دفع اصعب قليلا على ذلك. ما حقا، إذا واصلنا هذا المنطق، ونحن بالتأكيد في النصف إدارة الوقت مع هذه الخوارزمية الثانية بواسطة رمي نصف أرقام، ولكن ماذا فعلنا على التالي التكرار، عندما كشفت جنيفر الرقم الثاني؟ نحن النصف أعداد الأبواب مرة أخرى. ثم ماذا نفعل بعد ذلك، إذا كان هناك المزيد من الأبواب للعب مع؟ فإننا النصف منهم، ومرة ​​أخرى، ومرة أخرى، ومرة ​​أخرى. وكان هذا مجرد مثل يا رفاق جميع واقفا في الأسبوع الأول من الطبقة، ونصف كنت جالسا، ونصف منكم الجلوس، نصف لك الجلوس، حتى واحد وحيد الروح واقفا. وقلنا أن وقت تشغيل ذلك، كان عدد من الخطوات التي اتخذت بناء على أمر من ماذا؟ سرور 1: [غير مسموع] DAVID J. مالان: تسجيل حتى 2 قاعدة من ن، أو مجرد ببساطة أكثر، سجل ن. ذلك شيء لوغاريتمي. وكان الرسم البياني لا خط مستقيم التي حصلت للتو أسوأ وأسوأ، وكان هذا المنحنى للاهتمام أن لم الحصول سيئا للغاية على مر الزمن. لذلك دعونا الابقاء على هذه الفكرة. دعونا نشكر جنيفر. شكرا جزيلا على حضوركم على ما يصل. و، واحدة ثانية. مصابيح لا مكتب اليوم، ولكن نحن لديهم CS50 كرات الإجهاد. جنيفر: ياي. DAVID J. مالان: حسنا، هنا. أشكركم على تكبد الضغط هنا. حسنا. لذلك دعونا نرى ما اذا كنا لا نستطيع الآن إضفاء الطابع الرسمي على هذا أكثر قليلا. ذلك مرة أخرى، ما فعلناه كان فقط أساسا نفس الشيء كما فعلنا في هذا الأسبوع الأول. ولكن بدلا من انهاء فقط مع الخطية الخوارزمية، وهو ما يصور سبق لأن هذا خط مستقيم، حيث، إذا وضعنا أكثر واحد على الباب الشاشة، ثم سوف جنيفر لقد كان للنظر، ويحتمل أن تكون، وراء واحد أكثر الباب. إذا وضعنا اثنين من أكثر الأبواب، وقالت انها قد تضطر لننظر وراء اثنين من أكثر الأبواب. وهكذا، كان هناك هذه الخطية العلاقة بين حجم المشكلة على، ويقول، المحور س، و مقدار الوقت الذي يستغرقه ل حل على ذ. ولكن الصورة كنت في اشارة الى وكان في وقت سابق من هذا الخط الأخضر. الأخضر عمدا، ل شعرت فقط أفضل. من الناحية النظرية، الخوارزمية، وعندما فعلنا ذلك مع دفتر الهاتف، وعندما فعلنا ذلك مع رفاق عد بعضها البعض، و في الحالة الثانية، عندما جنيفر فقط فعل ذلك هنا، كان من نوع من أفضل جذريا. لأنه لم يكن مجرد أسرع مرتين. لم يكن حتى أربع مرات أسرع وقت. كان عليه اعتمادا كليا على ما وكان حجم المدخلات، عن كيفية العديد من الخطوات التي اتخذت في نهاية المطاف. وحتى هذه الفكرة البسيطة التي نحن جميعا استغرق من المسلمات مع دفتر الهاتف، يمكن تطبيقها بالمثل إلى شيء من هذا القبيل. وهذا قد يكون أكثر عرضا المعروف، كما قد تخيل، فرق تسد. لا يختلف ما فعلناه، بطبيعة الحال، مع دفتر الهاتف. ولكن شبة الكود، أذكر، كان هذا. لذلك نحن لن نفعل ذلك مرة أخرى، ولكن أذكر أن الأسبوع الأول، وقفت كل منا حتى ثم نصف كنت جلست، ونصف كنت جلست، ونصف كنت جلست. تم تنفيذ الخوارزمية التي في قليلا من وسيلة الغش، في ذلك، لم يكن واحدا فقط من عد لي، في الأساس، وأكثر كفاءة. في هذه الحالة، كنت الاستفادة مورد الثانوية. نوعا ما، وحدات المعالجة المركزية متعددة، والعقول متعددة، الناس الذكية متعددة في غرفة تم الحصول عليها من مساعدتي شيء خطية إلى شيء لوغاريتمي، من شيء الأحمر إلى شيء أخضر. ولكن في هذه الحالة، جنيفر وحده يمكن تحسين جذري على أداء أول خوارزمية لها من قبل، مرة أخرى، مجرد التفكير أصعب قليلا. والآن، عندما يحين الوقت لتنفيذ هذه الأشياء، ومعرفة ما أسطر من التعليمات البرمجية يمكنك كتابة مثل يمكنك أن أكررها مرة أخرى، و مرة أخرى، ومرة ​​أخرى، نوع من بطريقة حلقات. لأنك لن يكون لديك الفاخرة، مثل جنيفر فعل في الأولى، ل يكون مجرد مجمله مجموعة من المحاذير ويقول: هم، إذا كان هذا الرقم الأول هو 4، اسمحوا لي أن القفز على طول الطريق حتى النهاية. أوه، إذا كان هذا عدد كبير جدا، اسمحوا لي أن تتحرك بشكل تعسفي العودة إلى العنصر الثاني. سوف تجد أنه سيكون الكثير أصعب لإضفاء الطابع الرسمي ما نحن البشر أمرا مفروغا منه كما معقولة جدا الاستدلال، ولكن ليست سوى جهاز كمبيوتر سوف تفعل ما أقول أن تفعله. الآن لديه هذا مثير جدا للاهتمام الآثار المترتبة عليها. هو نوع من يعني هذا الرسم البياني إلى نوع من تطغى بصريا، ولكن لاحظ، حيث هو خط مستقيم في هذا الرسم البياني؟ أين هو الرسم البياني الخطي التي نسميها ن؟ حسنا، انها نوع من نحو القاع هذه الصورة، أليس كذلك؟ لذلك كل ما فعلناه هو أننا قمنا نوع من التصغير إلى محور س و المحور الصادي في محاولة للحصول على شعور ما أنواع أخرى من المنحنيات تبدو. وخصوصيات الرياضية تعبيرات اليوم لن يهم ذلك كثيرا، ولكن لاحظت أن هناك الكثير من الخوارزميات التي هي أسوأ بكثير من هذا شيء الخطية. في الواقع، ن مكعبة تبدو سيئة جدا. 2 إلى ن تبدو سيئة جدا. ن المربعة تبدو سيئة جدا. وسنرى ما بعض تلك قد تكون في الواقع اليوم. وسجل ن لا يشعر بالسوء، ولكن أفضل من n هو قاعدة سجل 2 من ن. ولكن كما تعلمون، كان يمكن أن يكون حتى اكثر من المدهش إذا جنيفر، أو إذا كنا، أن الأسبوع الأول، قد حان حتى مع شيء وهذا السجل من سجل ن. لذلك وبعبارة أخرى، هناك هذا كله مجموعة من الحلول الممكنة ل المشاكل، ولكن حتى هنا، لاحظ ما الذي سيحدث. عندما كنت التصغير، أي من هذه المنحنيات سوف يثبت أن المطلقة أسوأ من تلك التي تظهر على الشاشة الآن؟ حتى ن مكعبة تبدو جميلة سيئة في الوقت الراهن. ولكن إذا كنا التصغير ونرى أكثر من س والمحور ص، الذي يحدث ل تهيمن في نهاية المطاف؟ لذلك تبين فعلا أن 2 إلى ن، ويمكنك معرفة ذلك فقط عن طريق يسد في بعض كبير ومتزايد الأرقام، وسترى أن 2 إلى ن، في الواقع، تكبر أسرع من ذلك بكثير. إذا كنا حقا تصغير، 2 ل ن خوارزمية تمتص تماما. أعني هذا هو ذاهب الى اتخاذ قدرا كبيرا من الوقت ل الكمبيوتر بعنف من خلال. ولكن سترى مع مرور الوقت، وخاصة مع مجموعات مشكلة في المستقبل، وحتى المشاريع النهائية، هي البيانات الخاصة بك مجموعة كبيرة يحصل، كل الحق؟ حتى في النسخة الأولى من الفيسبوك، كما أن عدد من الأصدقاء، و حصل عدد المستخدمين المسجلين كبير، يمكنك فرز الهاتف في و تنفيذ شيء مع البحث الخطي، أو الفرز بسيط جدا الخوارزمية، كما سنرى اليوم. عليك أن تبدأ التفكير أصعب وأصعب حول هذه المشاكل. وأنواع من المشاكل مثل يضع الفيسبوك، وجوجل، ومايكروسوفت، والبعض الآخر عمل على هو بالضبط هذه نوع البيانات نوع من كبيرة من الأسئلة على نحو متزايد هذه الأيام. حسنا. لذلك النجاح جنيفر في هذا الثاني الخوارزمية، بصراحة، فعلت مثير للدهشة كذلك أول مرة، ولكن دعونا إرسال الحظ أنها حتى نتمكن يمكن أن تجعل هذه النقطة. في الحالة الثانية، وقالت انها عبأت الخوارزمية التي تتكرر مرة أخرى و مرة أخرى، ولكن أخذت لمنح افتراض أن بعض سمحنا لها، لكنها استغلت بعض التفصيل المرة الثانية التي قالت انها لم يكن لديها المرة الأولى. الذي كان ماذا؟ التي تم فرز القائمة. ذلك في أقرب وقت تم فرز قائمة، ونحن يدعون أن جنيفر كان قادرا على القيام جوهريا أفضل. 7 أبواب، نعم، ليست مثيرة للاهتمام، ولكن لنفترض أنه نحن 7 ملايين الأبواب. سجل ن هو بالتأكيد لأداء الكثير، الكثير أسرع في المدى الطويل. ولكن كان عليها أن لديها أبواب فرز لها. الآن، أخذت الحرية لفعل ذلك مقدما على شاشة الكمبيوتر هنا، ولكن لنفترض أن جنيفر كان لفعل ذلك بنفسها؟ لنفترض أن الأبواب في السؤال البيانات ممثلة في قاعدة بيانات، أو الأصدقاء مسجلة لالفيسبوك، أو أي صفحات على شبكة الانترنت على شبكة الإنترنت أن مختلف المواقع قد تحتاج إلى الفهرس أو البحث عبر. افترض أنك كان مجرد البيانات الخام تعيين وتركت ذلك لك، أو ل جنيفر لفعل ذلك الفرز؟ التي، بدلا من ذلك، يتطلب منا الإجابة السؤال، حسنا، كم من الوقت كان قد اتخذ جنيفر، أو حتى لي، لفرز هذه الأرقام في وقت مبكر حتى أنها يمكن أن تستفيد من ذلك؟ أليس كذلك؟ لأن ضمنا، بالطبع، هو إذا كان يأخذ مني الكثير من الوقت لفرز أرقام، الذي يهتم هيك أنك يمكن العثور على عدد مثل 50 بسرعة، كما في حالة جنيفر، وإذا كنا أكثر من طغى على مقدار الوقت الإجمالي استغرق الأمر من خلال فرز الأشياء مقدما؟ لذلك دعونا نرى ما اذا كنا لا يمكن لل ترسم الصورة هنا. لدي كله حفنة مزيد من التوتر الكرات، واذا كان ذلك يساعد كسر الجليد هنا. وإذا كنت لا تمانع، ونحن يحتاج الى سبع التطوعي - على، OK. نجاح باهر. لذلك نحن لم يكن لديك لقضاء على المصابيح المكتبية، على ما يبدو. حسنا. فكيف لك اثنين في الجبهة. كيف عنك اثنين من اللاعبين في الخلف. ذلك أن الأربعة. كيف عنك أمام خمسة، ستة وسبعة. هناك حق. صديقك لافتا لكم، حتى تحصل على الجائزة. حسنا. تأتي على ما يصل. ولماذا لا يكون لك نحن رفاق هيا أكثر من هنا. انا ذاهب الى ان نعطيكم كل عدد. والمضي قدما وترتيب أنفسكم مطابق لما هو صورت على الشاشة. [VOICES فاصلة] DAVID J. مالان: OOP، آسف. علة. حسنا. حسنا، هنا نذهب. رقم خمسة. رقم ستة. واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، سبعة. أوه، هذا هو حرج. المتحدث 2: سوف مجرد الحصول على -. DAVID J. مالان: صفقة جيدة. حسنا. شكرا لك على المشاركة. [تصفيق] موافق. حسنا. لذلك لدينا أربعة، اثنان، ستة، واحد، ثلاثة، سبعة، خمسة. مثالية لذلك لدينا سبعة متطوعين هنا الذين متساوون في العرض ل مجموعة أننا نلعب مع في وقت سابق. واختار سبعة لأسباب التي من شأنها أن تكون مجرد مريحة في قليلا. وانا ذاهب الى اقتراح الأولى التي نحن فرز هؤلاء المتطوعين سبعة. إذا كنت ترغب، أولا، على الرغم من أن أقول مرحبا. لأن هذا سيكون ل عدة دقائق حرج. أعرض أنفسكم. جريس: مرحبا، أنا غريس. أنا طالبة في يفيريت البيت. BRANSON: مرحبا. أنا برانسون. أنا طالبة في ولد. GABE: مرحبا. أنا غابي. أنا صغير في كابوت. نيل: أنا نيل. أنا طالبة في ماثيوز. جيسون: أنا جيسون. أنا طالبة في جرينوف. مايك: أنا مايك. أنا طالبة في غرايز. جيس: أنا جيس. أنا طالبة في يفيريت. DAVID J. مالان: ممتاز. حسنا. حسنا، شكرا لكم جميعا لدينا المتطوعين هنا حتى الآن. والتحدي الآن في متناول اليد يجري أن تكون لفرز من هؤلاء الرجال، ولكن بعد ذلك ونحن في طريقنا إلى أن نفكر قليلا من الصعب حول مدى كفاءة ونحن في الواقع فرز لهم. لذلك دعونا نحاول الاولى من هذا. يمكنك معرفة أرقام اللاعبين بعضهم البعض فقط عن طريق وضع حول الزوايا. المضي قدما واتخاذ بضع ثوان، و فرز أنفسكم من أصغر على من اليسار إلى أكبر على اليمين. تذهب. موافق. جيدة. كان ذلك حقا سريع الرتق. الآن شخص ما هنا، ما كان الخوارزمية أن هؤلاء الرجال تطبيقها؟ سرور 1: الأقل الى أكبر. DAVID J. مالان: OK. الأقل إلى الأكبر هو في الحقيقة نوع من الهدف، ولكن لست متأكدا من ذلك حقا خوارزمية. الأقل إلى الأكبر لا أقول لي خطوة بخطوة ما يجب القيام به. نعم؟ سرور 1: [غير مسموع] DAVID J. مالان: OK. حتى إذا كنت ترى شخص أصغر من رقم هاتفك، ثم الانتقال إلى حق لهم. بحيث يزداد الآن أكثر تعبيرا، أشبه الخوارزمية، لأنك يمكن القول، إذا كان هذا، ثم ذلك. لذلك لدينا نوع من بناء الشرطي. وبدا هؤلاء الرجال للقيام بذلك قليلة مرات، وذلك لأن البعض منكم انتقلت قليلا من مسافة بعيدة. لذلك كان هناك نوع من المفترض حلقات يدور في عقولهم. ولكن دعونا نحاول أن إضفاء الطابع الرسمي على ذلك. إذا يا رفاق يمكن إعادة تعيين لهذا الترتيب. دعونا نرى ما اذا كنا لا يمكن إضفاء الطابع الرسمي على هذا قليلا، ثم نطرح هذا السؤال، فقط مدى كفاءة هذا؟ بطبيعة الحال، عندما نفعل ذلك ببطء أكثر، انها سوف تشعر كما لا بأس به من خوارزمية، ولكن دعونا نرى ما اذا كنا نستطيع وضع أصابعنا على الخطوات الدقيقة. لذلك كنت اثنين من اللاعبين أربعة واثنين. أو يمكنك تصحيح أو ترتيب غير صحيح؟ من الواضح غير صحيحة. لذلك نحن تبادلت. الآن انا ذاهب الى التحرك جانبا وهنا أقول، 05:56. أنت صحيحة أو غير صحيحة؟ GABE: صحيح. DAVID J. مالان: صحيح. ستة واحد؟ كلا. المبادلة. ذلك أن اثنين مقايضة. ستة وثلاثة؟ كلا. المبادلة. ستة وسبعة؟ تبدو جيدة. سبعة وخمسة؟ جيس: [غير مسموع] DAVID J. مالان: OK، مبادلة. وفرزها. حسنا. لذلك من الواضح أن لا، أليس كذلك؟ لذلك كان هناك أكثر مستمرة. ولكن، في الواقع، هؤلاء الرجال، حتى غريزي فقط. أبقى تتحرك. أنها لم تتوقف فقط، وبمجرد أن تصحيح مشكلة واحدة. لذلك. في الواقع، انا ذاهب ل لتفعل الشيء نفسه. انا ذاهب الى أن نوعا من الترجيع الى الوراء إلى بداية هذه المشكلة، أو بداية هذه مجموعة من الناس، دعونا بدء الدعوة لهم. والآن ماذا ينبغي خوارزمية بلدي على مسار الثاني أن يكون؟ سرور 1: نفس الشيء. DAVID J. مالان: نفس الشيء. وهذا، أنا بدأت أحب، أليس كذلك؟ بمجرد أن تجد نفسك تفعل الشيء نفسه مرارا وتكرارا، وهذا أصبحت أشبه خوارزمية، وأقل غريزة الإنسان. وحتى الآن، وهنا نذهب مرة أخرى. اثنين وأربعة؟ لا. أربعة واحد؟ آه، كان هناك بالفعل بعض العمل لا يزال يتعين القيام به. لوثلاثة؟ جيدة. أربعة وستة؟ ستة وخمسة؟ ستة وسبعة؟ حسنا، الآن، القيام به. حسنا، لا. لا بد لي من العودة. وحتى الآن، ومرة ​​أخرى، ونحن نفعل ذلك أكثر من ذلك بقليل عمدا. والآن، هناك دماغ واحد فقط تنفيذ هذه الخوارزمية. واحد وحدة المعالجة المركزية، اذا صح التعبير. وبصراحة، هذا هو المورد الوحيد ونحن في طريقنا إلى الحصول على. ومرة واحدة ونحن لا نعود إلى لوحة مفاتيح والحصول على شيء مثل C في موقعنا التخلص منها، ونحن كتابة برنامج فقط التي يمكن أن تفعل شيئا واحدا في وقت واحد. في حين، هؤلاء الرجال قبل لحظة، ونحن الاستدانة القدرات العقلية الجماعية مثل يا رفاق فعلت في الأسبوع الصفر. لذلك دعونا نواصل القيام بذلك. اثنين واحد. اثنين وثلاثة. ثلاثة وأربعة. أربع وخمس سنوات. خمسة وستة. ستة وسبعة. فعلت؟ لذلك أنا، ولكن اسمحوا لي اللعب محامي الشيطان. يمكنني، هذا النوع من الكمبيوتر الذي فقط قدم تمريرة من خلال هذه المجموعة من الناس، ونعرف أن انتهيت؟ سرور 1: رقم DAVID J. مالان: إذن لماذا؟ ما الذي يجب أن أقوم به من أجل اختتام حاسم أنني فعلت؟ على الارجح واحدة تمريرة أكثر من ذلك. أليس كذلك؟ لأن كل ما أعرفه أن من السابق تمرير هو أنني تصحيح الخطأ. وهذا يعني، ربما هناك لا يزال خطأ آخر أنني بحاجة إلى تصحيح. حتى أتمكن من التأكد فقط من قبل اللف، و ثم التحقق، 01:59، وهما و ثلاثة وثلاثة وأربعة، وأربعة وخمسة، خمسة وستة، ستة وسبعة. حسنا، الآن أنا فعلت أي عمل. أستطيع أن أتذكر بالتأكيد أنني لم يفعل العمل مع شيء من هذا القبيل متغير، مثل كثافة العمليات. نسميها مقايضة، وإذا هو مقايضة 0 مرة واحدة إلى هنا، وأنها بدأت في 0، ثم سأكون مجرد غبي على الاستمرار ذهابا وإيابا، والتحقق مرة أخرى، و مرة أخرى، ومرة ​​أخرى، أليس كذلك؟ لأنك تتعثر في بعض نوع من حلقة لا نهائية. ذلك في أقرب وقت هناك مقايضة 0، ويمكن أن ندعي أن هذا الخوارزمية هو في الواقع كاملة. الآن، دعونا نضع اسما في هذا الشأن. الخوارزمية التي أقترح أننا فقط ينفذ هو ما يسمى فقاعة نوع، والمعروفة باسم مثل بمعنى أن الأرقام التي هي نوع من أكبر فقاعة طريقهم صعودا إلى الأعلى، أو ما يصل إلى نهاية مجموعة من الأرقام. ولكن كيف كان كفاءة هذه الخوارزمية؟ كيف العديد من الخطوات لم لدي جسديا ل تتخذ، على سبيل المثال، لفرز هذه سبع البشر؟ أربعة إلى خمسة؟ موافق، وكثير جدا هو في نهاية المطاف سيكون الجواب. ولكن حتى ذلك الحين، وعدد محدد ليس للاهتمام بذلك. دعونا تعميمها كما ن. حتى إذا كان لي ن الناس هنا، وأنها كانت، نوعا ما، في ترتيب عشوائي في بداية، في هذا النظام الأصلي. حسنا، كيف العديد من الخطوات لم لدي لتأخذ على مرور الأول؟ وكانت واحدة، اثنان، ثلاثة، أربعة، خمسة، ستة، وانهم سبعة أشخاص، لذلك هذا هو سبعة، ستة -، حتى أن ن ناقص واحد الخطوات للمرة الأولى. الآن، كم من الخطوات التي لدي لاتخاذ عندما لف؟ حسنا، نحن يمكن أن تتضاعف في الواقع أنه إذا كنا نريد حقا أن، لكنه الآن، وأنا فقط أريد أن أقول، كل الحق، ن آخر ناقص 1. حتى ن ناقص 1 هو الذهاب الى الحصول لتتبع، لذلك دعونا مزعج مجرد جولة ارتفاعا طفيفا. الخطوات 2N ذلك. حتى 14 الخطوات، يعطي أو يأخذ. كم مرة لم أنتهز خطوة في المرة القادمة؟ حسنا، انها 3N. حقا. والآن، في أسوأ الأحوال، ل مثلا، كم مرة سوف لدي ذهب ذهابا وإيابا، ذهابا وإيابا، تنفيذ هذه الخوارزمية، مبادلة الناس تمر على كل، تقريبا؟ انها في الواقع ن التربيعية، أليس كذلك؟ لأنه في أسوأ الحالات، يمكنك النوع من التفكير في هذا حدسي، على الرغم من ان الامر قد يستغرق قليلا قليلا من الوقت لتغرق فيها. في أسوأ الحالات، ما هذه وقد بدا سبعة أشخاص مثل، في حيث الترتيب من أعدادهم؟ تماما إلى الوراء، أليس كذلك؟ وفقط لمحاكاة ذلك، ما كان اسمك مرة أخرى؟ مايك: مايك. DAVID J. مالان: مايك؟ موافق، مايك، يمكنك فقط الانضمام لي أكثر هنا لمدة ثانية واحدة فقط؟ في الواقع، لا. آسف مايك، دعونا الترجيع. ما اسمك مرة أخرى؟ نيل: نيل. DAVID J. مالان: نيل. موافق، ونيل، جئت مع لي، إذا كنت لا تمانع. لذلك أنا ذاهب الى اقتراح، فقط ل بساطة، أن نيل هو الآن في بلده أسوأ حالة ممكنة. ولكن أذكر كيف تنفذ بلدي الخوارزمية. أنا مقارنة، مقارنة، مقارنة، مقارنة، مقارنة، أوه. الآن هؤلاء الرجال هم خارج من النظام، لذلك أنا إصلاح. لذلك يا رفاق مبادلة. ولكن النظر الآن، وكم أبعد لا نيل أن تذهب؟ انها تقريبا ن. كما تعلمون، انها ليست في الواقع ن. انها مثل، ن ناقص 1، ولكن انني اتلقى المسار حفظ منزعج من القليل عدد، لذلك دعونا ندعو فقط لانه ن. إذا كان الأمر كذلك يتحرك خطوة واحدة نيل الحد الأقصى لكل الوقت، والتحرك نيل خطوة واحدة، لقد جعل هذا تمريرة شاقة حقا ذهابا وإيابا، وهذا هو ما يقرب من القيام بذلك، ن الخطوات، ما مجموعه مرات ن، لأنه يحدث أن يأخذني أن العديد من الخطوات للحصول على نيل جميع الطريق إلى المكان الذي ينتمي إليه. ناهيك عن الجميع إذا يا رفاق كان كل سوء أمر كذلك. لذلك دعونا ندعو فقاعة نوع ن المربعة. وقت تشغيل هذه الخوارزمية، و أداء هذه الخوارزمية، و كفاءة هذه الخوارزمية، ونحن يجب فقط وصف أكثر عموما كما ن المربعة. التي هي لطيفة، لأنني يمكن أن تفعل نفس المثال مع ثمانية أشخاص، تسعة الناس، من مليون شخص، والتي الجواب لن تتغير. لذلك إذا كنت لا تمانع في الرجال، دعونا إعادة تعيين لك حيث كنت بدأت. ودعونا نحاول نهجين الأخرى و نرى ما اذا كنا لا نستطيع أن نفعل الأساس أفضل من هذا. وحتى هذا الوقت، انا ذاهب الى اقتراح نوع من خوارزمية مختلفة. كان ذلك ذكي جدا منا في المرة السابقة، وكانت يا رفاق الحق في الحصول على الغرائز حق مجرد نوع مبادلة البشرى. ولكن إذا أردت حقا أن هذا النهج ببساطة، وهدفي هو التحرك جميع الأرقام قليلا بهذه الطريقة، و دفع كل من الأرقام الكبيرة التي بالمناسبة، لماذا لا أنا فقط تفعل ذلك في معظم طريقة ساذجة ممكن، ومعرفة ما اذا كنت يمكن أن نفعل ما هو أفضل مما كان خوارزمية معقدة إلى حد ما؟ لذلك دعونا نرى. أربعة هو عدد صغير جدا، لذلك أنا سوف أترك لكم هناك لحظة. أوه، رقم اثنين، بل هو أفضل. حتى تتمكن من خطوة إلى الأمام فقط للحظة؟ هذا هو حاليا أصغر مرقمة بلدي مرشح، وانا ذاهب الى تذكر مع أن، مثل، متغير. ولكن انا ذاهب للحفاظ على التحقق. هناك شخص الذي عدد أصغر؟ ستة، لا. أوه، هناك نيل مرة أخرى. لذلك أنا ذاهب لدفع لك مرة أخرى نوع من الناحية المفاهيمية. سيأتي نيل الأمام. والآن، المتغير الذي أنا باستخدام ل تتبع لديه أصغر يتم تحديث عدد لاحتواء موقع نيل. حسنا، دعونا نرى. ثلاثة، سبعة، خمسة. حسنا، أنا أعرف كان نيل أصغر. ما هو أبسط شيء بالنسبة لي أن أفعل الآن؟ أنا لن أضيع وقتي فقط عن طريق محتدما نيل بقعة واحدة إلى اليسار. لماذا لا أنا فقط وضعت نيل حيث ينتمي، الذي هو بطبيعة الحال أين؟ كل وسيلة في البداية. حتى نيل، وتأتي معي. وماذا كان اسمك مرة أخرى؟ جريس: غريس. DAVID J. مالان: غريس. موافق. حتى غريس، للأسف، كنت نوع من في الطريق. فكيف نحل هذه المشكلة؟ أليس كذلك؟ إذا كان هذا هو صفيف، هناك فقط سبعة مواقع. أذكر أنه مع روب، تحدثنا عن معلنا الأعمار، وكان لدينا فقط عدد محدود من الأعمار؟ نفس الفكرة هنا. ليس لدينا سوى عدد محدود من رجات. نعمة هو نوع من خلال موقعنا طريقة، لذلك كيف يمكننا إصلاح؟ أبسط طريقة هي مثل، نعمة، آسف. وأنت تسير لدينا ليذهب أكثر هناك حتى نتمكن من جعل الغرفة. الآن، إذا كنت تفكر في ذلك، وربما التي قطعناها على أنفسنا فقط المشكلة سوءا. وربما فعلنا، لأن ما إذا كانت نعمة في المكان المناسب؟ ولكننا نعرف أنها ليست، ل خلاف ذلك، وقالت انها كانت يقف إلى الأمام بدلا من نيل في هذا الوقت، أليس كذلك؟ بحثنا بالفعل عدد لها للخروج. حسنا. وحتى الآن، ونيل في المكان المناسب، و يمكنني القيام به لتحسين طفيف. لفي الدقيقة التالية، انا ذاهب الى تجاهل نيل كل ذلك معا، حتى لا يضيع وقته، أو عن طريق الخطأ مبادلة له إلى المكان الخطأ. وحتى الآن، وكيف يمكنني العثور على القادم العنصر الذي هو أصغر؟ اثنين. هذا هو عدد جيد جدا، وإذا تريد خطوة إلى الأمام و سوف نتذكر لك. ستة، ليس جيدا. أربعة، ثلاثة، سبعة، خمسة، ليس جيدا. لذلك اسمحوا لي نقل لكم ل المكان حقك. ونحن فقط حصلت على الحظ هذه المرة. الآن، انا ذاهب الى تجاهل هذه اثنين من اللاعبين، والآن تفعل أكثر واحد تمر عبر هذا. ستة، أن عددا صغيرا جدا. هيا إلى الأمام. أوه، آسف. عدد النعمة هو أفضل، ذلك خطوة على الأمام. أربعة. آسف، غريس. أعود مرة أخرى. رقم ثلاثة هو أفضل. سبعة. خمسة. والآن ما اسمك مرة أخرى؟ JASON: جايسون. DAVID J. مالان: جايسون. حتى جيسون هو الآن أصغر لقد عنصر المحدد. أين هو ذاهب للذهاب؟ فأين هو ستة. واسمك مرة أخرى؟ GABE: غابي. DAVID J. مالان: غابي. غابي في الطريق. ما هو أسهل ما يمكن فعله؟ مبادلة اثنين من هؤلاء الرجال والاستمرار. حتى الآن دعونا نرى. من هو أصغر؟ أربعة. اسمحوا لي أن مجرد نوع من الغش. خمسة ستكون أصغر. أجد المقبل، إذا، وتريد أن الخطوة إلى الأمام، ماذا علي أن أفعل مع هؤلاء الرجال، مع غابي؟ مبادلة مرة أخرى. حتى الآن، لا تزال خارج قليلا من النظام. لقد وجدت غابي ليكون أصغر، لذلك أنا البوب ​​له بالخروج، تحرك يا رفاق أكثر. والقيام به. ذلك الجواب هو نفسه. والنتيجة النهائية هي نفسها. أي من هذه الخوارزميات اثنين هو أفضل؟ ثانية واحدة، سمعت. لماذا؟ SPEAKER 3: انها ن الخطوات [غير مسموع]. DAVID J. مالان: انها خطوات ن على الأكثر. مثيرة للاهتمام. فهل في هذه الحالة على الرغم من؟ فكيف لم أجد أصغر عنصر؟ كيف العديد من الخطوات لم لا بد لي من اتخاذ والعثور على أصغر عنصر؟ كان لي نظرة على طول الطريق في النهاية، أليس كذلك؟ لأنه في هذه الحالة الأسوأ، ما إذا كان نيل أكثر من هنا؟ حتى مجرد العثور على أصغر عنصر يأخذ لي ن الخطوات، أو ن ناقص 1. ولكن، حسنا. حتى نيل إصلاح. تذكر أنه، لمدة دقيقة أو نحو ذلك قبل. ولكن كيف لم أجد المقبل أصغر عنصر؟ انها ن ناقص 1، أو ناقص 2 ن حقا، من عدد من الخطوات. موافق لذلك. هكذا فعلت ن ناقص 2. حسنا. بحيث يشعر على نحو أفضل قليلا. حسنا. كيف العديد من الخطوات في المرة القادمة للعثور على رقم ثلاثة؟ حتى ن ناقص 4. حتى انها في تناقص، واحدة أقل خطوة على كل تكرار. لذلك هذا لا يشعر على نحو أفضل، أليس كذلك؟ إذا كان آخر مرة تقريبا ن ن مرات، هذه المرة انها ن ناقص 1، بالإضافة إلى ن ناقص 2، بالإضافة إلى ن ناقص 3، بالإضافة إلى ن ناقص 4، نقطة، نقطة، نقطة. ولكن إذا كنت أذكر من المدرسة الثانوية الخاصة بك الكتب المدرسية، والغش قليلا ورقة في الجزء الخلفي الذي يحتوي على الصيغ، إذا يمكنك إضافة حتى هذه السلسلة من الأرقام، ما هو العدد الإجمالي من الخطوات ستكون أن أغتنم هنا؟ هذا هو واحد من هؤلاء، مثل، ن ناقص 1، ن مرات، مقسوما على 2. لذلك اسمحوا لي أن نرى ما اذا كان يمكنني سحب هذا الأمر لمجرد لحظة. ومرة أخرى، وأنا نوع من التقريب بعض أرقام فقط للحفاظ على حياتنا بسيطة، ولكن على ما أذكر، انها شيء من هذا القبيل إذا أفعل ن ناقص 1 الأشياء، ثم ن ناقص 2، ثم ن ناقص 3، انها تقريبا شيء من هذا القبيل أكثر من 2، وإذا كنت مضاعفة هذا الخروج، وهذا في الواقع ن مربع. هذا ليس شعور جيد جدا. ن ن ناقص أكثر من 2. ولكن هنا الشيء. في علوم الكمبيوتر، وعندما المشاكل تبدأ في الحصول على اهتمام هو عندما ن يحصل كبيرة حقا. وعندما ن يحصل كبيرة حقا، والتي من هذه القيم سوف تهيمن على كل من الآخرين؟ انها نوع من ن التربيعية، أليس كذلك؟ نعم، قسمة 2 هو جيد جدا. ولكن إذا كنت تتحدث عن المليارات من قطعة من البيانات، أو تريليونات قطعة من البيانات، حسنا، كنت أسرع مرتين. ولكن من يهتم حقا إذا كان هذا عدد كبير، إذا كان هذا العامل هو ما يحصل أكبر وأكبر. وبالتأكيد، فإنه يجعل أكثر من فرق من هذا الرجل. ذلك على الرغم من يا رفاق هي الحق، و الخوارزمية الثانية، ونحن سوف يطلق عليه اختيار نوع، هو، في العالم الحقيقي، و بت أسرع يحتمل، لأنني اتخاذ أقل وأقل الخطوات في كل مرة. انها ليست حقا جوهريا أسرع. لأنه إذا لعبنا فعلا من ذلك ل قيم كبيرة من ن، في نهاية اليوم، ل n كبيرة بما فيه الكفاية، فإنه لا يزال سوف تشعر بطيئا جدا. حسنا، اسمحوا لي أن تأخذ واحدة تمريرة مشاركة في ذلك. هذا هو ما يمكن أن أسميه اختيار نوع. يمكنك إعادة تعيين الرجال أنفسكم للمرة الأخيرة؟ وفي هذه الحالة الأخيرة، انا ذاهب لاقتراح شيء دعا الإدراج الفرز. الإدراج نوع الوجود، من الناحية النظرية، مختلفة بعض الشيء. بدلا من الذهاب ذهابا وإيابا و اختيار أصغر عنصر، وأنا مجرد الذهاب للتعامل مع كل من هذه الرجال كما واجهت منهم، وإدراج لهم في مكانها الصحيح. لذلك أنا ذاهب فقط لتبدأ غريس، وأرى أن انها رقم أربعة. أين رقم أربعة تنتمي؟ أنا لم تكن قد بدأت الفرز أي شيء، حتى يحصل على نعمة البقاء هناك. والآن انا ذاهب الى المطالبة، إذا كنت قد اتخاذ خطوة إلى اليمين، وهذا قائمتي فرزها، وهذا هو بلدي قائمة المتبقية التي لم يتم فرزها. حتى الآن انا ذاهب الى المضي قدما المقبل، وما اسمك مرة أخرى؟ BRANSON: برانسون. DAVID J. مالان: برانسون. حتى برانسون هو رقم اثنين. لذلك أنا ذاهب الى اتخاذ لكم من لحظة واحدة. والآن، أين كنت تنتمي في هذه المجموعة؟ ذلك أن حق النعمة. ذلك مرة أخرى، نحن نوع من صنع نعمة القيام بالكثير من العمل هنا. أين نضع لك؟ لذلك نحن ذاهبون الى الشريحة التي ل اليسار، وإدراج برانسون هناك. ولكن الآن أزعم أن تتم يا رفاق. ولكن الإشعار، أنا لا تستخدم مساحة إضافية. انها لا تزال عناصر 2 هنا، 5 أكثر من هنا. إجمالي حجم الصفيف هو 7، لذلك أنا لا الغش، كل الحق؟ حتى الآن لدينا، مع غابي هنا، رقم ستة، أين كنت تنتمي؟ كنت محظوظا مرة أخرى. حتى تحصل على الحق في البقاء هناك. مجرد اتخاذ خطوة طفيفة إلى اليمين فقط لتوضيح أن كنت فرزها. والآن لدينا نيل مرة أخرى، عدد واحد، أين تذهب؟ والآن حيث سنبدأ أن نرى أن هذه الخوارزمية، على الرغم من الأولى محة، يشعر ذكية جدا، ومشاهدة ما هو على وشك الحدوث. إذا كنت قد خطوة إلى الأمام. أين نحن نريد ان نضع نيل؟ لذلك من الواضح هنا، فكيف لم نحصل على نيل هناك؟ دعونا نفعل ذلك خطوة خطوة. غابي، حيث لا تحتاج أن تذهب؟ نعم، حتى تأخذ خطوة واحدة كبيرة، أو اثنين من نصف خطوات لجعل خطوة واحدة هناك. نعمة، أين تذهب؟ جيدة. ذلك خطوة أخرى. وأخيرا، برانسون؟ خطوة أخرى. والآن يمكننا وضع نيل في مكانها. وحتى الآن، لا تزال هذه المنطق. على الرغم من أننا لا يتحول نيل أكثر، وعلى، وعلى، وضعه أين يذهب، في أسوأ الحالات، و عدد المقبلة التي يمكن أن نواجهها يمكن أن عدد، على سبيل المثال، كان هناك عدد صفر، ثم ونحن في طريقنا لتحويل جميع هؤلاء الرجال. لنفترض أن هناك عددا، السلبية واحد، ثم لدينا لتحول كل من هؤلاء الرجال. لذلك نحن حقا مجرد نوع من التقليب مشكلة حولها، بحيث نحن نقل حساب من عملية الاختيار وبالتالي فإن الإدراج العملية، بحيث يا رفاق للتو لنقل ما يقرب من ن ناقص شيء عدد من الخطوات. وهذا العدد من الخطوات لن يؤدي الا لزيادة وأنا تحديد المزيد من الأرقام، إذا كان لدي للحفاظ تدافع يا رفاق مرة أخرى، ومرة ​​أخرى، والظهر. وبالتالي فإن الشيء المحزن الآن كل هذه ون التربيعية الخوارزميات. دعونا نمضي قدما وبفضل هذه الرجال، وتصور هذه قليلا بشكل مختلف. جيد جدا. [تصفيق] حسنا. هناك تذهب. شكرا ل- BRANSON: [غير مسموع] الحفاظ على الأرقام. DAVID J. مالان: لا، كنت قد الحفاظ على الأرقام أيضا. حسنا. عمله بشكل جيد. حسنا. لذلك دعونا نرى ما اذا كنا لا نستطيع تلخيص الآن بسرعة أكبر، وأكثر جمالا، بالضبط ما حدث للتو هنا على النحو التالي. انا ذاهب الى المضي قدما وسحب ما يصل فايرفوكس. سنقوم ربط هذه التظاهرة على الموقع الإلكتروني للدورة و. جافا هو مزعج بعض الشيء للحصول على عمل في بعض المتصفحات في هذه الأيام. لذلك إذا كنت لا تلعب مع هذا في المنزل، تدرك أنك قد تحتاج إلى استخدام فايرفوكس للحصول على انها تعمل. وما انا ذاهب الى القيام به مع هذا مظاهرة هو التالي. في الجزء السفلي، ولدي مجموعة كاملة من خيارات القائمة، بما في ذلك بداية و زر التوقف. أيضا، بوصفها جانبا، يبدو أن هناك ل خطأ في هذه البرامج، حيث كنت لا يمكن أن نرى في الواقع بداية أو وقف زر إلا إذا كنت عقد الأوامر أو البديل بالإضافة إلى والتكبير، والتي الغريب يظهر لك المزيد من الأزرار. وذلك فقط لمعلوماتك اذا كنت تلعب مع هذا في الداخل. الآن انا ذاهب الى انقر فوق ابدأ في مجرد لحظة، وبعد تحديد تأخير، مثل، 200 ميلي ثانية هنا، فقط حتى نتمكن من معرفة ما يحدث. لذلك أزعم أن هذا هو التصور من الخوارزمية الأولى هؤلاء الرجال فعل، فقاعة الفرز، حيث نحن تبادلت الناس الزوج الحكيم. والفكرة الرئيسية لهذا التصور غير أن ارتفاع القضبان يمثل حجم الرقم. وبالتالي فإن أطول شريط، و أكبر عدد. أقصر شريط، أصغر عدد. وإذا لاحظت، ونحن في طريقنا من خلال التكرار الأول من هذه الخوارزمية، مبادلة أعداد الكبيرة والصغيرة، بحيث عدد صغير يأتي أولا و عدد كبير يذهب إلى اليمين. وحالما نحصل على نهاية مجموعة العديد من أكثر من سبعة أرقام، ونحن سوف أعود إلى البداية. وتوقع هذا. في أقصى اليسار، وهذا الرجل قليلا يحدث لمبادلة إلى الجانب، وهذا يكرر العملية. الآن هذا التصور يحصل بسرعة مملة، لذلك اسمحوا لي المضي قدما ووقف ذلك، تغيير شيء من ذلك بكثير تأخير أسرع لمجرد الحصول الآن، يشعر ل هذه الخوارزمية. حتى على الرغم من أنني قد اسرعت عنه، وهذا هو مثل رفع مستوى المعالج بلدي، وشراء جهاز كمبيوتر جديد. أنا لم تتغير جذريا بلدي الخوارزمية، ولكن يمكنك أن ترى في الواقع أكثر من الواضح مع البشر، أن كبير الأرقام محتدما تصل إلى أعلى، وبأعداد صغيرة ومحتدما إلى أسفل. والآن هذا الشيء هنا فرزها. وبوصفها جانبا، في الساحات، وهناك فقط بعض مسك الدفاتر هناك ل تساعدك نحصي العديد من المقارنات، أو كم مقايضة ديك فعلا تم ذلك. حسنا، دعونا نحاول واحدة من الآخرين رأينا. اسمحوا لي انقر على فقاعة نوع هنا، و اسمحوا لي أن تختار، وهذا صفحة ويب كاملة هو القليل من عربات التي تجرها الدواب. دعونا قبول المخاطر وتشغيله مرة أخرى. هناك نذهب. لذلك دعونا نفعل اختيار نوع. أنا لا أعرف لماذا القائمة يظهر هناك. دعونا التكبير لإصلاح ذلك علة، تغيير هذا إلى 50. آه، دعونا نفعل فعلا أن أسرع بكثير. خمسة ميلي ثانية أو نحو ذلك، وابدأ. لذلك هذا هو اختيار نوع. ذلك مرة أخرى، والتفكير في ما نحن فعلت مع البشر هنا. ذهبنا من خلال مجموعة مختارة و أصغر عنصر مرة أخرى، ومرة أخرى، ومرة ​​أخرى. الآن أزعم أنه لا تزال سيئة جدا. كان لا يزال ن التربيعية، يعطي أو يأخذ، ولكنه كان، في العالم الحقيقي، قليلا أسرع، لأنني كنت أخذ الواقع خطوات أقل قليلا في كل مرة. ولكن نحن فقط نتحدث ماذا؟ ربما 40 أو نحو ذلك الحانات هنا؟ نحن لا نتحدث 40 مليون نسمة. حتى انها ليست واضحة تماما بالنسبة لي أن كان في الواقع مكاسب كبيرة. اسمحوا لي الآن العودة وتغيير لدينا خوارزمية الثالث، الذي كان حدد الإدراج الفرز. والآن حان حقا لأن عربات التي تجرها الدواب القائمة حقا لا ينبغي أن يكون هناك. لذلك نحن الآن سوف انتقل احتياطية هنا وتبدأ هذه الخوارزمية. نعيق، تشغيل وإيقاف. لذلك هذا واحد لديه نوع من نمط جميلة لذلك، حيث أننا مرة أخرى إدراج البشر، أو في هذه الحالة، والحانات في الموقع المناسب لها. وانها فعلت قبل التفت حولها. ولكن هذا واحد، أيضا، من الناحية النظرية، لا يزال ن المربعة. لذلك دعونا نرى ما اذا كنا لا نستطيع تلخيص هذه كما يلي. انا ذاهب الى المضي قدما وفقط لإعطاء لنا نوعا من وسيلة مشتركة من الحديث حول هذه الأمور، واسمحوا لي أن أعرض فقط قليلا من التدوين هنا. كنت على وشك أن ترى شيئا يسمى كبيرة O، لأنه هو حرفيا كبيرة O. وهذه هي الطريقة التي جهاز كمبيوتر عالم أو حتى الاستخدامات الرياضيات لوصف إدارة الوقت بعض الخوارزمية. كيف العديد من الخطوات التي يستغرقها فعلا؟ الآن انا ذاهب لإحراج نفسي مع الكتابة اليدوية الخاصة بي هنا في مجرد لحظة. ولكن اسمحوا لي أن تمضي قدما وأقول إن هذا سيكون يا كبير هنا. واسمحوا لي أن أعرض الآخر رمز، وهو أوميغا رأس المال. أوميغا ستكون عكس ذلك، أساسا، من O. كبيرة في حين يا كبير الوسائل، في أسوأ الحالات، وكم من الوقت قد يستغرق بعض الخوارزمية، في حيث ن، أوميغا هو الذهاب الى كم من الوقت تكون قد كان تأخذ في أفضل الأحوال. وسنرى ما نعنيه أفضل الحال في مجرد لحظة. لذلك دعونا نبدأ بشيء بسيط. اسمحوا لي أن أبدأ مع البحث الخطي. حتى لا الفرز. وسوف ندعو هذا البحث الخطي. والآن، وجعل قليلا للخروج من هذا الجدول. والآن، في حالة البحث الخطي، في أسوأ الحالات، وكيف العديد من الخطوات هي هو يذهب أن يأخذني إلى إيجاد عدد من خيار التعسفي؟ وهناك ن مجموع الأبواب أو ن مجموع الأرقام. أسوأ الحالات. كيف العديد من الخطوات أنا ذاهب لدينا ل تتخذ للعثور على رقم 50 في مجموعة ن الأبواب؟ ولماذا؟ لأنه قد يكون كل على الطريق إلى نهاية. مثل الكثير جنيفر اجه، و وكان عدد 50 all the طريق على، وذلك في أسوأ حالة البحث الخطي هو يا كبير من ن، ونحن سوف أقول. ماذا عن أفضل الأحوال، إذا كنت محظوظا حقا؟ انها مجرد الذهاب الى اتخاذ خطوة واحدة، أو عدد ثابت من الخطوات. ولذا فإننا سوف تصف بأنه 1. لذلك هذا امر جيد جدا. الآن ماذا لو فعلنا شيئا مثل البحث الثنائي؟ البحث الثنائية حتى في أسوأ الحالة، كم من الوقت استغرق؟ [VOICES فاصلة] DAVID J. مالان: وهكذا في الواقع، وأنا سمعت ذلك في الأماكن زوجين. حتى انها لتسجيل الواقع ن، يعطي أو يأخذ، لأنه كما نقسم القائمة في النصف مرة أخرى، ومرة ​​أخرى، ومرة ​​أخرى، ونحن قادرون العثور عليها، في نهاية المطاف، وقيمة، لو كان هناك، ولكن هناك كمية الصيد. ما هو افتراض أن لدينا ل أمرا مفروغا منه للبحث ثنائي؟ لا بد من فرزها. انها غير مصنفة ذلك، يمكنك تقسيم الشيء في النصف مرارا وتكرارا، وكنت يمكن أن تذهب اليسرى، ويمكنك الذهاب الحق، و يمكنك الذهاب اليمين واليسار، ولكن كنت لن تجد العنصر إذا لا يتم فرز القائمة، لأن كنت قد تفوت. لأن ارشادي الخاص بك، للذهاب ترك أو اليمين ستكون معيبة إذا كان في الواقع غير مصنفة. لذلك هناك نوع من التكاليف الخفية لاستخدام شيء من هذا القبيل. الآن، دعونا نذهب إلى الفرز لدينا خوارزميات لا تبحث - أوه، في الواقع دعونا نذهب في هذا فارغا. البحث الثنائي في أفضل الأحوال؟ كما انها 1 إذا كان يحدث لمجرد أن يكون في منتصف جدا من مجموعة، أو وسط دفتر الهاتف. الآن دعونا نفعل فقاعة الفرز. ذلك مرة أخرى، ونحن الآن ندخل في أنواع، وليس البحث. في أسوأ الحالات، لم كم عدد الخطوات التي فقاعة المطالبة نوع سيستغرق؟ ن المربعة. لذلك أنا ذاهب لرسم ذلك. أوه، يا الكتابة اليدوية تبدو أكثر سوءا عندما يكون من المتوقع أن كبير. حسنا. بحيث انها المربعة ن. وفي أفضل الأحوال من فقاعة نوع، كيف العديد من الخطوات تسير الأمور لاتخاذ؟ 1، سمعت. سرور 1: ن. DAVID J. مالان: ن، سمعت. سرور 1: 2. DAVID J. مالان: 2، سمعت. لم أسمع 3؟ حسنا. حتى لقد سمعت 1، ن 2، ولكن دعونا اختيار وبصرف النظر على الأقل أول تلك اقتراحات، 1. انها ليست غريزة سيئة، لأنه نوع من يتبع نمطا هنا. ولكن إذا كان يستغرق سوى 1 الخطوة، وكيف في يمكن العالم أزعم أن قائمة يتم فرز، لأنه إذا أنا سمحت فقط لاتخاذ الخطوة 1، وكيفية العديد من العناصر أنا في الواقع يمكن أن تحقق للتأكد؟ حسنا، فقط 1، وهو ما يعني أن هناك ن ناقص 1 العناصر التي يمكن أن يكون من النظام، وأنا مجرد الذهاب على الإيمان بعد أبحث في 1 العنصر أن يتم فرز الشيء. حتى 1 لن تصحيح هنا. الحد الأدنى لذلك، كم يمكنني أن ننظر؟ [VOICES فاصلة] DAVID J. مالان: ن ناقص 1، أو حقا، ن، لأنني بحاجة الى ان ننظر في كل عنصر للتأكد من أن انها ليست خارج الترتيب. ولكن مرة أخرى، فإننا سوف نوع من موجة لدينا اليدين في أرقام أصغر و نفترض أن، كما ن يحصل كبيرة، وانهم رتيبا على أي حال. ذلك أن فقاعة الفرز. والآن، دعونا نفعل هذه الماضيين. اختيار نوع، ومن ثم سنقوم القيام الإدراج الفرز. وبعد ذلك سوف ضربة الخاص عقول بشيء من ذلك بكثير أفضل من كل هذه. حسنا. ما هو أسوأ حالة تشغيل وقت اختيار نوع؟ سرور 4: ن المربعة. DAVID J. مالان: ن مربع، أسمع. ولكن لماذا ن التربيعية، حدسي؟ سرور 4: لأننا فقط فعل ذلك. DAVID J. مالان: لأننا فقط فعل ذلك. موافق. إجابة جيدة. ولكن حدسي، لماذا هو الاختيار نوع ن التربيعية؟ ماذا علينا أن نفعل مرارا وتكرارا؟ كان لدينا للحفاظ على المسح الضوئي من خلال، و كنت أصغر، هل أنت و أصغر، هل أنت أصغر. ومنح، كنا قادرين على اتخاذ ن الخطوات، ثم ن ناقص 1، ثم ن ناقص 2. ولكن إذا كنت نوع من إضافة تلك كل شيء، أو أن أعتبر على الإيمان بأنني قمت بإضافتها لهم حتى في وقت مبكر، والحصول على ما يقرب من ن مربع ناقص بعض الأرقام أصغر. لذلك أنا ذاهب لاستدعاء هذا ن المربعة. ولكن مع نوع التحديد في أفضل القضية، وكيف العديد من الخطوات هو عليه سيستغرق لي؟ سرور 5: [غير مسموع] DAVID J. مالان: انها للأسف لا تزال ن التربيعية، أليس كذلك؟ لأنه إذا أنا اختيار أصغر العنصر، وكان لدينا سبعة أشخاص هنا، أنا أعرف فقط، وبمجرد أن أحصل على جدا نهاية، التي وجدتها أصغر العدد، أو أينما كان وقالت انها قد تكون. ولكن كيف أجد المقبل أصغر عدد؟ يجب أن أقوم به تمريرة أخرى. حتى في أفضل الأحوال، ما هو الإدخال إلى اختيار نوع؟ انها قائمة بالفعل نوعا، رقم واحد، رقم اثنين ورقم ثلاثة، رقم أربعة. ولكن أنا جهاز كمبيوتر. أنا يمكن أن ننظر فقط في واحد شيء في وقت واحد. لا أستطيع نوعا من اتخاذ خطوة مرة أخرى مثل الإنسان والقول، أوه، هذا يبدو الصحيح. أستطيع أن الفصل في صحة فقط اختيار نوع عن طريق تحديد أصغر رقم. ولكن حتى إذا وجدت رقم واحد أول، إذا أنا لا أعرف أي شيء آخر عن أرقام أخرى، وأنا لا، كل ما أعرف أنني قد تم تسليم مجموعة أو مجموعة من الأبواب التي هي وراء الأرقام، الطريق الوحيد الذي أعرفه أن واحدا كان أصغر؟ إذا كنت تحصل على طول الطريق هنا وندرك، لعنة، بل كان واحدا أصغر. ولكن كيف يمكنني ثم تحديد أن اثنين هو أصغر القادمة؟ عن طريق القيام بنفس الكفاءة مرارا وتكرارا. حتى النهاية، مع إدخال نوع، كيف، في أسوأ الحالات، لم نقول أنه ينفذ؟ ذلك أيضا هو ن مربع. وماذا عن أفضل حال؟ سنترك ذلك على أنه التشويق. وسنقوم في ملء ذلك في المرة القادمة فارغة، ولكن أولا اسمحوا لي أن أقترح أن نقوم تفعل أفضل من الأساس كل هذه، كل الحق؟ لذلك اعتقد لنفسك ما الإدراج نوع ستكون. حسنا، هذا لم يكن مثيرة للغاية، لأنني أنا الوحيد التي شهدت التغيير. نجاح باهر. موافق. حتى هنا لدينا إلى حد ما مظاهرة مختلفة. إذا كنت تكبير هنا، سترى أن على اليسار لدينا فقاعة الفرز، في منتصف لدينا اختيار نوع، وعلى الحق الآن، لدينا شيء نحن لم ينظر في بعد دعا دمج الفرز. ولكن النظر في ما كنا تفعل هنا حتى الآن اليوم. عندما جاء جنيفر أول مرة على خشبة المسرح، ذهبنا من خلال مجموعة من الأرقام مرة أخرى، ومرة ​​أخرى، مع البحث الخطي، وحصلنا على خطي إدارة الوقت، يا كبير ن، إذا جاز التعبير. عندما ننظر الآن في الأسبوع الأول من الطبقة، وعندما كنا فرق تسد، وكان لدينا تمزيق دفتر الهاتف، وجنيفر، ونحن بشكل جماعي الاستدانة أن الفكرة الرئيسية، والتي كان ل تكرر نفسك مرارا وتكرارا من قبل رمي بعيدا إلى حد ما، ورمي بعيدا، رمي بعيدا، نصف المشكلة، أو عموما، تقسيم المشكلة إلى النصف، ثم علاج قطعة أصغر من المشكلة كما تعادل من الناحية المفاهيمية إلى أخرى، على نحو ما فعلنا جوهريا أفضل. ولكن مع فقاعة نوع، مع اختيار نوع، مع الإدراج النوع، لدينا يجوز لا يوجد مثل هذا الأفكار التي جنيفر فعلت. لدينا الكثير جدا فقط مشى ذهابا و إيابا في مجمله مجموعة من الأوقات، ونحن أنب الأمور قليلا، مبادلة في هذا النظام، وربما إدخال أو اختيار. ولكن في نهاية اليوم، فعلت الكثير من حرج المشي ذهابا وإيابا. لم نكن الاستفادة حقا شيء الذكية مثل جنيفر فعل مثل تقسيم وقهر. لذلك دمج النوع، على النقيض من ذلك، ونحن لن ترى حتى الاسبوع المقبل، انه سيكون للاستفادة من هذه الفكرة الأساسية بقسمة المدخلات، ثم خفض، ثم خفض، ومن ثم خفض. وعلى كل تكرار تلك الحلقة، فرز النصف الأيسر، والحق نصف، ثم النصف الأيسر من النصف الأيسر، والنصف الأيمن من الجهة اليسرى، ثم النصف الأيسر من النصف الأيمن، و النصف الأيمن من النصف الأيمن. وتكرار مرارا وتكرارا. لذلك عليك أن ترى هذا بصريا، ولكن هذا هو ما ينتظرنا في الأسبوع القادم. وبشكل عام، عندما نفكر قليلا بت أصعب على أي مشكلة من هذا القبيل. لقد المربعة ن على اليسار، ن مربع في الوسط، ون تسجيل ن على اليمين. ولذلك لا يوجد التشويق الخاص بك الحقيقي. سنرى لك يوم الاثنين. [تصفيق]