[عزف الموسيقى] DAVID J. مالان: هذا هو CS50. وهذا هو بداية ثلاثة أسابيع. لذلك نحن قد حصلت على الكثير من مثيرة أشياء لتغطية اليوم. وهناك الكثير من الفرص لل المتطوعين على خشبة المسرح. وفي نهاية المطاف، واليوم هو لا حول قانون على الإطلاق. لكنه حول الأفكار، و ولكن عن الخوارزميات، وبذلك الواقع مرة أخرى بعض الدروس المستفادة من الأسبوع الصفر، حيث تذكر، ونحن قدم هذا المسخ. والإلهام الاقتراض من ذلك، لبدء لحل أكثر تطورا من أي وقت مضى المشاكل حسابيا. ولكن أولا، وزوجين من الإعلانات. حتى واحد، إذا كنت ترغب في الانضمام الموظفين CS50 وزملاء الدراسة في الغداء هذا الجمعة، سواء هنا أو في كامبريدج، ونيو هافن، يرجى زيارة بالطبع ل على شبكة الإنترنت، حيث URL يمكن العثور عليها. محاضرة يوم الأربعاء سوف لن يكون هنا في ساندرز. وسوف تكون على الانترنت فقط، لذلك الاستماع في موقع CS50، و سواء هنا في كامبريدج أو نيو هافن كذلك. والمشكلة قم بتعيين اثنين هو بالفعل في يديك. إذا لم تكن قد ارتمى في ذلك، اسمحوا لي لتقديم اقتراح شديد اللهجة ذلك، خصوصا الآن، كما المشكلة تحدد مسبقا، هل حقا تريد أن تبدأ الآن، إن لم يكن اشتغل قليلا في عطلة نهاية الأسبوع أو قبل عندما يذهبون لأول مرة على الجمعة، لأنك سوف تجد أنهم ليسوا بالضرورة الحصول على أطول أو أكثر تحديا في حد ذاتها. أعتقد أنك ستجد أنه في عموما، فإنها تميل إلى اتخاذ تقريبا حول نفس المقدار من الوقت. ولكن ذلك يعتمد بالتأكيد على الطالب، وذلك يعتمد على عقلية والتي يمكنك التعامل معها. ولكن دائما، وأنت تسير لتشغيل حتى ضد بعض الجدار، وأنت تسير لضرب بعض الأخطاء، وكنت للتو لن تكون قادرة على الحصول على أكثر من ذلك في بعض نقطة. وانها ذات قيمة كبيرة لتكون قادرة على بعد خطوة، ويعود في اليوم التالي، انتقل إلى ساعات العمل، وظيفة على CS50 ناقش أو ما شابه ذلك، للحصول على الافراج الواقع. حتى أن تبقي في الاعتبار. بدءا أقرب وقت ممكن هو أفضل شيء يمكنك القيام به. حتى هنا حيث بدأنا الطبقة، في أكثر من أسبوع الصفر. ويمكن أن نحصل على المتطوعين هنا لمساعدتي في العثور ميكروفونات؟ حسنا. الوقوف بالفعل. تأتي على ما يصل. اعتقد ان هذا كيف انها الذهاب الى العمل. ما اسمك؟ ALAN إسترادا: آلان استرادا. DAVID J. مالان: آلان استرادا. تأتي على ما يصل. تشرفت بمقابلتك. ALAN استرادا: لطيف لمقابلتك. DAVID J. مالان: وكنت هنا معنا في الأسبوع الصفر، بطبيعة الحال. ALAN إسترادا: كنت. انا كنت. DAVID J. مالان: إذن هل يمكن أن تذهب إلى الأمام وإيجاد بالنسبة لنا مايك سميث، بأسرع ما يمكن؟ بأسرع ما يمكن. تمزيق حرفيا المشكلة في النصف كما كنت في حاجة إليها. ALAN إسترادا: أم. DAVID J. مالان: حرفيا تمزيق مشكلة في النصف. ALAN إسترادا: أوه. مم. جيد جدا. DAVID J. مالان: OK. جيد. شكرا. ALAN إسترادا: جيد جدا. حسنا. DAVID J. مالان: وهكذا الآن، كنت قد تتفكك عليه إلى نصف حجم المشكلة. الآن، نحن لتصل إلى ربع النهائي. أنت تدفع الانتباه إلى الجانب الذي نحن حفظ؟ [يضحك] ALAN إسترادا: نعم، أنا think-- DAVID J. مالان: ما هو أكثر قسم نحن في؟ ALAN إسترادا: الخمارات، لذلك. DAVID J. مالان: OK. لكن مايك سميث يجري ليكون بعد الخمارات. هكذا-- [يضحك] حسنا. ALAN إسترادا: أين نحن تبحث؟ DAVID J. مالان: مايك سميث. ALAN إسترادا: مايك سميث. DAVID J. مالان: الآن، نحن في العمليات الجراحية. الآن، والأطباء. Now-- ALAN إسترادا: Let's- دعنا نذهب مع ريال مدريد. ريال مدريد. DAVID J. مالان: ريال. حسنا. اذا كنت بحاجة الى ريال مدريد. الآن، الطريق الذي هو مايك سميث؟ ALAN إسترادا: بهذه الطريقة. DAVID J. مالان: ما هي الطريقة؟ ALAN إسترادا: انتظر. M is-- أليس كذلك؟ بدأنا with-- DAVID J. مالان: نعم. كنت تركوا. لديك حق. ALAN إسترادا: نعم. DAVID J. مالان: في ذلك مايك هنا. ALAN إسترادا: ماذا؟ [يضحك] سيئة سبيل المثال، والرجال. آسف. DAVID J. مالان: هذا سيعلم أنت للقفز من مقعده الخاص بك. ALAN إسترادا: أوه. اه. فهمتك. فهمتك. اه. اه. هذا is-- موافق، وحصلت لك. سميث هنا؟ DAVID J. مالان: سميث، شكرا لك. ولذا فإنني سوف تبقى تبحث حتى سميث؟ ALAN إسترادا: أوه، نعم. لا لا لا. اوه لا. هذا لي. DAVID J. مالان: أوه، كنت حصلت سميث. حسنا. ALAN إسترادا: نعم، أنا حصل سميث هنا. آسف شباب. اعتقدت Michael-- نحن كانوا يبحثون عن مايكل. آسف. DAVID J. مالان: لا بأس. كل الحق، والآن نحن في Paccini وأولاده. ALAN إسترادا: Paccini والأبناء. DAVID J. مالان: أنت فقط وأنا في في هذا الشأن. حسنا. تجدنا مايك سميث. سميث. ALAN إسترادا: سميث. DAVID J. مالان: سميث. نحن في R للقمامة. ALAN إسترادا: القمامة. اه. هذا يحدث لبعض الوقت. [يضحك] DAVID J. مالان: أحذية. نحن في الأحذية. ALAN إسترادا: نحن الآن gonna-- DAVID J. مالان: نيس. ALAN إسترادا: Which-- [يضحك] أوه، هذا شيء عظيم. [يضحك] DAVID J. مالان: لا بأس. ALAN إسترادا: أوه، هذا أمر جيد. أنا لا أعتقد أنني ذاهب ل لدينا رفاقا PSAT بعد ذلك. DAVID J. مالان: جيد. الرياضية. ALAN إسترادا: الرياضية. أم، L، M، N، O، P. DAVID J. مالان: OK. لذلك دعونا المسيل للدموع في هذا الشوط. كل شيء على مايرام. هذا ينتهي سيئة على أي حال، لأن مايك ويل سميث لن يكون في الصفحات الصفراء. ALAN إسترادا: فصيل عبد الواحد. DAVID J. مالان: لا، لا بأس. ولكن دعونا نتظاهر مثل وقال انه على هذه الصفحة. وحتى الآن، وكنت قد تتفكك مشكلة أسفل لصفحة واحدة، ووجدنا مايك سميث. [هتاف] حسنا شكرا لك. حسنا. كان ذلك رائعا. ولكنه كان لا يزال أسرع من البحث الخطي، حيث نبدأ في بداية الكتاب، ونحن نمضي في طريقنا من اليسار إلى اليمين، في نهاية المطاف يبحث عن مايك سميث. وهكذا، إذا كان الكتاب الهاتف كان ربما 1000 صفحات، ربما كان قد اتخذ لنا 10 أو نحو ذلك الدموع الصفحة. ولكنك قد الاستدانة تطرق افتراض خلال كل ذلك، وهو ما يعني ان الكتاب الهاتف في وقت مبكر كان ماذا؟ الحضور: الترتيب. DAVID J. مالان: هو مرتبة و. الصحيح؟ لقد فرزها حسب الترتيب الأبجدي، لذلك أن جميع تلك الأسماء وأرقام يتم فرز من A إلى Z، وو أبجديا بينهما. ولكن اليوم، ونحن نسأل الآن السؤال، حسنا، كيف فعلت فيريزون أو الهاتف شركة الحصول عليه في تلك الحالة؟ لأنه شيء واحد للاستفادة هذا الافتراض، وبالتالي، حل مشكلة مع خوارزمية أكثر كفاءة. لكننا أبدا حقا طلب في الأسبوع الصفر، حسنا، كم تكبد هي تكلفة فيريزون أو شخص آخر للحصول على هذا الكتاب الهاتف من أجل فرزها؟ الصحيح؟ لا يهم إذا يبحث حتى مايك سميث هو بسرعة فائقة، إذا كان يأخذك العام لفرز الصفحات في البداية. الصحيح؟ بالاضافة الى انك قد نخل فقط من خلال دليل الهاتف العشوائية، إذا أريد لها أن تكون فائقة تكلفة لترتيب هذا الامر. إذا كان الأمر كذلك فإننا يمكن أن يكون متطوع آخر. دعونا نلقي نظرة هنا في كيف يمكننا might-- هيا up-- كيف قد نذهب حول فرز هذه. وإذا استطاع الأردن الواقع الانضمام إلينا هنا على خشبة المسرح. هيا حتى لمجرد لحظة. ما اسمك؟ كارولين: كارولين. DAVID J. مالان: كارولين، وتأتي على ما يصل. وعليك أن تكون انضم لي من قبل والاردن هنا. كارولين، وشكرا لكم. حسنا. ذلك ما لدينا هنا ل كارولين هو 26 كتابا الزرقاء يستخدم لإدارة FAS بعض الامتحانات النهائية. هذه هي الحصول من الصعب العثور على، ولكن ما قمنا به مسبقا هو أننا قد وضعت اسم شخص ما على واجهة كل من هذه، ولكن لدينا أبقاها بسيطة من قبل ثم اخماد الأسماء الكاملة. لذلك نحن من شأنه أن يضع الشخص مع اسم L، D، J، B، على طول الطريق من A إلى Z، ولكنهم في ترتيب عشوائي. وحتى لو تفضلتم، والحديث الخاص بك الطريق من خلال المشكلة كما كنت تفعل ذلك، يمكنك ان تمضي قدما و فرز هذه بالنسبة لنا، من الألف إلى الياء الحضور: حسنا، L هو مثل، والوسط. C هو بداية. B. J قبل L. B، Q. DAVID J. مالان: عقد أن فكرت لثانية واحدة. لأن خلاف ذلك، وهذا هو فقط مثيرة للاهتمام بالنسبة لك، لي، والأردن. هناك نذهب. الحضور: (غير مسموع). R. DAVID J. مالان: OK. ماذا تفعل؟ كارولين: M يأتي بعد O. DAVID J. مالان: OK. كارولين: O. DAVID J. مالان: O، جيد. كارولين: E. DAVID J. مالان: E، F. نعم. كارولين: T، U، V. DAVID J. مالان: V، T، U، V. لذلك يبدو أنك كنت making-- الاستمرار. يبدو أنك نحرز كومة كبيرة هنا، ونوع من كومة كبيرة هناك. حتى النصف الأول من الأبجدية، النصف الثاني من الأبجدية. حسنا. جيد. نوع من تقسيم المشكلة إلى قسمين. M، N، X. نعم. كارولين: K. DAVID J. مالان: OK. K. لذا كنت نوع من اختيار واحدا تلو الآخر، وضعه إما اليمين أو اليسار، أو Z يجري على الأرض. حسنا. كارولين: Z يجري على الأرض. DAVID J. مالان: OK. Y يجري على الأرض. الآن يمكننا وضع X. كارولين: G. DAVID J. مالان: الذهاب اليسار G. S يجري الصحيح. كل الحق، A تسير على طول الطريق اليسار. كارولين: A، B، C، D. DAVID J. مالان: الآن، وحسن. لدينا A، B، C. W في الذهاب الى هناك. كل الحق، T. كارولين: H، I، J. DAVID J. مالان: H، I، J. جيد. كارولين: في الوسط، أنا gonna-- DAVID J. مالان: OK. وحتى الآن، ونحن في طريقنا إلى نوع من دمج هذه الأكوام المختلفة. لذلك من خلال C، ثم أرى D، و E، F و، وG، H و، وI. نيس. J، K. وبعد ذلك، وهذا هو كومة رأسا على عقب، ولكن هذا موافق. بالتأكيد. يمكننا خفض بعض الزوايا. حسنا. ومن ثم نحتاج W، X، Y، Z. كارولين: نعم. DAVID J. مالان: ممتاز. لذلك شكرا جزيلا لك كارولين لفرز هذه. [هتاف] شكرا. شكرا جزيلا. حتى الآن دعونا نتأمل لحظة كيف ذهب كارولين عن فعل ذلك، وبالضبط نحن تمكنوا to-- كيف يمكننا كانت قادرة على حل هذه عندما كنا مجرد مشكلة نظرا مجموعة كاملة من المدخلات العشوائية. حسنا، يبدو أن هناك كان نوعا من النظام هناك؟ الصحيح. حتى الرسائل السابقة في الأبجدية، وقالت انها كان وضع إلى اليسار، و رسائل في وقت لاحق في الأبجدية، كانت تضع في الحق. وحالما وجدت بعض الحروف الداني، منها التي تذهب بجوار بعضها البعض، فإنها ستضع تلك الموجودة في النظام. ولذا فإننا النوع من كان هؤلاء الصغيرة أكوام من المدخلات التي تم فرزها الحدوث. وحتى هذا تماما مثل ما ومعظمنا يفعل البشر. كنا النوع من التدقيق من خلال ذلك، وسيكون لدينا نوع من الآلية. ولكن قد يكون من الصعب الكتابة عليه في صيغة في حد ذاته. ورأى أكثر قليلا العضوية من ذلك. لذلك دعونا نرى ما اذا كنا نستطيع الآن ملزمة المشكلة مع عدد أقل من المدخلات. بدلا من 26، دعنا نفعل شيئا أقل بكثير مع أن أقول، سبعة، وراء هذه الأبواب، إذا جاز التعبير. هل هناك فقط سبعة أرقام؟ وإذا كان الهدف الآن في اليد لإيجاد قيمة، دعونا نرى كيف بكفاءة يمكننا أن نذهب عن القيام بذلك. ودعونا نرى ما اذا كان يمكننا الآن البدء في تطبيق بعض الأرقام، أو بعض الصيغ التي لوصف كفاءة دفتر الهاتف لدينا الخوارزمية، لدينا خوارزمية كتاب الامتحان، و بشكل عام، وإيجاد المعلومات. لذلك لهذا، اسمحوا لي أن المضي قدما، و على شاشة تعمل باللمس أكثر من هنا، طرح متصفح الإنترنت الذي لديه بالضبط هذه الأبواب السبعة. وإذا لم نتمكن من الحصول على واحدة أخرى التطوع لتأتي على أكثر من هنا، لقد وضعت هذه نفس الأبواب أكثر من هنا. المتطوعين سريع. هذه العروض احدا-- تسير إلى أسرع وأسرع الآن. تعال للأسفل. ما اسمك؟ TREVOR: تريفور. DAVID J. مالان: تريفور؟ كل الحق، تريفور، هيا إلى أسفل. لذلك فقد تطوع تريفور هنا ل القيام مشكلة مماثلة، ولكن واحد وهذا أضيق نطاقا، والتي يجري للسماح لنا في محاولة لإضفاء الطابع الرسمي الآن عملية الفرز هذه الأرقام. حتى تريفور، لطيف لمقابلتك. حتى هنا هو مجموعة، وذلك ل الكلام، وقائمة من سبعة أبواب. المضي قدما وتجد لنا رقم 50. ثم بعد وقوعها، تقول لنا كيف كنت وجدت. يجب be-- كل الحق. نعم، وهذا هو واحد هنا؟ اه اوه. حسنا. نقرت أن واحدا. جيد. و جيد. الآن يمكنك النقر أن واحدا. واسمحوا لي أن أقدم لكم الميكروفون، بحيث يكون لديك في لحظة فقط. المضي قدما وانقر على المجاور الذي تنوي. نعم جيد. TREVOR: هل يمكنني unclick الباب؟ DAVID J. مالان: لا، لا يمكنك unclick. TREVOR: OK. هذا. DAVID J. مالان: أين تريد أن تذهب؟ أي واحد؟ TREVOR: هذا واحد. DAVID J. مالان: رقم TREVOR: OK. هذا. DAVID J. مالان: نعم. كان ذلك جيدا. حسنا. فما كان خوارزمية أو الإجراء للقيام بذلك، تريفور؟ TREVOR: أنا فقط ذهبت من خلال الأبواب حتى وجدت 50. DAVID J. مالان: OK. خوارزمية ممتازة. لذلك فلا بأس. لأنه في الواقع، إذا أنا تكشف ما خلف هذه الأبواب الأخريين، ما سنجد هنا هو أن ليس لدينا سوى إدخال عشوائي. بحيث كان في الواقع كما جيدة كما يمكن أن تحصل. وفي الواقع، كنت حصلت على أفضل من البحث باستفاضة في مجموعة كاملة، لأنه يمكن أن يكون حقا غير محظوظين إذا كنت قد تصل إلى العدد 50 في الباب الأخير للغاية. ولكن ماذا لو أننا بدلا من ذلك أعطاك هذا الافتراض. افترض نوع جميعا هذه الأبواب حولها، بحيث يكون لديك ل أرقام فرز هذه المرة، ولكن هذه المرة انها فعلا وdifferent-- هذا الوقت، انها مرتبة في الواقع بالنسبة لك. والآن الهدف في متناول اليد هو ضرب رقم 50. TREVOR: OK. DAVID J. مالان: ما هو خوارزمية الخاص بك سيكون؟ TREVOR: حسنا، إذا كان مرتبة، فإنه إما الذهاب لbe-- إذا الأكبر لأكبر، تنازلي، فإنه سوف يكون أول واحد، أو إذا كان العكس، وسوف يكون آخر واحد. ولذا فإنني سوف مجرد استغلال هذا الباب، و ثم فقط اضغط على الباب الأخير. DAVID J. مالان: ممتاز. حسنا. لذلك وجدنا عدد 50. ذلك في أقرب وقت كما كنت أعرف تم فرزها، ونحن كانوا قادرين على الاستفادة من هذا الافتراض. حتى انهم مثل الكثير على سبيل المثال دفتر الهاتف. بأسرع ما لديك، حتى مع مشكلة صغيرة مثل هذه، إسهاماتكم مرتبة مسبقا، ما في وسعنا تجد في الواقع قيمة يمكن القول أكثر كفاءة. وأنا لا أقول لكم إذا كان فرز الصغيرة الى الكبيرة، أو كبيرة للمشاريع الصغيرة، وهكذا كان من المعقول جدا أن تبدأ في نهاية واحدة أو أخرى لتجد في الواقع أن القيمة المستهدفة. لذا شكرا لتريفور كذلك. وسوف propose-- القيام به بشكل جيد. لدينا القليل من مقطع، في الواقع، أن من بين اللحظات المفضلة لدينا في CS50، حيث في بعض الأحيان هذه العروض لا تذهب تماما وفقا للخطة الموضوعة. والآن في الواقع الحق، وأنا سحب ما يصل الواجهة غير صحيح مع الذي لاستخدام شاشة تعمل باللمس. لذلك كان هذا خطأي هناك. ولذلك فإن هذا سيجعل ل مقطع العام المقبل كما لماذا كنت النقر على الشاشة الخاصة. ولكن دعونا نلقي نظرة سريعة في ما حدث العام الماضي مع جاي، الذي جاء، والكثير مثل تريفور هنا، تطوع، وهذا مقطع قصير، سترى كيف هذا العرض نفسه ليس تماما كشف نفس الدروس المستفادة. [تشغيل الفيديو] -جميع أريدك أن نفعله الآن هو للعثور بالنسبة لي، وبالنسبة لنا، حقا، عدد 50 خطوة واحدة في وقت واحد. -THE عدد 50؟ -THE عدد 50. ويمكنك الكشف عما هو وراء كل من هذه الأبواب ببساطة عن طريق لمسها بأصابعك. عليك اللعنة. [يضحك] [END قراءة] DAVID J. مالان: ولهذا سارت على ما يرام. كانت تلك الأبواب التي لم يتم فرزها. وجاي، بطبيعة الحال، وجدت كل شيء بسرعة كبيرة جدا. لم تريفور بعمل أفضل بكثير من حيث لحظة قابلة للتعليم، إذا جاز التعبير، وهذا العام في يستغرق وقتا أطول للعثور عليه. وبطبيعة الحال، ثم أعطينا جاي على فرصة ثانية، حيث قمنا بفرز الأبواب، تماما كما فعلنا لتريفور، وفعل تريفور السوبر جيدا هذه المرة. ولكن جاي فعل ذلك نصف في أسرع وقت. [تشغيل الفيديو] -THE الهدف الآن هو أيضا تجدنا عدد 50، ولكنها تفعل ذلك حسابيا، و تخبرنا كيف وأنت تسير حول هذا الموضوع. -حسنا. -و إذا وجدت أنه، عليك أن تبقي الفيلم. إذا كنت لا تجد ذلك، ليعيدها. -man. أوه! - [غير مسموع] OK. لذلك أنا ذاهب للتحقق الغايات أولا لتحديد ما إذا there's-- أوه. [تصفيق] [END قراءة] DAVID J. مالان: OK. حتى فرز الأبواب بشكل واضح يؤدي إلى زيادة الكفاءة. وهكذا، أسرع مرتين ما قصدته هناك. وهكذا حصلت جاي محظوظا في كل الأوقات. وحصل أيضا محظوظا في ذلك الماضي العام، وأمرت بعض أقراص بلو راي لإعطاء فعلا. أنا آسف لهذا العام، ونحن لم يكن لديك واحدة، تريفور. ولكن الأفضل من ذلك كان قبل بضع سنوات. والبعض منكم قد تعرف هذا زميل، شون، الذي عندما كان في CS50، وطعن مع الدقة نفس المشكلة، وإن كان ذلك في SD، كما سترى قريبا، مرة في اليوم. وسوف تجد أن لا فعل فقط انه يستغرق وقتا أطول قليلا من جاي، لفترة أطول قليلا من تريفور، كان عليه في الواقع هذه الفرصة الرائعة لإشراك الجميع تقريبا في الحشد على غرار السعر مناسبا، وتشجيع له للعثور على عدد كنا نسعى. دعونا. نلقي نظرة سريعة. [تشغيل الفيديو] -حسنا. لذلك مهمتك هنا، شون، هو ما يلي. لقد خفية وراء هذه أبواب الرقم سبعة. لكن مطوي بعيدا في بعض هذه الأبواب كما هي أيضا الأرقام السلبية الأخرى. وهدفك هو التفكير هذا الصف العلوي من الأرقام كمجرد صفيف، أو مجرد تسلسل قطعة من الورق مع الأرقام التي تقف وراءها. وهدفك هو، فقط باستخدام أعلى مجموعة هنا، تجد لي الرقم سبعة. ونحن بعد ذلك يذهب إلى نقد كيف تذهب عن القيام بذلك. -حسنا. -Find لنا رقم سبعة، من فضلك. لا. خمسة و 19 و 13. [يضحك] انها ليست مسألة خدعة. واحدة. [يضحك] في هذه المرحلة، والنتيجة ليست غاية جيدة، لذلك قد واصلتم بالإضافة الذهاب. ثلاثة. [يضحك] تابع. بصراحة، لا يسعني إلا أن أتساءل ما كنت حتى التفكير، so-- [يضحك] فقط في الصف العلوي، لذلك كنت قد حصلت على ثلاثة اليسار. لذلك تجد لي سبعة. [يضحك] 17. سبعة. [تصفيق] حسنا. [END قراءة] DAVID J. مالان: حتى يمكن لنا مشاهدة هذه طوال اليوم. وبطبيعة الحال، بعض العروض هذا العام ربما سينتهي الآن حتى في القادم الفيديو العام كذلك. حتى الآن دعونا الواقع التركيز على خوارزميات هنا، ونرى اذا كنا لا يمكن نبدأ الآن لإضفاء الطابع الرسمي كيف يمكننا التوجه نحو الحصول على البيانات المتوفرة لدينا في هذه الحالة وهذا ما فرزها، حتى أنه في نهاية المطاف، ويمكننا فعلا بحث عنها بشكل أكثر كفاءة. وعلى الرغم من أننا ذاهبون استخدام مجموعات البيانات صغيرة إلى حد ما، مثل نحن ثمانية أرقام لدينا هنا على متن الطائرة، في نهاية المطاف يمكن أن تنطبق هذه الأفكار نفسها إلى 1000 المدخلات، مليون المدخلات، 4 مليارات المدخلات، لأن الخوارزميات ستكون الأساس نفسه. وهكذا هذا هو موقفنا الأخير فرصة للمتطوعين اليوم، ولكن ربما الأكثر انخراطا واحد، التي نحتاج ثمانية متطوعين من أجل التوصل إلى والسير بنا من خلال عملية الفرز ما قريبا يكون على هذه الموسيقى تقف هنا. اسمحوا لي أن أبدأ هنا مرة أخرى. حتى واحد في المنطقة الخضراء turquoise-- هو؟ هل بارتكاب؟ اثنين. تعال للأسفل. حسنا. ثلاثة. أربعة. السماح me-- OK، خمسة. كنت ترشيحهم من قبل صديقك. ستة، سبعة، وثمانية. تأتي على ما يصل. حسنا. شكرا جزيلا. تأتي على ما يصل. تأتي على ما يصل. حسنا. ذلك ما لدينا here-- وهذا من بين تلك الأكثر حرج، لأن هذا سوف تتطلب منك النكتة لي قليلا من الوقت. يجب أن تكون رقم واحد. ما اسمك؟ عنان: عنان. DAVID J. مالان: عنان. ديفيد. ما اسمك؟ يوسف: يوسف. DAVID J. مالان: يوسف كنت رقم اثنين. سيرينا: سيرينا، رقم ثلاثة. ستيفان، رقم أربعة. CYNTHIA: سينثيا. DAVID J. مالان: سينثيا، رقم خمسة. (غير مسموع) DAVID J. مالان: (غير مسموع). ديفيد، رقم ستة. مات: مات. DAVID J. مالان: مات الرقم سبعة. و؟ WAVERLY: يفرلي. DAVID J. مالان: يفرلي، رقم ثمانية. حسنا. إذا كنت could-- يصيح. إذا كنت فقط، كما لديك التحدي الأول، هناك هي ثمانية وتقف والموسيقى تواجه هنا للجمهور. إذا كنت قد وضعت الأرقام الخاصة بك على هذه الموسيقى يقف في مثل هذه الطريقة أنهم يصطف مع نفس الأرقام على لوحة. وهكذا جعل أنفسكم تبدو مثل هذا من قبل وضع الأرقام الخاصة بك على هذه الموسيقى تقف هنا. ممتاز حتى الآن. ممتاز. حسنا. وحتى الآن، ونحن في طريقنا لمطالبة السؤال في عدة طرق مختلفة. كيف يمكن أن نذهب حول فرز هؤلاء الناس هنا؟ لأنه كان لدينا عدد قليل من النهج في وقت سابق، حيث كنا نوع من جعل دلوين مختلفة. ثم كنا عموما التفكيك الأشياء معا. في أقرب وقت كما رأينا رقمين التي تنتمي معا، وضعنا لهم معا. رسالتين التي تنتمي معا. ولكن دعونا نرى ما اذا كنا لا يمكن إضفاء الطابع الرسمي على هذا، حتى يكون لدينا في نهاية المطاف بعض الزائفة رمز شئت، والتي يمكنك حل هذه المشاكل. وحتى الآن، وأنا أبحث خارج في هذه الأرقام هنا. وأرى في مجمله مجموعة من الأخطاء. في النهاية، أريد واحدة على اليسار وثمانية على اليمين. وهكذا أنا أبحث في هذين، أربعة واثنين. وما هي المشكلة، من الواضح؟ نعم. هكذا. ومن الواضح أن اثنين من يأتي قبل أربعة، لذلك أنت تعرف لماذا؟ اسمحوا لي أولا أن تتخذ نهجا الجشع، اذا صح التعبير، والكثير مشكلة مثل تعيين احدا-- إذا كنت تذكر من الإصدار القياسي من مشكلة مجموعة واحدة، حيث أنا فقط حل المشكلة محليا هذا صحيح هنا أمامي ونرى أين يقودني. حسنا. حتى اثنين وأربعة، واسمحوا لي ان اذهب قبل وبعد مبادلة لكم اثنين. إذا كنت تستطيع التحرك جسديا أنفسكم والورق، يبدو لي أن حصلت على قائمة في حالة أفضل. الآن، انهم جيدة. انا ذاهب للمضي قدما، أربعة وستة، تبدو جيدة. ليست مشكلة. ستة وثمانية، OK. ثمانية واحد، مشكلة أخرى. لأن ما هو صحيح حوالي ثمانية واحد؟ واحد يأتي قبل ثمانية، وذلك ما ينبغي أن نفعله؟ دعونا مبادلة هذين. واحد وثمانية. والآن، انا ذاهب الى الاستمرار. انا ذاهب للحفاظ على استشراف المستقبل. ودعونا نرى ما سيحدث. ثمانية وثلاثة من بطبيعة الحال، للخروج من النظام. دعونا المبادلة. ثمانية وسبعة، بطبيعة الحال. من النظام. دعونا المبادلة. ثمانية وخمسة، وبطبيعة الحال، دعونا المبادلة. حسنا. يتم فرز القائمة. نعم؟ OK، من الواضح أن لا. ولكن من الأفضل قليلا، أليس كذلك؟ لأن إشعار ما حدث. في كل مرة أجرينا المبادلة أصغر عدد النوع من يسيل بهذه الطريقة، وعدد أكبر يسيل بهذه الطريقة، أو أننا سوف بدء قائلا فقاعات ل اليسار أو فقاعات إلى اليمين. الآن، فإنه لا يكفي، لأن في أحسن الأحوال قد عدد تحركت بقعة واحدة إلى الأمام، أو في أسوأ الأحوال، عدد قد يكون انتقل بقعة واحدة أبعد من ذلك. حتى تعرف ما، وهذا النوع من عملت بشكل جيد جدا حتى الآن. اسمحوا لي انها مجرد محاولة مرة أخرى. اثنين وأربعة، وانهم موافق. أربعة وستة، وانهم موافق. ستة واحد، خارج الترتيب. لذلك دعونا مبادلة لكم اثنين. والآن، لاحظ للمشكلة بدءا من الحصول على أفضل قليلا مرة أخرى. ستة وثلاثة، خارج الترتيب. دعونا مبادلة لكم اثنين. ستة وسبعة، كنت جيدة. سبعة وخمسة، بطبيعة الحال، للخروج من النظام. سبعة وثمانية في النظام. والآن، وأنا قد تحتاج إلى القيام بذلك عدة مرات. وفي الواقع، أعتقد أن لأنفسكم ربما كم مرة الحد الأقصى قد لدي على المشي ذهابا وإيابا؟ سوف نعود إلى ذلك. حتى اثنين وأربعة لا تزال موافق. أربعة واحد، كلا. لذا، دعونا المبادلة. ومرة أخرى، لاحظ بصريا واحد هو نوع من السطح إلى اليسار، حيث يجب أن تكون. أربعة وثلاثة المبادلة. أربعة وستة. ستة وخمسة المبادلة. ستة وسبعة. سبعة وثمانية جيدة. جيد. نحن نحصل على أفضل. لذلك دعونا نرى. الآن، لدينا اثنين واحد. وبطبيعة الحال، مبادلة. اثنين وثلاثة، وثلاثة وأربعة، وأربعة و خمسة وستة وسبعة، السابع والثامن. جيد. وأنت تعرف لماذا؟ لأنني تغييرا واحدا هناك، اسمحوا لي أن تفعل الاختيار التعقل واحد. اسمحوا لي أن يذهب كل في طريقه العودة إلى البداية. حسنا. واحد، two-- نعم، ترى؟ شيئا ما كان خطأ. ثلاثة، أربعة، خمسة، ستة، سبعة، ثمانية. وفي هذا المرور الماضي، هي كنت مرتاحا مع بلدي الآن مدعية يتم فرز ذلك؟ حسنا. بصريا، وهذا صحيح تماما. ولكن وظيفيا، ما أيضا لم يحدث فقط في هذا الممر الأخير الذي يسمح لك للتأكد من أن هذه القائمة هي في الواقع مرتبة؟ ماذا أفعل أو لا تفعل هذا المرور الماضي؟ الحضور: لم تكن هناك تغييرات. DAVID J. مالان: عذرا؟ الجمهور: لا تغييرات. DAVID J. مالان: كانت هناك أية تغييرات. لذلك سيكون من الغباء لي ل فعل ذلك الخوارزمية نفسها مرة أخرى إذا لم تقم بإجراء أية التغييرات في المرة الأولى. والدولة لم يتغير. بالتأكيد، أنا لا أذهب إلى جعل أي تغيير للمرة الثانية. وهكذا، انها آمنة الآن أن أقول، يتم فرز القائمة. والواقع، وهذا هو الآن شيء سنقوم عموما الدعوة من نوع فقاعة، حيث زوجيا، يمكنك تصحيح الأخطاء مرة أخرى، ومرة أخرى، ومرة ​​أخرى، وكنت الاستمرار ذهابا وإيابا، وذهابا وإيابا، حتى جعل جود مثل هذه المقايضات، وعند هذه النقطة يمكنك أن تكون على ثقة، نعم، وأنا الانتهاء من إصلاح جميع الأخطاء. دعونا إعادة تعيين ومحاولة مقاربة أخرى. إذا يا رفاق يمكن أن تذهب مرة أخرى إلى النظام الذي كان قبل لحظة، التي بدت مثل هذا. الآن، دعونا نلقي النهج ل أكثر قليلا مثل كتاب الامتحان، حيث كنا باستمرار اختيار حرف من الأبجدية أننا نوع من أراد للتعامل مع القادم. ربما كان بريد إلكتروني عالية، مثل A، أو بريد إلكتروني Z. منخفض لذلك الجميع مرة أخرى في هذا النظام. والآن اسمحوا لي أن تفعل هذا. دعونا نرى أنا أعرف أن لدي ثمانية أرقام هنا. انا ذاهب الى المضي قدما و ما عليك سوى اختيار عمدا أصغر العناصر. الصحيح؟ هذا يبدو بديهية جدا. لماذا لا أجد أصغر عنصر، ووضعها حيث ينتمي، ثم الحصول على أصغر عنصر المقبل، وطرح ذلك المكان الذي ينتمي إليه، ومجرد تكرار. لأن حدسي، التي يجب أن تعمل أيضا. حتى أربعة، وهذا عدد قليل جدا. أنا ذاهب لنتذكر فيها هذا. إنتظر دقيقه. الثاني هو أصغر. اسمحوا لي أن أتذكر الآن حيث اثنين هو، ونسيان الأربعة. نحن سنتعامل مع ذلك لاحقا. ستة، أنا غير مهتم. ثمانية، وأنا لست مهتما. واحد هو رقم هاتفي صغيرة جديدة. لذلك أنا ذاهب لنتذكر فيها واحد هو. ثلاثة، ليست مهتمة. سبعة، ليست مهتمة. خمسة، ليست مهتمة. ذلك دون السقوط المرحلة هذا العام، انا ذاهب الى الاستيلاء على عدد احدا-- وماذا كان اسمك مرة أخرى؟ عنان: عنان. DAVID J. مالان: عنان. وإذا كنت قد ينضم لي في في بداية القائمة، دعونا نضع لك أين كنت تنتمي. Unfortunately-- ما اسمك؟ STEFAN: ستيفان. DAVID J. مالان: ستيفان هو في الطريق. حتى قبل ستيفان يحل هذا المشكلة، ماذا علينا أن نفعل؟ ماذا نفعل مع ستيفان؟ الحضور: (غير مسموع). DAVID J. مالان: OK. حتى نتمكن من فعل ذلك. يمكننا أن نوعا من اتخاذ ستيفان وله أربعة، ومجرد وضعها في متغير وعقد لذلك ل بعض مقدار الوقت، مما يجعل مجالا لرقم واحد. وهذا ليس سيئا. ويمكنني أن أقترح، لماذا لا نحن مجرد وضع ستيفان هنا؟ لماذا هذا قد تنتهك واحدة من الأفكار بدأنا الحديث عن المرة السابقة، في الأسبوع الماضي؟ نعم؟ الحضور: (غير مسموع). DAVID J. مالان: لا يوجد أي مؤشر لذلك. إذا كنت تفكر في ذلك، في الواقع، بوصفه مجموعة، وهذا هو مثل واحد سلبي، لذلك ليس هناك ذاكرة الواقع هنا إذا كان هذا هو في الواقع مجموعة، كما أعلنا الأسبوع الماضي في محاضرة. لذلك لا ينبغي لنا أن نفعل ذلك. ونحن قد تخزينه في متغير. أو أنت تعرف لماذا؟ سمعت شخص آخر تشير إلى ذلك. ماذا يمكن أن نفعل مع ستيفان؟ لماذا لا يتم فقط إقصائه و وضعه فوق، حيث كان رقم واحد. حتى إذا كنت تريد أن تذهب إلى هناك. والواقع، وهذا هو حل جيد جدا. الآن من ناحية، لقد النوع من جعل المشكلة أكثر سوءا. أربعة هو الآن بعيدا من حيث ينبغي أن يكون. وينبغي أن يكون نحو هذا الشوط. ولكن هل تعرف لماذا؟ كان يمكن أن يكون أن سوء الحظ. ربما كان عدد ثمانية هنا. وهكذا، ربما لو كنا وقد حصلت محظوظ، ودفعت ثمانية أقرب إلى النهاية. وذلك في نهاية اليوم، انها نوع من جميع المتوسطات. نحن لسنا بحاجة لرعاية حوالي أربعة. كل ما يهمني الآن هو اختيار أصغر عنصر. والآن، ما أنا ذاهب ل القيام به هو نسيان رقم واحد بشكل دائم، لأنني أعرف يتم فرز الآن قائمة ورائي. لذلك كانت قائمتي سابقا حجم الثمانية. الآن، انها من حجم سبعة. ذلك هو الحصول على مشكلتي أصغر، وإن كان ذلك خطيا. وحتى الآن، وانا ذاهب لتحديد أصغر عنصر الحالي، وهما. ستة، ثمانية، أربعة، ثلاثة، سبعة، خمسة. وهذا هو أصغر عنصر. ذلك ما أنا ذاهب الى القيام به with-- ما كان اسمك مرة أخرى؟ يوسف: يوسف. DAVID J. مالان: جوزيف؟ ونحن في طريقنا لمغادرة يوسف في المكان. الآن، انا ذاهب الى التظاهر أن هؤلاء الرجال are-- جيدا، وأنا أعلم أن هذين يتم فرز بالفعل. دعونا نركز الآن على تبقى قائمة. ستة هو أصغر الحالي. ثمانية هو أكبر. أربعة هي الآن أصغر الحالي. ثلاثة هي الآن أصغر الحالي. وحتى الآن، وانا ذاهب لتحديد ثلاثة، الذين is-- ما اسمك مرة أخرى؟ سيرينا: سيرينا. DAVID J. مالان: سيرينا، إذا كنت تستطيع الاستيلاء على رقمك وتبادل with-- KALSANG: Kalsang. DAVID J. مالان: Kalsang. هيا إلى الوراء، ونحن الذهاب لمبادلة هذين. والآن، دعونا نضع هذا على الطيار الآلي. انا ذاهب الى الذهاب وترك الأمر ليا رفاق لتحديد العناصر التالية أصغر. كميت، كميت، كميت، كميت. رقم أربعة، ماذا يجب ان تفعل؟ ممتاز. الآن، وانا ذاهب لجعل مسار آخر. كميت، كميت، كميت، كميت. أرى خمسة هو أصغر المقبل. الآن، وانا ذاهب اتخاذ مسار آخر. كميت، كميت، كميت، كميت. ستة هو أصغر. جيد. سبعة هو أصغر. لا تغيير. ثمانية هو أصغر. فعله. وذلك ما فعلناه فقط عن طريق تكراري اختيار عنصر واحد تلو الآخر تم تنفيذ شيء نحن الذهاب إلى إضفاء الطابع الرسمي على النحو اختيار نوع. وانها ربما بساطة لشرح، في هذا حرفيا كل ما تريد القيام به هو الحفاظ فقط ذهابا وإيابا عبر قائمة اختيار، أصغر عنصر المقبل، حتى الانتهاء من ذلك. لذلك فمن أبسط، وربما حدسي، من الماضي. دعونا نحاول واحد آخر واحد. إذا يا رفاق يمكن إعادة أنفسكم في المواقف التالية مرة واحدة نهائية، دعونا نرى إذا كنا لا نستطيع إضفاء الطابع الرسمي الآن النهج الآخر. في الواقع، فإن أي شخص هناك ترغب في اقتراح وإلا كيف يمكننا أن تذهب عن القيام بذلك؟ دون القذف من العبارات الطنانة أو فرز من الأجوبة التي أضحت معروفة، فقط بشكل حدسي، ماذا يمكن أن نفعل؟ الحضور: (غير مسموع). DAVID J. مالان: نعم. لذلك هناك بعض الحدس كبيرة هناك. الأشياء الجيدة يبدو أن يحدث حتى الآن في علوم الكمبيوتر عندما نقسم وقهر مشكلة تقسيم في نصف ونصف ونصف. وهكذا في الواقع، ونحن يمكن أن تبدأ في فعل ذلك. في واقع الأمر، وهذا سوف يكون، ونحن سوف ترى، واحدة من أفضل الحلول لدينا حتى الان. ولكن دعونا نعود إلى ذلك قبل فترة طويلة. في الواقع، ونحن في طريقنا للقيام في وقت لاحق قليلا هذا الاسبوع. ماذا يمكن أن نفعل لحل هذا؟ لذلك الجميع هنا في لكي تبدو عشوائية. أتعلم؟ بدلا من الذهاب ذهابا وإيابا، ذهابا وإيابا، ذهابا وإيابا في كل مرة، وهذا يشعر وكأنه أنا أفعل الكثير من المشي. لماذا لا أستطيع مجرد بداية في في بداية القائمة، وضعت للتو أربعة حيث تنتمي؟ لذلك اسمحوا لي نفترض للحظة أن قائمتي هي فقط هذا العنصر الأول. يتم فرز أربعة في هذه اللحظة في الوقت المناسب، إذا كان كل ما يهمني هو كل شيء هنا؟ هذا هو نوع من صحيح مسلي، أليس كذلك؟ مثل قائمة تحتوي على رقم واحد، و يتم فرز هذا العدد أربعة واضح. لذلك اسمحوا لي تنص فقط التي تم فرزها هذه القائمة. ولكن الآن لدي بقية من هذه القائمة. وحتى الآن، واجهت اثنين. أين اثنين من الواضح تنتمي فيما يتعلق الأربعة؟ قبل أربعة. لذلك ماذا يمكنني أن أفعل هنا؟ ما أسمك مرة أخرى؟ يوسف: يوسف. DAVID J. مالان: يوسف إذا كنت قد خطوة إلى الوراء لمجرد لحظة مع رقمك. والآن ما الذي يجب القيام به ستيفان هنا؟ دعونا نقل ستيفان أكثر من هنا. والآن، دعونا جوزيف تأتي في هنا. والآن، اسمحوا لي أن الادعاء بأن يتم فرز كل شيء هنا. لذلك، نتيجة مماثلة، ولكن مقاربة مختلفة جذريا. أنا لم ينظر حتى ما هو موجود هناك. أنا فقط تبقى مع العناصر كما انهم سلم لي، والتعامل معهم. وحتى الآن، وأرى رقم ستة. أين رقم ستة تنتمي؟ لدينا اثنين، أربعة، ستة. بالضبط أين هي الآن. لذلك دعونا نترك هذا وحده، والآن يدعون أن هذا الجزء من القائمة يتم فرز الآن. وهكذا، وهذا يشعر الأساس يختلف في ذلك أنا فقط تتحرك من خلال قائمة هنا خطيا، وأنا أبدا مضاعفة الظهر. نعم. حسنا. حتى ثمانية، حيث تنتمي؟ هنا. الكمال. وحتى الآن، واحد. اه اوه. هذا يبدو وكأنه هو ستكون مكلفة. الآن، في الخوارزمية السابقة، تبادلت أنا مجرد مجموعة من الناس. لذلك أنا قد وضعت له على طول الطريق في في البداية، ولكن بعد ذلك انتقل يوسف. ولكن إذا انتقلت يوسف الآن ما يحدث أن أكون مخطئا؟ الآن، لقد نوعا من undone-- لدي اتخذت خطوة واحدة إلى الأمام ثم خطوة واحدة إلى الوراء، لأنه الآن أن جوزيف تكون خارج الترتيب. لذلك دعونا نفعل هذا. اذا كنت قد يستغرق رقم واحد وخطوة إلى الوراء لمجرد لحظة. كيف يمكننا put-- ما كان اسمك مرة أخرى؟ عنان: عنان. DAVID J. مالان: عنان في المكان؟ ما يجب أن يحدث مع الاحترام لاثنين، أربعة، ستة، وثمانية؟ انهم جميعا بحاجة إلى تغيير. إذا كان الأمر كذلك ثمانية ترغب في التحول أولا، ثم ستة، ثم أربعة، ثم اثنين. ثم أنان، إذا كنت تحب أن تأتي إلى هنا، وحسن. ولكن هنا، لدينا فقط نوع من دفع ثمنا في وجهة نظر مختلفة في الخوارزمية. في حين أن آخر مرة مع اختيار نوع، وحتى نوع فقاعة، أنا أمشي ذهابا و إيابا، ذهابا وإيابا، ويضيف بالتأكيد ما يصل في الوقت الحكمة، ومتدرج حرفيا. الإدراج النوع، في البداية وهلة، يبدو انها السوبر أكثر ذكاء، في أنني فقط جعل بطيئا، التقدم التدريجي، ولكن أنا لن هذا ذهابا وإيابا. ولكن اذا كان شخص ما هو في الواقع من النظام، وإشعار كل من عمل أنا فقط كان علي القيام به. واضطررت الى نقل نصف القائمة فقط لإفساح المجال لعدد واحد. لذلك هو نفس المبلغ بعيدا من العمل وبالتالي فإنه يشعر، مجرد نوع مختلف من العمل. فلنتابع. حتى الآن نحن نعلم أن الجميع بين واحد وثمانية يتم فرز. هنا، لا بد لي رقم ثلاثة. إذا كنت ترغب في التقاط رقم ثلاثة، خطوة واحدة الى الوراء. وماذا يا رفاق تحتاج إلى القيام به؟ نعم. بحيث واحد آخر، اثنان، ثلاث خطوات. ثلاث وحدات من الوقت الذي تكلف فقط لي، لذلك أن ثلاثة يمكن أن يصلح الآن. وأخيرا، سبعة. دعونا نمضي قدما ولها كنت تأخذ خطوة إلى الوراء. هذا لن يؤدي الا الى يكلفنا وحدة واحدة من الزمن، ولكن هذا موافق. والآن، والذهاب خمسة ل يكون قليلا أكثر تكلفة. إذا كنت ترغب في التراجع. نحن بحاجة إلى التحرك ثمانية، وسبعة، وستة. وبعد ذلك يتم فرز الآن الجميع. حتى يد كبيرة للمتطوعين لدينا هنا. شكرا جزيلا. [تصفيق] شكرا لكم جميعا. شكرا لكم جميعا. لذلك دعونا نرى الآن كيف تكلفة كل ذلك كان. دعونا النظر ربما أبسط من هذه، نوع فقاعة. وأنا أقول أبسط، فقط ل يمكنك حلها فقط عن طريق بشراهة حل المشكلة البشرى هنا. حل المشكلة البشرى هنا، مرارا وتكرارا ومرة أخرى، وتكرار ما يصل الأوقات التي تحتاج إلى الواقع. هكذا اتضح أن مع نوع فقاعة، حسنا، كم عدد الخطوات التي يجب أن تأخذ على مرور الأول من أن الخوارزمية؟ أنا قد take-- دعونا see-- واحد، اثنان، ثلاثة، أربعة، خمسة، ستة، سبعة. وهناك ثمانية عناصر هنا. لذلك فمن مثل ن ناقص 1 خطوات ل الحصول عليها من بداية القائمة إلى نهاية القائمة. ولكن مع اختيار النوع، أذكر أنني اختيار العناصر مرارا وتكرارا ومرة أخرى هذا هو أصغر، أنا وضعه في المكان، ولكن بعد ذلك أنا لست أبحث رائي مرة أخرى. لذلك اعتقد انها قليلا أكثر وضوحا ثم أن المرة الأولى، وأنا قد يجب أن تتخذ جميع الخطوات ن ناقص 1 العثور على أصغر عنصر. ثم وضعت لهم في المكان، وأنا طرد كل من كان هنا سابقا. ولكن بعد ذلك لم يكن لديك ل مواصلة البحث في هذا العنصر، لأنني أعلم أنها ل بالفعل أصغر. وحتى الآن، ويمكنني أن ننظر فقط سبعة العناصر، ثم ستة عناصر، ثم خمسة عناصر، ثم أربعة عناصر. وحتى رياضيا، إذا كان n هو عدد العناصر أو أرقام التي بدأنا مع، يمكنك أن تتخيل أن هذا هو نفس ن ناقص 1، بالإضافة إلى ن ناقص 2 خطوات، بالإضافة إلى ن ناقص 3 خطوات، بالإضافة إلى ن ناقص 4 خطوات، كل الطريق إلى خطوة واحدة فقط. وأنا في بلدي الماضي شخص. وإذا كنت أذكر أن الكثير احصائيات الكتب أو كتب الرياضيات لديك تلك الصيغ على غلاف الخلفي أو الأمامي منها، اتضح أن هذه السلسلة يمكن التعبير ببساطة أكثر مرات ن ن ناقص 1 على 2. وأنها على ما يرام إذا كان هذا لا في طليعة من عقلك. ولكن هذا هو الواقع الحقيقي. هذا هو مجرد وسيلة أبسط من كتابة هذا التقرير. ثم إذا كنت تعتقد العودة إلى المدارس الابتدائية، عند بدء تشغيل فقط بضرب الامور، وهذا بطبيعة الحال، هو مجرد ن مربع ناقص ن مقسوما على 2. كل ما قمت به هو توسيع التعبيرات هناك. وذلك دعونا إعادة كتابة هذا بشكل مختلف قليلا. وهذا ما ن التربيعية مقسوما على 2 ناقص ن / 2. ذلك مرة أخرى، أنا مجرد نوع من تطبيق قواعد ببعض العمليات الحسابية هناك. ولكن لاحظ الآن أن مصطلح أكبر في هذا التعبير، إذا جاز التعبير، غير أن ن تربيع. لذلك نعم، انها ن التربيعية مقسوما على 2، ناقص ن / 2. ولكن بصفة عامة، إذا كان n هو ستكون قيمة كبيرة، انا ذاهب الى الادعاء بأن ن تربيع سيكون العامل المهيمن. انها مجرد سيكون المساهم الأكبر إلى عدد من الخطوات من ن / 2. فماذا يعني هذا؟ دعونا نحاول مثال بسيط، حتى على الرغم من أن الرياضيات يحصل على القليل كبيرة. لذلك افترض كان لدينا 1000000 الناس على خشبة المسرح، أو 1000000 الأمور أننا نريد لفرز. دعونا سد مليون إلى ذلك بالضبط صيغة لمعرفة عدد الخطوات التي تتخذها مجموعه فرز مليون العناصر باستخدام يقول، اختيار نوع. لذلك سيكون لدينا نفس الصيغة كما كان من قبل. فما استقاموا لكم فاستقيموا سد مليون، بحيث أحصل مليون التربيعية مقسوما على 2، ناقص مليون مقسوما على 2. إذا فعلت ذلك الرياضيات مقدما هنا، لدينا 500 مليار ناقص 500،000، التي يعطينا 499999500000، وهي جميلة كبيرة الرتق. في الواقع، إذا ما قورنت الآن 499000000000، 999000000، 500،000 ضد لدينا القيمة الأصلية، 500 مليار، حتى انها لعنة وثيق. الصحيح؟ ن التربيعية مقسوما على 2 يعطي us-- أو بالأحرى، ن التربيعية مقسوما على 2 قدم لنا 500 مليار. هذا الرتق جميلة قريبة ل499999500000، وهو ما يعني طرح من 500،000، أو بصورة أعم، طرح قبالة ن التربيعية، وليس حقا صفقة كبيرة. ن تربيع يجعل هذه تنمو الأرقام بسرعة حقا. الآن، وهذا هو المهم فقط بقدر ونحن كعلماء الكمبيوتر، عموما لن تهتم كثيرا حول الفروق الدقيقة في هذه الصيغ وبالضبط ما إجابات دقيقة و. نحن نهتم ذلك فحسب، وأنت تعرف لماذا؟ في نهاية اليوم، وهذه الصيغة هو بناء على أمر من ن المربعة. نعم، نحن قسمة 2 في هناك. نعم، نحن طرح قبالة ن ناقص 2. ولكن في نهاية المطاف، فإن مصطلح هذا يؤلمنا حقا ويكلفنا الكثير من الخطوات هو أن مصطلح مربع. وماذا في ذلك عالم الكمبيوتر وتنوي القيام به بشكل عام وتجاهل كل تلك شروط أجل الصغيرة، ومجرد إلقاء نظرة على واحد تساهم أكثر من غيرها في التكلفة. وهذا هو لطيف، لأننا يمكن الحديث الآن في أكبر بكثير عمومية حول الخوارزميات، ويمكن مقارنتها. والحقيقة أنني باستخدام هذه O غير المتعمد. عندما أقول على النظام من، وأنا على وجه التحديد في اشارة الى شيء دعا كبير O. وكبير O هو تدوين أن الكمبيوتر عالم يستخدم لوصف الحد الأعلى على شيء. حتى إذا كنت أقول إن خوارزمية في O كبير من ن تربيع، كما اقترحت مجرد لحظة قبل، وهذا يعني هذا من حيث تسييرها الوقت أو كفاءته، فإنه يأخذ على النظام ن مربع الخطوات. ربما أكثر من ذلك، وربما أقل من ذلك. ولكن هذا بناء على أمر من ن تربيع. وهذا هو الحد الأعلى. انها لن تكون أكثر إيلاما من ذلك. انها لن تكون ن مكعبة، أو 2 لن، أو شيء أكبر من ذلك بكثير. هذا هو الحد الأعلى على أي ان التكلفة. فنظرا لهذا، دعونا النظر في مجرد أمثلة قليلة. وهذا هو مجرد قائمة محدودة أوقات شائعة جدا تشغيل لالخوارزميات التي من المفترض أن تكون توضيحية لبعض الأشياء التي قمت رأينا بالفعل. هكذا على سبيل المثال، في حالة اختيار نوع، ما أنا مدعيا هنا يشغل هذا النوع اختيار ل الوقت هو بناء على أمر من ن تربيع. في أسوأ الحالات، وانا ذاهب ل مجموعة كاملة من أرقام عشوائية هنا. وكما رأينا رياضيا، إذا كنت الحفاظ على المشي من خلال القائمة، من خلال قائمة، واختيار بجوار أصغر العنصر مرة أخرى ومرة ​​أخرى، إذا أنا إرسال الواقع أسفل كل الخطوات أنا أخذ كما اقترحت formulaically قبل ذلك، هو بناء على أمر من ن التربيعية الخطوات التي أنا أخذ. واتضح أن فقاعة نوع ونوع الإدراج مثلما هي بطيئة في أسوأ الحالات. تنظر، على سبيل المثال، الإدراج النوع، الخوارزمية الأخيرة جدا تعاملنا مع، والتي كان لنا أن ننظر في العنصر، ثم أدخله حيث تنتمي. ثم نظرنا إلى العنصر التالي، وإدراجها حيث تنتمي. حتى النظر في أفضل سيناريو ممكن. لنفترض أنني قد المتطوعين بلدي يصطف حرفيا مثل هذا، واحد من خلال ثمانية، فرز بالفعل. عدد الخطوات هي نوع الإدراج يجري اتخاذها لفرز ثمانية أشخاص، إذا وصولهم على خشبة المسرح يبحث مثل هذا؟ ثمانية أشخاص فرز بالفعل. وأنا أستخدم الإدراج النوع. أن آخر من الخوارزميات. حسنا، دعونا يعيدون تمثيل بسرعة حقيقية. حتى لو كنت تبدأ هنا، أرى واحدة. حيث يمكن للمرء تنتمي؟ وهو ينتمي هنا. أرى اثنين. أين اثنين تنتمي؟ هنا. أرى أن هناك ثلاثة. أين الثلاثة تنتمي؟ هنا. أرى الأربعة. هنا. خمسة، ستة، سبعة، ثمانية. ليس هناك سبب لتكرار نفسي. وهكذا، كيف خطوات كثيرة غير أنه من حيث ن؟ انها بناء على أمر من ن الخطوات، أليس كذلك؟ ن ناقص 1. ولكن أخذت عددا الخطي من الخطوات، والآن أنا فعلت. ولهذا أفضل الأحوال، وإن كان. ماذا عن أسوأ الحالات؟ ما ثمانية كانوا هناك، وسبعة كانوا هناك، وكان واحد واثنين أكثر من هنا، لذلك أن القائمة تم عكس حقا؟ حسنا، ما يحدث في الواقع إذا كان هذا هو العدد؟ ونحن سوف نفعل مجرد بضعة أمثلة. ماذا لو، في الواقع، وعدد ثمانية هنا، ويصيح number--. ولكن ماذا لو، في الواقع، فإن عدد ثمانية هو كل وسيلة أكثر من هنا، وأنا باستخدام الإدراج الفرز؟ حسنا. أزعم في هذه اللحظة انها في المكان. ولكن الآن، seven-- أين سبعة تذهب؟ بطبيعة الحال، فإنه يذهب أكثر من هنا. لذلك يجب أن تتحرك ثمانية على مكان واحد. الآن ستة، أين تذهب؟ حسنا، كل الحق. الآن، لا بد لي من نقل أكثر من ثمانية مكان، وسبعة على المكان، وبعد ذلك صوت نزول المطر بانخفاض ستة. لذا في المرة الأولى، فإنه التكلفة لي خطوة واحدة لاصلاح الامور، ثم كلفني ذلك خطوتين لإصلاح الأمور. عدد الخطوات هو عليه يجري اتخاذها لإصلاح الأشياء لوضع خمسة في المكان المناسب؟ ثلاثة. لأنه الآن لا بد لي من نقل واحد، اثنان، ثلاثة. عدد الخطوات هو الذهاب الى اتخاذ لوضع أربعة في المكان المناسب؟ 4 + 5، بالإضافة إلى 6، بالإضافة إلى 7. وحتى انها متطابقة رياضيا ل ما وصفنا لاختيار نوع. لدينا هذه السلسلة هذا ما المتزايد فقط. 1 زائد 2 زائد 3 زائد 4، أو على العكس، 7 زائد 6 بالإضافة إلى 5 زائد 4 يصل لهذا اليوم التربيعية الأغراض بناء على أمر من ن. لذلك اسمحوا لي أيضا أن تنص فقاعة النوع هو أيضا في ن تربيع. لأنه مع فقاعة نوع، كل مرة أذهب من خلال القائمة، أنا أخذ تقريبا كيف العديد من الخطوات؟ في كل مرة أنا حرفيا المشي من هناك إلى هناك؟ تقريبا ن الخطوات. ولكن كم مرة قد I بحاجة للذهاب من خلال القائمة؟ حسنا، تقريبا ن الوقت. ربما ن ناقص 1، ولكن تقريبا ن مرات. حسنا، لماذا؟ حسنا، مع فقاعة نوع، إذا نبدأ مع فقاعة نوع، مع قائمة في أسوأ ممكن الوضع الذي هو مرة أخرى تماما الى الوراء، ما الذي سيحدث؟ ذهبت من خلال القائمة، وعدد واحد ينتمي كل وسيلة هناك. ولكن مع فقاعة النوع، إلى أي مدى لا أحد الانتقال الأول تمريرة بلدي من خلال القائمة؟ كم عدد البقع انه لا يحصل أقرب إلى المكان الصحيح؟ واحد فقط. حتى إذا كنت نوع العقل من خلال هذا، في كل مرة من خلال هذه الخوارزمية، أخذ تقريبا ن الخطوات داود. ولكن كيف عدة تمريرات من خلال القائمة عليه ذاهب الى اتخاذ لأحد أن فقاعة إلى اليسار حيث تنتمي؟ وقد حصل على التحرك مثل، ن المساحات بهذه الطريقة. حتى لمجرد القيام فرز القائمة، لا بد لي من المشي ذهابا وإيابا ن مرات. وفي كل مرة، وأنا أبحث في ن العناصر. حتى لا ن ن الأشياء مرات على ترتيب ن تربيع. الآن، وسنرى في بعض من السراويل التي هي جزء لا يتجزأ في المشكلة القادمة CS50 ل مجموعة، نهج آخر في هذه، لكنه الآن، دعونا النظر فقط في بعض الأحيان الأخرى على التوالي، خصوصا إذا تأخذ تلك الفرز قليلا من الوقت لتغرق في. ما هو خوارزمية رأيناه بالفعل أن يأخذ على ترتيب ن الخطوات؟ ما ينبغي أن تتخذ عددا الخطي من الخطوات التي شهدناها حتى الآن؟ ما هذا؟ البحث في دليل الهاتف. الخوارزمية الأولى. الصحيح؟ حيث نحن خطيا البحث عن مايك سميث؟ في الواقع. من أسبوع الصفر، وعندما بدأت تحويل صفحة واحدة في وقت واحد، حتى وقلت أنه كان من نوع خوارزمية الشعور الخطية، وكان لدينا تلك الصورة على المجلس مع الخط الأحمر على التوالي والأصفر على التوالي الخط، كانت تلك في الواقع الخوارزميات التي هي في O كبير من ن. لأن للعثور على مايك سميث في الهاتف كتاب صفحات ن، في أسوأ الأحوال، قد يأخذني ن الخطوات. ماذا عن أخذ الحضور؟ واحد اثنان ثلاثة اربعة خمسة ستة. ما هو وقت تشغيل هذه خوارزمية لأخذ الحضور؟ O كبير من ن، لأنه في نظرية I يجب أن نشير الجميع في الغرفة. الآن بوصفها جانبا، ماذا عن الأمثل آخرين من الأسبوع الصفر؟ اثنين، أربعة، ستة، ثمانية، 10، 12. عالم الكمبيوتر سوف ندرك، انتظر لحظة، وهذا بناء على أمر من تنقسم ن من قبل اثنين من الخطوات. الصحيح؟ لأنني أقوم بعمل شخصين في وقت واحد. ولكن ونحن في طريقنا إلى تجاهل هذه المصطلحات أجل الدنيا، ونحن ذاهبون لمجرد رمي بعيدا القسمة على 2، ونقول فقط يا كبير من ن لذلك خوارزمية كذلك. مذا عن هذه؟ سنقوم تخطي بعض من هذه، ولكن ما وكانت خوارزمية الذي كان سجل من ن؟ أن أخذت ما يقرب من تسجيل ن الخطوات؟ وفرق تسد. بالضبط. كما في المثال دليل الهاتف في الأسبوع صفر و في وقت سابق اليوم، حيث قسمنا المشكلة مرة أخرى، ومرة ​​أخرى ومرة ​​أخرى. تعادلنا على المجلس في الأسبوع الصفر بمثابة الخط الأخضر المنحني، وقال لنا أنه كان في ذلك اليوم خوارزمية لوغاريتمي. وبالفعل، فإن عدد من الخطوات التي يلزم لأداء فرق تسد، أو البحث الثنائي كما سنبدأ الدعوة إليها، كما هو الحال في دفتر الهاتف، هو بناء على أمر من السجل والخطوات. وهذا هو قليلا من واحد غريب. ما يأخذ خطوة واحدة، أو بشكل أكثر تحديدا عدد ثابت من الخطوات؟ ربما حان اثنين، وربما انها الثلاث، ولكن عالم الكمبيوتر فقط يبسط أنها O كبيرا من 1، بعض عدد ثابت من الخطوات. ما هو شيء يمكن أن تفعل ذلك يأخذ عدد ثابت من الخطوات؟ ما هو وقت تشغيل التصفيق؟ وقت ثابت. الصحيح؟ مثل، ما هو وقت تشغيل فعل أي شيء يأخذ واحد فقط العملية، مثل طباعة F مرحبا العالم. يمكن القول أن ذلك وقت ثابت، ما لم أقل حالة الزاوية مع الطباعة F، ما قد إدارة الوقت الطباعة F يكون في الواقع؟ ولماذا؟ ما هو ن القياس في هذه الحالة؟ الحضور: (غير مسموع). DAVID J. مالان: بالضبط. عدد الأحرف نريد للطباعة. لذلك فمن حساسة للسياق ذاته. اليوم، لقد تم التركيز كثيرا على الحروف والأرقام هنا على متن الطائرة. ولكن قد يكون أيضا الأحرف في سلسلة الفعلية. هكذا اتضح هناك أخرى الإجراء الذي سيبدأ مبالين، وهذا هو عكس ذلك من يا كبير، إذا جاز التعبير. هذا التدوين أوميغا. في حين O الكبير يعني ما هو، و الحد الأعلى في الوقت المحدد الجري؟ الحد الأقصى، وكم من الوقت قد يستغرق شيئا؟ آسف Omega-- هذا يبقي القادمة up-- هو العكس من ذلك، حيث انها الأدنى على مقدار الوقت شيئا ما قد تتخذ. هكذا. على سبيل المثال، ما هو خوارزمية أن تتخذ خطوات دائما مربع ن؟ حسنا، واحدة من خوارزميات رأيناه اليوم، في الواقع، قد يكون ذلك أيضا. اختيار نوع. اختيار هو نوع من الغباء جدا. حتى لو كان algorithm-- آسف، حتى إذا تم فرز مجموعة بالفعل، اختيار النوع هو الذهاب الى الحفاظ على المشي من خلال قائمة للتأكد من أنها أصغر العنصر مرة أخرى ومرة ​​أخرى ومرة ​​أخرى. وعلى الرغم من أن البشر في جمهور يعرفون ذلك، انتظر لحظة، مررت بالفعل أصغر عنصر، الكمبيوتر لا يعرف أن حتى يبدو على طول الطريق من خلال القائمة. وبالمثل، فإن الأدنى أن ويمكن أيضا أن تؤخذ بعين الاعتبار قد يكون الزمن الخطي. كم من الوقت يستغرق ل عناصر نوع ن في أفضل حالة استخدام شيء مثل فقاعة الفرز؟ لنفترض يتم فرز قائمتك بالفعل. قلنا فقاعة نوع يأخذ على ترتيب ن تربيع الخطوات. ولكن ما اذا كان تم فرزها بالفعل؟ ماذا لو كنت أدرك بعد مرور واحد من خلال مجموعة التي قمت بها لا مقايضة؟ هل تحتاج إلى الحفاظ على صنع أكثر يمر؟ لا. لذلك الأدنى على فقاعة الفرز قد يقال أن تكون خطية. أوميغا ن. ويمكننا أن ننظر في البعض الآخر من هذه كذلك. لذلك دعونا نلقي نظرة سريعة في مجرد التصور هنا لنرى كيف يمكن لهذه يميزوا أنفسهم. انا ذاهب الى النزول هنا في هذا الصفحة التي تتوفر على موقع C50، و لكنه لن يكون الألم للحصول على العمل، لأنه يستخدم تقنية تسمى تطبيقات جافا، وهو معتمد بشكل كبير هذه الأيام، على الأقل الكروم وبعض الآخرين. واسمحوا لي أن المضي قدما وتسريع هذا حتى وشرح ما يحدث. وهذا دليل فقاعة النوع، الخوارزمية الأولى ونحن ننظر في. وانها التصور في أن كل من هذه القضبان تمثل عددا. وأكبر شريط، وأكبر عدد. أصغر شريط، أصغر رقم. وماذا يمكن أن ترى بالعين المجردة، حتى رغم أن هذا يجري بسرعة فائقة، غير أن شريط أحمر هو مثلي، المشي ذهابا وإيابا تحديد المشاكل. يمكنك أن ترى أن العناصر أكبر ومحتدما بالفعل ما يصل إلى الحق، والعناصر الصغيرة السبب تظهر على السطح إلى اليسار. وإلى هنا، واذا كنا ننظر في الواقع عن كثب، نستطيع أن نعول الواقع عدد من المقارنات ومقايضة التي تبذل. ولكن بدلا من ذلك، دعونا ننظر في الخوارزمية الثانية ونحن ننظر في وقت سابق مع دينا المتطوعين، واختيار نوع. بصريا، لديها تأثير مختلف جدا. لكنه، مرة أخرى، بديهية جدا، في أن نبقي اختيار بجوار أصغر عنصر، وحصلنا على الحظ قليلا. ورأى أن الأساس أسرع. ولكن إذا هربنا هذا مرارا وتكرارا ومرة أخرى مع الكثير من المدخلات، كنا نرى أنه من الواقع لا يزال في O كبير من ن المربعة. دعونا نفعل واحد آخر واحد هنا، الإدراج النوع، التي كانت الخوارزمية الثالثة ونحن ننظر في واستدعاء أن هذا واحد يتعامل مع العناصر كما أنه واجه لهم، ولكن بعد ذلك ربما التحولات الأمور لجعل غرفة، إدراج العناصر التي تنتمي إليها. وهذا ينتهي جدا حتى إعطاء النتيجة النهائية. الآن كل ثلاثة من هذه شعر سريعة جدا. وبالفعل، ركضت لهم في مقطع جيدة. لكن في الأساس، انهم جميعا فظيع جدا، أن نكون صادقين. الآن كل هذه الخوارزميات وبالتالي التي تعمل في O كبير من ن تربيع تأخذ قدرا كبيرا من الوقت لتشغيل في نهاية المطاف. وبالفعل، يمكننا أن نرى ويشعر هذا أخيرا إذا كنت سحب ما يصل هذا العرض الثالث والأخير. هذا هو آخر تصور ما يجري لإظهار فقاعة فرز على اليسار، نوع التحديد في الوسط وشيء، باعتبارها واحدة من لدينا ومن ناحية تثير اقترحت في وقت سابق، دمج النوع على اليمين. A فرق تسد استراتيجية على اليمين. وهذا هو، في الواقع، ما نحن سوف ننظر في يوم الاربعاء. ولكن لندع الوقت هذه بالتوازي. انها تقريبا نفس العدد من العناصر، كل يعمل في نفس الوقت. فقاعة نوع مقابل اختيار نوع مقابل دمج النوع. الآن، انهم جميعا تشغيل من الناحية النظرية في نفس الوقت. هو وحدة المعالجة المركزية على التوالي في بنفس السرعة، ولكنك يمكن أن نرى كيف مملة هذا هو بسرعة جدا سوف تصبح، ومدى سرعة عندما نحن حقن قليلا من أسبوع خوارزميات الصفر ويمكن نحن تسريع الامور. والآن دعونا نقارن هذه في شكل آخر واحد. انا ذاهب الى المضي قدما إلى موقع الويب CS50، حيث لدينا هذا الرابط النهائي لهذا اليوم، حيث شخص ما على شبكة الإنترنت يرجى وضع معا شريط فيديو يلتقط ما الفرز مختلفة خوارزميات الصوت مثل. هذا هو الإدراج النوع. [تنبيه] حيث كنت التقدم بطلب تردد استنادا إلى ارتفاع شريط شريط. هذا هو فقاعة النوع. [تنبيه مشوه] الخروج المقبل is-- القادمة يصل المقبل الفرز اختيار is--، حيث مرة أخرى، ونحن اختيار أصغر عنصر المقبل، ويمكننا أن نرى ذلك تزايد من اليسار الى اليمين. دمج النوع، بعيدا الفائز لدينا بذلك اليوم. لاحظ كيف انها تقسيم الأشياء إلى (غير مسموع) نصف وأرباع. نوع غنوم، التي لدينا لا تحدث عن ويخلق بصريا وaudally قليلا من شكل مختلف والصوت. ذهابا وإيابا، تنظيف الامور. كما تحقق heapsort على موقع الويب هذا الرجل. وهذا كل شيء. سوف نرى لك في المرة القادمة. [الرنين AND MUSIC]